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}

1.4.10 Multiplication in time-domain/Modulation property

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

1
DFT{x1 (n) × x2 (n)} = N X1 (k) ⊗N X2 (k)
Digital Signal Processing 37

Proof:
N
X −1
DFT{x(n)} = X(k) = x(n)WNkn
n=0
N
X −1
DFT{x1 (n) × x2 (n)} = [x1 (n) × x2 (n)]WNkn
n=0
N −1
X2 (l)WN−ln
X
1
where, x2 (n) = N
k=0
N −1 −1
1 NX
X2 (l)WN−ln WNkn
X
DFT{x1 (n) × x2 (n)} = x1 (n) ×
n=0
N k=0
N −1 N −1
1
[x1 (n)WN−ln ]WNkn
X X
DFT{x1 (n) × x2 (n)} = X2 (l)
N k=0 n=0
N −1
1
X2 (l) DFT{x1 (n)WN−ln }
X
DFT{x1 (n) × x2 (n)} =
N k=0
−1
1 NX
DFT{x1 (n) × x2 (n)} = X2 (l)X1 ((k − l))N ∵ Circular frequency shift property
N k=0
1
∴ DFT{x1 (n) × x2 (n)} = N X1 (k) ⊗N X2 (k)
38 Module-1

DSP FORMULAS
N −1
X −j2πkn
• X(k) = x(n) · e N

n=0

N −1
X j2πkn
1
• x(n) = N X(k) · e N

k=0

N −1
X 1 − αN
• αn =
n=0
1−α
∞
X 1
• αn =
n=0
1−α
−j2πkn
• e N = cos( 2πkn 2πkn
N ) − j · sin( N )

• ω = e−j2π
−j2π
• ωN = e N

−j2πkn
kn = e
• ωN N

• DF T {δ(n)} = 1
mk
• DF T {δ(n − m)} = ωN
−mk
• DF T {δ(n + m)} = ωN
 
1 1 1 1
 
 1 −j −1 j 
• 4 × 4 matrix f or DF T = 
 

 1 −1 1 −1 
 
1 j −1 −j
 
1 1 1 1
 
 1 j −1 −j 
• 4 × 4 matrix f or IDF T = 41 × 
 

 1 −1 1 −1 
 
1 −j −1 j
N
• Linearity: If x(n) ←
→ X(k) then
DF T {a · x1 (n) + b · x2 (n)} = a · X1 (k) + b · X2 (k)
N
• Circular - time shift: If x(n) ←
→ X(k) then
mk · X(k)
DF T {x((n − m))N } = ωN
Digital Signal Processing 39
N
• Circular - frequency shift: If x(n) ←
→ X(k) then
−mn
DF T {ωN · x(n)} = X((k − m))N

• Symmetry: If the sequence x(n) is real, then its DFT is such that
X(k) = X ∗ (N − k)
N
• Circular folding: If x(n) ←
→ X(k) then
DF T {x((−n))N } = X((−k))N
N
• Symmetry: DFT of real even and real odd sequences: If x(n) ←
→ X(k) then
DF T {xe (n)} = A = P urely real and DF T {x0 (n)} = jB = P urely imaginary
N
• DFT of a complex conjugate sequence: If x(n) ←
→ X(k) then
DF T {x∗ (n)} = X ∗ (N − k) = X ∗ ((−k))N
1
• Multiplication in time: DF T {x1 (n) · x2 (n)} = N · X1 (k) ~N X2 (k)

• Circular convolution in time is equivalent to multiplication in frequency domain:

DF T {x(n) ~N y(n)} = X(k) · H(k)
N −1 −1
∗ 1 NX
X ∗ (k)Y (k)
X
• Parseval’s theorem/Inner product: x (n)y(n) =
n=0
N k=0
N −1 −1
X 1 NX
| x(n) |2 = | X(k) |2
n=0
N k=0