Derivation of fast DCT-4 algorithm based on DFT

It’s well known that an point DCT-4 can be computed using an point complex FFT. Although the algorithm is widespread, the texts which I have read on the subject have not provided the details as to how it works. I’ve been trying to understand this for a while (I tend not to use algorithms until I understand them) and finally figured it out and thought I would share (please provide comments/links if you can find a better or shorter explanation – this is as good as I could get).

Trig functions are hard to manipulate in expressions (for me anyway), so knowing that is real, we change the into a complex exponential and obtain the following:

It is worth noting that the sign of the exponent is irrelevant.

We then split the expression up to operate over two half-length sequences composed of and . The second sequence is reversed and decimated because when the is replaced by in the term of the exponential, the expression is negated rather than the offset being modified. We move the term into another exponential which becomes trivial as cancels the denominator. i.e.:

Or:

The exponentials still contain no term which resembles an DFT (over length anyway). To get one, we break up into the terms and . Again we choose to reverse the second sequence because it will keep the exponential terms in a similar but negated form.

Now because we are only interested in the real terms, we can ignore or conjugate anything which contributes to the imaginary term of the above expressions. This means that we can conjugate the exponentials when they are only modulating a real term. Doing this, we obtain:

Almost there, but to obtain the full benefit we need the inner terms to be the same. If we now multiply the term by , we get:

Done. If we expand out the and terms completely we get:

Which give us the steps for a DFT based DCT-4 algorithm:

• Transform the point real sequence into the point complex sequence .
• Multiply each element of the sequence by .
• Find , the DFT of the sequence .
• Multiply each element of by .
• The DCT-4 outputs are given by:

2 thoughts on “Derivation of fast DCT-4 algorithm based on DFT”

1. Niels Möller

Note that it’s an easy change to use identical pre- and postfactors,

e^{- j \pi (k+1/8) / N}

The interesting property is that when we multiply together all
the exponentials, the FFT exponent 4nk/N is replaced by

4 n k/N + (k+1/8) / N + (n+1/8) / N
= (4n+1)(4k+1) / 4N

which resembles the DCT “kernel” expression, for indices 2n and 2k.