Lair Of The Multimedia Guru

Its really high time to update by blog before it starts rotting. So here are a few words about the modified discrete cosine transform. The reason why iam writing this, is that most docs about the MDCT ive seen are quite obfuscated so i thought maybe i could do better (or worse ;)). Note ive made no attempt to write formal proofs for sake of readability, but they are all very trivial.

Basis functions of the normal DCT

Basis functions of the MDCT

Both of the transforms have orthogonal basis functions, that is the forward transform is simply the series of dot products of the input and the basis functions. While the inverse transform is the sum of the basis functions each scaled by the dot product from the forward transform. This can also be said in a dozen different ways …

What makes the MDCT special, is that it has half as many basis functions as it has inputs. Thus performing the MDCT and then IMDCT on a single block will generally not result in the original. The magic with the MDCT is that it can be overlapped by 50% and then suddenly doing the MDCTs and IMDCTs leads to perfect reconstruction of the original. One can see such lapped transform as a single non lapped transform of infinite length if one wants.

To proof that simply applying the MDCT and then the IMDCT on each block i, which is 50% lapped over block i-1 leads to the original, one really only has to proof that all basis functions are orthogonal (have a mutual dot product = 0). We already assumed that the basis functions of a single MDCT are orthogonal (that can easily be proofen by trigonometric identities if someone is bored). We also know that non adjacent blocks can only have mutually orthogonal basis functions as they do not overlap. Whats left are the adjacent blocks. The proof for their orthogonality is very trivial, if one looks at the graph above, it is immedeatly obvious that there are 2 symmetries one at 0.25 and one at 0.75 in all basis functions. So they behave as (…, c, b, a, -a, -b, -c, …, x, y, z, z, y, x, …). Thus the dot product of 2 basis functions of 2 adjacent blocks is …
… c*x + b*y + a*z – a*z – b*y – c*x … which is obviously 0.

I also should mention that because of these 2 symmetries mentioned above one really just needs to calculate 50% of the IMDCT as the rest is identical up to the sign

The above is still missing one detail, that is that normally the (I)MDCT is used with a window to smoothly get the basis functions down to 0 at their ends. An example with sine window is below

The obvious question is, are the basis functions still orthogonal? The blocks which are not adjacent of course still have to be because their basis functions dont overlap. The basis functions from adjacent blocks assuming a symmetric window
(…c*w_-2, b*w_-1, a*w₀, -a*w₁, -b*w₂, -c*w₃, …, x*w₃, y*w₂, z*w₁, z*w₀, y*w_-1, x*w_-2, …) now have a dot product of …c*w_-2*x*w₃ + b*w_-1*y*w₂ + a*w₀*z*w₁ – a*w₁*z*w₀ – b*w₂*y*w_-1 – c*w₃*x*w_-2 … which is still 0 thus to our “big surprise” any symmetric window maintains orthogonality between 2 adjacent blocks. Whats left are the basis functions within a block. For them the dot product looks like
… c*C*w_-2² + b*B*w_-1² + a*A*w₀² + a*A*w₁² + b*B*w₂² + c*C*w₃² … + x*X*w₃² + y*Y*w₂² + z*Z*w₁² + z*Z*w₀² + y*Y*w_-1² + x*X*w_-2² …
or reordered and common stuff factored out:
… c*C*(w_-2²+w₃²) + b*B*(w_-1²+w₂²) + a*A*(w₀²+ w₁²) +
… x*X*(w₃²+w_-2²) + y*Y*(w₂²+w_-1²) + z*Z*(w₁² + w₀²)
If we now choose a window for which w_i² + w_1-i² = 2 then the dot product equals what it is without the window, thus our windowed MDCT is still orthogonal and thus easy invertible