www.EasyEngineering.

net

Fast Fourier Transform

7
ww
w .Ea
7.1 INTRODUCTION
syE
The N-point DFT of a sequence x(n) converts the time domain N-point sequence x(n) to a

ngi
frequency domain N-point sequence X(k). The direct computation of an N-point DFT requires
N ´ N complex multiplications and N(N – 1) complex additions. Many methods were
developed for reducing the number of calculations involved. The most popular of these is the

nee
Fast Fourier Transform (FFT), a method developed by Cooley and Turkey. The FFT may be
defined as an algorithm (or a method) for computing the DFT efficiently (with reduced

rin
number of calculations). The computational efficiency is achieved by adopting a divide and
conquer approach. This approach is based on the decomposition of an N-point DFT into

g.n
successively smaller DFTs and then combining them to give the total transform. Based on
this basic approach, a family of computational algorithms were developed and they are
collectively known as FFT algorithms. Basically there are two FFT algorithms; Decimation-
in-time (DIT) FFT algorithm and Decimation-in-frequency (DIF) FFT algorithm. In this
chapter, we discuss DIT FFT and DIF FFT algorithms and the computation of DFT by these
methods.
e t
7.2 FAST FOURIER TRANSFORM
The DFT of a sequence x(n) of length N is expressed by a complex-valued sequence X(k) as
N 1
X (k ) =  x(n) e j 2Q nk/N , k = 0, 1, 2, ..., N  1
n0

Let WN be the complex valued phase factor, which is an Nth root of unity given by

WN = e j 2Q /N
479

www.EasyEngineering.net
 www.EasyEngineering.net

480 h Digital Signal Processing

Thus, X(k) becomes

N 1
X (k ) =  x (n) WNnk , k = 0, 1, 2, ..., N  1
n0

Similarly, IDFT is written as

N 1
1
x (n) =
N
 X (k) WNnk , n = 0, 1, 2, ..., N  1
k 0

From the above equations for X(k) and x(n), it is clear that for each value of k, the direct

ww
computation of X(k) involves N complex multiplications (4N real multiplications) and N – 1
complex additions (4N – 2 real additions). Therefore, to compute all N values of DFT,
N2 complex multiplications and N(N – 1) complex additions are required. In fact the DFT

w
and IDFT involve the same type of computations.

.Ea
If x(n) is a complex-valued sequence, then the N-point DFT given in equation for X(k)
can be expressed as
X(k) = XR(k) + jXI(k)

or syE
X (k ) =
N 1

 xR (n) + jxI (n) cos

 2Q nk
 j sin
2Q nk 
N 
n 0

ngi N

Equating the real and imaginary parts of the above two equations for X(k) we have

X R (k ) =
N 1



nee
2Q nk 2Q nk 
 x R (n) cos N + x I (n) sin N 
 
n0

N 1 rin

X I (k ) =    x R (n) sin
n0 
2Q nk
N
 x I (n) cos
2Q nk 
N 
g.n
The direct computation of the DFT needs 2N2 evaluations of trigonometric functions, 4N2
real multiplications and 4N(N – 1) real additions. Also this is primarily inefficient as it
cannot exploit the symmetry and periodicity properties of the phase factor WN, which are
e t
N
k+
Symmetry property WN 2 =  WNk

Periodicity property WNk + N = WNk

FFT algorithm exploits the above two symmetry properties and so is an efficient algorithm
for DFT computation.
By adopting a divide and conquer approach, a computationally efficient algorithm can
be developed. This approach depends on the decomposition of an N-point DFT into
successively smaller size DFTs. An N-point sequence, if N can be expressed as N = r1r2r3, ..., rm

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 481

where r1 = r2 = r3 = ... = rm, then N = rm, can be decimated into r-point sequences. For each
r-point sequence, r-point DFT can be computed. Hence the DFT is of size r. The number r is
called the radix of the FFT algorithm and the number m indicates the number of stages in
computation. From the results of r-point DFT, the r2-point DFTs are computed. From the
results of r2-point DFTs, the r3-point DFTs are computed and so on, until we get rm-point
DFT. If r = 2, it is called radix-2 FFT.

7.3 DECIMATION IN TIME (DIT) RADIX-2 FFT

In Decimation in time (DIT) algorithm, the time domain sequence x(n) is decimated and

ww
smaller point DFTs are computed and they are combined to get the result of N-point DFT.
In general, we can say that, in DIT algorithm the N-point DFT can be realized from
two numbers of N/2-point DFTs, the N/2-point DFT can be realized from two numbers of

w
N/4-point DFTs, and so on.
In DIT radix-2 FFT, the N-point time domain sequence is decimated into 2-point

.Ea
sequences and the 2-point DFT for each decimated sequence is computed. From the results
of 2-point DFTs, the 4-point DFTs, from the results of 4-point DFTs, the 8-point DFTs and

syE
so on are computed until we get N-point DFT.
For performing radix-2 FFT, the value of r should be such that, N = 2m. Here, the
decimation can be performed m times, where m = log2N. In direct computation of

ngi
N-point DFT, the total number of complex additions are N(N – 1) and the total number of
complex multiplications are N2. In radix-2 FFT, the total number of complex additions are
reduced to N log2N and the total number of complex multiplications are reduced to (N/2)
log2N.
nee
Let x(n) be an N-sample sequence, where N is a power of 2. Decimate or break this

rin
sequence into two sequences f1(n) and f2(n) of length N/2, one composed of the even indexed
values of x(n) and the other of odd indexed values of x(n).
N 
Given sequence x (n): x (0), x (1), x (2), ..., x   1  , ..., x ( N  1)
2  g.n
Even indexed sequence f1 (n) = x (2n): x (0), x (2), x (4), ..., x (N  2)
Odd indexed sequence f2 (n) = x (2n + 1): x (1), x (3), x (5), ..., x (N  1)
We know that the transform X(k) of the N-point sequence x(n) is given by
e t
N 1
X (k ) =  x (n) WNnk , k = 0, 1, 2, ..., N  1
n0

Breaking the sum into two parts, one for the even and one for the odd indexed values, gives
N 2 N 1
X (k ) =  x (n) WNnk +  x (n) WNnk , k = 0, 1, 2, ..., N  1
n even n odd

www.EasyEngineering.net
 www.EasyEngineering.net

482 h Digital Signal Processing

When n is replaced by 2n, the even numbered samples are selected and when n is replaced
by 2n + 1, the odd numbered samples are selected. Hence,
N N
1 1
2 2
X (k ) =  x (2n) WNk (2n) +  x (2n + 1) WNk (2n 1)
n0 n 0

Rearranging each part of X(k) into (N/2)-point transforms using

2nk nk
  j 2Q    j 2Q 
WN2nk = (WN2 ) nk = e N  =  e N/2  = WNnk/2
   

ww
and WN(2 n +1) k = WNk WNnk/2 , we can write
   

w .Ea X (k) =
N
2

1

n 0
f1 (n) WNnk/2 + WNk
N
2

1

n0
f2 (n) WNnk/2

syE
By definition of DFT, the N/2-point DFT of f1(n) and f2(n) is given by
N N

ngi
1 1
2 2
F1 (k ) =  f1 (n) WNkn/2 and F2 (k ) =  f2 (n) WNkn/2
n 0 n 0

\ X (k ) = F1 (k ) + WNk F2 (k ), nee k = 0, 1, 2, . . ., N  1

The implementation of this equation for X(k) is shown in Figure 7.1.

This first step in the decomposition breaks the N-point transform into two (N/2)-point rin
transforms and the WNk provides the N-point combining algebra.
The DFT of a sequence is periodic with period given by the number of points of DFT. g.n
Hence, F1(k) and F2(k) will be periodic with period N/2.

\  N  N
F1  k +  = F1 (k ) and F2  k +  = F2 (k )
 2   2
e t
In addition, the phase factor WN
k + N2  =  WNk .
Therefore, for k ³ N/2, X(k) is given by

 N  N
X ( k ) = F1  k    WNk F2  k  
 2   2

The implementation using the periodicity property is also shown in Figure 7.1.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 483

ww
w .Ea
Figure 7.1 Illustration of flow graph of the first stage DIT FFT algorithm for N = 8.

The total number of complex multiplications, h1, required to evaluate the N-point

syE
transform with this first decimation becomes N + N2/2 determined as follows
2 2
I1 =   +   + N = N +
N2

ngi
N N
2 2 2

nee
The first term in the sum is the number of complex multiplications for the direct calculation
of the (N/2)-point DFT of the even indexed sequence; the second term is the number of
complex multiplications for the direct calculation of the (N/2)-point DFT of the odd indexed

rin
sequence; and the third term is the number of complex multiplications required for the
combining algebra.

g.n
Having performed the decimation in time once, we can repeat the process for each of
the sequences f1(n) and f2(n). Thus f1(n) would result in two (N/4)-point sequences and f2(n)

e
would result in another two (N/4)-point sequences.

\
Let the decimated (N/4)-point sequences of f1(n) be g11(n) and g12(n).

N 
g11 (n) = f1 (2n); for n = 0, 1, 2, ...,   1 
4 
t
N 
and g12 (n) = f1 (2n + 1); for n = 0, 1, 2, ...,   1 
4 
Let the decimated (N/4)-point sequences of f2(n) be g21(n) and g22(n).

\ N 
g21 (n) = f2 (2n); for n = 0, 1, 2, ...,   1 
 4 

N 
and g22 (n) = f2 (2n + 1); for n = 0, 1, 2, ...,   1 
4 

