MODULE - I

Discrete Fourier Transforms (DFT): Frequency domain sampling and Reconstruction

of Discrete Time Signals, The Discrete Fourier Transform, DFT as a linear transformation,
Properties of the DFT: Periodicity, Linearity and Symmetry properties, Multiplication of two
DFTs and Circular Convolution, Additional DFT properties.

1.1 Introduction
DSP manipulates different types of signals with the intention of filtering, measuring, or
compressing and producing analog signals. Analog signals differ by taking information and
translating it into electric pulses of varying amplitude, whereas digital signal information is
translated into binary format where each bit of data is represented by two distinguishable
amplitudes. Another noticeable difference is that analog signals can be represented as sine
waves and digital signals are represented as square waves. DSP can be found in almost
any field, whether it’s oil processing, sound reproduction, radar and sonar, medical image
processing, or telecommunications- essentially any application in which signals are being
compressed and reproduced.
The digital signal process takes signals like audio, voice, video, temperature, or pressure
that have already been digitized and then manipulates them mathematically. This informa-
tion can then be represented as discrete time, discrete frequency, or other discrete forms so
that the information can be digitally processed. An analog-to-digital converter is needed in
the real world to take analog signals (sound, light, pressure, or temperature) and convert
them into 0’s and 1’s for a digital format.

1.2 Frequency domain sampling and reconstruction of discrete time signals

An aperiodic finite energy signal has continuous spectra. For an aperiodic signal x[n] the
spectrum is:
∞
x[n]e−jwn
X
X[w] = (1.1)
n=−∞

Suppose we sample X[w] periodically in frequency at a sampling of δw radians between

successive samples. We know that DTFT is periodic with 2π, therefore only samples in

1
2 Module-1

X(w)

0 w

Fig. 1.1. Frequency domain sampling of the spectrum.

the fundamental frequency range will be necessary. For convenience we take N equidistant
samples in the interval; 0 < w < 2π The spacing between samples will be as δw = 2π/N
shown below in Fig. 1.1.
Let us first consider selection of N , or the number of samples in the frequency domain.
If we evaluate eqn. (1.1) at

∞
2πk
 
x[n]e−j2~n/N
X
X = k = 0, 1, 2, . . . . . . ., (N − 1) (1.2)
N n=−∞

We can divide the summation in eqn. (1.1) into infinite number of summations where
each sum contains N terms.

−1 N −1 2N −1
2πk
 
x[n]e−j2~n/N + x[n]e−j2~n/N + x[n]e−j2πn/N
X X X
X = ...... +
N n=−N n=0 n=N

∞ lN +N
X−1
2πk
 
x[n]e−j2πkn/N
X
X =
N l=−∞ n=lN

If we then change the index in the summation from n to n − lN and interchange the order
of summations we get:
 
N −1 ∞
2πk
 
x[n − lN ] e−j2πkn/N ; k = 0, 1, 2, . . . . . . , (N − 1)
X X
=  (1.3)
N n=0 l=−∞

The quantity inside the bracket denotes xp [n]. This signal is a repeating version of x[n] every
N samples. Since it is a periodic signal it can be represented by the Fourier Series.
Digital Signal Processing 3

N
X −1
xp [n] = ck ej2πk/N n = 0, 1, 2, . . . . . . , (N − 1) (1.4)
k=0

with Fourier series coefficients:

−1
1 NX
ck = xp [n]e−j2πk/N k = 0, 1, 2, . . . . . . , (N − 1)
N n=0

Therefore it is possible to write the expression xp [n] as below:

−1
1 NX 2π
 
xp [n] = X k ej2πkn/N n = 0, 1, . . . . . . , (N − 1) (1.5)
N k=0 N

The above formula shows the reconstruction of the periodic signal xp [n] from the samples
of the spectrum X[w]. But it does not say if X[w] or x[n] can be recovered from the samples.
Since xp [n] is the periodic extension of x[n] it is clear that x[n] can be recovered from xp [n] if
there is no aliasing in the time domain. That is if x[n] is time-limited to less than the period
N of xp [n]. This is depicted in Fig. below:

x(n)

x(n) contains L=4 samples

n
xp(n)
Here N=6, N>L no aliasing

n
xp(n)
Here N=3, N<L aliasing

n
Overlap due to
aliasing

Fig. 1.2. An original signal, periodic repetition with N > L and periodic repetition with
N < L.
4 Module-1

1.3 Discrete Fourier Transform (DFT)

• DFT:
N −1 N −1
2πkn
x(n)e−j
X X
X(k) = x(n)WNkn = N ; k = 0, 1, 2, . . . , N − 1
n=0 n=0

• IDFT:
−1 −1
1 NX −kn
N
X 2πkn
x(n) = X(k)WN = X(k)ej N ; n = 0, 1, 2, . . . , N − 1
N k=0 k=0

1.3.1 DFT as a linear transformation

The expression for DFT and IDFT can be given as,

N −1 N −1
2πkn
x(n)e−j
X X
X(k) = x(n)WNkn = N ; k = 0, 1, 2, . . . , N − 1
n=0 n=0

−1 −1
1 NX −kn
N
X 2πkn
x(n) = X(k)WN = X(k)ej N ; n = 0, 1, 2, . . . , N − 1
N k=0 k=0

where by definition, WN = e−j2π/N , Which is an N th root of unity. The computation of each

point of DFT can be accomplished by N complex multiplications and (N − 1) complex addi-
tion. Hence the N-point DFT values can be computed in a total of N 2 complex multiplication
and N × (N − 1) complex addition.
The values of WNkn can be represented as a [WN ] of size N × N . With these definitions,
the N-point DFT can be expressed as,

XN = WN ×N

where, WN is the matrix of the linear transformation and WN is symmetric matrix. If we

assume that inverse of the WN is exists then above eqn. can be inverted by pre-multiplying
both sides by WN−1 . Therefore we get
xn = WN−1 XN but according to definition of IDFT, this is the expression of IDFT. Also,
IDFT eqn. can be expressed as

1 ∗
xn = W × XN
N N
Where WN∗ denotes the complex conjugate of the, matrix WN . Comparing above equations
Digital Signal Processing 5

we can conclude that

WN−1 = 1
N × WN∗
WN · WN∗ = N × IN
Where, IN is the N × N identity matrix. Hence DFT is linear transformation.

Example 1.1: Compute the 4-point DFT of the sequence x(n) = {0, 1, 2, 3}.

 Solution:

N −1 N −1
2πkn
x(n)e−j
X X
X(k) = x(n)WNkn = N ; k = 0, 1, 2, . . . , N − 1
n=0 n=0

4−1 3
2πkn
x(n)e−j
X X
X(k) = x(n)W4kn = 4

n=0 n=0

2πkn
   
WNkn = e−j N = cos 2πkn
N − j sin 2πkn
N

when k = 0
3
X 3
X 3
X
X(0) = x(n)W40×n = x(n) × 1 = x(n) = 0 + 1 + 2 + 3 = 6
n=0 n=0 n=0

when k = 1
3
X 3
X
X(1) = x(n)W41×n = x(n) × W4n
n=0 n=0
X(1) = x(0)W40 + x(1)W41 + x(2)W42 + x(3)W43
X(1) = 0 × (1) + 1 × (−j) + 2 × (−1) + 3 × (j) = −2 + 2j

when k = 2
3
X 3
X
X(2) = x(n)W42×n = x(n) × W42n
n=0 n=0
X(2) = x(0)W40 + x(1)W42 + x(2)W44 + x(3)W46
X(2) = 0 × (1) + 1 × (−1) + 2 × (1) + 3 × (−1) = −2
6 Module-1

when k = 3
3
X 3
X
X(3) = x(n)W43×n = x(n) × W43n
n=0 n=0
X(3) = x(0)W40 + x(1)W43 + x(2)W46 + x(3)W49
X(3) = 0 × (1) + 1 × (j) + 2 × (−1) + 3 × (−j) = −2 − 2j

X(k)={6, -2+2j, -2, -2-2j}

Example 1.2: Given a finite length sequence, x(n) = δ(n) + 2δ(n − 3). Determine the 6-point
DFT of x(n).

 Solution: Given, x(n) = δ(n) + 2δ(n − 3) = {1, 0, 0, 2, 0, 0}; N = 6

N −1 N −1
2πkn
x(n)e−j
X X
X(k) = x(n)WNkn = N ; k = 0, 1, 2, . . . , N − 1
n=0 n=0

when k = 0
P5 0×n
X(0) = n=0 x(n)wN
X(0) = x(0)w60n + x(1)w60n + x(2)w60n + x(3)w60n + x(4)w60n + x(5)w60n
X(0) = x(0) + x(1) + x(2) + x(3) + x(4) + x(5) = 3

when k = 1
P5 1×n
X(1) = n=0 x(n)w6
X(1) = x(0)w60 + x(1)w61 + x(2)w62 + x(3)w63 + x(4)w64 + x(5)w65
X(1) = 1 + 0 + 0 + 2(−1) + 0 + 0 = −1

when k = 2
5
X
X(2) = x(n)w62×n
n=0
X(2) = x(0)w60 + x(1)w62 + x(2)w64 + x(3)w66 + x(4)w68 + x(5)w610
X(2) = 1 + 0 + 0 + 2(1) + 0 + 0 = 3

when k = 3
5
X
X(3) = x(n)w63×n X(3) = x(0)w60 + x(1)w63 + x(2)w66 + x(3)w69 + x(4)w612 + x(5)w615
n=0
X(3) = 1 + 0 + 0 + 2(−1) + 0 + 0 = −1
Digital Signal Processing 7

when k = 4
5
X
X(4) = x(n)w64×n
n=0
X(4) = x(0)w60 + x(1)w64 + x(2)w68 + x(3)w612 + x(4)w616 + x(5)w620
X(4) = 1 + 0 + 0 + 2(1) + 0 + 0 = 3
X(4) = 3

when k = 5
5
X
X(5) = x(n)w65×n
n=0
X(5) = x(0)w60 + x(1)w61 + x(2)w62 + x(3)w63 + x(4)w64 + x(5)w65
X(5) = 1 + 0 + 0 + 2(−1) + 0 + 0 = −1
X(5) = −1

X(k)={3, -1, 3, -1, 3, -1}

