Definition of DCT

The discrete Fourier transform (DFT) transforms a complex signal into its complex spectrum. However, if the signal is real as in most of the applications, half of the data is redundant. In time domain, the imaginary part of the signal is all zero; in frequency domain, the real part of the spectrum is even symmetric and imaginary part odd. In comparison, Discrete cosine transform (DCT) transforms is a real transform that transforms a sequence of real data points into its real spectrum and therefore avoids the problem of redundancy. Also, as DCT is derived from DFT, all the desirable properties of DFT (such as fast algorithm) are preserved.

To derive the DCT of an N-point real signal sequence $\{x[m],\;\;\;(m=0,\cdots,N-1)\;\}$, we first construct a new sequence of $2N$ points:

$$x'[m]\stackrel{\triangle}{=}\left\{ \begin{array}{ll} x[m] ... ...\leq N-1) x[-m-1] & (-N \leq m \leq -1) \end{array} \right.$$

This 2N-point sequence $x'[m]$ is assumed to repeat its self outside the range $-N \leq n \leq N-1$, i.e., it is periodic with period $2N$, and it is even symmetric with respect to the point $m=-1/2$:

$$x'[m]=x'[-m-1]=x'[2N-m-1]$$

If we shift the signals $x'[m]$ to the right by 1/2, or, equivalently, shift $m$ to the left by 1/2 by defining another index $m'=m+1/2$, then $x'[m]=x'[m'-1/2]$ is even symmetric with respect to $m'=0$. In the following we simply represent this new function by $x[m]$.

The DFT of this 2N-point even symmetric sequence can be found as:

$$X[n] = \frac{1}{\sqrt{2N}} \sum_{m'=-N+1/2}^{N-1/2} x[m'-\frac{1}{2}]e^{-j2\pi m'n/2N}$$

$$= \frac{1}{\sqrt{2N}} \sum_{m=-N+1/2}^{N-1/2}x[m'-\frac{1}{2}]\;cos... ...ac{j}{\sqrt{2N}} \sum_{m=-N}^{N-1/2}x[m'-\frac{1}{2}]\;sin(\frac{2\pi m'n}{2N})$$

$$= \frac{1}{\sqrt{2N}} \sum_{m=-N+1/2}^{N-1/2}x[m'-\frac{1}{2}]\;cos(\frac{2\pi m'n}{2N}) \;\;\;\;\;\;\;(n=0,\cdots,2N-1)$$

Note that the second summation above is zero. This is because $x[m]$ is even and $sin((2m+1)n\pi/2N)$ is odd with respect to $m=-1/2$, all terms in the second summation are odd and the summation is zero (while all terms in the first summation are even). It can also be seen that all $X[n]$ is real and even $X[n]=X[-n]$. Next, we replacie $m'$ by $m+1/2$ and get

$$X[n] = \frac{1}{\sqrt{2N}} \sum_{m=-N+1/2}^{N-1/2}x[m'-\frac{1}{2}]\;cos... ...'n}{2N}) =\frac{1}{\sqrt{2N}} \sum_{m=-N}^{N-1}x[m]\;cos(\frac{(2m+1)n\pi}{2N})$$

$$= \sqrt{\frac{2}{N}} \sum_{m=0}^{N-1}x[m]\;cos(\frac{(2m+1)n\pi}{2N}), \;\;\;\;\;\;\;(n=0,\cdots,2N-1)$$

Note that since all terms in the summation are even, only the first half of the data points need to be used. Moreover, as cosine function is even, $X[n]=X[-n]$ is also even and periodic with period $2N$, we have $X[N+n]=X[N+n-2N]=X[-N+n]=X[N-n]$, indicating that a point $X[N+n]$ ( $n=0,1,\cdots,N-1$) in the second half is the same as its corresponding point $X[N-n]$ in the first half, i.e., the second half is redundant and therefore can be dropped. Now we have the discrete cosine transform (DCT):

$$X[n]=\sqrt{\frac{2}{N}} \sum_{m=0}^{N-1}x[m]\;cos(\frac{(2m+1... ... =\sum_{m=0}^{N-1} c[n,m]x[m], \;\;\;\;\;\;\;(n=0,\cdots,N-1)$$

where $c[n,m]$ the nth row and mth column of the DCT matrix:

$$c[n,m]\stackrel{\triangle}{=}\sqrt{\frac{2}{N}}cos(\frac{ (2m+1)n\pi}{2N}) \;\;\;\;\;(m,n=0,1,\cdots,N-1)$$

All row vectors of this DCT matrix are orthogonal and normalized except the first one ($n=0$):

$$\sqrt{\sum_{m=0}^{N-1}c^2[n,m]}= \sqrt{\sum_{m=0}^{N-1}\;\fra... ...sqrt{2} & (n=0) 1 & (n=1,2,\cdots,N-1) \end{array} \right.$$

To make DCT a orthonormal transform, we define a coefficient

$$a[n]=\left\{ \begin{array}{ll} \sqrt{1/N} & \mbox{for $n=0$} ... ...rt{2/N} & \mbox{for $ n=1,2,\cdots,N-1$} \end{array} \right.$$

so that DCT now becomes

$$X[n] = a[n] \sum_{m=0}^{N-1}x[m]\;cos(\frac{ (2m+1)n\pi}{2N}) =\sum_{m=0}^{N-1}x[m]\;c[n,m]\;\;\;\;\;\;\;(n=0,\cdots,N-1)$$

where $c[n,m]$ is modified with $a[n]$, which is also the component in the nth row and mth coloum of the N by N cosine transform matrix:

$$\left[ \begin{array}{ccc} \cdots & \cdots & \cdots \\ \cdots... ...^T \cdots {\bf c}_{N-1}^T \end{array} \right] ={\bf C}^T$$

Here ${\bf c}_i^T=[c[i,0],\cdots,c[i,N-1]$ is the ith row of the DCT transform matrix ${\bf C}$. As these row vectors are orthogonal:

$$({\bf c}_i,{\bf c}_j)={\bf c}_i^T {\bf c}_j =\delta_{ij} =\left\{ \begin{array}{ll}1 & i=j 0 & i\ne j \end{array} \right.$$

the DCT matrix ${\bf C}$ is orthogonal:

$${\bf C}^{-1}={\bf C}^T,\;\;\;\;\mbox{i.e.} \;\;\;\;{\bf C}^T {\bf C}= {\bf I}$$

and it is real ${\bf C}={\bf C}^*$. Now the DCT can be expressed in matrix form as:

$${\bf X}={\bf C}^T {\bf x}$$

The inverse DCT is

$$x[m] = \sum_{n=0}^{N-1} X[n]\;c[m,n]= \sum_{n=0}^{N-1} a[n] X... ...}) =\sum_{n=0}^{N-1}X[n]\;c[n,m]\;\;\;\;\;\;\;(m=0,\cdots,N-1)$$

or in matrix form:

$${\bf x}=({\bf C}^T)^{-1} {\bf X} ={\bf C}{\bf X}$$

Example: A $N=4$-point DCT matrix can be generated by $c[n,m]=a[n] cos( (2m+1)n\pi/8)$ to be

$${\bf C}^T=\left[ \begin{array}{c} {\bf c}_0^T \\ \vdots \\ {\... ....50 & 0.50 \\ 0.27 & -0.65 & 0.65 & -0.27 \end{array} \right]$$

Assume the signal is ${\bf x}=[0\; 1\; 2\; 3]^T$, then its DCT transform is:

$${\bf X}={\bf C}^T {\bf x}=\left[ \begin{array}{rrrr} 0.50 & ... ...egin{array}{r} 3.00 -2.23 0.00 -0.16 \end{array} \right]$$

The inverse transform is:

$${\bf x}={\bf C} {\bf X}=\left[ \begin{array}{rrrr} 0.50 & 0.... ...ht] =\left[ \begin{array}{r} 0 1 2 3 \end{array} \right]$$

This result is very similar to the example shown in the previous section for WHT transform. In fact, these two transforms are very comparible, as seen from the figure below:

Compared with DFT, DCT has two main advantages:

• It is a real transform with better computational efficiency than DFT which by definition is a complex transform.
• It does not introduce discontinuity while imposing periodicity in the time signal. In DFT, as the time signal is truncated and assumed periodic, discontinuity is introduced in time domain and some corresponding artifacts is introduced in frequency domain. But as even symmetry is assumed while truncating the time signal, no discontinuity and related artifacts are introduced in DCT.