Fast computational structures for an efficient implementation of the complete TDAC analysis/synthesis MDCT/MDST filter banks. (English) Zbl 1178.94038

Summary: A new fast computational structure identical both for the forward and backward modified discrete cosine/sine transform (MDCT/MDST) computation is described. It is the result of a systematic construction of a fast algorithm for an efficient implementation of the complete time domain aliasing cancellation (TDAC) analysis/synthesis MDCT/MDST filter banks. It is shown that the same computational structure can be used both for the encoder and the decoder, thus significantly reducing design time and resources. The corresponding generalized signal flow graph is regular and defines new sparse matrix factorizations of the discrete cosine transform of type IV (DCT-IV) and MDCT/MDST matrices. The identical fast MDCT computational structure provides an efficient implementation of the MDCT in MPEG layer III (MP3) audio coding and the Dolby Labs AC-3 codec. All steps to derive the computational structure are described in detail, and to put them into perspective a comprehensive list of references classified into categories is provided covering new research results achieved in the time period 1999-2008 in theoretical and practical developments of TDAC analysis/synthesis MDCT/MDST filter banks (general mathematical, symmetry and special properties, fast MDCT/MDST algorithms and efficient software/hardware implementations of the MDCT in MP3).


94A11 Application of orthogonal and other special functions
65T50 Numerical methods for discrete and fast Fourier transforms
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory


Full Text: DOI


