Chapter 5

Discrete Fourier Transform(DFT)

and Fast Fourier Transform(FFT)

5.1 Introduction
The Discrete Time Fourier Transform (DTFT) discussed in Chapter 4, provides a method to represent
a discrete time signal in frequency domain and to perform frequency analysis of discrete time signal.
The drawback in DTFT is that the frequency domain representation of a discrete time signal obtained
using DTFT will be a continuous function of w and so it cannot be processed by digital system. The discrete
Fourier transform (DFT) has been developed to convert a continuous function of w to a discrete function of
w, so that frequency analysis of discrete time signals can be performed on a digital system.
Basically, the DFT of a discrete time signal is obtained by sampling the DTFT of the signal at N uniform
frequency intervals and the number of samples (i.e., value of N) should be sufficient to avoid aliasing of
frequency spectrum. The samples of DTFT are represented as a function of integer k, and so the DFT is a
sequence consisting of N complex numbers represented as X(k) for k = 0,1,2,3,...... (N – 1).
Since X(k) is a sequence consisting of complex numbers, the magnitude and phase of each sample can
be computed and listed as magnitude sequence and phase sequence respectively. The graphical plots of
magnitude and phase as a function of k are also drawn.
The plot of magnitude versus k is called magnitude spectrum and the plot of phase versus k is called
phase spectrum. In general, these plots are called frequency spectrum.
The drawback in DFT is that the computation of each sample of DFT involves a large number of
calculations and when large number of samples are required, the number of calculations will further increase.
In order to overcome this drawback, a number of methods or algorithms have been developed to reduce the
number of calculations. The various methods developed to compute DFT with reduced number of calculations
are collectively called Fast Fourier Transform (FFT).
Chapter 5- Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 2

5.2 Discrete Fourier Transform (DFT) of Discrete Time Signal

5.2.1 Development of DFT from DTFT
The frequency domain representation of a discrete time signal obtained using discrete time Fourier
transform (DTFT) will be a continuous and periodic function of w, with periodicity of 2p. In order to obtain
discrete function of w, the DTFT can be sampled at sufficient number of frequency intervals.
Let X(ejw ) be discrete time Fourier transform of the discrete time signal x(n). The discrete Fourier
transform (DFT) of x(n) is obtained by sampling one period of the discrete time Fourier transform X(ejw ) at a
finite number of frequency points.
The frequency domain sampling is conventionally performed at N equally spaced frequency points in
the period, 0 £ w £ 2p . The sampling frequency points are denoted as w k and they are given by,
2πk
ωk = ; for k = 0, 1, 2, ..... ,N – 1
N
Now, the DFT is a sequence consisting of N-samples of DTFT. Let the samples are denoted by X(k)
for k = 0, 1, 2, ...... N-1. Therefore, the sampling of X(ejw ) is mathematically expressed as,

X(k) = X (e jω ) ; for k = 0, 1, 2, ....., N – 1 .....(5.1)

2 πk
ω=
N
The DFT sequence starts at k = 0, corresponding to w = 0 but does not include k = N, corresponding
to w = 2p, (since the sample at w = 0 is same as the sample at w = 2p). Generally, the DFT is defined along with
number of samples and is called N-point DFT. The number of samples N for a finite duration sequence x(n) of
length L should be such that, N ³ L, in order to avoid aliasing of frequency spectrum.
The sampling of Fourier transform of a sequence to get DFT is shown in example 5.1. To calculate DFT
of a sequence it is not necessary to compute Fourier transform, since the DFT can be directly computed using
the definition of DFT as given by equation (5.2).
5.2.2 Definition of Discrete Fourier Transform (DFT)
Let, x(n) = Discrete time signal of length L
X(k) = DFT of x(n)
Now, the N-point DFT of x(n), where N ³ L, is defined as,
N −1 − j2 πkn
X( k ) = ∑
n=0
x(n) e N ; for k = 0,1,2,......., N − 1 .....(5.2)

Symbolically, the N-point DFT of x(n) can be expressed as,

DFT{x(n)}
where, DFT is the operator that represents discrete Fourier transform.
N −1 − j2 πkn
∴ DFT {x(n)} = X( k ) = ∑ x(n) e N ; for k = 0, 1, 2, ..... , N − 1
n=0

Since X(k) is a sequence consisting of N-complex numbers for k = 0, 1, 2, ...... N-1, the DFT of x(n) can
be expressed as a sequence as shown below.
l
X( k ) = X(0), X(1), X(2),................ X( N − 1) q
5. 3 Digital Signal Processing
5.2.3 Frequency Spectrum Using DFT
The X(k) is a discrete function of frequency of discrete time signal w, and so it is also called discrete
frequency spectrum (or signal spectrum) of the discrete time signal x(n).
The X(k) is a complex valued function of k and so it can be expressed in rectangular form as,
X(k) = Xr(k) + jXi(k)
where, Xr(k) = Real part of X(k)
Xi(k) = Imaginary part of X(k)
Now the Magnitude function (or Magnitude spectrum) |X(k)| is defined as,
|X(k)|2 = X(k) X*(k) or X(k) = X(k) X* (k)
where X*(k) is complex conjugate of X(k)
2
Alternatively, X(k) = X(k) X* (k) = Xr ( k ) + jXi ( k ) X r ( k ) − jXi ( k )
= X2r ( k ) + Xi2 ( k )

∴ X(k) = X2r ( k ) + Xi2 ( k )

The Phase function (or Phase spectrum) ÐX(k) is defined as,

∠X(k) = Arg[X(k)] = tan −1

LM X (k) OP
i

N X (k) Q
r

Since X(k) is a sequence consisting of N-complex numbers for k = 0, 1, 2, ......... N-1, the magnitude and
phase spectrum of X(k) can be expressed as a sequence as shown below.
Magnitude sequence, X(k) = X(0) , n X(1) , X(2) ,................ s
X(N − 1)

l
Phase sequence, ∠X(k) = ∠X(0), ∠X(1), ∠X(2),................ ∠X(N −1)q
The magnitude and phase sequence can be sketched graphically as a function of k.
The plot of samples of magnitude sequence versus k is called magnitude spectrum and the plot of
samples of phase sequence versus k is called phase spectrum. In general, these plots are called frequency
spectrum.
5.2.4 Inverse DFT
Let, x(n) = Discrete time signal
X(k) = N-point DFT of x(n)
The inverse DFT of the sequence X(k) of length N is defined as,
N −1 j2 πkn
1
x(n) =
N ∑
k=0
X(k) e N ; for n = 0, 1, ....., N − 1 .....(5.3)

Symbolically the inverse DFT of x(n) can be expressed as,

DFT-1{X(k)}
where, DFT -1 is the operator that represents inverse DFT.
N −1 j2 πkn
1
DFT −1 {X(k)} = x(n) =
N ∑
k=0
X(k) e N ; for n = 0, 1, ...... , N − 1
Chapter 5- Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 4
We also refer to x(n) and X(k) as a DFT pair and this relation is expressed as,
DFT
x(n) ¬ ® X(k)
DFT - 1

5.3 Properties of DFT

1. Linearity
The linearity property of DFT states that the DFT of a linear weighted combination of two or more
signals is equal to similar linear weighted combination of the DFT of individual signals.
Let, DFT{x1(n)} = X1(k) and DFT{x2(n)} = X2(k). Then by linearity property,
DFT{a1 x1(n) + a2 x2(n)} = a1 X1(k) + a2 X2(k) , where a1 and a2 are constants.
Proof :
By definition of discrete Fourier transform,
N −1 − j2πkn
X1(k) = DFT {x1(n)} = ∑ x (n) e1
N .....(5.4)
n=0

N −1 − j2 πkn
X 2(k) = DFT {x 2(n)} = ∑ x 2(n) e N .....(5.5)
n=0

N −1 − j2πkn
DFT {a1 x1(n) + a2 x 2(n)} = ∑ a1 x1(n) + a2 x 2 (n) e N

n=0

N −1 LMa x (n)e − j2πkn − j2πkn OP

= ∑ MN1 1
N + a2 x 2 (n) e N
PQ
n=0

N −1 − j2 πkn N −1 − j2 πkn
= a1 ∑ x1(n)e N + a2 ∑ x (n) e
2
N

n=0 n=0

= a1 X1(k) + a 2 X 2 (k) Using equations (5.4) and (5.5).

2. Periodicity
If a sequence x(n) is periodic with periodicity of N samples then N-point DFT, X(k) is also periodic with
a periodicity of N samples.
Hence, if x(n) and X(k) are N point DFT pair then,
x(n + N) = x(n) ; for all n
X( k + N) = X(k) ; for all k
Proof :

By definition of DFT, the (k + N)th coefficient of X(k) is given by,

− j2πn (k + N) − j2 πn k − j2 πn N
N−1 N−1
N
X(k + N) = ∑ x(n) e = ∑ x(n) e N e N

n=0 n=0
N−1 − j2πn k N−1 − j2 πn k
= ∑ x(n) e N e− j2πn = ∑ x(n) e N for integer n, e− j2πn = 1
n=0 n=0
= X(k ) Using definition of DFT.
5. 5 Digital Signal Processing
3. Circular time shift
The circular time shift property of DFT says that if a discrete time signal is circularly shifted in time
− j2 πkm
by m units then its DFT is multiplied by e N .

2 π km
−j
l q l
i. e., if , DFT x(n) = X(k), then DFT x(( n − m)) N = X(k) e q N

Proof :

N−1 − j2 πkn N−1 − j2 πk(p + m)

m
DFT x((n − m))N r= n=0
∑ x((n − m))N e N = ∑
p=0
x(p) e N
Let, p = n – m, \ n = p + m
N−1 − j2πkp − j2 πkm
= ∑ x(p) e N e N
p=0

LM
N−1 − j2πkp OP e − j2 πkm

MN ∑
= x(p) e N N
p=0 PQ
− j2πkm
= X( k) e N Using definition of DFT.

4. Time reversal
The time reversal property of DFT says that reversing the N-point sequence in time is equivalent to
reversing the DFT sequence.
i.e., if, DFT{x(n)} = X(k), then DFT{x (N-n)} = X(N-k).
Proof :

N−1 − j2πkn N−1 − j2 πk( N − m )

Let, m = N – n, \ n = N – m
m r ∑ x(N − n) e
DFT x(N − n) =
n=0
N = ∑
m=0
x(m) e N

N−1 −j2πk N j2πkm N−1 j2πkm

= ∑
m=0
x(m) e N e N = ∑
m=0
x(m) e N e − j2 π k
Since k is an integer, e- j2p k = 1.
N−1 j2πkm N−1 j2 πkm
= ∑ x(m)
m=0
e N = ∑ x(m)
m=0
e N e− j2πm Since m is an integer, e- j2p m = 1.

N−1 j2 πkm − j2 πm N N−1 − j2 πm( N − k)

= ∑
m=0
x(m) e N e N = ∑
m=0
x(m) e N

= X(N − k) Using definition of DFT.

5. Conjugation
Let x(n) be a complex N-point discrete sequence and x*(n) be its conjugate sequence.
Now if, DFT{x(n)} = X(k), then DFT{x*(n)} = X*(N–k).
Chapter 5- Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 6
Proof :
N−1 − j2 πkn LM x(n) e OP
N−1 j2 πkn
∗

o
DFT x∗(n) t = ∑
n=0
x∗( n) e N =
n=0MN ∑ PQ
N

LM x(n) e
N−1 j2 πkn OP = LM x(n) e
∗
N−1 j2 πkn − j 2 πnN OP ∗

MN ∑ e− j2π n
PQ MN ∑
= N N e N e–j2pn = 1
n=0 n=0 PQ
L N−1
= M ∑ x( n) e
− j2πn( N − k )
N
∗
OP = X(N − k) = X∗(N − k)
∗
Using definition of DFT.
MN n=0 PQ
6. Circular frequency shift
The circular frequency shift property of DFT says that if a discrete time signal is multiplied by
j2 πmn
e N its DFT is circularly shifted by m units.

R| j2 π m n U|
l q
i.e., if, DFT x(n) = X(k) then DFT x(n) e S| N
V| = X((k − m)) N
T W
Proof :
R| j2 πmn U| = x(n) e
N−1 j2πmn − j2πkn

S|
DFT x( n) e N
V| ∑ N e N

T W n=0

N−1 − j2 π( k − m) n
= ∑ x( n) e N

n=0

= X(( k − m))N Using definition of DFT.

7. Multiplication
The multiplication property of DFT says that the DFT of product of two discrete time sequences is
equivalent to circular convolution of the DFTs of the individual sequences scaled by a factor 1/N.
1
i.e., if, DFT {x(n)} = X(k), then DFT x1 (n) x2 (n) = m r X (k) * X2 (k)
N 1
Proof :
1
N−1 j2 πkn
1
N −1 j2 πmn Let, k = m
By definition of inverse DFT, x1(n) =
N
∑ X1(k) e N =
N
∑ X1(m) e N .....(5.6)
k=0 m=0
By definition of DFT,
N −1 − j2 πkn N−1L1 N−1 j2 πmn OP − j2 πkn
DFT {x1(n) x 2 (n)} = ∑ x1(n) x2 (n) e N = ∑ MM N ∑ X1(m) e N
PQ x (n) Using
e 2
N

n=0 n=0N m=0

equation (5.6).
1
N−1 LM N−1 − j2 πkn j2 πmn OP
=
N
∑ MN ∑
X1(m) x 2(n) e N e N
PQ
Rearranging the order of summation.
m=0 n=0
Using definition of DFT.
1
N−1 L N−1 − j2 π(k − m)n OP 1 N−1
=
N ∑ X (m) MM ∑
1 x 2 (n) e N
PQ = N ∑ X1(m) X 2 ((k − m))N
m=0 N n=0 m=0

1
= X1(k) ∗ X 2(k)
N Using definition of circular convolution.
5. 7 Digital Signal Processing
8. Circular convolution
The circular convolution of two N-point sequences x1(n) and x2(n) is defined as,
N −1
x1 ( n) ∗ x 2 ( n) = ∑ x1 ( m) x 2 (( n − m)) N Refer equation (2.57) of Chapter 2.
m= 0

The convolution property of DFT says that, the DFT of circular convolution of two sequences is
equivalent to product of their individual DFTs.
Let, DFT{x1(n)} = X1(k) and DFT{x2(n)} = X2(k), then by convolution property,
DFT{x1(n) * x2(n)} = X1(k) X2(k)
Proof :

Let, x1(n) and x 2(n) be N - point sequences. Now by definition of DFT,

N−1 − j2 π n k N−1 − j2 π n k
Let, n = m
X1(k) = ∑ x1(n) e N = ∑ x1(m) e N ; k = 0, 1, 2, ..... N − 1 .....(5.7)
n=0 n=0

N−1 − j2 π n k N−1 − j2 πpk Let, n = p

X 2 (k) = ∑ x 2(n) e N = ∑ x 2(p) e N ; k = 0, 1, 2, ..... N − 1 .....(5.8)
n=0 p=0

Consider the product X1(k) X 2(k). The inverse DFT of the product is given by,
N−1 j2πnk
1
DFT −1{X1(k) X 2(k)} =
N
∑ X1(k) X 2 (k) e N

k=0

1 N−1 L N−1 − j2πmk OP LM x (p) e

N−1 − j2 πpk OP e j2 πnk Using equations
= ∑ MM ∑ x1(m) e N
PQ MN ∑ 2
N
PQ
N
(5.7) and (5.8).
Nk=0 N m=0 p=0

j2 πk(n − m − p)
1 N−1 N−1 N−1
=
Nm=0
∑
x1(m) x 2(p) ∑ ∑ e N .....(5.9)
p=0 k=0

N-1 j2 πk(n − m − p)
Consider the summation ∑ e N in equation (5.9).
k=0
Let, n − m − p = qN, where q is an integer. Since q is an
integer, e j2p q =1.
N−1 j2 πk(n − m − p) N−1 j2 πkqN N−1 N−1
k
∴ ∑
k=0
e N = ∑
k=0
e N = ∑
k=0
ee j = ∑ 1
j2πq

k=0
k
=N .....(5.10)

N-1
Consider the summation ∑
p=0
x 2 (p) in equation (5.9).

Since, n − m − p = qN, p = n − m − qN
N−1 N−1 N−1 N−1
∴ ∑ x (p)
p=0
2 = ∑ x (n − m − qN) = ∑ x (n − m, mod N) = ∑ x ((n − m))
m=0
2
m=0
2
m=0
2 N .....(5.11)

Using equations (5.10) and (5.11), the equation (5.9) can be written as shown below.
N−1 N−1 N−1
1
DFT −1{X1(k) X 2 (k)} =
N m=0
∑ x (m) ∑ x ((n − m))
1
m=0
2 N N= ∑ x (m) x ((n − m))
m=0
1 2 N

= x1(n) ∗ x 2 (n)
Using definition of circular convolution.
∴ X1(k) X 2 (k) = DFT { x1(n) ∗ x 2(n)}
Chapter 5- Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 8
9. Circular correlation
The circular correlation of two sequences x(n) and y(n) is defined as,
N−1
rxy (m) = ∑ x(n) y∗ ((n − m)) N Refer equation (2.70) of Chapter 2.
n=0

