Comparison of DFT and FFT via Matrices - Rhea

Comparison of the DFT and FFT via Matrices

   The purpose of this article is to illustrate the differences of the Discrete Fourier Transform (DFT) versus the Fast Fourier Transform (FFT). Please note, the following explanation of the FFT will use the "divide and conquer" method. 

   To start, we will define the DFT as, 

$ X[k] = \sum_{n=0}^{N-1} x[n] e^{-j2pikn/N} $

x[n] = n²(u[n + 3] − u[n − 1])

x[n] = n²(δ(n + 3) + δ(n + 2) + δ(n + 1) + δ(n))

$ X(z) = \sum_{n=-\infty}^{+\infty} x[n] z^{-n} $

$ X(z) = \sum_{n=-\infty}^{+\infty} n^2(\delta(n+3)+\delta(n+2)+\delta(n+1)+\delta(n)) z^{-n} $

X(z) = 9z³ + 4z² + z + 1 for all z in complex plane