next up previous
Next: About this document ... Up: dct Previous: Definition of DCT

Fast DCT algorithm

Forward DCT

The DCT of a sequence $\{x[m],\;\;\;(m=0,\cdots,N-1)\;\}$ can be implemented by FFT. First we define a new sequence $\{\;y[m],\;\;\;(m=0,\cdots,N-1)\;\}$:

\begin{displaymath}\left\{ \begin{array}{ll} y[m]\stackrel{\triangle}{=}x[2m] & ...
...triangle}{=}x[2m+1] & (i=0,\cdots, N/2-1) \end{array} \right.

Then the DCT of $x[n]$ can be written as the following (the coefficient $a[n]$ is dropped for now for simplicity):
$\displaystyle X[n]$ $\textstyle =$ $\displaystyle \sum_{m=0}^{N-1} x[m] \cos\left( \frac{ (2m+1)n\pi}{2N}\right)$  
  $\textstyle =$ $\displaystyle \sum_{m=0}^{N/2-1}x[2m] \cos\left( \frac{ (4m+1)n\pi}{2N} \right) +
\sum_{m=0}^{N/2-1}x[2m+1] \cos\left( \frac{ (4m+3)n\pi}{2N} \right)$  
  $\textstyle =$ $\displaystyle \sum_{m=0}^{N/2-1}y[m] \cos\left( \frac{ (4m+1)n\pi}{2N} \right)+
\sum_{m=0}^{N/2-1}y[N-1-m] \cos\left( \frac{ (4m+3)n\pi}{2N}\right)$  

where the first summation is for all even terms and second all odd terms. We define for the second summation $m'\stackrel{\triangle}{=}N-1-m$, then the limits of the summation $0$ and $N/2-1$ for $m$ becomes $N-1$ and $N/2$ for $m'$, and the second summation can be written as

\sum_{m'=N/2}^{N-1} y[m'] \cos\left( 2n\pi - \frac{ (4m'+1)...
...m'=N/2}^{N-1} y[m'] \cos\left( \frac{ (4m'+1)n\pi}{2N} \right)

Now the two summations in the expression of $X[n]$ can be combined

\begin{displaymath}X[n]=\sum_{m=0}^{N-1}y[m] \cos\left( \frac{ (4m+1)n\pi}{2N}\right) \end{displaymath}

Next, consider the DFT of $y[m]$:

Y[n]=\sum_{m=0}^{N-1} y[m] e^{-j2\pi mn/N}
...i mn}{N}\right)-j\;\sin\left(\frac{2\pi mn}{N}\right) \right]

If we multiply both sides by

\begin{displaymath}e^{-jn\pi/2N}=\cos\left(\frac{n\pi}{2N}\right)-j\;\sin\left(\frac{n\pi}{2N}\right) \end{displaymath}

and take the real part of the result (and keep in mind that both $x[m]$ and $y[m]$ are real), we get:

Re[e^{-jn\pi/2N} Y[n]]=\sum_{m=0}^{N-1} y[m] \left[\cos\left...
...sum_{m=0}^{N-1} y[m] \cos\left( \frac{ (4m+1)n\pi}{2N} \right)

The last equal sign is due to the trigonometric identity:

\begin{displaymath}cos(\alpha+\beta)=cos \alpha \;cos \beta - sin \alpha \;sin \beta \end{displaymath}

This expression for $Re[e^{-jn\pi/2N} Y[n]]$ is identical to that for $X[n]$ above, therefore we get

\begin{displaymath}X[n]=Re[\; e^{-jn\pi/2N} Y[n]\;] \end{displaymath}

where $Y[n]$ is the DFT of $y[m]$ (defined from $x[m]$) which can be computed using FFT algorithm with time complexity $O(N log_2 N)$.

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

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:

However, there is a more efficient way to do the inverse DCT. Consider first the real part of the inverse DFT of the sequence $X[n]e^{jn\pi/2N}$:

Re\;\left[ \sum_{n=0}^{N-1} [X[n]e^{jn\pi/2N}]\;e^{j2\pi mn...
= x[2m]\;\;\;\;\;\;(m=0, \cdots, N-1)

This equation gives the inverse DCT of all $N/2$ even data points $x(2m)\;\;\;\;(m=0,\cdots,N/2-1)$. To obtain the odd data points, recall that $x[m]=x[2N-m-1]$, and all odd data points


can be obtained from the second half of the previous equation in reverse order $(m=N-1, N-2, \cdots, N/2)$.

In summary, we have these steps to compute IDCT:

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

See the demos.

next up previous
Next: About this document ... Up: dct Previous: Definition of DCT
Ruye Wang 2013-10-27