Let, DFT{x (n)} = X(k) and DFT{y (n)} = Y(k), then by correlation property,

DFT {rxy (m)} = DFT

|RS ∑ x(n) y ((n − m))
N−1
* |UV = X(k) Y (k) *
|T
n=0
N
|W
Proof :
Let, x(n) and y(n) be N - point sequences. Now by definition of DFT,
N−1 − j2 πnk
X(k) = ∑ x(n) e N ; k = 0, 1, 2, ..... N − 1 .....(5.12)
n=0
N−1 − j2 πnk N−1 − j2 πpk Let, n = p
Y(k) = ∑ y(n) e N = ∑ y(p) e N ; k = 0, 1, 2, ..... N − 1 .....(5.13)
n=0 p=0

Consider the product X(k)Y * (k). The inverse DFT of the product is given by,

1 N−1 j2πnk
1 N−1 j2 πmk Let, n = m
DFT −1 {X(k) Y * (k)} = ∑ X(k) Y * (k) e N = ∑ X(k) Y * (k) e N
N k=0 N k=0

1 N−1 L N−1 − j2 πnk OP LM N−1 − j2 πpk OP* e j2 πmk

Using equations
= ∑ MM ∑ x(n) e N
PQ MN ∑ y(p) e N
PQ
N
(5.12) and (5.13).
N k=0 N n=0 p=0

N−1 N−1 N−1 j2πk(m − n + p)

1
=
N
∑ x(n) ∑ y*(p) ∑ e N .....(5.14)
n=0 p=0 k=0

N-1 j2πk(m − n + p)
Consider the summation ∑ e N in equation (5.14).
k=0

Let, m − n + p = qN, where q is an integer. Since q is an integer, e j2p q =1.

N−1 j2 πk(m − n + p) N−1 j2πkqN N−1 N−1
k
∴ ∑
k=0
e N = ∑
k=0
e N = ∑
k=0
ee jj2πq
=
k=0
∑1 k
= N .....(5.15)

N-1
Consider the summation ∑
p=0
y∗(p) in equation (5.14).
.....(5.16)
Since, m − n + p = qN, p = n − m + qN
N−1 N−1 N−1 N−1
∴ ∑ y* (p) = ∑ y*(n − m + qN) = ∑ y* (n − m, mod N) = ∑ y* ((n − m))
p=0 n=0 n=0 n=0
N

Using equations (5.15) and (5.16), the equation (5.14) can be written as shown below.
N−1 N−1
1
DFT −1 {X(k) Y * (k)} = ∑ x(n) ∑ y* ((n − m)) N N
N n=0 n=0
N−1
= ∑ x(n) y* ((n − m))
n=0
N = rxy (m)

∴ X(k) Y * (k) = DFT rxy (m) n s Using definition of circular correlation.

5. 9 Digital Signal Processing
10. Parseval's relation
Let DFT{x1(n)} = X1(k) and DFT{x2(n)} = X2(k). Then by Parseval's relation,
N−1 N−1
1
∑ x1 (n) x*2 (n) = ∑ X1 (k) X*2 (k)
n=0
N k=0

Proof :

Let, x1(n) and x 2(n) be N - point sequences.

N−1 − j2 π n k
Now by definition of DFT, X1(k) = ∑ x1(n) e N .....(5.17)
n=0
− N 1 j2 π n k
1
Now by definition of inverse DFT, x2 (n) =
N k=0
X 2(k) e ∑ N .....(5.18)

Consider the right - hand side term of Parseval's relation. Using equation (5.17).

1 N−1
1 N−1 L N−1 OP * − j2 πnk

N ∑ X1(k) X *2 (k) = N ∑ MM ∑ x1(n) e

PQ X (k)
N
2
k=0 k=0 N n=0

N−1 L1 N−1 OP L1− j2 πnk N−1 N−1 j2 πnk OP*

= ∑ x (n) MM N ∑ X * (k) e
1
PQ2= ∑ x (n) M
MN N ∑
N
1 X 2(k) e N
PQ
n=0 N k=0 n=0 k=0
N−1
= ∑ x1(n) x2* (n) Using equation (5.18).
n=0

5.4 Relation Between DFT and Z -Transform

The Z-transform of N-point sequence x(n) is given by,
N−1
l q = X( z) = ∑ x ( n ) z
Z x( n) −n

n= 0 j2 πk
N
Let us evaluate X(z) at N equally spaced points on unit circle, i.e., at z = e
j2πk j2π k
N N 2πk
Note : Since, e = 1 and ∠e = ,
N
j2π k
the term, z = e N , for k = 0,1,2,3.....N − 1
represents N equally spaced points on unit circle in z-plane.
N−1 N−1 − j2 πkn
∴ X( z) j2 πk
= ∑ x(n)z− n j2 πk = ∑ x(n) e N .....(5.19)
z=e N n=0 z=e N n=0

By the definition of N-point DFT we get,

N−1 − j2πkn
X( k ) = ∑ x( n) e N .....(5.20)
n= 0

From equations (5.19) and (5.20) we can say that,

X( k ) = X( z ) j2πk .....(5.21)
z= e N
From equation (5.21), we can conclude that the N-point DFT of a finite duration sequence can be obtained
from the Z-transform of the sequence, by evaluating the Z-transform of the sequence at N equally spaced points
around the unit circle. Since the evaluation is performed on unit circle the ROC of X(z) should include unit circle.
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 10
Table 5.1 : Properties of Discrete Fourier Transform (DFT)
Note : X(k) = DFT {x(n)} ; X1(k) = DFT {x1(n)} ; X2(k) = DFT {x2(n)} ; Y(k) = DFT {y(n)}

Property Discrete time signal Discrete Fourier Transform

Linearity a1x1(n) + a2x2(n) a1X1(k) + a2 X2(k)

Periodicity x(n + N) = x(n) X(k + N) = X(k)

− j2 π k m
Circular time shift x((n – m))N X(k) e N

Time reversal x(N – n) X(N – k)

Conjugation x*(n) X*(N – k)
j2 π m n
Circular frequency shift x(n) e N X(( k − m )) N

1
Multiplication x1(n) x2(n) X1 ( k ) ∗ X2 ( k )
N
N−1
Circular convolution x1 ( n) ∗ x2 ( n) = ∑ x1 ( m) x2 (( n − m)) N X1(k) X2(k)
m=0
N−1
Circular correlation rxy ( m) = ∑ x(n) y* ((n − m)) N X(k) Y*(k)
n=0
Symmetry of X ( k ) = X∗ ( N − k )
real signals x(n) is real
X r ( k ) = Xr ( N − k )
Xi ( k ) = − Xi ( N − k )
| X( k )| = | X( N − k )|
∠X ( k ) = − ∠X ( N − k )

Symmetry of x(n) is real and even X(k) = Xr(k) and Xi(k) = 0

real and even signal x(n) = x(N – n)
Symmetry of x(n) is real and odd X(k) = jXi(k) and Xr(k) = 0
real and odd signal x(n) = -x(N – n)
N−1 N−1
1
Parseval's relation ∑ x1(n) x∗2 (n) N ∑ X1 ( k ) X∗2 ( k )
n=0 k= 0

5.5 Analysis of LTI Discrete Time Systems Using DFT

In Chapter 4, Section 4.6, it is shown that Fourier transform is an useful tool for the analysis of discrete
time systems in frequency domain. But the drawback in Fourier transform is that it is a continuous function of
w and so it will not be useful for digital processing of signals and systems. Hence DFT is proposed, therefore
the analysis of discrete time systems in frequency domain can be conveniently performed using DFT for
digital processing of signals and systems.
Discrete Frequency Spectrum
In general the DFT of a signal gives the discrete frequency spectrum of a signal.
Let x(n) and X(k) be a DFT pair.
5. 11 Digital Signal Processing
Now, X(k) = Discrete frequency spectrum of discrete time signal.
|X(k)| = Magnitude spectrum of discrete time signal.
ÐX(k) = Phase spectrum of discrete time signal.
In particular, the DFT of impulse response, h(n) of a discrete time system gives discrete frequency
response or frequency spectrum of the discrete time system.
Let h(n) and H(k) be a DFT pair.
Now, H(k) = Discrete frequency spectrum of discrete time system.
|H(k)| = Magnitude spectrum of discrete time system.
ÐH(k) = Phase spectrum of discrete time system.
Response of LTI Discrete Time System Using DFT
The response of an LTI discrete time system is given by linear convolution of input and impulse
response of the system.
Let, x(n) = Input to an LTI system
h(n) = Impulse response of the LTI system
Now, the response or output of the system y(n) is given by,
y(n) = x(n) * h(n) = h(n) * x(n)
+∞
where, x(n) ∗ h(n) = ∑ x( m) h(n − m)
m =−∞
.....(5.22)

The DFT supports only circular convolution and so, the linear convolution of equation (5.22) has to
be computed via circular convolution. If x(n) is N1-point sequence and h(n) is N2-point sequence then linear
convolution x(n) and h(n) will generate y(n) of size N1 + N2 - 1. Therefore in order to perform linear convolution
via circular convolution the x(n) and h(n) should be converted to N1 + N2 - 1 point sequences by appending
zeros. Now the circular convolution of N1 + N2 - 1 point sequences x(n) and h(n) will give same result as that
of linear convolution.
Let, x(n) be N1-point sequence and h(n) be N2-point sequence.
Let us convert x(n) and h(n) to N1+N2-1 point sequences.
Let, Y(k) = N1 + N2 - 1 point DFT of y(n)
X(k) = N1 + N2 - 1 point DFT of x(n)
H(k) = N1 + N2 - 1 point DFT of h(n)
Now by circular convolution theorem of DFT,
DFT{x(n) * h(n)} = X(k) H(k)
On taking inverse DFT of the above equation we get,
x(n) * h(n) = DFT –1{X(k) H(k)}
Since, x(n) * h(n) = y(n), the above equation can be written as,
y(n) = DFT –1{X(k) H(k)} .....(5.23)
From the equation (5.23), we can say that the output y(n) is given by the inverse DFT of the product
of X(k) and H(k). Hence to determine the response of an LTI discrete time system, first find
N1 + N2 - 1 point DFT of input x(n) to get X(k) and N1 + N2 - 1 point DFT of impulse response h(n) to get H(k),
then take inverse DFT of the product X(k) H(k).
Chapter 5- Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 12

Example 5.1
Compute 4-point DFT and 8-point DFT of causal three sample sequence given by,

1
x(n) = ; 0 ≤ n ≤ 2
3
= 0 ; else
Show that DFT coefficients are samples of Fourier transform of x(n), (Refer example 4.6 of Chapter 4 for
Fourier transform).

Solution
By the definition of N-point DFT, the kth complex coefficient of X(k), for 0 £ k £ N – 1, is given by,
N − 1 − j2πkn
X(k) = ∑ x(n) e N

n =0

a) 4-point DFT (\
\ N = 4)
4 −1 − j2πkn 2 − jπkn − jπk
X(k) = ∑ x(n) e 4 = ∑ x(n) e 2 = x(0) e0 + x(1) e 2 + x(2) e − jπk e±j q = cosq ± jsinq
n=0 n =0
− jπk
=
1 1
+ e 2 +
1 − jπk 1
e = 1+ cos
πk LM
− j sin
πk
+ cos πk – jsin πk
OP
3 3 3 3 2 N 2 Q
For 4-point DFT, X(k) has to be evaluated for k = 0, 1, 2, 3.

1
When k = 0 ; X(0) = [1 + cos 0 − j sin 0 + cos 0 − j sin 0]
3
1
= (1 + 1 − j0 + 1 − j0) = 1 = 1∠0
3

When k = 1 ; X(1) =
1 LM
1 + cos
π
− j sin
π
+ cos π − j sin π
OP
3 N 2 2 Q
1 1 1
=
(1 + 0 − j − 1 − j0) = − j = ∠ − π / 2 = 0.333∠ − 0.5π
3 3 3
1
When k = 2 ; X(2) = 1 + cos π − j sin π + cos 2π − j sin 2π
3
1 1
= (1 − 1 − j0 + 1 − j0) = = 0.333∠0
3 3

When k = 3 ; X(3) =
1 LM
1 + cos
3π
− j sin
3π
+ cos 3π − j sin 3π
OP
3 N 2 2 Q
1 1 1
= (1 + 0 + j − 1 − j0) = j = ∠π / 2 = 0.333∠0.5π
3 3 3
\ The 4-point DFT sequence X(k) is given by,

X(k) = { 1∠0, 0.333∠ − 0.5π, 0.333∠0, 0.333∠0.5π } Phase angles

∴ Magnitude Function, X(k) = { 1, 0.333, 0.333, 0.333 } are in radians.
Phase Function, ∠X(k) = { 0, − 0.5π, 0, 0.5π }
5. 13 Digital Signal Processing
b) 8-point DFT (\
\ N = 8)
8 −1 − j2πkn 2 − jπkn − jπk − jπk
X(k) = ∑ x(n) e 8 = ∑ x(n) e 4 = x(0) e0 + x(1) e 4 + x(2) e 2
e±j q = cosq ± jsinq
n=0 n =0
− jπk − jπk
=
1 1
+ e 4 +
1
e 2 =
1LM
1+ cos
πk
− j sin
πk
+ cos
πk
– jsin
πk OP
3 3 3 3 N 4 4 2 2 Q
For 8-point DFT, X(k) has to be evaluated for k = 0, 1, 2, 3, 4, 5, 6, 7.
1
When k = 0 ; X(0) = [1 + cos 0 − j sin 0 + cos 0 − j sin 0]
3
1
= (1 + 1 − j0 + 1 − j0) = 1 = 1∠0
3

When k = 1 ; X(1) =
1 LM
1 + cos
π
− j sin
π
+ cos
π
− j sin
π OP
3 N 4 4 2 2 Q
= 0.333 (1 + 0.707 − j0.707 + 0 − j1)
= 0.568 − j0.568 = 0.803∠ − 0.785 = 0.803∠ − 0.25π
0.785
1 LM 2π 2π 2π 2π OP × π = 0.25π
When k = 2 ; X(2) = 1 + cos − j sin + cos − j sin π
3 N 4 4 2 2 Q
= 0.333 (1 + 0 − j1 − 1 − j0)
= − j0.333 = 0.333∠ − π / 2 = 0.333∠ − 0.5π

When k = 3 ; X(3) =
1 LM
1 + cos
3π
− j sin
3π
+ cos
3π
− j sin
3π OP
3 N 4 4 2 2 Q
= 0.333 (1 − 0.707 − j0.707 + 0 + j1)
= 0.098 + j0.098 = 0.139∠ 0.785 = 0.139∠0.25π

When k = 4 ; X(4) =
1 LM
1 + cos
4π
− j sin
4π
+ cos
4π
− j sin
4π OP
3 N 4 4 2 2 Q
= 0.333 (1 − 1 − j0 + 1 − j0) = 0.333 = 0.333∠0

When k = 5 ; X(5) =
1 LM
1 + cos
5π
− j sin
5π
+ cos
5π
− j sin
5π OP
3 N 4 4 2 2 Q
= 0.333 (1 − 0.707 + j0.707 + 0 − j1)
= 0.098 − j0.098 = 0.139∠ − 0.785 = 0.139∠ − 0.25π

When k = 6 ; X(6) =
1 LM
1 + cos
6π
− j sin
6π
+ cos
6π
− j sin
6π OP
3 N 4 4 2 2 Q
= 0.333 (1 + 0 + j1 − 1 − j0)
= j0.333 = 0.333∠π / 2 = 0.333∠0.5π

When k = 7 ; X(7) =
1 LM
1 + cos
7π
− j sin
7π
+ cos
7π
− j sin
7π OP
3 N 4 4 2 2 Q Phase angles
= 0.333 (1 + 0.707 + j0.707 + 0 + j1) are in radians.
= 0.568 + j0.568 = 0.803∠0.785 = 0.803∠0.25π

\ The 8-point DFT sequence X(k) is given by,

X(k) = {1∠0, 0.803∠ − 0.25π , 0.333∠ − 0.5π, 0.139∠0.25π, 0.333∠0, 0.139∠ − 0.25π,
0.333∠0.5π, 0.803∠0.25π }
∴ Magnitude Function, X(k ) = { 1, 0.803, 0.333, 0.139, 0.333, 0.139, 0.333, 0.803 }
Phase Function, ∠X(k) = { 0, − 0.25π, − 0.5π, 0.25π, 0, − 0.25π, 0.5π, 0.25π }
Chapter 5- Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 14
The magnitude spectrum of X(k) are shown in fig 1, 2 and 3 for N = 4, N = 8, and N = 16 respectively. The
curve shown in dotted line is the sketch of magnitude function of X(ejw ) for w in the range 0 to 2p. Here it is
observed that the magnitude of DFT coefficients are samples of magnitude function of X(ejw ), (Refer example 4.6
for the magnitude function of X(ejw )).
The phase spectrum of X(k) are shown in fig 4, 5 and 6 for N = 4, N = 8, and N = 16 respectively. The
curve shown in dotted line is the sketch of phase function of X(ejw ) for w in the range 0 to 2p. Here it is observed
that the phase of the DFT coefficients are samples of phase function of X(ejw ), (Refer example 4.6 for the phase
function of X(ejw )).
X (k) ∠X ( k )
1.0 0.75 π

