Research On Fast Algorithms Of Discrete Cosine Transform

DCT (Discrete Cosine Transform) and IDCT (Inverse Discrete Cosine Transform) are widely used in video/image CODEC, such as MEPG-1, MPEG-2, and MPEG-4 part 2, which require the implementation of integer 8x8 DCT and IDCT. And Modified DCT and IDCT (MDCT and IMDCT) have also been adopted in several international standards and commercial products, such as MPEG-1, MPEG-2, and AC-3 for audio coding. Hower, the computional complexiey of existing fast algorithsis is relatively high. And computational precision is low which lead to"Drift"problem. In this thesis, we propose new IDCT fast algorithms and MDCT/IMDCT fast algorithms which performace better in computational complexity and precision.In this thesis I introduce the definition of DCT/IDCT and analysis two classical algorithms: B.G. Lee's IDCT algorithm and AAN's IDCT algorithm. Then, based on these two algorithms, I replace the multiplication operators in original algorithms with addition and shift operators to realize the fix-point and multiplier-free computation of IDCT, respectively. Due to the absence of the multiplication operators, these improved algorithms take less time to complete the computation than the classical algorithm. Among of them, AAN algorithm just need 46 addition and 20 shift operators to complete 1-D IDCT and 737 addition and 320 shift operators to complete 2-D IDCT. The error of the algorithm is less than 1/20 error in IEEE 1180 and ISO/IEC 23002-1 specifications. These novel fast algorithms obtain the sound balance between computational complexity and precision and are suitable to be applied to mobile device.An efficient fast algorithm of the forward MDCT is presented. We improve the flow graph of Britanak's algorithm which employs discrete cosine transform of type II (DCT-II) and discrete sine transform of type II (DST-II) to compute MDCT/IMDCT. In order to obtain more precision, we change the location of the scaling factors and reduce the amount of multiplication operators. We test our novel algorithm and other existing algorithms (such as T. K. Truong'algorithm and Vladimir Nikolajevic's algorithm). These algorithms are used to encode some randam data and decode them, and test the SNR (Signal Noise Rate) between recoved data and original data. The result of the test is that our algorithm's SNR is higher than other existing algorithms'. This algorithm is suitable for N≠2 MDCT/IMDCT, and is used in CODEC in G.711 wide-brand scaling lay.