Discrete Cosine Transform

Created by Mauricio Alvarez
Last update: 06.11.2003

Fast 1D-DCT Algorithms

Algorithm	Year	Mult.-1D*	Add/Sub-1D*	Mult-2D **	Add/Sub-2D**	Implementation
Reference 1D-DCT N. Ahmed, T. Natarjan and K. R. Rao. [1]	1974	64	64	1024	1024	MOM
W.-H. Chen H. Smith and S.C. Fralick. [2]	1977	16	26	224	416
W.-H. Chen H. Smith and S.C. Fralick. Fast	1977	13	29	176	464	Scalar MPEG encoding Altivec [14]
Z. Wang. [3]	1984	13	29
B. Lee. [4]	1984	12	29
M. Vetterli and N. Nussbaumer. [5]	1984	12	29
N. Suheiro and M. Hatori. [6]	1986	12	29
H. S. Hou. [7]	1987	12	29
Y. Arai, T. Agui and M. Nakajima. [8]	1988	13	29	144	464	MMX/SSE [15] SSE2[17]
Loeffler, Ligtengerb and Moschytz. [9]	1988	12	32	224	416
Loeffler, Ligtengerb and Moschytz. Fast.	1989	11	29	176	464	Scalar JPEG encoding MMX.[16]
Artieri and Colavin. [10]	1990

*Operation per 8x8 element 1D-DCT

Fast 2D-DCT Algorithms

Algorithm	Year	Mult-2D.**	Add/Sub-2D**	Implementation
Reference 2D DCT		4096	4096
Kamangar and Rao. [12]	1982	128	430
]Cho and Lee (2D).[11]	1993	96	466
Feig and Winograd[13]	1992	94	454

** Operations per 8x8 2D-DCT

References

[1] N. Ahmed, T. Natarajan, and K. R. Rao, Discrete Cosine Transform, IEEE. Trans. Computer, Vol C-23, pp. 90-93, Jan 1974
[2] W.-H. Chen, C.H. Smith, and S.C. Fralick, "A Fast Algorithm for the Discrete Cosine Transform," IEEE Trans. on Communications, Vol. COM25, No. 9, Sep. 1977, pp. 1004-9. 183
[3] Z. Wang, "Fast algorithms for the discrete W transform and for the discrete Fourier transform," IEEE Trans. Acoust, Speech, Signal Processing, vol. ASSP-32, pp. 803--816, Aug. 1984.
[4]. B. G. Lee, "A new algorithm for computing the discrete cosine transform," IEEE Trans. Acoust., Speech, Signal Processing, Vol. ASSP-32, Dec. 1984, pp. 1243-1245.
[5]. Vetterli, M. and H. Nussbaumer, "Simple FFT and DCT Algorithms with Reduced Number of Operations", Signal Processing, vol. 6, pp. 267-278, Aug 1984.
[6]. N. Suehiro, M. Hateri: "Fast Algorithms for the DFT and other sinusoidal transforms", IEEE Transactions on Acous- tic, Signal, and Speech Processing, Vol. 34, No. 6, pp. 642- 644, 1986.
[7] H. S. Hou, "A fast recursive algorithm for computing the discrete cosine transform," IEEE Trans. Acoust., Speech, Signal Process. 6(10), 1455-1461 (1987).
[8]. Y. Arai, T. Agui, and M. Nakajima, "A Fast DCT-SQ Scheme for Images," Trans. of the IEICE, vol. E-71, no. 11, pp. 1095-1097, Nov. 1988.
[9]. C. Loeffler, A. Ligtenberg, and G. Moschytz. Practical Fast 1D DCT Algorithms With 11 Multiplications. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, pages 988--991, 1989.
[10]. A. Artieri, O. Colavin, "A chip set core for image compression," IEEE Trans. on Consumer Electronics, vol. 36, pp.395-402, Aug. 1990
[11] N. I. Cho, I. D. Yun, and S. U. Lee. On the regular structure for the fast 2-D DCT algorithm. IEEE Trans. Circuits and Syst., 40(4):259--266, April 1993.
[12] Kamanagar, F. A. and K. R. Rao, "Fast Algorithms for the 2-D Discrete Cosine Transform", IEEE Trans. On Computers, vol. C-31, no. 9, pp. 899-906, Sep 1982.
[13] E. Feig and S. Winograd, "Fast Algorithms for the Discrete Cosine Transform," IEEE Trans. on Signal Processing, vol. 40, no. 9, pp. 2174--2193, 1992.
[14]. S. Li, J. Zhang, X. Zhang, An Implementation of 2D IDCT Using Altivec, Proceedings of ICSP'02. pp. 17-20. 2002.
[15]. A Fast Precise Implementation of 8x8 Discrete Cosine Transform Using the Streaming SIMD Extensions and Intel® MMX™ Instructions, Intel Application Note. AP-922. 1999.
[16]. Using Streaming SIMD Extensions in a Fast DCT Algorithm for MPEG Encoding, Intel Application Note. AP-817. 1999.
[17] Using the Pentium 4 Processor SSE2 Instruction Set to Implement an Inverse Discrete Cosine Transform, Intel Application Note AP-945. 2000.