0.50 π
0.8
0.25 π
0.6
0
1 2 3 4 K
0.4
−0.25π

0.2 −0.50π

0 −0.75 π
1 2 3 4 K
F ig 4 : P h a se sp e ctru m o f X (k) fo r N = 4 .
F ig 1 : M a g n itu d e sp ectru m o f X (k ) for N = 4 .
X(k) ∠X ( k )
0.75 π

0.50 π

0.25 π

0
1 2 3 4 5 6 7 8 K
−0.25π

−0.50π

−0.75 π

F ig 5 : P h a se sp e c tru m o f X (k ) fo r N = 8 .

X(k) ∠X ( k )
0.75π

0.50π

0.25π

0
1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 K
−0.25π 9

−0.50π

−0.75 π

F ig 6 : P h a se sp ectrum o f X (k ) for N = 1 6 .
5. 15 Digital Signal Processing
Example 5.2
Compute the DFT of the sequence, x(n) = {0, 1, 2, 1}. Sketch the magnitude and phase spectrum.

Solution
The given signal x(n) is 4-point signal and so, let us compute 4-point DFT.

By the definition of DFT, the 4-point DFT is given by, e±j q = cosq ± jsinq
4 −1 − j2πkn 3 − jπkn
X(k) = ∑ x(n) e 4 = ∑ x(n) e 2
n = 0 n = 0
− jπk − j3πk − jπk − j3πk
= x(0) e0 + x(1) e 2 + x(2) e− jπk + x(3) e 2 = 0 + e 2 + 2 e− jπk + e 2

πk πk 3πk 3πk
= cos − jsin + 2(cos πk − j sin πk) + cos − j sin
2 2 2 2

=
FG cos πk
+ 2 cos πk + cos
3πk IJ FG
− j sin
πk
+ sin
3πk IJ sin πk = 0 for integer k
H 2 2 K H 2 2 K
When k = 0 ; X(0) = ( cos 0 + 2 cos 0 + cos 0) – j (sin 0 + sin 0)

= (1 + 2 + 1) – j (0 + 0) = 4 = 4Ð 0

When k = 1; X(1) =
FG cos π + 2 cosπ + cos
3π IJ FG
− j sin
π
+ sin
3π IJ
H 2 2 K H 2 2 K
= (0 − 2 + 0) − j (1 − 1) = –2 = 2∠180o = 2∠π

c
When k = 2 ; X(2) = cos π + 2 cos 2π + cos 3π − j(sin π + sin 3π) h
= ( −1 + 2 − 1) − j (0 + 0) = 0

When k = 3 ; X(3) =
FG cos 3π + 2 cos 3π + cos
9π IJ FG
− j sin
3π
+ sin
9π IJ
H 2 2 K H 2 2 K
= (0 − 2 + 0) − j( −1 + 1) = –2 = 2∠180o = 2∠π
\ X(k) = { 4 Ð 0, 2Ð p, 0, 2Ð p }
Magnitude Spectrum, |X(k)| = { 4, 2, 0, 2 }
Phase Spectrum, ÐX(k) = { 0, p, 0, p }

X(k) ∠X ( k )
π π
π
4
0.75π
3

2 0.5π
2
2

0.25π
1

0 1 2 3 0 1 2 3
k k
F ig 1 : M a g n itu d e S p e ctru m . F ig 2 : P h a se S pe ctru m .
Chapter 5- Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 16

Example 5.3
Compute circular convolution of the following two sequences using DFT.
x1(n) = { 0, 1, 0, 1 } and x2(n) = { 1, 2, 1, 2 }
- -
Solution
Given that, x1(n) = { 0, 1, 0, 1 }. The 4-point DFT of x1(n) is,
4 −1 − j2πnk 3 − jπnk
l
DFT x1(n) q = X1(k) = ∑ x1(n) e 4 = ∑ x1(n) e 2 ; k = 0, 1, 2, 3
n = 0 n = 0
πk 3πk
−j −j
= x1(0) e0 + x1(1) e 2 + x1(2) e− jπk + x1(3) e 2

πk 3πk πk 3πk
−j −j −j −j
= 0 + e 2 + 0 + e 2 = e 2 +e 2

When k = 0 ; X1(0) = e0 + e0 = 1 + 1 = 2
− jπ − j3π e±j q = cosq ± jsinq
When k = 1 ; X1(1) = e 2 + e 2 = −j + j = 0
− jπ − j3π
When k = 2 ; X1(2) = e + e = − 1 − 1 = −2
− j3π − j9π
When k = 3 ; X1(3) = e 2 + e 2 = j − j= 0

Given that, x2(n) = { 1, 2, 1, 2}. The 4-point DFT of x2(n) is,

4−1 − j2πnk 3 − jπnk
l
DFT x 2 (n) q = X2(k) = ∑ x 2 (n) e 4 = ∑ x 2(n) e 2 ; k = 0, 1, 2, 3
n = 0 n = 0
− jπk − j3πk
= x 2(0) e0 + x 2(1) e 2 + x 2(2) e− jπk + x 2(3) e 2

− jπk − j3πk
= 1 + 2e 2 + e− jπk + 2 e 2

When k = 0 ; X2(0) = 1 + 2 e0 + e0 + 2 e0 = 1 + 2 + 1 + 2=6

− jπ − j3π
When k = 1 ; X2(1) = 1 + 2 e 2 + e− jπ + 2 e 2 = 1 − 2j − 1 + 2j = 0
− jπ − j2π − j3π
When k = 2 ; X2(2) = 1 + 2 e + e + 2e = 1 − 2 + 1 − 2 = −2
− j3π − j9 π
When k = 3 ; X2(3) = 1 + 2 e 2 + e− j3π + 2 e 2 = 1 + 2j − 1 − 2j = 0
R| 2 ; k = 0 R| 6 ; k = 0

X1(k) =
|S 0 ; k = 1
X2 (k) =
|S 0 ; k = 1

||−2 ; k = 2 ||−2 ; k = 2
|T 0 ; k = 3 |T 0 ; k = 3
Let, X3(k) be the product of X1(k) and X2(k).
\ X3(k) = X1(k) X2(k)

When k = 0 ; X3(0) = X1(0) ´ X2(0) = 2 ´ 6 = 12

When k = 1 ; X3(1) = X1(1) ´ X2(1) = 0 ´ 0 = 0
When k = 2 ; X3(2) = X1(2) ´ X2(2) = -2 ´ –2 = 4

When k = 3 ; X3(3) = X1(3) ´ X2(3) = 0 ´ 0 = 0

∴ X3 (k ) = m 12, 0, 4, 0 r
5. 17 Digital Signal Processing
By circular convolution theorem of DFT, we get,
DFT {x1(n) * x2(n)} = X1(k) X2(k) Þ x1(n) * x2(n) = DFT-1 { X1(k) X2(k) } = DFT-1 { X3(k) }
Let x3(n) be the 4-point sequence obtained by taking inverse DFT of X3(k).
4 −1 j2πnk 3 jπnk
1 1 1
DFT − mX (k)r
3 = x3(n) = ∑ X3 (k) e 4 = ∑ X3(k) e 2 ; n = 0, 1, 2, 3
4 k = 0
4 k = 0

=
1 LM
X3 (0) e0 + X3(1) e
jπn
2 + X3(2) e jπn + X3(3) e
j3πn
2
OP sin πn = 0
4 MN PQ for integer n
1
= 12 + 0 + 4e jπn + 0 = 3 + e jπn = 3 + cos πn + j sin πn = 3 + cos πn
4
When n = 0 ; x 3(0) = 3 + cos 0 = 3 + 1 = 4
When n = 1 ; x 3(1) = 3 + cos π = 3 − 1 = 2
When n = 2 ; x3 (2) = 3 + cos 2π = 3 + 1 = 4
When n = 3 ; x 3 (3) = 3 + cos 3π = 3 − 1 = 2
∴ x1(n) ∗ x 2 (n) = x3 (n) = l4, 2, 4, 2q
-

Example 5.4
Compute linear and circular convolution of the following two sequences using DFT.
x(n) = {1, 2 } and h(n) = { 2, 1 }
- -
Solution
Linear Convolution by DFT
The linear convolution of x(n) and h(n) will produce a 3 sample sequence. To avoid time aliasing let us
convert the 2 sample input sequences into 3-sample sequences by padding with zeros.
∴ x(n) = 1, 2, 0l q and h(n) = l2, 1, 0q
- -
By the definition of N-point DFT, the three point DFT of x(n) is,
3−1 − j2πkn − j2πk − j4 πk − j2πk
X(k) = ∑ x(n) e 3 = x(0) e0 + x(1) e 3 + x(2) e 3 = 1 + 2e 3

n = 0
When k = 0 ; X(0) = 1 + 2e0 = 1+ 2 = 3
− j 2π
When k = 1; X(1) = 1 + 2 e 3 = 1 + 2( −0.5 − j0.866) = − j1.732 e±jq = cosq ± jsinq
− j4 π
When k = 2; X(2) = 1 + 2 e 3 = 1 + 2( −0.5 + j0.866) = j1.732
By the definition of N-point DFT, the three point DFT of h(n) is,
3−1 − j2πkn − j2πk − j4 πk − j2πk
H(k) = ∑ h(n) e 3 = h(0) e0 + h(1) e 3 + h(2) e 3 = 2 + e 3

n = 0

When k = 0 ; H(0) = 2 + e0 = 2 + 1= 3
− j 2π
When k = 1; H(1) = 2 + e 3 = 2 − 0.5 − j0.866 = 1.5 − j0.866
− j4 π
When k = 2; H(2) = 2 + e 3 = 2 − 0.5 + j0.866 = 1.5 + j0.866
Chapter 5- Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 18
Let, Y(k) = X(k) H(k) ; for k = 0, 1, 2
When k = 0 ; Y(0) = X(0) H(0) = 3 ´ 3 = 9
When k = 1 ; Y(1) = X(1) H(1) = (– j1.732) ´ (1.5–j0.866) = –1.5 – j2.598
When k = 2 ; Y(2) = X(2) H(2) = ( j1.732) ´ (1.5+j0.866) = –1.5 + j2.598
\ Y(k) = {9, – 1.5 – j2.598, – 1.5 + j2.598}
-
The sequence y(n) is obtained from inverse DFT of Y(k). By definition of inverse DFT,
N − 1 j2πkn
1
y(n) = DFT −1 {Y(k)} = ∑ Y(k) e N ; for n = 0, 1, 2, ..... , N − 1
N k = 0
2 j2πkn
1
∴ y(n) =
3 ∑ Y(k) e 3

k = 0

1L OP
j2πn j4 πn
= MY(0) e +
3M
0
Y(1) e 3 + Y(2) e 3
PQ ; for n = 0, 1, 2
N
1L OP
j2πn j4πn
= M9 + (−1.5
3M
− j2.598) e 3 + (−1.5 + j2.598) e 3
PQ
N
j2πn j4 πn
= 3 + (−0.5 − j0.866) e 3 + (−0.5 + j0.866) e 3

When n = 0 ; y(0) = 3 + (−0.5 − j0.866) e0 + ( −0.5 + j0.866) e0

= 3 − 0.5 − j0.866 − 0.5 + j0.866 = 2
j2π j4 π
3 3
e±jq = cosq ± jsinq
When n = 1; y(1) = 3 +(−0.5 − j0.866) e + (−0.5 + j0.866) e
= 3 + (−0.5 − j0.866) ( −0.5 + j0.866) + (−0.5 + j0.866) ( −0.5 − j0.866)
= 3 + (0.52 + 0.8662 ) + (0.52 + 0.8662 ) = 3 + 1+ 1= 5
j4 π j8 π
3 3
When n = 2; y(2) = 3 +( −0.5 − j0.866) e + (−0.5 + j0.866) e
= 3 + (−0.5 − j0.866) ( −0.5 − j0.866) + (−0.5 + j0.866) (−0.5 + j0.866)
= 3 + (−0.5 − j0.866)2 + (−0.5 + j0.866)2
= 3 − 0.5 + j0.866 − 0.5 − j0.866 = 2
∴ x(n) ∗ h(n) = y(n) = l2, 5, 2q
A
Circular Convolution by DFT
The given sequences are 2-point sequences. Hence 2-point DFT of the sequences are obtained as
follows.
The 2-point DFT of x(n) is given by,
2− 1 − j2πkn
X(k) = ∑ x(n) e 2 = x(0) e0 + x(1) e− jπk = 1 + 2 e− jπk ; for k = 0,1
n = 0
When k = 0; X(0) = 1 + 2 e0 = 1 + 2 = 3
When k = 1; X(1) = 1 + 2 e–jp = 1 – 2 = -1
∴ X(k) = l3, − 1q
-
The 2-point DFT of h(n) is given by,
2−1 − j2πkn
H(k) = ∑ h(n) e 2 = h(0) e0 + h(1) e− jπk = 2 + e− jπk ; for k = 0, 1
n = 0
5. 19 Digital Signal Processing

When k = 0; H(0) = 2 + e0 = 2 + 1= 3
When k = 1; H(1) = 2 + e − jπ = 2 − 1 = 1

∴ H(k) = l3, 1q
-

Let the product of X(k) and H(k) be equal to Y(k).

∴ Y(k ) = X(k ) H(k) ; for k = 0, 1

When k = 0 ; Y(0) = X(0) H(0) = 3 × 3 = 9

When k = 1 ; Y(1) = X(1) H(1) = −1 × 1 = −1
l
∴ Y(k) = 9, − 1 q
A
The sequence y(n) is obtained from inverse DFT of Y(k). By the definition of inverse DFT,
N − 1 j2πkn
1
y(n) = DFT −1{Y(k)} =
N
∑ Y(k) e N ; for n = 0, 1, 2, ..... , N − 1
k =0

Here, N = 2

1 j2πkn
1 1 1
∴ y(n) =
2
∑ Y(k) e
k =0
2 =
2
Y(0) + Y(1) e jπn =
2
9 − e jπn = 4.5 − 0.5e jπn

When n = 0; y(0) = 4.5 − 0.5e0 = 4.5 − 0.5 = 4

When n = 1; y(1) = 4.5 − 0.5e jπ = 4.5 + 0.5 = 5 ejp = –1

∴ x(n) ∗ h(n) = y(n) = l4, 5q

-

5.6 Fast Fourier Transform (FFT)

The Fast Fourier Transform (FFT) is a method (or algorithm) for computing the discrete Fourier
transform (DFT) with reduced number of calculations. The computational efficiency is achieved if we adopt
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 an efficient computational algorithms
known collectively as FFT algorithms.
Radix-r FFT
In an N-point sequence, if N can be expressed as N = rm, then the sequence can be decimated into
r-point sequences. For each r-point sequence, r-point DFT can be computed. 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. This FFT algorithm is called radix-r FFT. In computing N-point DFT by this method
the number of stages of computation will be m times.
Radix-2 FFT
For radix-2 FFT, the value of N should be such that, N = 2m, so that the N-point sequence is decimated
into 2-point sequences and the 2-point DFT for each decimated sequence is computed. From the results of
2-point DFTs, the 4-point DFTs can be computed. From the results of 4-point DFTs, the 8-point DFTs can be
computed and so on, until we get N-point DFT.
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 20

Number of Calculations in N-point DFT

Let, X(k) be N-point DFT of an L-point discrete time sequence x(n), where N ³ L. Now, the N-point DFT
is a sequence consisting of N-complex numbers. Each complex number of the sequence is calculated using
the following equation (equation 5.2).
N −1 − j2 πkn
X(k) = ∑ x(n) e N ; for k = 0,1,2,......., N − 1
n=0
− j2 πk − j4 πk − j6 πk − j2(N −1) πk
= x(0) e0 + x(1) e N + x(2) e N + x(3) e N +...............+ x(N − 1) e N

− j2 πk − j4 πk − j6 πk − j 2 ( N −1) πk
∴ X(k) = x(0) e0 + x(1)e N + x( 2) e N + x( 3) e N + ..... + x( N − 1) e N
123 14243 14243 14243 144424443
Complex Complex Complex Complex Complex
multiplication multiplication multiplication multiplication multiplication
1 444444444444444 424444444444444444 3
N − 1 Complex additions

From the above equation we can say that,