(
1/3, 0 ≤ n ≤ 2
Example 1.3: Obtain 4-point DFT of the sequence, x(n) =
0, otherwise

(
1/3, 0 ≤ n ≤ 2
 Solution: Given, x(n) = = {1/3, 1/3, 1/3, 0}
0, otherwise
N
X −1 4−1
X 3
X
X(k) = x(n)WNkn = x(n)W4kn = x(n)W4kn
n=0 n=0 n=0

when k = 0
3
X 3
X
X(0) = x(n)W40×n = x(n) × 1
n=0 n=0
X(0) = x(0) + x(1) + x(2) + x(3) = 1

when k = 1
3
X 3
X
X(1) = x(n)W41×n = x(n) × W4n
n=0 n=0
X(1) = x(0)W40 + x(1)W41 + x(2)W42 + x(3)W43
1 1 1
X(1) = 3 × (1) + 3 × (−j) + 3 × (−1) + 0 × (j) = − 13 j
8 Module-1

when k = 2
3
X 3
X
X(2) = x(n)W42×n = x(n) × W42n
n=0 n=0
X(2) = x(0)W40 + x(1)W42 + x(2)W44 + x(3)W46
1 1 1 1
X(2) = 3 × (1) + 3 × (−1) + 3 × (1) + 0 × (−1) = 3

when k = 3
P3 3×n
= 3n=0 x(n) × W43n
P
X(3) = n=0 x(n)W4
X(3) = x(0)W40 + x(1)W43 + x(2)W46 + x(3)W49
1 1 1
X(3) = 3 × (1) + 3 × (j) + 3 × (−1) + 0 × (−j) = 13 j

X(k)={1, -1/3 j, 1/3, 1/3 j}

Example 1.4: Compute the 8-point DFT of the sequence x(n) = {1, 1, 1, 1, 0, 0, 0, 0}.

 Solution: Given, x(n) = {1, 1, 1, 1, 0, 0, 0, 0}; N = 8.

N
X −1 8−1
X 7
X
X(k) = x(n)WNkn = x(n)W8kn = x(n)W8kn
n=0 n=0 n=0

when k = 0
7
X 7
X 7
X
X(0) = x(n)W80×n = x(n) × 1 = x(n) = 1 + 1 + 1 + 1 + 0 + 0 + 0 + 0 = 4
n=0 n=0 n=0

when k = 1
7
X 7
X
X(1) = x(n)W81×n = x(n) × W8n
n=0 n=0
X(1) = x(0)W8 + x(1)W81 + x(2)W82 + x(3)W83 + x(4)W84 + x(5)W85
0 + x(6)W86 + x(7)W87
X(1) = 1W80 + 1W81 + 1W82 + 1W83 + 0W84 + 0W85 + 0W86 + 0W87
X(1) = 1 × 1 + 1 × (0.707 − j0.707) + 1 × (−j) + 1(−0.707 − j0.707) = 1 − j2.414

when k = 2
7
X 7
X
X(2) = x(n)W82×n = x(n) × W82n
n=0 n=0
X(2) = x(0)W80 + x(1)W82 + x(2)W84 + x(3)W86 + x(4)W88 + x(5)W810 + x(6)W812 + x(7)W814
X(2) = 1W80 + 1W82 + 1W84 + 1W86 + 0W88 + 0W810 + 0W812 + 0W814
X(2) = 1 × 1 + 1 × (−j) + 1 × (−1) + 1(j) = 0
Digital Signal Processing 9

when k = 3
7
X 7
X
X(3) = x(n)W83×n = x(n) × W83n
n=0 n=0
X(3) = x(0)W80 + x(1)W83 + x(2)W86 + x(3)W89 + x(4)W812 + x(5)W815 + x(6)W818 + x(7)W821
X(3) = 1W80 + 1W83 + 1W86 + 1W89 + 0W812 + 0W815 + 0W818 + 0W821
X(3) = 1 × 1 + 1 × (−0.707 − j0.707) + 1 × (j) + 1(0.707 − j0.707) = 1 − j0.414

7
X 7
X
X(4) = x(n)W84×n = x(n) × W84n
n=0 n=0
X(4) = x(0)W80 + x(1)W84 + x(2)W88 + x(3)W812 + x(4)W816 + x(5)W820 + x(6)W824 + x(7)W828
X(4) = 1W80 + 1W84 + 1W88 + 1W812 + 0W816 + 0W820 + 0W824 + 0W828
X(4) = 1 × 1 + 1 × (−1) + 1 × (1) + 1(−1) = 0
Hint: WNa = WNa+N ; ∴ W88 = W80+8 = W80 and W812 = W84+8 = W84

when k = 5
7
X 7
X
X(5) = x(n)W85×n = x(n) × W85n
n=0 n=0
X(5) = x(0)W80 + x(1)W85 + x(2)W810 + x(3)W815 + x(4)W820 + x(5)W825 + x(6)W830 + x(7)W835
X(5) = 1W80 + 1W85 + 1W810 + 1W815 + 0W820 + 0W825 + 0W830 + 0W835
X(5) = 1 × 1 + 1 × (−0.707 + j0.707) + 1 × (−j) + 1(0.707 + j0.707) = 1 + j0.414
Hint: WNa = WNa+N ; ∴ W810 = W82+8 = W82 and W815 = W87+8 = W87

when k = 6
7
X 7
X
X(6) = x(n)W86×n = x(n) × W86n
n=0 n=0
X(6) = x(0)W80 + x(1)W86 + x(2)W812 + x(3)W818 + x(4)W824 + x(5)W830 + x(6)W836 + x(7)W842
X(6) = 1W80 + 1W86 + 1W812 + 1W818 + 0W824 + 0W830 + 0W836 + 0W842
X(6) = 1 × 1 + 1 × (j) + 1 × (−1) + 1(−j) = 0
Hint: WNa = WNa+N ; ∴ W818 = W810+8 = W810 = W82+8 = W82

when k = 7
7
X 7
X
X(7) = x(n)W87×n = x(n) × W87n
n=0 n=0
X(7) = x(0)W80 + x(1)W87 + x(2)W814 + x(3)W821 + x(4)W828 + x(5)W835 + x(6)W842 + x(7)W849
X(7) = 1W80 + 1W87 + 1W814 + 1W821 + 0W828 + 0W835 + 0W842 + 0W849
X(7) = 1 × 1 + 1 × (0.707 + j0.707) + 1 × (j) + 1(−0.707 + j0.707) = 1 + j2.414
10 Module-1

Hint: WNa = WNa+N ; ∴ W814 = W86+8 = W86 and W821 = W813+8 = W813 = W85+8 = W85
X(k)={4, 1-j2.414, 0, 1-j0.414, 0, 1+j0.414, 0, 1+j2.414}

Example 1.5: Compute DFT of the sequence x(n) = {0, 1, 2, 3} using matrix method.

 Solution:

W40 W40 W40 W40 W40 W40 W40 W40 0

W40 W41 W42 W43 W40 W41 W42 W43 1
X(k) = × x(n) = ×
W40 W42 W44 W46 W40 W42 W44 W46 2
W40 W43 W46 W49 W40 W43 W46 W49 3

j2π∗0
W40 = e− 4 = cos(0) − j sin(0) = 1

j2π∗1
   
W41 = e− 4 = cos 2π
4 − j sin 2π
4 = −j

j2π∗2
   
W42 = e− 4 = cos 4π
4 − j sin 4π
4 = −1

j2π∗3
   
W43 = e− 4 = cos 6π
4 − j sin 6π
4 =j

W44 = W40+4 = W40 = 1

W46 = W42+4 = W42 = −1

W49 = W45+4 = W45 = W41+4 = W41 = −j

1 1 1 1 0 0+1+2+3 6
1 −j −1 j 1 0 − j − 2 + 3j −2 + 2j
X(k) = × = =
1 −1 1 −1 2 0−1+2−3 −2
1 j −1 −j 3 0 + j − 2 − 3j −2 − 2j

X(k)={6, -2+2j, -2, -2-2j}

Example 1.7: Find the 4-point DFT of the sequence, x(n) = cos(nπ/4). Also plot |X(k)| and
∠X(k).
Digital Signal Processing 11

 Solution:
nπ


x(n) = cos 4  
0π
n = 0; x(0) = cos =1
4
n = 1; x(1) = cos 1π = 0.707
4
n = 2; x(2) = cos 2π =0
4
n = 3; x(3) = cos 3π
4 = −0.707
x(n) = {1, 0.707, 0, − 0.707}

W40 W40 W40 W40 1 1 1 1 1

W40 W41 W42 W43 1 −j −1 j 0.707
X(k) = × x(n) = ×
W40 W42 W44 W46 1 −1 1 −1 0
W40 W43 W46 W49 1 j −1 −j −0.707

1 1 ∠0◦
1 − j1.414 1.73 ∠ − 54.73◦
X(k) = =
1 1 ∠0◦
1 + j1.414 1.73 ∠54.73◦

|X(k)| ∟X(k)
2
1 50°
k k
0 1 2 3
-50°

Example 1.8: Find the 4-point DFT of the sequence, x(n) = 6 + sin(2nπ/N ).

 Solution:  
2nπ
x(n) = 6 + sin
 N 
x(0) = 6 + sin 2×0×π =6
 4 
x(1) = 6 + sin 2×1×π =7
 4 
x(2) = 6 + sin 2×2×π =6
 4 
x(3) = 6 + sin 2×3×π
4 =5
x(n) = {6, 7, 6, 5}
12 Module-1

W40 W40 W40 W40 1 1 1 1 6 24

W40 W41 W42 W43 1 −j −1 j 7 −2j
X(k) = × x(n) = × =
W40 W42 W44 W46 1 −1 1 −1 6 0
W40 W43 W46 W49 1 j −1 −j 5 2j

X(k)={24, -2j, 0, 2j}

Example 1.9: Compute the N -point DFT of x(n) = an ; 0 ≤ n ≤ N − 1. Also, determine the
DFT of the sequence, x(n) = 0.5n u(n); 0 ≤ n ≤ 3.

 Solution:
x(n) = an ; 0 ≤ n ≤ N − 1

N
X −1
X(k) = x(n)WNkn
n=0

N −1 N −1
j2π×kn
an e −
X X
X(k) = an WNkn = N

n=0 n=0

 −j2πk
N
N −1  n 1− a·e N
X −j2πk
X(k) = a·e N = −j2πk
n=0 1−a·e N

j2πkN
−
1−aN ×e N 1−aN ×e−j2πk
X(k) = −
j2πk = −
j2πk
1−a·e N 1−a·e N

e−j2πk = cos(2πk) − j sin(2πk) = 1 − j × 0 = 1

1−aN
X(k) = −
j2πk
1−a·e N

For, x(n) = 0.5n u(n); 0 ≤ n ≤ 3, a = 0.5 & N = 4.

1−aN 1−0.54
X(k) = −
j2πk = j2πk
1−a·e N 1−0.5·e− 4

0.9375
X(k) = jπk
1−0.5×e− 2
Digital Signal Processing 13

0.9375 0.9375
k = 0; X(0) = jπ0 = 0.5 = 1.875
1−0.5×e− 2

k = 1; X(1) = 0.9375
jπ1 = 0.9375
1+j0.5 = 0.9375
1.118b26.56◦ = 0.8385∠ − 26.56◦ = 0.75 − j0.375
1−0.5×e− 2

0.9375 0.9375
k = 2; X(2) = jπ2 = 1−0.5(−1) = 0.625
1−0.5×e− 2

k = 3; X(3) = 0.9375
jπ3 = 0.9375
1−j0.5 = 0.9375
1.118b−26.56◦ = 0.8385∠26.56◦ = 0.75 + j0.375
1−0.5×e− 2

X(k)={1.875, 0.75-j0.375, 0.625, 0.75+j0.375}

1.4 Properties of DFT

1.4.1 Periodicity

if x(n + N ) = x(n) for all n

then X(k + N ) = X(k) for all k
Proof:
N
X −1
X(k) = DF T {x(n)} = x(n)WNkn
n=0
To prove periodicity, put k = k + N
N −1
X (k+N )n
X(k + N ) = x(n)WN
n=0
N
X −1
X(k + N ) = x(n)WNkn WNN n
n=0
WNN n = e−j2πN n/N = e−j2πn = 1
N
X −1
∴ X(k + N ) = x(n)WNkn
n=0
X(k + N ) = X(k)

1.4.2 Linearity

If DFT {a · x1 (n) + b · x2 (n)} = a · X1 (k) + b · X2 (k), k = 0, 1, 2, . . . , N − 1 with X1 (k)

and X2 (k) are the DFT’s of the sequences x1 (n) and x2 (n), respectively of length N .
14 Module-1

Proof:
N
X −1
X(k) = DF T {x(n)} = x(n)WNkn
n=0
Letting x(n) = {a · x1 (n) + b · x2 (n)}
N
X −1
X(k) = DF T {a · x1 (n) + b · x2 (n)} = {a · x1 (n) + b · x2 (n)} WNkn
n=0
N
X −1 N
X −1
X(k) = DF T {a · x1 (n) + b · x2 (n)} = a · x1 (n)WNkn + b · x2 (n)WNkn
n=0 n=0
N
X −1 N
X −1
X(k) = DF T {a · x1 (n) + b · x2 (n)} = a x1 (n)WNkn + b x2 (n)WNkn
n=0 n=0
X(k) = DF T {a · x1 (n) + b · x2 (n)} = a · X1 (k) + b · X2 (k)

DFT {a · x1 (n) + b · x2 (n)} = a · X1 (k) + b · X2 (k)

Example 1.10: Find the 4-point DFT of the sequence, x(n) = cos(nπ/4) + sin(nπ/4), use
linearity property. Also, verify the result.

 Solution:

n x1 (n) = cos(nπ/4) x2 (n) = sin(nπ/4)

0 1 0
1 0.707 0.707
2 0 1
3 -0.707 0.707

X1 (k)=DFT {x1 (n)} and X2 (k)=DFT {x2 (n)}

W40 W40 W40 W40 1 1 1 1 1 1

W40 W41 W42 W43 1 −j −1 j 0.707 1 − j1.414
X1 (k) = × x1 (n) = ∗ =
W40 W42 W44 W46 1 −1 1 −1 0 1
W40 W43 W46 W49 1 j −1 −j −0.707 1 + j1.414
Digital Signal Processing 15

W40 W40 W40 W40 1 1 1 1 0 2.414

W40 W41 W42 W43 1 −j −1 j 0.707 −1
X2 (k) = × x2 (n) = ∗ =
W40 W42 W44 W46 1 −1 1 −1 1 −0.414
W40 W43 W46 W49 1 j −1 −j 0.707 −1

Finally, applying the linearity property

1 2.414 3.414
1 − j1.414 −1 −j1.414
X(k) = X1 (k) + X2 (k) = + =
1 −0.414 0.586
1 + j1.414 −1 j1.414

Verification using matrix method: x(n) = cos(nπ/4) + sin(nπ/4) = {1, 1.414, 1, 0}

W40 W40 W40 W40 1 1 1 1 1 3.414

W40 W41 W42 W43 1 −j −1 j 1.414 −j1.414
X(k) = ∗ x(n) = ∗ =
W40 W42 W44 W46 1 −1 1 −1 1 0.586
W40 W43 W46 W49 1 j −1 −j 0 j1.414

1.4.3 Symmetry: real-valued sequences

If the sequence x(n), n = 0, 1, 2, ..., N − 1 is real, then its DFT is such that
X(k) = X ∗ (N − k); k = 0, 1, ..., N − 1.
Proof:
N
X −1
X(k) = x(n)WNkn
n=0
Taking conjugates on both the sides, we get
N −1
x∗ (n)WN−kn
X
X ∗ (k) =
n=0
since x(n) is real, we have x∗ (n) = x(n)
N −1
x(n)WN−kn
X
X ∗ (k) =
n=0
N −1
x(n)WN−kn WNN n
X
X ∗ (k) =
n=0
16 Module-1

j2πN n
since WNN n = e− N = e−j2πn = 1
N −1
X (N −k)n
X ∗ (k) = x(n)WN = X(N − k)
n=0
X ∗ (k) = X(N − k)

∴ X(k) = X ∗ (N − k)

Example 1.11: The first five points of the 8-point DFT of a real valued sequence are
{0.25, 0.5-j0.5, 0, 0.5-j0.86, 0}. Find the remaining three points.

 Solution:
*
X(1) X(3) X(4) X(5) X(7)
X(0) X(2) X(6)

*
*
Given, X(0) = 0.25, X(1) = 0.5 − j0.5, X(2) = 0, X(3) = 0.5 − j0.86, X(4) = 0

X(k) = X ∗ (N − k)
X(k) = X ∗ (8 − k)
X(5) = X ∗ (8 − 5) = X ∗ (3) = 0.5 + j0.86
X(6) = X ∗ (8 − 6) = X ∗ (2) = 0
X(7) = X ∗ (8 − 7) = X ∗ (1) = 0.5 + j0.5

X(k)= {0.25, 0.5-j0.5, 0, 0.5-j0.86, 0, 0.5+j0.86, 0, 0.5+j0.5}.

Example 1.12: Compute the 5-point DFT of the sequence, x(n) = {1, 0, 1, 0, 1} and hence
verify the symmetry property.

 Solution: Given, x(n) = {1, 0, 1, 0, 1}

Digital Signal Processing 17

W50 W50 W50 W50 W50 W50 W50 W50 W50 W50 1
W50 W51 W52 W53 W54 W50 W51 W52 W53 W54 0
X(k) = W50 W52 W54 W56 W58 × x(n) = W50 W52 W54 W56 W58 × 1
W50 W53 W56 W59 W512 W50 W53 W56 W59 W512 0
W50 W54 W58 W512 W516 W50 W54 W58 W512 W516 1
1 1 1 1 1 1
1 0.309 − j0.951 −0.809 − j0.587 −0.809 + j0.587 0.309 + j0.951 0
X(k) = 1 −0.809 − j0.587 0.309 + j0.951 0.309 − j0.951 −0.809 + j0.587 × 1
1 −0.809 + j0.587 0.309 − j0.951 0.309 + j0.951 −0.809 − j0.587 0
1 0.309 + j0.951 −0.809 + j0.587 −0.809 − j0.587 0.309 − j0.951 1
3
0.5 + j0.364
X(k) = 0.5 + j1.538
0.5 − j1.538
0.5 − j0.364

X(k)={3, 0.5+j0.364, 0.5+j1.538, 0.5-j1.538, 0.5-j0.364}

Verification:
X(k) = X ∗ (N − k)
X(k) = X ∗ (5 − k)
k = 1; X(1) = X ∗ (5 − 1) = X ∗ (4)
k = 2; X(2) = X ∗ (5 − 2) = X ∗ (3)

Linear shift v/s Circular shift

Let us consider the sequence, x(n) = {0, 1, 2, 3, 4}

ie., x(0) = 0, x(1) = 1, x(2) = 2, x(3) = 3, x(4) = 4

Linear Shift: Circular shift:

y(n) = x(n − 2) y(n) = x((n − 2))5
x(n − 1) = {0, 0, 1, 2, 3, 4} x((n − 1))5 = {4, 0, 1, 2, 3}
x(n − 2) = {0, 0, 0, 1, 2, 3, 4} x((n − 2))5 = {3, 4, 0, 1, 2}
18 Module-1

x(n) x(n-2) x((n-1))5 x((n-2))5

4 4 4 4

3 3 3 3

2 2 2 2

1 1 1 1

0 1 2 3 4 n 0 1 2 3 4 5 6 n 0 1 2 3 4 n 0 1 2 3 4 n
Linear shift: y(n)=x(n) Linear shift: y(n)=x(n-2) Circular shift: y(n)=x((n-1))5 Circular shift: y(n)=x((n-2))5

1.4.4 Circular time shift

If, DFT{x(n)} = X(k)

Then, DFT {x((n − m))N } = WNmk · X(k), 0 ≤ k ≤ N − 1
Proof:
−1
1 NX
x(n) = X(k)WN−kn
N k=0
−1
1 NX −k(n−m)
x(n − m) = X(k)WN
N k=0
since the shift is circular, we can write the above equation as
−1
1 NX −k(n−m)
x((n − m))N = X(k)WN
N k=0
−1
1 NX
x((n − m))N = X(k)WN−kn · WNkm
N k=0
−1 h
1 NX i
x((n − m))N = X(k) · WNkm · WN−kn
N k=0
h i
x((n − m))N = IDFT X(k) · WNkm
DF T {x((n − m))N } = WNmk X(k)

Example 1.13: Find the 4-point DFT of the sequence, x(n) = {1, −1, 1, −1}. Also, using
time shift property, find the DFT of the sequence, y(n) = {x((n − 2))4 } .

 Solution: Given, x(n) = {1, −1, 1, −1}

Digital Signal Processing 19

W40 W40 W40 W40 1 1 1 1 1 0

W40 W41 W42 W43 1 −j −1 j −1 0
X(k) = × x(n) = × =
W40 W42 W44 W46 1 −1 1 −1 1 4
W40 W43 W46 W49 1 j −1 −j −1 0

X(k)={0, 0, 4, 0}

using time shift property,

DF T {y(n)} = DF T {x((n − 2))4 }

Here, N = 4 & m = 2
Y (k) = WNmk X(k) = W42k X(k)
k = 0; Y (0) = W42×0 X(0) = 1 ∗ 0 = 0
k = 1; Y (1) = W42×1 X(1) = −1 ∗ 0 = 0
k = 2; Y (2) = W42×2 X(2) = 1 ∗ 4 = 4
k = 3; Y (3) = W42×3 X(3) = −1 ∗ 0 = 0

Y(k)={0, 0, 4, 0}

Example 1.14: Suppose x(n) is a sequence defined as (0, 1, 2, 3, 4, 5, 6, 7). Obtain

(i) y(n) = {x((n − 2))8 }
(ii) z(n) = {x((n + 2))8 }
(iii) Y (k)
(iv) Z(k)

 Solution: Given, x(n) = {0, 1, 2, 3, 4, 5, 6, 7}

(i)
x((n − 1))8 = (7, 0, 1, 2, 3, 4, 5, 6)
x((n − 2))8 = (6, 7, 0, 1, 2, 3, 4, 5)

(ii)
x((n + 1))8 (1, 2, 3, 4, 5, 6, 7, 0)
x((n + 2))8 (2, 3, 4, 5, 6, 7, 0, 1)
20 Module-1

(iii)
Y (k) = DFT of y(n) = DF T {x((n − 2))8 }
Applying time shift property, N = 8 & m = 2
Y (k) = W82k · X(k)

(iv)
Z(k) = DFT of z(n) = DF T {x((n + 2))8 }
Applying time shift property, N = 8 & m = −2
Z(k) = W8−2k · X(k)

Example 1.15: Let X(k) denote a 6-point DFT of a length-6 real sequence, x(n) =
{1, −1, 2, 3, 0, 0}. Without computing the IDFT, determine the length-6 sequence, y(n) whose
6-point DFT is given by, Y (k) = W32k · X(k).

 Solution: Given, x(n) = {1, −1, 2, 3, 0, 0}

2k 2∗2k 4k
Y (k) = W32k X(k) = e−j2π 3 X(k) = e−j2π 3∗2 X(k) = e−j2π 6 X(k)
DF T {x((n − m))N } = WNmk · X(k)
n o
{x((n − m))N } = IDF T WNmk · X(k)
m=4&N =6
n o
x((n − 4))6 = IDFT W64k · X(k) = IDFT(Y (k))
IDFT(Y (k)) = x((n − 4))6
y(n) = x((n − 4))6
x(n) {1, −1, 2, 3, 0, 0}
x((n − 1))8 {0, 1, −1, 2, 3, 0}
x((n − 2))8 {0, 0, 1, −1, 2, 3}
x((n − 3))8 {3, 0, 0, 1, −1, 2}
x((n − 4))8 {2, 3, 0, 0, 1, −1}

y(n) = x((n − 4))6 = {2, 3, 0, 0, 1, −1}

1.4.5 Circular frequency shift (multiplication by exponential in time-domain)

n o
If DFT{x(n)} = X(k), then DFT WN−ln x(n) = X((k − l))N
Digital Signal Processing 21

Proof:
N
X −1
X(k) = x(n)WNkn
n=0
N −1
X (k−l)n
X(k − l) = x(n)WN
n=0

Since the shift in frequency is circular

N −1
x(n)WNkn · WN−ln
X
∴ X((k − l))N =
n=0
N −1 h i
x(n)WN−ln · WNkn
X
X((k − l))N =
n=0
n o
X((k − l))N = DFT WN− ln x(n)

Example 1.16: Compute the 4-point DFT of the sequence x(n) = {1, 0, 1, 0}. Also, find y(n),
if Y (k) = X((k − 2))4

 Solution: Given, x(n) = {1, 0, 1, 0}

W40 W40 W40 W40 1 1 1 1 1 2

W40 W41 W42 W43 1 −j −1 j 0 0
X(k) = × x(n) = × =
W40 W42 W44 W46 1 −1 1 −1 1 2
W40 W43 W46 W49 1 j −1 −j 0 0

X(k)={2, 0, 2, 0}

Given, Y (k) = X((k − 2))4

n o
Using circular frequency shift property, X((k − l))N = DFT WN− ln · x(n)
N =4&l=2
n o
Y (k) = X((k − 2))4 = DFT W4−2n x(n)
∴ y(n) = W4−2n x(n)
y(0) = W4−2×0 x(0) = 1 × 1 = 1
y(1) = W4−2×1 x(1) = 0
y(2) = W4−2×2 x(2) = 1 × 1 = 1
y(3) = W4−2×3 x(3) = 0
22 Module-1

y(n)={1, 0, 1, 0}

h  i
1 1 2π N
Example 1.17: If, w(n) = 2 + 2 cos N n− 2 ; 0 ≤ n ≤ N − 1. What is the DFT of the
sequence, y(n) = x(n) × w(n)? keep the answer in terms of X(k).

 Solution:
1 1 2π N
  
w(n) = + cos n− ;0 ≤ n ≤ N − 1
2 2 N 2
 
2π N 2π N
1 1  ej N (n− 2 ) + e−j N (n− 2 ) 
w(n) = +
2 2 2
1 1 j 2π (n− N ) 1 −j 2π (n− N )
w(n) = + e N 2 + e N 2
2 4 4
1 1 2π 2πN 1 2π 2πN
w(n) = + ej N n · e−j N 2 + e−j N n · ej N 2
2 4 4
1 1 2π 1 2π
w(n) = + ej N n · e−jπ + e−j N n · ejπ
2 4 4
1 1 j 2π n 1 2π
w(n) = + e N · (−1) + e−j N n · (−1)
2 4 4
1 1 −n 1 n
w(n) = − WN − WN
2 4 4
Given, y(n) = x(n) × w(n)
1 1 −n 1 n
 
∴ y(n) = x(n) × − WN − WN
2 4 4
1 1 −n 1 n
y(n) = x(n) − WN x(n) − WN x(n)
2 4 4
1 1 n o 1
Y (k) = X(k) − DF T WN−n x(n) − DF T {WNn x(n)}
2 4 4

Y (k) = 12 X(k) − 41 X((k − 1))N − 41 X((k + 1))N

1.4.6 Inner product (Parseval’s theorem)

If DFT x(n) = X(k) and y(n) = Y (k)

N −1 −1
1 NX
x∗ (n)y(n) = X ∗ (k)Y (k)
X

n=0
N k=0
Digital Signal Processing 23

Proof:
From the definition of IDFT
−1
1 NX
x(n) = X(k)WN−kn
N k=0
−1
1 NX
x∗ (n) = X ∗ (k)WNkn
N k=0
N −1 N −1 −1
1 NX
!
∗
X ∗ (k)WNkn y(n)
X X
∴ x (n)y(n) =
n=0 n=0
N k=0
N −1 N −1 N −1
!
X
∗ 1 X
∗
X
x (n)y(n) = X (k) y(n)WNkn
n=0
N k=0 n=0
N −1 N −1
1
x∗ (n)y(n) = X ∗ (k)Y (k)
X X

n=0
N k=0

Corollary:
If y(n) = x(n), we get
N −1 N −1
x∗ (n)x(n) =
X X
|x(n)|2
n=0 n=0
N −1 N −1
1
X ∗ (k)X(k)
X X
|x(n)|2 =
n=0
N k=0
N −1 −1
X
21 NX
|x(n)| = |X(k)|2
n=0
N k=0

Example 1.18: Find the energy of the 4-point sequence x(n) = sin(2πn/N ); 0 ≤ n ≤ 3 using
time-domain and frequency domain approaches.

 Solution:
 
2π
x(n) = sin Nn ;0 ≤ n ≤ 3
x(n) = {0, 1, 0, −1}
Time-domain approach:
N
X −1 4−1
X 2
X
E= |x(n)|2 = |x(n)|2 = |x(n)|2 = 02 + 12 + 02 + 12 = 2 J.
n=0 n=0 n=0
Frequency-domain approach:
N −1 −1
X 1 NX
E= |x(n)|2 = |X(k)|2
n=0
N k=0
24 Module-1

W40 W40 W40 W40 1 1 1 1 0 0

W40 W41 W42 W43 1 −j −1 j 1 −2j
X(k) = × x(n) = × =
W40 W42 W44 W46 1 −1 1 −1 0 0
W40 W43 W46 W49 1 j −1 −j −1 2j

X(k) = {0, −2j, 0, 2j}

N
X −1
E= 1
N |X(k)|2
k=0

1 1
E= 4 {0 + 4 + 0 + 4} = 4 × 8 = 2 J.

Example 1.19: Let x(n) = {1, 2, 0, 3, −2, 4, 7, 5}. Evaluate the following
(i) X(0)
(ii) X(4)
7
X
(iii) X(k)
k=0
X7
(iv) |X(k)|2
k=0

N −1
 Solution: DFT of x(n) = X(k) =
X
x(n)WNkn
n=0
(i) when k = 0;

7
X 7
X
X(0) = x(n)W80×n = x(n) = 1 + 2 + 0 + 3 − 2 + 4 + 7 + 5 = 20
n=0 n=0

(ii) when k = 4;

7 7 7 7
2π
x(n)e−j x(n)e−j×π×n =
X X X X
X(4) = x(n)W84×n = 8
4×n
= x(n)(−1)n
n=0 n=0 n=0 n=0
X7
X(4) = x(n)(−1)n = x(0) − x(1) + x(2) − x(3) + x(4) − x(5) + x(6) − x(7)
n=0
X(4) = 1 − 2 + 0 − 3 − 2 − 4 + 7 − 5 = −8
Digital Signal Processing 25

(iii)
−1
1 NX
x(n) = X(k)WN−kn
N k=0
Letting n = 0
−1
1 NX
x(0) = X(k)WN−k×0
N k=0
−1
1 NX
x(0) = X(k) × 1
N k=0
N
X −1
N × x(0) = X(k)
k=0
2−1
X
8 × x(0) = X(k)
k=0
7
X
8×1= X(k) = 8
k=0
7
X
X(k) = 8
k=0

(iv)
N −1 −1
X 1 NX
E= |x(n)|2 = |X(k)|2
n=0
N k=0
8−1
X 1 8−1
X
|x(n)|2 = |X(k)|2
n=0
8 k=0
7 7
X 1X
|x(n)|2 = |X(k)|2
n=0
8 k=0
X7 7
X
2
∴ |X(k)| = 8 × |x(n)|2
k=0 n=0
7
X
2
|X(k)| = 8(1 + 4 + 0 + 9 + 4 + 16 + 49 + 25) = 864
k=0

Example 1.20: Let x(n) = {1, −2, 3, −4, 5, −6}. Evaluate the following without computing
its DFT
(i) X(0)
(ii) X(3)
5
X
(iii) X(k)
k=0
26 Module-1

5
X
(iv) |X(k)|2
k=0
5
X
(v) (−1)k X(k)
k=0

 Solution: Given, x(n) = {1, −2, 3, −4, 5, −6}

(i) when k = 0;

5
X 5
X
X(0) = x(n)W60×n = x(n) = 1 − 2 + 3 − 4 + 5 − 6 = −3
n=0 n=0

(ii) when k = 3;

5 5 5 5
2π
x(n)e−j x(n)e−j∗π×n =
X X X X
X(3) = x(n)W63×n = 6
3n
= x(n)(−1)n
n=0 n=0 n=0 n=0
X5
X(3) = x(n)(−1)n = x(0) − x(1) + x(2) − x(3) + x(4) − x(5)
n=0
X(3) = 1 + 2 + 3 + 4 + 5 + 6 = 21

(iii)
−1
1 NX
x(n) = X(k)WN−kn
N k=0
Letting n = 0
−1
1 NX
x(0) = X(k)WN−k×0
N k=0
−1
1 NX
x(0) = X(k) × 1
N k=0
N
X −1
N × x(0) = X(k)
k=0
6−1
X
6 × x(0) = X(k)
k=0
5
X
6×1= X(k) = 6
k=0
Digital Signal Processing 27
5
X
X(k) = 6
k=0

(iv)
6−1
X 1 6−1
X
E= |x(n)|2 = |X(k)|2
n=0
6 k=0
5 5
X 1X
|x(n)|2 = |X(k)|2
n=0
6 k=0
X5 5
X
2
∴ |X(k)| = 6 × |x(n)|2
k=0 n=0
5
X
2
|X(k)| = 6(1 + 4 + 9 + 16 + 25 + 36) = 546
k=0

5
X
|X(k)|2 = 546
k=0
5
X
(v) Given, (−1)k X(k)
k=0

 k  k −3k

k −6jπ −2×3jπ  −j2π
(−1)k can be written as (−1)k = ejπ = e −6 = e −6 = e 6

N −1
X(k)WN−kn
X
1
x(n) = N
k=0
Letting n = 3
6−1
X(k)W6−k×3
X
1
x(3) = 6
k=0
5
X(k) × W6−3k
X
6 × x(3) =
 i=0
−j2π −3k
  6jπ
k
k
W6−3k = e 6 = e 6 = ejπ = (−1)k
5
X
∴ 6 × x(3) = X(k) × (−1)k
k=0
5
X
X(k) × (−1)k = 6 × (−4) = −24
k=0

5
X
X(k) × (−1)k = −24.
k=0
28 Module-1

1.4.7 Circular folding

If, DFT{x(n)} = X(k), then, DFT {x((−n))N } = X((−k))N

Proof:
N
X −1
X(k) = x(n)WNkn
n=0
Let m = N − n
n = 0; m=N −0=N
n = N − 1; m = N − N + 1 = 1
1
X k(N −m)
X(k) = x(N − m)WN
m=N
N −1
X k(N −m)
X(k) = x(N − m)WN
m=0
Since m is a dummy variable, replace m with n.
N −1
X k(N −n)
X(k) = x(N − n)WN
n=0
N −1
x(N − n)WN−kn × WNkN
X
X(k) =
n=0
N −1
x(N − n)WN−kn × 1
X
X(k) =
n=0
N −1
x(N − n)WN−kn
X
X(k) =
n=0
N −1
x(N − n)Wn−(N −k)n
X
∴ X(N − k) =
n=0
N −1
x(N − n)WN−N n × WNkn
X
X(N − k) =
n=0
X(N − k) = DFT{x(N − n)}
x((−k))N = DFT {x((−n))N }

Example 1.21: Compute the 4-point DFT of the sequence, x(n) = {1, 2, 1, 0}. Also, find Y (k)
if, y(n) = {x((−n))N }

 Solution:
Given, x(n) = {1, 2, 1, 0}
Digital Signal Processing 29

W40 W40 W40 W40 1 1 1 1 1 4

W40 W41 W42 W43 1 −j −1 j 2 −2j
X(k) = × x(n) = × =
W40 W42 W44 W46 1 −1 1 −1 1 0
W40 W43 W46 W49 1 j −1 −j 0 2j

X(k)={4, -2j, 0, 2j}

Since x(n) is real, it may be noted that the symmetry property:

X(k) = X ∗ (N − k)
y(n) = x((−n))N
Y (k) = X((−k))N = X ∗ (k)
∴ Y (k) = {4, 2j, 0, −2j}

1.4.8 Symmetry: DFT of real even and real odd sequences

If x(n) = xe (n) + xo (n), where xe (n) is the even part and xo (n) is the odd part of the
sequence x(n), then DFT{xe (n)} is purely real and DFT{xo (n)} is purely imaginary.
Proof:
1
xe (n) = {x(n) + x(−n)}
2
1
xe (n) = {x(n) + x((−n))N }
2
1 1
DF T {xe (n)} = DF T {x(n)} + DF T {x((−n))N }
2 2
1 1
DF T {xe (n)} = X(k) + X((−k))N
2 2
1
DF T {xe (n)} = [X(k) + X((−k))N ]
2
1
DF T {xe (n)} = [X(k) + X ∗ (k)]
2
Let, X(k) = A + jB & X ∗ (k) = A − jB
1
DF T {xe (n)} = [A + jB + A + jB]
2
DF T {xe (n)} = A = Purely real.
30 Module-1

1
x0 (n) = {x(n) − x(−n)}
2
1
x0 (n) = {x(n) − x((−n))N }
2
1 1
DF T {xo (n)} = DF T {x(n)} − DF T {x((−n))N }
2 2
1 1
DF T {xo (n)} = X(k) − X((−k))N
2 2
1
DF T {xo (n)} = [X(k) − X((−k))N ]
2
1
DF T {xo (n)} = [X(k) − X ∗ (k)]
2
1
DF T {xo (n)} = [A + jB − A + jB]
2
DF T {xo (n)} = jB = Purely imaginary.

Example 1.22: Consider the following sequences of length-8 defined for 0 ≤ n ≤ 7.

(i) x1 (n) = (2, 2, 2, 0, 0, 0, 2, 2)
(ii) x2 (n) = (2, 2, 0, 0, 0, 0, −2, −2)
(iii) x3 (n) = (0, 2, 2, 0, 0, 0, −2, −2)
(iv) x4 (n) = (0, 2, 2, 0, 0, 0, 2, 2)
Which sequences have a real-valued 8-point DFT? Which sequences have an imaginary valued
8-point DFT?

 Solution: To circularly fold the sequence, enter the sequence in the clockwise direction
along the circumference of a circle with an equal spacing between successive points and read
the sequence anticlockwise.
(i)
2

2 2

2 2 x1(n)
x1((-n))8
0 0
0

x1 ((−n))8 = (2, 2, 2, 0, 0, 0, 2, 2). It is observed that x1 (n) = x1 ((−n))8 , is an even se-

quence and hence X1 (k) will be purely real.
Digital Signal Processing 31

(ii)
2

-2 2

-2 0 x2(n)
x2((-n))8
0 0
0

x2 ((−n))8 = (2, −2, −2, 0, 0, 0, 0, 2). It is observed that x2 (n) is neither even nor odd and
hence X2 (k) is neither purely real nor purely imaginary.
(iii)
0

-2 2

-2 2 x3(n)
x3((-n))8
0 0
0

x3 ((−n))8 = (0, −2, −2, 0, 0, 0, 2, 2). It is observed that x3 (n) is odd sequence and hence
and hence X3 (k) is purely imaginary.
(iv)
0

2 2

2 2 x4(n)
x4((-n))8
0 0
0

x4 ((−n))8 = (0, 2, 2, 0, 0, 0, 2, 2). It is observed that x4 (n) = x4 ((−n))8 , is an even se-

quence and hence X4 (k) will be purely real.
32 Module-1

1.4.9 Circular convolution in time

Let x(n) and h(n) be two sequences of length N . Then,

N
X −1 N
X −1
y(n) = x(n) ⊗N h(n) = x((n − m))N × h(m) = x(m) × h((n − m))N
m=0 m=0
Proof: Consider the block diagram shown

X(k)
x(n) DFT{}
Y(k)
IDFT{} y(n)
h(n) DFT{}
H(k)

Y (k) = X(k)H(k)
y(n) = IDF T {X(k)H(k)}
−1
1 NX
y(n) = {X(k)H(k)}WN−kn
N k=0
where,
N
X −1
X(k) = x(i)WNik
i=0
N
X −1
H(k) = h(m)WNmk
m=0

Substituting the values of X(k) and H(k) in y(n)

−1 N −1 −1
1 NX N
h(m)WNmk WN−kn
X X
y(n) = x(i)WNik
N k=0 i=0 m=0

Interchanging the order of summation

−1 −1 −1
1 NX N N
WNik WNmk WN−kn
X X
y(n) = x(i) h(m)
N i=0 m=0 k=0
−1 −1 −1
1 NX N
X N
X (i+m−n)k
y(n) = x(i) h(m) WN
N i=0 m=0 k=0

when i = n − m
i = 0; m = n
i = N − 1; m = n − N + 1
Digital Signal Processing 33

n−N
X+1 N −1 N −1
1 X X (n−m+m−n)k
y(n) = x(n − m) h(m) WN
N m=n m=0 k=0
N −1 N −1 N −1
1 X X X
y(n) = x(n − m) h(m) 1
N m=0 m=0 k=0
N −1 N −1
1 X X
y(n) = x((n − m))N h(m) × N
N m=0 m=0
N
X −1
y(n) = x((n − m))N h(m) = x(n) ⊗N h(n)
m=0

Example 1.23: Compute x(n) ⊗N h(n). Given, x(n) = {1, 1, 1} and h(n) = {1, −2, 2}.

N −1
 Solution: y(n) = x(n) ⊗N h(n) =
X
x((n − m))N h(m); N = 3
m=0

n x(m) h((n − m))N y(n)

0 (1, 1, 1) (1, 2, −2) 1 × 1 + 1 × 2 + 1 × −2 = 1
1 (1, 1, 1) (−2, 1, 2) 1 × −2 + 1 × 1 + 1 × 2 = 1
2 (1, 1, 1) (2, −2, 1) 1 × 2 + 1 × −2 + 1 × 1 = 1

y(n)={1, 1, 1}

Example 1.24: Compute, x(n) ⊗N h(n). Using time domain and frequency domain (Stock-
ham’s method) approach. Given, x(n) = {1, 2, 3, 1} and h(n) = {4, 3, 2, 2}.

 Solution: Time domain approach:

N
X −1
y(n) = x(n) ⊗N h(n) = x((n − m))N h(m); N = 4
m=0

n x(m) h((n − m))N y(n)

0 (1, 2, 3, 1) (4, 2, 2, 3) 1 × 4 + 2 × 2 + 2 × 3 + 1 × 3 = 17
1 (1, 2, 3, 1) (3, 4, 2, 2) 1 × 3 + 2 × 4 + 3 × 2 + 2 × 1 = 19
2 (1, 2, 3, 1) (2, 3, 4, 2) 1 × 2 + 2 × 3 + 3 × 4 + 1 × 2 = 22
3 (1, 2, 3, 1) (2, 2, 3, 4) 1 × 2 + 2 × 2 + 3 × 3 + 1 × 4 = 19

y(n)={17, 19, 22, 19}

34 Module-1

Frequency domain approach:

1. Obtain DFT of x(n) = X(k).

2. Obtain DFT of h(n) = H(k).

3. Multiply X(k) and H(k), ie., Y (k) = X(k) × H(k).

4. Take IDFT of Y (k) = y(n).

W40 W40 W40 W40 1 1 1 1 1 7

W40 W41 W42 W43 1 −j −1 j 2 −2 − j
X(k) = × x(n) = × =
W40 W42 W44 W46 1 −1 1 −1 3 1
W40 W43 W46 W49 1 j −1 −j 1 −2 + 2j

W40 W40 W40 W40 1 1 1 1 4 11

W40 W41 W42 W43 1 −j −1 j 3 2−j
H(k) = × h(n) = × =
W40 W42 W44 W46 1 −1 1 −1 2 1
W40 W43 W46 W49 1 j −1 −j 2 2+j

Y (k) = X(k) × H(k) = {77, −5, 1, −5}

y(n) = IDF T {Y (k)}

W4−0 W4−0 W4−0 W4−0 1 1 1 1 77 17

W4−0 W4−1 W4−2 W4−3 1 j −1 −j −5 19
y(n) = 1/4 × Y (k) = 1/4 × =
W4−0 W4−2 W4−4 W4−6 1 −1 1 −1 1 22
W4−0 W4−3 W4−6 W4−9 1 −j −1 j −5 19

y(n)={17, 19, 22, 19}

Example 1.25: Compute, y(n) = x(n) ⊗N h(n) using Stockham’s method. Given, x1 (n) =
n + 1, 0 ≤ n ≤ 3. and x2 (n) = cos(nπ), 0 ≤ n ≤ 3.

 Solution: Given, x1 (n) = {1, 2, 3, 4} and x2 (n) = {1, −1, 1, −1}

Digital Signal Processing 35

1 1 1 1 1 10
1 −j −1 j 2 −2 + 2j
X1 (k) = =
1 −1 1 −1 3 −2
1 j −1 −j 4 −2 − 2j

1 1 1 1 1 0
1 −j −1 j −1 0
X2 (k) = =
1 −1 1 −1 1 4
1 j −1 −j −1 0

X1 (k) × X2 (k) = {0, 0, −8, 0}

y(n) = x1 (n) ⊗4 x2 (n) = IDFT {X1 (k) × X2 (k)}
1 1 1 1 0 −8
1 1 j −1 −j 0 1 8
y(n) = 4 = 4
1 −1 1 −1 −8 −8
1 −j −1 j 0 8

y(n)={-2, 2, -2, 2}

Example 1.25: Compute circular convolution using DFT-IDFT method and matrix method.
Given, x1 (n) = n and x2 (n) = cos(nπ/2). Assume N = 4.

 Solution: Given, x1 (n) = n = {0, 1, 2, 3} and x2 (n) = cos(nπ/2) = {1, 0, −1, 0}.
DFT-IDFT method or Stockham’s method or Frequency domain approach:

1 1 1 1 0 6
1 −j −1 j 1 −2 + 2j
X1 (k) = =
1 −1 1 −1 2 −2
1 j −1 −j 3 −2 − 2j

1 1 1 1 1 0
1 −j −1 j 0 2
X2 (k) = =
1 −1 1 −1 −1 0
1 j −1 −j 0 2
36 Module-1

X1 (k) × X2 (k) = {0, −4 + 4j, 0, −4 − 4j}

y(n) = x1 (n) ⊗4 x2 (n) = IDF T {X1 (k) ∗ X2 (k)}
1 1 1 1 0 −8
1 1 j −1 −j −4 + 4j 1 −8
y(n) = 4 = 4
1 −1 1 −1 0 8
−1 −j −1 j −4 − 4j 8

y(n)={-2, -2, 2, 2}

Matrix method:

0 & 3 & 2 & 1 1 −2

1 & 0 & 3 & 2 0 −2
y(n) = x1 (n) ⊗4 x2 (n) = =
2 & 1 & 0 & 3 −1 2
3 2 1 0 0 2

y(n)={-2, -2, 2, 2}

Example 1.26: Compute circular convolution x1 (n) = {1, 2, 3, 1} and x2 (n) = {4, 3, 2, 2}

 Solution: Given, x1 (n) = {1, 2, 3, 1} and x2 (n) = {4, 3, 2, 2}

1 & 1 & 3 & 2 4 17

2 & 1 & 1 & 3 3 19
y(n) = x1 (n) ⊗4 x2 (n) = =
3 & 2 & 1 & 1 2 22
1 3 2 1 2 19

y(n)={17, 19, 22, 19}

 MODULE - II
Linear filtering methods based on the DFT: Use of DFT in Linear Filtering, Filtering
of Long data Sequences. Fast-Fourier-Transform (FFT) algorithms: Efficient Computation of
the DFT: Radix-2 FFT algorithms for the computation of DFT and IDFT-decimation-in-time
and decimation-in-frequency algorithms.

2.1 Introduction
Linear filtering is one of the most powerful image enhancement methods. It is a process
in which part of the signal frequency spectrum is modified by the transfer function of the
filter. Linear filtering of a signal can be seen as a controlled scaling of the signal components
in the frequency domain. DFT provides an alternative approach to time domain convolution.
It can be used to perform linear filtering in frequency domain. The advantage is that, having
knowledge of faster DFT techniques likes of FFT, a computationally higher efficient algorithm
can be developed for digital computer computation in comparison with time domain approach.

2.2 Use of DFT in Linear Filtering

Since the DFT provides a discrete frequency representation of a finite-duration sequence
in the frequency domain, it is interesting to explore its use as a computational tool for linear
system analysis and, especially, for linear filtering. Suppose that we have a finite-duration
sequence x(n) of length L which excites an FIR filter of length M . Without loss of generality,
let,
x(n) = 0, n < 0 and n ≥ L
h(n) = 0, n < 0 and n ≥ M

where h(n) is the impulse response of the FIR filter. The output sequence y(n) of the FIR
filter can be expressed in the time domain as the convolution of x(n) and h(n), that is

M
X −1
y(n) = h(k)x(n − k)
k=0

37
38 Module-2

Since h(n) and x(n) are finite-duration sequences, their convolution is also finite in duration.
In fact, the duration of y(n) is L + M − 1. The frequency-domain equivalent is

Y (ω) = X(ω)H(ω)

If the sequence y(n) is to be represented uniquely in the frequency domain by samples of its
spectrum Y (w) at a set of discrete frequencies, the number of distinct samples must equal or
exceed (L + M − 1). Therefore, a DFT of size N ≥ L + M − 1 is required to represent y(n)
in the frequency domain. Now if,

Y (k) = Y (ω)|ω=2πk/N ; k = 0, 1, . . . , N − 1
= X(ω)H(ω)|ω=2πk/N ; k = 0, 1, . . . , N − 1

then,
Y (k) = X(k)H(k); k = 0, 1, . . . , N − 1

The DFT provides an efficient way to calculate the time-domain convolution of two signals.
One of the most important applications of the DFT is calculating the time-domain convolution
of signals. This can be achieved by multiplying the DFT representation of the two signals
and then calculating the inverse DFT of the result as shown in Fig. 2.1.

x(n) M-1 zeros N-point

length L padding DFT
y(n)
N-point N-point
length
DFT IDFT
N=L+M-1
h(n) L-1 zeros N-point
length M padding DFT

Fig. 2.1. Linear convolution of x(n) and h(n) in frequency domain.

Example 2.1: Given x(n) = {1, 2, 3, 4} and h(n) = {1, 2, 2} compute

i) circular convolution
ii) linear convolution
iii) linear convolution using circular convolution.
Digital Signal Processing 39

 Solution: Given x(n) = {1, 2, 3, 4} and h(n) = {1, 2, 2}