www.EasyEngineering.net
 www.EasyEngineering.net

484 h Digital Signal Processing

Let G11(k) = N/4-point DFT of g11(n) | G21(k) = N/4-point DFT of g21(n)

G12(k) = N/4-point DFT of g12(n) | G22(k) = N/4-point DFT of g22(n)
Then like earlier analysis, we can show that

N 
F1 (k ) = G11 (k ) + WNk/2 G12 (k ); for k = 0, 1, 2, ...,   1 
 2 

N 
F2 (k ) = G21 (k ) + WNk/2 G22 (k ); for k = 0, 1, 2, ...,   1 
 2 

ww
Hence the (N/2)-point DFTs are obtained from the (N/4)-point DFTs.
The implementation of these equations for F1(k) and F2(k) is shown in Figure 7.2.

w .Ea
syE
ngi
nee
rin
g.n
Figure 7.2 Illustration of flow graph of the second stage DIT FFT algorithm for N = 8.

This second step in the decomposition breaks the N/2-point transforms into N/4-point

e
transforms and WNk/2 provides the N/2-point combining algebra. Since the DFT of a sequence
is periodic with period given by the number of points of DFT, G11(k), G12(k), G21(k) and
G22(k) will be periodic with period N/4. t
\  N  N
G11  k +  = G11 (k ) and G12  k +  = G12 (k )
 4  4

 N  N
G21  k +  = G21 (k ) and G22  k +  = G22 (k )
 4  4

 N
k 4 
In addition, the phase factor WN 
=  WNk/ 2

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 485

Therefore, for k ³ N/4, F1(k) and F2(k) are given by

 N  N
F1 (k ) = G11  k    WNk/2 G12  k  
 4  4

 N  N
F2 (k ) = G21  k    WNk/2 G21  k  
 4  4

The implementation using periodicity property is also shown in Figure 7.2.

This decimation of the data sequences is repeated again and again until the resulting
sequences are reduced to two point sequences.

ww Figure 7.3 shows the last stage without and with the consideration of periodicity.

w .Ea
syE
ngi
nee
rin
Figure 7.3 Illustration of flow graph of the third stage DIT FFT algorithm for N = 8.

g.n
Figure 7.4 illustrates the complete flow graph for 3 stages for N = 8. The same graph
drawn in a way to remember easily considering the symmetry is shown in Figure 7.8.

7.4 THE 8-POINT DFT USING RADIX-2 DIT FFT

e t
The computation of 8-point DFT using radix-2 FFT involves three stages of computation.
Here N = 8 = 23, therefore, r = 2 and m = 3. The given 8-point sequence is decimated into
four 2-point sequences. For each 2-point sequence, the two point DFT is computed. From the
results of four 2-point DFTs, two 4-point DFTs are obtained and from the results of two
4-point DFTs, the 8-point DFT is obtained.
Let the given 8-sample sequence x(n) be {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)}.
The 8-samples should be decimated into sequences of two samples. Before decimation they
are arranged in bit reversed order as shown in Table 7.1.

www.EasyEngineering.net
 www.EasyEngineering.net

486 h Digital Signal Processing

ww
w .Ea
Figure 7.4

syE
Illustration of complete flow graph obtained by combining all the three stages for N = 8.

TABLE 7.1 Normal and bit reversed order for N = 8.

Normal order ngi Bit reversed order

x(0)
x(1)
x(000)
x(001) nee x(0)
x(4)
x(000)
x(100)
x(2)
x(3)
x(4)
x(010)
x(011)
x(100)
x(2)
x(6)
x(1)
x(010)
x(110)
x(001) rin
x(5)
x(6)
x(101)
x(110)
x(5)
x(3)
x(101)
x(011) g.n
x(7) x(111) x(7) x(111)
e
The x(n) in bit reversed order is decimated into 4 numbers of 2-point sequences as
shown below.
t
(i) x(0) and x(4)
(ii) x(2) and x(6)
(iii) x(1) and x(5)
(iv) x(3) and x(7)
Using the decimated sequences as input, the 8-point DFT is computed. Figure 7.5 shows the
three stages of computation of an 8-point DFT.
The computation of 8-point DFT of an 8-point sequence in detail is given below. The
8-point sequence is decimated into 4-point sequences and 2-point sequences as shown below.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 487

ww Figure 7.5 Three stages of computation in 8-point DFT.

w
Let x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)} be the 8-point sequence.
f1(n) = {x(0), x(2), x(4), x(6)}, f2(n) = {x(1), x(3), x(5), x(7)} 4-point sequences
obtained from x(n).
.Ea
g11(n) = {x(0), x(4)}, g12(n) = {x(2), x(6)}, 2-point sequences obtained from f1(n)

syE
g21(n) = {x(1), x(5)}, g22(n) = {x(3), x(7)}, 2-point sequences obtained from f2(n)
The relations between the samples of various sequences are given below.
g11(0)
g11(1)
=
=
f1(0)
f1(2)
=
=
x(0)
x(4) ngi g21(0)
g21(1)
=
=
f2(0)
f2(2)
=
=
x(1)
x(5)
g12(0)
g12(1)
=
=
f1(1)
f1(3)
=
=
x(2)
x(6) nee
g22(0)
g22(1)
=
=
f2(1)
f2(3)
=
=
x(3)
x(7)

The first stage of computation

rin
In the first stage of computation, 2-point DFTs of the 2-sample sequences are computed.
Let G11(k) = DFT{g11(n)}. The 2-point DFT of g11(n) is given by
g.n
G11 (k ) =
1

 g11 (n) WNnk/4 ;

n0
for k = 0, 1
e t
\ G11 (0) = g11 (0) W20 + g11 (1) W20 = g11 (0) + g11 (1) = x (0) + x (4) = x (0) + x (4) W20

G11 (1) = g11 (0) W20 + g11 (1) W21 = g11 (0)  g11 (1) = x (0)  x (4) = x (0)  x (4) W20
Let G12(k) = DFT{g12(n)}. The 2-point DFT of g12(n) is given by
1
G12 (k ) =  g12 (n) WNnk/4 ; for k = 0, 1
n 0

\ G12 (0) = g12 (0) W20 + g12 (1) W20 = g12 (0) + g12 (1) = x (2) + x (6) = x (2) + x (6) W20

G12 (1) = g12 (0) W20 + g12 (1) W21 = g12 (0)  g12 (1) = x (2)  x (6) = x (2)  x (6) W20

www.EasyEngineering.net
 www.EasyEngineering.net

488 h Digital Signal Processing

Let G21(k) = DFT{g21(n)}. The 2-point DFT of g21(n) is given by

1
G21 (k ) =  g21 (n) WNnk/4 ; for k = 0, 1
n0

\ G21 (0) = g21 (0) W20 + g21 (1) W20 = g21 (0) + g21 (1) = x (1) + x (5) = x (1) + x (5) W20

G21 (1) = g21 (0) W20 + g21 (1) W21 = g21 (0)  g21 (1) = x (1)  x (5) = x (1)  x (5) W20
Let G22(k) = DFT{g22(n)}. The 2-point DFT of g22(n) is given by
1

 g22 (n) WNnk/4 ;

ww
G22 (k ) = for k = 0, 1
n 0

\ G22 (0) = g22 (0) W20 + g22 (1) W20 = g22 (0) + g22 (1) = x (3) + x (7) = x (3) + x (7) W20

w G22 (1) = g22 (0) W20 + g22 (1) W21 = g22 (0)  g22 (1) = x (3)  x (7) = x (3)  x (7) W20

.Ea
The computation of first stage is shown in Figure 7.6(a).

syE
The second stage of computation
In the second stage of computations, 4-point DFTs are computed using the 2-point DFTs
obtained in stage one as inputs.
ngi
Let F1(k) = DFT{f1(n)}. The 4-point DFT of f1(n) can be computed using the equation

\
F1 (k ) = G 11 (k ) +
nee
WNk/2 G12 (k ); for k = 0, 1, 2, 3

F1 (0) = G11 (0) + W40 G12 (0) = G11 (0) + G12 (0) W40

F1 (1) = G11 (1) + W41G12 (1) = G11 (1) + G12 (1) W41 rin
F1 (2) = G11 (2) + W42 G12 (2) = G11 (0)  G12 (0) W40
g.n
F1 (3) = G11 (3) + W43G12 (3) = G11 (1)  G12 (1) W41

Let F2(k) = DFT{f2(n)}. The 4-point DFT of f2(n) can be computed using the equation
F2 (k ) = G 21 (k ) + W4k G22 (k ); for k = 0, 1, 2, 3
e t
\ F2 (0) = G21 (0) + W40 G22 (0) = G21 (0) + G22 (0) W40
F2 (1) = G21 (1) + W41G22 (1) = G21 (1) + G22 (1) W41
F2 (2) = G21 (2) + W42 G22 (2) = G21 (0)  G22 (0) W40
F2 (3) = G21 (3) + W43G22 (3) = G21 (1)  G22 (1) W41
Here G11(k) and G12(k) are periodic with periodicity of 2.
i.e. G11 (k + 2) = G11 (k ) and G12 ( k + 2) = G12 (k )

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 489

Here G21(k) and G22(k) are periodic with periodicity of 2.

i.e. G21 (k + 2) = G21 (k ) and G22 ( k + 2) = G22 (k )
The computation of second stage is shown in Figure 7.6(b).

The third stage of computation

