**Forward DCT**

The DCT of a sequence
can be implemented by
FFT. First we define a new sequence
:

Then the DCT of can be written as the following (the coefficient is dropped for now for simplicity):

where the first summation is for all even terms and second all odd terms. We define for the second summation , then the limits of the summation and for becomes and for , and the second summation can be written as

Now the two summations in the expression of can be combined

Next, consider the DFT of :

If we multiply both sides by

and take the real part of the result (and keep in mind that both and are real), we get:

The last equal sign is due to the trigonometric identity:

This expression for is identical to that for above, therefore we get

where is the DFT of (defined from ) which can be computed using FFT algorithm with time complexity .

In summary, fast forward DCT can be implemented in 3 steps:

**Step 1:**Generate a sequence from the given sequence :

**step 2:**Obtain DFT of using FFT. (As is real, is symmetric and only half of the data points need be computed.)

**step 3:**Obtain DCT from by

**Inverse DCT**

The most obvious way to do inverse DCT is to reverse the order and the mathematical operations of the three steps for the forward DCT:

**step 1:**Obtain from . In step 3 above there are N equations but 2N variables (both real and imaginary parts of ). However, note that as are*real*, the real part of its spectrum is even (N+1 independent variables) and imaginary part odd (N-1 independent variables). So there are only N variables which can be obtained by solving the N equations.

**step 2:**Obtain from by inverse DFT also using FFT in complexity.

**Step 3:**Obtain from by

However, there is a more efficient way to do the inverse DCT. Consider first
the real part of the inverse DFT of the sequence
:

This equation gives the inverse DCT of all even data points . To obtain the odd data points, recall that , and all odd data points

can be obtained from the second half of the previous equation in reverse order .

In summary, we have these steps to compute IDCT:

**step 1:**Generate a sequence from the given DCT sequence :

**step 2:**Obtain from by inverse DFT also using FFT. (Only the real part need be computed.)

**Step 3:**Obtain from by

These three steps are mathematically equivalent to the steps of the first method.

See the demos.