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 Week 2 of Lab 6 in ECE 438. A 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 X[k] where k = 0, 1, 2, ... N-1. Referring to our definition of the Discrete Fourier Transform above, it should be apparent that we are simply repeating 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], simply means repeating Eq. 1, N times, and each entry x[n] is a real scalar value. 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} $
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 discovery of the Fast Fourier Transform has reduced computation time by orders of magnitude.
\begin{bmatrix}
x[0] & 0 & {\dotsb} & 0 \\
0 & x[1] & {\dotsb} & {\vdots} \\
{\vdots} & & {\ddots} \\
0 & {\dotsb} & & x[N-1]
\end{bmatrix}
