ECT303 DIGITAL SIGNAL
PROCESSING
MODULE 2-PART –I
(DIT-FFT)
Ms. Neethu Radha Gopan, Asst. Professor, Dept. of ECE, RSET
Syllabus
2
Part 1
&2
Part 3
Total Operation Count in DFT
3
𝑁−1 𝑁−1
2π𝑘
−𝑗 𝑁 𝑛
𝐃𝐅𝐓: 𝑋 𝑘 = 𝑥(𝑛) 𝑒 = 𝑥(𝑛) 𝑊𝑁 𝑘𝑛
𝑛=0 𝑛=0
➢ Each inner product requires N complex multiplications and there are N such
DFT samples. Hence we totally require N2 complex multiplications.
➢ Each inner product requires N − 1 complex additions and there are N such DFT
samples. Hence we require N(N-1) complex additions.
➢ For large N, the straightforward method is slow and impractical even for a
moderately long sequence.
Fast Fourier Transform (FFT)
4
➢ Highly efficient procedure for computing the DFT of a finite series.
➢ Less number of computations than normal DFT.
➢ 2 algorithms: DIT (Decimation in Time) FFT & DIF (Decimation in frequency)
FFT.
The Decimation-in-Time (DIT) FFT algorithm
5
➢ From x[n] form two sequences as follows:
𝑁
xe[n]= x[2n] and xo[n]=x[2n+1] , 0≤𝑛≤ −1
2
where xe[n] are the even-indexed samples, while xo[n] are the odd-indexed samples.
➢ Consider the original DFT equation:
𝑁−1 𝑁−1
2π𝑘
−𝑗 𝑁 𝑛
𝑋 𝑘 = 𝑥(𝑛) 𝑒 = 𝑥(𝑛) 𝑊𝑁 𝑘𝑛
𝑛=0 𝑛=0
𝑁 𝑁
−1 −1
2 2
X(k) = 𝑥(2𝑛) 𝑊𝑁 𝑘(2𝑛) + 𝑥(2𝑛 + 1) 𝑊𝑁 𝑘(2𝑛+1)
𝑛=0 𝑛=0
𝑁 𝑁
2 −1 2 −1
X(k) = 𝑥(2𝑛) 𝑊𝑁 𝑘(2𝑛) + 𝑊𝑁 𝑘 𝑥(2𝑛 + 1) 𝑊𝑁 𝑘(2𝑛)
𝑛=0 𝑛=0
Note : N point DFT is
𝑁 𝑁 𝑁−1
−1 −1
2 2
2𝑘𝑛 𝑘 2𝑘𝑛 𝑋 𝑘 = 𝑥(𝑛) 𝑊𝑁 𝑘𝑛
X k = 𝑥𝑒 𝑛 𝑊𝑁 + 𝑊𝑁 𝑥𝑜 𝑛 𝑊𝑁
𝑛=0
𝑛=0 𝑛=0
𝑗2𝜋 𝑗2𝜋
− .2 −𝑁/2
We know that 𝑊𝑁2 = 𝑒 𝑁 =𝑒 = 𝑊𝑁/2
𝑁 𝑁
2 −1 2 −1
Therefore X k = 𝑥𝑒 𝑛 𝑊𝑁/2 𝑘𝑛 + 𝑊𝑁 𝑘 𝑥𝑜 𝑛 𝑊𝑁/2 𝑘𝑛
𝑛=0 𝑛=0
N/2 point DFT of even N/2 point DFT of odd
indexed sequence indexed sequence
6
7
𝑋 𝑘 = 𝑋𝑒 𝑘 + 𝑊𝑁 𝑘 𝑋𝑜 (𝑘)
𝑋𝑒 𝑘 and 𝑋𝑜 𝑘 are N/2 point DFT’s (periodic wrt to N/2 ) where k varies from 0
to N/2 –1 but required X(k) is a N point DFT.
➢ So for k ≥ N/2, we have 𝑊𝑁 𝑘+𝑁/2 = −𝑊𝑁 𝑘
𝑋 𝑘 + 𝑁/2 = 𝑋𝑒 𝑘 + 𝑁/2 + 𝑊𝑁 𝑘+𝑁/2 𝑋𝑜 𝑘 + 𝑁/2 = 𝑋𝑒 𝑘 − 𝑊𝑁 𝑘 𝑋𝑜 (𝑘)
➢ Therefore we have
𝑋 𝑘 = 𝑋𝑒 𝑘 + 𝑊𝑁 𝑘 𝑋𝑜 𝑘 −−−−−−−−−−−−− −(1)
𝑘 𝑁
𝑋 𝑘 + 𝑁/2 = 𝑋𝑒 𝑘 − 𝑊𝑁 𝑋𝑜 𝑘 𝑓𝑜𝑟 0 ≤ 𝑘 ≤ − 1 −−−−−− −(2)
2
8
Eg: Take N=8. Substitute values of k from 0 to 3 (0 to N/2 -1) in equation (1)
& (2) 0
X (0) = X e (0) + W8 X o (0)
X (1) = X e (1) + W81 X o (1)
X (2) = X e (2) + W82 X o (2)
X (3) = X e (3) + W83 X o (3)
X (4) = X e (0) − W80 X o (0)
X (5) = X e (1) − W81 X o (1)
X (6) = X e (2) − W82 X o (2)
X (7) = X e (7) − W83 X o (3)
9
10
➢ The same idea can be applied for calculating the N/2 point DFT of the
sequences xe[n]and xo[n]. Computational savings can be obtained by
dividing xe[n]and xo[n] into their odd- and even-indexed halves.
𝑋𝑒 𝑘 = 𝑋𝑒𝑒 𝑘 + 𝑊𝑁2𝑘 𝑋𝑒𝑜 𝑘
𝑁
𝑋𝑒 𝑘 + 𝑁/4 = 𝑋𝑒𝑒 𝑘 − 𝑊𝑁2𝑘 𝑋𝑒𝑜 𝑘 𝑓𝑜𝑟 0 ≤ 𝑘 ≤ − 1
4
𝑋𝑜 𝑘 = 𝑋𝑜𝑒 𝑘 + 𝑊𝑁2𝑘 𝑋𝑜𝑜 𝑘
𝑁
𝑋𝑜 𝑘 + 𝑁/4 = 𝑋𝑜𝑒 𝑘 − 𝑊𝑁2𝑘 𝑋𝑜𝑜 𝑘 𝑓𝑜𝑟 0 ≤ 𝑘 ≤ − 1
4
11
➢ We continue the decomposition of stages until we are left with only 2
point DFT.
➢ Each decomposition is called a stage and the number of stages is given by
M = log 2 N
Butterfly diagram of 2 point DFT
12
Concept of DIT-FFT
13
Q. Find DFT of sequence x[n]={0,1,2,3} using DIT-FFT algorithm.
14
x(0) = 0 2 6
-2 -2+2j N=4
x(2) = 2
-1 j2𝜋
𝑊40 =1 −
4 -2 𝑊𝑁 = e N
j2𝜋
x(1) = 1 𝑊4 = e 4 .0 = 1
0 −
𝑊40 = 1 -1
j2𝜋.1
1 − 4
𝑊4 = e = −j
x(3) = 3
-1 -2 -1 -2-2j
𝑊40 =1 𝑊41 = −𝑗
X(k)={6, -2+2j, -2, -2 –2j}
Number of Complex Computations
15
➢ Total no. of stages in the calculation of an N-point DFT using FFT= 𝐥𝐨𝐠 𝟐 𝐍
𝐍
➢ No. of complex multiplications in each stage ∶
𝟐
➢ No. of complex additions in each stage ∶N
𝐍
➢ Total no. of complex multiplications in the entire DIT FFT : 𝐥𝐨𝐠 𝟐 𝐍
𝟐
➢ Total no. of complex additions in the entire DIT FFT :𝐍 𝐥𝐨𝐠 𝟐 𝐍
Q. Find DFT of a sequence x(n)={0,1,2,3,4,5,6,7} using DIT-FFT algorithm.
Also compute the number of complex additions & multiplications required
for conventional DFT & DIT FFT.
16
Soln: N=8
Only find the first 4 twiddle factor Note:
j2𝜋 Number of stages= log 2 𝑁 = log 2 8=3
−
𝑊𝑁 = e N
j2𝜋
𝑊8 = e 8 .0 = 1
0 −
Third stage will have all the 4 twiddle factors.
1
j2𝜋.1
− 8 1 𝑗
𝑊8 = e = −
2 2 Second stage will have even twiddle factors
2 −
j2𝜋.2 from the third stage (𝑊8 0 & 𝑊8 2 )
𝑊8 = e 8 = −𝑗
3 −
j2𝜋.3 1 𝑗
𝑊8 = e 8 = − − First stage will have even twiddle factors from
2 2 the second (𝑊8 0 ).
4 12 28
0
-4 -4+4j - 4+9.656j
4
𝑊80 = 1 -1
8 -4 - 4+4j
2
𝑊80 = 1 -1
-4 -4-4j - 4+1.656j
6
𝑊80 = 1 -1 𝑊82 = −𝑗 -1
1 6 16 -4
𝑊80 = 1 -1
5 -4 -4+4j - 4-1.656j
-1 1 𝑗 -1
𝑊80 =1 𝑊81 = −
2 2
10 -4 - 4- 4j
3 -1
𝑊80 = 1 𝑊82 = −𝑗 -1
7 -4
𝑊80 = 1 -1 𝑊82 = −𝑗 -1 -4-4j 𝑊 3 = − 1 − 𝑗 -1 - 4- 9.656j
8
2 2
17
18
X(k) = {28, - 4+9.656j, - 4+4j, - 4+1.656j, -4, - 4-1.656j, - 4- 4j, - 4-9.656j }
No. of complex additions:
DFT : N(N-1) = 8(7) =56
DIT FFT : N log 2 N = 8 log 2 8 = 24
No. of complex multiplications:
DFT : 𝑁 2 = 82 = 64
N
DIT FFT : log 2 N = 4 log 2 8 = 12
2
IDFT using FFT Algorithms
19
➢ FFT algorithms can be used to compute inverse DFT without any change in the
algorithm
➢ By definition of DFT and IDFT we have
2k − 2k
N −1 −j n N 1 1 j n
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 (or phase factor
𝑊𝑁 ) are conjugate and 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]={0, 2+j2 , -j4 , 2-j2 , 0 , 2+j2 , 4j, 2-j2 } using DIT-FFT algorithm.
20
Soln:
❑ Draw the same structure as that of 8 point DIT FFT.
❑ Interchange X(k) and x(n) N=8
j2𝜋
❑ Replace twiddle factors by their conjugate pairs. −
𝑊𝑁 = e N
❑ Multiply final result by 1/N= 1/8 j2𝜋
𝑊8 = e 8 .0 = 1
0 −
−1
j2𝜋.1 1 𝑗
𝑊8 = e 8 = +
2 2
j2𝜋.2
−2
𝑊8 = e 8 = 𝑗
−3
j2𝜋.3 1 𝑗
𝑊8 = e 8 = − +
2 2
0 0 8
0
0 8 8
0
𝑊80 = 1 -1
0 0 -8
-4j
𝑊80 = 1 -1
4j -8j -8 -8
𝑊80 = 1 -1 𝑊8−2 = 𝑗 -1
8 -8
2+2j 4+4j 𝑊80 = 1 -1
0 8
2+2j 0 1 𝑗
-1 𝑊8−1 = + -1
𝑊80 =1 2 2 8
8j
2-2j 4-4j 𝑊 0 = 1 -1
8
𝑊8−2 = 𝑗 -1
-8
2-2j 0 1 𝑗
𝑊80 = 1 -1 0 𝑊8−2 =𝑗 -1 𝑊8−3 =− + -1
2 2
21
22
1
𝑥 𝑛 = 8, 8, −8, −8, −8, 8, 8, −8 = {1, 1, −1, −1, −1, 1, 1, −1}
𝑁
References
23
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.
24 END of PART -I
THANK YOU!
