|
| ARTICLE |
|
|
|
| Year : 2009 | Volume
: 55
| Issue : 4 | Page : 180-191 |
 |
|
Unified Recursive Structure for Forward and Inverse Modified DCT/DST/DHT
Priyanka Jain1, Balbir Kumar2, Shail Bala Jain1
1 Department of Electronics and Communication Engg., Indira Gandhi Institute of Technology, Kashmere Gate, New Delhi - 110 006, India
2 Department of Electronics and Communication Engg., Maharaja Surajmal Institute of Technology, New Delhi - 110 058, India
| Date of Web Publication | 23-Sep-2009 |
Correspondence Address:
Priyanka Jain
Department of Electronics and Communication Engg., Indira Gandhi Institute of Technology, Kashmere Gate, New Delhi - 110 006
India
 DOI: 10.4103/0377-2063.55986
 Abstract | | |
This paper proposes implementation of the Modified Discrete Sine Transform (MDST) and Inverse MDST (IMDST) using recursive structures. The formulae required for recursive structures have been derived. Discrete Hartley Transform (DHT), a real-valued transform, is closely related to Discrete Fourier Transform (DFT) of a real-valued sequence and hence its use as an alternative to the Fourier Transform avoids complex arithmetic. This paper presents Modified Discrete Hartley Transform (MDHT)/Inverse MDHT (IMDHT) using Modified Discrete Cosine Transform (MDCT)/Inverse MDCT (IMDCT) and MDST/Inverse MDST (IMDST) recursive structures. The proposed structures are used for simultaneous computation of MDCT/MDST/MDHT of length N (divisible by four) and their Inverse (IMDST/IMDHT). The proposed structures are parallel, simple, regular and therefore highly suitable for VLSI implementation. Keywords: Infinite-impulse response, Modified discrete cosine transform, Modified discrete Hartley transform, Modified discrete sine transform, Recursive structure.
How to cite this article:
Jain P, Kumar B, Jain SB. Unified Recursive Structure for Forward and Inverse Modified DCT/DST/DHT. IETE J Res 2009;55:180-91 |
| 1. Introduction | |  |
Discrete Cosine Transform (DCT), Discrete Sine Transform (DST) and Discrete Hartley Transform (DHT) are important transforms in signal processing. Most of the modern digital coding techniques achieve impressive compression ratios by means of transform-based coding. Coding gain is achieved by exploring the transform domain-both the perceptually irrelevant aspects of human audition and statistical redundancies of the source signal. The filter bank chosen to perform the time-frequency mapping is of critical importance to the coder's ability to exploit the perceptual irrelevancies and source redundancies [1] . The modified discrete cosine transform (MDCT) and modified discrete sine transform (MDST) are employed in sub band/transform coding schemes as analysis/synthesis filter banks based on the concept of time domain aliasing cancellation (TDAC). Princen et al [2] . have defined two types of MDCT for evenly stacked and oddly stacked [3] analysis/synthesis systems. Both these filter banks can be viewed as block transforms in which basic functions overlap the adjacent blocks by 50%. These have been adopted as the basic processing components for high-quality audio compression in the international audio coding standards and commercial products (proprietary audio coding algorithms) such as Sony MiniDisc/ATRAC/ATRAC2/SDDS digital audio coding systems [4],[5] . The oddly stacked system has some advantages compared with the evenly stacked one. It is uniform, i.e., it has equally spaced bands of equal bandwidth and its computational structure, though more complex, requires the application of the MDCT only; while in the evenly stacked system, alternate applications of the MDCT/MDST are needed. For these reasons, the oddly stacked system is preferred in the audio coding applications. The oddly stacked MDCT can also be seen as modulated lapped transforms (MLT) [6],[7] , extended lapped transform (ELT) [8],[9],[10] , or modulated bi-orthogonal lapped transform (MBLT) [11] which belong to the class of lapped transforms. Hadas et al. [12] have shown that audio packet loss concealment can be done using MDCT and MDST instead of Discrete Short-Time Fourier Transform (DSTFT). Almost all existing audio coding systems use the complex-valued or real-valued FFT algorithms and DCT/DST of type IV (DCT-IV/DST IV) for MDCT/MDST computation. The comprehensive list of references with a detailed discussion related to existing fast algorithms is available in [13] .
Over the years, DHT has been established as a potential tool for signal processing and communication applications, e.g., computation of convolution and deconvolution [14],[15] , interpolation of real-valued signal [16] , image compression [17],[18] , error control coding [19] , adaptive filtering [20],[21] , multi-carrier modulation and many other applications [22],[23] . This paper proposes recursive algorithms for unified MDST/MDHT and IMDST/IMDHT computation in the oddly stacked system. Using these, unified structures have been evolved for computation of MDCT/MDST/MDHT and also for IMDST/IMDHT for any N divisible by 4. Chen et al. [24] have suggested a recursive algorithm of the MDCT/IMDCT. This paper also proposes an algorithm for the MDST/IMDST. The suggested algorithms require fewer multipliers and are equally efficient as the MDCT/IMDCT [24] algorithm. We have proposed the realization of MDHT/IMDHT through the efficient combination of MDST/IMDST and MDCT/IMDCT.
| 2. Computation of Oddly-Stacked Recursive Modified DST (O-MDST) | | |
The MDST of the N-point input sequence x[n] can be written as
Where N is the window length. Equation (1) is divided into two parts as
Let  in first series and  in second series of (2). Doing so (2) reduces to
i.e.
Rearranging the input data as follows:
As we progress, it will be seen that such an arrangement of input data makes computations more efficient. Using the value of y[n] from (5) and (6), Equation (4) yields
We can write (7) as
Putting n =N −1−n′ in the second term of (8), we get
i.e.
Using trigonometric identity sin α cos β=  [sin (α- β)+sin(α + β)]
we may write
which gives
Now (10) may be written as
where
Writing (13a) as
We may write (14) as
where U[k] is the second series on R.H.S. of (14), which may be written as
Putting  on second series of (16), we have
which simplifies to
After simple algebraic manipulation, we get
where,
Replacing n by  −1−n in (20a), we obtain
or
According to whether k is even or odd, (23) is divided into two parts. When k is even, we have
After simplification we get
Where
On the other hand, when k is odd, we have
i.e.
where
Recollecting the trigonometric identities
Using (28a & b) and denoting  (25b) and (27b) can be written as
Using (25a) and (27a) in (15a), we can realize the MDST by using the following formulae
2.1 Oddly-Stacked Modified Discrete Cosine Transform
MDCT can be defined as [24]
The recursive relations for MDCT from [24] are as follows:
where
and
Combining the results of MDCT and MDST we obtain the Modified DHT. A Modified Discrete Hartley Transform is defined as
i.e.
It is seen from (41) that the first sequence in the equation is MDCT and second sequence is MDST. A unified structure using (41) has been obtained and shown in [Figure 1].
| 3. Computation of Oddly Stacked Recursive Inverse Modified DST (O-IMDST) | | |
Inverse MDST is defined as
The corresponding structure is shown in [Figure 2]. Although in the oddly stacked system only MDST is used, the corresponding IMDST is also defined here for completeness. The notation  [n]emphasizes the fact that the recovered data sequence by the inverse transforms does not correspond to the original data sequence [13] .In the context of TDAC (analysis/synthesis filter banks the distorted sequence  [n] is said to be time domain aliased [2],[3] . The derivation of Inverse MDST is shown in appendix.
3.1 Oddly-Stacked Inverse Modified Discrete Cosine Transform
IMDCT is defined as [24] .
With
when
z′[n] is expressed as [24]
where
Inverse Modified Discrete Hartley Transform (IMDHT) is defined as
or
Then combining the results of IMDCT and IMDST we can obtain the Inverse Modified DHT as shown in [Figure 3].
| 4. Computational Complexity for Forward and Inverse MDCT/MDST/MDHT | | |
In [Figure 1], assume that total number of samples is N. Consider one value of k (k ≠ 0). Each recursive structure (A and B) will require  multiplications (by 2 cos θk) as only  samples are inputted ((24),(26)). Outputs at C,D,E, and F require one more multiplication each. Therefore, outputs at C and D are available after total of  multiplications. Similarly, outputs at E and F are also available after  multiplications. No multiplication is needed for k =0 (since cos θk = 1 and sin θk = 0). Also block G, which generates input for data manipulator requires  multiplications. Hence, total number of multiplications needed for all values of k are  . For example, for N=12 total number of multiplications needed are 26. Note that with these numbers of multiplications, we have computed three different types of transforms viz. MDCT, MDST and MDHT. Similarly, the number of additions for all values of k can be computed as follows: Calculation of u[n] from (13b) requires  additions. Computation of P[n] from (20b) requires  additions. Number of additions required till C and D blocks are  Similarly number of additions till E and F blocks are  The number of additions required after C, D, E and F are  Therefore, the total number of additions for all values of k is  Number of multiplications required for calculating IMDST are  and number of additions are  Similarly, the computation complexity for IMDHT is as follows: Number of multiplications is  and number of additions is 
We have compared the computational complexity of the proposed algorithm with those proposed by Troung [25] , Lee [26] and Hadas [12] as shown in [Table 1].
| 5. Performance | | |
It is seen from [Figure 1] that the structure constitutes resonators with poles at ± ejθk , i.e. the poles lie on the unit circle. These resonators have resonance frequency of èk and sharper peak at resonance [27] . This feature is useful for filter applications. The number of real multiplications and additions in the structure which realizes three transforms (MDCT, MDST and MDHT) is lesser than those needed for computation of only MDST in [12] and MDCT in [25] and [26] . The suggested structure is, therefore, highly efficient besides being versatile as shown in [Table 1]. It is well known that the wiring scheme for hardware implementation of butterfly type connections (as in conventional FFT, etc.) is quite involved. Since there are no butterfly/cross-connections in the proposed structure, therefore, it is highly suitable for hardware implementation. In general, recursive structures require less memory and are preferred where we have memory constraints. Moreover, any desired output kernel is computable independently.[28]
| 6. Conclusion | | |
The proposed recursive algorithm has been derived mathematically and realized as kernels for MDST, MDCT, and MDHT and their inverse. The analyzed results show that much lesser cycles are needed to simultaneously compute N point MDST, MDCT, MDHT and their inverse with high data throughput per transformation. Fewer recursive cycles result in smaller round-off errors of the algorithm. The proposed unified structure for MDCT/MDST/MDHT is simple and suitable for parallel VLSI implementation.
Authors
 Priyanka Jain received the B.E. degree (Electronics & Telecommunication) from Amravati University, Mahrashtra, India, in 1998, M.Tech. (Microwave Engg.) from Delhi University, India. From 2001 to 2002, she worked as Lecturer at Guru Prem Sukh Memorial College of Engineering (GGSIP University), Delhi, India. From 2002 she is working as Lecturer at India Gandhi Institute of Technology, New Delhi, Her teaching and research are in the area of signal processing, analog electronics and microwave.
 Balbir Kumar , Ph.D. (IIT Delhi) is professor, Department of Electronics and Communication Engineering, Maharaja Surajmal Institute of Technology, Delhi. From 1988-2005, he was with Netaji Subhas Institute of Technology (NSIT), Delhi and held various positions such as Head of the Department, Dean and Director of the institute. A life fellow of the Institution of Engineers (India) and IETE; a senior member of IEEE, USA; and a life member ISTE, Prof. Kumar has published more then sixty technical papers in National and International journal of repute. His area of interest is analog and digital signal processing.
 Shail B. Jain , Ph.D.(University of Delhi), is professor and Head, Department of Electronics and Communication Engineering, Indira Gandhi Institute of Technology, GGSIP University, Delhi. She has over 31 years of teaching experience at Delhi college of Engineering. A life fellow of IETE and senior member of IEEE, USA, she is a co-author of a book on linear Integrated Circuits. She has published a large number of papers in national and international journal in the field of digital signal processing. Her field of interest is linear integrated circuits and digital signal processing.
| References | | |
| 1. | K. Thompson, and L.E Atlas, "A non - uniform modulation transform for audio coding with increased time resolution," Proc. IEEE ICASSP'03, Hong-Kong, V397-V400 Vol. 5, 6-10 Apr. 2003.  |
| 2. | J.P. Princen, and A.B. Bradley, "Analysis/ Synthesis filter bank design based on time domain aliasing cancellation," IEEE Trans. ASSP-34(5), pp. 1153-61, 1986. |
| 3. | J.P. Princen, A.W. Johnson, and A.B. Bradley, "Subband/Transform coding using filter bank designs based ontime domain aliasing cancellation," Proc. IEEE, ICASSP'87, Dallas, TX, pp. 2161-4, Apr. 1987. |
| 4. | T. Painter, and A. Spanias, "Perceptual coding of digital audio," Proc. IEEE 88(4), pp. 451-13, Apr. 2000. |
| 5. | L.D.Fielder, and D.P. Robinson, "AC-2 and AC-3: The technology and its application," 5 th Australian Regional Convention, Audio Engineering Society Preprint#4022, Sydney, Apr. 1995. |
| 6. | H.S. Malvar, "Signal processing with Lapped Transform," Artech House, Norwood, MA, Apr. 1992. |
| 7. | H.S. Malvar, "Lapped transforms for efficient transform/subband coding," IEEE Trans. Acoustic Speech Signal Processing, ASSP-38, pp. 969-78, June. 1990. |
| 8. | H.S. Malvar, "Modulated QMF filter banks with perfect reconstruction," Electronics Letters 26, pp. 906-7, June 1990. |
| 9. | H.S. Malvar, "Extended lapped transforms: Fast algorithms and applications," Proceedings IEEE(ICASSP'91), Toronto, Canada, pp. 1797-1800, May. 1991. |
| 10. | H.S. Malvar, "Extended lapped transforms: Properties, applications and fast algorithms," IEEE Trans.Signal Processing 40(11), pp. 2703- 14, Nov. 1992. |
| 11. | H.S. Malvar, "Biorthogonal and nonuniform lapped transform for transform coding with reduced blocking and ringing artifacts," IEEE Trans. SP 46, pp. 1043-53, Apr. 1998. |
| 12. | H. Ofir, D. Malah, and I. Cohen, "Audio Packet Loss Concealment in a Combined MDCT-MDST Domain," IEEE Signal Processing Letters, Vol. 14(12), pp. 1032-5, Dec. 2007. |
| 13. | V. Britanak, and K.R. Rao, "A new fast algorithm for the unified forward and inverse MDCT/MDSTcomputation," Signal Processing 82, pp. 433-59, Mar. 2002. |
| 14. | P.K. Meher, J.C. Patra, and M.N.S. Swamy, "High-Throughput Memory-Based Architecture for DHT Using a New Convolutional Formulation," IEEE Transactions on Circuits and Systems-II: Express briefs, Vol. 54, No. 7, pp. 606-10, July. 2007. |
| 15. | L.Z. Cheng, L. Tong, and Z.R. Jiang, "Real transform algorithm for computing discrete circular deconvolution," Proc. 3rd IEEE Int. Conf. Signal Process., Vol. 1, pp. 166-9, Oct. 1996. |
| 16. | G.S. Maharana, and P.K. Meher, "Algorithm for efficient interpolation of real-valued signals using discrete Hartley transform," Comp. Elect. Eng., Vol. 23, No. 2, pp. 129-34, Mar. 1997. |
| 17. | I. Duleba, "Hartley transform in compression of medical ultrasonic image," Image analysis and processing, proc. 1999 IEEE, Sep. 1999. |
| 18. | R. Shyam Sunder, C. Eswaran, and N. Sriraam, "A 3-D discrete Hartley transform coder for compression of magnetic resonance images," IEEE International Conference on Electro Information Technology, 22-25 May. 2005, Page(s):6. |
| 19. | J.L. Wu and J. Shiu, "Discrete Hartley transform in error control coding," IEEE Trans. Signal Process., Vol. 39, No. 10, pp. 2356-59, Oct. 1991. |
| 20. | R. Muralishanka, H.N. Shankar, and D.O. Shaughnessy," A performance analysis of features from complex cepstra of warped DST, DCT and DHT filters for phoneme recognition," 2007 IEEE, pp. 591-94. |
| 21. | C.C. Tseng, and S.L. Lee, "Closed-form design of fractional delay FIR filter using discrete Hartley transform," IEEE 2007,pages-4. |
| 22. | D. Wang, D. Liu, F. Liut and G. Yue, "A novel DIT-based ultra-wideband system", Proc. of IEEE International Symposium on Communications and Information Technology, ISCIT 2005, Vol. 1, 12-14 Oct. 2005 pp. 672-675. |
| 23. | Z. Lin, F. Yin, and R.W. McCallum, "A fast running Hartley transform algorithm and its application in adaptive signal enhancement," ICASSP 2005, pp. IV 189-92. |
| 24. | C.H. Chen, B.D Liu, and J.F. Yang, "Recursive architectures for realizing Modified discrete cosine transform and its inverse," IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing, Vol. 50 (1), pp. 38-45, Jan.2003. |
| 25. | T.K. Truong, and P.D. Chen, T.C. Cheng, "Fast algorithm for computing the forward and inverse MDCT in MPEG audio coding," Signal Processing 86(2006),pp. 1055-60. |
| 26. | S.W. Lee, "Improved algorithm for efficient computation of the forward and backward MDCT in MPEG audio coder," IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing, Vol. 48 (10), pp. 990-4, Oct. 2001. |
| 27. | J.G. Proakis, and Manolakis "Digital Signal Processing", 1996, 3 rd ed. Prentice Hall: Englewood Cliffs, NJ, U.S.A. |
| 28. | P. Jain, B. Kumar, and S.B. Jain, "Discrete sine transform and its inverse realization through recursive algorithms," International Journal of Circuit Theory and Application, Vol. 36, No.4, pp. 441-9, Sep.2007. |
[Figure 1], [Figure 2], [Figure 3]
[Table 1]
|