The number of calculations to calculate X(k) for one value of k are,
N number of complex multiplications and
N – 1 number of complex additions.
The X(k) is a sequence consisting of N complex numbers.
Therefore, the number of calculations to calculate all the N complex numbers of the X(k) are,
N ´ N = N2 number of complex multiplications and
N ´ (N – 1) = N(N – 1) number of complex additions.
Hence, in direct computation of N-point DFT, the total number of complex additions are N(N – 1) and
total number of complex multiplications are N2.
Number of Calculations in Radix-2 FFT
In radix-2 FFT, N = 2m, and so there will be m stages of computations, where m = log2N, with each stage
having N/2 butterflies. (Refer section 5.7.2 and 5.8.2).
The number of calculations in one butterfly are,
1 number of Complex multiplication and
2 number of Complex additions.
N
There are butterflies in each stage.
2
Therefore, number of calculations in one stage are,
N N
× 1= complex multiplications and
2 2
N
× 2 = N complex additions.
2
The N-point DFT involves m stages of computations. Therefore, the number of calculations for m
stages are,
N N N
m× = log 2 N × = log 2 N complex multiplications and
2 2 2
m × N = log 2 N × N = N log 2 N complex additions.
5. 21 Digital Signal Processing
Hence, in radix-2 FFT, the total number of complex additions are reduced to Nlog2N and total number
of complex multiplications are reduced to (N/2) log2N.
The table 5.2 presents a comparison of the number of complex multiplications and additions in
radix-2 FFT and in direct computation of DFT. From the table it can be observed that for large values of N, the
percentage reduction in calculations is also very large. log22m = m log10 x
log y x =
Table 5.2 : Comparison of Number of Computation in Direct DFT and FFT log10 y

Direct Computation Radix-2 FFT

Number of
Complex Complex Complex Complex
points
additions Multiplications additions Multiplications
N
N(N–1) N2 Nlog2N (N/2)log2N

4 4
4 (= 22) 12 16 4 ´ log222 =4 ´ 2 = 8 × log2 22 = × 2 = 4
2 2
8 8
8 (= 23) 56 64 8 ´ log223 = 8 ´ 3 = 24 × log2 23 = × 3 = 12
2 2
16 16
16 (= 24) 240 256 16 ´ log224 = 16 ´ 4 = 64 × log2 24 = × 4 = 32
2 2
32 32
32 (= 25) 992 1,024 32 ´ log225 = 32 ´ 5 = 160 × log2 25 = × 5 = 80
2 2
64 64
64 (= 26) 4,032 4,096 64 ´ log226 = 64 ´ 6 = 384 × log2 26 = × 6 = 192
2 2

128 128
128 (= 27) 16,256 16,384 128 ´ log227 = 128 ´ 7 = 896 × log2 27 = × 7 = 448
2 2

Phase or Twiddle Factor

By the definition of DFT, the N-point DFT is given by,
N−1 − j2πnk
X( k ) = ∑ x( n) e N ; for k = 0, 1, 2,.....,N – 1 .....(5.24)
n= 0

To simplify the notation it is desirable to define the complex valued phase factor WN (also called as
twiddle factor) which is an Nth root of unity as,
− j2π
WN = e N

Here, W represents a complex number 1Ð –2p. Hence the phase or argument of W is –2p. Therefore,
when a number is multiplied by W, only its phase changes by –2p but magnitude remains same.
− j2π
∴W = e
The phase value –2p of W can be multiplied by any integer and it is represented as prefix
in W. For example multiplying –2p by k can be represented as Wk.
− j2π × k
∴e ⇒ Wk
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 22
The phase value –2p of W can be divided by any integer and it is represented as suffix in W.
For example dividing –2p by N can be represented as WN.
1
− j2 π ×
− j2 π ÷ N N
∴e = e ⇒ WN
− j2 π n k nk
∴e N
e
= e − j2 π j N = WNnk .....(5.25)

Using equation (5.25) the equation (5.24) can be written as,

N−1
X( k ) = ∑ x( n) WNkn ; for k = 0, 1, 2,.....,N – 1 .....(5.26)
n= 0

The equation (5.26) is the definition of N-point DFT using phase factor, and this equation is popularly
used in FFT.

5.7 Decimation in Time (DIT) Radix-2 FFT

The N-point DFT of a sequence x(n) converts the time domain N-point sequence x(n) to a frequency
domain N-point sequence X(k). In Decimation In Time (DIT) algorithm, the time domain sequence x(n) is
decimated and smaller point DFTs are performed. The results of smaller point DFTs are combined to get the
result of N-point DFT.
In DIT radix-2 FFT, the time domain sequence is decimated into 2-point sequences. For each two point
sequence, the two point DFT is computed. The results of 2-point DFTs are used to compute 4-point DFTs. A
pair of 2-point DFT results are used to compute one 4-point DFT. The results of 4-point DFTs are used to
compute 8-point DFTs. A pair of 4-point DFT results are used to compute one 8-point DFT. This process is
continued until we get N-point DFT.
In general we can say that, in decimation in time 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 N/4 point DFTs, and so on.
Let, x(n) be N-sample sequence. We can decimate x(n) into two sequences of N/2 samples. Let the two
sequences be f1(n) and f2(n). Let f1(n) consists of even numbered samples of x(n) and f2(n) consists of odd
numbered samples of x(n).

bg b g
∴ f1 n = x 2n ; for n = 0, 1, 2, 3 ....., N − 1
2
f b ng = xb2n + 1g
2 ; for n = 0, 1, 2, 3 ....., N −1
2
Let, X(k) = N-point DFT of x(n)
F1(k) = N/2 point DFT of f1(n)
F2(k) = N/2 point DFT of f2(n)
By definition of DFT the N/2 point DFT of f1(n) and f2(n) are given by,
N N
−1 −1
2 2
F1 (k) = ∑ f1(n) WNkn2 ; F2 (k) = ∑ f2 (n) WNkn2
n= 0 n= 0

Now, N-point DFT X(k), in terms of N/2 point DFTs F1(k) and F2(k) is given by,
k
X( k ) = F1 (k) + WN F2 (k) , where, k = 0, 1, 2, ....., N – 1 .....(5.27)
5. 23 Digital Signal Processing
The proof of equation (5.27) is given below.
Proof :
when n ® 2n, even numbered
By definition of DFT, the N-point DFT of x(n) is, samples of x(n) are selected.
N−1 when n ® 2n +1, odd numbered
X(k) = ∑ x(n) W kn
N
samples of x(n) are selected.
n=0

= ∑ x(n) W kn
N + ∑ x(n) WNkn ; k = 0, 1, 2 .....,N − 1
n = even n = odd

N N
−1 −1
2 2
= ∑ x(2n) WNk( 2n) + ∑ x(2n +1) W k( 2n +1)
N b g
..... 5.28
n= 0 n= 0

The phase factors in equation (5.28) can be modified as shown below.

k( 2 n ) kn

e
WNk( 2n) = e− j2π j N

k( 2n + 1)
e
= e− j2π j N/ 2

k2n
= W Nkn2
k kn k
.....(5.29)

WNk( 2n + 1) = e e− j2π j N = e e− j2π Nj e j

e− j2π N = e j e
e− j2π N 2 j
e− j2π N = WNkn2 WNk .....(5.30)

Using equations (5.29) and (5.30), the equation (5.28) can be written as,
N N
−1 −1
2 2
kn kn k
X( k) = ∑ x(2n)
n= 0
WN 2 +
n= 0
∑ x(2n +1) W N2 W
N
x(2n) = f1(n) and x(2n+1) = f2(n)
N N
−1 −1
2 2
kn k kn
= ∑ f (n) W
n= 0
1 N2 + W
N ∑ f (n) W
n= 0
2 N2 .....(5.31)

By definition of DFT the N/2 point DFT of f1(n) and f2(n) are given by,
N N
−1 −1
2 2
F1(k) = ∑ f (n) W
1
kn
N2 and F2 (n) = ∑ f (n) W2
kn
N2 .....(5.32)
n= 0 n= 0

Using equation (5.32) in equation(5.31) we get,

k
X(k) = F1(k) + WN F2 (k) , where k = 0, 1, 2, ....., N –1

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 the two N/4 point sequences and f2(n) would result in another two
N/4 point sequences.
Let the decimated N/4 point sequences of f1(n) be v11(n) and v12(n).

∴ v11 (n) = f1 (2n) ; for n = 0, 1, 2, ....., N − 1

4
v12 (n) = f1 (2 n + 1) ; for n = 0, 1, 2, ....., N − 1
4
Let the decimated N/4 point sequences of f2(n) be v21(n) and v22(n).
∴ v 21 (n) = f2 (2n) ; for n = 0, 1, 2 , ....., N − 1
4
v 22 (n) = f2 (2n + 1) ; for n = 0, 1, 2, ....., N −1
4

bg
Let, V11 k = N 4 point DFT of v11 n ; bg bg
V21 k = N 4 point DFT of v21 n bg
V12 bkg = N 4 point DFT of v b ng ; 12 V22 bkg = N 4 point DFT of v 22 b ng
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 24

Then like earlier analysis we can show that,

F1 (k) = V11 (k) + WNk 2 V12 (k) ; for k = 0, 1, 2, ....., N − 1 .....(5.33)

2
k
F2 (k) = V21 (k) + WN 2 V22 (k) ; for k = 0, 1, 2, ....., N −1 .....(5.34)
2
Hence the N/2 point DFTs are obtained from the results of N/4 point DFTs.
The decimation of the data sequence can be repeated again and again until the resulting sequences
are reduced to 2-point sequences.
5.7.1 8-Point DFT Using Radix-2 DIT FFT
The input sequence is 8-point sequence. Therefore, N = 8 = 23 = rm. Here, r = 2 and m = 3.
Therefore, the computation of 8-point DFT using radix-2 FFT, involves three stages of computation.
The given 8-point sequence is decimated to 2-point sequences. For each 2-point sequence, the 2-point DFT
is computed. From the results of 2-point DFT, the 4-point
DFT can be computed. From the results of 4-point DFT, Table 5.3
the 8-point DFT can be computed. Normal order Bit reversed order
Let the given sequence be x(0), x(1), x(2), x(3), x(0) x(000) x(0) x(000)
x(4),x(5), x(6), x(7), which consists of 8 samples. The x(1) x(001) x(4) x(100)
8-samples should be decimated into sequences of
2-samples. Before decimation they are arranged in bit
reversed order, as shown in table 5.3. x(2) x(010) x(2) x(010)
x(3) x(011) x(6) x(110)
The x(n) in bit reversed order is decimated into 4
numbers of 2-point sequences as shown below.
x(4) x(100) x(1) x(001)
Sequence-1 : {x(0), x(4)} x(5) x(101) x(5) x(101)
Sequence-2 : {x(2), x(6)}
Sequence-3 : {x(1), x(5)} x(6) x(110) x(3) x(011)
x(7) x(111) x(7) x(111)
Sequence-4 : {x(3), x(7)}
Using the decimated sequences as input the 8-point DFT is [Link] fig 5.1 shows the three
stages of computation of an 8-point DFT.

x (0)
C om pute
x(4) 2-point D FT C om bine X (0)
2-point D FT s
to X (1)
get 4-point
x (2) C om pute D FT X (2)
2-point D FT C om bine
x (6)
4-point
X (3)
D FT s to
get 8-point
x (1) X (4)
C om pute D FT
2-point D FT C om bine
x (5) X (5)
2-point D FT s
to X (6)
get 4-point
x (3)
C om pute D FT
X (7)
x (7) 2-point D FT

F ig 5.1 . T h ree sta g es o f co m p u ta tio n s in 8 -p o in t D F T .

5. 25 Digital Signal Processing
Let us examine the 8-point DFT of an 8-point sequence in detail. The 8-point sequence is decimated
into 4-point sequences and 2-point sequences as shown below.

Let x(n) = 8-point sequence

f1(n), f2(n) = 4-point sequences obtained from x(n)

v11(n), v12(n) = 2-point sequences obtained from f1(n)

v21(n), v22(n) = 2-point sequences obtained from f2(n).

The relations between the samples of various sequences are given below.

v11(0) = f1(0) = x(0) v21(0) = f2(0) = x(1)

v11(1) = f1(2) = x(4) v21(1) = f2(2) = x(5)

v12(0) = f1(1) = x(2) v22(0) = f2(1) = x(3)

v12(1) = f1(3) = x(6) v22(1) = f2(3) = x(7)

First Stage Computation

In the first stage of computation the two point DFTs of the 2-point sequences are computed.

Let, V11(k) = DFT{v11(n)}.

Using equation (5.26), the 2-point DFT of v11(n) is given by,

b g ∑ v b ng W
V11 k = 11
nk
2 ; for k = 0, 1
n = 0, 1

0
When k = 0; V11 ( k ) = V11 (0) = v11 ( 0) W2 + v11 (1) W20 = v11 (0) + v11 (1) = x( 0) + x(4)
0
When k = 1; V11 ( k ) = V11 (1) = v11 ( 0) W2 + v11 (1) W21 = v11 ( 0) − W20 v11 (1) = x(0) − W20 x(4)
0 1
j2 π × − j2 π ×
W20 = e 2 = e0 = 1 W21 = e 2 = e − jπ = (cos π − j sin π) = − 1 = − 1 × W20 = − W20

Let, V12(k) = DFT{v12(n)}.

Using equation (5.26), the 2-point DFT of v12(n) is given by,

V12 (k) = ∑ v12 (n) W2nk ; for k = 0, 1

n = 0, 1

0 0
When k = 0; V12 ( k ) = V12 (0) = v12 (0) W2 + v12 (1) W2 = v12 (0) + v12 (1) = x( 2) + x( 6)
0 0 0
When k = 1; V12 ( k ) = V12 (1) = v12 ( 0) W2 + v12 (1) W21 = v12 (0) − W2 v12 (1) = x(2) − W2 x(6)
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 26
Let, V21(k) =DFT{v21(n)}.

Using equation (5.26), the 2-point DFT of v21(n) is given by,

V21 (k) = ∑ v21(n) W2nk ; for k = 0, 1

n = 0, 1

0
When k = 0; V21 ( k ) = V21 (0) = v21 ( 0) W2 + v21 (1) W20 = v21 (0) + v21 (1) = x(1) + x(5)
0
When k = 1; V21 ( k ) = V21(1) = v21 (0) W2 + v21 (1) W21 = v21 (0) − W20 v21(1) = x(1) − W20x(5)

Let, V22(k) = DFT{v22(n)}.

Using equation (5.26), the 2-point DFT of v22(n) is given by,

V22 (k) = ∑ v22 (n) W2nk ; for k = 0, 1.

n = 0, 1

0
When k = 0 ; V22 ( k ) = V22 (0) = v 22 ( 0) W2 + v22 (1) W20 = v22 ( 0) + v 22 (1) = x( 3) + x( 7)
0
When k = 1; V22 ( k ) = V22 (1) = v22 ( 0) W2 + v 22 (1) W21 = v22 ( 0) − W20 v 22 (1) = x( 3) − W20 x( 7)

Second Stage Computation

In the second stage of computation the 4-point DFTs are computed using the results of first stage as
input. Let, F1(k) = DFT{f1(n)}. The 4-point DFT of f1(n) can be computed using equation (5.33).

∴ F1 (k) = V11 ( k ) + W4k V12 (k) ; for k = 0, 1, 2, 3. V11(k) and V12(k) are periodic
with periodicity of 2 samples.
When k = 0; F1 ( k ) = F1 (0) = V11 ( 0) + W40 V12 (0) \ V11(k + 2) = V11(k)
V12(k + 2) = V12(k)
When k = 1; F1 ( k ) = F1 (1) = V11 (1) + W41 V12 (1)
When k = 2; F1 ( k ) = F1 (2) = V11 ( 2) + W42 V12 (2) = V11 (0) − W40 V12 (0)
When k = 3; F1 ( k ) = F1 (3) = V11 ( 3) + W43 V12 (3) = V11 (1) − W41 V12 (1)
2
− j2 π ×
W42 = e 4 = e − jπ = (cos π − j sin π ) = −1 = −1 × W40 = − W40

3 2 1 1
− j2 π × − j2 π × − j2 π × − j2 π ×
W43 = e 4 =e 4 e 4 = e − jπ e 4 = (cos π − j sin π ) W41 = −1 × W41 = − W41

Let, F2(k) = DFT{f2(n)}. The 4-point DFT of f2(n) can be computed using equation (5.34).

∴ F2 (k) = V21 ( k ) + W4k V22 (k) ; for k = 0, 1, 2, 3. V21(k) and V22(k) are periodic
with periodicity of 2 samples.
When k = 0; F2 ( k ) = F2 (0) = V21 ( 0) + W40 V22 (0) \ V21(k + 2) = V21(k)
V22(k + 2) = V22(k)
When k = 1; F2 ( k ) = F2 (1) = V21 (1) + W41 V22 (1)
When k = 2; F2 ( k ) = F2 (2) = V21 ( 2) + W42 V22 (2) = V21 ( 0) − W40 V22 (0)
When k = 3; F2 ( k ) = F2 (3) = V21 ( 3) + W43 V22 (3) = V21 (1) − W41 V22 (1)
5. 27 Digital Signal Processing
Third Stage Computation

