Difference between revisions of "Comparison of DFT and FFT via Matrices" - Rhea

Revision as of 11:37, 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, 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} + 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}