In the third stage of computations, the 8-point DFT is computed using the 4-point DFTs
obtained in second stage as inputs.
Let X(k) = DFT{x(n)}. The 8-point DFT of x(n) can be computed using the equation.
X (k ) = F1 (k ) + W8k F2 (k ); for k = 0, 1, 2, 3, 4, 5, 6, 7

ww
\ X (0) = F1 (0) + W80 F2 (0)

w X (1) = F1 (1) + W81 F2 (1)

.Ea
X (2) = F1 (2) + W82 F2 (2)
X (3) = F1 (3) + W83 F2 (3)

syE
X (4) = F1 (4) + W84 F2 (4) = F1 (0)  F2 (0)W80
X (5) = F1 (5) + W85 F2 (5) = F1 (1)  F2 (1)W81

ngi
X (6) = F1 (6) + W86 F2 (6) = F1 (2)  F2 (2)W82

nee
X (7) = F1 (7) + W87 F2 (7) = F1 (3)  F2 (3)W83

Here F1(k) and F2(k) are periodic with periodicity of 4.

i.e. F1 (k + 4) = F1 (k ) and F2 (k + 4) = F2 ( k )
rin
The computation of third stage is shown in Figure 7.6(c).

g.n
e t

(a) (b) (c)

Figure 7.6 (a)–(c) Flow graphs for implementation of 1st, 2nd and 3rd stages of computation.

www.EasyEngineering.net
 www.EasyEngineering.net

490 h Digital Signal Processing

7.4.1 Butterfly Diagram

Observing the basic computations performed at each stage, we can arrive at the following
conclusions:
(i) In each computation, two complex numbers a and b are considered.
(ii) The complex number b is multiplied by a phase factor W kN.
(iii) The product bW Nk is added to the complex number a to form a new complex number A.
(iv) The product bW kN is subtracted from complex number a to form new complex
number B.
The above basic computation can be expressed by a signal flow graph shown in Figure 7.7.

ww The signal flow graph is also called butterfly diagram since it resembles a butterfly.

w .Ea
Figure 7.7 Basic butterfly diagram or flow graph of radix-2 DIT FFT.

syE
The complete flow graph for 8-point DIT FFT considering periodicity drawn in a way
to remember easily is shown in Figure 7.8. In radix-2 FFT, N/2 butterflies per stage are

ngi
required to represent the computational process. In the butterfly diagram for 8-point DFT
shown in Figure 7.8, for symmetry, W20 , W40 and W80 are shown on the graph eventhough they

nee
are unity. The subscript 2 indicates that it is the first stage of computation. Similarly,
subscripts 4 and 8 indicate the second and third stages of computation.

rin
g.n
e t
Figure 7.8 The signal flow graph or butterfly diagram for 8-point radix-2 DIT FFT.

7.5 DECIMATION IN FREQUENCY (DIF) RADIX-2 FFT

In decimation in frequency algorithm, the frequency domain sequence X(k) is decimated. In
this algorithm, the N-point time domain sequence is converted to two numbers of N/2-point

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 491

sequences. Then each N/2-point sequence is converted to two numbers of N/4-point

sequences. This process is continued until we get N/2 numbers of 2-point sequences. Finally,
the 2-point DFT of each 2-point sequence is computed. The 2-point DFTs of N/2 numbers of
2-point sequences will give N-samples, which is the N-point DFT of the time domain
sequence. Here the equations for N/2-point sequences, N/4-point sequences, etc., are obtained
by decimation of frequency domain sequences. Hence this method is called DIF.
To derive the decimation-in-frequency form of the FFT algorithm for N, a power of 2,
we can first divide the given input sequence x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6),
x(7) into the first half and last half of the points so that its DFT X(k) is
N
1
N 1 2 N 1

ww X (k ) =  x(n) WNkn =
n0

n0
x (n) WNkn + 
n  N/2
x (n) WNkn

w
N N
1 1  N
2 2
 N  k n  
  x  n +  WN  2 

.Ea =
n 0
x (n) WNkn +
n 0  2

syE
It is important to observe that while the above equation for X(k) contains two summations
over N/2-points, each of these summations is not an N/2-point DFT, since WNnk rather than
WNnk/2 appears in each of the sums.

or
N
2
1

 x (n) WNnk ngi

+ WN( N/2)k
N
2
1

 x  n +
N  nk

nee 2 
X (k ) = WN
n0 n0

rin
N
1
2
  N  nk 
=   x (n) WN + (  1) x  n + 2  WN 

nk k

  
n 0

N
1 g.n
=
2

n0
 k  N   nk
 x (n) + (  1) x  n + 2   WN


Let us split X(k) into even and odd numbered samples.

  e t
For even values of k, the X(k) can be written as

N
1
2
 2k  N   2 nk
X (2k ) =   x (n) + (  1) x  n + 2   WN
  
n0

N
1
2
  N   kn N 
=   x ( n) + x  n + 2   WN/2 ;
  
for k = 0, 1, 2, ...,   1 
2 
n0

www.EasyEngineering.net
 www.EasyEngineering.net

492 h Digital Signal Processing

For odd values of k, the X(k) can be written as

N
1
2
 2 k +1  N   (2 k 1) n
X (2k + 1) =   x (n) + (  1)

xn +

 WN
2  
n0

N
1
2
  N   n kn N 
=   x ( n)  x  n + 2   WN WN/2 ;
  
for k = 0, 1, 2, ...,   1 
2 
n0

The above equations for X(2k) and X(2k + 1) can be recognized as N/2-point DFTs. X(2k) is

ww
the DFT of the sum of first half and last half of the input sequence, i.e. of
{x (n) + x (n + N/2)} and X (2k + 1) is the DFT of the product WNn with the difference of first
half and last half of the input, i.e. of {x (n)  x (n + N/2)}WN .
n

w If we define new time domain sequences, u1(n) and u2(n) consisting of N/2-samples,
such that
.Ea  N N
1

syE
u1 (n) = x (n) + x  n +  ; for n = 0, 1, 2, ...,
 2 2

  N 

ngi
N
and u2 (n) =  x (n)  x  n +   WNn ; for n = 0, 1, 2, ..., 1
  2  2

nee
then the DFTs U1(k) = X(2k) and U2(k) = X(2k + 1) can be computed by first forming the
sequences u1(n) and u2(n), then computing the N/2-point DFTs of these two sequences to
obtain the even numbered output points and odd numbered output points respectively. The

rin
procedure suggested above is illustrated in Figure 7.9 for the case of an 8-point sequence.

g.n
e t

Figure 7.9 Flow graph of the DIF decomposition of an N-point DFT computation into two N/2-point
DFT computations N = 8.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 493

Now each of the N/2-point frequency domain sequences, U 1(k) and U2(k) can be
decimated into two numbers of N/4-point sequences and four numbers of new N/4-point
sequences can be obtained from them.
Let the new sequences be v11(n), v12(n), v21(n), v22(n). On similar lines as discussed
above, we can get

N
v11 (n) = u1 (n) + u1 (n + 2); for n = 0, 1, 2, ..., 1
4

N
v12 (n) = [u1 (n)  u1 (n + 2)] WNn/2 ; for n = 0, 1, 2, ..., 1
4

ww
and

v21 (n) = u2 (n) + u2 (n + 2); for n = 0, 1, 2, ...,

N
1

w
4

.Ea
v22 (n) = [u2 (n)  u2 (n + 2)] WNn/2 ; for n = 0, 1, 2, ...,
N
4
1

syE
This second stage computation for N = 8 is shown in Figure 7.10.

ngi
nee
rin
g.n
Figure 7.10
e
Signal flow graph or butterfly diagram for second stage of computation of 8-point radix-2
t
DIF FIT.

This process is continued till we get only 2-point sequences. The DFT of those 2-point
sequences is the DFT of x(n), i.e. X(k) in bit reversed order.
The third stage of computation for N = 8 is shown in Figure 7.11.
The entire process of decimation involves m stages of decimation where m = log2N.
The computation of the N-point DFT via the DIF FFT algorithm requires (N/2) log 2N
complex multiplications and (N – 1) log2N complex additions (i.e. total number of
computations remains same in both DIF and DIT).

www.EasyEngineering.net
 www.EasyEngineering.net

494 h Digital Signal Processing

ww
w
Figure 7.11 Third stage of computation of DFT of an 8-point sequence by radix-2 DIF FIT algorithm.

.Ea
Observing the basic calculations, each stage involves N/2 butterflies of the type shown
in Figure 7.12.

syE
The butterfly computation involves the following operations:
(i) In each computation two complex numbers a and b are considered.

ngi
(ii) The sum of the two complex numbers is computed which forms a new complex
number A.
(iii) Subtract the complex number b from a to get the term (a – b). The difference term

nee
(a – b) is multiplied with the phase factor or twiddle factor WNn to form a new
complex number B.

rin
g.n
Figure 7.12 Basic butterfly diagram for DIF FIT.

e
The signal flow graph or butterfly diagram of all the three stages together is shown in
Figure 7.13. t
7.6 THE 8-POINT DFT USING RADIX-2 DIF FFT
The DIF computations for an 8-sample sequence are given below in detail.
Let x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)} be the given 8-sample sequence.

First stage of computation

In the first stage of computation, two numbers of 4-point sequences u1(n) and u2(n) are
obtained form the given 8-point sequence x(n) as shown below.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 495

ww
wFigure 7.13 Signal flow graph or butterfly diagram for the 8-point radix-2 DIF FFT algorithm.

.Ea  N
u1 (n) = x (n) + x  n + 
 2

