1 Crore+ students have signed up on EduRev. Have you? 
UNIT: III, FFT(Fast frequency transform)
0 ≤K ≤ N  1
DITFFT:
Although k=0 to N1, 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 x_{e}(n) & Xeo(k) is the 2 point DFT of odd no. of x_{e}(n)
Similarly, the sequence x_{o}(n) can be divided in to even & odd numbered sequences as
Xoe(k) is the 2pt DFT of evennumbered of x_{o}(n)
Xoo(k) is the 2pt DFT of oddnumbered of x_{o}(n)
No. of Stages  No. of points N  No. of Complex Multiplications  Speed Improvement Factor:  
Direct N^{2}  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= Log_{2}N = Log2^{8} = 3.
No. of 2 i/p sets = 2^{( Log }2^{N 1 )} = 4
Total No. of Complex additions using DITFFT is NLog_{2}N
= 8 * 3 =24
Each stage no. of butterflies in the stage= 2^{mq} where q = stage no. and N=2^{m} 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 N1 = 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)] W_{8}^{2}
X(6) = f(0)  f(2)  [ f(1)  f(3)]W_{8}^{2}
Find the IDFT using DIFFFT
X(k) = { 4, 1j 2.414, 0, 1j 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 videos76 docs63 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
32 videos76 docs63 tests