In the third stage of computation the 8-point DFTs are computed using the results of second stage as
inputs.
Let, X(k) = DFT{X(n)}. The 8-point DFT of x(n) can be computed using equation (5.27).
∴ X( k ) = F1 ( k ) + W8k F2 (k) ; for k = 0, 1, 2, 3, 4, 5, 6, 7 F1(k) and F2(k) are periodic with
periodicity of 4 samples.
When k = 0; X( k ) = X( 0) = F1 ( 0) + W80 F2 (0) \ F1(k + 4) = F1(k)
When k = 1; X( k ) = X(1) = F1 (1) + W81 F2 (1) F2(k + 4) = F2(k)
When k = 2; X( k ) = X( 2) = F1 ( 2) + W82 F2 ( 2)
When k = 3; X( k ) = X( 3) = F1 (3) + W83 F2 ( 3)
When k = 4; X( k ) = X( 4) = F1 ( 4) + W84 F2 (4) = F1 (0) − W80 F2 ( 0) − j2 π ×
4
W84 = e 8 = e − jπ
When k = 5; X( k ) = X(5) = F1 (5) + W85 F2 (5) = F1 (1) − W81 F2 (1)
= (cos π − j sin π)
When k = 6; X( k ) = X( 6) = F1 ( 6) + W86 F2 (6) = F1 (2) − W82 F2 ( 2)
= −1
When k = 7; X( k ) = X( 7) = F1 ( 7) + W87 F2 (7) = F1 (3) − W83 F2 ( 3)

W84 = W84 × W80 = − W80 W85 = W84 × W81 = − W81 W86 = W84 × W82 = − W82 W87 = W84 × W83 = −W83

5.7.2 Flow Graph for 8-Point DFT using Radix-2 DIT FFT
If we observe the basic computation performed at every stage of radix-2 DIT FFT in previous section,
we can arrive at the following conclusion.
1. In each computation two complex numbers "a" and "b" are considered.

2. The complex number "b" is multiplied by a phase factor "WNk " .

k
3. The product "bWN " is added to complex number "a" to form new complex number "A".
k
4. The product "bWN " 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 Fig 5.2. (For detailed discussion on signal flow a
1
A = a + bW N
k

graph, refer Chapter 2, Section 2.6.2). 1

The signal flow graph is also called butterfly diagram since it k 1

WN k
resembles a butterfly. In radix-2 FFT, N/2 butterflies per stage are b B = a − bW N
k −1
bW N
required to represent the computational process. The butterfly
diagram used to compute the 8-point DFT via radix-2 DIT FFT can be F ig 5.2 : B a sic b u tterfly o r flo w grap h
arrived as shown below, using the computations shown in previous o f D IT ra d ix-2 FF T.
section.
The sequence x(n) is arranged in bit reversed order and then decimated into two sample sequences as
shown below.
x(0) x(2) x(1) x(3)
x(4) x(6) x(5) x(7)
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 28

Flow Graph or (Butterfly Diagram) for First Stage of Computation

Input of first stage

[x(n) in bit reversed order] Output of first stage

1 1
x(0) x(0) + W 02 x(4) = V11(0)
1
1
W20
x(4) x(0) − W20 x(4) = V11(1)
−1
x(2) 1 1 x(2) + W20 x(6) = V12 (0)
1
1
W20
x(6) x(2) − W20 x(6) = V12 (1)
−1
1 1
x(1) x(1) + W20 x(5) = V21(0)
1
1
W20
x(5) x(1) − W20 x(5) = V21(1)
−1
1 1
x(3) x(3) + W20 x(7) = V22 (0)
1
W20 1
x(7) x(3) − W20 x(7) = V22 (1)
−1

F ig 5 .3 : F irst sta g e o f flo w g ra p h (o r b u tterfly d ia g ra m ) fo r 8 -p o in t D F T v ia rad ix-2 D IT F F T.

Flow Graph (or Butterfly Diagram) for Second Stage of Computation

Output of first stage as

Input of second stage Output of second stage
1 1
V11(0) V11 0 + W40 V12 0 = F1 0
1
1 1 1
V11(1) V11 1 + W4 V12 1 = F1 1
1

W40 -1
1 0
V12(0) V11 0 − W4 V12 0 = F1 2

W41 -1 1
V12(1) V11 1 − W4 V12 1 = F1 3

1 1 0
V21(0) V21 0 + W4 V22 0 = F2 0
1
1 1 1
V21(1) V21 1 + W4 V22 1 = F2 1
1

W40 1
-1 0
V22(0) V21 0 − W4 V22 0 = F2 2

1
W41 -1 1
V22(1) V21 1 − W4 V22 1 = F2 3

F ig 5.4 : S ec o nd sta g e o f flo w g ra p h ( o r bu tterfly d iag ram ) fo r 8 -po in t D F T v ia ra dix-2 D IT F F T.

5. 29 Digital Signal Processing
Flow Graph (or Butterfly Diagram) for Third Stage of Computation

O utput of s econd stage as

O utput of third stage
Input of third s tage
[X (k)in norm al ord er]
1 1
F 1 (0) F1(0) + W 80 F 2 (0) = X (0)

1
1 1
F 1 (1) F1 (1) + W 8 F2 (1) = X (1)
1
1
1
F 1 (2) F1(2) + W 82 F 2 (2) = X (2)
1
1
1
F 1 (3) F1 (3) + W 83 F 2 (3) = X (3)
0 1
W 8
F 2 (0) F1(0) − W 80 F 2 (0) = X (4)

1
W 8 1
F 2 (1) F1 (1) − W 8 F2 (1) = X (5)
2
W 8
F 2 (2) F1(2) − W 82 F 2 (2) = X (6)
3
W8
F 2 (3) F1 (3) − W 83 F2 (3) = X (7)

F ig 5 .5 : T hird sta g e o f flo w g ra p h ( o r b u tterfly d iag ra m ) for 8 -p o in t D F T v ia rad ix-2 D IT F F T.

The Combined Flow Graph (or Butterfly Diagram) of All the Three Stages of Computation

1 1 1 1 1 1
x (0) X (0)
1 1
0
W2 1 1
1 1 1
x (4) X (1)
−1 1 1
0
1 W4 1 1
1 −1 1
x (2) X (2)
1
1 1 1
0
W2 1 W4
1 1
x (6) X (3)
−1 −1
1
0
1 W8 1
1 1 1
x (1) X (4)
1 −1
0 1 1
W2 1 W8 1
1 1 −1
x (5) X (5)
−1 1
0 2
W4 1 W8 1 −1
1 1 −1
x (3) X (6)
0
1 3
1 1
W2 1 W4 −1 W8 1 −1
x (7) X (7)
−1

F ig 5.6 : T h e flo w g ra p h (o r b u tterfly d iagra m ) fo r 8 -po in t D F T v ia ra dix-2 D IT F F T.

5.8 Decimation in Frequency (DIF) Radix-2 FFT

In decimation in frequency algorithm the frequency domain sequence X(k) is decimated, (but in
decimation in time algorithm, the time domain sequence x(n) is decimated).
In this algorithm, 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.
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 30
Thus we get 4 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 forming N/2 point sequences, N/4 point sequences, etc., are obtained by
decimation of frequency domain sequences. Hence this method is called DIF. For example the N-point
frequency domain sequence X(k) can be decimated to two numbers of N/2 point frequency domain sequences
G1(k) and G2(k). The G1(k) and G2(k) defines new time domain sequences g1(n) and g2(n) respectively, whose
samples are obtained from x(n).
It can be shown that the N-point DFT of x(n) can be realized from two numbers of
N/2 point DFTs. The N/2 point DFTs can be realized from two numbers of N/4 point DFTs and so on. The
decimation continues upto 2-point DFTs.
Let x(n) and X(k) be N-point DFT pair.
Let G1(k) and G2(k) be two numbers of N/2 point sequences obtained by the decimation of X(k).
Let G1(k) be N/2 point DFT of g 1(n), and G2(k) be N/2 point DFT of g2(n).
Now, the N-point DFT X(k) can be obtained from the two numbers of N/2 point DFTs G1(k) and G2(k),
as shown below.
X(k)½k = even = G1(k)
X(k)½k = odd = G2(k)
Proof :

By definition of DFT, the N-point DFT of x(n) is,

kN 2π kN
N −j
N−1 2
−1
N−1 WN2 = e N 2 = e− jπk
X(k) = ∑
n=0
x(n) WNkn = ∑
n=0
x(n) WNkn + ∑ N
x(n) WNkn
e j = b−1g
= e− jπ
k k

n=
2
N N N N
−1 −1 FG N IJ −1 −1
kN

∑ xFH n + N2 IK W FH IK
2 2 k n+ 2 2
H K x n + N WNkn WN2
= ∑ x(n) W
n=0
kn
N +
n=0
N
2
= ∑ x(n) W
n=0
kn
N + ∑
n=0
2
N N
−1 −1

∑ LMNx(n) W FH IK OP ∑ LMNx(n) + b−1g xFH n + N2 IK OPQ W

2 2
k
= kn
+ (−1)k x n + N WNkn = kn

n=0
N
2 Q n=0
N

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

X(k) k = even = X(2k) ; for k = 0, 1, 2, ...., N − 1
N
2 FH IK
g1(n) = x(n) + x n + N ; for n = 0, 1, 2,... N –1
−1 2 2
∑ LMNx(n) + (−1) FH IK OP W
2
= 2k
x n+ N 2kn
bg
G1 k is N point DFT of g1(n).
n=0
2 Q N
2
N N
−1 −1
= ∑ LMx(n) + xFH n + N IK OP W
2 2

N
n=0
2 Q
kn
N2 ∴ G1 k =b g ∑ g bng W 1
kn
N2 ; for k = 0, 1, 2,.. N –1
2
n=0
N
−1
2
= ∑ g (n) W
1
kn
N2 = G1(k)
n=0
5. 31 Digital Signal Processing

X(k) k = odd = X(2k + 1) ; for k = 0, 1, 2, ....., N –1

2
N
−1

=
2

∑ LMx(n) + (−1) xFH n + N IK OP W

(2k + 1) (2k + 1)n

n=0N 2 Q N

N
−1

∑ LMNx(n) − xFH n + N2 IK OPQ W W g (n) = F x(n) − xF n + N I I W ; for n = 0, 1, 2, .....,

2
2kn n
= N N n N –1
n=0
N
H H 2 KK 2 N
2
−1

∑ LNMx(n) − xFH n + N2 IK OQP W W

2 N
n
G (k) is kn
point DFT of g (n).
= N N2 2 2
n=0
2
N N
−1 −1
2 2
= ∑ g (n) W Nkn2 = G2 (k) ∴ G2(k) = ∑ g2(n) W Nkn2 ; for k = 0, 1, 2, ....., N –1
2
n=0
2
n=0

In the next stage of decimation the N/2 point frequency domain sequence G1(k) is decimated into two
numbers of N/4 point sequences D11(k) and D12(k), and G2(k) is decimated into two numbers of N/4 point
sequences D21(k) and D22(k).
Let D 11(k) and D12(k) be two numbers of N/4 point sequences obtained by the decimation of G1(k).
Let D11(k) be N/4 point DFT of d 11(n), and D12(k) be N/4 point DFT of d12(n).
Let D 21(k) and D22(k) be two numbers of N/4 point sequences obtained by the decimation of G2(k).
Let D21(k) be N/4 point DFT of d 21(n), and D22(k) be N/4 point DFT of d22(n).
Now, N/2 point DFTs can be obtained from two numbers of N/4 point DFTs as shown below.
G1(k)½k = even = D11(k)
G1(k)½k = odd = D12(k)
G2(k)½k = even = D21(k)
G2(k)½k = odd = D22(k)
Proof :

By definition of DFT, the N/2 point DFT of G1(k) is,

N N N
−1 −1 −1
2 4 2
G1(k) = ∑ g (n)
n=0
1 W Nkn2 =
n=0
∑ g (n) 1 W Nkn2 + ∑ g (n) W
N
1
kn
N2
n=
4
N N N N
−1 −1
G F N IJ −1 −1
N

∑ g FH n + N4 IK W H FH IK
4 4 k n+ 4 4
= ∑ g (n) K g1 n + N W Nkn2 W N 42
k

n=0
1 W Nkn2 +
n=0
1 N2
4
= ∑
n=0
g1(n) W Nkn2 + ∑
n=0
4
N
L4
−1
O
kn
= ∑ Mg (n) + W g FH n + N IK P W
4 kn
kN
−j
2 π kN
W N2 = e N 2 = e − jπk
MN
n=0
1
4 PQ
N2 1 N2
k
N
−1
e j = b −1g
= e − jπ
k

= ∑ LMg (n) + (−1) g FH n + N IK OP W

4
k kn
N
n=0
1
4 Q 1 N2

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

Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 32

G1(k) k = even = G1(2k) ; for k = 0, 1, 2, ....., N − 1

4
d11(n) = g1(n) + g1 n + N FH IK
4
N
−1
D11(k) is N point DFT of d11(n).
∑ LMNg (n) + (−1) g FH n + N4 IK OPQ W
4
= 1
2k
1
2kn
N2
4
n=0 N
−1
N N 4
−1 −1

= ∑ LMg (n) + g FH n + N IK OP W
4
= ∑ d (n) W kn
4
kn
= D11(k)
∴ D11(k) =
n=0
∑d 11(n) W Nkn4
N 1
4 Q 1 N4 11 N4

(n) = LMg b ng − g FH n + N IK OP W
n=0 n=0
n
d12
G1(k) k = odd = G1(2k + 1) ; for k = 0, 1, 2,....., N − 1
N 1 1
4 Q N2

4
D12(k) is N point DFT of d12(n).
N
−1 4
=
4

∑ LMg (n) + (−1) (2k +1) FH

g1 n + N IK OP W (2k +1)n N
−1
n=0 N1
4 Q N2
∴ D12(k) =
4

∑d 12(n) WNkn4
N N
−1 −1 n=0

=
4

∑ LMg (n) − g FH n + N IK OP W n
W Nkn4 =
4

∑ d12(n) W Nkn4 = D12(k)

n=0 N1
4 Q
1 N/2
n=0

d21(n) = g2(n) + g2 n + N FH IK
Similarly the N/2 point sequence G 2 (k) can be decimated 4
into two numbers of N/4 point sequences. D21(k) is N point DFT of d21(n).
4
G2(k) k = even = G2(2k) ; for k = 0, 1, 2, ....., N − 1 N
4
−1
4
N
4
−1
∴ D21(k) = d21(n) WNkn4 ∑
n=0
= ∑d 21(n) WNkn4 = D21(k)
LM
n=0
d22 (n) = g 2 (n) − g 2 n + N FH IK OP W n
N 4 Q N 2

G2(k) k = odd = G2(2k + 1) ; for k = 0, 1, 2, ....., N − 1

4 D22 (k) is N point DFT of d 22 (n).
N 4
−1
4 N
= ∑d 22(n) W Nkn4 = D22(k) 4
− 1

n=0 ∴ D22 (k) = ∑d

n = 0
22 (n) W Nkn4

The decimation of the frequency domain sequence can be continued until the resulting sequence are
reduced to 2-point sequences. The entire process of decimation involves, m stages of decimation where
m = log2N. The computation of the N-point DFT via the decimation in frequency FFT algorithm requires
(N/2)log2N complex multiplications and N log2N complex additions. (i.e., the total number of computations
remains same in both DIT and DIF).
5.8.1 8-point DFT Using Radix-2 DIF FFT
The DIF computations for an eight sequence is discussed in detail in this section. Let x(n) be an
8-point sequence. Therefore N = 8 = 23 = rm. Here, r = 2 and m = 3. Therefore, the computation of 8-point DFT
using radix-2 FFT involves three stages of computation.
The samples of x(n) are,
x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)
First Stage Computation
In the first stage of computation, two numbers of 4-point sequences g1(n) and g2(n) are obtained from
x(n) as shown below.
LM
g1 (n) = x(n) + x n + N e jOQP = x(n) + x(n + 4) ;for n = 0, 1, 2, 3
N 2
5. 33 Digital Signal Processing
When n = 0; g1(n) = g1(0) = x(0) + x(4)
When n = 1; g1(n) = g1(1) = x(1) + x(5)
When n = 2; g1(n) = g1(2) = x(2) + x(6)
When n = 3; g1(n) = g1(3) = x(3) + x(7)
LM
g 2 (n) = x(n) – x n + N
e jOPQ Wn
= x(n) – x(n + 4) W8n ; for n = 0, 1, 2, 3
N 2 N

When n = 0; g2 (n) = g2 (0) = [x(0) − x(4)] W80

When n = 1; g2 (n) = g2 (1) = [x(1) − x(5)] W81
When n = 2; g2 (n) = g2 (2) = [x(2) − x(6)] W82
When n = 3; g2 (n) = g2 (3) = [x(3) − x(7)] W83
Second Stage Computation
In the second stage of computation, 2 numbers of 2-point sequences d11(n) and d12(n) are generated
from the samples of g1(n), and another 2 numbers of 2-point sequences d21(n) and d22(n) are generated from
the samples of g2(n), as shown below.

b g
d11 (n) = g1 (n) + g1 n + N 4 = g1 (n) + g1 (n + 2) ; for n = 0, 1

When n = 0; d11 (n) = d11 (0) = g1 (0) + g1 (2)

