The Discrete Cosine Transform (DCT)

In image coding (such as MPEG and JPEG), and many audio coding algorithms (MPEG), the discrete cosine transform (DCT) is used because of its nearly optimal asymptotic theoretical coding gain.^A.9For 1D signals, one of several DCT definitions (the one called DCT-II)^A.10is given by

$\displaystyle \hbox{\sc DCT}_k(x)$	$\displaystyle =$	$\displaystyle 2\sum_{n=0}^{N-1} x(n) \cos\left[\frac{\pi k}{2N}(2n+1)\right], \quad k=0,1,2,\ldots,N-1$
	$\displaystyle =$	$\displaystyle 2\sum_{n=0}^{N-1} x(n) \cos\left[\omega_k\left(n+\frac{1}{2}\right)\right] \protect$	(A.2)

where

$\displaystyle \omega_k \isdef \frac{2\pi}{2N}k.$

Note that $\omega_k$ is the DFT frequency for a length

DFT (as opposed to

For real signals, the real part of the DFT is a kind of DCT:

$\begin{eqnarray*} \mbox{re}\left\{\hbox{\sc DFT}_k(x)\right\} &\isdef & \mbox{r... ...right\}\\ &=& \sum_{n=0}^{N-1} x(n) \cos\left(\omega_k n\right) \end{eqnarray*}$

Thus, the real part of a double-length FFT is the same as the DCT except for the half-sample phase shift in the sinusoidal basis functions $s_k(n) = e^{j\omega_k n}$ (and a scaling by 2 which is unimportant).

In practice, the DCT is normally implemented using the same basic efficiency techniques as in FFT algorithms. In Matlab and Octave (Octave-Forge), the functions dct and dct2 are available for the 1D and 2D cases, respectively.

Exercise: Using Euler's identity, expand the cosine in the DCT defined by Eq. $\,$ (A.2) above into a sum of complex sinusoids, and show that the DCT can be rewritten as the sum of two phase-modulated DFTs:

$\displaystyle \hbox{\sc DCT}_{N,k} = e^{j\omega_k\frac{1}{2}} \overline{X_{2N}(\omega_k)} +e^{-j\omega_k\frac{1}{2}} X_{2N}(\omega_k)$

where $X_{2N}(\omega_k)=\hbox{\sc DFT}_{2N,k}(x)$ denotes the length

DFT of

Previous: Related Transforms
Next: Number Theoretic Transform

Order a Hardcopy of Mathematics of the DFT

About the Author: Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.

Sign in

Search Online Books

Free Online Books

Ads

Chapters

See Also

Mathematics of the DFT
    Fast Fourier Transform (FFT) Algorithms
       Related Transforms
          The Discrete Cosine Transform (DCT)