Difference between revisions of "Fast Fourier Transform ECE438F12Ersoy" - Rhea

Revision as of 18:48, 7 November 2012

Defining equation for the N point DFT of the signal x(n) , so we have

$ X(k) = \sum_{n=0}^{N-1} x(n)e^{-j{\frac{2{\pi}kn}{N}}} $

We denote

X(k) = DFT_N[X(n)]               * Here we assume that N is even

In the preceding steps, we will show show Radix-2 FFT Alorithm for computation o the DFT based on the divide-and-conquer approach.

Step 1: Deine two new N/2 points from th original N point sequency x(n)

x₀(n) = x(2n)                even subset of x(n)

x₁(n) = x(2n + 1)            odd subset of x(n)

* where n  = 0,1,2 .... N/2-1

Step 2: Perform an N/2 point DFT on each subset

$ X_0 (k)=DFT_\frac{N}{2}[x_0 (n)] $

$ X_1 (k)=DFT_\frac{N}{2}[x_1 (n)] $

Then  we have

X(k) = X₀(k) + X₁(k)

Let n = 2m (even) and n = 2m+1 (odd)

$ {X(k) = \sum_{m=0}^{\frac{N}{2}-1} x(2m)e^{-j{\frac{2{\pi}k}{N}}(2m)}}+ { \sum_{m=0}^{\frac{N}{2}-1} x(2m+1)e^{-j{\frac{2{\pi}k}{N}}(2m+1)}} $ $ {X(k) = \sum_{m=0}^{\frac{N}{2}-1} x(2m)e^{-j{\frac{2{\pi}k}{N}}(2m)}}+ { {e^{-j{\frac{2{\pi}k}{N}}}}{\sum_{m=0}^{\frac{N}{2}-1} x(2m+1)e^{-j{\frac{2{\pi}k}{N}}(2m+1)}}} $

$ X(k)= X_0(k) + e^{-j{\frac{2{\pi}k}{N}}}X_1(k) $

Step 3: Define twiddle factor and find periodic version of X(k)

Notice: each N/2 point DFT is periodic with period N/2

So we have

$ X(k+ \frac{N}{2})= X_0(k+\frac{N}{2}) + e^{-j{\frac{2{\pi}}{N}}{(k+\frac{N}{2})}}X_1(k+\frac{N}{2}) $

$ X(k+ \frac{N}{2})= X_0(k+\frac{N}{2}) + e^{-j{\frac{2{\pi}k}{N}}}(-1)X_1(k+\frac{N}{2}) $

Let's define twiddle factors

$ W_N^k = e^{-j{\frac{2{\pi}k}{N}}} $

Then we can get the following expression

$ X(k+{\frac{N}{2}})= X_0(k) - e^{-j{\frac{2{\pi}k}{N}}}X_1(k) $

So we derive the a simple expression for the N point DFT

$ X(k)= X_0(k) + W_N^k X_1(K) $

$ X(k+{\frac{N}{2}})= X_0(k)- W_N^k X_1(K) $

•  For k = 0,1,2 ... N/2-1
  

These two expressions interpretate the N point DFT by using the "divide -and - conquer DFT"