New universal rotation-based fast computational structures for an efficient implementation of the DCT-IV/DST-IV and analysis/synthesis MDCT/MDST filter banks.

*(English)*Zbl 1169.94305Summary: New universal rotation-based fast computational structures identical both for the discrete cosine/sine transform of type IV (DCT-IV/DST-IV) and the forward/backward modified discrete cosine/sine transform (MDCT/MDST) computation are described. They are the result of a systematic construction of a fast algorithm for an efficient implementation of the time domain aliasing cancellation (TDAC) analysis/synthesis MDCT/MDST filter banks employed in various audio compression schemes. New fast algorithms provide novelty computational structures based exclusively on the computation of Givens-Jacobi rotations, and thus, the need of any discrete sinusoidal unitary transform such as the discrete Fourier transform (DFT), DCT-IV/DST-IV or discrete cosine/sine transforms of type II (DCT-II/DST-II) of reduced size is completely eliminated, so simplifying the computational structure of the algorithms. The rotators and summators are used only as the basic computational modules (in a hardware implementation they are simple hardware blocks). The simple and regular Givens-Jacobi rotation-based fast computational structures valid for any \(N\) divisible by 4 (\(N\) being the length of data sequence) define new sparse matrix factorizations of the DCT-IV and MDCT matrices and in particular, generate an efficient implementation of the MDCT in MP3 audio coding standard. For a given \(N=2^n\) they can be easily reconfigurable for a specific audio coding scheme. Finally, since Givens-Jacobi rotation can be factored into a product of Gauss elementary matrices being unit lower and unit upper triangular matrices, the new fast rotation-based computational structures are suitable for an integer approximation of the DCT-IV/DST-IV (integer DCT-IV/DST-IV) and MDCT/MDST (integer MDCT/MDST) which are currently modern transform technologies for lossless audio coding.

##### MSC:

94A11 | Application of orthogonal and other special functions |

93E11 | Filtering in stochastic control theory |

65T50 | Numerical methods for discrete and fast Fourier transforms |

##### Keywords:

modified discrete cosine transform; modified discrete sine transform; analysis and synthesis MDCT filter banks; modulated lapped transform; modulated complex lapped transform; fast computational structure; MPEG audio coding; integer MDCT; lossless audio coding
PDF
BibTeX
XML
Cite

\textit{V. Britanak}, Signal Process. 89, No. 11, 2213--2232 (2009; Zbl 1169.94305)

Full Text:
DOI

##### References:

[1] | J.P. Princen, A.W. Johnson, A.B. Bradley, Subband/transform coding using filter bank designs based on time domain aliasing cancellation, in: Proceedings of the IEEE ICASSP’87, Dallas, TX, April 1987, pp. 2161 – 2164. |

[2] | Bosi, M.; Goldberg, R. E.: Introduction to digital audio coding and standards, (2003) |

[3] | Spanias, A.; Painter, T.; Atti, V.: Audio signal processing and coding, (2007) |

[4] | Herre, J.; Dietz, M.: MPEG-4 high-efficiency AAC coding, IEEE signal processing magazine 25, No. 3, 137-142 (May 2008) |

[5] | Digital Audio Compression (AC-3) ATSC Standard, Document A/52 of Advanced Television Systems Committee (ATSC), Audio specialist group T3/S7, December 1995. |

[6] | Digital Audio Compression Standard (AC-3, E-AC-3), Revision B. Document A/52B of Advanced Television Systems Committee (ATSC), June 2005. |

[7] | *0.8* 1.2Vorbis I Specification, Document on web site: \langle http://www.xiph.org/\rangle , 2004, 68pp. |

[8] | X. Yang, S. Shi, A.K. Wong, Tradeoffs in modified discrete cosine transform implementations, in: Proceedings of the IEEE 4th International Conference on ASIC, Shanghai, China, October 2001, pp. 370 – 373. |

[9] | ISO/IEC JTC1/SC29/WG11 Moving Picture Experts Group, Final call for proposals on MPEG-4 lossless audio coding, Meeting Document N5208, Shanghai, China, October 2002. |

[10] | 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) |

[11] | 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) |

[12] | 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) |

[13] | 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 · doi:10.1016/S0165-1684(01)00195-5 |