()i) Circular convolution

1 4 3 2 1 15
2 1 4 3 2 12
y(n) = x(n) ⊗4 h(n) = =
3 2 1 4 2 8
4 3 2 1 0 14

y(n) = x(n) ⊗4 h(n) = {15, 12, 8, 14}

(ii) Linear convolution

x(n) 1 2 3 4
h(n) 1 2 2
2 4 6 8
2 4 6 8
1 2 3 4
1 4 9 14 14 8

y(n) = x(n) ∗ h(n) = {1, 4, 9, 14, 14, 8}

(iii) Linear convolution using circular convolution

• x(n) = {1, 2, 3, 4} ; length of x(n) is M = 4.

• h(n) = {1, 2, 2}; length of h(n) is N = 3.

• y(n) = x(n) ∗ h(n) will have a length of (M + N − 1) = 4 + 3 − 1 = 6. Padding zeros,

• x(n) = {1, 2, 3, 4, 0, 0} and h(n) = {1, 2, 2, 0, 0, 0}

1 0 0 4 3 2 1 1
2 1 0 0 4 3 2 4
3 2 1 0 0 4 2 9
y(n) = x(n) ⊗6 h(n) = =
4 3 2 1 0 0 0 14
0 4 3 2 1 0 0 14
0 0 4 3 2 1 0 8

y(n) = x(n) ∗ h(n) = {1, 4, 9, 14, 14, 8}

40 Module-2

Example 2.2: Obtain linear convolution using circular convolution. Also, verify the result.
x(n) = {1, 1, 0, −1, −1} and h(n) = {1, 2, 3, 2, 1}.

 Solution: Given, x(n) = {1, 1, 0, −1, −1} and h(n) = {1, 2, 3, 2, 1}

• x(n) = {1, 1, 0, −1, −1} ; length of x(n) is M = 5.

• h(n) = {1, 2, 3, 2, 1}; length of h(n) is N = 5.

• y(n) = x(n) ∗ h(n) will have a length of (M + N − 1) = 5 + 5 − 1 = 9. Padding zeros,

• x(n) = {1, 1, 0, −1, −1, 0, 0, 0, 0} and h(n) = {1, 2, 3, 2, 1, 0, 0, 0, 0}

1 0 0 0 0 1 2 3 2 1 1
2 1 0 0 0 0 1 2 3 1 3
3 2 1 0 0 0 0 1 2 0 5
2 3 2 1 0 0 0 0 1 −1 4
y(n) = h(n) ⊗9 x(n) = 1 2 3 2 1 0 0 0 0 −1 = 0
0 1 2 3 2 1 0 0 0 0 −4
0 0 1 2 3 2 1 0 0 0 −5
0 0 0 1 2 3 2 1 0 0 −3
0 0 0 0 1 2 3 2 1 0 −1

y(n) = {1, 3, 5, 4, 0, −4, −5, −3, −1}

Verification:
x(n) 1 1 0 −1 −1
h(n) 1 2 3 2 1
1 1 0 −1 −1
2 2 0 −2 −2
3 3 0 −3 −3
2 2 0 −2 −2
1 1 0 −1 −1
1 3 5 4 0 −4 −5 −3 −1

Example 2.3: An FIR filter has the impulse response, h(n) = {1, 2, 3}. Determine the
response of the filter to the input sequence, x(n) = {1, 2}. Use DFT and IDFT. Also, verify
the result. .
Digital Signal Processing 41

 Solution: Given, x(n) = {1, 2, 3} and h(n) = {1, 2}

• h(n) = {1, 2, 3} ; length of h(n) is M = 3.

• x(n) = {1, 2}; length of x(n) is N = 2.

• y(n) = x(n) ∗ h(n) will have a length of (M + N − 1) = 3 + 2 − 1 = 4. Padding zeros,

