FFT (Fast Frequency Transform) | Digital Signal Processing - Electronics and Communication Engineering (ECE) PDF Download

UNIT:  III, FFT(Fast frequency transform)

   0 ≤K ≤ N - 1

• Direct evaluation of X(k) requires N 2 complex multiplications and N(N-1) complex additions.
• 4 N² real multiplications 
• { 4(N-1) + 2} N = N(4N-2) real additions
• The direct evaluation of DFT is basically inefficient because it does not use the symmetry
•  & periodicity properties 

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 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 2-pt DFT of even-numbered of x_o(n)

Xoo(k) is the 2-pt DFT of odd-numbered of x_o(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= Log₂N = Log2⁸ = 3.

No. of 2 i/p sets = 2^{( Log} 2^{N  -1 )} = 4

Total No. of Complex additions using DITFFT is  NLog₂N

= 8 * 3 =24

Each stage no. of butterflies in the stage= 2^m-q 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 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)] W₈²

X(6) = f(0) - f(2) - [ f(1) - f(3)]W₈²

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}