[14] | 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 |

[15] | N. Rama Murthy, M.N.S. Swamy, A parallel/pipelined algorithm for the computation of MDCT and IMDCT, in: Proceedings of the International Symposium on Circuits and Systems (ISCAS’2003), vol. 4, Bangkok, Thailand, May 2003, pp. 540 – 543. |

[16] | P.-S. Wu, Y.-T. Hwan, Efficient IMDCT core designs for audio signal processing, in: Proceedings of the IEEE Workshop on Signal Processing Systems: Design and Implementation (SiPS’2003), Seoul, Korea, August 2003, pp. 275 – 280. |

[17] | Britanak, V.: The fast DCT-IV/DST-IV computation via the MDCT, Signal processing 83, No. 8, 1803-1813 (August 2003) · Zbl 1144.94321 |

[18] | V. Nikolajevič, G. Fettweis, Improved implementation of MDCT in MP3 audio coding, in: Proceedings of the IEEE 10th Asian-Pacific Conference on Communications and 5th International Symposium on Multi-Dimensional Mobile Communications (APCC/MDMC’2004), vol. 1, Tsinghua University, Beijing, China, August – September 2004, pp. 309 – 312. |

[19] | H.-S. Kim, Y.-K. Cho, W.-P. Lee, A new optimized algorithm for computation of MDCT and its inverse transform, in: Proceedings of the IEEE International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS’2004), Seoul, Korea, November 2004, pp. 528 – 530. |

[20] | Y.-K. Cho, T.-H. Song, H.-S. Kim, An optimized algorithm for computing the modified discrete cosine transform and its inverse transform, in: Proceedings of the IEEE Region 10 Conference TENCON’2004, Chiang Mai, Thailand, November 2004, pp. 626 – 628. |

[21] | 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 · doi:10.1016/j.sigpro.2005.02.001 |

[22] | Y.-T. Hwang, S.-C. Lai, A novel MDCT/IMDCT computing kernel design, in: Proceedings of the IEEE Workshop on Signal Processing Systems: Design and Implementation, Athens, Greece, November 2005, pp. 526 – 531. |

[23] | 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 · doi:10.1016/j.sigpro.2005.07.027 |

[24] | K.C. Anup, A.K. Bangla, A new efficient implementation of TDAC synthesis filterbank based on radix-2 FFT, in: Proceedings of the 14th EUSIPCO Signal Processing Conference, Florence, Italy, September 2006. |

[25] | T. Zhang, S. Liu, J. He, H. Zhang, A new algorithm on short window MDCT for Dolby AC-3, Proceedings of the International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS’2007), Xiamen, China, November – December 2007, pp. 478 – 481. |

[26] | T. Zhang, J. He, C. Chen, On the relationship of MDCT transform kernels in AC-3, in: Proceedings of the International Conference on Audio, Language and Image Processing (ICALIP’2009), Shanghai, China, July 2008, pp. 839 – 842. |

[27] | 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 (February 2007) |

[28] | T. Li, R. Zhang, R. Yang, H. Huang, F. Lin, A unified computing kernel for MDCT/IMDCT in modern audio coding standards, in: Proceedings of the IEEE International Symposium on Communication and Information Technologies (ISCIT’2007), Sydney, Australia, October 2007, pp. 546 – 550. |

[29] | R.K. Chivukula, Y.A. Reznik, Efficient implementation of a class of MDCT/IMDCT filterbanks for speech and audio coding applications, in: Proceedings of the IEEE ICASSP’2008, Las Vegas, NV, March – April 2008, pp. 213 – 216. |

[30] | X. Dai, M.D. Wagh, An MDCT hardware accelerator for MP3 audio, in: Proceedings of the IEEE Symposium on Application Specific Processors (SASP’2008), Anaheim, CA, June 2008, pp. 121 – 125. |

[31] | 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 · doi:10.1016/j.sigpro.2007.11.024 |

[32] | Wu, J. S.; Shu, H. Z.; Senhadji, L.; Luo, L. M.: A fast algorithm for the computation of 2-D forward and inverse MDCT, Signal processing 88, No. 6, 1313-1326 (June 2008) · Zbl 1186.94016 · doi:10.1016/j.sigpro.2007.12.003 |

