ECT303 DIGITAL SIGNAL
PROCESSING
MODULE 2-PART II
(DIF-FFT)
Ms. Neethu Radha Gopan, Asst. Prof., Department of ECE, RSET.
The Decimation-in-Frequency (DIF) FFT algorithm
2
➢ Decimation in frequency is an alternate way of developing the FFT algorithm.
➢ It is different from decimation in time in its development, although it leads to
a very similar structure. 𝑁−1 𝑁−1
2π𝑘
−𝑗 𝑁 𝑛
➢ Consider the original DFT equation : 𝑋 𝑘 = 𝑥(𝑛) 𝑒 = 𝑥(𝑛) 𝑊𝑁 𝑘𝑛
𝑛=0 𝑛=0
➢ Separate the first half and the second half of time samples:
𝑁/2−1 𝑁−1
𝑋 𝑘 = 𝑥(𝑛) 𝑊𝑁 𝑘𝑛 + 𝑥(𝑛) 𝑊𝑁 𝑘𝑛
𝑛=0 𝑛=𝑁/2
𝑁/2−1 𝑁/2−1
𝑁
𝑘𝑛 𝑘(𝑛+ 2 )
= 𝑥(𝑛) 𝑊𝑁 + 𝑥(𝑛 + 𝑁/2) 𝑊𝑁
𝑛=0 𝑛=0
𝑁/2−1 𝑁/2−1
X(k) = 𝑥(𝑛) 𝑊𝑁 𝑘𝑛 + 𝑊𝑁 𝑘𝑁/2 𝑥(𝑛 + 𝑁/2) 𝑊𝑁 𝑘𝑛
𝑛=0 𝑛=0
𝑗2𝜋 𝑘𝑁
We know that 𝑊𝑁 𝑘𝑁/2 = 𝑒 𝑁.2
−
=𝑒−𝑗𝜋𝑘
= 𝑐𝑜𝑠𝜋𝑘 − 𝑗𝑠𝑖𝑛𝜋𝑘 = (−1)𝑘
𝑁/2−1 𝑁/2−1
∴ X k = 𝑥(𝑛) 𝑊𝑁 𝑘𝑛 + (−1)𝑘 𝑥(𝑛 + 𝑁/2) 𝑊𝑁 𝑘𝑛
𝑛=0 𝑛=0
𝑁/2−1
∴ X k = 𝑥 𝑛 + −1 𝑘
𝑥(𝑛 + 𝑁/2) . 𝑊𝑁 𝑘𝑛 −− −(1)
𝑛=0
➢ Now we divide X(k) to even & odd sequences
➢ When k is even, we get X(0), X(2), X(4)……and −1 𝑘 =1.
𝑁/2−1
∴ Equation 1 becomes X 2𝑘 = 𝑥 𝑛 + 𝑥(𝑛 + 𝑁/2) . 𝑊𝑁 2𝑘𝑛
𝑛=0
3
𝑁/2−1
𝑁/2−1
X 2𝑘 = 𝑥 𝑛 + 𝑥(𝑛 + 𝑁/2) . 𝑊𝑁/2 𝑘𝑛 = 𝑔(𝑛) . 𝑊𝑁/2 𝑘𝑛 −− −(2)
𝑛=0
𝑛=0
➢ In equation (1), when k is odd,
➢ We get X(1), X(3), X(5)……and −1 𝑘 = -1.
𝑁/2−1
∴ Equation 1 becomes X 2𝑘 + 1 = 𝑥 𝑛 − 𝑥(𝑛 + 𝑁/2) . 𝑊𝑁 (2𝑘+1)𝑛
𝑁/2−1 𝑛=0
X 2𝑘 + 1 = 𝑥 𝑛 − 𝑥(𝑛 + 𝑁/2) . 𝑊𝑁 𝑛 𝑊𝑁 2𝑘𝑛
𝑛=0
𝑁
𝑁/2−1 2 −1
X 2𝑘 + 1 = 𝑥 𝑛 − 𝑥(𝑛 + 𝑁/2) . 𝑊𝑁 𝑛 𝑊𝑁/2 𝑘𝑛 = ℎ 𝑛 𝑊𝑁 𝑘𝑛 −−− −(3)
𝑛=0 2
𝑛=0
4
N N
➢ Equation 2 gives the pointDFT even DFT samples of the point
2 2
sequence 𝑔 n which is obtained by adding first half and second half of
the input sequence.
N N
➢ Equation 3 gives the point DFT odd DFT samples of the point sequence
2 2
h n which is obtained by subtracting first half and second half of the input sequence
and then multiplying the result with 𝑊𝑁 𝑛 .
Eg: Take N = 8, we find g n and h(n) which are inputs to compute X 2k and X(2k + 1)
𝑔 𝑛 = 𝑥 𝑛 + 𝑥(𝑛 + 𝑁/2)
𝑔 0 = 𝑥 0 + 𝑥(4) 𝑔 2 = 𝑥 2 + 𝑥(6)
𝑔 1 = 𝑥 1 + 𝑥(5) 𝑔 3 = 𝑥 3 + 𝑥(7)
5
h 𝑛 = 𝑥 𝑛 − 𝑥(𝑛 + 𝑁/2) . 𝑊𝑁 𝑛
h 0 = 𝑥 0 − 𝑥(4) . 𝑊8 0
h 1 = 𝑥 1 − 𝑥(5) . 𝑊81
h 2 = 𝑥 2 − 𝑥(6) . 𝑊8 2
h 3 = 𝑥 3 − 𝑥(7) . 𝑊8 3
➢ This is the first stage of decomposition.
6
7
8
➢ We continue the decomposition of odd and even output points until we are
left with only 2 point DFT.
Q. Find DFT of sequence x[n]={1,0,0,1} using DIF-FFT algorithm.
Soln: N=4
9
x(0) = 1 1 1 2 2 X(0)
1 0 0 X(2)
x(1) = 0 1
-1 𝑊40 = 1
1 1 1+j 1+j X(1)
x(2) = 0
-1 𝑊40 = 1
-1 j
x(3) = 1 1-j X(3)
-1 -1 1-j
𝑊41 = −𝑗 𝑊40 = 1
j2𝜋 j2𝜋 j2𝜋.1
𝑊𝑁 = e −
N , 0
𝑊4 = e −
4 .0 = 1, 1
𝑊4 = e − 4 = −j X(k)={2, 1+j, 0, 1 –j}
Q. Find DFT of a sequence x(n)={1,3,2,2,1,3,2,2}using DIF FFT algorithm.
10
Soln:
Note:
N=8 Number of stages= log 2 𝑁 = log 2 8=3
j2𝜋
− N
𝑊𝑁 = e First stage will have all the 4 twiddle factors.
j2𝜋
𝑊8 = e 8 .0 = 1
0 −
1 −
j2𝜋.1 1 𝑗 Second stage will have even twiddle factors from
𝑊8 = e 8 = −
2 2 the first stage (𝑊8 0 & 𝑊8 2 )
j2𝜋.2
2 −
𝑊8 = e 8 = −𝑗 Third stage will have even twiddle factors from
j2𝜋.3
− 8 1 𝑗
𝑊8 3 = e = − − the second (𝑊8 0 ).
2 2
2 2 6 6 16 X(0)
1
6 6 10 10 -4 X(4)
3
-1 𝑊80
4 4 -2 -2 -2-2j X(2)
2
-1 𝑊80
2 4 4 2 - 2j -2+2j X(6)
-1 𝑊82 -1 𝑊80
0 0 0 0 X(1)
1 0
-1 𝑊80
0 0 0 X(5)
3 0
-1 0 𝑊81 -1 𝑊80
0 0 X(3)
2 0 0 -1 0
-1 𝑊82 𝑊80
0 0 X(7)
2
0 𝑊3 0 -1 0 -1 𝑊80
-1 8 𝑊82
11
12
X(k)={16, 0, -2-2j, 0, -4, 0, -2+2j, 0}
Number of Complex Computations
13
𝑁
➢ log 2 𝑁 complex multiplications and 𝑁 log 2 𝑁 complex additions.
2
Q. Find the number of complex additions & complex multiplications in 64 point
and 1024 point DFT using (i) conventional DFT & (ii) radix 2 FFT.
Soln:
For N=64 (1024 – do as Home Work)
Complex Additions: DFT =N(N-1)=64× (63)=4032
FFT=𝑁 log 2 𝑁=64 log 2 64 =64 log 2 26 =64×6 log 2 2= 384
Complex Multiplications: DFT =𝑁 2 = 642 =4096
𝑁
FFT= log 2 𝑁 = 64/2 log 2 64 =32 log 2 26 =32×6 log 2 2= 192
2
Comparing DIT and DIF structures:
14
➢ DIT- bit reversal for input and output is of normal order; DIF – bit reversal for
output and input is in normal order.
➢ DIT - Complex multiplication takes place before add-subtract; DIF - Complex
multiplication takes place after subtraction.
DIT FFT structure DIF FFT structure
IDFT using DIF FFT algorithms
15
➢ FFT algorithms can be used to compute an inverse DFT without any change in the
algorithm.
➢ By definition of DFT and IDFT, we have
2kn 2kn
N −1 −j 1 N −1 j
X (k ) = x ( n )e N x ( n) =
N k =0
X ( k )e N
n =0
➢ If we observe the two equations the difference is that the twiddle factors are conjugates.
➢ The IDFT equation has multiplier 1/N.
➢ Therefore using the existing flow graph we can compute the IDFT by interchanging I/P
and O/P, replacing the twiddle factors by its conjugate pairs and finally multiplying by
1/N.
Q. Find 8-point IDFT of a sequence X[k]={4, 1-j2.414, 0, 1-j0.414, 0} using DIF
FFT algorithm.
16
Soln:
𝑋 𝑘 = 𝑋 ∗ (𝑁 − 𝑘)
N=8 𝑋 5 = 𝑋 ∗ 8 − 5 = 𝑋 ∗ 3 = 1 + 𝑗0.414
j2𝜋
− N
𝑊𝑁 = e
j2𝜋 𝑋 6 = 𝑋∗ 2 = 0
𝑊8 = e 8 .0 = 1
0 −
j2𝜋.1 1 𝑗
−1
𝑊8 = e 8 = + 𝑋 7 = 𝑋 ∗ 1 = 1 + 𝑗2.414
2 2
j2𝜋.2
−2
𝑊8 = e 8 = 𝑗 X(k)={4, 1-j2.414, 0, 1-j0.414, 0, 1+j0.414, 0, 1+j2.414}
−3
j2𝜋.3 1 𝑗
𝑊8 = e 8 = − +
2 2
4 4 4 4 4 8 1/8 1
1-2.414j 2-2j 2-2j 4 4 0 1/8 0
-1 𝑊80
0 0 0 4 4 8 1/8 1
-1 𝑊80
2+2j 4 0 1/8
1-0.414j 2+2j -4j 0
-1 𝑊8−2 -1 𝑊80
1/8
0 4 4 8 1
4 4
-1 𝑊80 1/8
1+0.414j 4 0
-2.828j 𝑊 −1 2-2j 4 0 𝑊0
-1 -1 8
8
0 4 1/8
0 0 8
-1 4 1
-1 𝑊8−2 𝑊80
1+2.414j -2.828j 2+2j 1/8
-4j 0
-1 𝑊8−3 -1 𝑊8−2 4 -1 𝑊80 0
17
18
Input Output (bit
reversed)
X(0) 000 000 x(0)
X(1) 001 100 x(4)
X(2) 010 010 x(2)
On reordering the output, we get x(n)= {1,1,1,1,0,0,0,0}
X(3) 011 110 x(6)
X(4) 100 001 x(1)
X(5) 101 101 x(5)
X(6) 110 011 x(3)
X(7) 111 111 x(7)
References
19
1. Proakis J. G. and Manolakis D. G., Digital Signal Processing, 4/e, Pearson
Education, 2007.
2. P. Ramesh Babu, Digital Signal Processing, Scitech Publications (India) Pvt
Ltd.
20 END of PART -II
THANK YOU!