When n = 1; d11 (n) = d11 (1) = g1 (1) + g1 (3)

d12 (n) = g1 (n) − g1 (n + N 4) WNn 2 = g1 (n) − g1 (n − 2) W4n ; for n = 0, 1

When n = 0; d12 ( n) = d12 ( 0) = [g1 ( 0) − g1 ( 2)] W40

When n = 1; d12 ( n) = d12 (1) = [g1 (1) − g1 (3)] W41

d 21 (n) = g2 (n) + g 2 (n + N 4) = g2 (n) + g 2 (n + 2) ; for n = 0, 1

When n = 0; d 21 (n) = d 21(0) = [g2 (0) + g2 (2)]

When n = 1; d 21 (n) = d 21 (1) = [g2 (1) + g2 (3)]

d 22 (n) = g2 (n) − g2 (n + N 4) WNn 2 = g2 (n) − g2 (n + 2) W4n ; for n = 0, 1

When n = 0; d 22 (n) = d 22 (0) = [g 2 (0) − g 2 (2)] W40

When n = 1; d 22 (n) = d 22 (1) = [g2 (1) − g2 (3)] W41

Third Stage Computation

In the third stage of computation, 2-point DFTs of the 2-point sequences d11(n), d12(n), d21(n) and
d22(n) are computed.
The 2-point DFT of the 2-point sequence d11(n) is computed as shown below.
1
l q
DFT d11 (n) = D11 (k) = ∑ d11(n) W2kn ; for k = 0, 1
n=0
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 34
1
W20 = 1
When k = 0; D11 (0) = ∑ d11(n) W20 = d11(0) + d11(1)
n=0
1
W21 = −1 = −1 × W20
When k = 1 ; D11 (1) = ∑ d11 (n) W2n = d11 (0) W20 + d11 (1) W21
n=0

= d11 (0) W20 + d11 (1) W21 W20 = d11 (0) − d11 (1) W20

Similarly the 2-point DFTs of the 2-point sequences d12(n), d21(n) and d22(n) are computed and the
results are given below.
D11 ( 0) = d11 ( 0) + d11 (1)
D11 (1) = d11 ( 0) − d11 (1) W20
D12 (0) = d12 (0) + d12 (1)
D12 (1) = d12 (0) − d12 (1) W20
D21 (0) = d 21 (0) + d 21 (1)
D21 (1) = d 21 (0) − d 21 (1) W20
D22 (0) = d 22 (0) + d 22 (1)
D22 (1) = d 22 (0) − d 22 (1) W20

Combining the Three Stages of Computation

The final output Dij(k) gives the X(k). The relation can be obtained as shown below.
X(2k) = G1(k) ; k = 0,1,2,3 X(2k + 1) = G2(k) ; k = 0, 1, 2, 3
\ X(0) = G1(0) \ X(1) = G2(0)
X(2) = G1(1) X(3) = G2(1)
X(4) = G1(2) X(5) = G2(2)
X(6) = G1(3) X(7) = G2(3)
G1 (2k) = D11 (k) ; k = 0, 1 G1 (2k + 1) = D12 (k) ; k = 0, 1
∴ G1 (0) = D11 (0) ∴ G1 (1) = D12 (0)
G1 (2) = D11 (1) G1 (3) = D11 (1)

G 2 (2k) = D21 (k) ; k = 0, 1 G 2 (2k +1) = D22 (k) ; k = 0, 1

∴ G 2 (0) = D21 (0) bg
∴ G 2 1 = D22 0 bg
G 2 (2) = D21 (1) bg
G 2 3 = D22 1 bg
From above relations we get,
D11(0) = G1(0) = X(0) D21(0) = G2(0) = X(1)

D11(1) = G1(2) = X(4) D21(1) = G2(2) = X(5)

D12(0) = G1(1) = X(2) D22(0) = G2(1) = X(3)

D12(1) = G1(3) = X(6) D22(1) = G2(3) = X(7)

From the above we observe that the output is in bit reversed order. In radix-2 DIF FFT, the input is in
normal order the output will be in bit reversed order.
5. 35 Digital Signal Processing
5.8.2 Flow Graph For 8-point DFT using Radix-2 DIF FFT
If we observe the basic computation performed at every stage of radix-2 DIF FFT in previous section,
we can arrive at the following conclusion.

1. In each computation two complex numbers "a" and "b" are considered.

2. The sum of the two complex numbers is computed which forms a new complex number "A".

3. Then subtract complex number "b" from "a" to get the term "a-b". The difference term "a-b" is
multiplied with the phase factor or twiddle factor "WNk " to form a new complex number "B".

The above basic computation can be expressed by a signal flow graph shown in Fig 5.7. (For detailed
discussion on signal flow graph, refer Chapter 2, Section 2.6.2).
1 a+ b
A = a+ b
1

1 k
WN k
b B = ( a − b)W N
−1 a −b

F ig 5.7 : B a sic b u tterfly o r flo w grap h

o f D IF ra d ix-2 FF T.
The signal flow graph is also called butterfly diagram since it resembles a butterfly. In radix-2 FFT,
N/2 butterflies per stage are required to represent the computational process. The butterfly diagram used to
compute the 8-point DFT via radix-2 DIF FFT can be arrived as shown below, using the computations shown
in previous section.
Flow Graph (or Butterfly Diagram) for First Stage of Computation

Input of first stage Output of first stage

[x(n) in normal order]

1 1
x(0) x(0) + x(4) = g1(0)
1
1 1
x(1) x(1) + x(5) = g1(1)
1
1 1
x(2) x(2) + x(6) = g1(2)
1
1 1
x(3) x(3) + x(7) = g1(3)
1
1 0
W8
0
x(4) [x(0) − x(4)] W8 = g 2 (0)
−1
1 1
−1 W8
1
x(5) [x(1) − x(5)] W8 = g 2 (1)

1 2
−1 W8 2
x(6) [x(2) − x(6)] W8 = g 2 (2)
1 3
−1 W8
3
x(7) [x(3) − x(7)] W8 = g 2 (3)

F ig 5 .8 : F irst sta g e o f flo w g ra p h (o r b u tterfly d ia g ra m ) fo r 8 -p o in t D FT v ia rad ix-2 D IF F F T.

Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 36
Flowgraph or Butterfly Diagram for Second Stage of Computation

Output of first stage as

Output of second stage
input of second stage.
1 1
g1(0) g1 0 + g1 2 = d11 0
1
1 1
g1(1) g1 1 + g1 3 = d11 1
1
1 0
W4 0
g1(2) [g1 0 − g1 2 ]W = d12 0
−1 4
1
1 W4 1
g1(3) [g1 1 − g1 3 ]W = d12 1
4
−1

1 1
g2(0) g2 0 + g2 2 = d 21 0

1
1 1
g2(1) g2 1 + g2 3 = d 21 1
1
1 0
W4
−1 [g2 0 − g2 2 ]W
0
= d 22 0
g2(2) 4
1 1
W4 1
g2(3) [g2 1 − g2 3 ]W = d 22 1
−1 4

F ig 5.9 : S e co n d sta g e of flow g ra ph (or b u tterfly d ia g ra m ) fo r 8 -p o in t D F T via ra d ix -2 D IF F F T.

Flow Graph( or Butterfly Diagram) for Third Stage of Computation

O utput of s econd stage as O utput o f third stage

input of third stage [X (k ) in bit rev ersed order]
1 1
d 1 1 (0) d 1 1(0) + d 11 (1) = D 11(0) = G 1(0) = X (0)
1

1 0
W2
d 1 1(1) [d 11 (0) − d 11 (1)]W 20 = D 11 (1) = G 1(2) = X (4)
−1
1 1
d 1 2 (0) d 12 (0) + d 12 (1) = D 12 (0) = G 1 (1) = X (2)
1
1 0
W2
d 1 2 (1) 0
[d 12 (0) − d 1 2 (1)]W 2 = D 12 (1) = G 1(3) = X (6)
−1
1 1
d 2 1 (0) d 21 (0) + d 21 (1) = D 21 (0) = G 2 (0) = X (1)
1

1 0
W2
d 2 1 (1) [d 2 1(0) − d 21 (1)]W 20 = D 21 (1) = G 2 (2) = X (5)
−1
1 1
d 2 2 (0) d 2 2 (0) + d 22 (1) = D 2 2 (0) = G 2 (1) = X(3)
1
0
1 W2
d 2 2 (1) [d 2 2 (0) − d 22 (1)]W 20 = D 22 (1) = G 2 (3) = X (7)
−1

F ig 5.1 0 : T hird sta ge o f flo w g ra p h (o r b u tt erfly d ia g ra m ) for 8 -p oin t D F T v ia ra dix-2 D IF F F T.

5. 37 Digital Signal Processing
The Combined Flow Graph (or Butterfly Diagram) of All the Three Stages of Computation
1 1 1 1 1 1
x(0) X(0)
1
1 0
1 1 W2
1 1 1
x(1) X(4)
1 1 −1
1 0
1 W4
1 1 1
x(2) X(2)
1 −1 1
1 1
1 0
W4 W2
x(3) 1 X(6)
1 −1 −1
1
0
W8 1 1 1
x(4) X(1)
−1 1 1
1 0
W8 1 W2
−1 1 1
x(5) X(5)
1 −1
2
1 0
W8 W4
−1 −1 1 1
x(6) X(3)
1
3 1 1 0
−1
W8 W4 1 W2
x(7) x(7)
−1 −1
F ig 5 .11 : T h e flo w g ra p h (o r b u tterfly d ia g ra m ) fo r 8-p o int D F T via rad ix-2 D IF F F T.

5.8.3 Comparison of DIT and DIF Radix-2 FFT

Differences in DIT and DIF
l In DIT the time domain sequence is decimated, whereas in DIF the frequency domain sequence
is decimated.
l In DIT the input should be in bit-reversed order and the output will be in normal order.
For DIF the reverse is true, i.e., input is normal order, while output is bit reversed.
l Considering the butterfly diagram, in DIT the complex multiplication takes place before the
add-subtract operation, whereas in DIF the complex multiplication takes place after the add-
subtract operation.
Similarities in DIT and DIF
l For both the algorithms the value of N should be such that, N = 2m, and there will be m stages
of butterfly computations, with N/2 butterfly per stage.
l Both algorithms involve same number of operations. The total number of complex additions
are Nlog2N and total number of complex multiplications are (N/2) log2N.
l Both algorithms require bit reversal at some place during computation.
5.9 Computation of Inverse DFT Using FFT
Let, x(n) and X(k) be N-point DFT pair.
Now by the definition of inverse DFT,
N−1 j2 πnk
1
x(n) =
N ∑ X(k) e N ; for n = 0, 1, 2, ....., N − 1
k=0

F − j2 πnk ∗I
1N 1
−
1N 1
−
∗ 1 LM Xbkg W
N−1
∗ O
=
Nk=0
X(k) e∑ GH N
JK = ∑ b g eWNnk j
N k=0
Xk =
N MN ∑ e
nk
N j PPQ .....(5.35)
k=0
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 38
In equation (5.35), the expression inside the bracket is similar to that of DFT computation of a
sequence, with following differences.
1. The summation index is k instead of n.
2. The input sequence is X(k) instead of x(n).
3. 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
phase factors. Also from equation (5.35) it is observed that the output of FFT computation should be divided
by N to get x(n).
The following procedure can be followed 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.

Example 5.5
An 8-point sequence is given by x(n) = {2, 1, 2, 1, 1, 2, 1, 2}. Compute 8-point DFT of x(n) by
a) radix-2 DIT-FFT and b) radix-2 DIF-FFT. Also sketch the magnitude and phase spectrum.

Solution
a) 8-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 1 −2 = −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
The 8-point DFT by radix-2 FFT involve 3 stages of computation with
4-butterfly computations in each stage. The sequence rearranged in the bit F ig 1 : B u tterfly d ia gram fo r
reversed order forms the input to the first stage. For other stages of computation first sta ge o f ra d ix -2 D IT F F T.
the output of previous stage will be the input for current stage.
First stage computation
The input sequence of first stage computation = { 2, 1, 2, 1, 1, 2, 1, 2} The phase factor involved in first
The butterfly computations of first stage are shown in fig 1. stage of computation is W20 .
Since, W20 =1, it is not considered
for computation.

The output sequence of first stage of computation = { 3, 1, 3, 1, 3, –1, 3, –1 }

5. 39 Digital Signal Processing
Second stage computation
The input sequence to second stage computation = { 3, 1, 3, 1, 3, –1, 3, –1 }
The phase factors involved in second stage computation are W40 and W41 .
1 1
3 3+3=6
The butterfly computations of second stage are shown in fig 2.
1
1 1
1 1+ 1( −j)= 1 −j
1
1
0 1 -1
− j 2π × 3 3 −3 = 0
W40 = e 4 = e0 = 1 1
−j -1
1 π 1 1 −1( −j)= 1+ j
− j2π × −j ×
W41 =e 4 =e 2
1 1
3 3+3=6
F −π IJ + j sinFG −π IJ
= cosG 1 1
1
H 2K H 2K −1
1
−1+ ( −1)( −j)= −1 +j

= −j 1 1
-1 3 −3 = 0
3
1
−j -1
−1 −1 −( −1)( −j)= −1 −j

The output sequence of second

= {6, 1–j, 0, 1+j, 6, –1+j, 0, –1–j} F ig 2 : B u tterfly d iag ra m fo r
stage of computation seco n d sta g e o f ra d ix-2 D IT F F T.
Third stage 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 W80 , W81 , W82 and W83.

The butterfly computations of third stage are shown in fig 3.

0
− j 2π ×
W80 = e 8 = e0 = 1
1 π
W81 = e
− j2 π ×
8 =e
−j ×
4 = cos
FG −π IJ + j sinFG −π IJ = 1 − j 1
H 4K H 4K 2 2
2 π
W82 = e
− j2 π × −j × F
= cosG
−π I F −π I
8 =e 2
H 2 JK + j sinGH 2 JK = −j
3 3π
W83 = e
− j 2π ×
8 =e
−j ×
4 F −3π IJ + j sinFG −3π IJ = − 1 − j
= cosG
1
H4K H4K 2 2

1
6 6 + 6 = 12 = X(0)

1− j
1 F 1 − j 1 I = 1− j − F
1 + j 1 + j 1 + 1 = 1 + j −1 + 2 I = 1 + j0 . 414 = X(1)
(1 − j) + (−1 + j) GH 2 2 JK 2 2 2 2
GH
2
JK
1 0 + 0 × ( −j) = 0 = X(2)
0

1 F I
(1 + j) + (−1 − j) − 1 − j 1 = 1 + j + 1 + j 1 + j 1 − 1 = 1 + j 1 + 2
F I = 1 + j2 . 414 = X(3)
1+j
2
GH 2
JK 2 2 2 2 2
GH JK
1
6 6 − 6 = 0 = X( 4)
1 −1
−j 1
2 2 F 1 − j 1 I = 1 − j − F− 1 +j 1 +j 1 + 1
I = 1 − jF1 + 2 I = 1 − j2 . 414 = X(5)
−1 + j
−1
(1 − j) − ( −1 + j) GH 2 2 JK GH 2 2 2 2
JK GH 2 JK
−j
0 0 − 0 × (−j) = 0 = X(6)
1 1 −1
− −j
2 2 1 1 1 +j 1 +j 1 − 1
−1− j (1 + j) − ( −1 − j) GH
− −j JK = 1+ j − GH JK = 1+ j 1− 2 GH JK = 1 − j0 . 414 = X(7)
−1 2 2 2 2 2 2 2

F ig 3 : B u tte rfly d ia gram for third sta ge o f ra d ix-2 D IT F F T o f X (k ) .

Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 40
The output sequence of third |UV = { 12, 1 + j0.414, 0 , 1+ j2.414, 0, 1 − j2.414, 0, 1 − j0.414 }
stage of computation |W
The output sequence of third stage of computation is the 8-point DFT of the given sequence in normal
order.

∴ DFT {x(n)} = X(k) = { 12, 1 + j0.414, 0, 1+ j2.414, 0, 1 − j2.414, 0, 1 − j0.414 }

b) 8-point DFT by Radix-2 DIF-FFT

For 8-point DFT by radix-2 FFT we require 3-stages of computation with 4-butterfly computation in each
stage. The given sequence is the input to first stage. For other stages of computations, the output of previous stage
will be the input for current stage.

First stage computation

The input sequence for first stage of computation = { 2, 1, 2, 1, 1, 2, 1, 2 }
The phase factors involved in first stage computation are W80 , W81 , W82 and W83.

The butterfly computations of first stage are shown in fig 4.

0
− j2π ×
W80 = e 8 =1
1 π
W81 = e
− j2π ×
8 =e
−j
4 FG π IJ + jsinFG − π IJ = 1 − j 1
= cos −
H 4K H 4K 2 2
2 π
W82 = e
− j2π ×
8 =e
−j
2 F πI F πI
= cosG − J + jsinG − J = − j
H 2K H 2K
3 3π
W83 = e
− j2π ×
8 =e
−j
4 F 3π IJ + jsinFG − 3π IJ = − 1 −
= cosG − j
1
H 4K H 4K 2 2

