| Line 1: | Line 1: | ||
| − | Defining equation for the | + | Defining equation for the N point DFT of the signal x(n) , so we have<br> |
| − | <math>X(k) = \sum_{n=0}^{N-1} x(n)e^{-j{\frac{2{\pi}kn}{N}}}</math><br><br> | + | <math>X(k) = \sum_{n=0}^{N-1} x(n)e^{-j{\frac{2{\pi}kn}{N}}}</math><br> |
| + | |||
| + | We denote | ||
| + | |||
| + | <span class="texhtml">''X''(''k'') = ''DFT''<sub>''N''</sub>[''X''(''n'')]</span> <span class="texhtml">* Here we assume that N is even</span> | ||
| + | |||
| + | <br> | ||
| + | |||
| + | In the preceding steps, we will show show Radix-2 FFT Alorithm for computation o the DFT based on the divide-and-conquer approach. | ||
| + | |||
| + | <u>Step 1</u>: Deine two new N/2 points from th original N point sequency x(n) | ||
| + | |||
| + | <span class="texhtml"><sub></sub></span><span class="texhtml">''x''<sub>0</sub>(''n'') = ''x''(2''n'')</span> even subset of x(n)<br> | ||
| + | |||
| + | <span class="texhtml">''x''<sub>1</sub>(''n'') = ''x''(2''n'' + 1) odd subset of x(n)</span> | ||
| + | |||
| + | <span class="texhtml">* where n = 0,1,2 .... N/2-1</span> | ||
| + | |||
| + | <br> | ||
| + | |||
| + | <u></u><u>Step 2:</u> Perform an N/2 point DFT on each subset | ||
| + | |||
| + | <math>X_0 (k)=DFT_\frac{N}{2}[x_0 (n)]</math><br> | ||
| + | |||
| + | <math>X_1 (k)=DFT_\frac{N}{2}[x_1 (n)]</math><br> | ||
| + | |||
| + | Then we have<br> | ||
| + | |||
| + | <span class="texhtml">''X''(''k'') = ''X''<sub>0</sub>(''k'') + ''X''<sub>1</sub>(''k'')</span> | ||
| + | |||
| + | <br> | ||
| + | |||
| + | <span class="texhtml">Let n = 2m (even) and n = 2m+1 (odd)</span> | ||
| + | |||
| + | <math>{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)}}</math> <math>{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)}}}</math> | ||
| + | |||
| + | <math>X(k)= X_0(k) + e^{-j{\frac{2{\pi}k}{N}}}X_1(k)</math><br> <br> | ||
| + | |||
| + | <u>Step 3:</u> Define twiddle factor and find periodic version of X(k)<br> | ||
| + | |||
| + | Notiece: each N/2 point DFT is periodic with period N/2 | ||
| + | |||
| + | So we have | ||
| + | |||
| + | <math>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})</math> | ||
| + | |||
| + | <math>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})</math> | ||
| + | |||
| + | Let's define ''twiddle factors''<br> | ||
| + | |||
| + | <u><math>W_N^k = e^{-j{\frac{2{\pi}k}{N}}}</math></u> | ||
| + | |||
| + | Then we can get the following expression | ||
| + | |||
| + | <math>X(k+{\frac{N}{2}})= X_0(k) - e^{-j{\frac{2{\pi}k}{N}}}X_1(k)</math> | ||
| + | |||
| + | <br> | ||
| + | |||
| + | So we derive the a simple expressiong for the N point DFT | ||
| + | |||
| + | <math>X(k)= X_0(k) + W_N^k X_1(K)</math> | ||
| + | |||
| + | <math>X(k+{\frac{N}{2}})= X_0(k)- W_N^k X_1(K)</math><br> | ||
| + | |||
| + | * For k = 0,1,2 ... N/2-1<br> | ||
Revision as of 17:45, 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) = DFTN[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)
x0(n) = x(2n) even subset of x(n)
x1(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) = X0(k) + X1(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)
Notiece: 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 expressiong 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
