| Line 49: | Line 49: | ||
X[0] \\ | X[0] \\ | ||
X[1] \\ | X[1] \\ | ||
| + | X[2] \\ | ||
{\vdots} \\ | {\vdots} \\ | ||
X[N-1] | X[N-1] | ||
\end{bmatrix} | \end{bmatrix} | ||
= | = | ||
| − | x[0] | + | x[0]\begin{bmatrix} |
e^{-j2{\pi}(0)n/N} \\ | e^{-j2{\pi}(0)n/N} \\ | ||
| − | e^{-j2{\pi}( | + | 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} \\ | {\vdots} \\ | ||
e^{-j2{\pi}(N-1)/N} | 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} | ||
| + | |||
| + | + | ||
| + | |||
| + | x[N-1]{/dotsb}\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} | \end{bmatrix} | ||
Revision as of 11:34, 26 October 2013
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, I 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 use the "divide and conquer" method.
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. We present this in 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} + x[N-1]{/dotsb}\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} $
\begin{bmatrix}
x[0] & 0 & {\dotsb} & 0 \\
0 & x[1] & {\dotsb} & {\vdots} \\
{\vdots} & & {\ddots} \\
0 & {\dotsb} & & x[N-1]
\end{bmatrix}
