UNIT: III, FFT(Fast frequency transform)
0 ≤K ≤ N - 1
DITFFT:
Although k=0 to N-1, each of the sums are computed only for k=0 to N/2 -1, since Xe(k) & Xo(k) are periodic in k with period N/2
For K≥ N/2
X(k) for K≥N/2
N = 8
X(0) & X(4) having same i/ps with opposite signs
(0 to 1)
For N=8
Where Xee(k) is the 2 point DFT of even no. of xe(n) & Xeo(k) is the 2 point DFT of odd no. of xe(n)
Similarly, the sequence xo(n) can be divided in to even & odd numbered sequences as
Xoe(k) is the 2-pt DFT of even-numbered of xo(n)
Xoo(k) is the 2-pt DFT of odd-numbered of xo(n)
No. of Stages | No. of points N | No. of Complex Multiplications | Speed Improvement Factor: | |
Direct N2 | FFT | |||
2 | 4 | 16 | 4 | 4 |
3 | 8 | 64 | 12 | 5.33 |
4 | 16 | 256 | 32 | 8 |
5 | 32 | 1024 | 80 | 12.8 |
6 | 64 | 4096 | 192 | 21.33 |
For N=8
No of stages given by= Log2N = Log28 = 3.
No. of 2 i/p sets = 2( Log 2N -1 ) = 4
Total No. of Complex additions using DITFFT is NLog2N
= 8 * 3 =24
Each stage no. of butterflies in the stage= 2m-q where q = stage no. and N=2m Each butterfly operates on one pair of samples and involves two complex additions and one complex multiplication. No. of butterflies in each stage N/2
DITFFT: ( different representation) (u can follow any one) ( both representations are
correct
k= 0 to N/2 -1 = 0 to 3
k = N/2 to N-1 = 4 to 7
2 pt DFT
Xee(0) = x(0)+x(4)
Xee(1) = x(0)-x(4)
Other way of representation
DIFFFT:
put n’ = n+N/2
Let f(n) = x(n) + x(n+N/2)
N=8
f(0) = x(0) + x(4)
f(1) = x(1) + x(5)
f(2) = x(2) + x(6)
f(3) = x(3) + x(7)
X(4k) = f(0) + f(2) + [ f(1) + f(3) ]
X(4k+2) = f(0) – f(2) + { [ f(1) – f(3) ]
X(0) = f(0) + f(2) + f(1) + f(3)
X(4) = f(0) + f(2) – [ f(1) + f(3) ]
X(2) = f(0) - f(2) + [ f(1) - f(3)] W82
X(6) = f(0) - f(2) - [ f(1) - f(3)]W82
Find the IDFT using DIFFFT
X(k) = { 4, 1-j 2.414, 0, 1-j 0.414, 0, 1+j 0.414, 0, 1+j 2.414 }
Out put 8x*(n) is in bit reversal order x(n) = { 1,1,1,1,0,0,0,0}
32 videos|76 docs|63 tests
|
1. What is FFT and how does it work? |
2. What are the main applications of FFT? |
3. How does FFT improve computational efficiency? |
4. Can FFT be used for non-periodic signals? |
5. Are there any limitations or drawbacks of using FFT? |
|
Explore Courses for Electronics and Communication Engineering (ECE) exam
|