Comparison of the DFT and FFT via Matrices
BY: Cary A. Wood
The purpose of this article is to illustrate the differences of the Discrete Fourier Transform (DFT) versus the Fast Fourier Transform (FFT). In addition, it will provide an alternative view of the FFT calculation path as described in Lab 6 (Week 2, pg. 5) of ECE 438. The link can be found here [1]. Please note the following explanation of the FFT will utilize the "divide and conquer" method and assume the user understands its basic concepts.
To start, we will define the DFT as,
$ X_N[k] = \sum_{n=0}^{N-1} x[n] e^{-j2{\pi}kn/N} {\;} {\;} (Eq. 1) $
It is fairly easy to visualize this 1 point DFT, but how does it look when x[n] has 8 points, 1024 points, etc. That's where matrices come in. For an N point DFT, we will define our input as x[n] where n = 0, 1, 2, ... N-1. Similarly, the output will be defined as X[k] where k = 0, 1, 2, ... N-1. Referring to our definition of the Discrete Fourier Transform above, to compute an N point DFT, all we need to do is simply repeat Eq. 1 N times. For every value of x[n] in the discrete time domain, there is a corresponding value, X[k].
Input x[n]
$ \begin{bmatrix} x[0] & x[1] & {\;}{\dotsb} & x[N-1] \end{bmatrix} $
Output X[k]
$ \begin{bmatrix} X[0] \\ X[1] \\ {\vdots} \\ X[N-1] \end{bmatrix} $
To solve for X[K], means simply repeating Eq. 1, N times, where x[n] is a real scalar value for each entry. We represent this in the matrices below.
$ \begin{bmatrix} X[0] \\ X[1] \\ X[2] \\ {\vdots} \\ X[N-1] \end{bmatrix} = x[0]\begin{bmatrix} e^{-j2{\pi}(0)n/N} \\ e^{-j2{\pi}(0)n/N} \\ e^{-j2{\pi}(0)n/N} \\ {\vdots} \\ e^{-j2{\pi}(0)n/N} \end{bmatrix} + x[1]\begin{bmatrix} e^{-j2{\pi}(0)/N} \\ e^{-j2{\pi}(1)/N} \\ e^{-j2{\pi}(2)/N} \\ {\vdots} \\ e^{-j2{\pi}(N-1)/N} \end{bmatrix} + x[2]\begin{bmatrix} e^{-j2{\pi}(0)/N} \\ e^{-j2{\pi}(2)/N} \\ e^{-j2{\pi}(4)/N} \\ {\vdots} \\ e^{-j2{\pi}2(N-1)/N} \end{bmatrix} + {\dotsb} + x[N-1]\begin{bmatrix} e^{-j2{\pi}(0)/N} \\ e^{-j2{\pi}(N-1)/N} \\ e^{-j2{\pi}2(N-1)/N} \\ {\vdots} \\ e^{-j2{\pi}{(N-1)^2}/N} \end{bmatrix} {\;} {\;} (Eq. 2) $
From this matrix representation of the DFT, you can see that N^2 complex multiplications and N^2 - N complex additions are necessary to fully compute the discrete fourier transform. There are a few simplifications that can be made right away. The first column vector of complex exponentials can be reduced to a vector of 1's. This is possible because, e^(0*anything) will always equal 1. This also applies for the first entry in each vector of complex exponentials because n always begins at 0.
Whats happens when we want to perform the DFT on 3 minute audio signal recorded at a 44.1 kHz sampling. Our handy-dandy DFT suddenly becomes extremely lengthy since computation time increases with a rate of N^2. Due to the work of Cooley and Turkey and previously developed by Gauss, the development of the Fast Fourier Transform has reduced computation time by orders of magnitude.
To derive the FFT we will use the "divide and conquer" method as stated before. This means that we will divide Eq. 1 into two separate equations. The first equation processes the even components of x[n] while the second equation processes the odd components of x[n]. This produces,
$ X_N[k] = \sum_{n=0,even}^{N-1} x[n] e^{-j2{\pi}kn/N} + \sum_{n=0,odd}^{N-1} x[n] e^{-j2{\pi}kn/N} {\;} {\;} (Eq. 3) $
Now replace n with 2m for the first summation, and n with 2m + 1 in the second summation. Since our vector x[n] was cut in half for each summation, N-1 becomes (N/2) - 1.
$ X_N[k] = \sum_{m=0}^{{N/2}-1} x[2m] e^{-j2{\pi}k(2m)/N} + \sum_{m=0}^{{N/2}-1} x[2m+1] e^{-j2{\pi}k(2m+1)/N} $
Looking at the previous equation, we can re-arrange the complex exponential in first summation so that we get an N/2 point DFT. In second summation, we can factor the complex exponential to achieve another (N/2) point DFT multiplied by a complex exponential.
$ X_N[k] = \sum_{m=0}^{{N/2}-1} x[2m] e^{-j2{\pi}k(m)/(N/2)} + e^{-j2{\pi}k/N}\sum_{m=0}^{{N/2}-1} x[2m+1] e^{-j2{\pi}k(m)/(N/2)} {\;} {\;} (Eq. 4) $
Our DFT has now been successfully split into two N/2 pt DFT's. For simplification purposes, the first summation will be defined as,
$ X_0[k] {\;} with input {\;} x_0[n] = x[2n] {(even x) {\;} $
And our second summation will be denoted as,
$ X_1[k] $ with input $ x_1[n] = x[2n+1] $ (odd x)
From this statement, our Eq. 4 can be simplified to,
$ X[k] = X_0[k] + e^{-j2{\pi}k/N}X_1[k] $
where $ X_0[k] = DFT_{N/2}[x_0[n]], {\;} X_1[k] = DFT_{N/2}[x_1[n]] $