[33] | Britanak, V.; Arrien¨, H. J. Lincklaen; S: Fast computational structures for an efficient implementation of the complete TDAC analysis/synthesis MDCT/MDST filter banks, Signal processing 89, No. 7, 1379-1394 (July 2009) · Zbl 1178.94038 |

[34] | J. Wu, H. Shu, L. Senhadji, L. Luo, Mixed-radix algorithm for the computation of forward and inverse MDCT, IEEE Transactions on Circuits and Systems — I: Regular Papers 56 (4) (April 2009) 784 – 794. |

[35] | Malvar, H. S.: Signal processing with lapped transforms, (1992) · Zbl 0948.94505 |

[36] | H.S. Malvar, Fast algorithms for orthogonal and biorthogonal modulated lapped transforms, in: Proceedings of the IEEE Symposium on Advances in Digital Filtering and Signal Processing, Victoria, Canada, June 1998, pp. 159 – 163. |

[37] | Jing, C. -Y.; Tai, H. -M.: Fast algorithm for computing modulated lapped transform, Electronics letters 37, No. 12, 796-797 (June 2001) |

[38] | Jing, C. -Y.; Tai, H. -M.: Design and implementation of a fast algorithm for modulated lapped transform, IEE Proceedings: vision image and signal processing 149, No. 1, 27-32 (February 2002) |

[39] | H.S. Malvar, A modulated complex lapped transform and its application to audio processing, in: Proceedings of the IEEE ICASSP’99, Phoenix, AR, May 1999, pp. 1421 – 1424. |

[40] | Xiong, Z.; Malvar, H. S.: A nonuniform complex modulated lapped transform, IEEE signal processing letters 8, No. 9, 257-260 (September 2001) |

[41] | 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) |

[42] | Malvar, H. S.: Fast algorithm for the modulated complex lapped transform, IEEE signal processing letters 10, No. 1, 8-10 (January 2003) |

[43] | 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) |

[44] | Chen, X. -J.; Dai, Q.: A novel DCT-based algorithm for computing the modulated complex lapped transform, IEEE transactions on signal processing 54, No. 11, 4480-4484 (November 2006) · Zbl 1374.94695 |

[45] | Dai, X.; Wagh, M. D.: Fast algorithm for modulated complex lapped transform, IEEE signal processing letters 16, No. 1 – 3, 30-33 (January – March 2009) |

[46] | Shu, H. Z.; Wu, J. S.; Senhadji, L.; Luo, L. M.: New fast algorithm for modulated lapped transform with sine windowing function, IEEE signal processing letters 16, No. 1 – 3, 93-96 (January – March 2009) |

[47] | C.-H. Chen, C.-B. Wu, B.-D. Liu, J.-F. Yang, Recursive architectures for the forward and inverse modified discrete cosine transform, in: Proceedings of the IEEE Workshop on Signal Processing Systems: Design and Implementation (SiPS’2000), Lafayette, LA, October 2000, pp. 50 – 59. |

[48] | V. Nikolajevič, G. Fettweis, New recursive algorithms for the forward and inverse MDCT, in: Proceedings of the IEEE Workshop on Signal Processing Systems: Design and Implementation (SiPS’2001), Antwerp, Belgium, September 2001, pp. 51 – 57. |

[49] | 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) |

[50] | 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 |

[51] | 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 · doi:10.1023/A:1023292117679 |

[52] | Z.-Y. Cheng, C.-H. Chen, B.-D. Liu, J.-F. Yang, Unified selectable fixed-coefficient recursive structures for computing DCT, IMDCT and subband synthesis filtering, in: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS’2004), vol. 3, Vancouver, Canada, May 2004, pp. 557 – 560. |

[53] | T.W. Fox, A. Carriera, Goertzel implementations of the forward and inverse modified discrete cosine transform, in: IEEE Canadian Conference on Electrical and Computer Engineering (CCECE’2004), vol. 4, Niagara Falls, Canada, May 2004, pp. 2371 – 2374. |

[54] | Hao, P.: Customizable triangular factorizations of matrices, Linear algebra and its applications 382, 135-154 (May 2004) · Zbl 1050.15012 · doi:10.1016/j.laa.2003.12.023 |