• h(n) = {1, 2, 3, 0} and x(n) = {1, 2, 0, 0}

DFT-IDFT method or Stockham’s method or Frequency domain approach:

1 1 1 1 1 3
1 −j −1 j 2 1 − 2j
H(k) = =
1 −1 1 −1 3 −1
1 j −1 −j 0 1 + 2j

1 1 1 1 1 6
1 −j −1 j 2 −2 − 2j
X(k) = =
1 −1 1 −1 0 2
1 j −1 −j 0 −2 + 2j

X(k) × H(k) = {18, −6 + 2j, −2, −6 − 2j}

y(n) = x(n) ⊗4 h(n) = IDF T {X(k) × H(k)}
1 1 1 1 18 4
1 1 j −1 −j −6 + 2j 1 16
y(n) = 4 = 4
1 −1 1 −1 −2 28
−1 −j −1 j −6 − 2j 24

y(n)={1, 4, 7, 6}

Verification:
x(n) 1 2 3
h(n) 1 2
2 4 6
1 2 3
1 4 7 6
42 Module-2

2.3 Filtering of Long data Sequences

Suppose, the input sequence x(n) of long duration is to be processed with a system having
finite duration impulse response by convolving the two sequences. Since, the linear filtering
performed via DFT involves operation on a fixed size data block, the input sequence is divided
into different fixed size data block before processing. The successive blocks are then processed
one at a time and the results are combined to produce the net result. As the convolution is
performed by dividing the long input sequence into different fixed size sections, it is called
sectioned convolution. A long input sequence is segmented to fixed size blocks, prior to FIR
filter processing.

[x1 (n) + x2 (n)] ∗ h(n) = x1 (n) ∗ h(n) + x2 (n) ∗ h(n)

Two methods are used to evaluate the discrete convolution:

1. Overlap-add method: Because convolution is linear, the output of a long sequence can
be calculated by simply summing the outputs of each block of the input. In this method,
overlapping the tail of the output from the previous block with the beginning of the
output from the present block.

Input signal:
L L L

x1(n) M-1
zeros
x21(n) M-1
zeros
Output signal: x31(n) M-1
zeros
y1(n)
Add
M-1 points y2(n)
Add
M-1 points y3(n)

Fig. 2.2. Overlap-add method.

2. Overlap-save method: Rather than sectioning the input and then calculating the output
Digital Signal Processing 43

from overlapped outputs from the individual input blocks, we will section the output
and then use whatever part of the input contributes to that output block. This method
has also been called overlap-discard because, rather than adding the overlapping output
blocks, the overlapping portion of the output blocks are discarded.

Input signal:
L L L

M-1
zeros
x1(n)
M-1 point
overlap x21(n)
M-1 point
overlap x31(n)
Output signal:
y1(n)

discard
y2(n)
M-1 points
discard
y3(n)
M-1 points
discard
M-1 points

Fig. 2.3. Overlap-save method.

Example 2.4: Consider a FIR filter with impulse response, h(n) = {3, 2, 1, 1}. If the input
is x(n) = {1, 2, 3, 3, 2, 1, −1, −2, −3, 5, 6, −1, 2, 0, 2, 1}. Find the output using overlap-add
method assuming the length of block as 7.

 Solution:

h(n) = {3, 2, 1, 1}; M = 4

x(n) = {1, 2, 3, 3, 2, 1, −1, −2, −3, 5, 6, −1, 2, 0, 2, 1}. since block length is 7. ie., N = 7
N =M +L−1⇒7=4+L−1⇒L=4
h(n) = {3, 2, 1, 1, 0, 0, 0}
44 Module-2

x1 (n) = {1, 2, 3, 3, 0, 0, 0} ; y1 (n) = x1 (n) ⊗7 h(n)

x2 (n) = {2, 1, −1, −2, 0, 0, 0}; y2 (n) = x2 (n) ⊗7 h(n)
x3 (n) = {−3, 5, 6, −1, 0, 0, 0}; y3 (n) = x3 (n) ⊗7 h(n)
x4 (n) = {2, 0, 2, 1, 0, 0, 0} ; y4 (n) = x4 (n) ⊗7 h(n)

1 0 0 0 3 3 2 3 3
2 1 0 0 0 3 3 2 8
3 2 1 0 0 0 3 1 14
y1 (n) = x1 (n) ⊗7 h(n) = 3 3 2 1 0 0 0 1 = 18
0 3 3 2 1 0 0 0 11
0 0 3 3 2 1 0 0 6
0 0 0 3 3 2 1 0 3

2 0 0 0 −2 −1 1 3 6
1 2 0 0 0 −2 −1 2 7
−1 1 2 0 0 0 −2 1 1
y2 (n) = x2 (n) ⊗7 h(n) = −2 −1 1 2 0 0 0 1 = −5
0 −2 −1 1 2 0 0 0 −4
0 0 −2 −1 1 2 0 0 −3
0 0 0 −2 −1 1 2 0 −2

−3 0 0 0 −1 6 5 3 −9
5 −3 0 0 0 −1 6 2 9
6 5 −3 0 0 0 −1 1 25
y3 (n) = x3 (n) ⊗7 h(n) = −1 6 5 −3 0 0 0 1 = 11
0 −1 6 5 −3 0 0 0 9
0 0 −1 6 5 −3 0 0 5
0 0 0 −1 6 5 −3 0 −1
Digital Signal Processing 45

2 0 0 0 1 2 0 3 6
0 2 0 0 0 1 2 2 4
2 0 2 0 0 0 1 1 8
y4 (n) = x4 (n) ⊗7 h(n) = 1 2 0 2 0 0 0 1 = 9
0 1 2 0 2 0 0 0 4
0 0 1 2 0 2 0 0 3
0 0 0 1 2 0 2 0 1

y1 (n) 3 8 14 18 11 6 3
y2 (n) 6 7 1 −5 −4 −3 −2
y3 (n) −9 9 25 11 9 5 −1
y4 (n) 6 4 8 9 4 3 1
y(n) 3 8 14 18 17 13 4 −5 −13 6 23 11 15 9 7 9 4 3 1

y(n) = x(n) ∗ h(n) = {3, 8, 14, 18, 17, 13, 4, −5, −13, 6, 23, 11, 15, 9, 7, 9, 4, 3, 1}.

Example 2.5: Determine the response of an LTI system with h(n) = {1, −1, 2} for an input
x(n) = {1, 0, 1, −2, 1, 2, 3, −1, 0, 2}. Employ overlap-add method with block length, N = 4.

 Solution:

h(n) = {1, −1, 2}; M = 3

x(n) = {1, 0, 1, −2, 1, 2, 3, −1, 0, 2}. Since block length is 4. ie., N = 4
N =M +L−1⇒4=3+L−1⇒L=2
x1 (n) = {1, 0, 0, 0} ; y1 (n) = x1 (n) ⊗4 h(n)
x2 (n) = {1, −2, 0, 0}; y2 (n) = x2 (n) ⊗4 h(n)
x3 (n) = {1, 2, 0, 0} ; y3 (n) = x3 (n) ⊗4 h(n)
x4 (n) = {3, −1, 0, 0}; y4 (n) = x4 (n) ⊗4 h(n)
x5 (n) = {0, 2, 0, 0} ; y5 (n) = x5 (n) ⊗4 h(n)

1 0 0 0 1 1
0 1 0 0 −1 −1
y1 (n) = x1 (n) ⊗4 h(n) = =
0 0 1 0 2 2
0 0 0 1 0 0
46 Module-2

1 0 0 −2 1 1
−2 1 0 0 −1 −3
y2 (n) = x2 (n) ⊗4 h(n) = =
0 −2 1 0 2 4
0 0 −2 1 0 −4

1 0 0 2 1 1
2 1 0 0 −1 1
y3 (n) = x3 (n) ⊗4 h(n) = =
0 2 1 0 2 0
0 0 2 1 0 4

3 0 0 −1 1 3
−1 3 0 0 −1 −4
y4 (n) = x4 (n) ⊗4 h(n) = =
0 −1 3 0 2 7
0 0 −1 3 0 −2

0 0 0 2 1 0
2 0 0 0 −1 2
y5 (n) = x5 (n) ⊗4 h(n) = =
0 2 0 0 2 −2
0 0 2 0 0 4

y1 (n) 1 −1 2 0
y2 (n) 1 −3 4 −4
y3 (n) 1 1 0 4
y4 (n) 3 −4 7 −2
y5 (n) 0 2 −2 4
y(n) 1 −1 3 −3 5 −3 3 0 7 0 −2 4

y(n) = {1, −1, 3, −3, 5, −3, 3, 0, 7, 0, −2, 4}.

Example 2.6: Find the output of a linear filter, given the impulse response h(n) = {1, 2} and
input, x(n) = {1, 2, −1, 2, 3, −2, −3, −1, 1, 1, 2, −1} using overlap-add method.

 Solution:
h(n) = {1, 2}; M = 2
x(n) = {1, 2, −1, 2, 3, −2, −3, −1, 1, 1, 2, −1}
N =M +L−1
N = 2M = 22 = 4
Digital Signal Processing 47

N =M +L−1⇒4=2+L−1⇒L=3
h(n) = {1, 2}; M = 2
x(n) = {1, 2, −1, 2, 3, −2, −3, −1, 1, 1, 2, −1}
N =M +L−1
N = 2M = 22 = 4
N =M +L−1⇒4=2+L−1⇒L=3
x1 (n) = {1, 2, −1, 0} ; y1 (n) = x1 (n) ⊗4 h(n)
x2 (n) = {2, 3, −2, 0} ; y2 (n) = x2 (n) ⊗4 h(n)
x3 (n) = {−3, −1, 1, 0}; y3 (n) = x3 (n) ⊗4 h(n)
x4 (n) = {1, 2, −1, 0} ; y4 (n) = x4 (n) ⊗4 h(n)
h(n) = {1, 2, 0, 0}

1 0 −1 2 1 1
2 1 0 −1 2 4
y1 (n) = x1 (n) ⊗ h(n) = =
−1 2 1 0 0 3
0 −1 2 1 0 −2

2 0 −2 3 1 2
3 2 0 −2 2 7
y2 (n) = x2 (n) ⊗ h(n) = =
−2 3 2 0 0 4
0 −2 3 2 0 −4

−3 0 1 −1 1 −3
−1 −3 0 1 2 −7
y3 (n) = x3 (n) ⊗ h(n) = =
1 −1 −3 0 0 −1
0 1 −1 −3 0 2

1 0 −1 2 1 1
2 1 0 −1 2 4
y4 (n) = x4 (n) ⊗ h(n) = =
−1 2 1 0 0 3
0 −1 2 1 0 −2
48 Module-2

y1 (n) 1 4 3 −2
y2 (n) 2 7 4 −4
y3 (n) −3 −7 −1 2
y4 (n) 1 4 3 −2
y(n) 1 4 3 0 7 4 −7 −7 −1 3 4 3 −2

y(n) = x(n) ∗ h(n) = {1, 4, 3, 0, 7, 4, −7, −7, −1, 3, 4, 3, −2}.

Example 2.7: Find the output of a linear filter given the impulse response h(n) = {1, 2} and
input, x(n) = {1, 2, −1, 2, 3, −2, −3, −1, 1, 1, 2, −1} using overlap-save method.

 Solution:

h(n) = {1, 2}; M = 2

x(n) = {1, 2, −1, 2, 3, −2, −3, −1, 1, 1, 2, −1}
N =M +L−1
N = 2M = 22 = 4
N =M +L−1⇒4=2+L−1⇒L=3
h(n) = {1, 2, 0, 0}
x1 (n) = {1, 2, −1}; x2 (n) = {2, 3, −2}; x3 (n) = {−3, −1, 1}; x4 (n) = {1, 2, −1}

x1 (n) 0 1 2 −1
x2 (n) −1 2 3 −2
x3 (n) −2 −3 −1 1
x4 (n) 1 1 2 −1
x5 (n) −1 0 0 0

x1 (n) = {0, 1, 2, −1} ; y1 (n) = x1 (n) ⊗4 h(n)

x2 (n) = {−1, 2, 3, −2} ; y2 (n) = x2 (n) ⊗4 h(n)
x3 (n) = {−2, −3, −1, 1}; y3 (n) = x3 (n) ⊗4 h(n)
x4 (n) = {1, 1, 2, −1} ; y4 (n) = x4 (n) ⊗4 h(n)
x5 (n) = {−1, 0, 0, 0} ; y5 (n) = x5 (n) ⊗4 h(n)
Digital Signal Processing 49

0 −1 2 1 1 −2
H

H
1 0 −1 2 2 1
y1 (n) = x1 (n) ⊗4 h(n) = =
2 1 0 −1 0 4
−1 2 1 0 0 3

−1 −2 3 2 1 −5
H

H
2 −1 −2 3 2 0
y2 (n) = x2 (n) ⊗4 h(n) = =
3 2 −1 −2 0 7
−2 3 2 −1 0 4

−2 1 −1 −3 1 0
A
−3 −2 1 −1 2 −7
y3 (n) = x3 (n) ⊗4 h(n) = =
−1 −3 −2 1 0 −7
1 −1 −3 −2 0 −1

1 −1 2 1 1 −1
H

H
1 1 −1 2 2 3
y4 (n) = x4 (n) ⊗4 h(n) = =
2 1 1 −1 0 4
−1 2 1 1 0 3

−1 0 0 0 1 −1
H

H
0 −1 0 0 2 −2
y5 (n) = x5 (n) ⊗4 h(n) = =
0 0 −1 0 0 0
0 0 0 −1 0 0

y1 (n) 1 4 3
y2 (n) 0 7 4
y3 (n) −7 −7 −1
y4 (n) 3 4 3
y5 (n) −2 0 0
y(n) 1 4 3 0 7 4 −7 −7 −1 3 4 3 −2 0 0

y(n) = x(n) ∗ h(n) = {1, 4, 3, 0, 7, 4, −7, −7, −1, 3, 4, 3, −2}

Example 2.8: Find the output of a linear filter given the impulse response h(n) = {1, 1, 1}
and input, x(n) = {3, −1, 0, 1, 3, 2, 0, 1, 2, 1} using overlap-save method.

 Solution:
50 Module-2

h(n) = {1, 1, 1}; M = 3

x(n) = {3, −1, 0, 1, 3, 2, 0, 1, 2, 1}
N =M +L−1
N = 2M = 23 = 8
N =M +L−1⇒8=3+L−1⇒L=6
x1 (n) = {3, −1, 0, 1, 3, 2}
x2 (n) = {0, 1, 2, 1, 0, 0}

x1 (n) 0 0 3 −1 0 1 3 2
x2 (n) 3 2 0 1 2 1 0 0

x1 (n) = {0, 0, 3, −1, 0, 1, 3, 2}

x2 (n) = {3, 2, 0, 1, 2, 1, 0, 0}

0 2 3 1 0 −1 3 0 1 ∗
0 0 2 3 1 0 −1 3 1 ∗
3 0 0 2 3 1 0 −1 1 3
−1 3 0 0 2 3 1 0 0 2
y1 (n) = x1 (n) ⊗8 h(n) = =
0 −1 3 0 0 2 3 1 0 2
1 0 −1 3 0 0 2 3 0 0
3 1 0 −1 3 0 0 2 0 4
2 3 1 0 −1 3 0 0 0 6

3 0 0 1 2 1 0 2 1 ∗
2 3 0 0 1 2 1 0 1 ∗
0 2 3 0 0 1 2 1 1 5
1 0 2 3 0 0 1 2 0 3
y2 (n) = x2 (n) ⊗8 h(n) = =
2 1 0 2 3 0 0 1 0 3
1 2 1 0 2 3 0 0 0 4
0 1 2 1 0 2 3 0 0 3
0 0 1 2 1 0 2 3 0 1

y(n) = {3, 2, 2, 0, 4, 6, 5, 3, 3, 4, 3, 1}.

Example 2.9: Find the output of a linear filter given the impulse response h(n) = {1, −1}
and input, x(n) = {1, 1, 1, 1, 1, 3, 1, 1, 4, 2, 1, 1, 3, 1} using overlap-save method. Use only 5
point circular convolution.
Digital Signal Processing 51

 Solution:
h(n) = {1, −1}; M = 2
x(n) = {1, 1, 1, 1, 1, 3, 1, 1, 4, 2, 1, 1, 3, 1}
N =M +L−1
N =M +L−1⇒5=2+L−1⇒L=4
x(n) = {1, 1, 1, 1 |, 1, 3, 1, 1 |, 4, 2, 1, 1 |, 3, 1}
x1 (n) = {1, 1, 1, 1}
x2 (n) = {1, 3, 1, 1}
x3 (n) = {4, 2, 1, 1}
x4 (n) = {3, 1, 0, 0}

x1 (n) 0 1 1 1 1
x2 (n) 1 1 3 1 1
x3 (n) 1 4 2 1 1
x4 (n) 1 3 1 0 0

x1 (n) = {0, 1, 1, 1, 1}
x2 (n) = {1, 1, 3, 1, 1}
x3 (n) = {1, 4, 2, 1, 1}
x4 (n) = {1, 3, 1, 0, 0}
h(n) = {1, −1, 0, 0, 0}

0 1 1 1 1 1 ∗
1 0 1 1 1 −1 1
y1 (n) = x1 (n) ⊗5 h(n) = 1 1 0 1 1 0 = 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0

1 1 1 3 1 1 ∗
1 1 1 1 3 −1 0
y2 (n) = x2 (n) ⊗5 h(n) = 3 1 1 1 1 0 = 2
1 3 1 1 1 0 −2
1 1 3 1 1 0 0
52 Module-2

1 1 1 2 4 1 ∗
4 1 1 1 2 −1 3
y3 (n) = x3 (n) ⊗5 h(n) = 2 4 1 1 1 0 = −2
1 2 4 1 1 0 −1
1 1 2 4 1 0 0

1 0 0 1 3 1 ∗
3 1 0 0 1 −1 2
y4 (n) = x4 (n) ⊗5 h(n) = 1 3 1 0 0 0 = −2
0 1 3 1 0 0 −1
0 0 1 3 1 0 0

y(n) = x(n) ∗ h(n) = {1, 0, 0, 0, 0, 2, −2, 0, 3, −2, −1, 0, 2, −2, −1, 0}.

2.4 Computational Complexity of DFT & Efficient Computation of the DFT

By the definition of DFT,

N −1 N −1
2πkn
x(n)e−j
X X
X(k) = x(n)WNkn = N ; k = 0, 1, 2, . . . , N − 1
n=0 n=0

Let, N = 4.

3
X
X(k) = x(n)W4kn Multiplication Addition
n=0
3
X
k = 0; X(0) = x(n)W40×n = x(0)W40 + x(1)W40 + x(2)W40 + x(3)W40 4 3
n=0
X3
k = 1; X(1) = x(n)W41×n = x(0)W40 + x(1)W41 + x(2)W42 + x(3)W43 4 3
n=0
X3
k = 2; X(2) = x(n)W42×n = x(0)W40 + x(1)W42 + x(2)W44 + x(3)W46 4 3
n=0
X3
k = 3; X(3) = x(n)W43×n = x(0)W40 + x(1)W43 + x(2)W46 + x(3)W49 4 3
n=0
Total 16 12

Hence, for N = 4.
No. of complex computation required for X(k) is 16.
No. of complex addition required for X(k) is 12.
In general,
Digital Signal Processing 53

No. of complex computation required for X(k) is N 2 .

No. of complex addition required for X(k) is N (N − 1).

Complex multiplication:

(a + jb) × (c + jd) = (a × c) + j(a × d) + j(b × c) + j 2 (b × d)

(a + jb) × (c + jd) = (a × c) + j(a × d) + j(b × c) − (b × d)
(a + jb) × (c + jd) = (a × c) − (b × d) + j(a × d + b × c)
∴ 1 complex multiplication = 4 real multiplications + 2 real additions.
Note: subtraction is also counted as addition in signal processing.

Complex addition:

(a + jb) + (c + jd) = (a + c) + j(b + d)

∴ 1 complex addition = 2 real additions.
In summary,

Operation Number of computations

Complex multiplications N2
Complex additions N (N − 1)
Real multiplications 4N 2
Real additions 2N (N − 1) + 2N 2 = 4N 2 − 2N
Trigonometric functions 2N 2

Example 2.10: Calculate the number of complex multiplications, complex additions, real
multiplications, real additions and trigonometric functions required for computing DFT for
N = 64 using direct method.

 Solution:

Operation Number of computation

Complex multiplications N2 642 = 4096
Complex additions N (N − 1) 64(64 − 1) = 4032
54 Module-2

Operation Number of computation

Real multiplications 4N 2 4 × 642 = 16, 384
Real additions 4N 2 − 2N 4 × 642 − 2 × 64 = 16, 256
Trigonometric functions 2N 2 2 × 642 = 8, 192

2.4.1 Phase factor/twiddle factor

Twiddle factors are a set of values that is used to speed up DFT and IDFT calculations.
Twiddle factors are mathematically represented as: WN = e−j2π/N .

2.4.2 Properties of Phase factor/twiddle factor

1. Periodicity property of WN : WNk+N = WNk

j2π(k+N ) j2πk j2πN j2πk

WNk+N = e− N = e− N e− N = e− N e−j2π

e−j2π = cos 2π − j sin 2π = 1 − j × 0 = 1

j2πk
WNk+N = e− N = WNk

k+N/2
2. Symmetry property of WN : WN = −WNk

j2π k+ N
( )
k+ N 2 j2πk j2πN j2πk
WN 2
= e− N = e− N e− 2N = e− N e−jπ