\
syE = x(n) + x(n + 4),
u1(0) = x(0) + x(4)
for n = 0, 1, 2, 3

ngi
u1(1) = x(1) + x(5)

nee
u1(2) = x(2) + x(6)
u1(3) = x(3) + x(7)

and
  N 
u2 ( n) =  x (n)  x  n +  WNn
  2 
rin
= [x (n)  x (n + 4)]WNn
g.n
\ u2 (0) = [x (0)  x (4)] W80
u2 (1) = [x (1)  x (5)] W81
u2 (2) = [x (2)  x (6)] W82
e t
u2 (3) = [ x (3)  x (7)] W83
The samples of the sequences u1(n) and u2(n) are obtained by the butterfly operation shown
in Figure 7.14(a).

Second stage of computation

In the second stage of computation, four numbers of 2-point sequences v11(n), v12(n) and
v21(n), v22(n) are obtained form the two 4-point sequences u1(n) and u2(n) obtained in stage
one as follows:

www.EasyEngineering.net
 www.EasyEngineering.net

496 h Digital Signal Processing

 N
v11 (n) = u1 (n) + u1  n + 
 4
= u1 (n) + u1 (n + 2), for n = 0, 1

\ v11(0) = u1(0) + u1(2)

v11(1) = u1(1) + u1(3)

  N 
and v12 (n) = u1 (n)  u1  n +   WNn/2
  4 

ww
\
= [u1 (n)  u1 (n + 2)] W4n

v12(0) = [u1(0) – u1(2)] W40

w
Also, we have
.Ea
v12(1) = [u1(1) – u1(3)] W41

 N

syE v21 (n) = u2 (n) + u2  n + 

 4
= u2 (n) + u2 (n + 2), for n = 0, 1

\ v21(0) = u2(0) + u2(2)

ngi
and
v21(1) = u2(1) + u2(3)

  nee
N 
v22 (n) = u2 (n)  u2  n +  WNn/2
  4 

= [u2 (n)  u2 (n + 2)]W4n rin

\ v22(0) = [u2(0) – u2(2)] W40 g.n
v22(1) = [u2(1) – u2(3)] W41
e
The samples of the sequences v11(n), v12(n) and v21(n), v22(n) are obtained by the butterfly
operation shown in Figure 7.14(b).
t
Third stage of computation
In the third stage of computation, the 2-point DFTs of the 2-point sequences obtained in the
second stage are computed as follows:
1
DFT [ v11 (n)] = V11 (k ) =  v11 (n) W2kn , for k = 0, 1
n0

1
\ V11 (0) =  v11 (n) W20 = v11 (0) + v11 (1)
n0

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 497

1
V11 (1) =  v11 (n) W2n = v11 (0) W20 + v11 (1) W21 = [v11 (0)  v11 (1)]W20
n0

1
DFT [ v12 (n)] = V12 ( k ) =  v12 (n) W2nk , for k = 0, 1
n0

1
\ V12 (0) =  v12 (n) W20 = v12 (0) + v12 (1)
n 0

ww V12 (1) =
1

 v12 (n) W2n = v12 (0) W20 + v12 (1) W21 = [v12 (0)  v12 (1)]W20
n0

w
Similarly

.Ea V21(0) = v21(0) + v21(1)

V21(1) = [v21(0) – v21(1)] W20
and

syE V22(0) = v22(0) + v22(1)

V22(1) = [v22(0) – v22(1)] W20

ngi
The computation of 2-point DFTs is done by the butterfly operation shown in Figure 7.14(c).

nee
rin
g.n
e t
Figure 7.14 (a)–(c) The first, second and third stages of computation of 8-point DFT by Radix-2 DIF
FFT.

Combining the 3 stages of computation

The final output Vij(k) gives the X(k). The relation can be obtained as given below:

www.EasyEngineering.net
 www.EasyEngineering.net

498 h Digital Signal Processing

X(2k) = U1(k); k = 0, 1, 2, 3 X(2k + 1) = U2(k); k = 0, 1, 2, 3

\ X(0) = U1(0) \ X(1) = U2(0)
X(2) = U1(1) X(3) = U2(1)
X(4) = U1(2) X(5) = U3(2)
X(6) = U1(3) X(7) = U3(3)
U1(2k) = V11(k); k = 0, 1 U1(2k + 1) = V12(k); k = 0, 1
\ U1(0) = V11(0) \ U1(1) = V12(0)
U1(2) = V11(1) U1(3) = V12(1)
U2(2k) = V21(k); k = 0, 1 U2(2k + 1) = V22(k); k = 0, 1
\ U2(0) = V21(0) \ U2(1) = V22(0)

wwU2(2) = V21(1)

From the above relation, we get

U2(3) = V22(1)

w .Ea
X(0) = U1(0) = V11(0)
X(4) = U1(2) = V11(1)

syE
X(2) = U1(1) = V12(0)
X(6) = U1(3) = V12(1)
X(1) = U2(0) = V21(0)

ngi
X(5) = U2(2) = V21(1)
X(3) = U2(1) = V22(0)

nee
X(7) = U2(3) = V22(1)

rin
From the above, we observe that the output is in bit reversed order. If the input is in normal
order, the output is in bit reversed order and the reverse is also true.
The combined signal flow graph or butterfly diagram for 8-point radix-2, DIF FFT
algorithm is shown in Figure 7.13.
g.n
Difference between DIT and DIF e
Comparison of DIT (Decimation-in-time) and DIF (Decimation-in-frequency) algorithms

1. In DIT, the input is bit reversed while the output is in normal order. For DIF, the
t
reverse is true, i.e. the input is in normal order, while the output is bit reversed.
However, both DIT and DIF can go from normal to shuffled data or vice versa.
2. Considering the butterfly diagram, in DIT, the complex multiplication takes place
before the add subtract operation, while in DIF, the complex multiplication takes
place after the add subtract operation.
Similarities
1. Both algorithms require the same number of operations to compute DFT.
2. Both algorithms require bit reversal at some place during computation.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 499

7.6.1 Computation of IDFT through FFT

The IDFT of an N-point sequence {X(k)}; k = 0, 1, ..., N – 1 is defined as

N 1 2Q N 1
1 1
  X (k ) WN nk
j nk
x (n) = X (k ) e N =
N k 0
N k 0

Taking the conjugate of the above equation for x(n), we get

*
1 N 1  1 N 1
x (n) = 
*
 X (k ) WN nk  =  X * (k ) WNnk
ww  N k 0

Taking the conjugate of the above equation for x*(n), we get

 N k 0

w .Ea x (n) =
1  N 1 *
N k 0

  X (k ) WNnk 

*

syE
The term inside the square brackets in the above equation for x(n) is same as the DFT
computation of a sequence X*(k) and may be computed using any FFT algorithm. So we can

ngi
say that the IDFT of X(k) can be obtained by finding the DFT of X *(k), taking the conjugate
of that DFT and dividing by N. Hence, to compute the IDFT of X(k) the following procedure
can be followed
1. Take conjugate of X(k), i.e. determine X*(k). nee
2.
3.
Compute the N-point DFT of X*(k) using radix-2 FFT.
Take conjugate of the output sequence of FFT.
rin
g.n
4. Divide the sequence obtained in step-3 by N.
The resultant sequence is x(n).

e
Thus, a single FFT algorithm serves the evaluation of both direct and inverse DFTs.

EXAMPLE 7.1 Draw the butterfly line diagram for 8-point FFT calculation and briefly
explain. Use decimation-in-time algorithm.
Solution: The butterfly line diagram for 8-point DIT FFT algorithm is shown in Figure 7.15.
t
For 8-point DIT FFT, the input sequence x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)},
must be fed in bit reversed order, i.e. as xr(n) = {x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)}.
Since N = 2m = 23, the 8-point DFT computation using radix-2 FFT involves 3 stages of
computation, each stage involving 4 butterflies. The output X(k) will be in normal order. In
the first stage, four 2-point DFTs are computed. In the second stage they are combined into
two 4-point DFTs. In the third stage, the two 4-point DFTs are combined into one 8-point
DFT. The 8-point FFT calculation requires 8 log28 = 24 complex additions and (8/2) log28 =
12 complex multiplications.

www.EasyEngineering.net
 www.EasyEngineering.net

500 h Digital Signal Processing

ww
w Figure 7.15 Butterfly line diagram for 8-point DIT FFT algorithm for N = 8.

.Ea
EXAMPLE 7.2 Implement the decimation-in-frequency FFT algorithm of N-point DFT
where N = 8. Also explain the steps involved in this algorithm.

syE
Solution: The 8-point radix-2 DIF FFT algorithm involves 3 stages of computation. The
input to the first stage is the input time sequence x(n) in normal order. The output of first
stage is the input to the second stage and the output of second stage is the input to the third

ngi
stage. The output of third stage is the 8-point DFT in bit reversed order.
In DIF algorithm, the frequency domain sequence X(k) is decimated. In this algorithm,

nee
the N-point time domain sequence is converted to two numbers of N/2-point sequences. Then
each N/2-point sequence is converted to two numbers of N/4-point sequences. Thus, we get
4 numbers of N/4, i.e. 2-point sequences. Finally, the 2-point DFT of each 2-point sequence

rin
is computed. The 2-point DFTs of N/2 number of 2-point sequences will give N-samples
which is the N-point DFT of the time domain sequence. The implementation of the 8-point
radix-2 DIF FFT algorithm is shown in Figure 7.16.
g.n
e t

Figure 7.16 Butterfly line diagram for 8-point radix-2 DIF FFT algorithm.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 501

