Editing Modified discrete cosine transform (section)

== Definition ==

As a lapped transform, the MDCT is somewhat unusual compared to other Fourier-related transforms in that it has half as many outputs as inputs (instead of the same number).  In particular, it is a [[linear function]] <math>F\colon \mathbf{R}^{2N} \to \mathbf{R}^N</math> (where '''R''' denotes the set of [[real number]]s).  The 2''N'' real numbers ''x''<sub>0</sub>, ..., ''x''<sub>2''N''−1</sub> are transformed into the ''N'' real numbers ''X''<sub>0</sub>, ..., ''X''<sub>''N''−1</sub> according to the formula
: <math>X_k = \sum_{n=0}^{2N-1} x_n \cos\left[\frac{\pi}{N} \left(n + \frac{1}{2} + \frac{N}{2}\right) \left(k + \frac{1}{2}\right) \right].</math>

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 ''time-domain aliasing cancellation'' ('''TDAC''').

The IMDCT transforms ''N'' real numbers ''X''<sub>0</sub>, ..., ''X''<sub>''N''−1</sub> into 2''N'' real numbers ''y''<sub>0</sub>, ..., ''y''<sub>2''N''−1</sub> according to the formula
: <math>y_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cos\left[\frac{\pi}{N} \left(n + \frac{1}{2} + \frac{N}{2}\right) \left(k + \frac{1}{2}\right) \right].</math>

Like for the [[Discrete_cosine_transform#DCT-IV|DCT-IV]], 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''<sup>2</sup>) 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 post-processing steps.  Also, as described below, any algorithm for the DCT-IV immediately provides a method to compute the MDCT and IMDCT of even size.