A Novel Recursive Multiplierless Algorithm for 2-D DCT

In this paper, a recursive algorithm for the computation of 2-D DCT using Ramanujan Numbers is proposed. With this algorithm, the floating-point multiplication is completely eliminated and hence the multiplierless algorithm can be implemented using shifts and additions only. The orthogonality of the recursive kernel is well maintained through matrix factorization to reduce the computational complexity. The inherent parallel structure yields simpler programming and hardware implementation and provides log 1 2 3 2 N N-N+ additions and N N 2 log 2 shifts which is very much less complex when compared to other recent multiplierless algorithms.

Authors:

• V.K.Ananthashayana
• Geetha.K.S

Keywords:

• DCT
• Multilplerless
• Ramanujan Number
• Recursive.

References:

[1] K.R.Rao, P.Yip, "Discreate Cosine Transform Algorithms, Advantages
Applications". New York: Academic 1990.
[2] H.S. Hou, "A Fast Recursive Algorithms for Computing the Discrete
Cosine Transform". IEEE Trans. Acoust., Speech, Signal Processing,
Vol.35, pp 1455-1461, Oct 1987.
[3] N.I.Cho, S.U.Lee, "A Fast 4X4 DCT Algorithm for the Recursive 2-D
DCT". IEEE Trans. Signal Processing, Vol.40, pp 2166-2173. Sep
1992.
[4] C.W.Kok, "Faast Algorithm for Computing Discrete Cosine
Transforms". IEEE Trans. Signal Processing, Vol.45, No.3, pp 757-760.
March 1977.
[5] T.Tran,"The BinDCT: Fast multiplier less approximation of the DCT".
IEEE Signal Proc.141-14 (2000).
[6] Yonghong Zeng, Lizhi Cheng, Guoan Bi, and Alex C. Kot, "Integer
DCT-s and Fast Algorithms".IEEE Transactions on Signal Processing
Vol 49, No.11, November 2001.
[7] Xu Hui, Cheng Lizhi,"An Integer Hierarchy:Lapped Biorthogonal
Transform via Lifting Steps and Application in Image Coding". Proc.
ICSP-02, 2002.
[8] Z.D.Wang, "Reconsideration of ÔÇÿA Fast Computational Algorithm for
the Discrete Cosine Transform-," . IEEE Trans. Comm., Vol.COM:31,
pp121-123. Jan 1983.
[9] W.H. Chen, C.H. Smith, and S.C.Fralick, "A Fast Computational
Algorithm for the Discrete Cosine Transform". IEEE Trans. Comm.
Vol.COM:25, No.9, pp 1004-1009. Sep 1997.
[10] Nirdosh Bhatnagar, "On computation of certain discrete Fourier
transforms using binary calculus".Signal Processing-Elsevier Vol
43,1995
[11] Nirdosh Bhatnagar, "DFT computation using shift and addition
operations".IEEE Int.Conf. on ASSP, Georgia, 1996.
[12] V.K. Ananthashayana, K. Chidanandagowda, "Fast Discrete Cosine
Transform using Ramanujan Numbers and its application to image
compression", Int. Conf. On Combinatories, Statistics, pattern
recognition and related areas, University of Mysore, Mysore, India,
pp.30, Dec. 28-30, 1998.
[13] Geetha.K.S, V.K.Ananthashayana,"Fast Multiplierless Recursive
transforms using Ramanujan Numbers".Proc. IEEE International
Conference on Multimedia, Signal Processing and Communication
Technologies, Aligarh, India. March 2008.
[14] Y.Zeng, L.Cheng,"Integer DCTs and Fast Algorithms"., IEEE Trans. on
Signal Processing, Vol.49,No.11, November 2001.
[15] Chih-Peng, Fan, "Fast 2-Dimensional 4X4 Forward Integer Transform
Implementation for H.264/AVC". IEEE Trans. on Circuits and systems.
Vol.53, Issue 3, pp174-177. March 2006.
[16] Ji Xiuhua, Z. Caiming, W.Yanling, "Fast Algorithm of the 2-D 4X4
Inverse Integer Transform for H.264/AVC". 0-7695-2882-1/07, IEEE
2007