198 O Digital Signal Processing
[0.5+j0.5+j0.707]= 0.5 +j 1.21
X (7) = [h (6) -h (7)] W =
Therefore, we get
(6), X (7]
X (k) = X (0),X (1), X (2), X (3), X (4), X (5), X
+jl.21}
Or
X (k)= {2, 0.5 -jl.207, 0, 0.5-j0.207, 0, 0.5 +j0.207, 0, 0.5 Ans,
5.9 COMPUTATION OF INVERSE DFT (IDFT) USING FFT ALGORITHMS
(Very Important)
We have discussed Radix-2 DIT and DIF FFT algorithms to compute the DFT, X (k). The
same
algorithm can be used to obtain input sequence x (n) from its DFT. This means that. we ca compute
IDFT. We know that the IDFT is expressed
-kn N-1
x (n) = X (k) W n= 0, 1, ..... ...5.100)
N k=0
Just for comparison, let us reproduce the expression for DFT i..e,
N-1 + kn
X (k) = (n) W k = 0, 1, ... N- 1 ...(5.101)
n =0
This, IDFT differs from DFT by,
1
(E) Multiplication by factor
(iü) Negative sign of imaginary part of(WN
X[0]1N
WN
X(1] o orl4]
1/N
X(2]
WN
X(3] ox{6]
1/N -1
X(4]° 1N ox{1]
W'N
X[5]o
1/N
WN ox[3]
X6]
1N
3 2
WN
1
Averaging Stage 1 Stage 2 Stage 3
by 1/N
Time domain
Frequency domain, terms, shuffled
DFT terms, in sequence x(n)
FIGURE 5.21 Computation of IDFT using FFT.
Eficient Computation of DFT: Fast Fourier Transform Algorithms O 199|
Canuse the samne algorithm to compute IDFT. But, we have to change the sign of
Thus,we
twiddlefactor andfor DIF FFT algorithm, we have to multiply input sequence X (k) by 1
The
N
flow graph has
been shown in figure 5.21.
otal
5.6 Using FFT and IDFT, determine the output of system if input xn) and
h(n) are given as under:
EXAMPLE
response
x(n) = {2, 2, 4}
impulse
h(n) = {1, 1}
into smaller
: Tf the given sequences are very long, then we have to divide such
sequences
In this case, it is not essential to divide the sequences.
Solution
segments.
Given that x (n)={2, 2, 4}
and h (n) = {1, 1)
Here,
L=Number of samples in x(n) =3
M= Number of samples in h (n) = 2
Therefore, L+ M-1= 3 +2-1=4
to 4.
This means that we have to make length of x (n) and h (n) equal
Therefore, x (n)= {2, 2, 4, 0}
and h (n)= {1, 1, 0, 0}
can also use DIF FFT algorithm.
First, let us obtain DFT ofx (n) using DIT FFT algorithms. We
The calculations have been shown in figure 5.22.
X[O]=2
1
-oX0]
X(2]=4 X2]
-1
W,=1 X[1]
X[1]=2 S
w)=j -X[3]
S 1
FIGURE 5.22
Here =6
So =x (0) + × (2) = 2 + 4
2-4 =-2
8 = x (0) - x (2) =
=2+0 =2
8, = [x (1) + x (3)] W
Są = [x (1) – x (3) ] W;= (2-0) (-) =-j2
The final outupt will be
=8
X (0) = &o + S, =6+ 2
X (1) = s, + 8, =-2-j2
X (2) = 8o-8, = 6-2 = 4
X (3) = s, -8 =-2 +j2
|200 O Digital Signal Processing0
Therefore, we have
X(k) = (8, -2-j2, 4,-2 +j2}
Now, let us obtain DFT of h (n) using DIT FFT as shown in figure 5.23.
Soi
h[O]=1
h[2]=0
-1
h[1]=1 H|2]
W, =1
S
h[3]=0 H[3]
w;= -1
FIGURE 5.23
Sp = h (0) + h (2)=1+0=1
S = h (0) – h (2) =1-0 =1
S, = [h (1) + h (3)] w =1+0 = 1
$g = (h (1) - h (3) ] W= (1-0) –j=-j
The final output will be
H (0)= So + S, = 1+1=2
H(1) = s + s, = 1-j
H (2) = So -S, = 1-l =0
H (3) = S - S =1+j
Therefore, we have
H ()= {2, 1-j, 0, 1 +)
Now, we shall multiply H (k) and X (k)
Let Y (k) = X (k). H (k)
Therefore, Y (k) = {8, - 2-j2, 4, -2 +j2). (2, 1-j, 0, 1+j}
Or Y (k) = {16, – 4, 0, – 4}
Now, let us perform IDFT to obtain sequence y(n). For this, we have to multiply each input Dy
1 1
Mthat means 4 and we have to change the sign ofimaginary part of twiddle factor. This computatou
has been shown in figure 5.24.
1 1
We have S0=Y(0) + Y(2)=(16)+ =4 (0) =4
Y(0) – Y(2)=(16) - (0) =4
1
(-4) =-2
,-rora]--o-o]--0
Eficient Computation of DFT: Fast Fourier
Transform Algorithms 201|
o y(0)
-1 oy(1)
Y1) S2
-oy(2)
Y3) -1 +j oy(3)
FIGURE 5.24
The final output will be
y (0) = so + S, = 4-2 = 2
r Y ()= S1+ S = 4 +0=4
y (2) = S0-S = 4 + 2 = 6
y (3) = s - S = 4-0= 4
Therefore, we have
y (n) = {2, 4, 6, 4) Ans.
5.10 APPLICATIONS OF FFT ALGORITHMS
The FFT algorithms described in previous sections find application ina variety of areas, including
linear filtering, correlation, and spectrum analysis. Basically, the FFT algorithm is used as an efficient
means to compute the DFT and the IDFT.
In this articls, let us consider the use of the FFT algorithm in linear filtering and in the
Computation of the cross-correlation of two sequences. In addition we illustrate how to enhance the
ethciency of the FFT algorithm by forming complex-valued sequences from real-valued sequences
prior to the computation of the DFT.