A Fast MDCT Implementation

The MDCT can be calculated using FFT. The naive approach, though, requires a $2n$ length FFT for a length $n$ block, because of the odd transform. There are faster approaches though [6]. The MDCT can be rewritten as an odd-time odd-frequency discrete Fourier transform (O$^2$DFT)

$$X(m) = \Re(O^2DFT_{shft(fx)}(m)) = \Re(\sum_{k=0}^{N-1}{f(k-\frac{n}{4})x(k-\frac{n}{4}) e^{\frac{-j\pi}{2n}(2k+1)(2m+1)}}).$$ (23)

[6] presents a fast algorithm for calculating

$$\mathcal{W} = O^2DFT(odd(f(k-\frac{n}{4})x(k-\frac{n}{4}))) = X(m)$$ (24)

as

$$\mathcal{W}_{2k} = \Re(\mathcal{P}_k)$$ (25)

$$\mathcal{W}_{n/2+2k} = \Im(\mathcal{P}_k)$$ (26)

$$\mathcal{W}_{2k+1} = -\mathcal{W}_{n-2(k+1)}$$ (27)

where

$$\mathcal{P}_k = 2e^{-j\frac{2\pi}{n}(k+\frac{1}{8})} \underb... ...{1}{8})}) e^{-j\frac{2\pi}{n/4}rk}} }_{n/4\ {\rm point\ FFT}}.$$ (28)

Thus, the MDCT can be calculated using only one $n/4$ point FFT and some pre- and post-rotation of the sample points. The IMDCT can be calculated in a similar way. See the code for a more detailed description.