| This thesis proposes effective methods to convert fast DCT algorithms, including 1-D DCT, row column 2-D DCT, and direct 2-D DCT, into their multiplierless versions. The basic conversion techniques used include: (1) to convert any butterfly structures in a DCT algorithm into lifting steps; (2) to use an optimized configuration of non-zero digits to approximate the coefficients so that multiplications can be converted into shift and add operations. We devised an effective algorithm based on the remainder theorem for finding an MSD representation, with minimum wordlength, of any float constant. As the approximation errors of different coefficients often affect the MSE of an approximated fast DCT algorithm differently, we developed an efficient search algorithm for finding an optimized configuration of non-zero digits for approximating each of the coefficients with an appropriate number of non-zero signed digits so that the approximated algorithm could achieve a minimum MSE.;In this thesis, we also investigated various conversion techniques concerning how to improve the performance of multiplierless fast 1-D DCT, and row column 2-D DCT fast algorithms. We have explored a number of choices of conversion techniques having an impact on the performance of multiplierless fast DCT algorithms. Based on our analytical analysis, and experiment results, we have the following findings: (1) a transform based on a reversible inverse generally performs better than a version based on a traditional inverse; (2) a transform with a delayed uniform normalization step can achieve a much better performance; (3) a lifting structure transform can usually achieve better performance than its non-lifting structure version; (4) using an optimized configuration of non-zero digits to approximate the coefficients can help to achieve a much better performance than using a non-optimized configuration.;When compared to those multiplierless fast 1-D DCT algorithms developed by others, the multiplierless 1-D DCT fast algorithms developed via our proposed conversion method can achieve similar or better performance in terms of MSE and PSNR. While the published methods were use to approximate only the kernels of the 1-D DCT fast algorithms with butterfly structures, our proposed methods can approximate both the kernels and the normalization steps of any 1-D DCT, row column 2-D DCT, and direct 2-D DCT fast algorithms. |