e−jπ = cos π − j sin π = −1 − j × 0 = −1

k+ N j2πk j2πk
WN 2
= e− N ∗ −1 = −e− N = −WNk

3. WN2 = WN/2

j2π(2) j2π
− N/2
WN2 = e− N =e = WN/2

2.5 Fast Fourier Transform (FFT)

The DFT is one of the most powerful tools in digital signal processing. The DFT enables
us to conveniently analyze and design systems in frequency domain. We have seen that the
Digital Signal Processing 55

computational part is too long with this technique. We want to reduce that. This can be done
through FFT or fast Fourier transform. So, we can say FFT is nothing but computation of
DFT in an algorithmic format, where the computational part will be reduced. The main idea
of FFT algorithms is to decompose an N-point DFT into transformations of smaller length.
For example, if we devise a hypothetical algorithm which can decompose a 1024-point DFT
into two 512-point DFTs.

2.5.1 Radix-2 DIT-FFT Algorithm

The radix-2 decimation-in-time algorithm rearranges the DFT equation into two parts: a
sum over the even-numbered discrete-time indices n = (0, 2, 4, ..., N − 2) and a sum over the
odd-numbered indices n = (1, 3, 5, ..., N − 1).
Let x(n) be a N -point sequence where N is assumed to be power of 2. Decimate/break
the sequence into 2 sequences of length N/2, where one is even indexed values of x(n) and
other is odd indexed values of x(n). ie.,

xe (n) = x(2n); n = 0, 1, ....., N/2 − 1.

xo (n) = x(2n + 1); n = 0, 1, ....., N/2 − 1.
N
X −1
X(k) = x(n)WNkn
n=0
(N/2)−1 (N/2)−1
X X (2n+1)k
X(k) = x(2n)WN2nk + x(2n + 1)WN
n=0 n=0
(N/2)−1 (N/2)−1
X X
X(k) = x(2n)WNnk /2 + W nk x(2n + 1)WNnk /2
n=0 n=0
nk
X(k) = Xe (k) + W Xo (k); 0 ≤ k ≤ N/2 − 1

Since, Xe (k) and Xo (k) are periodic interms of k with period N/2 and so for k = N/2, ....., N −
1, the values are same as those for k = 0, 1, ..., N/2 − 1.

(k+N/2)
∴ for k ≥ N/2; WN = −WNk
We can write,
(k−N/2)
X(k) = Xe (k − N/2) − WN Xo (k − N/2); k = N/2, ..., N − 1
Let us consider N = 8
X(k) = Xe (k) + W8k Xo (k)
X(k) = Xe (k − 4) − W8k−4 Xo (k − 4)
56 Module-2

k = 0; X(0) = Xe (0) + W80 Xo (0)

k = 1; X(1) = Xe (1) + W81 Xo (1)
k = 2; X(2) = Xe (2) + W82 Xo (2)
k = 3; X(3) = Xe (3) + W83 Xo (3)
k = 4; X(4) = Xe (0) − W80 Xo (0)
k = 5; X(5) = Xe (1) − W81 Xo (1)
k = 6; X(6) = Xe (2) − W82 Xo (2)
k = 7; X(7) = Xe (3) − W83 Xo (3)
This is called a decimation in time because the time samples are rearranged in alternating
groups, and a radix-2 algorithm because there are two groups. Fig. 2.4 graphically illustrates
the DIT-FFT computation for N = 8.

x(0)
xe(0)
x(1)
xe(1)
4-point x(2)
xe(2) DFT
x(3)
xe(3)

w80 x(4)
xoe(0)
w81 x(5)
xo(1)
4-point w82
xo(2) DFT x(6)
w83
xo(3) x(7)

Fig. 2.4. Decimation in time of a length N-DFT into two length-N/2 DFTs followed by
a combining stage.

2.5.2 Radix-2 DIF-FFT Algorithm

N
X −1
We know that, X(k) = x(n)WNkn . Decimate it into 2 sequences,
n=0
Digital Signal Processing 57

N/2−1 N −1
X X
X(k) = x(n)WNkn + x(n)WNkn
n=0 n=N/2

Let m = n − N/2
n = N/2; m = N/2 − N/2 = 0
n = N − 1; m = (N − 1) − N/2 = N/2 − 1
N/2−1 N/2−1
X X k(m+N/2)
X(k) = x(n)WNkn + x(m + N/2)WN
n=0 m=0

since m is dummy variable, replace m by n

N/2−1 N/2−1
X X k(n+N/2)
X(k) = x(n)WNkn + x(n + N/2)WN
n=0 n=0
N/2−1 N/2−1
X X kN/2
X(k) = x(n)WNkn + x(n + N/2)WNkn WN
n=0 n=0
kN/2 −j2πkN/N 2 −jπ k
WN =e = (e ) = (−1)k
N/2−1 N/2−1
X X
∴ X(k) = x(n)WNkn + (−1) k
x(n + N/2)WNkn
n=0 n=0
N/2−1
X
∴ X(k) = [x(n) + (−1)k x(n + N/2)]WNkn
n=0

Let us split even and odd sequences,

N/2−1
X
X(2k) = [x(n) + (−1)2k x(n + N/2)]WN2kn
n=0
N/2−1
X (2k+1)n
X(2k + 1) = [x(n) + (−1)2k+1 x(n + N/2)]WN
n=0
2k
since, (−1) = 1 & (−1)2k+1 = −1
N/2−1
X
X(2k) = [x(n) + x(n + N/2)]WN2kn
n=0
N/2−1
X (2k+1)n
X(2k + 1) = [x(n) − x(n + N/2)]WN
n=0

Let g1 (n) = x(n) + x(n + N/2)

g2 (n) = [x(n) − x(n + N/2)]WNn
58 Module-2

N/2−1
X
kn
X(2k) = g1 (n)WN/2
n=0
N/2−1
X
kn
X(2k + 1) = g2 (n)WN/2
n=0

Let, N = 8
g1 (n) = x(n) + x(n + 4); g2 (n) = [x(n) − x(n + 4)]W8n
g1 (0) = x(0) + x(4); g2 (0) = [x(0) − x(4)]W80
g1 (1) = x(1) + x(5); g2 (1) = [x(1) − x(5)]W81
g1 (2) = x(2) + x(6); g2 (2) = [x(2) − x(6)]W82
g1 (3) = x(3) + x(7); g2 (3) = [x(3) − x(7)]W83
This is called a decimation in frequency because the frequency samples are computed sepa-
rately in alternating groups, and a radix-2 algorithm because there are two groups. Fig. 2.5
graphically illustrates this form of the DFT computation.

g1(0)
x(0) x(0)
g1(1)
x(1) w8 0
4-point x(4)
w8 1 g1(2) DFT x(2)
x(2)
w8 2 g1(3)
x(6)
x(3)
w8 3

g2(0)
x(1)
x(4) g2(1)
4-point x(5)
x(5) g2(2) DFT x(3)
x(6) g2(3)
x(7)
x(7)

Fig. 2.5. Decimation in frequency of a length N-DFT into two length-N/2 DFTs preceded
by a pre-processing stage.

Normal and Bit reversed Addressing

Bit-reversed addressing is used for simplifying and speeding-up the access to the arrays in
FFT algorithms. In bit reversed addressing, transposed the original binary bits representing
Digital Signal Processing 59

the normal index order by reversing their positions. The most significant bit becomes the
least significant bit and the least significant bit becomes the most significant bit, the next
to the most significant bit becomes the next to the least significant bit, and the next to the
least significant bit becomes the next to the most significant bit, and so on.

Normal input Bit reversed output

000 = 0 000 = 0
001 = 1 100 = 4
010 = 2 010 = 2
011 = 3 110 = 6
100 = 4 001 = 1
101 = 5 101 = 5
110 = 6 011 = 3
111 = 7 111 = 7

Let, N = 23 = 8. ∴ N/2 = 4 = 100. Perform the addition from left to right (−→).

• Normal input = 000; bit reversed output = 000.

• 000+(N/2)=000+100=100; bit reversed output = 100.

• 100+(N/2)=100+100=010; bit reversed output = 010.

• 010+(N/2)=010+010=110; bit reversed output = 110.

• 110+(N/2)=110+100=001; bit reversed output = 001.

• 001+(N/2)=001+100=101; bit reversed output = 101.

• 101+(N/2)=101+100=011; bit reversed output = 011.

• 011+(N/2)=011+100=111; bit reversed output = 111.

Example 2.11: Using DIF-FFT algorithm compute DFT of the sequence, x(n) =
{1, 2, −1, 2, 4, 2, −1, 2}.

 Solution:
60 Module-2

Given, x(0) = 1, x(1) = 2, x(2) = −1, x(3) = 2, x(4) = 4, x(5) = 2, x(6) = −1, x(7) = 2.

(i) N/2 twiddle factors. Here N = 8

8
∴ = 4 twiddle factors. W80 = 1; W81 = 0.707 − j0.707; W82 = −j; W83 = −0.707 − j0.707
2
(ii) Input is normal and output is bit reversed.
(iii) Butterfly operation

a c=a+b

b d=(a-b)Wnr

(iv) Number of stages = log2 N = log2 8 = log2 23 = 3 log2 2 = 3 × 1 = 3.

A = x(0) + x(4) = 5 I =A+C =3 X(0) = I + J = 11

B = x(1) + x(5) = 4 J =B+D =8 X(4) = (I − J)W80 = −5
C = x(2) + x(6) = −2 K = [A − C]W80 = 7 X(2) = K + L = 7
D = x(3) + x(7) = 4 L = [B − D]W82 =0 X(6) = (K − L)W80 = 7
E = [x(0) − x(4)]W80 = −3 M = E + G = −3 X(1) = M + N = −3
F = [x(1) − x(5)]W81 = 0 N =F +H =0 X(5) = (M − N )W80 = −3
G = [x(2) − x(6)]W82 = 0 P = [E − G]W80 = −3 X(3) = P + Q = −3
H = [x(3) − x(7)]W83 = 0 Q = [F − H]W82 = 0 X(7) = (P − Q)W80 = −3
X(k) = {11, −3, 7, −3, −5, −3, 7, −3}

Example 2.12: Obtain 8-point DFT of the sequence x(n) = {2, 1, 2, 1} using radix-2 DIF-FFT
algorithm. Show all the results along signal flow graph.

 Solution:
Given, x(0) = 2, x(1) = 1, x(2) = 2, x(3) = 1, x(4) = 0, x(5) = 0, x(6) = 0, x(7) = 0.
Digital Signal Processing 61
A I
x(0) X(0)

B J
x(1) X(4)
w80
C K
x(2) X(2)
w80
D L
x(3) X(6)
w82 w8 0
E M
x(4) X(1)
w8 0
F N
x(5) X(5)
w8 1 w8 0
G P
x(6) X(3)
w8 2 w80
H Q
x(7) X(7)
w8 3 w82 w8 0

(i) N/2 twiddle factors. Here N = 8

8
∴ = 4 twiddle factors. W80 = 1; W81 = 0.707 − j0.707; W82 = −j; W83 = −0.707 − j0.707
2
(ii) Input is normal and output is bit reversed.
(iii) Butterfly operation

a c=a+b

b d=(a-b)Wnr

(iv) Number of stages = log2 N = log2 8 = log2 23 = 3 log2 2 = 3 × 1 = 3.

A = x(0) + x(4) = 2 I =A+C =4 X(0) = I + j = 6

B = x(1) + x(5) = 1 J =B+D =2 X(4) = (l − J)W80 = 2
C = x(2) + x(6) = 2 K = [A − C]W80 = 0 X(2) = K + L = 0
D = x(3) + x(7) = 1 L = [B − D]W82 = 0 X(6) = (K − L)W80 = 0
E = [x(0) − x(4)]W80 = 2 M = E + G = 2 − 2j X(1) = M + N = 2 − j3.414
F = [x(1) − x(5)]W81 = 0.707 − j0.707 N = F + H = −j1.414 X(5) = (M − N )W80 = 2 − j0.586
G = [x(2) − x(6)]W82 = −2j P = [E − G]W80 = 2 + 2j X(3) = P + Q = 2 + j0.586
H = [x(3) − x(7)]W83 = −0.707 − j0.707 Q = [F − H]W82 = −j1.414 X(7) = (P − Q)W80 = 2 + j3.414
62 Module-2

A I
x(0) X(0)

B J
x(1) X(4)
w80
C K
x(2) X(2)
w80
D L
x(3) X(6)
w82 w8 0
E M
x(4) X(1)
w8 0
F N
x(5) X(5)
w8 1 w8 0
G P
x(6) X(3)
w8 2
w80
H Q
x(7) X(7)
w8 3 w82 w8 0

X(k) = {6, 2 − j3.414, 0, 2 + j0.586, 2, 2 − j0.586, 0, 2 + j3.414}

Example 2.13: Obtain 8-point DFT of the sequence x(n) = {1, 1, 1, 1, 0, 0, 0, 0} using radix-2
DIT-FFT algorithm. Show all the results along signal flow graph.

 Solution:
Given, x(0) = 1, x(1) = 1, x(2) = 1, x(3) = 1, x(4) = 0, x(5) = 0, x(6) = 0, x(7) = 0.

(i) N/2 twiddle factors. Here N = 8

8
∴ = 4 twiddle factors. W80 = 1; W81 = 0.707 − j0.707; W82 = −j; W83 = −0.707 − j0.707
2
(ii) Input is bit reversed and output is normal.
(iii) Butterfly operation

a c=a+Wnrb

b d=a-Wnrb

(iv) Number of stages = log2 N = log2 8 = log2 23 = 3 log2 2 = 3 × 1 = 3.

Digital Signal Processing 63

A = x(0) + W80 x(4) = 1 I = A + W80 C = 2 X(0) = I + W80 M = 4

B = x(0) − W80 x(4) = 1 J = B + W82 D = 1 − j X(1) = J + W81 N = 1 − j2.414
C = x(2) + W80 x(6) = 1 K = A − W80 C = 0 X(2) = K + W82 P = 0
D = x(2) − W80 x(6) = 1 L = B − W82 D = 1 + j X(3) = L + W83 Q = 1 − j0.414
E = x(1) + W20 x(5) = 1 M = E + W20 G = 2 X(4) = I − W20 M = 0
F = x(1) − W20 x(5) = 1 N = F + W22 H = 1 − j X(5) = J − W21 N = 1 + j0.414
G = x(3) + W20 x(7) = 1 P = E − W20 G = 0 X(6) = K − W82 P = 0
H = x(3) − W80 x(7) = 1 Q = F − W22 H = 1 + j X(7) = L − W83 Q = 1 + j2.414

A I
x(0) X(0)

B J
x(4) X(1)
w80
C K
x(2) X(2)
w8 0
D L
x(6) X(3)
w80 w8 2
E M
x(1) X(4)
w80
F N
x(5) X(5)
w80 w81
G P
x(3) X(6)
w80 w82
H Q
x(7) X(7)
w80 w82 w83

X(k) = {4, 1 − j2.414, 0, 1 − j0.414, 0, 1 + j0.414, 0, 1 + j2.414}

Example 2.14: Obtain 8-point DFT of the sequence x(n) = {1, 1, 0, 0, −1, −1, 0, 0} using
radix-2 DIT-FFT algorithm. Show all the results along signal flow graph.

 Solution:
Given, x(0) = 1, x(1) = 1, x(2) = 0, x(3) = 0, x(4) = −1, x(5) = −1, x(6) = 0, x(7) = 0.

(i) N/2 twiddle factors. Here N = 8

8
∴ = 4 twiddle factors. W80 = 1; W81 = 0.707 − j0.707; W82 = −j; W83 = −0.707 − j0.707
2
(ii) Input is bit reversed and output is normal.
(iii) Butterfly operation
64 Module-2

a c=a+Wnrb

b d=a-Wnrb

(iv) Number of stages = log2 N = log2 8 = log2 23 = 3 log2 2 = 3 × 1 = 3.

A I
x(0) X(0)

B J
x(4) X(1)
w80
C K
x(2) X(2)
w8 0
D L
x(6) X(3)
w80 w8 2

E M
x(1) X(4)
w80
F N
x(5) X(5)
w80 w81
G P
x(3) X(6)
w80 w82
H Q
x(7) X(7)
w80 w82 w83

A = x(0) + W20 x(4) = 0 I = A + W20 C = 0 X(0) = I + W20 M = 0

B = x(0) − W80 x(4) = 2 J = B + W82 D = 2 X(1) = J + W81 N = 3.414 − j1.414
C = x(2) + W80 x(6) = 0 K = A − W80 C = 0 X(2) = K + W82 P = 0
D = x(2) − W80 x(6) = 0 L = B − W82 D = 2 X(3) = L + W82 Q = 0.586 − j1.414
E = x(1) + W20 x(5) = 0 M = E + W20 G = 0 X(4) = I − W20 M = 0
F = x(1) − W20 x(5) = 2 N = F + W22 H = 2 X(5) = J − W21 N = 0.586 + j1.414
G = x(3) + W20 x(7) = 0 P = E − W80 G = 0 X(6) = K − W82 P = 0
H = x(3) − W80 x(7) = 0 Q = F − W82 H = 2 X(7) = L − W83 Q = 3.414 + j1.414

X(k) = {0, 3.414 − j1.414, 0, 0.586 − j1.414, 0, 0.586 + j1.414, 0, 3.414 + j1.414}.

Example 2.15: What is the speed improvement factor in calculating 64-point DFT of a
sequence using direct computation and FFT algorithm? Also mention the number of real
registers required.

 Solution:
Direct computation:
Complex multiplication = N 2 = 4096.
Digital Signal Processing 65

Complex addition = N (N − 1) = 4032

FFT algorithm:
N
Complex multiplication = 2 log2 N = 192
Complex addition = N log2 N = 384

N2 4096
Speed improvement factor = N
log2 N
= 192 = 21.33
2

Number of real registers required for FFT:

Registers required for real part; N = 64
Registers required for imaginary part; N = 64
Registers required for twiddle factor; N = 64
Total registers required = 3N = 64 × 3 = 192.

Example 2.16: Calculate the IDFT of X(k) = {0, 2.8284 − j2.8284, 0, 0, 0, 0, 0, 2.8284 +
j2.8284} using inverse radix-2 DIT-FFT algorithm.

 Solution:
Given, X(0) = 0, X(1) = 2.8284 − j2.8284, X(2) = 0, X(3) = 0, X(4) = 0, X(5) =
0, X(6) = 0, X(7) = 2.8284 + j2.8284.

(i) N/2 twiddle factors. Here N = 8

8
∴ = 4 twiddle factors. W8−0 = 1; W8−1 = 0.707 + j0.707; W8−2 = j; W8−3 = −0.707 + j0.707
2
(ii) Input is normal and output is bit reversed.
(iii) Butterfly operation

a c=a+b

b d=(a-b)Wn-r

(iv) Number of stages = log2 N = log2 8 = log2 23 = 3 log2 2 = 3 × 1 = 3.

66 Module-2

1
A = X(0) + X(4) = 0 I =A+C =0 x(0) = 8
(I + J) = 0.707
B = X(1) + X(5) = 2.8284 − j2.8284 J = B + D = 5.6568 x(4) = 1
8
(I − J)W8−0 = −0.707
C = X(2) + X(6) = 0 K = [A − C]W8−0 = 0 x(2) = 1
8
(K + L) = 0.707
D = X(3) + X(7) = 2.8284 + j2.8284 L = [B − D]W8−2 = 5.6568 x(6) = 1
8
(K − L)W8−0 = −0.707
E = [X(0) − X(4)]W8−0 = 0 M =E+G=0 x(1) = 1
8
(M + N ) = 1
F = [X(1) − X(5)]W8−1 = 4 N =F +H =8 x(5) = 1
8
(M − N )W8−0 = −1
G = [X(2) − X(6)]W8−2 = 0 P = [E − G]W8−0 = 0 x(3) = 1
8
(P + Q) = 0
H = [X(3) − X(7)]W8−3 = 4 Q = [F − H]W8−2 = 0 x(7) = 1
8
(P − Q)W8−0 = 0

A I 1/8 x(0)
X(0)
B J 1/8 x(4)
X(1)
w8-0
C K 1/8 x(2)
X(2)
w8-0
D L 1/8 x(6)
X(3)
w8-2 w8-0
E M 1/8 x(1)
X(4)
w8-0
F N 1/8 x(5)
X(5)
w8-1 w8-0
G P 1/8 x(3)
X(6)
w8-2 w8-0
H Q 1/8 x(7)
X(7)
w8-3 w8-2 w8-0

x(n) = {0.707, 1, 0.707, 0, −0.707, −1, −0.707, 0}.

Example 2.17: Compute the IDFT of the sequence X(k) = {0, 2−j4.8284, 0, 2+j0.8284, 0, 2−
j0.8284, 0, 2 + j4.8284} using DIF-FFT algorithm.

 Solution:
Given, X(0) = 0, X(1) = 2 − j4.8284, X(2) = 0, X(3) = 2 + j0.8284, X(4) = 0, X(5) =
2 − j0.8284, X(6) = 0, X(7) = 2 + j4.8284.

(i) N/2 twiddle factors. Here N = 8

8
∴ = 4 twiddle factors. W8−0 = 1; W8−1 = 0.707 + j0.707; W8−2 = j; W8−3 = −0.707 + j0.707
2
(ii) Input is bit reversed and output is normal.
(iii) Butterfly operation
Digital Signal Processing 67

(iii) Butterfly operation

a c=a+Wn-rb

b d=a-Wn-rb

(iv) Number of stages = log2 N = log2 8 = log2 23 = 3 log2 2 = 3 × 1 = 3.