EXAMPLE 7.3 (a) Implement the decimation-in-time FFT algorithm for N = 16, (b) In the
above question how many non-trivial multiplications are required?
Solution: (a) The butterfly line diagram showing the implementation of 16-point radix-2
DIT FFT algorithm for N = 16 is shown in Figure 7.17. For DIT FFT, the given 16-point
sequence x(n) is to be fed in bit reversed order as
xr(n) = {x(0), x(8), x(4), x(12), x(2), x(10), x(6), x(14), x(1), x(9), x(5), x(13), x(3),
x(11), x(7), x(15)}
Since N = 16 = 24, the radix-2 DIT FFT computation involves 4 stages. The output is in
normal order.

ww (b) The number of non-trivial multiplications required in the implementation of DIT

FFT for N = 16 = 24 is N/2 log2N = 16/2 log216 = 8 log2 24 = 8 ´ 4 = 32. The number of
complex additions are N log2 N = 16 log216 = 16 log2 24 = 16 ´ 4 = 64.

w
240.
Number of multiplications required by direct computation = N2 = 162 = 256

.Ea
Number of complex additions required by direct computation = N(N – 1) = 16 ´ 15 =

syE
ngi
nee
rin
g.n
e t

Figure 7.17 Butterfly line diagram for DIT FFT algorithm for N = 16.

www.EasyEngineering.net
 www.EasyEngineering.net

502 h Digital Signal Processing

EXAMPLE 7.4 What is FFT? Calculate the number of multiplications needed in the
calculation of DFT using FFT algorithm with 32-point sequence.
Solution: The FFT, i.e. Fast Fourier transform is a method (or algorithm) for computing
the DFT with reduced number of calculations. The computational efficiency is achieved by
adopting a divide and conquer approach. This approach is based on the decomposition of an
N-point DFT into successively smaller DFTs. This basic approach leads to a family of
efficient computational algorithms known as FFT algorithms. Basically there are two FFT
algorithms. (i) DIT FFT algorithm and (ii) DIF FFT algorithm. If the length of the sequence
N = 2m, 2 indicates the radix and m indicates the number of stages in the computation. In
radix-2 FFT, the N-point sequence is decimated into two N/2-point sequences, each N/2-point

ww
sequence is decimated into two N/4-point sequences and so on till we get two point
sequences. The DFTs of two point sequences are computed and DFTs of two 2-point
sequences are combined into DFT of one 4-point sequence, DFTs of two 4-point sequences

w
are combined into DFT of one 8-point sequence and so on till we get the N-point DFT.

.Ea
The number of multiplications needed in the computation of DFT using FFT algorithm

with N = 32-point sequence is =

N
log 2 N =
32
log 2 2 5 = 80 .

syE
2 2
The number of complex additions = N log2 N = 32 log2 32 = 32 log2 25 = 160

ngi
EXAMPLE 7.5 Explain the inverse FFT algorithm to compute inverse DFT of a 8-point
DFT. Draw the flow graph for the same.
Solution:
nee
The IDFT of an 8-point sequence {X(k), k = 0, 1, 2, ..., 7} is defined as

1 7
x ( n) =  X (k ) W8nk , n = 0, 1, 2, ..., 7
8 k 0
rin
Taking the conjugate of the above equation for x(n), we have
g.n
x * (n) =
1 7 *
  X (k ) W8 
8 k  0

Taking the conjugate of the above equation for x*(n) we have
nk

 e t
*
1 7 
x (n) =   X * (k ) W8 
nk
8 k 0 

The term inside the square brackets in the RHS of the above expression for x(n) is the 8-
point DFT of X *(k). Hence, in order to compute the IDFT of X(k) the following procedure
can be followed:
1. Given X(k), take conjugate of X(k) i.e. determine X *(k).
2. Compute the DFT of X *(k) using radix-2 DIT or DIF FFT, [This gives 8x*(n)]

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 503

3. Take conjugate of output sequence of FFT. This gives 8x(n).

4. Divide the sequence obtained in step 3 by 8. The resultant sequence is x(n).
The flow graph for computation of N = 8-point IDFT using DIT FFT algorithm is
shown in Figure 7.18.

ww
w .Ea
syE
Figure 7.18 Computation of 8-point DFT of X*(k) by radix-2, DIT FFT.

ngi
From Figure 7.18, we get the 8-point DFT of X *(k) by DIT FFT as

\
1 nee
8x* (n) = {8x* (0), 8x* (1), 8x* (2), 8 x* (3), 8 x* (4), 8x* (5), 8 x* (6), 8 x* (7)}

{8x * (0), 8x * (1), 8x * (2), 8 x * (3), 8 x * (4), 8 x * (5), 8 x * (6), 8 x* (7)}*

rin
x (n) =
8

EXAMPLE 7.6 Find the 4-point DFT of the sequence x(n) = {2, 1, 4, 3} by
(a) DIT FFT algorithm (b) DIF FFT algorithm. Also plot the magnitude and phase plot.
g.n
Solution: (a) To compute the 4-point DFT by DIT FFT algorithm, first the given sequence
x(n) = {x(0), x(1), x(2), x(3)} is to be written in bit reversed order as xr(n) = {x(0), x(2), x(1),
x(3)}. The output will be in normal order. The given x(n) in bit reversed order is xr(n) = {2, 4,
1, 3}. The 4-point DFT of x(n) using DIT FFT algorithm is computed as shown in Figure 7.19.
e t

Figure 7.19 4-point DFT by DIT FFT.

www.EasyEngineering.net
 www.EasyEngineering.net

504 h Digital Signal Processing

From Figure 7.19, the 4-point DFT of x(n) by radix-2, DIT FFT algorithm is
X(k) = {10, –2 + j2, 2, –2, –j2}
(b) To compute the DFT by DIF FFT, the input sequence is to be in normal order and
the output sequence will be in bit reversed order. Figure 7.20 shows the computation of
4-point DFT of x(n) by radix-2 DIF FFT algorithm.

ww
w .Ea
Figure 7.20 4-point DFT by DIF FFT.

From Figure 7.20, the 4-point DFT of x(n) is X(k) = {10, –2 + j2, 2, –2 – j2}.
To draw the magnitude and phase plot, we have
X (0) = 10
syE X (0) = 10 and X (0) = 0° = 0 rad

X (1) =  2 + j 2  X (1) = 2 2 + 2 2 = 2.828 and X (1) = 135° = 2.356 rad

ngi
X (2) = 2  X (2) = 2 and X (2) = 0 = 0 rad

nee
X (3) =  2  j 2  X (3) = 2 2 + 2 2 = 2.828 and X (3) =  135° =  2.356 rad

The magnitude and phase spectrum are shown in Figure 7.21.

rin
g.n
e t
Figure 7.21 (a) Magnitude spectrum (b) Phase spectrum.

EXAMPLE 7.7 Compute the circular convolution of the two sequences x1(n) = {1, 2, 0, 1}
and x2(n) = {2, 2, 1, 1} using DFT approach.
Solution: To compute the circular convolution of the two sequences x1(n) and x2(n), i.e. to
compute x1(n) Å x2(n) using DFT approach, first the DFTs of the two sequences, i.e. X1(k)

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 505

and X2(k) are to be determined independently, then their product Y(k) = X1(k)X2(k) is to be
determined and then the IDFT of Y(k), i.e. y(n) is to be determined. Here DFTs and IDFT
are performed via FFT. For DIT FFT, the input sequence is in bit reversed order and output
sequence is in normal order. The computation of 4-point DFTs of x1(n) and x2(n) using radix-
2 DIT FFT algorithm is shown in Figures 7.22(a) and (b).

ww
w .Ea
syE
Figure 7.22
ngi
Computation of (a) DFT of x1(n); (b) DFT of x2(n) by DIT FFT.

From Figures 7.22(a) and (b), we have

nee
X1 (k ) = {4, 1  j,  2, 1 + j} and X 2 (k ) = {6, 1  j, 0, 1 + j}
\ The product sequence X(k) = X1(k)X2(k)
rin
\

\ X * (k ) = {24, j 2, 0,  j 2} in normal order

g.n
X (k ) = {4, 1  j,  2, 1 + j}{6, 1  j, 0, 1 + j} = {24,  j 2, 0, j 2}

X *(k) in bit reverse order is Xr* (k ) = {24, 0, j 2,  j 2}

The computation of 4-point DFT of X *(k) using radix-2 DIT FFT algorithm is shown in
e t
Figure 7.23. For DIT FFT, the input is in bit reversed order and the output is in normal order.

Figure 7.23 Computation of 4-point DFT of X*(k) by radix-2 DIT FFT.

www.EasyEngineering.net
 www.EasyEngineering.net

506 h Digital Signal Processing

From Figure 7.23, we have 4x*(n) = {24, 28, 24, 20}

1
\ x * (n) = {24, 28, 24, 20} = {6, 7, 6, 5}
4
x(n) = {6, 7, 6, 5}* = {6, 7, 6, 5}
\ [x1(n) = {1, 2, 0, 1}] Å [x2(n) = {2, 2, 1, 1}] = [x(n) = {6, 7, 6, 5}]

EXAMPLE 7.8 Compute the DFT of the square wave sequence

 N 
 1, 0  n    1 

ww 
x( n) = 


1,
N
n N
2 




w
where N is even.

Solution: .Ea
2

It is given that N is even, but the value of N is not given. Let us take N = 4.
\
syE x(n) = {1, 1, –1, –1}
Let us calculate X(k) using 4-point radix-2 DIT FFT algorithm as shown in Figure 7.24. For

