 Modified discrete cosine transform

The modified discrete cosine transform (MDCT) is a Fourierrelated transform based on the typeIV discrete cosine transform (DCTIV), with the additional property of being lapped: it is designed to be performed on consecutive blocks of a larger dataset, where subsequent blocks are overlapped so that the last half of one block coincides with the first half of the next block. This overlapping, in addition to the energycompaction qualities of the DCT, makes the MDCT especially attractive for signal compression applications, since it helps to avoid artifacts stemming from the block boundaries. As a result of these advantages, the MDCT is employed in most modern lossy audio formats, including MP3, AC3, Vorbis, Windows Media Audio, ATRAC, Cook, and AAC.
The MDCT was proposed by Princen, Johnson, and Bradley in 1987, following earlier (1986) work by Princen and Bradley to develop the MDCT's underlying principle of timedomain aliasing cancellation (TDAC), described below. (There also exists an analogous transform, the MDST, based on the discrete sine transform, as well as other, rarely used, forms of the MDCT based on different types of DCT or DCT/DST combinations.)
In MP3, the MDCT is not applied to the audio signal directly, but rather to the output of a 32band polyphase quadrature filter (PQF) bank. The output of this MDCT is postprocessed by an alias reduction formula to reduce the typical aliasing of the PQF filter bank. Such a combination of a filter bank with an MDCT is called a hybrid filter bank or a subband MDCT. AAC, on the other hand, normally uses a pure MDCT; only the (rarely used) MPEG4 AACSSR variant (by Sony) uses a fourband PQF bank followed by an MDCT. Similar to MP3, ATRAC uses stacked quadrature mirror filters (QMF) followed by an MDCT.
Contents
Definition
As a lapped transform, the MDCT is a bit unusual compared to other Fourierrelated transforms in that it has half as many outputs as inputs (instead of the same number). In particular, it is a linear function (where R denotes the set of real numbers). The 2N real numbers x_{0}, ..., x_{2N1} are transformed into the N real numbers X_{0}, ..., X_{N1} according to the formula:
(The normalization coefficient in front of this transform, here unity, is an arbitrary convention and differs between treatments. Only the product of the normalizations of the MDCT and the IMDCT, below, is constrained.)
Inverse transform
The inverse MDCT is known as the IMDCT. Because there are different numbers of inputs and outputs, at first glance it might seem that the MDCT should not be invertible. However, perfect invertibility is achieved by adding the overlapped IMDCTs of subsequent overlapping blocks, causing the errors to cancel and the original data to be retrieved; this technique is known as timedomain aliasing cancellation (TDAC).
The IMDCT transforms N real numbers X_{0}, ..., X_{N1} into 2N real numbers y_{0}, ..., y_{2N1} according to the formula:
(Like for the DCTIV, an orthogonal transform, the inverse has the same form as the forward transform.)
In the case of a windowed MDCT with the usual window normalization (see below), the normalization coefficient in front of the IMDCT should be multiplied by 2 (i.e., becoming 2/N).
Computation
Although the direct application of the MDCT formula would require O(N^{2}) operations, it is possible to compute the same thing with only O(N log N) complexity by recursively factorizing the computation, as in the fast Fourier transform (FFT). One can also compute MDCTs via other transforms, typically a DFT (FFT) or a DCT, combined with O(N) pre and postprocessing steps. Also, as described below, any algorithm for the DCTIV immediately provides a method to compute the MDCT and IMDCT of even size.
Window functions
In typical signalcompression applications, the transform properties are further improved by using a window function w_{n} (n = 0, ..., 2N1) that is multiplied with x_{n} and y_{n} in the MDCT and IMDCT formulas, above, in order to avoid discontinuities at the n = 0 and 2N boundaries by making the function go smoothly to zero at those points. (That is, we window the data before the MDCT and after the IMDCT.) In principle, x and y could have different window functions, and the window function could also change from one block to the next (especially for the case where data blocks of different sizes are combined), but for simplicity we consider the common case of identical window functions for equalsized blocks.
The transform remains invertible (that is, TDAC works), for a symmetric window w_{n} = w_{2N1n}, as long as w satisfies the PrincenBradley condition:
 .