A I 1/8 x(0)
X(0)

B J 1/8 x(1)
X(4)
-0
w8
C K 1/8 x(2)
X(2)
w8-0
D L 1/8 x(3)
X(6)
w8-0 w8-2
E M 1/8 x(4)
X(1)
w8-0
F N 1/8 x(5)
X(5)
w8 -0
w8-1
G P 1/8 x(6)
X(3)
w8-0 w8-2
H Q 1/8 x(7)
X(7)
w8-0 w8-2 w8-3

A = X(0) + W8−0 X(4) = 4 I = A + W8−0 C = 4 I + W2−0 M = 1

1


x(0) = 8
B = X(0) − W8−0 X(4) = 4 J = B + W8−2 D = 4 J + W8−1 N = 1
1


x(1) = 8
= X(2) + W8−0 X(6) = 0 K = A − W8−0 C = 4 K + W8−2 P = 1
1


C x(2) = 8
= X(2) − W8−0 X(6) = 0 L = B − W8−2 D = 4 L + W8−3 Q = 1
1


D x(3) = 8
= X(1) + W8−0 X(5) = 2 − j2 M = E + W8−0 G = 4 I − W8−0 M = 0
1


E x(4) = 8
= X(1) − W8−0 X(5) = −j2.828 N = F + W8−2 H = 2.828 − j2.828 J − W8−1 N = 0
1


F x(5) = 8
= X(3) + W8−0 X(7) = 2 + 2j P = E − W8−0 G = −4j K − W8−2 P = 0
1


G x(6) = 8
= X(3) − W8−0 X(7) = −j2.828 Q = F − W8−2 H = −2.828 − j2.828 −3
1


H x(7) = 8
L − W8 Q = 0

x(n) = {1, 1, 1, 1, 0, 0, 0, 0}.

Example 2.18: If x(n) = {1, 2, 0, 1} and y(n) = {1, 3, 3, 1} obtain z(n) = x(n) ⊗4 y(n) using
DIT-FFT algorithm.

 Solution:
68 Module-2
A
x(0) X(0)

B
x(2) X(1)
w40
C
x(1) X(2)
w40
D
x(3) X(3)
w40 w41

A
y(0) Y(0)

B
y(2) Y(1)
w40
C
y(1) Y(2)
w40
D
y(3) Y(3)
w40 w41

A 1/4
Z(0) z(0)

B 1/4
Z(1) z(2)
-0
w4
C 1/4
Z(2) z(1)
w4-0
D 1/4
Z(3) z(3)
w4-1 w4-0

(i) N/2 twiddle factors. Here N = 4

(ii) Number of stages = log2 N = log2 4 = log2 22 = 2 log2 2 = 2 × 1 = 2.
(iii) X(k) :

A = x(0) + W40 x(2) = 1 X(0) = A + W40 C = 4

B = x(0) − W40 x(2) = 1 X(1) = B + W41 D = 1 − j
C = x(1) + W40 x(3) = 3 X(2) = A − W40 C = −2
D = x(1) − W40 x(3) = 1 X(3) = B − W41 D = 1 + j

(iv) Y (k) :
Digital Signal Processing 69

A = y(0) + W40 y(2) = 4 Y (0) = A + W40 C = 8

B = y(0) − W40 y(2) = −2 Y (1) = B + W41 D = −2 − 2j
C = y(1) + W40 y(3) = 4 Y (2) = A − W40 C = 0
D = y(1) − W40 y(3) = 2 Y (3) = B − W41 D = −2 + 2j
(v) Z(k) = X(k) × Y (k) = {32, −4, 0, −4}. (vi) z(n) :

A = Z(0) + Z(2) = 32 z(0) = 14 [A + B] = 6

B = Z(1) + Z(3) = −8 z(2) = 14 [A − B]W4−0 = 10
C = [Z(0) − Z(2)]W4−0 = 32 z(1) = 14 [C + D] = 8
D = [Z(1) − Z(3)]W4−1 = 0 z(3) = 14 [C − D]W4−0 = 8

z(n) = x(n) ⊗4 y(n) = {6, 8, 10, 8}.

Example 2.19: If x(n) = {1, 1, 1, 1} and y(n) = {1, 0, 1, 0} obtain z(n) = x(n) ⊗4 y(n) using
DIF-FFT algorithm.

 Solution:

(i) N/2 twiddle factors. Here N = 4

(ii) Number of stages = log2 N = log2 4 = log2 22 = 2 log2 2 = 2 × 1 = 2.
(iii) X(k) :
A = x(0) + x(2) = 2 X(0) = [A + B] = 4
B = x(1) + x(3) = 2 X(2) = [A − B]W40 = 0
C = [x(0) − x(2)]W40 = 0 X(1) = [C + D] = 0
D = [x(1) − x(3)]W41 = 0 X(3) = [C − D]W40 = 0
(iv) Y (k) :

A = y(0) + y(2) = 2 Y (0) = [A + B] = 2

B = y(1) + y(3) = 0 Y (2) = [A − B]W40 = 2
C = [y(0) − y(2)]W40 = 0 Y (1) = [C + D] = 0
D = [y(1) − y(3)]W41 = 0 Y (3) = [C − D]W40 = 0
70 Module-2

(v) Z(k) = X(k) × Y (k) = {8, 0, 0, 0}.

(vi) z(n) :
A = Z(0) + W4−0 Z(2) = 8 z(0) = 14 [A + W4−0 C] = 2
B = Z(0) − W4−0 Z(2) = 8 z(1) = 14 [B + W4−1 D] = 2
C = Z(1) + W4−0 Z(3) = 0 z(2) = 14 [C + W4−0 D] = 2
D = Z(1) − W4−0 Z(3) = 0 z(3) = 14 [C − W4−1 D] = 2

A
x(0) X(0)

B
x(1) X(2)
w40
C
x(2) X(1)
w40 w40
D
x(3) X(3)
w41

A
y(0) Y(0)

B
y(1) Y(2)
w40
C
y(2) Y(1)
w40 w40
D
y(3) Y(3)
w41

Z(0)
A 1/4
z(0)

B 1/4
Z(2) z(1)
w4-0

Z(1)
C 1/4 z(2)
w4-0

Z(3)
D 1/4 z(3)
w4-0 -1
w4

z(n) = x(n) ⊗4 y(n) = {2, 2, 2, 2}.

Digital Signal Processing 71

Example 2.20: Let x(n) = {1, 1/2, 1/4, 1/8} and y(n) = {1, 1, 1, 1}. Compute the DFT
of x(n) by the decimation in time FFT algorithm and that of y(n) by the decimation in
frequency FFT algorithm. Using the above results, evaluate the circular convolution of x(n)
and y(n).

 Solution:

(i) N/2 twiddle factors. Here N = 4

(ii) Number of stages = log2 N = log2 4 = log2 22 = 2 log2 2 = 2 × 1 = 2.

(iii) X(k) :

5 15
A = x(0) + W40 x(2) = 4 X(0) = A + W40 C = 8
3 3
B = x(0) − W40 x(2) = 4 X(1) = B + W41 D = 4 + j 38
5 5
C = x(1) + W40 x(3) = 8 X(2) = A − W40 C = 8
3 3
D = x(1) − W40 x(3) = 8 X(3) = B − W41 D = 4 − j 38

(iv) Y (k) :

A = y(0) + y(2) = 2 Y (0) = [A + B] = 4

B = y(1) + y(3) = 2 Y (2) = [A − B]W40 = 0
C = [y(0) − y(2)]W40 = 0 Y (1) = [C + D] = 0
D = [y(1) − y(3)]W41 = 0 Y (3) = [C − D]W40 = 0

(v) Z(k) = X(k) × Y (k) = {15/2, 0, 0, 0}.

(vi) z(n) :

15
A = Z(0) + Z(2) = 2 z(0) = 14 [A + B] = 15
8
B = Z(1) + Z(3) = 0 z(2) = 14 [A − B]W4−0 = 15
8
C = [Z(0) − Z(2)]W4−0 = 15
2 z(1) = 14 [C + D] = 15
8
D = [Z(1) − Z(3)]W4−1 = 0 z(3) = 14 [C − D]W4−0 = 15
8

z(n) = x(n) ⊗4 y(n) = {15/8, 15/8, 15/8, 15/8}.

72 Module-2

A
x(0) X(0)

B
x(2) X(1)
w40
C
x(1) X(2)
w40
D
x(3) X(3)
w40 w41

A
y(0) Y(0)

B
y(1) Y(2)
w40
C
y(2) Y(1)
w40 w40
D
y(3) Y(3)
w41

A 1/4
Z(0) z(0)

B 1/4
Z(1) z(2)
-0
w4
C 1/4
Z(2) z(1)
w4-0
D 1/4
Z(3) z(3)
-0
w4-1 w4

Example 2.21: Using DIF-FFT algorithm compute DFT of the sequence, x(n) =
{1, 2, −1, 2, 4, 2, −1, 2}. If y(n) = x(−n) without performing FFT, find Y (k) using X(k).

 Solution:
Given, x(0) = 1, x(1) = 2, x(2) = −1, x(3) = 2, x(4) = 4, x(5) = 2, x(6) = −1, x(7) = 2.
Digital Signal Processing 73

A = x(0) + x(4) = 5 I =A+C =3 X(0) = I + J = 11

B = x(1) + x(5) = 4 J =B+D =8 X(4) = (I − J)W80 = −5
C = x(2) + x(6) = −2 K = [A − C]W80 = 7 X(2) = K + L = 7
D = x(3) + x(7) = 4 L = [B − D]W82 =0 X(6) = (K − L)W80 = 7
E = [x(0) − x(4)]W80 = −3 M = E + G = −3 X(1) = M + N = −3
F = [x(1) − x(5)]W81 = 0 N =F +H =0 X(5) = (M − N )W80 = −3
G = [x(2) − x(6)]W82 = 0 P = [E − G]W80 = −3 X(3) = P + Q = −3
H = [x(3) − x(7)]W83 = 0 Q = [F − H]W82 = 0 X(7) = (P − Q)W80 = −3

A I
x(0) X(0)

B J
x(1) X(4)
w80
C K
x(2) X(2)
w80
D L
x(3) X(6)
w82 w8 0
E M
x(4) X(1)
0
w8
F N
x(5) X(5)
w8 1 w8 0
G P
x(6) X(3)
w8 2
w80
H Q
x(7) X(7)
w8 3
w82 w8 0

11

-3 -3

7 7 X(k)
X((-k))8
-3 -3
-5

X(k) = {11, −3, 7, −3, −5, −3, 7, −3}.

To obtain the DFT of y(n) = x(−n)
x(−n) is basically circularly folded sequence.
∴ y(n) = x((−n))N
74 Module-2

Using the circular time reversal property of DFT

DF T
x((−n))N −→ X((−k))N

∴ Y (k) = X((−k))N = {11, −3, 7, −3, −5, −3, 7, −3}.

Example 2.22: First five points of eight point DFT of a real valued sequence is given by,
X(k) = {0, 2 + 2j, −4j, 2 − 2j, 0}. Determine the remaining points. Hence find the sequence
x(n) using DIF-FFT algorithm.

 Solution:
Given, X(k) = {0, 2 + 2j, −4j, 2 − 2j, 0}
X(0) = 0, X(1) = 2 + 2j, X(2) = −4j, X(3) = 2 − 2j, X(4) = 0.

X(5) = X(3)∗ = 2 + 2j
X(6) = X(2)∗ = 4j
X(7) = X(1)∗ = 2 − 2j
X(k) = {0, 2 + 2j, −4j, 2 − 2j, 0, 2 + 2j, 4j, 2 − 2j}.

*
X(1) X(3) X(4) X(5) X(7)
X(0) X(2) X(6)

*
*

X(0) = 0, X(1) = 2 + 2j, X(2) = −4j, X(3) = 2 − 2j, X(4) = 0, X(5) = 2 + 2j, X(6) =
4j, X(7) = 2 − 2j.

(i) N/2 twiddle factors. Here N = 8

8
∴ = 4 twiddle factors. W8−0 = 1; W8−1 = 0.707 + j0.707; W8−2 = j; W8−3 = −0.707 + j0.707
2
(ii) Input is bit reversed and output is normal.
(iii) Butterfly operation
Digital Signal Processing 75
A I 1/8 x(0)
X(0)

B J 1/8 x(1)
X(4)
-0
w8
C K 1/8 x(2)
X(2)
w8-0
D L 1/8 x(3)
X(6)
w8-0 w8-2
E M 1/8 x(4)
X(1)
w8-0
F N 1/8 x(5)
X(5)
w8 -0
w8-1
G P 1/8 x(6)
X(3)
w8-0 w8-2
H Q 1/8 x(7)
X(7)
w8-0 w8-2 w8-3

a c=a+Wn-rb

b d=a-Wn-rb

(iv) Number of stages = log2 N = log2 8 = log2 23 = 3 log2 2 = 3 × 1 = 3.

A = X(0) + W8−0 X(4) = 0 I = A + W8−0 C = 0 I + W8−0 M = 1

1


x(0) = 8
B = X(0) − W8−0 X(4) = 0 J = B + W8−2 D = 8 J + W8−1 N = 1
1


x(1) = 8
= X(2) + W8−0 X(6) = 0 K = A − W8−0 C = 0 K + W8−2 P = −1
1


C x(2) = 8
= X(2) − W8−0 X(6) = −8j L = B − W2−2 D = −8 L + W8−3 Q = −1
1


D x(3) = 8
= X(1) + W8−0 X(5) = 4 + 4j M = E + W8−0 G = 8 I − W8−0 M = −1
1


E x(4) = 8
= X(1) − W8−0 X(5) = 0 N = F + W8−2 H = 0 J − W8−1 N = 1
1


F x(5) = 8
= X(3) + W8−0 X(7) = 4 − 4j P = E − W8−0 G = 8j K − W8−2 P = 1
1


G x(6) = 8
= X(3) − W8−0 X(7) = 0 Q = F − W8−2 H = 0 −3
1


H x(7) = 8
L − W8 Q = −1

x(n) = {1, 1, −1, −1, −1, 1, 1, −1}.

Example 2.23: Bring out differences between linear convolution and circular convolution.

 Solution:
76 Module-2

Linear convolution Circular convolution

(i) length of sequences may not be equal length of sequences must be equal
(ii) Resultant sequence: N = N1 + N2 − 1 Resultant sequence: N = N1 = N2
(iii) Shift is linear Shift is circular
(iv) Aliasing is not present Aliasing is present
∞
X N
X −1
(v) y(n) = x(n)h(n − k) y(n) = x(n)h(n − k)
n=−∞ k=0

Example 2.23: Bring out differences between DIT-FFT and DIF-FFT.

 Solution:

DIT-FFT DIF-FFT
(i) Reducing samples in time do- Reducing samples in fre-
main quency domain
(ii) Input is bit reversed while the Input is in natural order while
output is in normal order the output is bit reversed.
(iii) Splits the two DFTs into even Splits the two DFTs into first
and odd indexed input sam- half and last half of the input
ples samples
(iv) Multiplication is done before Multiplication is done after
addition addition
(v) Butterflies are defined on the Butterflies are defined on the
last pass of FFT first pass of FFT
 MODULE - III
Design of FIR Filters: Characteristics of practical frequency-selective filters, Symmetric
and Antisymmetric FIR filters, Design of Linear-phase FIR filters using windows - Rectan-
gular, Hamming, Hanning, Bartlett windows. Design of FIR filters using frequency sampling
method. Structure for FIR Systems: Direct form, Cascade form and Lattice structures.

3.1 Introduction
In the design of frequency-selective filters, the desired filter characteristics are specified
in the frequency domain in terms of the desired magnitude and phase response of the filter.
In the design process, we determine the coefficients of a causal FIR filter that closely approx-
imates the desired frequency response specifications. In practice, FIR filters are employed in
filtering problems where there is a requirement for a linear-phase characteristic within the
passband of the filter. Causality has very important implications in the design of frequency
selective filters.

• The frequency response H(w) cannot be zero, except at a finite set of points in fre-
quency.

• The magnitude |H(w)| cannot be constant in any finite range of frequencies and the
transition from passband to stopband cannot be infinitely sharp.

• The magnitude |H(w)| and phase of H(w) cannot be chosen arbitrarily.

3.2 Characteristics of Practical Frequency-Selective Filters

Ideal filters are non causal and hence physically unrealizable for real-time signal process-
ing applications. If we relax certain conditions, it is possible to realize causal filters that
approximate the ideal filters as closely as we wish. In particular,

• A small amount of ripple in the passband.

• It is not necessary to insist that |H(w)| be constant in the entire passband.

• A small, nonzero value or a small amount of ripple in the stopband.

77
78 Module-3

|H(ω)|

1 + δp - - - - - - - - - - - - - - Passband ripple

1 − δp --------------

--------- ----
–-------
Stopband
Transition
δs
band
ωp ωs π ω

Fig. 3.1. Magnitude characteristics of physically realizable filters.

The transition of the frequency response from passband to stopband denotes the transition
band of the filter as shown in Fig. 3.1. The band edge frequency ωp defines the edge of
the passband, while the frequency ωs denotes the beginning of the stopband. The width
of the passband (ωs − ωp ) is called the bandwidth of the filter. It is common practice to
use a logarithmic scale for the magnitude |H(w)| to accommodate a large dynamic range in
the frequency response. Thus, the ripple in the passband is (20 log10 δp dB) and that of the
stopband is (20 log10 δs dB).
In any filter design, we need to specify:

• Maximum tolerable passband ripple (δp ).

• Maximum tolerable stopband ripple (δs ).

• Stopband edge frequency (ωs ).

• Passband edge frequency (ωp ).

3.3 Symmetric and Anti-symmetric FIR filters

Linear phase is a property of a filter, where the phase response of the filter is a linear
function of frequency. The result is that all frequency components of the input signal are
shifted in time by the same constant amount, which is referred to as the phase delay. Linear-
phase filters have a symmetric impulse response. Unit sample response of FIR filters is
Digital Signal Processing 79

symmetric if it satisfies following condition.

h(n) = h(M − 1 − n); n = 0, 1, ..., M − 1 (3.1)

Unit sample response of FIR filters is Anti-symmetric if it satisfies following condition

h(n) = −h(M − 1 − n); n = 0, 1, ..., M − 1 (3.2)

Consider the z - transform of unit sample response,

M −1
h(n)z −n
X
H(z) = (3.3)
n=0

3.3.1 Symmetric Impulse Response with M=odd

Symmetric impulse response with M =odd, then z = ejω

M −3
2
M − 1 −jω( M −1 ) X
   h i
H e jω
=h e 2 + h(n) e−jωn + e−jω(M −1−n) (3.4)
2 n=0

M −1
e−jωn = e−jωn ejω( 2 ) e−jω( M2−1 ) = ejω( M2−1 −n) · e−jω( M2−1 )

M −1
e−jω(M −1−n) = e−jω(M −1) ejωn = e−jω( 2 ) · e−jω( M2−1 ) ejωn = e−jω( M2−1 ) · e−jω( M2−1 −n)

jω M2−1 −n
( ) +e−jω( M2−1 −n)
h i
−jω ( M2−1 ) e M −1
e−jωn
+e −jω(M −1−n)
=e = e−jω( 2 )2 cos ω( M2−1 −n)
Substituting in eqn. (3.4)

M −3
2
M −1
 
M −1
−jω ( M2−1 )
 
M −1 −jω ( )+
X
H (ω) = h 2 e 2 h(n)e 2 cos ω −n
n=0
2
 M −3

(3.5)
2
M −1
 
−jω ( M2−1 ) 
 
M −1
X
H (ω) = e h +2 h(n) cos ω −n 

2 2
n=0

The polar form of H(ω) can be expressed as

H(ω) = |H(ω)|ej∠H(ω) (3.6)

80 Module-3

Comparing eqn. (3.6) with eqn. (3.5) we get,

M −3
2
M −1 M −1
  X  
|H(ω)| = h +2 h(n) cos ω −n
2 n=0
2
  
 −ω M −1 for |H(ω)| > 0
2
∠H(ω) =  
 −ω M −1 + π for |H(ω)| < 0
2

3.3.2 Anti-symmetric Impulse Response with M=even

For even value of M we can write eqn. (3.5) directly as

 
M
2
−1
M −1
 
M −1
H(ω) = e−jω( )
X
2 h(n) cos ω −n  (3.7)
2

n=0
2

Consequently,
M
2
−1
M −1
X  
|H(ω)| = 2 h(n) cos ω −n
n=0
2
  
 −ω M −1 for |H(ω)| > 0
∠H(ω) =  2 
 −ω M −1 + π for |H(ω)| < 0
2

3.4 Design of Linear-phase FIR filters using Windows

Based on the desired frequency response specification Hd (ω) determine the corresponding
unit sample response hd (n).
  ∞
hd (n)e−jωn
X
jω
Hd e = (3.8)
n=0

where, Z π
1  
hd (n) = Hd ejω ejωn dω (3.9)
2π −π

In general the sample response hd (n) is infinite in duration and must be truncated at some
point to get an FIR filter of length M . Truncation is achieved by multiplying hd (n) by
window function. The unit sample response of the FIR filter becomes
Digital Signal Processing 81

