| Line 1: | Line 1: | ||
'''Comparison of the DFT and FFT via Matrices''' | '''Comparison of the DFT and FFT via Matrices''' | ||
| + | BY: Cary A. Wood | ||
<span> | <span> | ||
| Line 22: | Line 23: | ||
<math> | <math> | ||
\begin{bmatrix} | \begin{bmatrix} | ||
| − | x[0] & x[1] & {\ | + | x[0] & x[1] & {\dotsb} & x[N-1] |
\end{bmatrix} | \end{bmatrix} | ||
</math> | </math> | ||
Revision as of 11:07, 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.
</math> \being{equation} \begin{bmatrix} X[0] \\ X[1] \\ {\vdots} \\ X[N-1] \end{bmatrix} = \being{bmatrix} x[0]
\end{equation}
</math>