1 1
x(0) = 2 2+1= 3
1
1 1
x(1) = 1 1+ 2 = 3
1
1 1
x(2) = 2 2+1= 3
1
1 1
x(3) = 1 1+2 = 3
1
1 1
x(4) = 1 2 −1= 1
−1 1 1
−j
1 2 2 1 1 1 1
x(5) = 2
−1
(1 − 2) GH 2
−j
2
JK =−
2
+j
2
1 −j
x(6) = 1 (2 − 1)( −j) = −j
−1 1 1
1 − −j
2 2 1 1 1 1
x(7) = 2
−1 (1 − 2) − GH 2
−j
2
JK =
2
+j
2

F ig 4 : B u tterfly d ia g ram fo r first sta ge o f ra d ix-2 D IF F F T.

The output sequence of first

RS 1 1 1 1UV
stage of computation = 3, 3, 3, 3, 1, − +j , − j, +j
T 2 2 2 2W
5. 41 Digital Signal Processing
Second stage computation
The input sequence for second
RS 1 1 1 1UV
stage of computation = 3, 3, 3, 3, 1, − +j , − j, +j
T 2 2 2 2W
The phase factors involved in second stage computation are W40 and W41 .
The butterfly computations of second stage are shown in fig 5.
1 1
3 3+3=6
1
0 1 1
− j 2π × 3 3+3=6
W40 = e 4 =1 1
1
1 π −1 1
− j 2π × −j × 3 3 −3 = 0
W41 = e 4 =e 2

= cos
FG −π IJ + j sin
FG −π IJ 3
−1 −j
(3 − 3) ( −j) = 0
H 2K H 2K 1 1
= −j 1 1 + ( −j) = 1 − j
1
1 1 1 1 1 1 1 1 2
−
2
+j
2 1 GH−
2
+j
2
JK + GH 2
+j
2
JK =j
2
1
−1 1
−j 1 − ( −j) = 1 + j
1
1 1
+j −1 −j 1 1 1 1 2
2 2 MNGH −
2
+j
2
JK − GH 2
+j
2
JKPQ ( − j) = j
2

F ig 5 : B u tte rfly d ia gra m for secon d sta g e o f ra d ix -2 D IF F F T.

The output sequence of second RS 2 2 UV
= 6, 6, 0, 0, 1 − j, j , 1+ j, j
stage of computation T 2 2W
Third stage computation
The input sequence to third RS 2 2 UV
= 6, 6, 0, 0, 1 − j, j , 1+ j, j
stage of computation T 2 2W
The butterfly computations of third stage are shown in fig 6.
6 6 + 6 = 12 = X (0)

The phase factor involved in third

6 6 − 6 = 0 = X (4)
stage of computation is W20 .
0 + 0 = 0 = X (2)
0 Since, W20 = 1, it is not
considered for computation.
0 0 − 0 = 0 = X (6)

2
1− j (1 − j) + j = 1 + j0.414 = X (1)
2

2 2
j (1 − j) − j = 1 − j2.414 = X (5)
2 2
1+ j 2
(1 + j) + j = 1 + j2.414 = X (3)
2
2 2
j (1 + j) − j = 1 − j0.414 = X (7)
2 2
F ig 6 : B u tte rfly d iag ra m fo r th ird stag e o f ra d ix -2 D IF F F T.
The output sequence of third stage of computation = { 12, 0, 0, 0, 1+j0.414, 1–j2.414, 1+j2.414, 1–j0.414 }
The output sequence of third stage of computation is the 8-point DFT of the given sequence in bit
reversed order.
In DIF-FFT algorithm the input to first stage is in normal order and the output of third stage will be in the
bit reversed order. Hence the actual result is obtained by arranging the output sequence of third stage in normal
order as shown below.
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 42
The sequence X(k) The sequence X(k)
in bit reversed order in normal order

X(0) = 12 X(0) = 12
X(4) = 0 X(1) = 1+ j0.414
X(2) = 0 X(2) = 0
X(6) = 0 X(3) = 1+ j2.414
X(1) = 1+ j0.414 X(4) = 0
X(5) = 1– j2.414 X(5) = 1– j2.414
X(3) = 1+ j2.414 X(6) = 0
X(7) = 1– j0.414 X(7) = 1– j0.414

\ DFT {x(n)} = X(k) = { 12, 1+ j0.414, 0, 1+ j2.414, 0, 1– j2.414, 0, 1– j0.414 }

Magnitude and phase specturm

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.
Note : The rectangular to polar conversion can be obtained by using R ® P conversion in calculator.

X(k) m 12, 1+ j0.414, 0, 1 + j2.414, 0, 1 − j2.414, 0, 1 − j0.414r

=
= m12∠0° , 1.08 ∠22 ° , 0∠0° , 2.61∠67 ° , 0 ∠0 °, 2.61∠− 67 ° , 0 ∠0 ° , 108
. ∠ − 22 °r
R|12∠0, 1.08 ∠22 °× π , 0∠0, 2.61∠67 ° × π , 0 ∠0, U|
= S 180 ° 180 °
|| π π
V|
2.61∠− 67 ° × , 0 ∠0, 1.08 ∠− 22 ° ×
T 180 ° 180 ° |W
= l 12∠0, 1.08 ∠0.12π , 0 ∠0, 2.61∠0.37 π , 0 ∠0, 2.61∠ − 0.37 π , 0 ∠0, 1.08 ∠ − 0.12πq
∴|X(k)| = m 12, 1.08, 0, 2 .61, 0, 2.61, 0, 1.08 r
∠X(k) = m 0, 0.12π, 0, 0.37π, 0, − 0.37π, 0, − 0.12πr

The magnitude specturm is the plot of the magnitude of each sample of X(k) as a function of k as shown
in fig 7. The phase spectrum is the plot of phase of X(k) as a function of k as shown in fig 8.
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 specturm will have a periodicity of 8 as shown in fig 7 and
fig 8.

X (k ) ∠X (k)
12
12
0.5π
0.37π 0.37π
0.25π
N=8 0.12π 0.12π

0
1 2 3 4 5 6 7 8 9 10 11
0.5π −0.12π
2.61 2.61 2.61
1.08 0.25π −0.37π
1.08 1.08

0 1 2 3 4 5 6 7 8 9 10 11 k
F ig 7 : M a gn itude sp ectrum . F ig 8 : P hase spectrum .
5. 43 Digital Signal Processing
Example 5.6
In an LTI system the input x(n) = {1, 2, 3} and the impulse response h(n) = {–1, –1}. Determine the response
of the LTI system by radix-2 DIT FFT.

Solution
The response y(n) of LTI system is given by 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.
The length of x(n) is 3 and h(n) is 2. Hence the length of y(n) is 3 + 2 – 1 = 4. Therefore given sequences
x(n) and h(n) are converted to 4 point sequences by appending zeros.
\ x(n) = {1, 2, 3, 0} and h(n) = {–1, –1, 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), DFT{y(n)} = Y(k).
By convolution theorem of DFT we get,
DFT {x(n) * h(n)} = X(k) H(k)
\ y(n) = DFT–1{Y(k)} = DFT-–1{X(k) H(k)}
The various steps in computing y(n) are,
Step - 1 : Determine X(k) using radix-2 DIT algorithm.
Step - 2 : Determine H(k) using radix-2 DIT algorithm.
Step - 3 : Determine the product X(k)H(k).
Step - 4 : Take inverse DFT of the product X(k)H(k) using radix-2 DIT algorithm.

Step-1: To determine X(k)

Since x(n) is a 4-point sequence, we have to compute
x(n) x(n)
4-point DFT. The 4-point DFT by radix-2 FFT consists of two
stages of computations with 2-butterflies in each stage. The given Normal order Bit reversed order
sequence x(n), is first arranged in bit reversed order as shown in
x(0) = 1 x(0) = 1
table.
x(1) = 2 x(2) = 3
The sequence arranged in bit reversed order forms the
input sequence to first stage computation. x(2) = 3 x(1) = 2
First stage computation x(3) = 0 x(3) = 0

Input sequence to first stage = { 1, 3, 2, 0 }. The butterfly computations of first stage are shown in fig1.

x (0) = 1 1+3=4 The phase factor involved in first

stage of computation is W20 .
x (2) = 3 1 − 3 = −2
Since, W20 = 1, it is not
x (1) = 2 2+0=2
considered for computation.

x (3) = 0 2 −0 = 2

F ig 1 : B u tterfly d ia gram fo r
first sta ge o f ra d ix -2 D IT F F T.
Output sequence of first stage of computation = { 4, -2, 2, 2 }
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 44
Second stage computation
Input sequence to second stage computation = { 4, -2, 2, 2 }
The phase factors involved in second stage computation are W40 and W41 .
The butterfly computations of second stage are shown in fig 2.
1 1 − j2π ×
0
4 4 + 2 = 6 = X (0)
1 W40 = e 4 =1
1 1 1 π
−2 −2 + 2( −j) = −2 − 2j = X (1) − j2π × −j ×
1 W41 = e 4 =e 2
1
1
2
-1 4 − 2 = 2 = X (2)
= cos
FG −π IJ + jsinFG −π IJ
2
−j
1
-1 −2 − 2( −j) = −2 + 2j = X (3)
H 2K H 2K
= −j
F ig 2 : B u tte rfly dia gra m fo r seco n d stag e o f ra d ix -2 D IT F F T.

Output sequence of second stage computation = { 6, -2–2j, 2, -2+2j }

The output sequence of second stage of computation is the 4-point DFT of x(n).
\ X(k) = DFT{x(n)} = {6, -2–2j, 2, -2+2j }

Step - 2: To determine H(k)

Since h(n) is a 4-point sequence, we have to compute 4-point DFT. The 4-point DFT by radix-2 FFT
consists of two stages of computations with 2-butterflies in each
h(n) h(n)
stage. The sequence h(n) is first arranged in bit reversed order as
Normal order Bit reversed order
shown in table.
h(0) = –1 h(0) = –1
The sequence in bit reversed order forms the input sequence
to first stage computation. h(1) = –1 h(2) = 0
First stage computation h(2) = 0 h(1) = –1
Input sequence of first stage = { –1, 0, –1, 0 }. The butterfly h(3) = 0 h(3) = 0
computations of first stage are shown in fig 3.
The phase factor involved in first
h(0) = −1 −1 + 0 = −1 stage of computation is W20 .
Since, W20 = 1, it is not
h(2) = 0 −1 − 0 = −1
considered for computation.
h(1) = −1 −1 + 0 = −1

h(3) = 0 −1 − 0 = −1

F ig 3 : B u tterfly d ia gram fo r
first sta g e o f ra dix -2 D IT FF T.

Output sequence of first stage computation = { –1, –1, –1, –1 }

Second stage computation
Input sequence to second stage computation = { –1, –1, –1, –1 }
0
− j2π ×
The phase factors involved are W40 and W41 . W40 = e 4 =1
1 π
− j2π × −j ×
The butterfly computations of second stage are shown in fig 4. W41 = e 4 =e 2

= cos
FG −π IJ + jsinFG −π IJ
H 2K H 2K
= −j
5. 45 Digital Signal Processing
1 1
−1 −1 + ( −1) = −2 = H (0)
1
1 1
−1 −1 + ( −1)( −j) = −1 + j = H (1)
1
1
1 -1
−1 −1 − ( −1) = 0 = H (2)
1
−j -1
−1 −1 − ( −1)( −j) = −1 −j = H (3)

F ig 4 : B u tte rfly d ia gram for seco n d

stag e o f ra d ix-2 D IT F F T o f H (k).
Output sequence of second stage computation = { –2, –1 + j, 0, –1 –j }
The output sequence of second stage computation is the 4-point DFT of h(n).

\ H(k) = DFT{h(n)} = { –2, –1 + j, 0, –1 –j }

Step 3 : To determine the product X(k)H(k)

Let the product, X(k)H(k) = Y(k); for k = 0, 1, 2, 3.
when k = 0; Y(0) = X(0) ´ H(0) = 6 ´ (–2) = –12
when k = 1; Y(1) = X(1) ´ H(1) = (–2–2j) ´ (–1 + j) = 4
when k = 2; Y(2) = X(2) ´ H(2) = 2 ´ 0 = 0
when k = 3; Y(3) = X(3) ´ H(3) = (–2+2j)´ (–1–j) = 4
\ Y(k) = { –12, 4, 0, 4}

Step - 4: To determine inverse DFT of Y(k)

The 4-point inverse DFT of Y(k) can be computed using radix-2 DIT FFT by taking conjugate of the phase
factors and then dividing the output sequence of FFT by 4.
Y(k) = { –12, 4, 0, 4}
The 4-point inverse DFT of Y(k) using radix-2 DIT FFT involves two stages of computations with
2-butterflies in each stage. The sequence Y(k) is arranged in bit
reversed order as shown in the table. Y(k) Y(k)
Normal order Bit reversed order
The sequence arranged in bit reversed order forms the input
sequence to first stage computation. Y(0) = –12 Y(0) = –12
First stage computation Y(1) = 4 Y(2) =0
Input sequence to first stage = { –12, 0, 4, 4 }. The butterfly Y(2) =0 Y(1) =4
computations of first stage are shown in fig 5.
Y(3) =4 Y(3) =4
Y (0) = −12 −12 + 0 = −12

The phase factor involved in first

Y (2) = 0 −12 − 0 = −12 ∗

Y (1) = 4 4+4=8
stage of computation is W20 . d i
0 ∗

Y (3) = 4 4 −4 = 0
Since, dW i
2 = 1, it is not
considered for computation.
F ig 5 : B u tterfly d iag ram fo r
first sta g e o f in v erse D F T o f Y (k).
The output sequence of first stage computation = { – 12, – 12, 8, 0}

Second stage computation

Input sequence to second stage computation = { – 12, – 12, 8, 0 }

The phase factors involved are (W40 )∗ and (W41)∗.

Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 46
The butterfly computation of second stage is shown in fig 6. ∗ j2π ×
0

−12
1 1
−12 + 8 = −4 = 4y(0)
dW i 0
4 =e 4 =1
1 π
1 1 ∗
j2π × j ×

−12
1 1
1
−12 + (0)(j) = −12 = 4y(1) dW i 4 = e 4 =e 2

W4
0 ∗
d i =1 1
-1 = cos
FG π IJ + jsinFG π IJ
8
1 ∗
−12 − 8 = −20 = 4y(2) H 2K H 2K
0
d i
W4 =j 1
-1
−12 − (0)(j) = −12 = 4y(3)
=j

F ig 6 : B u tte rfly d ia gram for seco n d

sta g e o f in verse D F T o f Y (k).
The output sequence of second stage computation = { – 4, – 12, – 20, – 12 }
The sequence y(n) is obtained by dividing each sample of output sequence of second stage by 4.

\ The response of the LTI system, y(n) = { –1, –3, –5, –3 }

Example 5.7
Determine the response of LTI system when the input sequence x(n) = {–1, 2, 2, 2, –1} by radix 2 DIT FFT.
The impulse response of the system is h(n) = {–1, 1, –1, 1}.

Solution
The response of an LTI system is given by 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 sequence x(n) and h(n) should be converted to the size of y(n), by appending with zeros,
and then circular convolution of x(n) and h(n) is performed.
The length of x(n) = 5, and h(n) = 4. Hence the length of y(n) is 5 + 4 – 1 = 8.
Therefore x(n) and h(n) are converted into 8-point sequence by appending zeros.
\ x(n) = { –1, 2, 2, 2, –1, 0, 0, 0 } and h(n) = { –1, 1, –1, 1, 0, 0, 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), DFT {y(n)} = Y(k).
By convolution theorem of DFT we get,
DFT {x(n) * h(n)} = X(k) H(k)
\ y(n) = DFT-1{Y(k)} = DFT-1{X(k) H(k)}
The various steps in computing y(n) are,
Step - 1 : Determine X(k) using radix-2 DIT algorithm.
Step - 2 : Determine H(k) using radix-2 DIT algorithm.
Step - 3 : Determine the product X(k)H(k).
Step - 4 : Take inverse DFT of the product X(k)H(k) using radix-2 DIT algorithm.
Step-1 : To determine X(k)
Since x(n) is an 8 point sequence, we have to compute 8-point DFT.
The 8-point DFT by radix-2 FFT algorithm consists of 3 stages of computations with 4 butterflies in each
stage.
The given sequence x(n) is arranged in bit reversed order as shown in the following table.
5. 47 Digital Signal Processing

x(n) x(n)
Normal order Bit reversed order
x(0) = –1 x(0) = –1
x(1) = 2 x(4) = –1
x(2) = 2 x(2) = 2
x(3) = 2 x(6) = 0
x(4) = –1 x(1) = 2
x(5) = 0 x(5) = 0
x(6) = 0 x(3) = 2
x(7) = 0 x(7) = 0