ngi
DIT FFT, the input is in bit reversed order and output is in normal order. x(n) in bit reversed
order is xr(n) = {1, –1, 1, –1}.

nee
rin
g.n
Figure 7.24 4-point DFT of x(n) by radix-2 DIT FFT.

From Figure 7.24, we have X(k) = {0, 2 – j2, 0, 2 + j2}.

e t
EXAMPLE 7.9 In an LTI system, the input x(n) = {2, 2, 2} and the impulse response
h(n) = {–2, –2}. Determine the response of LTI system by radix-2, DIT FFT.
Solution: The response y(n) of LTI system is given by the linear convolution of input x(n)
and impulse response h(n).
\ Response or output y(n) = x(n) * h(n)
The DFT (or FFT) supports only circular convolution. Hence, to get the result of linear
convolution from circular convolution, the sequences x(n) and h(n) should be converted to the
size of y(n) by appending with zeros and circular convolution of x(n) and h(n) is performed.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 507

The length of x(n) is 3 and the length of h(n) is 2. Hence, the length of y(n) is 3 + 2 – 1 = 4.
Therefore, the given sequences x(n) and h(n) are converted into 4-point sequences by
appending zeros.
\ x(n) = {2, 2, 2, 0} and h(n) = {–2, –2, 0, 0}
Now the response y(n) is given by y(n) = x(n) Å h(n)
Let DFT{x(n)} = X(k), DFT{h(n)} = H(k), and DFT{y(n)} = Y(k)
By convolution theorem of DFT, we get
DFT{x(n) Å h(n)} = X(k)H(k)

ww
\ y(n) = IDFT{X(k)H(k)} = IDFT{Y(k)}
The various steps in computing y(n) are

w Step
Step
Step
Step
1: Determine X(k) using radix-2 DIT FFT algorithm

.Ea
2: Determine H(k) using radix-2 DIT FFT algorithm
3: Determine the product X(k)H(k)
4: Take IDFT of the product X(k)H(k) using radix-2 DIT FFT algorithm.

syE
1. The 4-point DFT of x(n), i.e. X(k) is determined using radix-2, DIT FFT algorithm
as shown in Figure 7.25. For DIT FFT, the input is in bit reversed order and output
is in normal order.
ngi
x(n) = {2, 2, 2, 0}; xr(n) = {2, 2, 2, 0}

nee
rin
g.n
Figure 7.25 Computation of 4-point DFT of x(n) by radix-2, DIT FFT.

From Figure 7.25, X(k) = {6, –j2, 2, j2}.

e t
2. The 4-point DFT of h(n), i.e. H(k) using 4-point DIT FFT is determined as shown
in Figure 7.26.

h( n) = {  2,  2, 0, 0}; hr (n) = {  2, 0,  2, 0}

From Figure 7.26, H ( k ) = {  4,  2 + j 2, 0,  2  j 2}

3. Y (k ) = X (k ) H (k ) = {6,  j 2, 2, j 2} {  4,  2 + j 2, 0,  2  j 2}
= {  24, 4 + j 4, 0, 4  j 4}
4. Y * (k ) = {  24, 4  j 4, 0, 4 + j 4}; Yr* (k ) = {  24, 0, 4  j 4, 4 + j 4}

www.EasyEngineering.net
 www.EasyEngineering.net

508 h Digital Signal Processing

Figure 7.26 Computation of 4-point DFT of h(n) by radix-2, DIT FFT.

The 4-point DFT of Y*(k) using radix-2, DIT FFT is computed as shown in Figure 7.27.

ww
w .Ea
syE
Figure 7.27 Computation of 4-point DFT of Y*(k) by radix-2, DIT FFT.

ngi
From Figure 7.27, we get 4y*(n) = {–16, –32, –32, –16}.

Therefore, y* (n) =
1
4 nee
{16,  32,  32,  16} = {  4,  8,  8,  4}

y(n) = {4,  8,  8,  4}* = {  4,  8,  8,  4}

rin
g.n
EXAMPLE 7.10 Find the response of LTI system with impulse response h(n) = {0.5, 1}
when the input sequence x(n) = {1, 0.5, 0} is applied to it by radix-2 DIT FFT.

x(n) and impulse response h(n), i.e. y(n) = x(n) * h(n).

e
Solution: The response y(n) of LTI system is given by linear convolution of input sequence

The length of x(n) = 3 and the length of h(n) = 2. So the length of output sequence
y(n) is 3 + 2 + (–1) = 4.
t
Since the DFT supports only circular convolution, to get the result of linear
convolution from circular convolution, the sequences x(n) and h(n) are to be converted to the
size of y(n)[i.e., N = 4] by appending with zeros and the circular convolution of x(n) and
h(n) is performed.
x(n) and h(n) as 4-point sequences are x(n) = {1, 0.5, 0, 0} and h(n) = {0.5, 1, 0, 0}.
Now to find y(n) by FFT, we have to find X(k) and H(k) by 4-point radix-2 DIT FFT,
get Y(k) = X(k)H(k), find DFT of Y *(k), take the conjugate of that and divide by 4. The entire
procedure is as given below:
Step 1: Determination of X(k)
Given x(n) = {1, 0.5, 0, 0}, x(n) in bit reversed order is xr(n) = {1, 0, 0.5, 0}.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 509

The computation of 4-point DFT of x(n), X(k) by radix-2 DIT FFT algorithm is shown
in Figure 7.28.

ww Figure 7.28 Computation of 4-point DFT of x(n) by DIT FFT.

From Figure 7.28, the 4-point DFT of x(n) is X(k) = {1.5, 1 – j0.5, 0.5, 1 + j0.5}.

w
Step 2: Computation of H(k)

.Ea
Given h(n) = {0.5, 1, 0, 0}, h(n) in bit reverse order is hr(n) = {0.5, 0, 1, 0).
The computation of 4-point DFT of h(n), i.e. H(k) using radix-2, DIT FFT algorithm is
shown in Figure 7.29.

syE
ngi
nee
Figure 7.29 Computation of 4-point DFT of h(n) by DIT FFT.rin
From Figure 7.29, the 4-point DFT of h(n) is H(k) = {1.5, 0.5 –j1, –0.5, 0.5 + j1}. g.n
Step 3: Computation of Y(k)
e
Y ( k ) = X (k ) H (k ) = {1.5, 1  j 0.5, 0.5, 1 + j 0.5}{1.5, 0.5  j1,  0.5, 0.5 + j1}
= {2.25,  j1.25,  0.25, j1.25}
t
\ Y * (k ) = {2.25, j1.25,  0.25,  j1.25}

Step 4: Y*(k) in bit reverse order is Yr* (k ) = {2.25,  0.25, j1.25,  j1.25}
Computation of 4-point DFT of Y *(k) using radix-2 DIT FFT is shown in Figure 7.30.
From Figure 7.30, we get 4y*(n) = {2, 5, 2, 0}.

1
\ y* (n) = {2, 5, 2, 0} = {0.5, 1.25, 0.5, 0}
4
\ y(n) = {0.5, 1.25, 0.5, 0}* = {0.5, 1.25, 0.5, 0}

www.EasyEngineering.net
 www.EasyEngineering.net

510 h Digital Signal Processing

Figure 7.30 Computation of 4-point DFT of Y *(k) by DIT FFT.

EXAMPLE 7.11 Compute the DFT of the sequence x(n) = {1, 0, 0, 0, 0, 0, 0, 0} (a) directly,

ww
(b) by FFT.
Solution: (a) Direct computation of DFT

w
The given sequence is x(n) = {1, 0, 0, 0, 0, 0, 0, 0}. We have to compute 8-point DFT. So
N = 8.
.Ea N 1 j
2Q N 1 7

 x ( n) e  x (n) WNnk =  x(n) W8nk

nk

syE
DFT {x (n)} = X (k ) = N =
n0 n 0 n0

0 1 2 3 4 5 6 7
= x (0) W8 + x (1) W8 + x (2) W8 + x (3) W8 + x (4) W8 + x (5) W8 + x (6) W8 + x (7) W8
1
ngi
3 4 5
= (1) (1) + (0) (W8 ) + (0) W82 + (0) W8 + (0) W8 + (0) W8 + (0) W8 + (0) W8 = 1
6 7

\
\
X(k) = 1 for all k
nee
X(0) = 1, X(1) = 1, X(2) = 1, X(3) = 1, X(4) = 1, X(5) = 1, X(6) = 1, X(7) = 1
\ X(k) = {1, 1, 1, 1, 1, 1, 1, 1}
rin
(b) Computation by FFT. Here N = 8 = 23
The computation of 8-point DFT of x(n) = {1, 0, 0, 0, 0, 0, 0, 0} by radix-2 DIT FFT
g.n
e
algorithm is shown in Figure 7.31. x(n) in bit reverse order is
xr(n) = {x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)}
= {1, 0, 0, 0, 0, 0, 0, 0}
For DIT FFT input is in bit reversed order and output is in normal order.
t
From Figure 7.31, the 8-point DFT of the given x(n) is X(k) = {1, 1, 1, 1, 1, 1, 1, 1}

EXAMPLE 7.12 An 8-point sequence is given by x(n) = {2, 2, 2, 2, 1, 1, 1, 1}.

Compute the 8-point DFT of x(n) by
(a) Radix-2 DIT FFT algorithm
(b) Radix-2 DIF FFT algorithm
Also sketch the magnitude and phase spectrum.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 511