[55] | She, Y.; Hao, P.: On the necessity and sufficiency of PLUS factorizations, Linear algebra and applications 400, 193-202 (May 2005) · Zbl 1071.15012 · doi:10.1016/j.laa.2004.11.024 |

[56] | Britanak, V.; Yip, P.; Rao, K. R.: Discrete cosine and sine transforms: general properties, fast algorithms and integer approximations, (2007) |

[57] | J. Wang, J. Sun, S. You, 1-D and 2-D transforms from integers to integers, in: Proceedings of the IEEE ICASSP’2003, vol. 2, Hong Kong, April 2003, pp. 549 – 552. |

[58] | Plonka, G.; Tasche, M.: Invertible integer DCT algorithms, Applied and computational harmonic analysis 15, No. 1, 70-88 (2003) · Zbl 1030.65144 · doi:10.1016/S1063-5203(03)00032-0 |

[59] | Plonka, G.: A global method for invertible integer DCT and integer wavelet algorithms, Applied and computational harmonic analysis 16, No. 2, 90-110 (March 2004) · Zbl 1053.65103 · doi:10.1016/j.acha.2003.10.004 |

[60] | Y. Yokotani, S. Oraintara, R. Geiger, G. Schuller, K.R. Rao, A comparison of integer fast Fourier transforms for lossless coding, in: Proceedings of the International Symposium on Communications and Information Technologies (ISCIT 2004), Sapporo, Japan, October 2004, pp. 1069 – 1073. |

[61] | Primbs, M.: Worst-case error analysis of lifting-based fast DCT-algorithms, IEEE transactions on signal processing 53, No. 8 Part 2, 3211-3218 (August 2005) · Zbl 1370.94045 |

[62] | Srinivasan, S.: Modulo transforms — an alternative to lifting, IEEE transactions on signal processing 54, No. 5, 1864-1874 (May 2006) · Zbl 1373.94521 |

[63] | R. Geiger, T. Sporer, J. Koller, K. Brandenburg, Audio coding based on integer transforms, in: 111th AES Convention, New York, September 2001, Preprint #5471. |

[64] | R. Geiger, J. Herre, J. Koller, K. Brandenburg, IntMDCT — a link between perceptual and lossless audio coding, in: Proceedings of the IEEE ICASSP’2002, vol. 2, Orlando, FL, May 2002, pp. 1813 – 1816. |

[65] | T. Krishnan, S. Oraintara, Fast and lossless implementation of the forward and inverse MDCT computation in MPEG audio coding, in: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS’2002), vol. 2, Phoenix, Scottsdale, AR, May 2002, pp. 181 – 184. |

[66] | R. Geiger, G. Schuller, Integer low delay and MDCT filter banks, in: Proceedings of the 36th Asilomar Conference on Signals, Systems and Computers, vol. 1, Pacific Grove, CA, November 2002, pp. 811 – 815. |

[67] | T. Krishnan, S. Oraintara, The integer MDCT and its application in the MPEG layer III audio, in: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS’2003), vol. 4, Bangkok, Thailand, May 2003, pp. 301 – 304. |

[68] | R. Geiger, Y. Yokotani, G. Schuller, Improved integer transforms for lossless audio coding, in: Proceedings of the 37th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, November 2003, pp. 2119 – 2123. |

[69] | Y. Yokotani, S. Oraintara, Lossless audio compression using integer modified discrete cosine transform, in: Proceedings of the IEEE International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS’2003), Awaji Island, Japan, December 2003. |

[70] | R. Geiger, Y. Yokotani, G. Schuller, J. Herre, Improved integer transforms using multidimensional lifting, in: Proceedings of the IEEE ICASSP’2004, Montreal, Canada, May 2004, pp. 1005 – 1008. |

[71] | Y. Yokotani, R. Geiger, G. Schuller, S. Oraintara, K.R. Rao, Improved lossless audio coding using the noise-shaped IntMDCT, in: Proceedings of the IEEE 11th Digital Signal Processing Workshop and Signal Processing Education Workshop, Taos Ski Valley, NM, August 2004, pp. 356 – 360. |