[1] Princen, J. P.; Johnson, A. W.; Bradley, A. B.: Subband/transform coding using filter bank designs based on time domain aliasing cancellation, , 2161-2164 (April 1987)
[2] A.W. Johnson, A.B. Bradley, Adaptive transform coding incorporating time domain aliasing cancellation, Speech Communications 6 (December 1987) 299 – 308.
[3] Rao, K. R.; Hwang, J. J.: Techniques and standards for digital image/video/audio coding, (1996)
[4] Painter, T.; Spanias, A.: Perceptual coding of digital audio, Proceedings of the IEEE 88, No. 4, 451-513 (April 2000)
[5] Information technology — coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s, Part 3: Audio, ISO/IEC JTC1/SC29/WG11 MPEG, International Standard 11172 – 3 (MPEG-1), 1992.
[6] Information technology — generic coding of moving pictures and associated audio, Part 3: Audio, ISO/IEC JTC1/SC29/WG11 MPEG, International Standard 13818 – 3 (MPEG-2), 1994.
[7] Digital audio compression (AC-3) ATSC Standard, Document of Advanced Television Systems Committee (ATSC), Audio specialist group T3/S7, December 1995.
[8] Information technology — generic coding of moving pictures and associated audio information, Part 7: Advanced Audio Coding , ISO/IEC JTC1/SC29/WG11 MPEG, International Standard 13818 – 7 (MPEG-2 AAC), 1997.
[9] Information technology — coding of audio – visual objects, Part 3: Audio, ISO/IEC JTC1/SC29/WG11 MPEG, International Standard 14496 – 3 (MPEG-4 audio), 1999.
[10] Herre, J.; Dietz, M.: MPEG-4 high-efficiency AAC coding, IEEE signal processing magazine 25, No. 3, 137-142 (May 2008)
[11] *0.8* 1.2Vorbis I specification, Document on web site: \langle http://www.xiph.org/\rangle , 2004, 68pp.
[12] Bosi, M.; Goldberg, R. E.: Introduction to digital audio coding and standards, (2003)
[13] Mathematical and special (peculiar) properties of the MDCT/MDST.
[14] Wang, Y.; Yaroslavsky, L.; Vilermo, M.: On the relationship between MDCT, , 44-47 (August 2000)
[15] Wang, Y.; Yaroslavsky, L.; Vilermo, M.; Väänänen, M.: Some peculiar properties of the MDCT, , 61-64 (August 2000)
[16] Wang, Y.; Vilermo, M.: Modified discrete cosine transform — its implications for audio coding and error concealment, Journal of audio engineering society 51, No. 1/2, 52-61 (January/February 2003)
[17] K. Wright, Notes on Ogg Vorbis and the MDCT, Draft document on web site: \langle www.free-comp-shop.com/vorbis.html\rangle , May 2003, 7pp.
[18] Britanak, V.: A note on the MDCT/MDST and pseudoinverse matrix, Computing and informatics 23, No. 3, 205-214 (March 2004) · Zbl 1092.65124
[19] Fast MDCT/MDST algorithms and efficient MDCT implementations in MP3. · Zbl 0567.65096
[20] Chan, D. -Y.; Yang, J. -F.; Chen, S. -Y.: Regular implementation algorithms of time domain aliasing cancellation, IEE Proceedings — vision, image and signal processing 143, No. 6, 387-392 (December 1996)
[21] Liu, C. -M.; Lee, W. -C.: A unified fast algorithm for cosine-modulated filter banks in current audio coding standards, Journal of the audio engineering society 47, No. 12, 1061-1075 (December 1999)
[22] Britanak, V.; Rao, K. R.: An efficient implementation of the forward and inverse MDCT in MPEG audio coding, IEEE signal processing letters 8, No. 2, 48-51 (February 2001)
[23] V. Britanak, The refined efficient implementation of the MDCT in MP3 and comparison with other methods, Technical Report II SAS-2002-02, Department of Numerical Methods and Algorithms, Institute of Informatics, Slovak Academy of Sciences, Bratislava, September 2002.
[24] Lee, S. W.: Improved algorithm for efficient computation of the forward and backward MDCT in MPEG audio coder, IEEE transactions on circuits and systems-II: analog and digital signal processing 48, No. 10, 990-994 (October 2001)
[25] Britanak, V.; Rao, K. R.: A new fast algorithm for the unified forward and inverse MDCT/MDST computation, Signal processing 82, No. 3, 433-459 (March 2002) · Zbl 1007.94521
[26] Cheng, M. -H.; Hsu, Y. -H.: Fast IMDCT and MDCT algorithms — a matrix approach, IEEE transactions on signal processing 51, No. 1, 221-229 (January 2003) · Zbl 1369.94112
[27] Murthy, N. Rama; Swamy, M. N. S.: A parallel/pipelined algorithm for the computation of MDCT and IMDCT, Proceedings of the international symposium on circuits and systems (ISCAS’2003) 4, 540-543 (May 2003)
[28] Wu, P. -S.; Hwan, Y. -T.: Efficient IMDCT core designs for audio signal processing, , 275-280 (August 2003)
[29] Britanak, V.: The fast DCT-IV/DST-IV computation via the MDCT, Signal processing 83, No. 8, 1803-1813 (August 2003) · Zbl 1144.94321
[30] Nikolajevič, V.; Fettweis, G.: Improved implementation of MDCT in MP3 audio coding, Proceedings of the IEEE 10th asian – Pacific conference on communications and 5th international symposium on multi-dimensional mobile communications (APCC/MDMC’2004) 1, 309-312 (August – September 2004)
[31] Kim, H. -S.; Cho, Y. -K.; Lee, W. -P.: A new optimized algorithm for computation of MDCT and its inverse transform, , 528-530 (November 2004)
[32] Cho, Y. -K.; Song, T. -H.; Kim, H. -S.: An optimized algorithm for computing the modified discrete cosine transform and its inverse transform, , 626-628 (November 2004)
[33] Britanak, V.: An efficient computing of oddly stacked MDCT/MDST via evenly stacked MDCT/MDST and vice versa, Signal processing 85, No. 7, 1353-1374 (July 2005) · Zbl 1148.94328
[34] H.J. Lincklaen Arriëns, Implementation of an 18-point IMDCT on FPGA, Internal Report no. CAS – LA05.1, Department of Electrical Engineering, Mathematical and Computer Science, Delft University of Technology, Delft, The Netherlands, July 2005, 22pp.
[35] Hwang, Y. -T.; Lai, S. -C.: A novel MDCT/IMDCT computing kernel design, , 526-531 (November 2005)
[36] Truong, T. K.; Chen, P. D.; Cheng, T. C.: Fast algorithm for computing the forward and inverse MDCT in MPEG audio coding, Signal processing 86, No. 5, 1055-1060 (May 2006) · Zbl 1163.94397
[37] Anup, K. C.; Bangla, A. K.: A new efficient implementation of TDAC synthesis filterbank based on radix-2 FFT’, (September 2006)
[38] Shu, H.; Bao, X.; Toumoulin, Ch.; Luo, L.: Radix-3 algorithm for the fast computation of forward and inverse MDCT, IEEE signal processing letters 14, No. 2, 93-96 (Febuary 2007)
[39] Li, T.; Zhang, R.; Yang, R.; Huang, H.; Lin, F.: A unified computing kernel for MDCT/IMDCT in modern audio coding standards, , 546-550 (October 2007)
[40] Chivukula, R. K.; Reznik, Y. A.: Efficient implementation of a class of MDCT/IMDCT filterbanks for speech and audio coding applications, , 213-216 (March – April 2008)
[41] Shao, X.; Johnson, S. G.: Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations, Signal processing 88, No. 6, 1313-1326 (June 2008) · Zbl 1186.94305
[42] Fast algorithms for the MLT computation. · Zbl 1186.94016
[43] Malvar, H. S.: Signal processing with lapped transforms, (1992) · Zbl 0948.94505
[44] Malvar, H. S.: Fast algorithms for orthogonal and biorthogonal modulated lapped transforms, , 159-163 (June 1998)
[45] Jing, C. -Y.; Tai, H. -M.: Fast algorithm for computing modulated lapped transform, Electronics letters 37, No. 12, 796-797 (June 2001)
[46] Fast algorithms for the MCLT computation.
[47] Malvar, H. S.: A modulated complex lapped transform and its application to audio processing, , 1421-1424 (May 1999)
[48] Tai, H. -M.; Jing, C. -Y.: Design and efficient implementation of a modulated complex lapped transform processor using pipeline technique, IEICE transactions fundamentals 84-A, No. 5, 1280-1287 (May 2001)
[49] Malvar, H. S.: Fast algorithm for the modulated complex lapped transform, IEEE signal processing letters 10, No. 1, 8-10 (January 2003)
[50] Dai, Q.; Chen, X. -J.: New algorithm for modulated complex lapped transform with symmetrical window function, IEEE signal processing letters 12, No. 12, 925-928 (December 2004)
[51] MDCT/MDST algorithms based on recursive filter structures. · Zbl 1374.94695
[52] Chen, C. -H.; Wu, C. -B.; Liu, B. -D.; Yang, J. -F.: Recursive architectures for the forward and inverse modified discrete cosine transform, , 50-59 (October 2000)
[53] Nikolajevič, V.; Fettweis, G.: New recursive algorithms for the forward and inverse MDCT, , 51-57 (September 2001)
[54] Chen, C. -H.; Liu, B. -D.; Yang, J. -F.: Recursive architectures for realizing modified discrete cosine transform and its inverse, IEEE transactions on circuits and systems-II: analog and digital signal processing 50, No. 1, 38-45 (January 2003)
[55] Nikolajevič, V.; Fettweis, G.: Computation of forward and inverse MDCT using clenshaw’s recurrence formula, IEEE transactions on signal processing 51, No. 5, 1439-1444 (May 2003) · Zbl 1369.94242
[56] Nikolajevič, V.; Fettweis, G.: New recursive algorithms for the unified forward and inverse MDCT/MDST, Journal of VLSI signal processing systems for signal, image and video technology 34, No. 3, 203-208 (July 2003) · Zbl 1039.68171
[57] Cheng, Z. -Y.; Chen, C. -H.; Liu, B. -D.; Yang, J. -F.: Unified selectable fixed-coefficient recursive structures for computing DCT, Proceedings of the IEEE international symposium on circuits and systems (ISCAS’2004) 3, 557-560 (May 2004)
[58] Hardware/software MDCT implementations in MP3.
[59] Yang, X.; Shi, S.; Wong, A. K.: Tradeoffs in modified discrete cosine transform implementations, , 370-373 (October 2001)
[60] P. Sundareson, A re-evaluation of fundamental transform structures for efficient implementation on semi-parallel DSP architectures, in: 112th AES Convention, Munich, Germany, May 2002, Preprint #5614.
[61] K.H. Bang, J.S. Kim, Y.C. Park, D.H. Youn, Design optimization of a dual MP3/AAC decoder, in: Proceedings of the IEEE ICASSP’2002, vol. 4, Orlando, FL, May 2002, pp. 3776 – 3779.
[62] Wang, X.; Dou, W.; Hou, Z.: An improved audio encoding architecture based on 16-bit fixed-point DSP, Proceedings of the IEEE international conference on communications, circuits and systems, and west sino expositions (ICCCAS and wesino expo’2002), Chengdu city, China 2, 918-921 (June 2002)
[63] Lee, W.; You, K.; Sung, W.: Software optimization of MPEG audio layer-III for a 32-bit RISC processor, Proceedings of the IEEE Asia – Pacific conference on circuits and systems 1, 435-438 (October 2002)
[64] Sung, W.; Chang, H.; Lee, W.; Ryu, S.: Speaking partner — an ARM7-based multimedia handheld device, , 218-221 (October 2002)
[65] Cardona, J. A. A.; Jayakumar, S.: Real-time MP3 encoder implemented in DSP hardware, (March – April 2003)
[66] I. Fältman, M. Hast, A. Lundgren, S. Malki, E. Montnemery, A. Rangevall, J. Sandvall and M. Stamenkovic, A hardware implementation of an MP3 decoder, Digital IC-Project, LTH, Lund Institute of Technology, Sweden, May 2003.
[67] Gurkhe, V.: Optimization of an MP3 decoder on the ARM processor, , 1475-1478 (October 2003)
[68] Tsai, T. -H.; Yang, Y. -C.: Low power and cost effective VLSI design for an MP3 audio decoder using an optimized synthesis-subband approach, Computers and digital techniques 151, No. 3, 245-251 (May 2004)
[69] Yao, Y.; Yao, Q.; Liu, P.; Xiao, Z.: Embedded software optimization for MP3 decoder implemented on RISC core, IEEE transactions on consumer electronics 50, No. 4, 1244-1249 (November 2004)
[70] DCT/DST (block) matrix factorizations, matrix theory and linear algebra.
[71] R. Geiger, T. Sporer, J. Koller, K. Brandenburg, Audio coding based on integer transforms, in: 111th AES Convention, New York, September 2001, Preprint #5471.
[72] Geiger, R.; Yokotani, Y.; Schuller, G.: Improved integer transforms for lossless audio coding, , 2119-2123 (November 2003)
[73] Geiger, R.; Yokotani, Y.; Schuller, G.; Herre, J.: Improved integer transforms using multidimensional lifting, , 1005-1008 (May 2004)
[74] Plonka, G.; Tasche, M.: Fast and numerically stable algorithms for discrete cosine transforms, Linear algebra and its applications 394, No. 1, 309-345 (January 2005) · Zbl 1072.65171
[75] Britanak, V.; Yip, P.; Rao, K. R.: Discrete cosine and sine transforms: general properties, fast algorithms and integer approximations, (2007)
[76] F.R. Gantmacher, The Theory of Matrices, second ed., Nauka, Moscow, 1966 (in Russian), (English translation: vols. 1 and 2, Chelsea, New York, 1959. · Zbl 0085.01001
[77] Golub, G. H.; Van Loan, C. F.: Matrix computations, (1996) · Zbl 0865.65009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.