On a Novel Decomposition of the DCT and its Application
The discrete cosine transform (DCT) is a widely used transform in signal and image coding applications. Its popularity in transform coding applications has led to its manufacture on a commercial scale in VLSI circuit form. In this correspondence, we give a novel decomposition of the DCT that enables the usage of the standard DCT hardware for implementing the DCT-IV and the discrete sine transform (DST-IV). Application of the derived relationship in implementing a version of the lapped orthogonal transform (LOT) and the modulated lapped transform (MLT) is also given. I. INTKODUCTWN The discrete cosine transform (DCT) is an orthonormal transform which is commonly employed in the transform coding of signals and images (see, e.g. , [ I ] ) . The main advantage of the DCT is that it is signal independent and is a good approximation to the statistically optimal Karhunen-Loe’ve transform (KLT) for a wide class of signals. The DCT of an N point real data sequence x ( n ) . 11 = 0 , 1 , . . . , N 1 is defined as Manuscript received February 21, 1991: revised October 14. 1991. This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-7739, and by MICRONET under the National Centres of Excellence program. The authors are with the Department of Electrical and Computer Engineering, Concordia University, Montreal, Quebec, H3G IM8, Canada. IEEE Log Number 9203387. IOSi-587X/93$03.00 e) 1993 IEEE IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 41, NO. I , JANUARY 1993 48 I and t(i) = 1, i # 0. ( 2 ) Similarly, the inverse DCT (IDCT) of X ( k ) , k = 0, I , . . . , N 1 is defined by n = 0, I , . . . , N 1 (3) where E ( . ) is defined as in ( 2 ) . The popularity of the DCT hardware due to its extensive application in several areas of signal processing, has led to its manufacture on a commercial scale in VLSI circuit form. DCT hardware is therefore inexpensive and is available as an off-the-shelf item. This, however, is not the case with DCT-IV and DST-IV type transforms [ 2 ] , which are used in very few signal processing applications. It is therefore commercially uneconomical and, thus, unlikely that they would be available as inexpensive VLSI circuits. Hence, we give a novel decomposition of the DCT that establishes its relation to DCT-IV and DST-IV, which enables the usage of the standard DCT hardware without any modifications for implementing DCT-IV and DST-IV. A practical application of the derived result in implementing a version of the LOT and the MLT is also given. 11. A NOVEL DECOMPOSITION OF T H E DCT For the decompositions that we propose in this article, we assume that N in ( I ) is an even integer, which is generally the case encountered in several practical applications. However, if N is an odd integer, where the situation so permits, an extra zero valued sample can be padded at the end of sequence x(n) to make N even. Let Cg denote cos ( s a / b ) and SX denote sin ( a a l b ) . By grouping the terms, ( I ) can be written as k = O , I ; . ' . N 1. (4) Defining two N / 2 point real sequences xl(n) and x?(n) such that = x ( n ) and x z ( n ) = x ( n + N / 2 ) , f l = 0, I . . . . , ( N / 2 ) 1 (4) may now be written as ( 5 ) Let us consider the even-indexed outputs of X ( k ) , i .e . , X ( 2 k ) , k = , and t ( 2 k ) = t ( k ) f o r k = 0, I , . . . , ( N / 2 ) I , we get k = 0, 1, . . . , N 1. 0, 1, . . . , ( N / 2 ) 1, Since CGrl+I+N!' = 1 X(2k) = 2 o r 1 2 X(2k) = { X l ( k ) + ( I ) ' X ? ( k ) } , k = 0, 1, . . . , ( N / 2 ) 1 (6) where X , ( k ) and X z ( k ) for k = 0, I , . . . , ( N / 2 ) 1 correspond to the ( N / 2 ) point DCT of the ( N / 2 ) point real sequences x , (n ) and x r ( n ) , respectively. Turning our attention to the odd-indexed outputs X ( 2 k + l ) , k = 0, 1, . . . , ( N / 2 ) I of ( 5 ) , and 4 2 k + I ) Since cf; + I ) ( 2 h + I) + N ( ? h + I ! = ( I sf; + l!i?i + I ) = 1 fork = 0, 1, . . . , ( N / 2 ) 1 , ( 7 ) can be written as or 1 X(2k + 1) = [X3(k) (-I)"X,(k)l, J x k = 0, I , . . . , ( N / 2 ) 1 (8) where X 3 ( k ) is the ( N / 2 ) point DCT-IV of xl(n) and X, (k ) is the ( N / 2 ) point DST-IV of x z ( n ) , respectively. The following may be observed from (6) and (8 ) . a) If x z ( n ) = 0 for n = 0, I , . . . , ( N / 2 ) 1, then X ( 2 k ) and X ( 2 k + 1) represent scaled versions of the ( N / 2 ) point DCT and the DCT-IV of sequence .xI ( n ) . b) I fx , (n) = 0 for n = 0. 1, . . . , ( N / 2 ) I , then X ( 2 k ) and X ( 2 k + 1) represent scaled and modulated versions (because of factor ( I ) ' ) of the ( N / 2 ) point DCT and DST-IV of sequence x 2 ( n ) . Since the demodulation for recovery of the scaled DCT and DST-IV, from the modulated outputs available involves only a sign change, no additional computationihardware is required in the demodulation process. Thus, it is seen that an N point DCT hardware, by setting the second half of its input samples to zero, can be used, to simultaneously produce an ( N / 2 ) point DCT and an ( N / 2 ) point DCT-IV of an ( N / 2 ) point sequence. Alternatively, by setting the first half of its input samples to zero, it can also be used to produce simultaneously an ( N / 2 ) point DCT and an ( N / 2 ) point DST-IV of an ( N / 2 ) point sequence. The decomposition of the IDCT is done in a slightly different manner and is presented in the next section. 111. A NOVFL DFCOMPOSITION F THE IDCT By separating the evenand odd-indexed points of X ( k ) , equation (3) can be written as