FAST Fourier transform series

Chapter5. Discrete Fourier Transform (DFT) and Fast Fourier Transforn(FFT) 5. 38
In equation (5.35), the expression inside the bracket is similar to that of DFT computation of a
withfollowing differences.
sequence,
The summation index is k instead ofn.
). The input sequence is X(k) instead of x(n),
1 The phase factors are conjugate of the phase factor used for DFT.
Hence,in order to compute inverse DFT of X(k), the FFT algorithm can be used by taking the conjugate of
phasc factors. Alsofrom equation (5.35) it is observed that the output of FFT computation should be divided
N(n).
t Ntoget
The following procedure can be followcd to compute inverse DFT using FFT algorithm.
1. Take N-point frequency domain sequence X(k) as input sequence.
2. Compute FFT by using conjugate of phase factors.
3. Divide the output sequence obtained in FFT computation by N, to get the sequence x(n).
Thus a single FFT algorithm can be used for evaluation of both DFT and inverse DFT.
Exomple 5.5
An 6-point sequence is given by x(n) = (2, 1, 2, 1, 1, 2, 1, 2). Compute &-point DFT of x(n) by
l adiy-2DpIT-FFT and b)radix-2 DIF-FFT. Also sketch the magnitude and phase spectrum.
Solution

o B-point DFT by Radix-2 DIT-FFT
The given sequence is first arranged in the bit reversed order.
The sequence x(n) The sequence x(n) in
in normal order bit reversed order x(0) =2 2+1= 3


x(0) = 2 x(0) = 2 x(4) =1 2-1 = 1

x(1)=1 x(4) = 1 x(2) = 2 2+1= 3
x(2) = 2 x(2) = 2
x(6) = 1 2-1= 1
x(3) = 1 x(6) = 1
x(1) = 1 1+2 = 3
x(4) = 1 x(1) =1
x(5) = 2 x(5) = 2 x(5) = 2 So1-2 =-1
1
x(6) = 1 x(3) =1 x(3) = 1 1+2- 3

x(7) = 2 x(7) =2
x(7) = 2 1-2 = -1
computation with
e Bpoint DFTby radix-2 FFT involve 3 stages of Fig I : Butterfly diagram for
in the bit
k-uuterloder
teversed
the
y forns the input to the first stage. For other stages of computation
Computations in each stage. The sequence rearranged
first stage of radis-2 DIT FFT:
oulput of previous stage will be the input for current stage.
First stage computation
sequence of first stage computation=(2, 1, 2, 1, 1,2, I, 21 The phase factor involved in first
e input stage of computation is w
The bulterfly computations offirst stage are shown in fig I. Since, w =1, itis not considered
for computation.


The output Isequence of first stage of computation = (3, I, 3, 1, 3, -1, 3, -1 )

,5.39

Second stage computation
Digital Signal Proces ing
The input sequenceto second stage computation = (3, 1, 3, 1, 3, -1, 3, -1)
w!.
The phase fators involved insecond stage computation are w and
3
The buterfly computations of second stage are shown in fig 2.
1 p3+3=8
36 1+1(-}=1
w -e
1

w e
36 1
1-1(4=1+
-1
3+3-9
= -j 3e
3-3=0
-16

The output tage
sequence of second
of computation =(6, 1-j, 0, 1+j, 6, -1+j, 0, -1-} Fig 2: Butterly diagram for
second stage of radix-2 DIT FFT
Third stoge computation
The input sequence to third stage computation = {6, 1-j,0, 1+j, 6, -1+j, 0, -1-j)
The phase factors involved in third stage computation are W, W, W and W.
The butterfly computations of third stage are shown in fig 3.
-j2r x
w =e 8 = e =1

w= e * j x 4 =


-co)-)-
8 =e 4 = 1



6+6=12 =X(0)

.414- X()


0+0×(-) =0= 2)
I+2.414- N3)
-
6-6 -0- X4)

(1-)


-1
0-0()-0-X6)
(1" )-<1
Fig 3 : Butterfly
diagram for third stage of radix-2 DIT
FFT of X(K).

, Transform(DFT) and Fast Fourier
Diserer Fourier Transform (FET) 5. 40
5- sequenceof third) (12, 1+ j0.414, 0,
ger
output
The
stageofcomputation 1j2.414, 0, 1 2414, 0, 1-j0414)
sequence ofthird stage of computation isthe B-point DFT of
the given sequencein normal
output.
The

x(n)})= X(K) -{12, 1+ j0.414, 0, 1+j2.414, 0, 1-j2.414, 0, 1- 0.4141|


y Radix-2 DIF-FFT
DFTby
DFTIbyradix-2 FFT We require 3-stages of computation with 4-butterfly
8point
For sequenceis
the to input first stage. For other stages computation
of computations,the output in each
of previous stage
Thegivenforcurrent stage.
input
Bstogecomputation

sequencefor first stage of computation = (2, 1,2, 1, 1, 2, 1, 2)
Theinput involved in first stage computation are W, w, w and
phaseifactors w:.
The
buttertfly computations of first stage are shown in fig 4.
The
-j2* x
W =e 8=1
1
co-in
-co in)
1


2+1=3
X(0) =2
X(1) = 1a 1+2=3
1

x(2) =2 - 2+1=3


x(3) = 1 1+2=3


x(4) =1 2-1=1


X(5) =2

x(6) =1 o (2-1)(-) =-j
1
K() =2

'g 4: Butterfly diagram for first stage ofradix-2 DIFFFI.
The
output Sequence of first
eof computation -3, 3, 3, 3, I, - t i ' E