A Novel Recursive Multiplierless Algorithm for 2-D DCT

Authors: V.K.Ananthashayana, Geetha.K.S

Abstract:

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.

Keywords: DCT, Multilplerless, Ramanujan Number, Recursive.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1056685

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