DSPRelated.com
Free Books
   Free Books    Mathematics of the DFT  

Related Transforms

There are alternatives to the Cooley-Tukey FFT which can serve the same or related purposes and which can have advantages in certain situations [10]. Examples include the fast discrete cosine transform (DCT) [5], discrete Hartley transform [21], and number theoretic transform [2].

The DCT, used extensively in image coding, is described in §A.6.1 below. The Hartley transform, optimized for processing real signals, does not appear to have any advantages over a ``pruned real-only FFT'' [74]. The number theoretic transform has special applicability for large-scale, high-precision calculations (§A.6.2 below).

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 $ 2N$ DFT (as opposed to $ N$).

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 $ 2N$ DFT of $ x$.

Number Theoretic Transform

The number theoretic transform is based on generalizing the $ N$th primitive root of unity (see §3.12) to a ``quotient ring'' instead of the usual field of complex numbers. Let $ W_N$ denote a primitive $ N$th root of unity. We have been using $ W_N = \exp(-j2\pi/N)$ in the field of complex numbers, and it of course satisfies $ W_N^N=1$, making it a root of unity; it also has the property that $ W_N^k$ visits all of the ``DFT frequency points'' on the unit circle in the $ z$ plane, as $ k$ goes from 0 to $ N-1$.

In a number theory transform, $ W_N$ is an integer which satisfies

$\displaystyle W_N^N = 1\left(\mbox{mod}\;p\right) $

where $ p$ is a prime integer. From number theory, for each prime number $ p$ there exists at least one primitive root $ r$ such that $ r^n$ (modulo $ p$) visits all of the numbers $ 1$ through $ p-1$ in some order, as $ n$ goes from $ 1$ to $ p-1$. Since $ m^{p-1}=1\left(\mbox{mod}\;p\right)$ for all integers $ m$ (another result from number theory), $ r$ is also an $ N$th root of unity, where $ N=p-1$ is the transform size. (More generally, $ N$ can be any integer divisor $ L$ of $ p-1$, in which case we use $ W_N=r^L$ as the generator of the numbers participating in the transform.)

When the number of elements in the transform is composite, a ``fast number theoretic transform'' may be constructed in the same manner as a fast Fourier transform is constructed from the DFT, or as the prime factor algorithm (or Winograd transform) is constructed for products of small mutually prime factors [43].

Unlike the DFT, the number theoretic transform does not transform to a meaningful ``frequency domain''. However, it has analogous theorems, such as the convolution theorem, enabling it to be used for fast convolutions and correlations like the various FFT algorithms.

An interesting feature of the number theory transform is that all computations are exact (integer multiplication and addition modulo a prime integer). There is no round-off error. This feature has been used to do fast convolutions to multiply extremely large numbers, such as are needed when computing $ \pi $ to millions of digits of precision.

Next Section:
FFT Software
Previous Section:
Fast Transforms in Audio DSP