| Line 56: | Line 56: | ||
x[0] & 0 & {\dotsb} & 0 \\ | x[0] & 0 & {\dotsb} & 0 \\ | ||
0 & x[1] & {\dotsb} & {\vdots} \\ | 0 & x[1] & {\dotsb} & {\vdots} \\ | ||
| − | {\vdots} & {\ddots} \\ | + | {\vdots} & & {\ddots} \\ |
0 & {\dotsb} & & x[N-1] | 0 & {\dotsb} & & x[N-1] | ||
\end{bmatrix} | \end{bmatrix} | ||
</math> | </math> | ||
Revision as of 12:16, 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] \\ {\vdots} \\ X[N-1] \end{bmatrix} = \begin{bmatrix} x[0] & 0 & {\dotsb} & 0 \\ 0 & x[1] & {\dotsb} & {\vdots} \\ {\vdots} & & {\ddots} \\ 0 & {\dotsb} & & x[N-1] \end{bmatrix} $