The sequence arranged in bit-reversed order forms the input sequence to the first stage computation.
First stage computation
Input sequence to first stage = { –1, –1, 2, 0, 2, 0, 2, 0 }.
The butterfly computation of first stage is shown in fig 1.
The phase factor involved in first
x (0) = −1 −1+ ( −1)= −2 stage of computation is W20 .
Since, W20 = 1, it is not
x (4) = −1 −1 −( −1) = 0
considered for computation.
x (2) = 2 2+0 = 2

x (6) = 0 2 −0 = 2

x (1) = 2 2+0 = 2

x (5) = 0 2 −0 = 2

x (3) = 2 2+0 = 2

x (7) = 0 2 −0 = 2

F ig 1 : B u tterfly d ia gram for first

stage o f ra dix-2 D IT F F T o f X (k ).
Output sequence of first stage of computation = { –2, 0, 2, 2, 2, 2, 2, 2 }

Second stage computation

The input sequence to second stage of computation = { –2, 0, 2, 2, 2, 2, 2, 2 }

Phase factors involved in second stage are W40 and W41.

The butterfly computation of second stage is shown in fig 2.

0
− j2π ×
W40 = e 4 =1
1 π
− j2π × −j ×
W41 = e 4 =e 2

= cos
FG −π IJ + jsinFG −π IJ
H 2K H 2K
= −j

Output sequence of second stage of computation = { 0, –2j, –4, 2j, 4, 2 –2 j, 0, 2 + 2j }

Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 48
1 1
−2 −2 + 2 = 0
1
1 1
0 0 + 2( −j) = −2j
1
1
1 -1
2 −2 − 2 = −4
1
−j -1
2 0 − 2( −j) = 2j

1 1
2 2+2=4
1
1 1
2 2 + 2( −j) = 2 − 2j
1
1 1
-1
2 2 −2 = 0
1
−j -1
2 2 − 2( −j) = 2 + 2j

F ig 2 : B u tte rfly d iag ra m fo r seco n d sta ge o f ra d ix-2 D IT F F T o f X (k).

Third stage computation
Input sequence to third stage computation = { 0, –2j, –4, 2j, 4, 2 – 2j, 0, 2 + 2j }.
Phase factors involved are W80 , W81, W82 and W83.
The butterfly computation of third stage is shown in fig 3.
0
− j2π ×
W80 = e 8 =1
1 π
W81 = e
− j2π ×
8 =e
−j ×
4 = cos
FG −π IJ + j sinFG −π IJ = 1 − j 1 = 0 . 707 − j0 . 707
H 4K H 4K 2 2
2 π
W82 = e
− j2π ×
8 = e
−j ×
2 F −π IJ + j sinFG −π IJ = −j
= cosG
H 2K H 2K
3 3π
W83 = e
− j2π ×
8 = e
−j ×
4 = cosG
F −3π IJ + j sinFG −3π IJ = − 1 − j 1 = −0 . 707 − j0 . 707
H4K H4K 2 2

1
0 0 + 4 = 4 = X(0)

1
− 2j −2 j + (2 − 2 j) × 0.707 − j0.707 = −j4 . 828 = X(1)

1 −4 + 0 × ( −j) = −4 = X(2)
−4

1
2j 2 j + (2 + 2 j) × −0.707 − j 0.707 = −j0 . 828 = X(3)

1
4 0 − 4 = −4 = X( 4)
0.707 −1
−j0.707
2−2j −2j − (2 − 2j) × 0 .707 − j0 .707 = j0 . 828 = X(5)
−1
−j
0 −4 − 0 × ( −j) = −4 = X(6)
−1
−0.707
−j0.707 2 j − (2 + 2 j) × −0 .707 − j0 .707 = j4 . 828 = X(7)
2+2j
−1

F ig 3 : B u tte rfly d ia gram for third sta g e o f rad ix-2 D IT F F T o f X (k ) .

Output sequence of third UV m 4,= − j4.828, − 4, − j0.828, − 4, j0.828, − 4, j4.828 r

stage of computation W
∴ DFT {x(n)} = X(k) = m 4, − j4.828, − 4, − j0.828, − 4, j0.828, − 4, j4.828 r
5. 49 Digital Signal Processing
Step 2 : To determine H(k)
Since h(n) is an 8-point sequence, we have to compute 8-point DFT. The 8-point DFT by radix-2 FFT
consists of three stages of computations with four butterflies in each stage.
The sequence h(n) is first arranged in bit reversed order as shown in the following table .

h(n) h(n)
Normal order Bit reversed order

h(0) = –1 h(0) = –1

h(1) = 1 h(4) = 0

h(2) = –1 h(2) = –1

h(3) = 1 h(6) = 0

h(4) = 0 h(1) = 1

h(5) = 0 h(5) = 0

h(6) = 0 h(3) = 1

h(7) = 0 h(7) = 0

The sequence arranged in bit reversed order forms the input sequence to the first stage.

First stage computation

Input sequence to first stage computation = { –1, 0, –1, 0, 1, 0, 1, 0 }
The butterfly computations of first stage is shown in fig 4.
Output sequence of first stage of computation = { –1, –1, –1, –1, 1, 1, 1, 1 }

h(0) = −1 −1+ 0 = −1
The phase factor involved in first
h(4) = 0 −1 −0 = −1 stage of computation is W20 .
h(2) = −1 −1+ 0 = −1 Since, W20 = 1, it is not
considered for computation.
h(6) = 0 −1 −0 = −1

h(1) = 1 1+0= 1

h(5) = 0 1 −0 = 1

h(3) = 1 1+0 = 1

h(7) = 0 1 −0 = 1

F ig 4 : B u tterfly d iag ra m fo r first

sta g e o f ra dix -2 D IT F F T o f H (k).
Second stage computation
Input sequence to second stage of computation = { –1, –1, –1, –1, 1, 1, 1, 1 }

Phase factors involved in second stage are W40 and W41 .

The butterfly computations of second stage are shown in fig 5.

Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 50
1 1
−1 −1 + ( −1) = −2
1 0
− j2π ×
−1
1 1
−1 + ( −1)( −j) = −1 + j W40 = e 4 =1
1
1 π
1 − j2π × −j ×
−1
1 -1
−1 − ( −1) = 0 W41 = e 4 =e 2

−j
1
-1 = cos
FG −π IJ + jsinFG −π IJ
−1 −1 − ( −1)( −j) = −1 − j
H 2K H 2K
1 1 = −j
1 1+1=2
1
1 1
1 1 + 1( −j) = 1 − j
1
1 1 -1
1 1 −1 = 0
1
−j -1
1 1 − 1( −j) = 1 + j

F ig 5 : B u tte rfly d ia gra m for seco n d

sta ge o f ra d ix-2 D IT F F T o f H (k).
Output sequence of second
= { –2, –1+ j, 0, –1–j, 2, 1 – j, 0, 1 + j }
stage of computation

Third stage computation

Input sequence to third stage computation = { –2, –1+ j, 0, –1–j, 2, 1 – j, 0, 1 + j }

Phase factors involved in third stage computations are W80 , W81, W82 , and W83.

The butterfly computations of third stage are shown in fig 6.

0
− j2π ×
W80 = e 8 =1
1 π
W81 = e
− j2π ×
8 =e
−j ×
4 FG −π IJ + j sinFG −π IJ = 1 − j 1 = 0 . 707 − j0 . 707
= cos
H 4K H 4K 2 2
2 π
W82 = e
− j2π ×
8 = e
−j ×
2 F −π IJ + j sinFG −π IJ = − j
= cosG
H 2K H 2K
3 3π
W83 = e
− j2π ×
8 = e
−j ×
4 F −3π IJ + j sinFG −3π IJ = − 1 − j 1 = −0 . 707 − j0 . 707
= cosG
H4K H4K 2 2

1
−2 −2 + 2 = 0 = H (0)

1
−1 + j −1 + j + 1 − j × 0 .707 − j0 .707 = −1 − j0 . 414 = H(1)

1
0 0 + 0 × ( −j) = 0 = H (2)

1
−1 − j −1 − j + 1 + j × −0 .707 − j0 .707 = −1 − j2 . 414 = H( 3 )

1
2 −2 − 2 = −4 = H (4)
0.707 −1
−j0.707
1 −j −1 + j − 1 − j × 0 .707 − j0 .707 = −1 + j2 . 414 = H(5)
−1
−j
0 0 − 0 × ( −j) = 0 = H (6)
−0.707 −1
−j0.707
1+j −1 − j − 1 + j × −0 .707 − j0 .707 = −1 + j0.414 = H (7)
−1
F ig 6 : B u tte rfly d ia gra m for th ird sta g e of rad ix-2 D IT F F T o f H (k ) .
5. 51 Digital Signal Processing
Output sequence of third UV = m0, − 1− j0.414, 0, r
− 1 − j2.414, − 4, − 1 + j2.414, 0, − 1 + j0.414
stage computation W
The output sequence of third stage computation is the 8-point DFT of h(n).

∴ DFT h(n)l q = H(k) = m0, − 1 − j0.414, 0, − 1 − j2.414, − 4, − 1 + j2.414, 0, − 1 + j0.414 r

Step 3 : To determine the product X(k)H(k)
Let the product of X(k)H(k) = Y(k); for k = 0, 1, 2, 3, 4, 5, 6, 7
\ Y(k) = X(k)H(k)
When k = 0 ; Y(0) = X(0) H(0) = 4 × 0=0
When k = 1; Y(1) = X(1) H(1) = − j4.828 × –1 − j0.414 = −2 + j4.828
When k = 2; Y(2) = X(2) H(2) = − 4 × 0 = 0
When k = 3; Y(3) = X(3) H(3) = – j0.828 × –1 − j2.414 = −2 + j0.828
When k = 4 ; Y(4) = X(4) H(4) = – 4 × – 4 = 16
When k = 5; Y(5) = X(5) H(5) = j0.828 × –1 + j2.414 = −2 − j0.828
When k = 6 ; Y(6) = X(6) H(6) = – 4 × 0 = 0
When k = 7 ; Y(7) = X(7) H(7) = j4.828 × –1 + j0.414 = −2 − j4.828

∴ Y(k) = m 0, – 2 + j4.828, 0, − 2 + j0.828, 16, − 2 − j0.828, 0, − 2 − j4.828 r

Step - 4: To determine inverse DFT of Y(k)
The 8-point inverse DFT of Y(k) can be computed using radix-2 DIT FFT by taking conjugate of the phase
factors and then dividing the output sequence of FFT by 8.
The 8-point inverse DFT of Y(k) using radix-2 DIT FFT involves three stages of computations with
4-butterflies in each stage. The sequence Y(k) is arranged in bit reversed order as shown in the following table.
The sequence arranged in bit reversed order forms the input sequence to first stage computation.

Y(k) Y(k)
Normal order Bit reversed order

Y(0) = 0 Y(0) = 0
Y(1) = −2 + j4.828 Y(4) = 16
Y(2) = 0 Y(2) = 0
Y(3) = −2 + j0.828 Y(6) = 0
Y(4) = 16 Y(1) = − 2 + j4.828
Y(5) = −2 − j0.828 Y(5) = −2 − j0.828
Y(6) = 0
Y(3) = − 2 + j0.828
Y(7) = –2 − j4.828
Y(7) = – 2 − j4.828
First stage computation

Input sequence of first stage =

RS 0, 16, 0, 0, – 2 + j4.828, − 2 + j0.828, UV
|T−2 + j0.828, − 2 − j4.828 |W
Chapter 5 - Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT) 5. 52
The butterfly computations of first stage are shown in fig 7.
The phase factor involved in first
Y(0) = 0 0 + 16 = 16 ∗
stage of computation is W20 . d i
∗ 0
Y(4) = 16 0 − 16 = −16 FH IK
Since, W2
0
=e
j2π ×
4 = e0 = 1,

Y(2) = 0 0+0=0
it is not considered for
computation.
Y(6) = 0 0 −0 = 0

Y 1 = − 2 + j 4.828 −2 + j 4.828 + −2 − j 0.828 = −4 + j4

Y 5 = − 2 + j 0.828 −2 + j 4.828 − −2 − 0.828 = j 5 .656

Y 3 = − 2 − j 0.828 −2 + j 0.828 + −2 − j 4.828 = −4 − j 4

Y 3 = − 2 − j 4.828 −2 + j 0.828 − −2 − j 4.828 = j 5 .656

F ig 7 : B u tte rfly d iag ra m fo r first sta g e o f inv erse D F T o f Y (k).

Output sequence of first stage = m 16, − 16, 0, 0, − 4 + j4, j 5.656, − 4 − j4, j5.656 r
Second stage computation

Input sequence of second stage = m 16, − 16, 0, 0, − 4 + j4, j5.656, − 4 − j4, j5.656 r
The butterfly computation of second stage is shown in fig 8.
The phase factors involved are (W0 )∗ and (W1)∗. 4 4
0
∗ j2π ×

16
1 1
16 + 0 = 16 dW i
0
4 =e 4 = e0 = 1
1 1 π
j2π × j ×
1 ∗
−16
1 1
1
−16 + (0)(+j) = −16 dW i
4 =e 4 =e 2

1
1
-1 = cos
FG π IJ + jsinFG π IJ
0
1
16 − 0 = 16
H 2K H 2K
+j -1 =j
0 −16 − (0)(+j) = −16

1 1
−4 + j4 (−4 + j4) + (−4 − j4) = −8
1
1 1
j5.656 j5.656 + j5.656(j) = −5.656 + j5.656
1
1 1 -1
−4 − j4 (−4 + j4) − (−4 − j4) = j8
1
+j -1
j5.656 j5.656 − j5.656 (j) = 5.656 + j5.656

F ig 8 : B utterfly diagram for second stag e of inverse D F T of Y(k)

Output sequence of second |UV = m 16, − 16, 16, − 16, − 8, − 5.656 + j 5 .656 , j8, 5.656 + j 5.656 r
stage computation |W
Third stage computation

Input sequence of third |UV = m 16, − 16, 16, − 16, − 8, − 5.656 + j 5 .656 , j8, 5.656 + j 5.656 r
stage computation |W
The butterfly computation of third stage is shown in fig 9.

The phase factors involved are (W80 )∗ , (W81)∗ , (W82 )∗ and (W83 )∗ .
5. 53 Digital Signal Processing
0
j2π ×
(W80 )∗ = e 8 =1
1 π
(W81)∗ = e
j2π ×
8 =e
j ×
4 = cos
FG π IJ + j sinFG π IJ = 1 + j 1 = 0. 707 + j0. 707
H 4K H 4K 2 2
2 π
(W82 )∗ = e
j2π ×
8 =e
j ×
2 F πI F πI
= cosG J + j sinG J = j
H 2K H 2K
3 3π
(W83 )∗ = e
j2π ×
8 =e
j×
4 F 3π I F 3π I 1 + j 1 = −0. 707 + j0. 707
= cosG J + j sinG J = −
H 4K H 4K 2 2
1
16 16 + ( −8) = 8 = 8y (0)

1
−16 −16 + −5 . 656 + j5 . 656 0.707 + j0 .707 = −24 = 8y (1)

1
16 16 + j8(j) = 16 − 8 = 8y (2)

1
−16 −16 + 5. 656 + j5. 656 × −0.707 + j0.707 = −24 = 8 y (3)

1 16 − (−8) = 24 = 8y (4)
−8
−1
0.707
+ j0.7 07 −1
−5.656 + j5.656 −16 − −5 . 656 + j5 . 656 0.707 + j0.707 = −8 = 8 y(5)

+j −1
j8 16 − j8(j) = 16 + 8 = 24 = 8y(6)
−0.707
+ j0.7 07 −1
5.656 + j5.656 −16 − 5. 656 + j5. 656 × −0 .707 + j0.707 = −8 = 8y(7)

F ig 9 : B u tte rfly d ia gra m for th ird sta g e of in v erse D F T o f Y (k ).

Output sequence of third stage computation = { 8, –24, 8, –24, 24, –8, 24, –8 }
The sequence y(n) is obtained by dividing each sample of output sequence of third stage by 8.

\ The response of the LTI system, y(n) = { 1, –3, 1, –3, 3, –1, 3, –1 }

5.10 Summary of Important Concepts

1. The drawback in DTFT is that the frequency domain representation of a discrete time signal obtained
using DTFT will be a continuous function of w.
2. The DFT has been developed to convert a continuous function of w to a discrete function of w.
3. The DFT of a discrete time signal can be obtained by sampling the DTFT of the signal.
4. The sampling of the DTFT is conventionally performed at N equally spaced frequency points in the
period, 0 £ w £ 2p .
5. DFT sequence starts at k = 0, corresponding to w = 0 but does not include k = N, corresponding to w =2p.
6. The DFT is defined along with number of samples and is called N-point DFT.
7. The number of samples N for a finite duration sequence x(n) of length L should be such that, N ³ L, in
order to avoid aliasing of frequency spectrum.
8. The X(k) is also called discrete frequency spectrum (or signal spectrum) of the discrete time signal x(n).
9. The plot of samples of magnitude sequence versus k is called magnitude spectrum.
10. The plot of samples of phase sequence versus k is called phase spectrum.
11. The DFT sequence X(k) is periodic with periodicity of N samples.