ww
w
Solution:
.Ea
Figure 7.31 8-point DFT by DIT FFT.

(a) 8-point DFT by Radix-2 DIT FFT algorithm

syE
The given sequence is x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)}
= {2, 2, 2, 2, 1, 1, 1, 1}
The given sequence in bit reversed order is
ngi
xr(n) = {x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)}

nee
= {2, 1, 2, 1, 2, 1, 2, 1}
For DIT FFT, the input is in bit reversed order and the output is in normal order. The

rin
computation of 8-point DFT of x(n), i.e. X(k) by Radix-2 DIT FFT algorithm is shown in
Figure 7.32.

g.n
e t

Figure 7.32 Computation of 8-point DFT of x(n), i.e. X(k) by DIT FFT.

www.EasyEngineering.net
 www.EasyEngineering.net

512 h Digital Signal Processing

From Figure 7.32, we get the 8-point DFT of x(n) as

X (k ) = {12, 1  j 2.414, 0, 1  j 0.414, 0, 1 + j 0.414, 0, 1 + j 2.414}

(b) 8-point DFT by radix-2 DIF FFT algorithm

For DIF FFT, the input is in normal order and the output is in bit reversed order. The
computation of DFT by radix-2 DIF FFT algorithm is shown in Figure 7.33.

ww
w .Ea
syE
Figure 7.33
ngi
Computation of 8-point DFT of x(n) by radix-2 DIF FFT algorithm.

nee
From Figure 7.33, we observe that the 8-point DFT in bit reversed order is
Xr (k ) = {X (0), X (4), X (2), X (6), X (1), X (5), X (3), X (7)}

rin
= {12, 0, 0, 0, 1  j 2.414, 1 + j 0.414, 1  j 0.414, 1 + j 2.414}
\ The 8-point DFT in normal order is
g.n
X (k ) = {X (0), X (1), X (2), X (3), X (4), X (5), X (6), X (7)}
= {12, 1  j 2.414, 0, 1  j 0.414, 0, 1 + j 0.414, 0, 1 + j 2.414}

Magnitude and Phase Spectrum

e t
Each element of the sequence X(k) is a complex number and they are expressed in
rectangular coordinates. If they are converted to polar coordinates, then the magnitude and
phase of each element can be obtained.
The magnitude spectrum is the plot of the magnitude of each sample of X(k) as a
function of k. The phase spectrum is the plot of phase of each sample of X(k) as a function of k.
When N-point DFT is performed on a sequence x(n) then the DFT sequence X(k) will have a
periodicity of N. Hence, in this example, the magnitude and phase spectrum will have a
periodicity of 8 as shown below.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 513

X (k ) = {12, 1  j 2.414, 0, 1  j 0.414, 0, 1 + j 0.414, 0, 1 + j 2.414}

= {12 0, 2.61 67, 0 0, 1.08 22, 0 0, 1.08 22, 0 0, 2.61 67}

= {12 0, 2.61 0.37Q , 0 0, 1.08  0.12Q , 0 0, 1.08 0.12 Q , 0 0, 2.61 0.37 Q}

\ X (k ) = {12, 2.61, 0, 1.08, 0, 1.08, 0, 2.61}

X (k ) = {0,  0.37Q , 0,  0.12 Q , 0, 0.12Q , 0, 0.37Q }

The magnitude and phase spectrum are shown in Figures 7.34(a) and (b).

ww
w .Ea
syE
ngi
Figure 7.34 nee
(a) Magnitude spectrum, (b) Phase spectrum.

EXAMPLE 7.13 Find the 8-point DFT by radix-2 DIT FFT algorithm.
rin
Solution:
x(n) = {2, 1, 2, 1, 2, 1, 2, 1}
g.n
The given sequence is x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)}
= {2, 1, 2, 1, 2, 1, 2, 1}
e
For DIT FFT computation, the input sequence must be in bit reversed order and the output
sequence will be in normal order.
t
x(n) in bit reverse order is
xr(n) = {x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)}
= {2, 2, 2, 2, 1, 1, 1, 1}
The computation of 8-point DFT of x(n) by radix-2 DIT FFT algorithm is shown in Figure 7.35.
From Figure 7.35, we get the 8-point DFT of x(n) as
X(k) = {12, 0, 0, 0, 4, 0, 0, 0}

www.EasyEngineering.net
 www.EasyEngineering.net

514 h Digital Signal Processing

ww Figure 7.35 Computation of 8-point DFT of x(n) by radix-2, DIT FFT.

w
EXAMPLE 7.14
.Ea
Compute the DFT for the sequence x(n) = {1, 1, 1, 1, 1, 1, 1, 1}.
Solution:

syE
The given sequence is x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)}
= {1, 1, 1, 1, 1, 1, 1, 1}

in Figure 7.36.
ngi
The computation of 8-point DFT of x(n), i.e. X(k) by radix-2, DIT FFT algorithm is shown

The given sequence in bit reversed order is

nee
xr(n) = {x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)}
= {1, 1, 1, 1, 1, 1, 1, 1}

rin
For DIT FFT, the input is in bit reversed order and output is in normal order.

g.n
e t

Figure 7.36 Computation of 8-point DFT of x(n) by radix-2, DIT FFT.

From Figure 7.36, we get the 8-point DFT of x(n) as X(k) = {8, 0, 0, 0, 0, 0, 0, 0}.

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 515

EXAMPLE 7.15 Given a sequence x(n) = {1, 2, 3, 4, 4, 3, 2, 1}, determine X(k) using
DIT FFT algorithm.
Solution: The given sequence is x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)}
= {1, 2, 3, 4, 4, 3, 2, 1}
The computation of 8-point DFT of x(n), i.e. X(k) by radix-2, DIT FFT algorithm is shown
in Figure 7.37. For DIT FFT, the input is in bit reversed order and the output is in normal
order.
The given sequence in bit reverse order is
xr(n) = {x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)} = {1, 4, 3, 2, 2, 3, 4, 1}

ww
w .Ea
syE
ngi
nee
Figure 7.37

rin
Computation of 8-point DFT of x(n) by radix-2, DIT FFT.

From Figure 7.37, we get the 8-point DFT of x(n) as

g.n
X (k ) = {20,  5.828  j 2.414, 0,  0.172  j 0.414, 0,  0.172 + j 0.414, 0,  5.828 + j 2.414}

EXAMPLE 7.16 Given a sequence x(n) = {0, 1, 2, 3, 4, 5, 6, 7}, determine X(k) using
DIT FFT algorithm.
Solution:
e
The given sequence is x(n) = {x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)}
t
= {0, 1, 2, 3, 4, 5, 6, 7}
The computation of 8-point DFT of x(n), i.e. X(k) by radix-2, DIT FFT algorithm is shown
in Figure 7.38. For DIT FFT, the input is in bit reversed order and output is in normal order.
The given sequence in bit reverse order is
xr(n) = {x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)}
= {0, 4, 2, 6, 1, 5, 3, 7}

www.EasyEngineering.net
 www.EasyEngineering.net

516 h Digital Signal Processing

ww
w Figure 7.38

.Ea
Computation of 8-point DFT of x(n) by radix-2, DIT FFT.

From Figure 7.38, we get the 8-point DFT of x(n) as

syE
X (k ) = {28,  4 + j 9.656,  4 + j 4,  4 + j1.656,  4,  4  j1.656,  4  j 4,  4  j 9.656}

EXAMPLE 7.17 Determine the response of LTI system when the input sequence x(n) =

ngi
{–1, 1, 2, 1, –1} by radix-2 DIT FFT. The impulse response of the system is h(n) = {–1, 1, –1, 1}.
Solution: The response y(n) is given by linear convolution of x(n) and h(n), but FFT

nee
supports only circular convolution and also for circular convolution the length of sequences
should be same. Since x(n) is of length 5 and h(n) is of length 4, y(n) will be of length
(5 + 4 – 1 = 8). So convert x(n) and h(n) to a length of 8(N1 + N2 – 1 = 5 + 4 – 1) by
appending zeros.
rin
\

and g.n
x(n) = {x(0), x (1), x(2), x (3), x(4), x (5), x(6), x (7)} = {  1, 1, 2, 1,  1, 0, 0, 0}

h(n) = {h (0), h(1), h(2), h(3), h (4), h(5), h(6), h(7)} = {  1, 1,  1, 1, 0, 0, 0, 0}

To compute y(n) by FFT, find DFT of x(n), i.e., X(k), find DFT of h(n), i.e., H(k), multiply
them to find Y(k) = X(k)H(k) and then take IDFT of Y(k).
e t
1. Computation of X(k)
x(n) in bit reversed order is
xr (n) = {x (0), x (4), x (2), x (6), x (1), x (5), x (3), x (7)} = {  1,  1, 2, 0, 1, 0, 1, 0}

The 8-point DFT of x(n), i.e., X(k) is computed by radix-2 DIT FFT as shown in
Figure 7.39. For DIT FFT, the input is in bit reversed order and output is in normal order.
From Figure 7.39, we get the 8-point DFT of x(n) as

X (k ) = {2,  j (2 + 2),  4, j (2  2),  2, j(  2 + 2),  4, j(2 + 2)}

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 517

ww
w Figure 7.39

.Ea
2. Computation of H(k)
Computation of 8-point DFT of x(n) by radix-2 DIT FFT.

syE
h(n) in bit reverse order is

hr (n) = {h(0), h(4), h(2), h (6), h (1), h (5), h (3), h(7)} = {  1, 0,  1, 0, 1, 0, 1, 0}