various window functions are common, e.g.
for MP3 and MPEG2 AAC, and
for Vorbis. AC3 uses a KaiserBessel derived (KBD) window, and MPEG4 AAC can also use a KBD window.
Note that windows applied to the MDCT are different from windows used for other types of signal analysis, since they must fulfill the PrincenBradley condition. One of the reasons for this difference is that MDCT windows are applied twice, for both the MDCT (analysis) and the IMDCT (synthesis).
Relationship to DCTIV and Origin of TDAC
As can be seen by inspection of the definitions, for even N the MDCT is essentially equivalent to a DCTIV, where the input is shifted by N/2 and two Nblocks of data are transformed at once. By examining this equivalence more carefully, important properties like TDAC can be easily derived.
In order to define the precise relationship to the DCTIV, one must realize that the DCTIV corresponds to alternating even/odd boundary conditions: even at its left boundary (around n=–1/2), odd at its right boundary (around n=N–1/2), and so on (instead of periodic boundaries as for a DFT). This follows from the identities and . Thus, if its inputs are an array x of length N, we can imagine extending this array to (x, –x_{R}, –x, x_{R}, ...) and so on, where x_{R} denotes x in reverse order.
Consider an MDCT with 2N inputs and N outputs, where we divide the inputs into four blocks (a, b, c, d) each of size N/2. If we shift these by N/2 (from the +N/2 term in the MDCT definition), then (b, c, d) extend past the end of the N DCTIV inputs, so we must "fold" them back according to the boundary conditions described above.
 Thus, the MDCT of 2N inputs (a, b, c, d) is exactly equivalent to a DCTIV of the N inputs: (–c_{R}–d, a–b_{R}), where R denotes reversal as above.
(In this way, any algorithm to compute the DCTIV can be trivially applied to the MDCT.)
Similarly, the IMDCT formula above is precisely 1/2 of the DCTIV (which is its own inverse), where the output is shifted by N/2 and extended (via the boundary conditions) to a length 2N. The inverse DCTIV would simply give back the inputs (–c_{R}–d, a–b_{R}) from above. When this is shifted and extended via the boundary conditions, one obtains:
 IMDCT(MDCT(a, b, c, d)) = (a–b_{R}, b–a_{R}, c+d_{R}, d+c_{R}) / 2.
Half of the IMDCT outputs are thus redundant, as b–a_{R} = –(a–b_{R})_{R}, and likewise for the last two terms.
One can now understand how TDAC works. Suppose that one computes the MDCT of the subsequent, 50% overlapped, 2N block (c, d, e, f). The IMDCT will then yield, analogous to the above: (c–d_{R}, d–c_{R}, e+f_{R}, e_{R}+f) / 2. When this is added with the previous IMDCT result in the overlapping half, the reversed terms cancel and one obtains simply (c, d), recovering the original data.
Origin of TDAC
The origin of the term "timedomain aliasing cancellation" is now clear. The use of input data that extend beyond the boundaries of the logical DCTIV causes the data to be aliased in exactly the same way that frequencies beyond the Nyquist frequency are aliased to lower frequencies, except that this aliasing occurs in the time domain instead of the frequency domain. Hence the combinations c–d_{R} and so on, which have precisely the right signs for the combinations to cancel when they are added.
For odd N (which are rarely used in practice), N/2 is not an integer so the MDCT is not simply a shift permutation of a DCTIV. In this case, the additional shift by half a sample means that the MDCT/IMDCT becomes equivalent to the DCTIII/II, and the analysis is analogous to the above.
TDAC for the windowed MDCT
Above, the TDAC property was proved for the ordinary MDCT, showing that adding IMDCTs of subsequent blocks in their overlapping half recovers the original data. The derivation of this inverse property for the windowed MDCT is only slightly more complicated.
Recall from above that when (a,b,c,d) and (c,d,e,f) are MDCTed, IMDCTed, and added in their overlapping half, we obtain (c + d_{R},c_{R} + d) / 2 + (c − d_{R},d − c_{R}) / 2 = (c,d), the original data.
Now we suppose that we multiply both the MDCT inputs and the IMDCT outputs by a window function of length 2N. As above, we assume a symmetric window function, which is therefore of the form (w,z,z_{R},w_{R}) where w and z are lengthN/2 vectors and R denotes reversal as before. Then the PrincenBradley condition can be written: , with the multiplications and additions performed elementwise, or equivalently (reversing w and z).
Therefore, instead of MDCTing (a,b,c,d), we now MDCT (wa,zb,z_{R}c,w_{R}d) (with all multiplications performed elementwise). When this is IMDCTed and multiplied again (elementwise) by the window function, the lastN half becomes:
 .
(Note that we no longer have the multiplication by 1/2, because the IMDCT normalization differs by a factor of 2 in the windowed case.)
Similarly, the windowed MDCT and IMDCT of (c,d,e,f) yields, in its firstN half:
 .