[72] | Y. Yokotani, S. Oraintara, R. Geiger, G. Schuller, K.R. Rao, Approximation error analysis for transform-based lossless audio coding, in: Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM’2004), vol. 2, Dallas, TX, November – December 2004, pp. 595 – 599. |

[73] | Y. Zhang, R. Hu, Scalable audio coding based on integer transform, in: Proceedings of the IEEE 1st International Conference on Communications and Networking in China (ChinaCom’2006), Beijing, China, October 2006, pp. 1 – 5. |

[74] | Yokotani, Y.; Geiger, R.; Schuller, G.; Oraintara, S.; Rao, K. R.: Lossless audio coding using the intmdct and rounding error shaping, IEEE transactions on audio, speech, and language processing 14, No. 6, 2201-2211 (November 2006) |

[75] | Huang, H.; Yu, R.; Lin, X.; Rahardja, S.: Method for realising reversible integer type-IV discrete cosine transform, Electronics letters 40, No. 8, 514-515 (April 2004) |

[76] | H. Huang, S. Rahardja, R. Yu, X. Lin, A fast algorithm of integer MDCT for lossless audio coding, in: Proceedings of the IEEE ICASSP’2004, vol. 4, Montreal, Canada, May 2004, pp. 177 – 180. |

[77] | Huang, H.; Rahardja, S.; Yu, R.; Lin, X.: Integer MDCT with enhanced approximation of the DCT-IV, IEEE transactions on signal processing 54, No. 3, 1156-1159 (March 2006) · Zbl 1373.94614 |

[78] | J. Li, A progressive to lossless embedded audio coder (PLEAC) with reversible modulated lapped transform, in: Proceedings of the IEEE International Conference on Multimedia and Expo (ICME’2003), vol. 3, Baltimore, MD, July 2003, pp. 221 – 224. |

[79] | J. Li, Reversible FFT and MDCT via matrix lifting, in: Proceedings of the IEEE ICASSP’2004, vol. 4, Montreal, Canada, May 2004, pp. 173 – 176. |

[80] | Li, J.: Low noise reversible MDCT (RMDCT) and its application in progressive-to-lossless embedded audio coding, IEEE transactions on signal processing 53, No. 5, 1870-1880 (May 2005) · Zbl 1370.94411 |

[81] | H.S. Malvar, Lossless and near-lossless audio compression using integer-reversible modulated lapped transforms, in: Proceedings of the IEEE Data Compression Conference (DCC’2007), Snowbird, UT, March 2007. |

[82] | Li, T.; Rahardja, S.; Yu, R.; Koh, S. N.: On integer MDCT for perceptual audio coding, IEEE transactions on audio, speech, and language processing 15, No. 8, 2236-2248 (November 2007) |

[83] | Muddhasani, V.; Wagh, M. D.: Bilinear algorithms for discrete cosine transforms of prime lengths, Signal processing 86, No. 9, 2393-2406 (September 2006) · Zbl 1172.94342 · doi:10.1016/j.sigpro.2005.10.022 |

[84] | R. Gluth, Regular FFT-related transform kernels for DCT/DST-based polyphase filter banks, in: Proceedings of the IEEE ICASSP’91, Toronto, Canada, May 1991, pp. 2205 – 2208. |

[85] | 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 · doi:10.1016/j.laa.2004.07.015 |

[86] | D.K. Faddeev, V.N. Faddeeva, Computational Methods of Linear Algebra, GIFML, Moscow, 1963 (in Russian), English translation: Dover Publications Inc., New York, 1959. · Zbl 0086.10802 |

[87] | 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 |

[88] | Golub, G. H.; Van Loan, C. F.: Matrix computations, (1996) · Zbl 0865.65009 |

[89] | H. Dawid, H. Meyr, CORDIC algorithms and architectures, in: K.K. Parhi, T. Nishitami (Eds.), Digital Signal Processing for Multimedia Systems, Marcel Dekker, Inc., New York, 1999, pp. 623 – 655 (Chapter 22). |

[90] | Deschamps, J. P.; Bioul, G. J. A.; Sutter, G. D.: Synthesis of arithmetic circuits: FPGA, ASIC and embedded systems, (2006) |

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.