ngi
The 8-point DFT of h(n), i.e., H(k) is computed by radix-2 DIT FFT algorithm as shown in
Figure 7.40. For DIT FFT, the input is in bit reversed order and output is in normal order.

nee
rin
g.n
e t
Figure 7.40 Computation of 8-point DFT of h(n) by radix-2 DIT FFT.

From Figure 7.40, we get the 8-point DFT of h(n) as

H (k ) = {0,  1 + j (1  2), 0,  1  j (1 + 2),  4,  1 + j (1 + 2), 0,  1 + j (  1 + 2)}

www.EasyEngineering.net
 www.EasyEngineering.net

518 h Digital Signal Processing

3. Determination of Y(k)
Y (k ) = X (k ) H (k ) = {2,  j (2 + 2),  4, j (2  2),  2, j(  2 + 2),  4, j(2 + 2)}

´ {0,  1 + j (1  2), 0,  1  j (1 + 2),  4,  1 + j (1 + 2), 0,  1 + j (  1 + 2)}

= {0,  2 + j(2 + 2), 0, 2  j (2  2), 8, 2 + j (2  2), 0,  2  j(2 + 2)}

4. Computation of IDFT of Y(k)

For the obtained Y(k), we have

Y * (k ) = {0,  2  j (2 + 2), 0, 2 + j (2  2), 8, 2  j(2  2), 0,  2 + j (2 + 2)}

ww
Y *(k) in bit reverse order is
Yr* (k ) = {0, 8, 0, 0,  2  j (2 + 2), 2  j (2  2), 2 + j (2  2),  2 + j (2 + 2)}

w
The 8-point radix-2 DIT FFT is computed as shown in Figure 7.41. For DIT FFT, the input

.Ea
is in bit reversed order and output is in normal order.

syE
ngi
nee
rin
g.n
Figure 7.41 Computation of 8-point DFT of Y*(k) by radix-2, DIT FFT.

From Figure 7.41, we get y* (n) =

1
8
{8,  16, 0,  8, 8, 0, 16,  8}
e t
= {1,  2, 0,  1, 1, 0, 2,  1}

\ y(n) = {y* (n)}* = {1,  2, 0,  1, 1, 0, 2,  1}

EXAMPLE 7.18 Find the IDFT of the sequence

X (k ) = {4, 1  j 2.414, 0, 1  j 0.414, 0, 1 + j 0.414, 0, 1 + j 2.414}
using DIF algorithm.
Solution: The IDFT x(n) of the given 8-point sequence X(k) can be obtained by finding
X*(k), the conjugate of X(k), finding the 8-point DFT of X*(k), using DIF algorithm to get

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 519

8x*(n), taking the conjugate of that to get 8x(n) and then dividing the result by 8 to get x(n).
For DIF algorithm, input X *(k) must be in normal order. The output will be in bit reversed
order for the given X(k).

X * (k ) = {4, 1 + j 2.414, 0, 1 + j 0.414, 0, 1  j 0.414, 0, 1  j 2.414}

The DFT of X *(k) using radix-2, DIF FFT algorithm is computed as shown in Figure 7.42.

ww
w .Ea
syE
Figure 7.42

ngi
Computation of 8-point DFT of X*(k) by radix-2 DIF FFT.

nee
From the DIF FFT algorithm of Figure 7.42, we get
8xr* (n) = {8, 0, 8, 0, 8, 0, 8, 0}
\ 8xr (n) = {8, 0, 8, 0, 8, 0, 8, 0}* = {8, 0, 8, 0, 8, 0, 8, 0}
1 rin
\ x (n) =
8
{8, 8, 8, 8, 0, 0, 0, 0} = {1, 1, 1, 1, 0, 0, 0, 0}

g.n
EXAMPLE 7.19 Compute the IDFT of the sequence

e
X (k ) = {7,  0.707  j 0.707,  j, 0.707  j 0.707, 1, 0.707 + j 0.707, j,  0.707 + j 0.707}
using DIT algorithm. t
Solution: The IDFT x(n) of the given sequence X(k) can be obtained by finding X*(k), the
conjugate of X(k), finding the 8-point DFT of X*(k) using radix-2 DIT FFT algorithm to get
8x*(n), taking the conjugate of that to get 8x(n) and then dividing by 8 to get x(n). For DIT
FFT, the input X*(k) must be in bit reverse order. The output 8x*(n) will be in normal order.
For the given X(k).

X * (k ) = {7,  0.707 + j 0.707, j, 0.707 + j 0.707, 1, 0.707  j 0.707,  j,  0.707  j 0.707}

X*(k) in bit reverse order is
Xr (k ) = {7, 1, j,  j,  0.707 + j 0.707, 0.707  j 0.707, 0.707 + j 0.707,  0.707  j 0.707}

www.EasyEngineering.net
 www.EasyEngineering.net

520 h Digital Signal Processing

The 8-point DFT of X*(k) using radix-2, DIT FFT algorithm is computed as shown in
Figure 7.43.

ww
w .Ea
Figure 7.43 Computation of 8-point DFT of X*(k) by radix-2, DIT FFT.

syE
From the DIT FFT algorithm of Figure 7.43, we have
8x*(n) = {8, 8, 8, 8, 8, 8, 8, 0}
\
\ ngi
8x(n) = {8, 8, 8, 8, 8, 8, 8, 0}
x(n) = {1, 1, 1, 1, 1, 1, 1, 0}

nee
EXAMPLE 7.20 Compute the IDFT of the square wave sequence X(k) = {12, 0, 0, 0, 4, 0,
0, 0} using DIF algorithm.

rin
Solution: The IDFT x(n) of the given sequence X(k) can be obtained by finding X*(k), the

g.n
conjugate of X(k), finding the 8-point DFT of X*(k) using DIF algorithm to get 8x*(n) taking
the conjugate of that to get 8x(n) and then dividing the result by 8 to get x(n). For DIF
algorithm, the input X*(k) must be in normal order and the output 8x*(n) will be in bit
reversed order.
For the given X(k)
X*(k) = {12, 0, 0, 0, 4, 0, 0, 0}
e t
The 8-point DFT of X *(k) using radix-2, DIF FFT algorithm is computed as shown in Figure
7.44.
From Figure 7.44, we have

8 xr* (n) = {16, 16, 16, 16, 8, 8, 8, 8}

\ 8xr (n) = {16, 16, 16, 16, 8, 8, 8, 8}* = {16, 16, 16, 16, 8, 8, 8, 8}

1
\ x (n) = {16, 8, 16, 8, 16, 8, 16, 8} = {2, 1, 2, 1, 2, 1, 2, 1}
8

www.EasyEngineering.net
 www.EasyEngineering.net

Fast Fourier Transform h 521

ww
w Figure 7.44

.Ea
Computation of 8-point DFT of X*(k) by radix-2 DIF FFT.

EXAMPLE 7.21 Find the IDFT of the following

(a) X ( k ) = {1, 1  j 2,  1, 1 + j 2} (b) X (k ) = {1, 0, 1, 0} (c) X (4) = {3, 2 + j, 1, 2  j}

syE
Solution: (a) Given X(k) = {1, 1 – j2, –1, 1 + j2}
Let us find the IDFT of X(k) by radix-2, DIT FFT as shown in Figure 7.45.

ngi
X * (k ) = {1, 1 + j 2,  1, 1  j 2}; Xr* (k ) = {1,  1, 1 + j 2, 1  j 2}

nee
rin
g.n
Figure 7.45

From Figure 7.45, we have

Computation of 4-point DFT of X*(k) by radix-2 DIT FFT. e t
4x*(n) = {2, 6, –2, –2}

1
\ x (n) = {2, 6,  2,  2}* = {0.5, 1.5,  0.5,  0.5}
4

(b) Given X(k) = {1, 0, 1, 0}

Let us find the IDFT of the given 4-point X(k) by radix-2, DIF FFT as shown in Figure 7.46.
X *(k) = {1, 0, 1, 0}

www.EasyEngineering.net
 www.EasyEngineering.net

522 h Digital Signal Processing

Figure 7.46 Computation of 4-point DFT of X*(k) using radix-2 DIF FFT.

From Figure 7.46, we have

ww
\ x (n) =
1
4 xr* (n) = {2, 2, 0, 0}

[2, 0, 2, 0]* = {0.5, 0, 0.5, 0}

w .Ea
(c) Given X(k) = {3, 2 + j, 1, 2 – j}
4

Let us find the IDFT of the given 4-point X(k) by radix-2, DIF FFT as shown in

syE
Figure 7.47.
X*(k) = {3, 2 – j, 1, 2 + j)

ngi
nee
rin
Figure 7.47

g.n
Computation of 4-point DFT of X*(k) by radix-2, DIF FFT.

e
From Figure 7.47, we have

\ x (n) =
4 xr* ( n) = {8, 0, 0, 4}

1
4
[8, 0, 0, 4]* = {2, 0, 0, 1}
t
7.7 FFT ALGORITHMS FOR N A COMPOSITE NUMBER
Till now we have discussed DIT and DIF FFT algorithms for the important special case of N
a power of 2, i.e. N = 2m. They are called radix-2 FFTs. When N is a power of 2, the
decomposition leads to a highly efficient computational algorithm. Furthermore, all the
required computations are butterfly computations that correspond essentially to two-point
DFTs. For this reason, the power-of-2 algorithms are particularly simple to implement. So in

www.EasyEngineering.net