When we add these two halves together, we obtain:
recovering the original data.
See also
Other overlapping windowed Fourier transforms include:
MDCT page from Google knol data base
References
 Henrique S. Malvar, Signal Processing with Lapped Transforms (Artech House: Norwood MA, 1992).
 John P. Princen and Alan B. Bradley, "Analysis/synthesis filter bank design based on time domain aliasing cancellation," IEEE Trans. Acoust. Speech Sig. Proc. ASSP34 (5), 11531161 (1986). (Described a precursor to the MDCT using a combination of discrete cosine and sine transforms.)
 J. P. Princen and A. W. Johnson and A. B. Bradley, "Subband/transform coding using filter bank designs based on time domain aliasing cancellation," IEEE Proc. Intl. Conf. on Acoustics, Speech, and Signal Processing (ICASSP) 12, 21612164 (1987). (Initial description of what is now called the MDCT.)
 A. W. Johnson and A. B. Bradley, "Adaptive transform coding incorporating time domain aliasing cancellation," Speech Comm. 6, 299308 (1987).
 For algorithms, see e.g.:
 ChiMin Liu and WenChieh Lee, "A unified fast algorithm for cosine modulated filterbanks in current audio standards", J. Audio Engineering 47 (12), 10611075 (1999).
 V. Britanak and K. R. Rao, "A new fast algorithm for the unified forward and inverse MDCT/MDST computation," Signal Processing 82, 433459 (2002)
 Vladimir Nikolajevic and Gerhard Fettweis, "Computation of forward and inverse MDCT using Clenshaw's recurrence formula," IEEE Trans. Sig. Proc. 51 (5), 14391444 (2003)
 CheHong Chen, BinDa Liu, and JarFerr Yang, "Recursive architectures for realizing modified discrete cosine transform and its inverse," IEEE Trans. Circuits Syst. II: Analog Dig. Sig. Proc. 50 (1), 3845 (2003)
 ...and references thereof.
Data compression methods Information theory Lossless Shannon–Fano · Shannon–Fano–Elias · Huffman · Adaptive Huffman · Arithmetic · Range · Golomb · Universal (Gamma · ExpGolomb · Fibonacci · Levenshtein)RLE · Byte pair encoding · DEFLATE · Lempel–Ziv (LZ77/78 · LZSS · LZW · LZWL · LZO · LZMA · LZX · LZRW · LZJB · LZS · LZT · ROLZ) · Statistical Lempel ZivOthersAudio Audio codec partsLPC (LAR · LSP) · WLPC · CELP · ACELP · Alaw · μlaw · ADPCM · DPCM · MDCT · Fourier transform · Psychoacoustic modelOthersImage TermsMethodsOthersVideo TermsVideo characteristics · Frame · Frame rate · Interlace · Frame types · Video quality · Video resolutionOthersSee Compression formats for formats and Compression software implementations for codecsCategories: Fourier analysis
 Discrete transforms
Wikimedia Foundation. 2010.
Look at other dictionaries:
Discrete cosine transform — A discrete cosine transform (DCT) expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy… … Wikipedia
Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… … Wikipedia
Discrete sine transform — In mathematics, the discrete sine transform (DST) is a Fourier related transform similar to the discrete Fourier transform (DFT), but using a purely real matrix. It is equivalent to the imaginary parts of a DFT of roughly twice the length,… … Wikipedia
Modulated complex lapped transform — The modulated complex lapped transform (MCLT) is a lapped transform, similar to the modified discrete cosine transform, that explicitly represents the phase (complex values) of the signal. References H. Malvar, A Modulated Complex Lapped… … Wikipedia
Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group … Wikipedia
MDCT — Modified Discrete Cosine Transform (Computing » Software) Modified Discrete Cosine Transform (Academic & Science » Mathematics) … Abbreviations dictionary
Window function — For the term used in SQL statements, see Window function (SQL) In signal processing, a window function (also known as an apodization function or tapering function[1]) is a mathematical function that is zero valued outside of some chosen interval … Wikipedia
List of Fourierrelated transforms — This is a list of linear transformations of functions related to Fourier analysis. Such transformations map a function to a set of coefficients of basis functions, where the basis functions are sinusoidal and are therefore strongly localized in… … Wikipedia
Vorbis — This article is about the audio compression codec. For the Discworld character, see Discworld characters. Vorbis Xiph.org Logo Filename extension .ogg .oga … Wikipedia
List of transforms — This is a list of transforms in mathematics.Integral transforms*Abel transform *Fourier transform **Short time Fourier transform *Hankel transform *Hartley transform *Hilbert transform **Hilbert Schmidt integral operator *Laplace transform… … Wikipedia