h(n) = hd (n)w(n)
(
hd (n), n = 0, 1, . . . , M − 1
=
0, otherwise

where ω(n) is the window function. Different types of windows are

• Rectangular window

• Hamming window

• Hanning window

• Bartlett (Triangular) window

• Blackman window

• Kaiser window

3.4.1 Rectangular window

The rectangular window may be defined by

(
1; for n = 0, 1, ..., M − 1
ωR (n) = (3.10)
0; otherwise

where M is the window length in samples.

 
ωM
sin 2
|WR (ω)| = ω

(3.11)
sin 2

In the magnitude spectrum of rectangular window there are one main lobe and many
side lobes. As M increases the main lobe becomes narrower. The area under the side lobes
remain same irrespective of changes in M .

3.4.2 Hamming window

Hamming window is most commonly used window in speech signal processing. This is a
modified version of the raised cosine window. It is given by,
  
 0.54 − 0.46 cos 2πn ; for n = 0, 1, ..., M − 1
M −1
ωH (n) = (3.12)
 0; otherwise
82 Module-3

The window has bell like shape and its first as well as last samples are not zero. Further, it
has reduced sidelobes but slightly increased main lobe.

wR(n) wH(n)

0 1 2 3 4 …... M-1 0 1 2 3 4 …... M-1

n n

(a) Rectangular window (b) Hamming window

wHN(n) wT(n)

n n
0 1 2 3 4 …... M-1 0 1 2 3 4 …... M-1

(c) Hanning window (d) Bartlett window

Fig. 3.2. Impulse response for different windows.

3.4.3 Hanning window

Hanning window has shape similar to those of Hamming but its first and last samples are
zero. This is a raised cosine window function given by
  
 1 1 − cos 2πn ; for n = 0, 1, ..., M − 1
2 M −1
ωHN (n) = (3.13)
 0; otherwise
Digital Signal Processing 83

It is observed that it has narrow main lobe, but first few sidelobes are significant and then
sidelobes reduce rapidly.

3.4.4 Bartlett window

Bartlett Window is also called as triangular window. It is mathematically expressed as


2|n− M2−1 |

1− M −1 ; for n = 0, 1, ..., M − 1
ωT (n) = (3.14)
 0; otherwise

Table 3.1: Summary of window function characteristics.

Window name Transition width of main lobe Min. stopband attenuation Peak value of side lobe
4π
Rectangular M +1 -21 dB -21 dB
8π
Hamming M -53 dB -41 dB
8π
Hanning M -44 dB -31 dB
8π
Bartlett M -25 dB -25 dB

Example 3.1: Design the symmetric FIR lowpass filter whose desired frequency response is
given as (
e−jωτ for |ω| ≤ ωc
Hd (ω) =
0 Otherwise

The length of the filter should be 7 and ωc = 1 r/sample. Use Hanning window.

 Solution: We know that, τ = M −1

2 = 7−1
2 = 3.

1 π
Z
hd (n) = Hd (ω)ejωn dω
2π −π
1 1 −jωτ jωn
Z
= e e dω
2π −1
1 1 jω(n−τ )
Z
= e dω
2π −1
" #1
1 ejω(n−τ )
=
2π j(n − τ ) −1
1 h i
= ej(n−τ ) − e−j(n−τ )
2jπ(n − τ )
84 Module-3

" #
1 ej(n−τ ) − e−j(n−τ )
=
π(n − τ ) 2j
sin [(n − τ )]
∴ hd (n) = ; for n 6= τ
π(n − τ )
when n = τ
1 1 jω(τ −τ )
Z
hd (n) = e dω
2π −1
1 1
Z
= 1 dω
2π −1
1
= [ω]1
2π −1
1
= [1 + 1]
2π
1
=
π
Thus hd (n) is, 
 sin(n−τ ) for n 6= τ
π(n−τ )
hd (n) = 1

π for n = τ

sin(0 − 3)
n = 0; hd (0) = = 0.015
π(0 − 3)
sin(1 − 3)
n = 1; hd (1) = = 0.1447
π(1 − 3)
sin(2 − 3)
n = 2; hd (2) = = 0.2678
π(2 − 3)
1
n = 3; hd (3) = = 0.3183
π
sin(4 − 3)
n = 4; hd (4) = = 0.2678
π(4 − 3)
sin(5 − 3)
n = 5; hd (5) = = 0.1447
π(5 − 3)
sin(6 − 3)
n = 6; hd (6) = = 0.015
π(6 − 3)
For M = 7 Hanning window is defined as
 
2πn
ω(n) = 0.5 1 − cos M −1
 
ω(n) = 0.5 1 − cos 2πn
6
Digital Signal Processing 85

ω(0) = 0  
ω(1) = 0.5 1 − cos 2π
6 = 0.25
 
ω(2) = 0.5 1 − cos 4π
6 = 0.75
 
ω(3) = 0.5 1 − cos 6π
6 =1
 
ω(4) = 0.5 1 − cos 8π
6 = 0.75
 
ω(5) = 0.5 1 − cos 10π
6 = 0.25
 
ω(6) = 0.5 1 − cos 12π
6 =0

∴ h(n) = hd (n) × ω(n); for 0 ≤ n ≤ 6.

h(0) = hd (0) × w(0) = 0.015 × 0 = 0

h(1) = hd (1) × w(1) = 0.1447 × 0.25 = 0.03618
h(2) = hd (2) × w(2) = 0.2678 × 0.75 = 0.20089
h(3) = hd (3) × w(3) = 0.3183 × 1 = 0.31831
h(4) = hd (4) × w(4) = 0.2678 × 0.75 = 0.20089
h(5) = hd (5) × w(5) = 0.1447 × 0.25 = 0.03618
h(6) = hd (6) × w(6) = 0.015 × 0.0 = 0

Example 3.2: Design a LPF using rectangular window for the desired frequency response of
π
a low pass filter given by ωc = 2 r/sec and take M = 11. Find the values of h(n). Also,
determine the magnitude response.
(
e−jωτ ; −ωc ≤ ω ≤ ωc
Hd (ω) =
0; Otherwise

 Solution: We know that, τ = M −1

2 = 11−1
2 =5
86 Module-3
1 π
Z
hd (n) = Hd (ω)ejωn dω
2π −π
1 ωc −jωτ jωn
Z
= e e dω
2π −ωc
1 ωc jω(n−τ )
Z
= e dω
2π −ωc
" #ωc
1 ejω(n−τ )
=
2π j(n − τ ) −ωc
1 h i
= ejωc (n−τ ) − e−jωc (n−τ )
2jπ(n − τ )
" #
1 ejωc (n−τ ) − e−jωc (n−τ )
=
π(n − τ ) 2j
sin [ωc (n − τ )]
∴ hd (n) = ; for n 6= τ
π(n − τ )
when n = τ Z π/2
1
hd (n) = ejω(τ −τ ) dω
2π −π/2
Z π/2
1
= 1 dω
2π −π/2
1 π/2
= [ω]
2π −π/2
1
= [π/2 + π/2]
2π
1
=
2
Thus hd (n) is, 
 sin π/2(n−τ ) for n 6= τ
π(n−τ )
hd (n) =
 1 for n = τ
2
Digital Signal Processing 87

sin π(0−5)
2
n = 0; hd (0) = = 0.0637
π(0 − 5)
sin π(1−5)
2
n = 1; hd (1) = =0
π(1 − 5)
sin π(2−5)
2
n = 2; hd (2) = = −0.106
π(2 − 5)
sin π(3−5)
2
n = 3; hd (3) = =0
π(3 − 5)
sin π(4−5)
2
n = 4; hd (4) = = 0.318
π(4 − 5)
n = 5; hd (5) = 0.5
sin π(6−5)
2
n = 6; hd (6) = = 0.318
π(6 − 5)
sin π(7−5)
2
n = 7; hd (7) = =0
π(7 − 5)
sin π(8−5)
2
n = 8; hd (8) = = −0.106
π(8 − 5)
sin π(9−5)
2
n = 9; hd (9) = =0
π(9 − 5)
sin π(10−5)
2
n = 10; hd (10) = = 0.0637
π(10 − 5)
For M = 11 rectangular window is defined as
(
1; for 0 ≤ n ≤ 10
ω(n) =
0; Otherwise

∴ h(n) = hd (n) × ω(n) = hd (n) for 0 ≤ n ≤ 10.

88 Module-3

The impulse response is symmetric with M = odd = 11.

M −3
2
M −1 M −1
  X  
|H(ω)| = h +2 h(n) cos ω −n
2 n=0
2
4
X
= h(5) + 2 h(n) cos ω(5 − n)
n=0

= h(5) + 2h(0) cos 5ω + 2h(1) cos 4ω + 2h(2) cos 3ω + 2h(3) cos 2ω + 2h(4) cos ω
|H(ω)| = 0.5 + 0.127 cos 5ω − 0.212 cos 3ω + 0.636 cos ω.

Example 3.3: The desired frequency response of low pass filter is given by
(

jω
 e−j3ω − 3π
4 ≤ω ≤
3π
4
Hd (ω) = Hd e = 3π
0 4 ≤ |ω| ≤ π

Determine the frequency response of the FIR, if, Hamming window is used with N = 7.

 Solution: We know that, τ = M −1

2 = 7−1
2 = 3.

1 π
Z  
hd (n) = Hd ejω ejωn dω
2π −π
1 ωc −j3ω jωn
Z
= e e dω
2π −ωc
Z ωc
1
= ejω(n−3) dω
2π −ωc
" #ωc
1 ejω(n−3)
=
2π j(n − 3) −ωc
" #
1 jω
e (n−3)
c − e−jωc (n−3)
=
π(n − 3) 2j
sin ωc (n − 3)
hd (n) = ; n 6= τ
π(n − 3)
Digital Signal Processing 89

when n = τ Z 3π/4
1
hd (n) = ejω(τ −τ ) dω
2π −3π/4
1 3π/4
Z
= 1 dω
2π −3π/4
1 3π/4
= [ω]
2π −3π/4
1
= [3π/4 + 3π/4]
2π
3
=
4
Thus hd (n) is, 
 sin 3π/4(n−τ ) for n 6= τ
π(n−τ )
hd (n) = 3

4 for n = τ
 
3π(0−3)
sin 4
n = 0; hd (0) = = 0.075
π(0 − 3)
 
3π(1−3)
sin 4
n = 1; hd (1) = = −0.159
π(1 − 3)
 
3π(2−3)
sin 4
n = 2; hd (2) = = 0.225
π(2 − 3)
n = 3; hd (3) = 0.75
 
3π(4−3)
sin 4
n = 4; hd (4) = = 0.225
π(4 − 3)
 
3π(5−3)
sin 4
n = 5; hd (5) = = −0.159
π(5 − 3)
 
3π(6−3)
sin 4
n = 6; hd (6) = = 0.075
π(6 − 3)
The Hamming window is described as
  
 0.54 − 0.46 cos 2πn ; for n = 0, 1, ..., M − 1
M −1
ωH (n) =
 0; otherwise

2πn
 
w(n) = 0.54 − 0.46 cos
7−1
90 Module-3
2πn
 
w(n) = 0.54 − 0.46 cos
6
 
0
n = 0; ω(0) = 0.54 − 0.46 cos = 0.08
6 
n = 1; ω(1) = 0.54 − 0.46 cos 2π = 0.31
6
n = 2; ω(2) = 0.54 − 0.46 cos 4π = 0.77
6
6π
n = 3; ω(3) = 0.54 − 0.46 cos 6 = 1
 
n = 4; ω(4) = 0.54 − 0.46 cos 8π = 0.77
6 
10π
n = 5; ω(5) = 0.54 − 0.46 cos 6 = 0.31
 
n = 6; ω(6) = 0.54 − 0.46 cos 12π
6 = 0.08

To find h(n); h(n) = hd (n) × ω(n)

h(0) = hd (0) × w(0) = 0.075 × 0.08 = 0.006

h(1) = hd (1) × w(1) = −0.159 × 0.31 = −0.049
h(2) = hd (2) × w(2) = 0.225 × 0.77 = 0.173
h(3) = hd (3) × w(3) = 0.750 × 1 = 0.750
h(4) = hd (4) × w(4) = 0.225 × 0.77 = 0.173
h(5) = hd (5) × w(5) = −0.159 × 0.31 = −0.049
h(6) = hd (6) × w(6) = 0.075 × 0.08 = 0.006
The impulse response is symmetric with M = odd = 7.

M −3
2
M −1 M −1
  X  
|H(ω)| = h +2 h(n) cos ω −n
2 n=0
2
2
X
= h(3) + 2 h(n) cos ω(3 − n)
n=0

= h(3) + 2h(0) cos 3ω + 2h(1) cos 2ω + 2h(2) cos ω

|H(ω)| = 0.75 + 0.012 cos 3ω − 0.0908 cos 2ω + 0.346 cos ω.
M −1
H(ω) = e−jω( 2
)
|H(ω)| = e−j3ω [0.75 + 0.012 cos 3ω − 0.0908 cos 2ω + 0.346 cos ω.]

Example 3.4: Determine the filter coefficients hd (n) for the desired frequency response of a
Digital Signal Processing 91

low pass filter given by

(

jω
 e−2jω ; for − π
4 ≤ω≤ π
4
Hd e = π
0; for 4 ≤ |ω| ≤ −π

Also, (
1; for 0 ≤ n ≤ 4
ω(n) =
0; otherwise

Determine h(n) and also the frequency response H(ejw ).

 Solution:
1 π Z
hd (n) = Hd ejω ejωn dω
2π −π
1 π/4 −j2ω jωn
Z
= e e dω
2π −π/4
Z π/4
1
= ejω(n−2) dω
2π −π/4
" #π/4
1 ejω(n−2)
=
2π j(n − 2) −π/4
1 h π π
i
= ej 4 (n−2) − e−j 4 (n−2)
2jπ(n − 2)
" π π #
1 ej 4 (n−2) − e−j 4 (n−2)
=
π(n − 2) 2j
sin π(n−2)
4
hd (n) = ; n 6= 2
π(n − 2)
when n = τ = 2 Z π/4
1
hd (n) = ejω(τ −τ ) dω
2π π/4
Z π/4
1
= 1 dω
2π π/4
1 π/4
= [ω]
2π π/4
1
= [π/4 + π/4]
2π
1
=
4
92 Module-3

Thus hd (n) is, 

 sin π/4(n−τ ) for n 6= τ
π(n−τ )
hd (n) =
 1 for n = τ
4

sin π(0−2)
4
n = 0; hd (0) = = 0.159
π(0 − 2)
sin π(1−2)
4
n = 1; hd (1) = = 0.224
π(1 − 2)
n = 2; hd (2) = 0.25
sin π(3−2)
4
n = 3; hd (3) = = 0.224
π(3 − 2)
sin π(4−2)
4
n = 4; hd (4) = = 0.159
π(4 − 2)
Also, (
1; for 0 ≤ n ≤ 4
ω(n) =
0; otherwise
This is rectangular window of length M = 5.

∴ h(n) = hd (n) × ω(n) = hd (n) for 0 ≤ n ≤ 4.

The frequency response is symmetric with M=odd=5.

M −3
2
M −1 M −1
    X  
jω
H e =h +2 h(n) cos ω −n
2 n=0
2

1
X
= h(2) + 2 h(n) cos ω(2 − n)
n=0

= h(2) + 2h(0) cos 2ω + 2h(1) cos ω

= 0.25 + 2 × 0.159 cos 2ω + 2 × 0.224 cos ω
 
H ejω = 0.25 + 0.318 cos 2ω + 0.448 cos ω
M −1
H(ω) = e−jω( 2
)
|H(ω)| = e−j2ω [0.25 + 0.318 cos 2ω + 0.448 cos ω.]

Example 3.5: Design a normalized linear phase FIR low pass filter having phase delay of
τ = 4 and at least 40 dB attenuation in the stopband. Also obtain the magnitude frequency
Digital Signal Processing 93

response of the filter.

 Solution: The linear phase FIR filter is normalized. ie., cut-off frequency, ωc = 1 r/sample.
We know that,

M −1
τ =4=
2
∴ M = 9.
1 ωc −jωτ jωn
Z
hd (n) = e e dω
2π −ωc
1 1 jω(n−4)
Z
= e dω
2π −1
" #1
1 ejω(n−4)
=
2π j(n − 4) −1
sin[(n − 4)]
hd (n) = ; n 6= 4
π(n − 4)
when n = τ = 4
1 1 jω(τ −τ )
Z
hd (n) = e dω
2π −1
1 1
Z
= 1 dω
2π −1
1
= [ω]1
2π −1
1
= [1 + 1]
2π
1
=
π
Thus hd (n) is, 
 sin(n−4) for n 6= 4
π(n−4)
hd (n) = 1

π for n = 4

To find h(n); h(n) = hd (n) × ω(n). The stopband attenuation required for this filter is 40
dB. From the Table 3.1 the Hanning window satisfies this requirement. The Hanning window
function given by:
  
 1 1 − cos 2πn ; for n = 0, 1, ..., M − 1
2 M −1
ωHN (n) =
 0; otherwise
94 Module-3

  
 1 sin[(n−4)] 1 − cos 2πn ; for n 6= 4
2 π(n−4)  8 
h(n) = hd (n) × ω(n) = 1
 1 − cos 2πn ;
2π 8 for n = 4
h  i
sin(0−4) π0
h(0) = π(0−4) h0.5 − 0.5 cos  4 i = 0.0000
sin(1−4) π1
h(1) = π(1−4) h0.5 − 0.5 cos  4 i = 0.0022
sin(2−4) 2π
h(2) = π(2−4) h0.5 − 0.5 cos  4 i = 0.0724
sin(3−4)
h(3) = 0.5 − 0.5 cos 3π = 0.2286
π(3−4)
h  i 4
1 4π
h(4) = π 0.5 −h 0.5 cos 4 = 0.3183
 i
sin(5−4) 5π
h(5) = π(5−4) h0.5 − 0.5 cos  4 i = 0.2286
sin(6−4) 6π
h(6) = π(6−4) h0.5 − 0.5 cos  4 i = 0.0724
sin(7−4) 7π
h(7) = π(7−4) h0.5 − 0.5 cos  4 i = 0.0022
sin(8−4) 8π
h(8) = π(8−4) 0.5 − 0.5 cos 4 = 0.0000

The frequency response is symmetric with M=odd=9

M −3
2
M −1 M −1
    X  
jω
H e =h +2 h(ω) cos −n
2 n=0
2
3
X
= h(4) + 2 h(n) cos ω(4 − n)
n=0

= h(4) + 2h(0) cos 4ω + 2h(1) cos 3ω + 2h(2) cos 2ω + 2h(3) cos ω

 
H ejω = 0.3183 + 0.0044 cos(3ω) + 0.1448 cos(2ω) + 0.4572 cos(ω).

Example 3.6: Design the bandpass linear phase FIR filter having cut-off frequencies of ωc1
= 1 r/sample and ωc2 = 2 r/sample. Obtain the unit sample response through following
window. (
1; for 0 ≤ n ≤ 6
ω(n) =
0; Otherwise
Also, obtain the frequency response of the filter.

 Solution: Z π
1
hd (n) = Hd (ω)ejωn dω
2π −π
Digital Signal Processing 95
"Z #
1 −ωc1 Z ωc
2
−jωτ jωn −jωτ jωn
= e e dω + e e dω
2π −ωc2 ωc1
"Z #
1 −ωc1 Z ωc
2
= ejω(n−τ ) + ejω(n−τ ) dω
2π −ωc2 ωc1
" #−ωC " #ωc 
1  ejω(n−τ ) 1
ejω(n−τ ) 2
= + 
2π (n − τ ) −ωC2
(n − τ ) ωc1
sin ωC2 (n − τ ) − sin ωc1 (n − τ )
= ; n 6= τ
π(n − τ )

 sin ωC2 (n−τ )−sin ωC1 (n−τ ) for n 6= τ
hd (n) = π(n−τ )
ωC2 −ωC1

π for n = τ

Given, M = 7, ωc1 = 1 r/sample & ωc2 = 2 r/sample.

M −1 7−1
τ= = =3
2 2

 sin 2(n−3)−sin(n−3) for n 6= 3
π(n−3)
hd (n) = 1

π for n = 3

sin 2(0 − 3) − sin(0 − 3)

n = 0; hd (0) = = −0.0446
π(0 − 3)
sin 2(1 − 3) − sin(1 − 3)
n = 1; hd (1) = = −0.2651
π(1 − 3)
sin 2(2 − 3) − sin(2 − 3)
n = 2; hd (2) = = 0.0215
π(2 − 3)
1
n = 3; hd (3) = = 0.3183
π
sin 2(4 − 3) − sin(4 − 3)
n = 4; hd (4) = = 0.0215
π(4 − 3)
sin 2(5 − 3) − sin(5 − 3)
n = 5; hd (5) = = −0.2651
π(5 − 3)
sin 2(6 − 3) − sin(6 − 3)
n = 6; hd (6) = = −0.0446
π(6 − 3)
Also, (
1; for 0 ≤ n ≤ 6
ω(n) =
0; Otherwise
96 Module-3

It’s a rectangular window

∴ h(n) = hd (n) × ω(n) = hd (n)

The magnitude response of the FIR filter for M=7=odd, is given by

M −3
2
M −1 M −1
    X  
jω
H e =h +2 h(n) cos ω −n
2 n=0
2
2
X
= h(3) + 2 h(n) cos ω(3 − n)
n=0

= h(3) + 2h(0) cos 3ω + 2h(1) cos 2ω + 2h(2) cos ω

 
H ejω = 0.3183 − 0.0892 cos 3ω − 0.5302 cos 2ω + 0.043 cos ω.
M −1
H(ω) = e−jω( 2
)
|H(ω)| = e−j3ω [0.3183 − 0.0892 cos 3ω − 0.5302 cos 2ω + 0.043 cos ω.]

3.5 Design of FIR Filters using Frequency Sampling Method

The frequency-sampling method for FIR filter design is perhaps the simplest and most
direct technique when a desired frequency response has been specified. It consists simply
of uniformly sampling the desired frequency response, and performing an inverse DFT to
obtain the corresponding (finite) impulse response. In this method a set of M equally spaced
samples in the interval (0, 2π) are taken in the desired frequency response Hd (ω). Further,
the continuous frequency ω is replaced by

2π
ω = ωk = k; k = 0, 1, . . . M − 1
M

The discrete time Fourier transform (DTFT) is

H(k) = Hd (ω)|ω=ωk
2π
 
= Hd k ; k = 0, 1, . . . M − 1
M
The M point inverse DFT of h(n) is

−1
1 MX
h(n) = H(k)ejωn
M k=0
−1
1 MX 2πkn
= H(k)ej M ; n = 0, 1, . . . M − 1
M k=0

For the FIR filter to be realizable the coefficients of h(n) must be real. This is possible if all
Digital Signal Processing 97

complex terms appear in complex conjugate pairs. Consider the term, H(M −k)ej2πn(M −k)/M

H(M − k)ej2πn(M −k)/M = H(M − k)ej2πn e−j2πkn/M

since, ej2πn = cos(2πn) + j sin(2πn) = 1

H(M − k)ej2πn(M −k)/M = H(M − k)e−j2πkn/M

substituting the |H(M − k)| = |H(k)|

H(M − k)ej2πn(M −k)/M = H(k)e−j2πkn/M

The term H(k)e−j2πkn/M is complex conjugate of H(k)ej2πkn/M . Consequently, the term

H(M − k)e−j2π(M −k)n/M is complex conjugate of H(k)e−j2πkn/M .

∴ H(M − k) = H ∗ (k)

Further,
P
!
1 X h
j2πkn/M
i
h(n) = H(0) + 2 Re H(k)e
M k=1

where, 
M −1


 2 ; if M is odd
P =

 M − 1;

if M is even
2

Example 3.7: Derive an expression for system function H(z) if the unit sample response h(n)
is obtained using frequency sampling technique.

 Solution:
We know that,
M −1
h(n)z −n
X
H(z) =
n=0

Substituting
−1
1 MX 2πkn
h(n) = H(k)ej M ; n = 0, 1, . . . M − 1
M k=0

−1 −1
M M
"M −1 #
−n 1 j 2πkn
z −n
X X X
H(z) = h(n)z = H(k)e M

n=0 n=0
M k=0
98 Module-3

interchanging the order of summation,

−1 −1
1 MX M
" #
2πkn
ej M z −n
X
H(z) = H(k)
M k=0 n=0
 
M −1
2πkn
M −1 
2πk
n 1 − ej2πk z −M 1 − ej2πk z −M 1 − z −M
z −n = z −1
X X
ej M ej M =   = =
j 2πk j 2πk 2πk
n=0 n=0 1− e M z −1 1−e M z −1 1 − ej M z −1
−1 −1
1 MX 1 − z −M −M
M
X H(k)/M
∴ H(z) = H(k) 2πk = 1 − z
M k=0 j 2πk −1
1 − ej M z −1 k=0 1 − e M z

Example 3.8: Design a lowpass FIR filter using frequency sampling technique having cut-off
π
frequency of 2 r/sample. The filter should have linear phase and length of 17.

 Solution: Given, M = 17, the Ideal LPF frequency response Hd (ω) for the linear phase is

 e−jω( M2−1 ) ; 0 ≤ ω ≤ π
Hd (ω) = 2
π
 0; 2 ≤ ω ≤ π

(
e−j8ω ; 0≤ω≤ π
2
Hd (ω) = π
0; 2 ≤ω≤π

To sample put,
2πk
ω= ; k = 0, 1, 2, ..., M − 1.
M
2πk
ω= ; k = 0, 1, 2, ..., 16.
17
.
2πk
e−j8
(
2πk π
17 ; 0≤ 17 ≤ 2
Hd (ω) = π 2πk
0; 2 ≤ 17 ≤ π

The range of k is

2πk
= 0 =⇒ k = 0
17
2πk π
= =⇒ k = 17/4 = 4.25
17 2
2πk
= π =⇒ k = 17/2 = 8.5
17
Digital Signal Processing 99

since, k is always an integer, we should consider the range as

16πk
e−j
(
17 ; 0≤k≤4
H(k) =
0; 5≤k≤8

The value of h(n) is given by

P
!
1 X h
j2πkn/M
i
h(n) = H(0) + 2 Re H(k)e
M k=1

M −1 17−1 16
P = 2 = 2 = 2 = 8.

8
!
1 X h i
h(n) = 1+2 Re H(k)ej2πkn/M
17 k=1

Also, |H(k)| = 1; 0≤k≤4

4
!
1 h 16πk
i
Re e−j 17 ej2πkn/17
X
h(n) = 1+2
17 k=1
4
!
1 X h i
h(n) = 1+2 Re ej2πk(n−8)/17
17 k=1
4 !
1 2πk(n − 8)
X 
h(n) = 1+2 cos
17 k=1
17

This is the unit sample response of the FIR filter obtained using frequency sampling technique.

Example 3.9: Determine the impulse response h(n) of a filter having desired frequency re-
sponse  (M −1)ω



e−j 2 ; 0 ≤ |ω| ≤ π
2
Hd (w) =
π
 0; 2 ≤ω≤π
assume M = 7, use frequency sampling approach.

 Solution: Given, M = 7

 e−jω( M2−1 ) ; 0 ≤ ω ≤ π
Hd (ω) = 2
 0; π2 ≤ ω ≤ π
(
e−j3ω ; 0≤ω≤ π
2
Hd (ω) = π
0; 2 ≤ω≤π
100 Module-3

To sample put,
2πk
ω= ; k = 0, 1, 2, ..., M − 1.
M
2πk
ω= ; k = 0, 1, 2, ..., 6.
7
.
2πk
e−j3
(
2πk π
7 ; 0≤ 7 ≤ 2
Hd (ω) = π 2πk
0; 2 ≤ 7 ≤π

The range of k is

2πk
= 0 =⇒ k = 0
7
2πk π
= =⇒ k = 7/4 = 1.75
7 2
2πk
= π =⇒ k = 7/2 = 3.5
7
since, k is always an integer, we should consider the range as
6πk
e−j
(
7 ; 0≤k≤1
H(k) =
0; 2≤k≤3

The value of h(n) is given by

P
!
1 X h
j2πkn/M
i
h(n) = H(0) + 2 Re H(k)e
M k=1

M −1 7−1 6
P = 2 = 2 = 2 = 3.

3
!
1 X h i
h(n) = 1+2 Re H(k)ej2πkn/M
7 k=1

Also, |H(k)| = 1; 0≤k≤1

1
!
1 h 6πk
i
Re e−j 7 ej2πkn/7
X
h(n) = 1+2
7 k=1
1
!
1 X h i
h(n) = 1+2 Re ej2πk(n−3)/7
7 k=1
1 !
1 2πk(n − 3)
X 
h(n) = 1+2 cos
7 k=1
7
Digital Signal Processing 101

This is the unit sample response of the FIR filter obtained using frequency sampling technique.

Example 3.10: Design a bandpass filter with the following specifications using frequency
sampling approach. Sampling frequency of 8000 Hz, cut-off frequencies 1000 Hz and 3000
Hz. Take M = 7.

 Solution:

1000 π 3000 3π
ωc1 = 2π = , ωc2 = 2π =
8000 4 8000 4
Given, M = 7 
 e−jω( M2−1 ) ; π ≤ ω ≤ 3π
Hd (ω) = 4 4
 0; otherwise
(
e−j3ω ; π
4 ≤ω≤ 3π
4
Hd (ω) =
0; otherwise
To sample put,
2πk
ω= ; k = 0, 1, 2, ..., M − 1.
M
2πk
ω= ; k = 0, 1, 2, ..., 6.
7
.

2πk π
= =⇒ k = 0.875
7 4
2πk 3π
= =⇒ k = 2.625
7 4
since, k is always an integer, we should consider the range as
6πk
e−j
(
7 ; 1≤k≤2
H(k) =
0; otherwise

The value of h(n) is given by

P
!
1 X h
j2πkn/M
i
h(n) = H(0) + 2 Re H(k)e
M k=1

M −1 7−1 6
P = 2 = 2 = 2 = 3.
102 Module-3

3
!
1 X h i
h(n) = 0+2 Re H(k)ej2πkn/M
7 k=1
2
!
1 h 6πk
i
Re e−j 7 ej2πkn/7
X
h(n) = 0+2
7 k=1
2
!
2 h i
Re e−j2πk(3−n)/7
X
h(n) =
7 k=1
2 !
2 2πk(3 − n)
X 
h(n) = cos
7 k=1
7
2 2π(3 − n) 4π(3 − n)
 
h(n) = cos + cos ; n = 0, 1, 2, ..., 6.
7 7 7
This is the unit sample response of the FIR filter obtained using frequency sampling technique.

2 2π(3 − 0) 4π(3 − 0) 2 6π 12π

   
h(0) = cos + cos = cos + cos = −0.0793
7 7 7 7 7 7
2 2π(3 − 1) 4π(3 − 1) 2 4π 8π
   
h(1) = cos + cos = cos + cos = −0.321
7 7 7 7 7 7
2 2π(3 − 2) 4π(3 − 2) 2 2π 4π
   
h(2) = cos + cos = cos + cos = 0.1145
7 7 7 7 7 7
2 2π(3 − 3) 4π(3 − 3) 2
 
h(3) = cos + cos = [cos 0 + cos 0] = 0.5741
7 7 7 7
2 2π(3 − 4) 4π(3 − 4) 2 −2π −4π
   
h(4) = cos + cos = cos + cos = 0.1145
7 7 7 7 7 7
2 2π(3 − 5) 4π(3 − 5) 2 −4π −8π
   
h(5) = cos + cos = cos + cos = −0.321
7 7 7 7 7 7
2 2π(3 − 6) 4π(3 − 6) 2 −6π −12π
   
h(6) = cos + cos = cos + cos = −0.0793
7 7 7 7 7 7

h(n) = {−0.0793, −0.321, 0.1145, 0.5741, 0.1145, −0.321, −0.0793}

3.6 Direct form Structure of FIR Systems

The realization for FIR systems is obtained by convolution of h(n) and x(n)

M
X −1
y(n) = h(k)x(n − k) (3.15)
k=0
Digital Signal Processing 103

The above equation can be expanded as,

y(n) = h(0)x(n) + h(1)x(n − 1) + h(2)x(n − 2) + ... + h(M − 1)x(n − M + 1) (3.16)

Implementation of direct form structure of FIR filter is based upon the above equation is
shown in Fig. 3.3. It is observed that,

• There are M − 1 unit delay blocks. One unit delay block requires one memory location.
Hence direct form structure requires M − 1 memory locations.

• The multiplication of h(k) and x(n − k) is performed for 0 to M-1 terms. Hence M
multiplications and M − 1 additions are required.

• Direct form structure is often called as transversal or tapped delay line filter.

x(n-1) x(n-2) x(n-M+1)

x(n) Z-1 Z-1 Z-1

h(0) h(1) h(2) h(M-1)

+ + + + y(n)

Fig. 3.3. Direct form realization of FIR filter.

3.7 Cascade form Structure of FIR Systems

In cascade form, stages are cascaded (connected) in series. The output of one system is
input to another. Thus total K number of stages are cascaded. The system function of FIR
system is given as
M −1
bk z −k
X
H(z) = (3.17)
k=0

H(z) = H1 (z) × H2 (z) × H3 (z) × ... × HK (z) (3.18)

where,
Hk (z) = bk0 + bk1 z −1 + bk2 z −2 + ... + bkM z −M

We know that
Yk (z)
Hk (z) = .
Xk (z)
104 Module-3

Yk (z)
= bk0 + bk1 z −1 + bk2 z −2 + ... + bkM z −M (3.19)
Xk (z)
Taking inverse z-transform of the eqn. (3.18),

yk (n) = bk0 xk (n) + bk1 xk (n − 1) + ... + bkM xk (n − M ) (3.20)

3.8 Lattice Structure of FIR Systems

Lattice filters are used extensively in digital speech processing and in the implementation
of adaptive filters. Lattice FIR filters are computationally efficient for the implementation of
wavelet transforms using filter bank and also, less sensitive to finite word length effect. Let
us begin the development by considering a sequence of FIR filters with system functions

Hm (z) = Am (z); m = 0, 1, 2, . . . , M − 1

where, Am (z) is the polynomial

m
am (k)z −k ;
X
Am (z) = 1 + m≥1
i=1

also, A0 (z) = 1. Therefore,

m
am (k)z −k ;
X
Hm (z) = 1 + m≥1
i=1

m
Y (z)
am (k)z −k
X
Hm (z) = =1+
X(z) i=1
m
am (k)z −k X(z)
X
∴ Y (z) = X(z) +
i=1

Applying inverse z-transform,

m
X
y(n) = x(n) + am (k)x(n − k)
k=1

The following formula is used to convert direct form to lattice.

For m = M, M − 1, .., 2, 1 do
Digital Signal Processing 105

km = am (m)
am (i) − am (m)am (m − i)
am−1 (i) = 2
; 1≤i≤m−1
1 − km
Conversion from lattice to direct form structure

For m = 1, 2, ..., M do

am (0) = 1

am (m) = km

am (i) = am−1 (i) + am (m)am−1 (m − i); 1≤i≤m−1

Example 3.11: Determine the direct form realization of the system

H(z) = 1 + 2z −1 − 3z −2 − 4z −3 + 5z −4

 Solution: Direct form realization

x(n) Z-1 Z-1 Z-1 Z-1

1 2 -3 -4 5
+ + + + y(n)

Example 3.12: Obtain the cascade realization of the system

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

 Solution:
H1 (z) = (1 + 2z −1 − z −2 ) and H2 (z) = (1 + z −1 − z −2 )
106 Module-3

x(n) Z-1 Z-1

1 2 -1
+ + Z-1 Z-1

1 1 -1
+ + y(n)

Example 3.13: Realize the following system in direct form

H(z) = 1 + 3/4z −1 + 17/8z −2 + 3/4z −3 + z −4

 Solution: Direct form:

x(n) Z-1 Z-1 Z-1 Z-1

1 3/4 17/8 3/4 1

+ + + + y(n)

Example 3.14: Realize the following system in cascade form

H(z) = 1 + 5/2z −1 + 2z −2 + 2z −3

 Solution:
−1 −2 −3 z 3 + 52 z 2 + 2z + 2
H(z) = 1 + 5/2z + 2z + 2z =
z3
z 2 + 1/2z + 1
(z + 2) z 3 + 5/2z 2 + 2z + 2
z 3 + 2z 2
1/2z
 2 + 2z

1/2z
 2+z

z+
 2

z+
 2


0
Digital Signal Processing 107

(z + 2)(z 2 + 0.5z + 1) (z + 2) (z 2 + 0.5z + 1)

H(z) = =
z.z 2 z z2
H(z) = (1 + 2z −1 )(1 + 0.5z −1 + z −2 )
H(z) = H1 (z) × H2 (z)

x(n) Z-1

1 2
+ Z-1 Z-1

1 0.5 1
+ + y(n)

Example 3.15: Realize the following system in direct form.

 n
1
h(n) = [u(n) − u(n − 5)]
2

 Solution:  n
1
h(n) = [u(n) − u(n − 5)]
2
"          #
1 0 1 1 1 2 1 3 1 4
h(n) = , , , ,
2 2 2 2 2
h(n) = {1, 1/2, 1/4, 1/8, 1/16}
∴ H(z) = 1 + 1/2z −1 + 1/4z −2 + 1/8z −3 + 1/16z −4

x(n) Z-1 Z-1 Z-1 Z-1

1 1/2 1/4 1/8 1/16

+ + + + y(n)

Example 3.16: Determine the coefficients and also draw the lattice structure for the system
108 Module-3

function
H(z) = 1 + 2z −1 + 1/3z −2

 Solution: Here, M = 2, a2 (1) = 2, a2 (2) = 1/3

For m = M, M − 1, .., 2, 1 do

km = am (m)
am (i) − am (m)am (m − i)
am−1 (i) = 2
; 1≤i≤m−1
1 − km

m = 2; k2 = a2 (2) = 1/3
a2 (1) − a2 (2)a2 (1)
m = 2 & i = 1; a1 (1) =
1 − k22
2 − 1/3 × 2 3
a1 (1) = =
1 − 1/9 2
3
m = 1; k1 = a1 (1) =
2
3 1
k1 = , k2 =
2 3

+ + y(n)
k1 k2
x(n)
k1 k2
Z-1 + Z-1 + r2(n)

Example 3.17: Given the difference equation y(n) = x(n)+3.1x(n−1)+5.5x(n−2)+4.2x(n−

3) + 2.3x(n − 4). Sketch the FIR lattice realization of the filter.

 Solution:

y(n) = x(n) + 3.1x(n − 1) + 5.5x(n − 2) + 4.2x(n − 3) + 2.3x(n − 4)

Y (z) = X(z) + 3.1z −1 X(z) + 5.5z −2 X(z) + 4.2z −3 X(z) + 2.3z −4 X(z)
Digital Signal Processing 109

Y (z)
= H(z) = 1 + 3.1z −1 + 5.5z −2 + 4.2z −3 + 2.3z −4
X(z)
M = 4, a4 (1) = 3.1, a4 (2) = 5.5, a4 (3) = 4.2, a4 (4) = 2.3

For m = M, M − 1, .., 2, 1 do

km = am (m)
am (i) − am (m)am (m − i)
am−1 (i) = 2
; 1≤i≤m−1
1 − km
For M = 4; k4 = a4 (4) = 2.3

a4 (i) − a4 (4)a4 (4 − i)
a3 (i) = ; 1≤i≤3
1 − k42
a4 (1) − a4 (4)a4 (3) 3.1 − 2.3 × 4.2
i = 1; a3 (1) = 2 = = 1.529.
1 − k4 1 − 2.32
a4 (2) − a4 (4)a4 (2) 5.5 − 2.3 × 5.5
i = 2; a3 (2) = = = 1.667.
1 − k42 1 − 2.32
a4 (3) − a4 (4)a4 (1) 4.2 − 2.3 × 3.1
i = 3; a3 (3) = 2 = = 0.683.
1 − k4 1 − 2.32

For M = 3; k3 = a3 (3) = 0.683

a3 (i) − a3 (3)a3 (3 − i)
a2 (i) = ; 1≤i≤2
1 − k32
a3 (1) − a3 (3)a3 (2) 1.529 − 0.683 × 1.667
i = 1; a2 (1) = 2 = = 0.732.
1 − k3 1 − 0.6832
a3 (2) − a3 (3)a3 (1) 1.667 − 0.683 × 1.529
i = 2; a2 (2) = = = 1.167.
1 − k32 1 − 0.6832

For M = 2; k2 = a2 (2) = 1.167

a2 (i) − a2 (2)a2 (2 − i)
a1 (i) = ; i=1
1 − k22
a2 (1) − a2 (2)a2 (1) 0.732 − 1.167 × 0.732
i = 1; a1 (1) = 2 = = 0.338.
1 − k2 1 − 1.1672
k1 = 0.338

k1 = 0.338, k2 = 1.137, k3 = 0.683, k4 = 2.3

110 Module-3

+ + + + y(n)
k1 k2 k3 k4
x(n)
k1 k2 k3 k4
Z-1 + Z-1 + Z-1 + Z-1 + r4(n)

Example 3.18: Let k1 = 0.1, k2 = 0.2, k3 = 0.3, are the 3-stage FIR lattice coefficients.
Realize the filter using lattice and direct form.

 Solution: Given, M = 3
For m = 1, 2, ..., M do

am (0) = 1

am (m) = km

am (i) = am−1 (i) + am (m)am−1 (m − i); 1≤i≤m−1

For m = 1
a1 (0) = 1
a1 (1) = k1 = 0.1

+ + + y(n)
k1 k2 k3
x(n)
k1 k2 k3
Z-1 + Z-1 + Z-1 + r3(n)

For m = 2
a2 (0) = 1
a2 (2) = k2 = 0.2
a2 (i) = a1(i) + a2 (2)a1 (2 − i); i=1
a2 (1) = a1 (1) + a2 (2)a1 (1)
a2 (1) = 0.1 + 0.2 × 0.1 = 0.12
Digital Signal Processing 111

For m = 3
a3 (0) = 1
a3 (3) = k3 = 0.3
a3 (i) = a2 (i) + a3 (3)a2 (3 − i); i = 1, 2
a3 (1) = a2 (1) + a3 (3)a2 (2) = 0.12 + 0.3 × 0.2 = 0.18
a3 (2) = a2 (2) + a3 (3)a2 (1) = 0.2 + 0.3 × 0.12 = 0.56
Thus,
H(z) = 1 + a3 (1)z −1 + a3 (2)z −2 + a3 (3)z −3
H(z) = 1 + 0.18z −1 + 0.56z −2 + 0.3z −3

x(n) Z-1 Z-1 Z-1

1 0.18 0.56 0.3

+ + + y(n)

Example 3.19: What is Gibbs phenomenon and why it occurs?

 Solution: To describe a signal with a sharp transient in the time domain requires infinite
frequency content. In practice, it is not possible to sample infinite frequency content. The
truncation of higher frequency content causes a time domain ringing artifact near the band
edge of the filter which is often referred to as the Gibbs phenomenon. It can be reduced by
selectig proper window.