Prepared by Dr.

Harish M S, AIT

Module 2
Z-Transforms
Definition of Z-transform: The Z-transform is the powerful mathematical tool for the analysis
of discrete signals and systems. The Z-transform of a discrete-time signal 𝑥(𝑛) is defined as the
power series
∞

𝑍 {𝑥(𝑛)} = 𝑋(𝑧) = ∑ 𝑥(𝑛)𝑧 −𝑛

𝑛=−∞

The above relation is sometimes called the direct Z-transform because it transforms the time-
domain signal 𝑥(𝑛) in to its complex plane representation 𝑋(𝑧). Where z is a complex variable,
in polar form z is expressed as
𝑧 = 𝑟𝑒 𝑗𝜃
Where 𝑟 = |𝑧| and 𝜃 = ∠𝑧 and the relation 𝑋(𝑧) and 𝑥(𝑛) is indicated by
𝑧
𝑥(𝑛) ↔ 𝑋(𝑧)
Since the Z-transform is an infinite power series, it exists only for those values of z for which the
series converges. The region of convergence (ROC) of 𝑋(𝑧) is the set of all the values of z for
which 𝑋(𝑧) attains a finite value. Thus, for z-transform, we have to mention ROC. We illustrates
these concepts by some simple examples
Problem: Determine the Z-transform of the following finite duration signals
1, 2, 5, 7, 0, 1
a) 𝑥1 (𝑛) = ( )
↑
1, 2, 5, 7, 0, 1
b) 𝑥2 (𝑛) = ( )
↑
0, 0, 1, 2, 5, 7, 0, 1
c) 𝑥3 (𝑛) = ( )
↑
2, 4, 5, 0, 1
d) 𝑥4 (𝑛) = ( )
↑
e) 𝑥5 (𝑛) = 𝛿(𝑛)
f) 𝑥6 (𝑛) = 𝛿 (𝑛 − 𝑘), 𝑘 > 0
g) 𝑥7 (𝑛) = 𝛿 (𝑛 + 𝑘), 𝑘>0
Solution:
1, 2, 5, 7, 0, 1
a) 𝑥1 (𝑛) = ( )
↑
The z-Transform of 𝑥1 (𝑛) is defined as

1
 Prepared by Dr.Harish M S, AIT

𝑍{𝑥1 (𝑛)} = 𝑋1 (𝑧) = ∑ 𝑥1 (𝑛)𝑧 −𝑛

𝑛=−∞
5

𝑋1 (𝑧) = ∑ 𝑥1 (𝑛)𝑧 −𝑛 = 𝑥1 (0)𝑧 0 + 𝑥1 (1)𝑧 −1 + 𝑥1 (2)𝑧 −2 + 𝑥1 (3)𝑧 −3 + 𝑥1 (4)𝑧 −4 + 𝑥1 (5)𝑧 −1

𝑛=0

𝑋1 (𝑧) = 1 + 2𝑧 −1 + 5𝑧 −2 + 7𝑧 −3 + 𝑧 −5 , ROC: is on the entire z-plane except 𝑧 = 0. The ROC

diagram is as shown in figure 2.1.

1, 2, 5, 7, 0, 1
b) 𝑥2 (𝑛) = ( )
↑
The z-transform of 𝑥2 (𝑛) is defined as 𝑍{𝑥2 (𝑛)} = 𝑋2 (𝑧) = ∑∞
𝑛=−∞ 𝑥2 (𝑛)𝑧
−𝑛

𝑋2 (𝑧) = ∑ 𝑥2 (𝑛)𝑧 −𝑛
𝑛=−2

= 𝑥2 (−2)𝑧 2 + 𝑥2 (−1)𝑧 1 + 𝑥1 (0)𝑧 0 + 𝑥1 (1)𝑧 −1 + 𝑥1 (2)𝑧 −2 + 𝑥1 (3)𝑧 −3

𝑋1 (𝑧) = 𝑧 2 + 2𝑧 1 + 5 + 7𝑧 −1 + 𝑧 −3 , ROC: is on the entire z-plane except 𝑧 = 0 and 𝑧 = ∞.
The ROC diagram is as shown in figure 2.2.

2
 Prepared by Dr.Harish M S, AIT

0, 0, 1, 2, 5, 7, 0, 1
c) 𝑥3 (𝑛) = ( )
↑
The z-Transform 𝑥3 (𝑛)is defined as 𝑍{𝑥3 (𝑛)} = 𝑋3 (𝑧) = ∑∞
𝑛=−∞ 𝑥3 (𝑛 )𝑧
−𝑛

𝑋3 (𝑧) = ∑ 𝑥3 (𝑛)𝑧 −𝑛 = 𝑥3 (0)𝑧 0 + 𝑥3 (1)𝑧 −1 + 𝑥3 (2) + 𝑧 −2 +𝑥3 (3)𝑧 −3 + 𝑥3 (4)𝑧 −4

𝑛=0

+ 𝑥3 (5)𝑧 −5 + 𝑥3 (6)𝑧 −6 + 𝑥3 (7)𝑧 −7

𝑋3 (𝑧) = 0 + 0 + 𝑧 −2 + 2𝑧 −3 + 5𝑧 −4 + 7𝑧 −5 + 0 + 𝑧 −7
𝑋3 (𝑧) = 𝑧 −2 + 2𝑧 −3 + 5𝑧 −4 + 7𝑧 −5 + 𝑧 −7 , ROC: is on the entire z-plane except 𝑧 = 0. The
ROC diagram is as shown in figure 2.3.

2, 4, 5, 0, 1
d) 𝑥4 (𝑛) = ( )
↑
The z-Transform 𝑥4 (𝑛) is defined as 𝑍{𝑥4 (𝑛)} = 𝑋4 (𝑧) = ∑∞
𝑛=−∞ 𝑥4 (𝑛)𝑧
−𝑛

𝑋4 (𝑧) = ∑ 𝑥4 (𝑛)𝑧 −𝑛 = 𝑥4 (−2)𝑧 2 + 𝑥4 (−2)𝑧 1 + 𝑥4 (0)𝑧 0 + 𝑥4 (1)𝑧 −1 + 𝑥4 (2)𝑧 −2

𝑛=−2

𝑋4 (𝑧) = 2𝑧 2 + 4𝑧 + 5 + 0 + 𝑧 −2
𝑋4 (𝑧) = 2𝑧 2 + 4𝑧 + 5 + 𝑧 −2 , ROC: is on the entire z-plane except 𝑧 = 0 and 𝑧 = ∞.The ROC
diagram is as shown in figure 2.4.

3
 Prepared by Dr.Harish M S, AIT

e) 𝑥5 (𝑛) = 𝛿(𝑛)
The z-Transform is 𝑥5 (𝑛) is defined as 𝑍{𝑥5 (𝑛)} = 𝑋5 (𝑧) = ∑∞
𝑛=−∞ 𝑥5 (𝑛)𝑧
−𝑛

∞ ∞
−𝑛
𝑋5 (𝑧) = ∑ 𝑥5 (𝑛)𝑧 = ∑ 𝛿(𝑛)𝑧 −𝑛 = 1
𝑛=−∞ 𝑛=−∞

𝑋5 (𝑧) = 1, ROC: is on the entire z-plane. The ROC diagram is as shown in figure2.5.

f) 𝑥6 (𝑛) = 𝛿 (𝑛 − 𝑘), 𝑘 > 0

The z-Transform 𝑥6 (𝑛) is defined as 𝑍{𝑥6 (𝑛)} = 𝑋6 (𝑧) = ∑∞
𝑛=−∞ 𝑥6 (𝑛)𝑧
−𝑛

∞ ∞

𝑋6 (𝑧) = ∑ 𝑥6 (𝑛)𝑧 −𝑛 = ∑ 𝛿 (𝑛 − 𝑘)𝑧 −𝑛 = 𝑧 −𝑘

𝑛=−∞ 𝑛=−∞

𝑋6 (𝑧) = 𝑧 −𝑘 , ROC: is on the entire z-plane except 𝑧 = 0. The ROC diagram is as shown in
figure 2.6.

4
 Prepared by Dr.Harish M S, AIT

g) 𝑥7 (𝑛) = 𝛿 (𝑛 + 𝑘), 𝑘>0

The z-Transform 𝑥7 (𝑛) is defined as 𝑍{𝑥7 (𝑛)} = 𝑋7 (𝑧) = ∑∞
𝑛=−∞ 𝑥7 (𝑛)𝑧
−𝑛

∞ ∞
−𝑛
𝑋7 (𝑧) = ∑ 𝑥7 (𝑛)𝑧 = ∑ 𝛿 (𝑛 + 𝑘)𝑧 −𝑛 = 𝑧 𝑘
𝑛=−∞ 𝑛=−∞
−𝑘
𝑋7 (𝑧) = 𝑧 , ROC: is on the entire z-plane except 𝑧 = ∞. The ROC diagram is as
shown in figure 2.7.

1 𝑛
Problem: Determine the z-transform of the signal 𝑥(𝑛) = (2) 𝑢(𝑛) and mention ROC of 𝑋(𝑧).
1 𝑛
1 𝑛 (2) , 𝑛≥0
Solution: 𝑥(𝑛) = (2) 𝑢(𝑛) = {
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
The right hand side infinite duration decreasing signal 𝑥(𝑛) is as shown in figure 2.8.
The z-Transform 𝑥(𝑛) is defined as 𝑍{𝑥 (𝑛)} = 𝑋 (𝑧) = ∑∞
𝑛=−∞ 𝑥(𝑛)𝑧
−𝑛

5
 Prepared by Dr.Harish M S, AIT

∞ ∞
1 1 1 1
𝑋 (𝑧) = ∑( )𝑛 𝑧 −𝑛 = ∑( 𝑧 −1 )𝑛 = 1 −1 , 𝑖𝑓 | 𝑧 −1 | < 1
2 2 1 − 𝑧 2
𝑛=0 𝑛=0 2

1 2𝑧
𝑋 (𝑧 ) = 1 =
1 − 2 𝑧 −1 2𝑧 − 1

1
To determine ROC, consider | 𝑧 −1 | < 1
2

1
| |<1
2𝑧
1
| | < |𝑧 |
2
1
|𝑧 | >
2
1
ROC: |𝑧| > 2, the ROC diagram as shown in figure 2.9.
2𝑧 1
Therefore, z-transform of 𝑥(𝑛)is 𝑋 (𝑧) = , with ROC: |𝑧| >
2𝑧−1 2

From the ROC diagram, if 𝑥(𝑛) is decrementing exponential right hand side signal, ROC is
1
exterior to the circle of radius |𝑧| > 2.

6
 Prepared by Dr.Harish M S, AIT

Problem: Determine the z-transform of the signal 𝑥(𝑛) = 𝑎𝑛 𝑢(𝑛) and mention ROC of 𝑋(𝑧),
and 0 < 𝑎 < 1.
𝑎𝑛 , 𝑛≥0
Solution: 𝑥(𝑛) = 𝑎𝑛 𝑢(𝑛) = {
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
The right hand side infinite duration decreasing signal 𝑥(𝑛) is as shown in figure 2.10.

The z-Transform 𝑥(𝑛) is defined as 𝑍{𝑥 (𝑛)} = 𝑋 (𝑧) = ∑∞

𝑛=−∞ 𝑥(𝑛)𝑧
−𝑛

∞ ∞
𝑛 −𝑛
1
𝑋 (𝑧 ) = ∑ 𝑎 𝑧 = ∑(𝑎𝑧 −1 )𝑛 = , 𝑖𝑓 |𝑎𝑧 −1 | < 1
1 − 𝑎𝑧 −1
𝑛=0 𝑛=0

1 𝑧
𝑋 (𝑧 ) = =
1 − 𝑎𝑧 −1 𝑧 − 𝑎
To determine ROC, consider |𝑎𝑧 −1 | < 1
𝑎
| |<1
𝑧
|𝑎 | < |𝑧 |
|𝑧 | > 𝑎
ROC: |𝑧| > 𝑎, the ROC diagram as shown in figure 2.11.
𝑧
Therefore, z-transform of 𝑥(𝑛)is 𝑋 (𝑧) = , with ROC: |𝑧| > 𝑎
𝑧−𝑎

7
 Prepared by Dr.Harish M S, AIT

From the ROC diagram, if 𝑥(𝑛) is decrementing exponential right hand side signal, ROC is
exterior to the circle of radius |𝑧| > 𝑎.
Problem: Determine the Z-transform of the signal 𝑥(𝑛) = −𝑎𝑛 𝑢(−𝑛 − 1) and mention ROC
of 𝑋(𝑧) , and 0 < 𝑎 < 1.
0, 𝑛≥0
Solution: 𝑥(𝑛) = −𝑎𝑛 𝑢(−𝑛 − 1) = { 𝑛
−𝑎 𝑛 ≤ −1
The left hand side infinite duration decreasing negative amplitude signal 𝑥(𝑛) is as shown in
figure 2.12.

The z-Transform 𝑥(𝑛) is defined as 𝑍{𝑥 (𝑛)} = 𝑋 (𝑧) = ∑∞

𝑛=−∞ 𝑥(𝑛)𝑧
−𝑛

−1 ∞
𝑛 −𝑛
𝑋(𝑧) = ∑ −𝑎 𝑧 = − ∑(𝑎−1 𝑧)𝑛
𝑛=−∞ 𝑛=1

Put 𝑙 = 𝑛 − 1, 𝑛 = 𝑙 + 1, 𝑖𝑓 𝑛 = 1, 𝑙 = 0, 𝑖𝑓 𝑛 = ∞, 𝑙 = ∞
∞ ∞
−1 𝑙+1
1
𝑋 (𝑧) = − ∑(𝑎 𝑧) = −𝑎 𝑧 ∑(𝑎−1 𝑧)𝑙 = − 𝑎−1 𝑧 (
−1
) , 𝑖𝑓 |𝑎−1 𝑧| < 1
1 − 𝑎−1 𝑧
𝑙=0 𝑙=0

−𝑎−1 𝑧 𝑎−1 𝑧 𝑧
𝑋 (𝑧 ) = −1
= −1
=
1−𝑎 𝑧 𝑎 𝑧−1 𝑧−𝑎
To determine ROC, consider |𝑎−1 𝑧| < 1
𝑧
| |<1
𝑎
|𝑧 | < |𝑎 |
|𝑧 | < 𝑎
ROC: |𝑧| < 𝑎, the ROC diagram as shown in figure 2.13.
𝑧
Therefore, z-transform of 𝑥(𝑛)is 𝑋 (𝑧) = , with ROC: |𝑧| < 𝑎
𝑧−𝑎

8
 Prepared by Dr.Harish M S, AIT

From the ROC diagram, if 𝑥(𝑛) is decrementing exponential left hand signal, ROC is enterior to
the circle of radius |𝑧| < 𝑎.
Problem: Determine the z-transform of the signal 𝑥(𝑛) = 𝑎𝑛 𝑢(𝑛)+𝑏𝑛 𝑢(−𝑛 − 1) and mention
ROC of 𝑋(𝑧).
Solution: 𝑥(𝑛) = 𝑎𝑛 𝑢(𝑛)+𝑏𝑛 𝑢(−𝑛 − 1)
−𝑏𝑛 , 𝑛 < −1
𝑥 (𝑛 ) = = { 𝑛 , the signal 𝑥(𝑛) is two sided, infinite duration.
𝑎 𝑛≥0
The z-Transform 𝑥(𝑛) is defined as 𝑍{𝑥 (𝑛)} = 𝑋 (𝑧) = ∑∞
𝑛=−∞ 𝑥(𝑛)𝑧
−𝑛

−1 ∞ ∞ ∞

𝑋(𝑧) = ∑ 𝑏𝑛 𝑧 −𝑛 + ∑ 𝑎𝑛 𝑧 −𝑛 = ∑(𝑏−1 𝑧)𝑛 + ∑ 𝑎𝑛 𝑧 −𝑛

𝑛=−∞ 𝑛=0 𝑛=1 𝑛=0

In first summation, put 𝑙 = 𝑛 − 1, 𝑛 = 𝑙 + 1, 𝑖𝑓 𝑛 = 1, 𝑙 = 0, 𝑖𝑓 𝑛 = ∞, 𝑙 = ∞

∞ ∞

𝑋 (𝑧) = ∑(𝑏−1 𝑧)𝑙+1 + ∑(𝑎𝑧 −1 )𝑛

𝑙=1 𝑛=0
∞ ∞
−1 −1
𝑋 (𝑧 ) = 𝑏 𝑧 ∑(𝑏 𝑧) + ∑(𝑎𝑧 −1 )𝑛
𝑙

𝑙=1 𝑛=0

𝑏 −1 𝑧 1
𝑋 (𝑧 ) = + , 𝑖𝑓 |𝑏 −1 𝑧| < 1 𝑎𝑛𝑑 |𝑎𝑧 −1 | < 1
1 − 𝑏 𝑧 1 − 𝑎𝑧 −1
−1

𝑏 −1 𝑧 1 𝑧 𝑧
𝑋 (𝑧 ) = −
−1
+ −1
=− +
𝑏 𝑧 − 1 1 − 𝑎𝑧 𝑧−𝑏 𝑧−𝑎
To determine ROC, consider |𝑏 −1 𝑧| < 1 and |𝑎𝑧 −1 | < 1
𝑧 𝑎
| |<1 | |<1
𝑏 𝑧

9
 Prepared by Dr.Harish M S, AIT

| 𝑧 | < |𝑏 | | 𝑎 | < |𝑧 |
|𝑧 | < 𝑏 |𝑧 | > 𝑎
Case 1|𝑏 | > |𝑎|: In this case the two 𝑅𝑂𝐶 do not overlap, thus 𝑋(𝑧) does not exist.
Case 1|𝑏 | < |𝑎|: In this case the two 𝑅𝑂𝐶 are overlapped, thus 𝑋(𝑧) exist. For these two cases
ROC diagram as shown in figure 2.14. From the diagram if |𝑏 | < |𝑎| 𝑋(𝑧) exist and ROC is
𝑎 < |𝑧| < 𝑏 is a ring like structure.

𝑧 𝑧
∴ 𝑋 (𝑧 ) = − + 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 𝑎 < |𝑧| < 𝑏 𝑖𝑓 |𝑏 | < |𝑎|
𝑧−𝑏 𝑧−𝑎
From these above examples, we see that the ROC of a signal depends both on duration and on
whether it is casual (Right side signal), anticausal (Left side signal) or two sided.
Properties of the z-Transform (Statements only)
The z-transform is a very powerful mathematical tool for the study of discrete-time signals and
systems. Some important properties of the z-transforms are
1. Linearity
2. Time shifting
3. Scaling in the z-domain
4. Time reversal
5. Differentiation in the z-domain
6. Convolution of two sequences
7. Correlation of two sequences
8. Multiplication of two sequences

10
 Prepared by Dr.Harish M S, AIT

9. Parseval’s relation
10. The initial value theorem
Linearity
𝑧 𝑧
Statement: If 𝑥1 (𝑛) ↔ 𝑋1 (𝑧) and 𝑥2 (𝑛) ↔ 𝑋2 (𝑧)
𝑧
Then 𝑥(𝑛) = 𝑎1 𝑥1 (𝑛) + 𝑎2 𝑥2 (𝑛) ↔ 𝑋(𝑧) = 𝑎1 𝑋1 (𝑧) + 𝑎2 𝑋2 (𝑧)
Problem: Determine the z-transform and ROC of the signal 𝑥(𝑛) = [3(2)𝑛 − 4(3)𝑛 ]𝑢(𝑛)
Solution: 𝑥(𝑛) = [3(2𝑛 ) − 4(3𝑛 )]𝑢(𝑛) = 3(2𝑛 )𝑢(𝑛) − 4(3𝑛 )𝑢(𝑛) = 𝑎1 𝑥1 (𝑛) + 𝑎2 𝑥2 (𝑛)
Thus, we define 𝑥1 (𝑛) = 3(2)𝑛 𝑢(𝑛) and 𝑥2 (𝑛) = 4(3)𝑛 𝑢(𝑛)
𝑧
Let 𝑥(𝑛) = 𝑎1 𝑥1 (𝑛) + 𝑎2 𝑥2 (𝑛) ↔ 𝑋 (𝑧) = 𝑎1 𝑋1 (𝑧) + 𝑎2 𝑋2 (𝑧)
𝑧 1
𝑥1 (𝑛) = 2𝑛 𝑢(𝑛) ↔ 𝑋1 (𝑧) = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 2
1 − 2𝑧 −1
𝑧 1
𝑥2 (𝑛) = 3𝑛 𝑢(𝑛) ↔ 𝑋2 (𝑧) = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 3
1 − 3𝑧 −1
3 4
𝑋 (𝑧) = 𝑎1 𝑋1 (𝑧) + 𝑎2 𝑋2 (𝑧) = 3𝑋1 (𝑧) − 4𝑋2 (𝑧) = −1
− , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 3
1 − 2𝑧 1 − 3𝑧 −1
Problem: Determine the z-transform of the signals 𝑥 (𝑛) = 𝑒 𝑗𝜔0 𝑛 𝑢(𝑛)
Solution:𝑥(𝑛) = 𝑒 𝑗𝜔0 𝑛 𝑢(𝑛)
∞

𝑍[𝑥(𝑛)] = 𝑋(𝑧) = ∑ 𝑥(𝑛)𝑧 −𝑛

𝑛=−∞
∞ ∞
1
𝑋(𝑧) = ∑ 𝑒 𝑗𝜔0 𝑛 𝑧 −𝑛 = ∑(𝑒 𝑗𝜔0 𝑧 −1 )𝑛 = , |𝑒 𝑗𝜔0 𝑧 −1 | < 1
1 − 𝑒 𝑗𝜔0 𝑧 −1
𝑛=0 𝑛=0

For ROC, |𝑒 𝑗𝜔0 𝑧 −1 | < 1, |𝑧 −1 | < 1, |𝑧 | > 1

1
∴ 𝑋 (𝑧 ) = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1 − 𝑒 𝑗𝜔0 𝑧 −1
Problem: Determine the z-transform of the signals
a) 𝑥(𝑛) = (𝑐𝑜𝑠𝜔0 𝑛)𝑢(𝑛)
b) 𝑥(𝑛) = (𝑠𝑖𝑛𝜔0 𝑛)𝑢(𝑛)
1 1
Solution: (𝑎)𝑥(𝑛) = (𝑐𝑜𝑠𝜔0 𝑛)𝑢(𝑛) = 2 𝑒 𝑗𝜔0 𝑛 𝑢(𝑛) + 2 𝑒 −𝑗𝜔0 𝑛 𝑢(𝑛)
1 1
Linearity property implies 𝑋 (𝑧) = 2 𝑍{𝑒 𝑗𝜔0 𝑛 𝑢(𝑛)} + 2 𝑍{𝑒 −𝑗𝜔0 𝑛 𝑢(𝑛)}
𝑧 1
𝑒 𝑗𝜔0 𝑛 𝑢(𝑛) ↔ , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1 − 𝑒 𝑗𝜔0 𝑧 −1

11
 Prepared by Dr.Harish M S, AIT

𝑧 1
𝑒 −𝑗𝜔0 𝑛 𝑢(𝑛) ↔ , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1− 𝑒 −𝑗𝜔0 𝑧 −1
1 1 1 1−𝑒 −𝑗𝜔0 𝑧 −1 +1−𝑒 𝑗𝜔0 𝑧 −1
Therefore 𝑋(𝑧) = + = 2 {(1−𝑒 𝑗𝜔0 𝑧 −1)(1−𝑒 −𝑗𝜔0 𝑧 −1)}
2(1−𝑒 𝑗𝜔0 𝑧 −1 ) 2(1−𝑒 −𝑗𝜔0 𝑧 −1 )

(𝑒 𝑗𝜔0 +𝑒 −𝑗𝜔0 )
1 2 − 𝑧 −1 (𝑒 𝑗𝜔0 + 𝑒 −𝑗𝜔0 ) 1 2 − 2𝑧 −1 2
𝑋 (𝑧 ) = { }= { }
2 1 + 𝑧 −2 − 𝑧 −1 (𝑒 𝑗𝜔0 + 𝑒 −𝑗𝜔0 ) 2 1 + 𝑧 −2 − 2𝑧 −1 (𝑒 𝑗𝜔0 +𝑒 −𝑗𝜔0 )
2
−1
1 − 𝑧 𝑐𝑜𝑠𝜔0
𝑋 (𝑧 ) = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1 + 𝑧 −2 − 2𝑧 −1 𝑐𝑜𝑠𝜔0
1 𝑗𝜔 𝑛 1
(𝑏)𝑥(𝑛) = (𝑠𝑖𝑛𝜔0 𝑛)𝑢(𝑛) = 𝑒 0 𝑢(𝑛) − 𝑒 −𝑗𝜔0 𝑛 𝑢(𝑛)
2𝑗 2𝑗
1 1
Linearity property implies 𝑋 (𝑧) = 2𝑗 𝑍{𝑒 𝑗𝜔0 𝑛 𝑢(𝑛)} − 2𝑗 𝑍{𝑒 −𝑗𝜔0 𝑛 𝑢(𝑛)}

1
𝑍{𝑒 𝑗𝜔0 𝑛 𝑢(𝑛)} = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1 − 𝑒 𝑗𝜔0 𝑧 −1
1
𝑍{𝑒 −𝑗𝜔0 𝑛 𝑢(𝑛)} = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1 − 𝑒 0 𝑧 −1
−𝑗𝜔

1 1 1 1−𝑒 −𝑗𝜔0 𝑧 −1−1+𝑒 𝑗𝜔0 𝑧 −1

Therefore 𝑋(𝑧) = − = 2𝑗 {(1−𝑒 𝑗𝜔0 𝑧 −1 )(1−𝑒 −𝑗𝜔0 𝑧 −1)}
2𝑗(1−𝑒 𝑗𝜔0 𝑧 −1) 2𝑗(1−𝑒 −𝑗𝜔0 𝑧 −1)

(𝑒 𝑗𝜔0 −𝑒 −𝑗𝜔0 )
1 𝑧 −1 (𝑒 𝑗𝜔0
−𝑒 1 −𝑗𝜔0 ) 2𝑧 −1
2
𝑋 (𝑧 ) = { −2 −1 𝑗𝜔 −𝑗𝜔
}= { }
2𝑗 1 + 𝑧 − 𝑧 (𝑒 0 +𝑒 0 ) 2𝑗 1 + 𝑧 −2 − 2𝑧 −1 𝑗𝜔0 +𝑒 −𝑗𝜔0 )
(𝑒
2

(𝑒 𝑗𝜔0 −𝑒 −𝑗𝜔0 )
𝑧 −1 𝑧 −1 𝑠𝑖𝑛𝜔0
2𝑗
𝑋 (𝑧 ) = { } = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1 + 𝑧 −2 − 2𝑧 −1
(𝑒 𝑗𝜔0 +𝑒 −𝑗𝜔0 ) 1 + 𝑧 −2 − 2𝑧 −1 𝑐𝑜𝑠𝜔0
2

Problem: Determine the z-transform of the signals 𝑥(𝑛) = 𝑎|𝑛| .

Solution: 𝑥(𝑛) = 𝑎|𝑛|
𝑎𝑛 , 𝑖𝑓 𝑛 ≥ 0 𝑎𝑛 , 0 ≤ 𝑛 ≤ ∞
𝑥(𝑛) = { 𝑂𝑟 𝑥(𝑛) = { −𝑛
𝑎−𝑛 , 𝑖𝑓 𝑛 < −1 𝑎 , − ∞ ≤ 𝑛 ≤ −1
∞ −1 ∞

𝑍[𝑥(𝑛)] = 𝑋(𝑧) = ∑ 𝑥(𝑛)𝑧 −𝑛 = ∑ 𝑎−𝑛 𝑧 −𝑛 + ∑ 𝑎𝑛 𝑧 −𝑛

𝑛=−∞ 𝑛=−∞ 𝑛=0
∞ ∞ ∞ ∞
𝑛 𝑛 𝑛 −𝑛
𝑋 (𝑧 ) = ∑ 𝑎 𝑧 + ∑ 𝑎 𝑧 = ∑(𝑎𝑧) + ∑(𝑎𝑧 −1 )𝑛
𝑛

𝑛=1 𝑛=0 𝑛=1 𝑛=0

12
 Prepared by Dr.Harish M S, AIT

Put 𝑙 = 𝑛 − 1, in the first summation 𝑛 = 𝑙 + 1, 𝑖𝑓 𝑛 = 1, 𝑙 = 0,

𝑖𝑓 𝑛 = ∞, 𝑙 = ∞
∞ ∞ ∞ ∞
𝑙+1 −1 𝑛
𝑋(𝑧) = ∑ (𝑎𝑧) + ∑(𝑎𝑧 ) = 𝑎𝑧 ∑ (𝑎𝑧) + ∑(𝑎𝑧 −1 )𝑛
𝑙

𝑙=0 𝑛=0 𝑙=0 𝑛=0

𝑎𝑧 1
𝑋(𝑧) = 1−𝑎𝑧 + 1−𝑎𝑧 −1, If |𝑎𝑧| < 1, 𝑎𝑛𝑑 |𝑎𝑧 −1 | < 1, then only 𝑋(𝑧) exist and it converges
𝑎𝑧 𝑧
𝑋 (𝑧 ) = +
1 − 𝑎𝑧 𝑧 − 𝑎
1
For ROC|𝑎𝑧| < 1, |𝑧| < 𝑎 and |𝑎𝑧 −1 | < 1, |𝑧| > 𝑎
𝑎𝑧 𝑧 1
∴ 𝑋 (𝑧 ) = + , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 𝑎 < |𝑧| <
1 − 𝑎𝑧 𝑧 − 𝑎 𝑎
The ROC diagram as shown in figure 2.15

1
( )𝑛 , 𝑛 ≥ 0
3
Problem: Determine the z-transform of the signals 𝑥(𝑛) = { 1 −𝑛
(2) , 𝑛<0
1
(3)𝑛 , 𝑛 ≥ 0
Solution: 𝑥(𝑛) = { 1
(2)−𝑛 , 𝑛 < 0
∞ −1 ∞
−𝑛
1 1
𝑍[𝑥(𝑛)] = 𝑋(𝑧) = ∑ 𝑥(𝑛)𝑧 = ∑ ( )−𝑛 𝑧 −𝑛 + ∑( )𝑛 𝑧 −𝑛
2 3
𝑛=−∞ 𝑛=−∞ 𝑛=0
∞ ∞ ∞ ∞
1 1 1 1
𝑋(𝑧) = ∑( )𝑛 𝑧 𝑛 + ∑( )𝑛 𝑧 −𝑛 = ∑( 𝑧)𝑛 + ∑( 𝑧 −1 )𝑛
2 3 2 3
𝑛=1 𝑛=0 𝑛=1 𝑛=0

13
 Prepared by Dr.Harish M S, AIT

Put 𝑙 = 𝑛 − 1 in the first summation, 𝑛 = 𝑙 + 1, 𝑖𝑓 𝑛 = 1, 𝑙 = 0,

𝑖𝑓 𝑛 = ∞, 𝑙 = ∞
∞ ∞ ∞ ∞
1 1 𝑧 1 1
𝑋 (𝑧) = ∑ ( 𝑧)𝑙+1 + ∑( 𝑧 −1 )𝑛 = ∑ ( 𝑧)𝑙 + ∑( 𝑧 −1 )𝑛
2 3 2 2 3
𝑙=0 𝑛=0 𝑙=0 𝑛=0
𝑧 1 1 1
𝑋 (𝑧 ) = 1 + 1 , If |2 𝑧| < 1, 𝑎𝑛𝑑 |3 𝑧 −1 | < 1, then only 𝑋(𝑧) exist and it converges
2(1− 𝑧) 1− 𝑧 −1
2 3

𝑧 3𝑧
𝑋 (𝑧 ) = +
2 − 𝑧 3𝑧 − 1
1 1 1
For ROC| 2 𝑧| < 1, |𝑧| < 2 and |3 𝑧 −1 | < 1, |𝑧| > 3
𝑧 3𝑧 1
∴ 𝑋 (𝑧 ) = + , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 < |𝑧| < 2
2 − 𝑧 3𝑧 − 1 3
Time shifting
𝑧
Statement: If 𝑥(𝑛) ↔ 𝑋(𝑧)
𝑧
Then 𝑥(𝑛 − 𝑘) ↔ 𝑧 −𝑘 𝑋 (𝑧)
1, 2, 5, 7, 0, 1
Problem: If 𝑥(𝑛) = ( ), determine the z-transform of 𝑥(𝑛), 𝑥(𝑛 + 2) and 𝑥(𝑛 − 2).
↑
Solution: 𝑍[𝑥(𝑛)] = 𝑋 (𝑧) = ∑∞
𝑛=−∞ 𝑥(𝑛)𝑧
−𝑛
= ∑5𝑛=0 𝑥(𝑛)𝑧 −𝑛
𝑋 (𝑧) = 𝑥(0)𝑧 0 + 𝑥(1)𝑧 −1 + 𝑥(2)𝑧 −2 + 𝑥(3)𝑧 −3 + 𝑥(4)𝑧 −4 + 𝑥(5)𝑧 −5
𝑋(𝑧) = 1 + 2𝑧 −1 + 5𝑧 −2 + 7𝑧 −3 + 𝑧 −5
𝑍[𝑥(𝑛 + 𝑘)] = 𝑧 2 𝑋 (𝑧) = 𝑧 2 (1 + 2𝑧 −1 + 5𝑧 −2 + 7𝑧 −3 + 𝑧 −5 )
= 𝑧 2 + 2𝑧 1 + 5 + 7𝑧 −1 + 𝑧 −3
𝑍[𝑥(𝑛 − 𝑘)] = 𝑧 −2 𝑋 (𝑧) = 𝑧 −2 (1 + 2𝑧 −1 + 5𝑧 −2 + 7𝑧 −3 + 𝑧 −5 )
= 𝑧 −2 + 2𝑧 −3 + 5𝑧 −4 + 7𝑧 −5 + 𝑧 −7
Scaling in the z-domain
𝑧
Statement: If 𝑥(𝑛) ↔ 𝑋(𝑧) with ROC: 𝑟1 < |𝑧| < 𝑟2
𝑧
Then 𝑎𝑛 𝑥(𝑛) ↔ 𝑋(𝑎−1 𝑧) with ROC |𝑎|𝑟1 < |𝑧| < 𝑟2 |𝑎|
Problem: Determine the z-transform of the signals
a) 𝑥(𝑛) = 𝑎𝑛 (𝑐𝑜𝑠𝜔0 𝑛)𝑢(𝑛)
b) 𝑥(𝑛) = 𝑎𝑛 (𝑠𝑖𝑛𝜔0 𝑛)𝑢(𝑛)
Solution: (𝑎)𝑥(𝑛) = 𝑎𝑛 (𝑐𝑜𝑠𝜔0 𝑛)𝑢(𝑛)

14
 Prepared by Dr.Harish M S, AIT

1 − 𝑧 −1 𝑐𝑜𝑠𝜔0
𝑍[(𝑐𝑜𝑠𝜔0 𝑛)𝑢(𝑛) ] = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1 + 𝑧 −2 − 2𝑧 −1 𝑐𝑜𝑠𝜔0
1 − (𝑎−1 𝑧)−1 𝑐𝑜𝑠𝜔0
𝑍[𝑎𝑛 (𝑐𝑜𝑠𝜔0 𝑛)𝑢(𝑛) ] = 𝑋(𝑧) = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 𝑎
1 + (𝑎−1 𝑧)−2 − 2(𝑎−1 𝑧)−1 𝑐𝑜𝑠𝜔0
1 − 𝑎𝑧 −1 𝑐𝑜𝑠𝜔0
𝑋 (𝑧 ) = , , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 𝑎
1 + 𝑎2 𝑧 −2 − 2𝑎𝑧 −1 𝑐𝑜𝑠𝜔0
(𝑏)𝑥(𝑛) = 𝑎𝑛 (𝑠𝑖𝑛𝜔0 𝑛)𝑢(𝑛)
𝑧 −1 𝑐𝑠𝑖𝑛𝜔0
𝑍[(𝑠𝑖𝑛𝜔0 𝑛)𝑢(𝑛) ] = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 1
1 + 𝑧 −2 − 2𝑧 −1 𝑐𝑜𝑠𝜔0
(𝑎−1 𝑧)−1 𝑠𝑖𝑛𝜔0
𝑍 [𝑎𝑛 (𝑠𝑖𝑛𝜔0 𝑛)𝑢(𝑛) ] = 𝑋(𝑧) = , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 𝑎
1 + (𝑎−1 𝑧)−2 − 2(𝑎−1 𝑧)−1 𝑐𝑜𝑠𝜔0
𝑎𝑧 −1 𝑠𝑖𝑛𝜔0
𝑋 (𝑧 ) = , , 𝑤𝑖𝑡ℎ 𝑅𝑂𝐶 |𝑧| > 𝑎
1 + 𝑎2 𝑧 −2 − 2𝑎𝑧 −1 𝑐𝑜𝑠𝜔0
1
Problem: Find the Z-transform of the signal 𝑥(𝑛) = (2)𝑛 [𝑢(𝑛) − 𝑢(𝑛 − 10)]
1
Solution: 𝑥(𝑛) = (2)𝑛 [𝑢(𝑛) − 𝑢(𝑛 − 10)]
9
1 − 𝑧 −10
𝑍[𝑢(𝑛) − 𝑢(𝑛 − 10)] = ∑ 𝑥(𝑛)𝑧 −𝑛 =
1 − 𝑧 −1
𝑛=0

1
𝑍[𝑥(𝑥 )] = 𝑋 (𝑧) = 𝑍 {( )𝑛 [𝑢(𝑛) − 𝑢(𝑛 − 10)]}
2
9 9 −10 1 −1
1 𝑛 −𝑛 1 −1 𝑛 1 − [ (2) 𝑧]
= ∑( ) 𝑧 = ∑( 𝑧 ) =
2 2 1 −1
𝑛=0 𝑛=0 1 − [(2) 𝑧]−1
1 −1 −10 1 10 −10
1−[ ( ) 𝑧] 1−( ) 𝑧
2 2
𝑋 (𝑧 ) = 1 −1 −1
= 1 −1 , ROC is on the entire z-plane except 𝑧 = 0
1−[( ) 𝑧] 1− 𝑧
2 2

1 𝑁
1 1−( ) 𝑧 −𝑁
If 𝑥(𝑛) = (2)𝑛 [𝑢(𝑛) − 𝑢(𝑛 − 𝑁 )], then its z-transform is 𝑋 (𝑧) = 2
1
1− 𝑧 −1
2

1
Problem: Determine the Z-transform of the signal 𝑥(𝑛) = (2)𝑛 𝑢(𝑛 − 2)
1
Solution: Let 𝑥(𝑛) = (2)𝑛 𝑢(𝑛 − 2), this signal is scaled and time shifted signal.

1 1 1 𝑛−2
𝑥(𝑛) = (2)𝑛 𝑢(𝑛 − 2) = 4 (2) 𝑢(𝑛 − 2)
1 𝑧 1 1
𝑍[ (2)𝑛 𝑢(𝑛)] ↔ 1 , with ROC |𝑧| > 2
1− 𝑧 −1
2

15
 Prepared by Dr.Harish M S, AIT

1 𝑛−2 𝑧 𝑧 −2 1
𝑍[ (2) 𝑢(𝑛 − 2)] ↔ 1 , with ROC |𝑧| > 2
1− 𝑧 −1
2

1 1 𝑛−2 𝑧 1 𝑧 −2 1
𝑍[ 4 (2) 𝑢(𝑛 − 2)] ↔ 4 [ 1 ], with ROC |𝑧| > 2
1− 𝑧 −1
2

1 𝑧 −2 1 1
Now 𝑋 (𝑧) =4 [ 1 ]= 4𝑧 2−2𝑧 , with ROC |𝑧| > 2
1− 𝑧 −1
2

Time reversal
𝑧
Statement: If 𝑥(𝑛) ↔ 𝑋(𝑧) with ROC: 𝑟1 < |𝑧| < 𝑟2
𝑧 1 1
Then 𝑥(−𝑛) ↔ 𝑋( 𝑧 −1 ) with ROC: 𝑟 < |𝑧| <
2 𝑟1

Problem: Determine the Z-transform of the signal 𝑥(𝑛) = 𝑢(−𝑛)

Solution: 𝑥(𝑛) = 𝑢(−𝑛)
∞

𝑍 [𝑥(𝑥 )] = 𝑋 (𝑧) = ∑ 𝑥(𝑛)𝑧 −𝑛

𝑛=−∞
𝑧 1
𝑢(𝑛) ↔ 1−𝑧 −1, with ROC: |𝑧| > 1
𝑧 1
𝑢(−𝑛) ↔ 1−𝑧 , with ROC: |𝑧| < 1

Problem: If 𝑥(𝑛) = 2𝑛 𝑢(𝑛), determine the z-transform of 𝑥(−𝑛)

Solution: Let𝑥(𝑛) = 2𝑛 𝑢(𝑛)
𝑧 1
𝑢 (𝑛 ) ↔ , with ROC: |𝑧| > 1
1−𝑧 −1
𝑧 1 𝑧
2𝑛 𝑢(𝑛) ↔ 1−2𝑧 −1 = 𝑧−2, with ROC: |𝑧| > 2
1 𝑧 𝑧 −1 1 1
2−𝑛 𝑢(−𝑛) = (2)𝑛 𝑢(−𝑛) ↔ 𝑧 −1 −2= 1−2𝑧 , with ROC: |𝑧| < 2

Differentiation in the z-domain

𝑧
Statement: If 𝑥(𝑛) ↔ 𝑋(𝑧)
𝑧 𝑑𝑋(𝑧 )
Then 𝑛𝑥(𝑛) ↔ − 𝑧 𝑑𝑧

Problem: Determine the z-transform of the signal 𝑥(𝑛) = 𝑛𝑎𝑛 𝑢(𝑛)

Solution: Let 𝑥(𝑛) = 𝑛𝑎𝑛 𝑢(𝑛)
𝑧 1
𝑢(𝑛) ↔ 1−𝑧 −1, with ROC: |𝑧| > 1
𝑧 1 𝑧
𝑎 𝑛 𝑢 (𝑛 ) ↔ = , with ROC: |𝑧| > 𝑎
1−𝑎𝑧 −1 𝑧−𝑎

16
 Prepared by Dr.Harish M S, AIT

𝑧 𝑑𝑋(𝑧 ) 𝑑 𝑧 −𝑎 𝑧𝑎 𝑎𝑧 −1
𝑛𝑎𝑛 𝑢(𝑛) ↔ 𝑋(𝑧) = −𝑧 = −𝑧 𝑑𝑧 {𝑧−𝑎} = −𝑧 {(𝑧−𝑎)2} = (𝑧−𝑎)2 = (1−𝑎𝑧 −1)2
𝑑𝑧
𝑧 𝑎𝑧 −1
𝑛𝑎𝑛 𝑢(𝑛) ↔ , With ROC|𝑧| > 𝑎
(1−𝑎𝑧 −1)2

Problem: Determine the Z-transform of the signal 𝑥(𝑛) = 𝑛2 𝑢(𝑛)

Solution: Let 𝑥(𝑛) = 𝑛2 𝑢(𝑛) = 𝑛[𝑛𝑢(𝑛)]
𝑧 1 𝑧
𝑢(𝑛) ↔ 1−𝑧 −1 = 𝑧−1, with ROC: |𝑧| > 1
𝑧 𝑑 𝑧 𝑧
𝑛𝑢(𝑛) ↔ − 𝑧 𝑑𝑧 {𝑧−1} = (𝑧−1)2 , with ROC: |𝑧| > 1

𝑧 𝑑 𝑧 (𝑧 − 1)2 − 2𝑧(𝑧 − 1) (𝑧 − 1) − 2𝑧
𝑍 {𝑛[𝑛𝑢(𝑛)]} ↔ −𝑧 { [ ]} = −𝑧 [ ] = −𝑧[ ]
𝑑𝑧 (𝑧 − 1)2 (𝑧 − 1)4 (𝑧 − 1)3
𝑧(𝑧+1)
𝑋 (𝑧 ) = , With ROC: |𝑧| > 1
(𝑧−1)3

Problem: Determine the Z-transform of the signal 𝑥(𝑛) = 𝑛(𝑛 − 1)𝑢(𝑛)

Solution: Let 𝑥(𝑛) = 𝑛(𝑛 − 1)𝑢(𝑛) = 𝑛2 𝑢(𝑛) − 𝑛𝑢(𝑛)
𝑧(𝑧 + 1) 𝑧
𝑛 2 𝑢 (𝑛 ) ↔
(𝑧 − 1)3
𝑧 𝑧
𝑛𝑢(𝑛) ↔
(𝑧 − 1)2
𝑧(𝑧+1) 𝑧 2𝑧
∴ 𝑍{𝑛2 𝑢(𝑛) − 𝑛𝑢(𝑛)} = 𝑋(𝑧) = (𝑧−1)3 − (𝑧−1)2 = (𝑧−1)3, With ROC: |𝑧| > 1

Convolution of two sequences

𝑧 𝑧
Statement: If 𝑥1 (𝑛) ↔ 𝑋1 (𝑧) and 𝑥2 (𝑛) ↔ 𝑋2 (𝑧)
𝑧
Then 𝑥(𝑛) = 𝑥1 (𝑛) ∗ 𝑥2 (𝑛) ↔ 𝑋(𝑧) = 𝑋1 (𝑧)𝑋2 (𝑧)
1, −2, 1
Problem: Compute the convolution of 𝑥(𝑛) of the signal 𝑥1 (𝑛) = ( ) and 𝑥2 (𝑛) =
↑
{ 1, ≤ 𝑛 ≤ 5
0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒
Solution: Let 𝑥(𝑛) = 𝑥1 (𝑛) ∗ 𝑥2 (𝑛) = ∑∞
𝑘=−∞ 𝑥1 (𝑘 )𝑥2 (𝑛 − 𝑘 ) , −∞ ≤𝑛 ≤∞
𝑍[𝑥(𝑛)] = 𝑍[𝑥1 (𝑛) ∗ 𝑥2 (𝑛)] = 𝑋(𝑧) = 𝑋1 (𝑧)𝑋2 (𝑧)
𝑋1 (𝑧) = 𝑍[𝑥1 (𝑛)] = 1 − 2𝑧 −1 + 𝑧 −2 , and 𝑋2 (𝑧) = 1 + 𝑧 −1 + 𝑧 −2 + 𝑧 −3 + 𝑧 −4 + 𝑧 −5
𝑋(𝑧) = 𝑋1 (𝑧)𝑋2 (𝑧) = (1 − 2𝑧 −1 + 𝑧 −2 )(1 + 𝑧 −1 + 𝑧 −2 + 𝑧 −3 + 𝑧 −4 + 𝑧 −5 )
𝑋(𝑧) = 1 − 𝑧 −1 − 𝑧 −6 + 𝑧 −7 … … . (𝐴)
From the definition of Z-transform 𝑋(𝑧) = ∑∞
𝑛=−∞ 𝑥 (𝑛 )𝑧
−𝑛
= ∑7𝑛=0 𝑥(𝑛)𝑧 −𝑛

17
 Prepared by Dr.Harish M S, AIT

𝑋(𝑧) = 𝑥(0)𝑧 0 + 𝑥(1)𝑧 −1 + 𝑥(2)𝑧 −2 + 𝑥(3)𝑧 −3 + 𝑥 (4)𝑧 −4 +𝑥(5)𝑧 −5 + 𝑥(6)𝑧 −6

+ 𝑥(7)𝑧 −7 … … … … (𝐵)
1, −1, 0, 0, 0, 0, −1, 1
On comparing equation A and B we get 𝑥(𝑛) = ( )
↑
1 𝑛
Problem: Compute the convolution of the signal 𝑥1 (𝑛) = (4) 𝑢(𝑛 − 1) and 𝑥2 (𝑛) =
1
[1 + ( )𝑛 ] 𝑢(𝑛)
2

Solution: Let 𝑥(𝑛) = 𝑥1 (𝑛) ∗ 𝑥2 (𝑛) = ∑∞

𝑘=−∞ 𝑥1 (𝑘 )𝑥2 (𝑛 − 𝑘 ) , −∞ ≤𝑛 ≤∞
𝑍[𝑥(𝑛)] = 𝑍[𝑥1 (𝑛) ∗ 𝑥2 (𝑛)] = 𝑋(𝑧) = 𝑋1 (𝑧)𝑋2 (𝑧)
1 𝑛 1 1
𝑥1 (𝑛) = ( ) 𝑢(𝑛 − 1) = ( )𝑛−1 𝑢(𝑛 − 1)
4 4 4
1 1
𝑍[𝑥1 (𝑛)] = 𝑋1 (𝑧) = 𝑍[( )𝑛 𝑢(𝑛)] = 1
4 1 − 𝑧 −1 4

1 𝑛−1 𝑧 −1
𝑍[( ) 𝑢(𝑛 − 1)] = 1
4 1 − 𝑧 −1 4

1 1 𝑛−1 1 𝑧 −1 1
𝑋1 (𝑧) = 𝑍 [ ( ) 𝑢(𝑛 − 1)] = [ 1 ]=
4 4 4 1 − 𝑧 −1 4𝑧 − 1
4

1 𝑛 1 𝑛
Now 𝑥2 (𝑛) = [1 + (2) ] 𝑢(𝑛) = 𝑢(𝑛) + (2) 𝑢(𝑛)

1 𝑛 𝑧 2𝑧
𝑍[𝑥2 (𝑛)] = 𝑋2 (𝑧) = 𝑍 [𝑢(𝑛) + ( ) 𝑢(𝑛)] = +
2 𝑧 − 1 2𝑧 − 1
1 𝑧 2𝑧 𝑧(4𝑧 − 3)
𝑋(𝑧) = 𝑋1 (𝑧)𝑋2 (𝑧) = ( )( + )=
4𝑧 − 1 𝑧 − 1 2𝑧 − 1 (4𝑧 − 1)(𝑧 − 1)(2𝑧 − 1)
𝑋 (𝑧 ) (4𝑧 − 3)
=
𝑧 (4𝑧 − 1)(𝑧 − 1)(2𝑧 − 1)
𝑋 (𝑧 ) 𝐴 𝐵 𝐶
= + +
𝑧 4𝑧 − 1 𝑧 − 1 2𝑧 − 1
16 1
𝐴 = − 3 , 𝐵 = 3 and 𝐶 = 2
−16 1 −4 1
𝑧 −2𝑧 𝑧 1
3 3 3 3
∴ 𝑋 (𝑧 ) = + + = 1 + −1
+ 1 −1
4𝑧 − 1 𝑧 − 1 2𝑧 − 1 1 − 𝑧 −1 1 − 𝑧 1 − 𝑧
4 2

−4 1 𝑛 1 1 𝑛
Now 𝑥(𝑛) = ( ) 𝑢(𝑛 ) + 3 𝑢 (𝑛 ) + (2) 𝑢(𝑛)
3 4

18
 Prepared by Dr.Harish M S, AIT

1
Problem: Compute the convolution of the signal 𝑥1 (𝑛) = 𝑢(𝑛) and 𝑥2 (𝑛) = 𝛿(𝑛) + (2)𝑛 𝑢(𝑛)

Solution: Let 𝑥(𝑛) = 𝑥1 (𝑛) ∗ 𝑥2 (𝑛) = ∑∞

𝑘=−∞ 𝑥1 (𝑘 )𝑥2 (𝑛 − 𝑘 ) , −∞ ≤𝑛 ≤∞
𝑍[𝑥(𝑛)] = 𝑍[𝑥1 (𝑛) ∗ 𝑥2 (𝑛)] = 𝑋(𝑧) = 𝑋1 (𝑧)𝑋2 (𝑧)
𝑥1 (𝑛) = 𝑢(𝑛)
1
𝑍[𝑥1 (𝑛)] = 𝑋1 (𝑧) = 𝑍[𝑢(𝑛)] =
1 − 𝑧 −1
1
𝑥2 (𝑛) = 𝛿(𝑛) + ( )𝑛 𝑢(𝑛)
2
1
1 𝑛 1 1 2 − 2 𝑧 −1
[ ( )] ( )
𝑍 𝑥2 𝑛 = 𝑋2 𝑧 = 𝑍 [𝛿(𝑛) ( )]
+( ) 𝑢 𝑛 = 1+ 1 =1+ 1 = 1
2 1 − 2 𝑧 −1 1 − 2 𝑧 −1 1 − 2 𝑧 −1
1
1 2 − 2 𝑧 −1 𝐴 𝐵
𝑋 (𝑧) = 𝑋1 (𝑧)𝑋2 (𝑧) = ( −1
)( 1 )= −1
+ 1
1−𝑧 1 − 𝑧 −1 1−𝑧 1 − 𝑧 −1
2 2

𝐴 = 3, 𝐵 = −1
𝐴 𝐵 3 1
𝑋 (𝑧 ) = −1
+ 1 = −1
− 1
1−𝑧 1 − 𝑧 −1 1 − 𝑧 1 − 𝑧 −1
2 2
𝑛
1
𝑥(𝑛) = 3𝑢(𝑛) − ( ) 𝑢(𝑛)
2
Correlation of two sequences
𝑧 𝑧
Statement: If 𝑥1 (𝑛) ↔ 𝑋1 (𝑧) and 𝑥2 (𝑛) ↔ 𝑋2 (𝑧)
𝑧
Then 𝑟𝑥1𝑥2 (𝑙 ) = 𝑥1 (𝑙 ) ∗ 𝑥2 (−𝑙 ) = ∑∞ −1
𝑛=−∞ 𝑥1 (𝑛 ) 𝑥2 (𝑛 − 𝑙 ) ↔ 𝑅𝑥1 𝑥2 (𝑧) = 𝑋1 (𝑧)𝑋2 (𝑧 )

Problem: Determine the autocorrelation sequence of the signal 𝑥 (𝑛) = 𝑎𝑛 𝑢(𝑛), −1 < 𝑎 < 1
Solution: Autocorrelation of a signal is the correlation with itself, thus
𝑅𝑥𝑥 (𝑧) = 𝑋(𝑧)𝑋(𝑧 −1 )
1 1 1
𝑋(𝑧) = 1−𝑎𝑧 −1 , with ROC: |𝑧| > |𝑎| and 𝑋(𝑧 −1 ) = 1−𝑎𝑧, with ROC: |𝑧| < |𝑎|
1 1 1 1
𝑅𝑥𝑥 (𝑧) = 𝑋(𝑧)𝑋(𝑧 −1 ) = (1−𝑎𝑧 −1 ) (1−𝑎𝑧) = 1−𝑎(𝑧+𝑧 −1)+𝑎2 , with ROC: |𝑎| < |𝑧| < |𝑎|

1
𝑟𝑥𝑥 (𝑙 ) = 𝑎|𝑙| , − ∞ ≤ 𝑙 ≤ ∞
1 − 𝑎2
Multiplication of two sequences
𝑧 𝑧
Statement: If 𝑥1 (𝑛) ↔ 𝑋1 (𝑧) and 𝑥2 (𝑛) ↔ 𝑋2 (𝑧)

19
 Prepared by Dr.Harish M S, AIT

𝑧 1 𝑧
Then 𝑥(𝑛) = 𝑥1 (𝑛)𝑥2 (𝑛) ↔ 𝑋(𝑧) = 2𝜋𝑗 ∮𝑐 𝑋1 (𝑣) 𝑋2 (𝑣)𝑣 −1 𝑑𝑣

Where C is a closed contour integration

Parseval’s relation
Statement: If 𝑥1 (𝑛) and 𝑥2 (𝑛) are the complex valued sequence
∗
Then ∑∞
𝑛=−∞ 𝑥1 (𝑛 )𝑥2 (𝑛) =
𝑧 1 1
𝑥1 (𝑛)𝑥2 (𝑛) ↔ 𝑋(𝑧) = ∮ 𝑋1 (𝑣) 𝑋2∗ ( )𝑣 −1 𝑑𝑣
2𝜋𝑗 𝑐 𝑣

Where C is a closed contour integration

The initial value theorem
Statement: If 𝑥(𝑛) is a causal signal, then 𝑥(0) = lim 𝑋(𝑧)
𝑧→∞

The System Function of a Linear Time Invariant system

Consider linear time invariant (LTI) system represented by impulse response ℎ(𝑛). The output
𝑦(𝑛)for any arbitrary input 𝑥(𝑛) can be obtained by computing the convolution of 𝑥(𝑛) with
unit impulse response ℎ(𝑛)as shown in below figure. The impulse response ℎ(𝑛) represents the
LTI system in time domain.

Out put
𝑦(𝑛) = 𝑥(𝑛) ∗ ℎ(𝑛)
Apply the Z-transform for the equation
𝑌 (𝑧) = 𝑋 (𝑧)𝐻(𝑧)
𝑌(𝑧)
𝐻 (𝑧 ) =
𝑋(𝑧)
It is clear that 𝐻(𝑧) represents the LTI system in z-domain, it characterizes the LTI system, it is
also known as transfer function or system function of the LTI system. The transfer function of
the discrete LTI system is defined as the ratio of the Z-transform of the output to the Z-transform
input. The same system can be represented linear constant by linear constant-coefficient
difference equation of the form

20
 Prepared by Dr.Harish M S, AIT

𝑁 𝑀

𝑦(𝑛) = − ∑ 𝑎𝑘 𝑦(𝑛 − 𝑘) + ∑ 𝑏𝑘 𝑥(𝑛 − 𝑘)

𝑘=1 𝑘=0

Apply the Z-transform to the above equation, we get

𝑁 𝑀

𝑌(𝑧) = − ∑ 𝑎𝑘 𝑌(𝑧)𝑧 −𝑘 + ∑ 𝑏𝑘 𝑋(𝑧)𝑧 −𝑘

𝑘=1 𝑘=0

𝑌(𝑧) ∑𝑀
𝑘=0 𝑏𝑘 𝑧
−𝑘
= 𝐻 (𝑧 ) =
𝑋(𝑧) 1 + ∑𝑁
𝑘=1 𝑎𝑘 𝑧
−𝑘

This is the general form of system function of system described by difference equation. If
coefficient 𝑎𝑘 = 0, now the system function reduces to
𝑀

𝐻 (𝑧) = ∑ 𝑏𝑘 𝑧 −𝑘
𝑘=0

This system is known as all-zero system, poles are at the origin. Due to the presence of zeros,
system has finite impulse response (FIR), and it is called FIR system or Moving average (MA)
system.
On the other hand, if 𝑏𝑘 = 0 for 1 ≤ 𝑘 ≤ 𝑀, now the system function reduces to
𝑏0
𝐻 (𝑧 ) = 𝑁
1+ ∑𝑘=1 𝑎𝑘 𝑧 −𝑘
This system if known as all-pole system, zeros are at the origin. Due to the presence of poles, the
system has an infinite impulse response and it is an IIR system.
If we consider the system function
∑𝑀
𝑘=0 𝑏𝑘 𝑧
−𝑘
𝐻 (𝑧 ) =
1 + ∑𝑁
𝑘=1 𝑎𝑘 𝑧
−𝑘

This system has poles as well as zeros, thus system is known as pole-zero system, Due to
presence of poles, system has infinite-impulse response and it is an IIR system.
Problem: Determine the system function and the unit sample response of the system described
1
by the difference equation 𝑦(𝑛) = 2 𝑦(𝑛 − 1) + 2𝑥(𝑛)
1
Solution: 𝑦(𝑛) = 2 𝑦(𝑛 − 1) + 2𝑥(𝑛)

Apply the Z-transform to the above difference equation, we get

1
𝑌 (𝑧) = 𝑌(𝑧)𝑧 −1 + 2𝑋(𝑧)
2

21
 Prepared by Dr.Harish M S, AIT

𝑌(𝑧) 1
=
𝑋(𝑧) 1 − 1 𝑧 −1
2
𝑌(𝑧) 1
Therefore, system function 𝑋(𝑧) = 𝐻 (𝑧) = 1
1− 𝑧 −1
2

𝑧 1
𝐻 (𝑧 ) = 1 , thus the poles are at 𝑧 = 2 and zeros are at 𝑧 = 0
𝑧−
2

1 𝑛
And impulse response or unit sample response is ℎ(𝑛) = (2) 𝑢(𝑛)

Introduction to Fourier representation

To obtain the frequency analysis of white light, we will use prism. Similarly, to obtain the
frequency analysis of the signal we have to use Fourier analysis. The Fourier analysis is a
mathematical tool to obtain the frequency analysis of the signal. The signal may be continuous
time or discrete time or periodic or nonperiodic signal. If the signal is continuous and periodic
then its frequency analysis is Fourier Series (FS). If the signal is continuous and nonperiodic
then its frequency analysis is Fourier transform (FT). If the signal is discrete and periodic then its
frequency analysis is Discrete Time Fourier Series (DTFS). If the signal is discrete and
nonperiodic then its frequency analysis is Discrete Time Fourier Transform (DTFT).
Mathematical expressions for Fourier Analysis
𝟐𝝅
i. If the signal x (t) is continuous-periodic with period 𝜴 = 𝟐𝝅𝑭 = radians/ Sec , then
𝑻

its FS is
1 𝑇
𝑐𝑘 = ∫ 𝑥(𝑡)𝑒 −𝑗𝑘𝛺𝑡 𝑑𝑡 → Analysis equation (Time domain to frequancy domain )
𝑇 0
∞

𝑥 (𝑡) = ∑ 𝑐𝑘 𝑒 𝑗𝑘𝛺𝑡 → Synthesiss equation (Frequency domain to time domain)

{ 𝑘=−∞

ii. If the signal x(t) is continuous-nonperiodic then its FT is

∞
𝑋( 𝛺) = ∫ 𝑥(𝑡)𝑒 −𝑗𝛺𝑡 𝑑𝑡 → Analysis equation (Time domain to frequancy domain )
−∞
1 ∞
( )
𝑥 𝑡 = ∫ 𝑋(𝛺)𝑒 𝑗𝛺𝑡 𝑑𝛺 → Synthesiss equation (Frequency domain to time domain)
{ 2𝜋 −∞
𝟐𝝅
iii. If the signal x (n) is discrete-periodic with period 𝑵 = samples in one period,
𝝎

then its DTFS is

22
 Prepared by Dr.Harish M S, AIT

𝑁−1
1
𝑐𝑘 = ∑ 𝑥(𝑛)𝑒 −𝑗𝑘𝜔𝑛 → Analysis equation (Time domain to frequancy domain )
𝑁
𝑛=0
𝑁−1

𝑥(𝑛) = ∑ 𝑐𝑘 𝑒 𝑗𝑘𝜔𝑛 → Synthesiss equation (Frequency domain to time domain)

{ 𝑘=0

iv. If the signal x (n) is discrete-nonperiodic with period then its DTFT is
∞

𝑋 ( ⍵) = ∑ 𝑥(𝑛)𝑒 −𝑗𝜔𝑛 → Analysis equation (Time domain to frequancy domain )

𝑛=−∞
1 𝜋
𝑥 (𝑛 ) = ∫ 𝑋(𝜔)𝑒 𝑗𝜔𝑛 𝑑𝜔 → Synthesiss equation (Frequency domain to time domain)
{ 2𝜋 −𝜋

Frequency-Domain Sampling: Discrete Fourier Transform (DFT)

To perform the frequency analysis of a discrete time signal 𝑥(𝑛) we have to transform the time
domain to frequency domain. Suppose 𝑥(𝑛) is nonperiodic, its frequency domain representation
is Discrete-Time Fourier Transform (DTFT) represented as 𝑋 (⍵). The quantity 𝑋(⍵) is
complex, continuous function of ⍵ and periodic with period 2𝜋.
Usually the frequency analysis of the signal is performed on general purpose digital computer or
specially designed digital hardware. The quantity 𝑋 (⍵) is continuous function of ⍵, to perform
the frequency analysis of 𝑥(𝑛) on the digital hardware or digital computer, 𝑋 (⍵) has to be
discritized. The samples of 𝑋 (⍵) are called Discrete Fourier Transform (DFT) and sampling of
𝑋(⍵) is known as frequency domain sampling.
Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals
Let us consider a discrete time finite energy nonperiodic signal 𝑥(𝑛), the DTFT of 𝑥(𝑛) is
𝑋( ⍵) = ∑∞
𝑛=−∞ 𝑥(𝑛)𝑒
−𝑗𝜔𝑛
……… (1)
We know that 𝑋 ( ⍵) is a complex continuous spectra and it is a function of ⍵, is periodic with
period 2𝜋 radians as shown in Figure 2.17.

23
 Prepared by Dr.Harish M S, AIT

Suppose if we sample 𝑋 ( ⍵) periodically at a spacing of 𝛿𝜔 radians between the successive

samples. Since 𝑋( ⍵) is periodic with period 2𝜋, we take N equidistance samples in the interval
0 ≤ 𝜔 ≤ 2𝜋 with spacing 𝛿𝜔 = 2𝜋/𝑁 as shown in Figure 2.17. If we evaluate the equation (1)
at 𝜔 = 2𝜋𝑘/𝑁, we obtain
𝑗2𝜋𝑘𝑛
−
𝑋(2𝜋𝑘/𝑁) = ∑∞
𝑛=−∞ 𝑥 (𝑛 )𝑒 𝑁 , 0 ≤ 𝑘 ≤ 𝑁 − 1 …….. (2)
The equation (2) can be subdivided into an infinite number of summations, each summation
contains N terms. Thus
−1 𝑁−1 2𝑁−1
−𝑗2𝜋𝑘𝑛 −𝑗2𝜋𝑘𝑛 −𝑗2𝜋𝑘𝑛
− −
𝑋(2𝜋𝑘/𝑁) = ⋯ . . + ∑ 𝑥(𝑛)𝑒 𝑁 + ∑ 𝑥 (𝑛 )𝑒 𝑁 + ∑ 𝑥 (𝑛 )𝑒 − 𝑁 +⋯
𝑛=−𝑁 𝑛=0 𝑛=𝑁
∞
𝑙𝑁+𝑁−1
𝑋 (2𝜋𝑘/𝑁) = ∑ (∑ 𝑥(𝑛)) 𝑒 −𝑗2𝜋𝑘𝑛/𝑁
𝑛=𝑙𝑁
𝑙=−∞

If we change the index in the inner summation from n to 𝑛 − 𝑙𝑁 and interchange the order of the
summation, we get
𝑁−1
∞
𝑋(2𝜋𝑘/𝑁) = ∑ (∑ 𝑥(𝑛 − 𝑙𝑁) 𝑒 −𝑗2𝜋𝑘(𝑛−𝑙𝑁)/𝑁
𝑙=−∞
𝑛=0
−𝑗2𝜋𝑘(𝑛−𝑙𝑁)/𝑁
𝑒 = 𝑒 −𝑗2𝜋𝑘𝑛/𝑁 𝑒 𝑗2𝜋𝑘𝑛𝑙 = 𝑒 −𝑗2𝜋𝑘𝑛/𝑁
𝑁−1
∞
𝑋(2𝜋𝑘/𝑁) = ∑ [∑ 𝑥(𝑛 − 𝑙𝑁)] 𝑒 −𝑗2𝜋𝑘𝑛/𝑁 , 0≤𝑘 ≤𝑁−1
𝑙=−∞
𝑛=0

𝑋(2𝜋𝑘/𝑁) = ∑𝑁−1
𝑛=0 𝑥𝑝 (𝑛) 𝑒
−𝑗2𝜋𝑘𝑛/𝑁
, 0 ≤ 𝑘 ≤ 𝑁 − 1 …….. (3)
The signal
𝑥𝑝 (𝑛) = ∑∞
𝑙=−∞ 𝑥(𝑛 − 𝑙𝑁 ) …………… (4)

24
 Prepared by Dr.Harish M S, AIT

This signal𝑥𝑝 (𝑛) is the periodic repetition of 𝑥(𝑛) consists of N samples in one period. We
know, Fourier coefficient of periodic signal is
𝑗2𝜋𝑘𝑛
1 −
𝑐𝑘 = ∑𝑁−1
𝑛=0 𝑥𝑝 (𝑛 )𝑒 𝑁 , 0 ≤ 𝑘 ≤ 𝑁 − 1 …….. (5)
𝑁

And
𝑥𝑝 (𝑛) = ∑𝑁−1
𝑘=0 𝑐𝑘 𝑒
𝑗2𝜋𝑘𝑛/𝑁
, 0 ≤ 𝑛 ≤ 𝑁 − 1 …………… (6)
Upon comparing equation (3) and (5), we conclude that
1 2𝜋
𝑐𝑘 = 𝑋 ( 𝑁 𝑘) , 0 ≤ 𝑘 ≤ 𝑁 − 1 …….. (7)
𝑁
𝑗𝑘2𝜋𝑛
1 2𝜋
∴ 𝑥𝑝 (𝑛) = 𝑁 ∑𝑁−1
𝑘=0 𝑋 ( 𝑁 𝑘) 𝑒
𝑁 , 0 ≤ 𝑛 ≤ 𝑁 − 1 …….. (8)

The relationship in equation (8) provides the reconstruction of the periodic signal 𝑥𝑝 (𝑛) from the
samples of the spectrum 𝑋(⍵). Once if we have the periodic signal𝑥𝑝 (𝑛), we can recovered
back the original nonperiodic signal 𝑥(𝑛) if there is no aliasing effect (Over or right sampling) i.
e. 𝑁 ≥ 𝐿 . Where L is number of samples in 𝑥(𝑛) and N is the number of samples in one period
of𝑋( ⍵).
𝑥 (𝑛 ) = 𝑥 𝑝 (𝑛 ) , 0≤𝑛 ≤𝑁−1
On the other hand, if 𝑁 < 𝐿, there is aliasing effect (under sampling) it is not possible to recover
the original nonperiodic signal. Thus, we conclude that the spectrum of the nonperiodic signal
𝑥(𝑛) with finite duration L can exactly recovered from its samples at frequency𝜔𝑘 = 2𝜋𝑘/𝑁,
if 𝑁 ≥ 𝐿 . The procedure to compute 𝑥𝑝 (𝑛) from equation (8); then
𝑥 (𝑛 ) 0 ≤ 𝑛 ≤ 𝑁 − 1
∴ 𝑥 (𝑛 ) = { 𝑝 ………..………….. (9)
0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒
And finally, 𝑋 ( ⍵) can be computed from equation (1).
The Discrete Fourier Transform (DFT)
The development in the previous section is concerned with the frequency-domain sampling of a
nonperiodic finite-energy sequence 𝑥(𝑛) . The equally spaced frequency
2𝜋𝑘
samples𝑋 ( ), 0 ≤ 𝑘 ≤ 𝑁 − 1, do not uniquely represents original sequence 𝑥(𝑛) when
𝑁

𝑥(𝑛) has infinite duration.

When the sequence 𝑥(𝑛) has a finite duration of length 𝐿 ≤ 𝑁, then 𝑥𝑝 (𝑛) is simply a periodic
2𝜋𝑘
repetition of 𝑥(𝑛 ). Consequently, the frequency samples 𝑋 ( ) , 0 ≤ 𝑘 ≤ 𝑁 − 1, uniquely
𝑁

25
 Prepared by Dr.Harish M S, AIT

represents the finite-duration sequence 𝑥(𝑛). The original finite-duration sequence 𝑥(𝑛) can be
2𝜋𝑘
obtained from frequency samples 𝑋 ( ) using the formula
𝑁
𝑁−1
1 2𝜋
∑ 𝑋 ( 𝑘) 𝑒 𝑗2𝜋𝑘𝑛/𝑁
𝑥 (𝑛 ) ≡ 𝑥 𝑝 (𝑛 ) = { 𝑁 𝑁 , 0 ≤𝑛 ≤𝐿−1
𝑘=0
0 , 𝐿 ≤ 𝑛 ≤ 𝑁−1
A finite-duration sequence 𝑥(𝑛) of length L has a Fourier transform
𝐿−1

𝑋(𝜔) = ∑ 𝑥(𝑛)𝑒 −𝑗𝜔𝑛 , 0 ≤ 𝜔 ≤ 2𝜋

𝑛=0
2𝜋𝑘
When we sample 𝑋(𝜔) at equally spaced frequencies 𝜔𝑘 = ( ) , 0 ≤ 𝑘 ≤ 𝑁 − 1,
𝑁

where 𝑁 ≥ 𝐿, the resultant samples are

𝐿−1
2𝜋 𝑗2𝜋𝑘𝑛
𝑋 (𝑘) = 𝑋 ( 𝑘) = ∑ 𝑥(𝑛)𝑒 − 𝑁 , 0≤𝑘 ≤ 𝑁−1
𝑁
𝑛=0

For convince, the upper index in the sum has been increased from 𝐿 − 1 to 𝑁 − 1 then
𝑁−1
𝑗2𝜋𝑘𝑛
∴ 𝑋 (𝑘 ) = ∑ 𝑥 (𝑛 ) 𝑒 − 𝑁 , 0≤𝑘 ≤𝑁−1
𝑛=0
−𝑗2𝜋𝑘𝑛
𝑋(𝑘) = ∑𝑁−1
𝑛=0 𝑥 (𝑛 )𝑒 𝑁 , 0 ≤ 𝑘 ≤ 𝑁 − 1 ………… (A)
The relation (A) is a formula for transforming the time domain sequence 𝑥(𝑛) of length L in to
frequency domain sequence 𝑋(𝑘) of length N. The relation (A) is also known as discrete Fourier
transform (DFT) of 𝑥(𝑛). The DFT samples 𝑋(𝑘) allow us to recover the sequence 𝑥(𝑛) using
the relation
1
𝑥(𝑛) = 𝑁 ∑𝑁−1
𝑘=0 𝑋(𝑘)𝑒
𝑗2𝜋𝑘𝑛/𝑁
, 0 ≤ 𝑛 ≤ 𝑁 − 1 ………… (B)

The relation (B) is known as inverse DFT (IDFT)

Problem: A finite duration sequence of length L is given by
1 0 ≤𝑛 ≤𝐿−1
𝑥 (𝑛 ) = { . Determine the N-point DFT of𝑥(𝑛).
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
Solution: The N-point DFT of 𝑥(𝑛) is 𝑋(𝑘)
𝑁−1
−𝑗2𝜋𝑘𝑛
𝑋 (𝑘 ) = ∑ 𝑥 (𝑛 )𝑒 𝑁 , 0 ≤𝑘 ≤ 𝑁−1
𝑛=0

26
 Prepared by Dr.Harish M S, AIT

−𝑗2𝜋𝑘𝑁
−𝑗2𝜋𝑘𝑛
1−𝑒 𝑁 1−𝑒 −𝑗2𝜋𝑘
𝑋 (𝑘 ) = ∑𝑁−1
𝑛=0 𝑒 𝑁 = 2𝜋𝑘 = 2𝜋𝑘 = 0 If 𝑘 ≠ 0
− −
1−𝑒 𝑁 1−𝑒 𝑁

−𝑗2𝜋𝑘𝑛 −𝑗2𝜋(0)𝑛
𝑋(𝑘) = ∑𝑁−1
𝑛=0 𝑥 (𝑛 )𝑒 𝑁 = ∑𝑁−1
𝑛=0 𝑒 𝑁 = ∑𝑁−1
𝑛=0 1 = 𝐿 If 𝑘 = 0
𝐿 𝑘=0
∴ 𝑋 (𝑘 ) = {
0 𝑘≠0
DFT as a linear transformation
Consider the DFT and IDFT formulas
−𝑗2𝜋𝑘𝑛
𝑋(𝑘) = ∑𝑁−1
𝑛=0 𝑥 (𝑛 )𝑒 𝑁 , 0 ≤ 𝑘 ≤ 𝑁 − 1 ………… (A)
1
𝑥(𝑛) = 𝑁 ∑𝑁−1
𝑘=0 𝑋(𝑘)𝑒
𝑗2𝜋𝑘𝑛/𝑁
, 0 ≤ 𝑛 ≤ 𝑁 − 1 ……….… (B)

The above formulas may be expressed as

𝑁−1

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 , 0 ≤ 𝑘 ≤ 𝑁 − 1 … … … … … (𝐶)

𝑛=0
1
𝑥(𝑛) = 𝑁 ∑𝑁−1 −𝑛𝑘
𝑘=0 𝑋(𝑘 ) 𝑊𝑁 , 0 ≤ 𝑛 ≤ 𝑁 − 1 ……….… (D)

Where, by definition,
𝑊𝑁 = 𝑒 −𝑗2𝜋/𝑁
We note that the computation of each point of the DFT can be accomplished by N complex
multiplications and (N-1) complex additions. Hence the N-point DFT needs 𝑁 2 complex
multiplications and 𝑁(𝑁 − 1) complex additions. Let us define an N-point vector 𝐱 𝑁 of the
signal sequence𝑥(𝑛),0 ≤ 𝑛 ≤ 𝑁 − 1, an N-point vector 𝐗 𝑁 of frequency samples, and an 𝑁 ×
𝑁matrix 𝐖𝑁 as
1 1 … 1
𝑥(0) 𝑋(0) 1
𝑊𝑁 𝑊𝑁2 …
… (𝑁−1)
𝑥 (1) ], 𝑋(1) 1 … 𝑊𝑁
𝐱𝑁 = [ 𝐗𝑁 = [ ] and 𝑊𝑁 = ⋮ ⋮
⋮ ⋮ ⋮ … ⋮
(𝑁−1) 𝑁(𝑁−1) (𝑁−1)(𝑁−1)
𝑥(𝑁 − 1) 𝑋(𝑁 − 1) [1 𝑊𝑁 𝑊𝑁 … 𝑊𝑁 ]
With these definitions, the N-point DFT may be expressed in matrix form as
𝐗 𝑁 = 𝐖𝑁 𝒙𝑵………. (E)
Where 𝐖𝑁 is the matrix of linear transformation, we observe that 𝐖𝑁 is a symmetric matrix. If
we assume that the inverse of 𝐖𝑁 exist, then (E) can be inverted by premultiplying both sides
by𝐖𝑁−1 . Thus we obtain
𝐱 𝑁 = 𝐖𝑁−1 𝐗 𝑁 … … (𝐹)

27
 Prepared by Dr.Harish M S, AIT

But this is just an expression for the IDFT. In fact, the IDFT can be expressed as in matrix form
as
1
𝐱 𝑁 = N 𝐖𝑁∗ 𝐗 𝑁 ……… (G)

Where 𝐖𝑁∗ denotes the complex conjugate of the matrix 𝐖𝑁 . On comparing equation (F) and (G)
1
leads us to conclude that𝐖𝑁−1 = N 𝐖𝑁∗ , which, in turn implies that 𝑾𝑁 𝐖𝑁∗ = N𝐈N

where 𝐈N is an 𝑁 × 𝑁 identity matrix. Therefore, the matrix 𝑾𝑁 in the transformation is an

orthogonal matrix.
Problem: Compute the 4-point DFT of the sequence 𝑥(𝑛) = {0 1 2 3}
Solution: The matrix form of N-point DFT of 𝑥(𝑛) i𝑠
𝐗 𝑁 = 𝐖𝑵 𝒙𝑵

0 𝑊40 𝑊40 𝑊40 𝑊40 1 1 1 1

𝑊0 𝑊41 𝑊42 𝑊43 1 −𝑗 −1 𝑗
𝐱 4 = [1], 𝐖4 = 40 =[ ]
2 𝑊4 𝑊42 𝑊44 𝑊46 1 −1 1 −1
3 [𝑊40 𝑊43 𝑊46 𝑊49 ] 1 𝑗 −1 −𝑗

1 1 1 1 0 6
1 −𝑗 −1 𝑗 1 −2 + 2𝑗
𝐗 4 = 𝐖𝟒 𝐱 𝟒 = [ ][ ] = [ ]
1 −1 1 −1 2 −2
1 𝑗 −1 −𝑗 3 −2 − 2𝑗
Problem: Compute the 5-point DFT and 3-point DFT of the sequence 𝑥 (𝑛) = {1,1,1}
Solution: The N-point DFT of 𝑥(𝑛) i𝑠 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0≤𝑘 ≤𝑁−1
The 5-point DFT of 𝑥(𝑛) i𝑠 𝑋(𝑘) = ∑4𝑛=0 𝑥(𝑛)𝑊5𝑛𝑘 0 ≤ 𝑘 ≤ 4
𝑋 (𝑘) = 𝑥 (𝑜)𝑊50 + 𝑥(1)𝑊5𝑘 + 𝑥(2)𝑊52𝑘 + 𝑥(3)𝑊53𝑘 + 𝑥(4)𝑊54𝑘
𝑋(𝑘) = 1 + 𝑊5𝑘 + 𝑊52𝑘 , 0 ≤ 𝑘 ≤ 4
𝑋 (0) = 1 + 1 + 1 = 3
𝑋(1) = 1 + 𝑊51 + 𝑊52
𝑊51 = e−j2π/5 = cos72° − jsin72° = 0.3 − 𝑗0.95
𝑊52 = e−j2π×2/5 = cos144° − jsin144° = −0.8 − 𝑗0.58
𝑋(1) = 1 + 𝑊51 + 𝑊52 = 1 + 0.3 − 𝑗0.95 − 0.8 − 𝑗0.58 = 0.5 − 𝑗1.53
𝑋(2) = 1 + 𝑊52 + 𝑊54
𝑊52 = e−j2π×2/5 = cos144° − jsin144° = −0.8 − 𝑗0.58
𝑊54 = e−j2π×4/5 = 𝑐𝑜𝑠288 − 𝑗𝑠𝑖𝑛288 = 0.3 + 𝑗0.95

28
 Prepared by Dr.Harish M S, AIT

𝑋 (2) = 1 + 𝑊52 + 𝑊54 = 1 − 0.8 − 𝑗0.58 + 0.3 + 𝑗0.95 = 0.5 + 𝑗0.37

𝑋(3) = 1 + 𝑊53 + 𝑊56
𝑊53 = e−j2π×3/5 = cos216 − jsin216 = −0.8 + j0.587
𝑊56 = e−j2π×6/5 = cos432 − jsin432 = 0.3 − j0.95
𝑋 (3) = 1 + 𝑊53 + 𝑊56 = 1 − 0.8 + j0.587 + 0.3 − j0.95 = 0.5 − j0.37
𝑋(4) = 1 + 𝑊54 + 𝑊58
𝑊54 = e−j2π×4/5 = 𝑐𝑜𝑠288 − 𝑗𝑠𝑖𝑛288 = 0.3 + 𝑗0.95
𝑊58 = e−j2π×8/5 = cos576 − jsin576 = −0.8 + j0.58
𝑋(4) = 1 + 𝑊54 + 𝑊58 = 1 + 0.3 + 𝑗0.95 − 0.8 + j0.58 = 0.5 + j1.53
𝑋(𝑘) = {𝑋 (0), 𝑋 (1), 𝑋(2), 𝑋(3), 𝑋 (4)} = {3,0.5 − 𝑗1.53 ,0.5 + 𝑗0.37,0.5 − j0.37 ,0.5 + j1.53}
The 3-point DFT of 𝑥(𝑛) i𝑠𝑋(𝑘) = ∑2𝑛=0 𝑥(𝑛)𝑊3𝑛𝑘 0 ≤ 𝑘 ≤ 2
𝑋(𝑘 ) = 𝑥(𝑜)𝑊30 + 𝑥(1)𝑊3𝑘 + 𝑥(2)𝑊32𝑘
𝑋(𝑘) = 1 + 𝑊3𝑘 + 𝑊32𝑘 0 ≤ 𝑘 ≤ 2
𝑋 (0) = 1 + 1 + 1 = 3
𝑋(1) = 1 + 𝑊31 + 𝑊32
𝑊31 = e−j2π/3 = cos120° − jsin120° = −0.5 − 𝑗0.866
𝑊32 = e−j2π×2/3 = cos240° − jsin240° = −0.5 + 𝑗0.866
𝑋 (1) = 1 + 𝑊31 + 𝑊32 = 1 − 0.5 − 𝑗0.866 − 0.5 + 𝑗0.866 = 0
𝑋(2) = 1 + 𝑊32 + 𝑊34
𝑊32 = e−j2π×2/3 = cos240° − jsin240° = −0.5 + 𝑗0.866
𝑊34 = e−j2π×4/3 = cos 480 − 𝑗𝑠𝑖𝑛480 = −0.5 − 𝑗0.866
𝑋(2) = 1 + 𝑊32 + 𝑊34 = 1 − 0.5 + 𝑗0.866 − 0.5 − 𝑗0.866 = 0
𝑋(𝑘) = {𝑋 (0), 𝑋(1), 𝑋(2)} = {3,0,0}
Problem: Compute the DFT of the sequence 𝑥(𝑛) = (−1)𝑛 , 0 ≤ 𝑛 ≤ 𝑁 − 1. If
1. 𝑁 = 3,
2. 𝑁 = 4,
3. 𝑁 odd
4. 𝑁 𝐸𝑣𝑒𝑛
Solution:𝑥(𝑛) = (−1)𝑛 0 ≤ 𝑛 ≤ 𝑁 − 1, The graph of signal x(n) as shown in figure 2.18.

29
 Prepared by Dr.Harish M S, AIT

The N-point DFT of 𝑥(𝑛) i𝑠 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘

𝑛=0 𝑥(𝑛)𝑊𝑁 0 ≤ 𝑘 ≤ 𝑁 − 1

1. If 𝑁 = 3 then 𝑋(𝑘) = ∑2𝑛=0 𝑥(𝑛)𝑊3𝑛𝑘 0 ≤ 𝑘 ≤ 2

𝑋(𝑘 ) = 𝑥(0)𝑊30 + 𝑥(1)𝑊3𝑘 + 𝑥(2)𝑊32𝑘
𝑋(𝑘) = 𝑊30 − 𝑊3𝑘 + 𝑊32𝑘
𝑋 (0) = 𝑊30 − 𝑊30 + 𝑊30 = 1 − 1 + 1 = 1
1 𝑗√3 1 𝑗√3
𝑋 (1) = 𝑊30 − 𝑊31 + 𝑊32 = 1 − (− − ) + (− + ) = 1 + 𝑗√3
2 2 2 2

1 𝑗√3 1 𝑗√3
𝑋(2) = 𝑊30 − 𝑊32 + 𝑊34 = 1 − (− + ) + (− − ) = 1 − 𝑗√3
2 2 2 2

𝑋(𝑘) = {𝑋 (0), 𝑋 (1), 𝑋(2)} = {1, 1 + 𝑗√3, 1 − 𝑗√3}

2. If N = 4 𝑋(𝑘) = ∑3𝑛=0 𝑥(𝑛)𝑊4𝑛𝑘 0 ≤ 𝑘 ≤ 3
𝑋(𝑘) = 𝑥(0)𝑊40 + 𝑥(1)𝑊4𝑘 + 𝑥(2)𝑊42𝑘 + 𝑥(2)𝑊43𝑘 , 0≤𝑘≤3
𝑋(𝑘) = 𝑊40 − 𝑊4𝑘 + 𝑊42𝑘 − 𝑊43𝑘
𝑋 (0) = 𝑊40 − 𝑊40 + 𝑊40 − 𝑊40 = 1 − 1 + 1 − 1 = 0
𝑋(1) = 𝑊40 − 𝑊41 + 𝑊42 − 𝑊43 = 1 − (0 − 𝑗) + (−1) − (𝑗) = 0
𝑋(2) = 𝑊40 − 𝑊42 + 𝑊44 − 𝑊46 = 1 − (−1) + (1) − (−1) = 4
𝑋(3) = 𝑊40 − 𝑊43 + 𝑊46 − 𝑊49 = 1 − (𝑗) + (−1) − (−𝑗) = 0
𝑋 (𝑘) = {0,0,4,0}
3. If N is odd 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥(𝑛)𝑊𝑁 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑁−1 𝑁−1
𝑛 1 − (−1)𝑁 𝑊𝑁𝑁𝑘
𝑋(𝑘) = ∑ (−1 )𝑛 𝑊𝑁𝑛𝑘 = ∑(−𝑊𝑁𝑘 ) =
1 + 𝑊𝑁𝑘
𝑛=0 𝑛=0

If N is odd then

30
 Prepared by Dr.Harish M S, AIT

1 − (−1)𝑁 𝑊𝑁𝑁𝑘 2
𝑋 (𝑘) == 𝑘 =
1 + 𝑊𝑁 1 + 𝑊𝑁𝑘
4. If Nis even 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥(𝑛)𝑊𝑁 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑁−1 𝑁−1
𝑛 1 − (−1)𝑁 𝑊𝑁𝑁𝑘 𝑁
𝑋(𝑘) = ∑ (−1 )𝑛 𝑊𝑁𝑛𝑘 = ∑(−𝑊𝑁𝑘 ) = 𝑘 = 0 𝑖𝑓 𝑘 ≠
1 + 𝑊𝑁 2
𝑛=0 𝑛=0
𝑁
If 𝑁𝑖𝑠 𝑒𝑣𝑒𝑛 𝑎𝑛𝑑 𝑎𝑛𝑑 𝑘 = then
2
𝑁−1 𝑁
𝑁−1 𝑁−1 𝑁−1
𝑛( )
𝑋 (𝑘) = ∑ (−1)𝑛 𝑊𝑁 2
= ∑(−1)𝑛 (−1)𝑛 = ∑ (1)𝑛 = ∑ 1 = 𝑁
𝑛=0 𝑛=0 𝑛=0 𝑛=0

𝑁
0 𝑘≠
𝑋(𝑘) = { 2
𝑁
𝑁 𝐾=
2
Problem: Compute the N-point DFT of 𝑥(𝑛) = 𝛿(𝑛)
Solution: The N-point DFT of 𝑥(𝑛) is 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0≤𝑘 ≤𝑁−1
𝑁−1

𝑋(𝑘) = ∑ 𝛿 (𝑛)𝑊𝑁𝑛𝑘 = 1
𝑛=0

Problem: Compute the 8-point DFT of 𝑥(𝑛) = 𝛿(𝑛) + 𝛿 (𝑛 − 1) + 𝛿 (𝑛 − 2)

Solution: 𝑥(𝑛) = {1, 1, 1}
The N-point DFT of 𝑥(𝑛) is 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0≤ 𝑘 ≤𝑁−1
For 8-point DFT
7

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊8𝑛𝑘 , 0 ≤ 𝑘 ≤ 7
𝑛=0

𝑋(𝑘) = 1 + 𝑊8𝑘 + 𝑊82𝑘

𝑋 (0) = 3
1 1
𝑋 (1) = 1 + 𝑊81 + 𝑊82 = 1 + −j − j = 1.707 − j1.707
√2 √2
𝑋 (2) = 1 + 𝑊82 + 𝑊84 = 1 − j − 1 = −j
𝑋 (3) = 1 + 𝑊83 + 𝑊86 = 1 − 0.707 − j0.707 + j = 0.293 + j0.293
𝑋 (4) = 1 + 𝑊84 + 𝑊88 = 1 − 1 + 1 = 1
𝑋(5) = 1 + 𝑊85 + 𝑊810 = 1 − 0.707 + j0.707 − j = 0.293 − j0.293

31
 Prepared by Dr.Harish M S, AIT

𝑋 (6) = 1 + 𝑊86 + 𝑊812 = 1 + j − 1 = j

𝑋(7) = 1 + 𝑊87 + 𝑊814 = 1 + 0.707 + j0.707 + j = 1.707 + j1.707
𝑋 (𝑘) = {3, 0.707 − j1.707, −j, 0.293 + j0.293, 1, 0.293 − j0.293, j, 1.707 + j1.707}
Symmetric matrix 𝑾𝑵
We know that 𝑁 × 𝑁 matrix 𝑾𝑵 linearly transforms time domain sequence 𝑥(𝑛) in to frequency
domain sequence 𝑋(𝑘) using the relation𝐗 𝑁 = 𝐖𝑁 𝐱 𝑁 . The 𝑾𝑵 is a symmetric matrix, its
elements are real, imaginary or complex matrix given as
1 1 … 1
1 … (𝑁−1)
1 𝑊𝑁 𝑊𝑁2 …
… 𝑊𝑁
𝑾𝑵 = ⋮ ⋮
⋮ … ⋮
(𝑁−1) 𝑁(𝑁−1) (𝑁−1)(𝑁−1)
[1 𝑊𝑁 𝑊𝑁 … 𝑊𝑁 ]
𝑊40 𝑊40 𝑊40 𝑊40
𝑊0 𝑊41 𝑊42 𝑊43
If 𝑁 = 4, then 𝐖4 = 40
𝑊4 𝑊42 𝑊44 𝑊46
[𝑊40 𝑊43 𝑊46 𝑊49 ]
We know that 𝑊40 = 𝑊44 = 𝑊48 = 1,𝑊41 = 𝑊45 = 𝑊49 = −𝑗,𝑊42 = 𝑊46 − 1 and 𝑊43 = 𝑊47 = 𝑗
𝑊40 𝑊40 𝑊40 𝑊40 1 1 1 1
𝑊0 𝑊41 𝑊42 𝑊43 1 −𝑗 −1 𝑗
∴ 𝐖4 = 40 =[ ]
𝑊4 𝑊42 𝑊40 𝑊42 1 −1 1 −1
[𝑊40 𝑊43 𝑊42 𝑊41 ] 1 𝑗 −1 −𝑗

These elements can be marked on the circumference of the unit circle as shown in figure

32
 Prepared by Dr.Harish M S, AIT

𝑊80 𝑊80 𝑊80 𝑊80 𝑊80 𝑊80 𝑊80 𝑊80

𝑊80 𝑊81 𝑊82 𝑊83 𝑊84 𝑊85 𝑊86 𝑊87
𝑊80 𝑊82 𝑊84 𝑊86 𝑊88 𝑊810 𝑊812 𝑊814
𝑊80 𝑊83 𝑊86 𝑊89 𝑊812 𝑊815 𝑊818 𝑊821
Similarly, if 𝑁 = 8, then 𝐖8 =
𝑊80 𝑊84 𝑊88 𝑊812 𝑊816 𝑊820 𝑊824 𝑊828
𝑊80 𝑊85 𝑊810 𝑊815 𝑊820 𝑊825 𝑊830 𝑊835
𝑊80 𝑊86 𝑊812 𝑊818 𝑊824 𝑊830 𝑊836 𝑊842
[𝑊80 𝑊87 𝑊814 𝑊821 𝑊828 𝑊835 𝑊842 𝑊849 ]
𝑊80 𝑊80 𝑊80 𝑊80 𝑊80 𝑊80 𝑊80 𝑊80
𝑊80 𝑊81 𝑊82 𝑊83 𝑊84 𝑊85 𝑊86 𝑊87
𝑊80 𝑊82 𝑊84 𝑊86 𝑊80 𝑊82 𝑊84 𝑊86
𝑊0 𝑊83 𝑊86 𝑊81 𝑊84 𝑊87 𝑊82 𝑊85
= 80
𝑊8 𝑊84 𝑊80 𝑊84 𝑊80 𝑊84 𝑊80 𝑊84
𝑊80 𝑊85 𝑊82 𝑊87 𝑊84 𝑊81 𝑊86 𝑊83
𝑊80 𝑊86 𝑊84 𝑊82 𝑊80 𝑊86 𝑊84 𝑊82
[𝑊80 𝑊87 𝑊86 𝑊85 𝑊84 𝑊83 𝑊82 𝑊81 ]
These elements can be marked on the circumference of the unit circle as shown in figure 2.20.

Problem: Compute the 6-point DFT of the sequence 𝑥(𝑛) = {1, 2, 3} and plot the magnitude and
phase.
Solution: The N-Point DFT of 𝑥(𝑛) is 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0 ≤𝑘 ≤ 𝑁−1
The 6-Point DFT of 𝑥(𝑛) is 𝑋(𝑘) = ∑5𝑛=0 𝑥(𝑛)𝑊6𝑛𝑘 0 ≤ 𝑘 ≤ 5
𝑋 (𝑘) = 𝑥(0)𝑊60 + 𝑥(1)𝑊6𝑘 + 𝑥(2)𝑊62𝑘 + 𝑥(3)𝑊63𝑘 + 𝑥 (4)𝑊64𝑘 + 𝑥(5)𝑊65𝑘

33
 Prepared by Dr.Harish M S, AIT

𝑋 (𝑘) = 1 + 2𝑊6𝑘 + 3𝑊62𝑘

𝑋 (0) = 1 + 2𝑊60 + 3𝑊60 = 1 + 2 + 3 = 6
1 √3 1 √3
𝑋(1) = 1 + 2𝑊61 + 3𝑊62 = 1 + 2 ( − 𝑗 ) + 3 (− − 𝑗 ) = 0.5 − 𝑗4.33
2 2 2 2

1 √3 1 √3
𝑋(2) = 1 + 2𝑊62 + 3𝑊64 = 1 + 2 (− − 𝑗 ) + 3 (− + 𝑗 ) = −1.5 + 𝑗0.866
2 2 2 2
𝑋 (3) = 1 + 2𝑊63 + 3𝑊66 = 1 + 2(−1) + 3(1) = 2
1 √3 1 √3
𝑋 (4) = 1 + 2𝑊64 + 3𝑊68 = 1 + 2 (− + 𝑗 ) + 3 (− − 𝑗 ) = −1.5 − 𝑗0.866
2 2 2 2

1 √3 1 √3
𝑋 (5) = 1 + 2𝑊65 + 3𝑊610 = 1 + 2 ( + 𝑗 ) + 3 (− + 𝑗 ) = 0.5 − 𝑗4.33
2 2 2 2
𝑋 (𝑘) = (6, 0.5 − 𝑗4.33, − 1.5 + 𝑗0.866, 2, −1.5 − 𝑗0.866, 0.5 + 𝑗4.33)
𝑋(𝑘) = 6∠0°, 4.3∠ − 83.41°, 1.73∠150°, 2∠0°, 1.73∠ − 150°, 4.3∠83.41°
|𝑋 (𝑘 )| = 6, 4.3, 1.73, 2, 1.73, 4.3
∠𝑋 (𝑘) = 0°, −83.41°, 150°, 0°, − 150°, 83.41°
∠𝑋(𝑘) = 0, −1.45, 2.62, 0, − 2.62, 1.45

34
 Prepared by Dr.Harish M S, AIT

Problem: Compute the N-point DFT of the sequence 𝑥(𝑛) = 𝑎𝑛 , 0 < 𝑎 < 1, 0 ≤ 𝑛 ≤ 𝑁 − 1
Solution: The N-Point DFT of the sequence 𝑥 (𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑁−1 𝑁−1
1 − (𝑎𝑊𝑁𝑘 )𝑁 1 − 𝑎𝑁 𝑊𝑁𝑘𝑁 1 − 𝑎𝑁
𝑋 (𝑘 ) = ∑ 𝑎𝑛 𝑊𝑁𝑛𝑘 = ∑(𝑎𝑊𝑁𝑘 )𝑛 = = =
1 − 𝑎𝑊𝑁𝑘 1 − 𝑎𝑊𝑁𝑘 1 − 𝑎𝑊𝑁𝑘
𝑛=0 𝑛=0

1 − 𝑎𝑁
∴ 𝑋 (𝑘 ) = , 0≤𝑘 ≤𝑁−1
1 − 𝑎𝑊𝑁𝑘
Problem: Compute the N-point DFT of the sequence 𝑥(𝑛) = 𝑎𝑛 , 0 ≤𝑛 ≤𝑁−1
Solution: The N-Point DFT of the sequence 𝑥 (𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑁−1 𝑁−1

𝑋 (𝑘 ) = ∑ 𝑎𝑛𝑊𝑁𝑛𝑘 = 𝑎 ∑ 𝑛𝑊𝑁𝑛𝑘
𝑛=0 𝑛=0

1−𝑏 𝑁 𝑏𝑁 −1
Consider ∑𝑁−1 𝑛
𝑛=0 𝑏 = =
1−𝑏 𝑏−1

𝑏𝑁 −1
∑𝑁−1 𝑛
𝑛=0 𝑏 = Differentiate both the side with respect to b we get
𝑏−1

35
 Prepared by Dr.Harish M S, AIT

𝑁−1
𝑛−1
(𝑏 − 1)𝑁𝑏𝑁−1 − (𝑏𝑁 − 1)
∑ 𝑛𝑏 =
(𝑏 − 1)2
𝑛=0
𝑁−1
𝑛𝑏𝑛 (𝑏 − 1)𝑁𝑏𝑁−1 − (𝑏𝑁 − 1)
∑ =
𝑏 (𝑏 − 1)2
𝑛=0
𝑁−1
𝑏[(𝑏 − 1)𝑁𝑏𝑁−1 − (𝑏𝑁 − 1)]
∑ 𝑛𝑏𝑛 =
(𝑏 − 1)2
𝑛=0
𝑁−1
𝑏[ 𝑏𝑁𝑏𝑁−1 − 𝑁𝑏𝑁−1 − (𝑏𝑁 − 1)]
∑ 𝑛𝑏𝑛 =
(𝑏 − 1)2
𝑛=0
𝑁−1
𝑏[ 𝑁𝑏𝑁 − 𝑁𝑏𝑁−1 − 𝑏𝑁 + 1]
∑ 𝑛𝑏𝑛 =
(𝑏 − 1)2
𝑛=0
𝑁−1
𝑏[ 𝑏𝑁 (𝑁 − 1) − 𝑁𝑏𝑁−1 + 1]
∑ 𝑛𝑏𝑛 =
(𝑏 − 1)2
𝑛=0

Put 𝑏 = 𝑊𝑁𝑘
𝑁−1 (𝑁−1)𝑘
𝑊𝑁𝑘 [𝑊𝑁𝑘𝑁 (𝑁 − 1) − 𝑁𝑊𝑁 + 1] 𝑊𝑁𝑘 [(𝑁 − 1) − 𝑁𝑊𝑁−𝑘 + 1]
∑ 𝑛𝑊𝑁𝑘 = =
(𝑊𝑁𝑘 − 1)2 (𝑊𝑁𝑘 − 1)2
𝑛=0

𝑊𝑁𝑘 [𝑁 − 𝑁𝑊𝑁−𝑘 ] 𝑊𝑁𝑘 𝑁[1 − 𝑊𝑁−𝑘 ]

= =
(𝑊𝑁𝑘 − 1)2 (𝑊𝑁𝑘 − 1)2
𝑁−1
𝑁[𝑊𝑁𝑘 − 1 ] 𝑁
∑ 𝑛𝑊𝑁𝑘 = = 𝑘 2
= 𝑘
(𝑊𝑁 − 1) 𝑊𝑁 − 1
𝑛=0
𝑎𝑁
∴ 𝑋(𝑘) = 𝑎 ∑𝑁−1 𝑘
𝑛=0 𝑛𝑊𝑁 = 𝑊 𝑘 −1 If 𝑘 ≠ 0
𝑁

𝑁−1
𝑎𝑁(𝑁 − 1)
𝑋 (𝑘 ) = 𝑎 ∑ 𝑛 = If k = 0
2
𝑛=0

𝑎𝑁
If k ≠ 0
𝑊𝑁𝑘 − 1
𝑋 (𝑘 ) =
𝑎𝑁(𝑁 − 1)
{ If k = 0
2
Problem: Compute the IDFT of the sequence 𝑋(𝑘) = {1,2,3,4}
Solution: The N-point IDFT of the sequence 𝑋(𝑘) is

36
 Prepared by Dr.Harish M S, AIT

𝑁−1
1
𝑥(𝑛) = ∑ 𝑋(𝑘)𝑊𝑁−𝑛𝑘 , 0 ≤ 𝑛 ≤ 𝑁 − 1
𝑁
𝑘=0
1
Given 𝑁 = 4 then 𝑥 (𝑛) = 4 ∑3𝑘=0 𝑋 (𝑘)𝑊4−𝑛𝑘 , 0 ≤ 𝑛 ≤ 3
1
𝑥 (𝑛 ) = (𝑋(0)𝑊40 + 𝑋 (1)𝑊4−𝑛 + 𝑋(2)𝑊4−2𝑛 + 𝑋 (3)𝑊4−3𝑛 )
4
1
= ( 𝑊40 + 2𝑊4−𝑛 + 3𝑊4−2𝑛 + 4𝑊4−3𝑛 )
4
1 1
𝑥(0) = (𝑊40 + 2𝑊40 + 3𝑊40 + 4𝑊40 ) = (1 + 2 + 3 + 4) = 2.5
4 4
1
𝑥(1) = (𝑊40 + 2𝑊4−1 + 3𝑊4−2 + 4𝑊4−3 )
4

1 1 1 1
𝑥 (1) = (1 + 2𝑗 − 3 − 4𝑗) = (−2 − 2𝑗) = − − 𝑗
4 4 2 2
1 1 1
𝑥(2) = (𝑊40 + 2𝑊4−2 + 3𝑊4−4 + 4𝑊4−6 ) = (1 + 2(−1) + 3 + 4(−1)) = −
4 4 2
1 1 1 𝑗
𝑥 (3) = (𝑊40 + 2𝑊4−3 + 3𝑊4−6 + 4𝑊4−9 ) = (1 + 2(−𝑗) + 3(−1) + 4(𝑗)) = − +
4 4 2 2
1 1 1 1 𝑗
∴ 𝑥 (𝑛) = (2.5, − − 𝑗 , − , − + )
2 2 2 2 2
1 𝑛 𝑒𝑣𝑒𝑛
Problem: Compute the N-DFT of the sequence 𝑥(𝑛) = { N is even
0 𝑛 𝑜𝑑𝑑
Solution: The N-point DFT of the sequence 𝑥(𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0 ≤ 𝑘 ≤ 𝑁 − 1

37
 Prepared by Dr.Harish M S, AIT

𝑁−1
(𝑁−1)𝑘
𝑋(𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 = 𝑥 (0)𝑊𝑁0 + 𝑥(1)𝑊𝑁𝑘 + 𝑥(2)𝑊𝑁2𝑘 + ⋯ . +𝑥(𝑁 − 1)𝑊𝑁
𝑛=0
(𝑁−2)𝑘
𝑋 (𝑘) = 𝑥(0)𝑊𝑁0 + 𝑥(2)𝑊𝑁2𝑘 + … . +𝑥(𝑁 − 2)𝑊𝑁
𝑁
−1
2

𝑋 (𝑘) = ∑ 𝑥(2𝑛)𝑊𝑁2𝑛𝑘 , 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑛=0
2𝑘𝑁
𝑁 𝑁
−1 −1 1− 𝑊𝑁 2 1− 𝑊𝑁𝑘𝑁 1−1
𝑋(𝑘) = ∑𝑛=0 𝑊𝑁2𝑛𝑘 = ∑𝑛=0 (𝑊𝑁2𝑘 )𝑛 =
2 2
= = 1−𝑊 2𝑘 = 0 If 𝑘 ≠ 0
1−𝑊𝑁2𝑘 1−𝑊𝑁2𝑘 𝑁
𝑁 𝑁
−1 −1 𝑁
𝑋(𝑘) = ∑𝑛=0 𝑊𝑁2𝑛𝑘 = ∑𝑛=0 1 =
2 2
If 𝑘 = 0
2
𝑁 𝑁 𝑁 𝑁 𝑁
−1 −1 2𝑛 −1 −1 𝑁 𝑁
𝑋(𝑘) = ∑𝑛=0
2
𝑊𝑁2𝑛𝑘 = ∑𝑛=0
2
𝑊𝑁 2
= ∑𝑛=0
2
𝑊𝑁𝑛𝑁 = ∑𝑛=0
2
1 = If 𝑘 =
2 2

0 if 𝑘 ≠ 0
𝑁
if 𝑘 = 0
∴ 𝑋 (𝑘 ) = 2
𝑁 𝑁
if 𝑘 =
{2 2
1 𝑛 𝑒𝑣𝑒𝑛
Problem: Compute the N-DFT of the sequence 𝑥(𝑛) = { N is odd
0 𝑛 𝑜𝑑𝑑
Solution: The N-point DFT of the sequence 𝑥(𝑛) is 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥(𝑛)𝑊𝑁 0 ≤ 𝑘 ≤ 𝑁 − 1

38
 Prepared by Dr.Harish M S, AIT

𝑁−1
(𝑁−1)𝑘
𝑋(𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 = 𝑥 (0)𝑊𝑁0 + 𝑥(1)𝑊𝑁𝑘 + 𝑥(2)𝑊𝑁2𝑘 + ⋯ . +𝑥(𝑁 − 1)𝑊𝑁
𝑛=0
(𝑁−1)𝑘
𝑋 (𝑘) = 𝑥(0)𝑊𝑁0 + 𝑥(2)𝑊𝑁2𝑘 + … . +𝑥(𝑁 − 1)𝑊𝑁
𝑁−1
2

𝑋 (𝑘) = ∑ 𝑥(2𝑛)𝑊𝑁2𝑛𝑘 , 0≤ 𝑘 ≤ 𝑁−1

𝑛=0
𝑁−1
𝑁−1 𝑁−1 2𝑘( +1)
2
1− 𝑊𝑁 1− 𝑊𝑁𝑘𝑁 𝑊𝑁𝑘 1−𝑊 𝑘
𝑋(𝑘) = ∑𝑛=0 𝑊𝑁2𝑛𝑘 = ∑𝑛=0(𝑊𝑁2𝑘 )𝑛 =
2 2
= 𝑁
= 1−𝑊 2𝑘 If 𝑘 ≠ 0
1−𝑊𝑁2𝑘 1−𝑊𝑁2𝑘 𝑁

If 𝑘 = 0
𝑁−1 𝑁−1
2 2
𝑁+1
𝑋 (𝑘) = ∑ 𝑊𝑁2𝑛𝑘 = ∑ 1 =
2
𝑛=0 𝑛=0

𝑁+1
𝑖𝑓 𝑘 = 0
2
∴ 𝑋 (𝑘 ) = 1 − 𝑊 𝑘
𝑁
2𝑘 𝑖𝑓 𝑘 ≠ 0
{1 − 𝑊𝑁
1 𝑛 𝑜𝑑𝑑
Problem: Compute the N-DFT of the sequence 𝑥(𝑛) = { N is even
0 𝑛 𝑒𝑣𝑒𝑛
Solution: The N-point DFT of the sequence 𝑥(𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0≤𝑘 ≤𝑁−1

𝑁−1
(𝑁−1)𝑘
𝑋(𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 = 𝑥 (0)𝑊𝑁0 + 𝑥(1)𝑊𝑁𝑘 + 𝑥(2)𝑊𝑁2𝑘 + ⋯ . +𝑥(𝑁 − 1)𝑊𝑁
𝑛=0
(𝑁−1)𝑘
𝑋 (𝑘) = 𝑥(1)𝑊𝑁𝑘 + 𝑥(3)𝑊𝑁3𝑘 + … . +𝑥(𝑁 − 1)𝑊𝑁
𝑁
−1
2
(2𝑛+1)𝑘
𝑋 (𝑘) = ∑ 𝑥(2𝑛 + 1)𝑊𝑁 , 0≤𝑘 ≤𝑁−1
𝑛=0

39
 Prepared by Dr.Harish M S, AIT

𝑁 𝑁 𝑁
−1 −1 −1 2𝑘𝑁
2 2 2
2
(2𝑛+1)𝑘 1 − 𝑊𝑁
𝑋 (𝑘) = ∑ 𝑊𝑁 = 𝑊𝑁𝑘 ∑ 𝑊𝑁2𝑛𝑘 = 𝑊𝑁𝑘 ∑(𝑊𝑁2𝑘 )𝑛 = 𝑊𝑁𝑘 ( )
1 − 𝑊𝑁2𝑘
𝑛=0 𝑛=0 𝑛=0

1− 𝑊𝑁𝑘𝑁 1−1
= 𝑊𝑁𝑘 ( ) = 𝑊𝑁𝑘 (1−𝑊 2𝑘 ) = 0 If 𝑘 ≠ 0
1−𝑊𝑁2𝑘 𝑁

If 𝑘 = 0
𝑁 𝑁
−1
(2𝑛+1)𝑘 −1 𝑁
𝑋(𝑘) = ∑𝑛=0
2
𝑊𝑁 = ∑𝑛=0
2
1= If 𝑘 = 0
2
𝑁
If 𝑘 = 2
𝑁 𝑁 𝑁 𝑁
−1 −1 −1 −1
2 2 2 2
𝑁 𝑁
(2𝑛+1)𝑘 2𝑛
𝑋(𝑘) = ∑ 𝑊𝑁 = 𝑊𝑁𝑘 ∑ 𝑊𝑁2𝑛𝑘 = 𝑊𝑁 ∑ 𝑊𝑁 2 2
= − ∑ 𝑊𝑁𝑛𝑁
𝑛=0 𝑛=0 𝑛=0 𝑛=0
𝑁
−1 𝑁 𝑁
= − ∑𝑛=0
2
𝑊𝑁𝑛𝑁 = − If 𝑘 =
2 2

0 if 𝑘 ≠ 0
𝑁
if 𝑘 = 0
∴ 𝑋 (𝑘 ) = 2
𝑁 𝑁
− if 𝑘 =
{ 2 2
1 𝑛 𝑜𝑑𝑑
Problem: Compute the N point DFT of the sequence 𝑥(𝑛) = { N is odd
0 𝑛 𝑒𝑣𝑒𝑛
Solution: The N-point DFT of the sequence 𝑥(𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0≤𝑘 ≤𝑁−1

𝑁−1
(𝑁−1)𝑘
𝑋(𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 = 𝑥 (0)𝑊𝑁0 + 𝑥(1)𝑊𝑁𝑘 + 𝑥(2)𝑊𝑁2𝑘 + ⋯ . +𝑥(𝑁 − 1)𝑊𝑁
𝑛=0
(𝑁−2)𝑘
𝑋 (𝑘) = 𝑥(1)𝑊𝑁𝑘 + 𝑥(3)𝑊𝑁3𝑘 + … . +𝑥(𝑁 − 2)𝑊𝑁

40
 Prepared by Dr.Harish M S, AIT

𝑁−3
2
(2𝑛+1)𝑘
𝑋 (𝑘) = ∑ 𝑥(2𝑛 + 1)𝑊𝑁 , 0 ≤𝑘 ≤ 𝑁−1
𝑛=0
𝑁−3 𝑁−3 𝑁−3
𝑁−3
2 2 2 2𝑘( +1
2
(2𝑛+1)𝑘 1 − 𝑊𝑁
𝑋 (𝑘 ) = ∑ 𝑊𝑁 = 𝑊𝑁𝑘 ∑ 𝑊𝑁2𝑛𝑘 𝑘 2𝑘 𝑛 𝑘
= 𝑊𝑁 ∑(𝑊𝑁 ) = 𝑊𝑁 ( )
1 − 𝑊𝑁2𝑘
𝑛=0 𝑛=0 𝑛=0

1− 𝑊𝑁−𝑘
= 𝑊𝑁𝑘 ( ) If 𝑘 ≠ 0
1−𝑊𝑁2𝑘

If 𝑘 = 0
𝑁−3 𝑁−3
(2𝑛+1)𝑘 𝑁−1
𝑋(𝑘) = ∑𝑛=0
2
𝑊𝑁 = ∑𝑛=0
2
1= If 𝑘 = 0
2

𝑁−1
𝑖𝑓 𝑘 = 0
2
∴ 𝑋 (𝑘 ) = 1 − 𝑊𝑁−𝑘
= 𝑊𝑁𝑘 ( 2𝑘 ) 𝑖𝑓 𝑘 ≠ 0
{ 1 − 𝑊𝑁

Problem: Compute the N-point DFT of the sequence 𝑥(𝑛) = 1, 0≤ 𝑛 ≤𝐿−1

Solution: The N-point DFT of the sequence 𝑥(𝑛) is 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0≤𝑘 ≤𝑁−1
1−𝑊𝑁𝐿𝑘
𝑋(𝑘) = ∑𝐿−1 𝑛𝑘
𝑛=0 𝑊𝑁 = If 𝑘 ≠ 0, 𝐿 ≠ 𝑁
1−𝑊𝑁𝑘

If 𝑘 = 0, 𝑋 (0) = ∑𝐿−1
𝑛=0 1 = 𝐿

1−𝑊𝑁𝐿𝑘
𝑋(𝑘) = ∑𝐿−1 𝑛𝑘
𝑛=0 𝑊𝑁 = = 0 If 𝑘 ≠ 0, 𝐿 = 𝑁
1−𝑊𝑁𝑘

1 − 𝑊𝑁𝐿𝑘
𝑘 If 𝑘 ≠ 0, 𝐿 ≠ 𝑁
( )
𝑋 𝑘 = 1 − 𝑊𝑁
L If 𝑘 = 0
{ 0 If 𝑘 ≠ 0, 𝐿 = 𝑁
Properties of DFT:
Periodicity property: Statement: If 𝑥(𝑛) and 𝑋(𝑘) are an N-Point DFT pair, then
𝑋(𝑘 + 𝑁) = 𝑋(𝑘) For all k
𝑥(𝑛 + 𝑁) = 𝑥(𝑛) For all n
𝑁−𝑃𝑜𝑖𝑛𝑡 𝐷𝐹𝑇 𝑁−𝑃𝑜𝑖𝑛𝑡 𝐷𝐹𝑇
Linearity property: 𝑥1 (𝑛) ↔ 𝑋1 (𝑘) and 𝑥2 (𝑛) ↔ 𝑋2 (𝑘)
Then for any real-valued or complex valued constants 𝑎1 and 𝑎2 ,
𝑁−𝑃𝑜𝑖𝑛𝑡 𝐷𝐹𝑇
𝑎1 𝑥1 (𝑛) + 𝑎2 𝑥2 (𝑛) ↔ 𝑎1 𝑋1 (𝑘) + 𝑎2 𝑋2 (𝑘)
𝜋𝑛 𝜋𝑛
Problem: Compute the 4-point DFT of the sequence 𝑥(𝑛) = 𝑐𝑜𝑠 + 𝑠𝑖𝑛
4 4

41
 Prepared by Dr.Harish M S, AIT

𝜋𝑛 𝜋𝑛
Solution: 𝑥(𝑛) = 𝑐𝑜𝑠 + 𝑠𝑖𝑛 = 𝑥1 (𝑛) + 𝑥2 (𝑛)
4 4
𝜋𝑛 1 1
𝑥1 (𝑛) = 𝑐𝑜𝑠 , 0 ≤ 𝑛 ≤ 3, 𝑥1 (𝑛) = (1, , 0, − ), 𝑋1 (𝑘) = [1, 1 − 𝑗1.414, 1, 1 + 𝑗1.414]
4 √2 √2
𝜋𝑛 1 1
𝑥2 (𝑛) = 𝑠𝑖𝑛 , 0 ≤ 𝑛 ≤ 3, 𝑥2 (𝑛) = (0, , 1, ), 𝑋2 (𝑘) = [2.414, −1, −0.414, −1]
4 √2 √2

∴ Using linearity property DFT of x(n)is X(k) = 𝑋1 (𝑘) + 𝑋2 (𝑘)

= [1, 1 − 𝑗1.414, 1, 1 + 𝑗1.414] + [2.414, −1, −0.414, −1]
= [3.414, −𝑗1.414, 0.586, 𝑗1.414]
2𝜋𝑛𝑘0
Problem: Compute the N-point DFT of 𝑥 (𝑛) = 𝑐𝑜𝑠 𝑁

Solution: The N-point DFT of 𝑥(𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘

𝑛=0 𝑥 (𝑛 )𝑊𝑁 , 0≤𝑘 ≤𝑁−1
𝑗2𝜋𝑛𝑘0 𝑗2𝜋𝑛𝑘0
−𝑛𝑘0 𝑛𝑘0
2𝜋𝑛𝑘0 𝑒 𝑁 + 𝑒− 𝑁 𝑊𝑁 + 𝑊𝑁
𝑥 (𝑛) = 𝑐𝑜𝑠 = =
𝑁 2 2
𝑁−1 N−1 −𝑛𝑘0 𝑛𝑘0
𝑊𝑁 + 𝑊𝑁
𝑋 (𝑘 ) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 = ∑( )𝑊𝑁𝑛𝑘 = X1 (k) + X2 (k)
2
𝑛=0 n=0
−𝑛𝑘0
𝑊𝑁 𝑊𝑁𝑛𝑘
Let X1 (k) = ∑N−1
n=0 2
(𝑘−𝑘0)𝑛 (𝑘−𝑘0)𝑁
𝑊𝑁 1 1−𝑊𝑁
X1 (k) = ∑N−1
n=0 = 2{ (𝑘−𝑘0) } = 0 If 𝑘 ≠ 𝑘0
2 1−𝑊𝑁

(𝑘−𝑘0)𝑛
𝑊𝑁 1 𝑁
If 𝑘 = 𝑘0 , then X1 (k) = ∑N−1
n=0 = ∑N−1
n=0 2 =
2 2

𝑁
∴ X1 (k) = 𝛿(𝑘 − 𝑘0 )
2
𝑛𝑘 (𝑘+𝑘0)𝑛 (𝑘+𝑘0)𝑁
𝑊𝑁 0 𝑊𝑁𝑛𝑘 𝑊𝑁 1 1−𝑊𝑁
Similarly, LetX2 (k) = ∑N−1
n=0 = ∑N−1
n=0 = 2{ (𝑘−𝑘0) } = 0 If 𝑘 ≠ −𝑘0
2 2 1−𝑊𝑁

(𝑘+𝑘0)𝑛
𝑊𝑁 1 𝑁
If 𝑘 = −𝑘0 , then X 2 (k) = ∑N−1
n=0 = ∑N−1
n=0 2 =
2 2

Using periodic property 𝑋(𝑘) = 𝑥(𝑘 + 𝑁), If 𝑘 = −𝑘0

𝑋(−𝑘0 ) = 𝑥(−𝑘0 + 𝑁)
𝑁
∴ X2 (k) =
𝛿(𝑘 − 𝑁 + 𝑘0 )
2
𝑁 𝑁
𝑋(𝑘) = X1 (k) + X2 (k) = 𝛿 (𝑘 − 𝑘0 ) + 𝛿(𝑘 − 𝑁 + 𝑘0 )
2 2
2𝜋𝑛𝑘0
Problem: Compute the N-point DFT of 𝑥 (𝑛) = 𝑠𝑖𝑛
𝑁

Solution: The N-point DFT of 𝑥(𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘

𝑛=0 𝑥(𝑛)𝑊𝑁 0≤ 𝑘 ≤𝑁−1

42
 Prepared by Dr.Harish M S, AIT

𝑗2𝜋𝑛𝑘0 𝑗2𝜋𝑛𝑘0
−𝑛𝑘0 𝑛𝑘0
2𝜋𝑛𝑘0 𝑒 𝑁 − 𝑒− 𝑁 𝑊𝑁 − 𝑊𝑁
𝑥(𝑛) = 𝑠𝑖𝑛 = =
𝑁 2𝑗 2𝑗
𝑁−1 N−1 −𝑛𝑘0 𝑛𝑘0
𝑊𝑁 − 𝑊𝑁
𝑋 (𝑘 ) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 = ∑( )𝑊𝑁𝑛𝑘 = X1 (k) − X2 (k)
2𝑗
𝑛=0 n=0
−𝑛𝑘0
𝑊𝑁 𝑊𝑁𝑛𝑘
Let X1 (k) = ∑N−1
n=0 2𝑗
(𝑘−𝑘0)𝑛 (𝑘−𝑘0)𝑁
𝑊𝑁 1 1−𝑊𝑁
X1 (k) = ∑N−1
n=0 = 2𝑗 { (𝑘−𝑘0) } = 0 If 𝑘 ≠ 𝑘0
2𝑗 1−𝑊𝑁

(𝑘−𝑘0)𝑛
𝑊𝑁 1 𝑁
If 𝑘 = 𝑘0 , then X1 (k) = ∑N−1
n=0 = ∑N−1
n=0 2𝑗 = 2𝑗
2𝑗

𝑁
∴ X1 (k) = 𝛿(𝑘 − 𝑘0 )
2𝑗
𝑛𝑘 (𝑘+𝑘0)𝑛 (𝑘+𝑘0)𝑁
𝑊𝑁 0 𝑊𝑁𝑛𝑘 𝑊𝑁 1 1−𝑊𝑁
Similarly, LetX2 (k) = ∑N−1
n=0 = ∑N−1
n=0 = 2𝑗 { (𝑘−𝑘0) } = 0 If 𝑘 ≠ −𝑘0
2𝑗 2𝑗 1−𝑊𝑁

(𝑘+𝑘0)𝑛
𝑊𝑁 1 𝑁
If 𝑘 = −𝑘0 , then X 2 (k) = ∑N−1
n=0 = ∑N−1
n=0 2 = 2𝑗
2

Using periodic property 𝑋(𝑘) = 𝑥(𝑘 + 𝑁), If 𝑘 = −𝑘0

𝑋(−𝑘0 ) = 𝑥(−𝑘0 + 𝑁)
𝑁
∴ X2 (k) = 𝛿(𝑘 − 𝑁 + 𝑘0 )
2𝑗
𝑁 𝑁
𝑋(𝑘) = X1 (k) − X2 (k) = 𝛿 (𝑘 − 𝑘0 ) − 𝛿(𝑘 − 𝑁 + 𝑘0 )
2𝑗 2𝑗
𝑗2𝜋𝑛𝑘0
Problem: Compute the N-point DFT of 𝑥 (𝑛) = 𝑒 𝑁 0≤𝑛 ≤𝑁−1
Solution: The N-point DFT of 𝑥(𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘
𝑛=0 𝑥(𝑛)𝑊𝑁 0 ≤ 𝑘 ≤ 𝑁 − 1
2𝜋𝑛𝑘0
−𝑛𝑘𝑜
𝑥 (𝑛 ) = 𝑒 𝑁 = 𝑊𝑁
𝑁−1 𝑁−1 𝑁−1
−𝑛𝑘 (𝑘−𝑘𝑜 )𝑛
𝑋 (𝑘 ) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 =∑ 𝑊𝑁 𝑜 𝑊𝑁𝑛𝑘 = ∑ 𝑊𝑁
𝑛=0 𝑛=0 𝑛=0
(𝑘−𝑘𝑜)𝑁 𝑁𝑘
(𝑘−𝑘𝑜 )𝑛 1−𝑊𝑁 1−𝑊𝑁𝑁𝑘 𝑊𝑁 𝑜
𝑋(𝑘) = ∑𝑁−1
𝑛=0 𝑊𝑁 = (𝑘−𝑘0) = (𝑘−𝑘0) = 0 , if 𝑘 ≠ 𝑘𝑜
1−𝑊𝑁 1−𝑊𝑁

If 𝑘 = 𝑘𝑜 , 𝑋(𝑘) = ∑𝑁−1
𝑛=0 1 = 𝑁

0 𝑖𝑓 𝑘 ≠ 𝑘𝑜
∴ 𝑋 (𝑘 ) = {
𝑁 𝑖𝑓 𝑘 = 𝑘𝑜

43
 Prepared by Dr.Harish M S, AIT

𝑜𝑟 𝑋(𝑘) = 𝑁𝛿(𝑘 − 𝑘𝑜 )
𝜋𝑛
Problem: Compute the N-point DFT of 𝑥 (𝑛) = 4 + 𝑐𝑜𝑠 2 ( 2 )

Solution: The N-point DFT of 𝑥(𝑛) is 𝑋 (𝑘) = ∑𝑁−1 𝑛𝑘

𝑛=0 𝑥(𝑛)𝑊𝑁 0 ≤ 𝑘 ≤ 𝑁 − 1

2𝜋𝑛 1 4𝜋𝑛
𝑥(𝑛) = 4 + 𝑐𝑜𝑠 2 (
) = 4 + (1 + 𝑐𝑜𝑠 )
4 2 4
1 1 1 (−1)𝑛 9 (−1)𝑛
𝑥(𝑛) = 4 + (1 + cos 𝜋𝑛) = 4 + (1 + (−1)𝑛 ) = 4 + + = +
2 2 2 2 2 2
𝑛
9 (−1)
∴ 𝑥 (𝑛 ) = +
2 2
𝑁−1 𝑁−1
9 (−1)𝑛 𝑛𝑘
𝑋 (𝑘 ) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 =∑ ( + )𝑊𝑁
2 2
𝑛=0 𝑛=0
𝑁−1 𝑁−1
9 𝑛𝑘 (−1)𝑛 𝑛𝑘
( )
𝑋 𝑘 = ∑ 𝑊𝑁 + ∑ 𝑊𝑁
2 2
𝑛=0 𝑛=0

9 1−𝑊 𝑁𝑘 1 1−(−1)𝑁 𝑊𝑁𝑁𝑘 1 2 1

𝑋(𝑘) = 2 ( 1−𝑊𝑁𝑘 ) + 2 ( ) = 0 + 2 (1+𝑊 𝐾 ) = If 𝑘 ≠ 0, 𝑁 odd
𝑁 1+𝑊𝑁𝑘 𝑁 1+𝑊𝑁𝐾

9 1−𝑊 𝑁𝑘 1 1−(−1)𝑁 𝑊𝑁𝑁𝑘

𝑋(𝑘) = 2 ( 1−𝑊𝑁𝑘 ) + 2 ( ) = 0 + 0 = 0 If 𝑘 ≠ 0, 𝑁 even
𝑁 1−𝑊𝑁𝑘

If 𝑘 = 0
9 (−1)𝑛 9 (−1)𝑛 9𝑁 1 1
𝑋(0) = ∑𝑁−1 0 𝑁−1
𝑛=0 2 𝑊𝑁 + ∑𝑛=0 𝑊𝑁0 = ∑𝑁−1 𝑁−1
𝑛=0 2 + ∑𝑛=0 = + 2 = 2 (9𝑁 + 1) If 𝑘 =
2 2 2

0, 𝑁 odd
9 (−1)𝑛 9𝑁 1 9𝑁
𝑋(0) = ∑𝑁−1 𝑁−1
𝑛=0 2 + ∑𝑛=0 = + 2 (0) = If 𝑘 = 0, 𝑁 even
2 2 2
𝑁
If 𝑘 = 2
𝑁 𝑁
𝑁 9 𝑛 (−1)𝑛 𝑛 9 (−1)𝑛 (−1)𝑛 𝑁
𝑋 ( 2 ) = ∑𝑁−1
𝑛=0 2 𝑊𝑁
2
+ ∑𝑁−1
𝑛=0 𝑊𝑁 2
= ∑𝑁−1 𝑛 𝑁−1
𝑛=0 2 (−1) + ∑𝑛=0 = 0 + 2 If 𝑘 =
2 2
𝑁
2

44
 Prepared by Dr.Harish M S, AIT

1
If 𝑘 ≠ 0, 𝑁 odd
1 − 𝑊𝑁𝐾
0 If 𝑘 ≠ 0, 𝑁 even
1
𝑋 (𝑘 ) = (9N + 1)If k = 0 N odd
2
9N
If k = 0 N even
2
𝑁 𝑁
{ 𝐼𝑓 𝑘 =
2 2
Circular symmetries of a sequence
Circular shift of a sequence
Consider a finite duration sequence 𝑥(𝑛), 0 ≤ 𝑛 ≤ 𝑁 − 1. The periodic extension of 𝑥(𝑛) is
𝑥𝑝 (𝑛) = ∑∞
𝑙=−∞ 𝑥(𝑛 − 𝑙𝑁 ) , the period of 𝑥𝑝 (𝑛) is N. Consider the signal 𝑥(𝑛) =
𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓
{ }, the periodic extension of 𝑥(𝑛) is 𝑥𝑝 (𝑛) = ∑∞
𝑙=−∞ 𝑥(𝑛 − 𝑙𝑁)
↑
1
𝑥 𝑝 (𝑛 ) = ∑ 𝑥(𝑛 − 𝑙4) = x(n + 6) + x(n) + x(n − 6)
𝑙=−1

𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓
={ }
↑
The graph of 𝑥(𝑛) and 𝑥𝑝 (𝑛) is as shown in figure 2.27 (a) and (b) respectively.

Now suppose that we shift the periodic sequence 𝑥𝑝 (𝑛) by k samples towards right, let us say
𝑘 = 2 we obtain another periodic 𝑥′𝑝 (𝑛) signal as shown in figure 2.28 (c). Let 𝑥′(𝑛) is a finite
𝑥′ (𝑛) 0≤𝑛 ≤𝑁−1
duration sequence derived from 𝑥′𝑝 (𝑛) is as follows 𝑥 ′ (𝑛) = { 𝑝 . The
0 other wise
plot 𝑥 ′ (𝑛) is as shown in figure 2.28 (d).

45
 Prepared by Dr.Harish M S, AIT

𝑒, 𝑓, 𝑎, 𝑏, 𝑐, 𝑑
The samples of 𝑥 ′ (𝑛) are 𝑥 ′ (𝑛) = { }
↑
To relate 𝑥(𝑛) with 𝑥 ′ (𝑛) we have to use circular shift and modulo index 𝑁.
𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓 𝑒, 𝑓, 𝑎, 𝑏, 𝑐, 𝑑
Example: signal 𝑥(𝑛) = { }, 0 ≤ 𝑛 ≤ 5, 𝑁 = 6 𝑥 ′ (𝑛) = { }
↑ ↑
The sequences of 𝑥(𝑛) and 𝑥 ′ (𝑛) are marked on the circumference of circle in anticlockwise
direction is as shown in figure 2.29(g) and (h) respectively.

46
 Prepared by Dr.Harish M S, AIT

From the diagram it is observed that 𝑥 ′ (𝑛) is circularly shifted two samples in anticlockwise
direction. Now we relate 𝑥(𝑛) and 𝑥 ′ (𝑛) using an index modulo N.
x ′ (n) = x(n − k, modulo N)
= x(N + n − k) = x((n − k))N
Since𝑘 = 2, x ′ (n) = x(N + n − 2) = x((n − 2))N
x ′ (0) = x(6 + 0 − 2) = x(4) = e
x ′ (1) = x(6 + 1 − 2) = x(5) = f
x ′ (2) = x(6 + 2 − 2) = x(6) = x(0) = a
x ′ (3) = x(6 + 3 − 2) = x(7) = x(1) = b
x ′ (4) = x(6 + 4 − 2) = x(8) = x(2) = c
x ′ (5) = x(6 + 5 − 2) = x(9) = x(3) = e
Circularly even sequence: An N-point sequence is called circularly even if it is symmetric
about the point zero on the circle. This implies that
𝑥(𝑁 − 𝑛) = 𝑥(𝑛), 1 ≤ 𝑛 ≤ 𝑁 − 1
Example: 𝑥(𝑛) = {1, 4, 3, 4}
Verification: 𝑥(𝑁 − 𝑛) = 𝑥(𝑛)
𝑥(4 − 𝑛) = 𝑥(𝑛), 𝑥(3) = 𝑥(1) = 4, 𝑥(2) = 𝑥(2) = 3

Circularly odd sequence: An N-point sequence is called circularly odd if it is anti-symmetric

about the point zero on the circle. This implies that
𝑥(𝑁 − 𝑛) = −𝑥(𝑛), 1 ≤ 𝑛 ≤ 𝑁 − 1
Example: 𝑥(𝑛) = {0, −2, −3, 3, 2}

47
 Prepared by Dr.Harish M S, AIT

Verification: 𝑥(𝑁 − 𝑛) = −𝑥(𝑛)

𝑥(5 − 𝑛) = −𝑥(𝑛), 𝑥(4) = −𝑥 (1), 𝑥(3) = −𝑥(2)

Circular folding (Time reversal): The circular folding of an N-point sequence is obtained by
reversing its samples about the point zero on the circle. If N-point sequence 𝑥(𝑛) is folded
circularly then it is denoted as𝑥((−𝑛))𝑁 = 𝑋 (𝑁 − 𝑛), 0 ≤ 𝑛 ≤ 𝑁 − 1. This circularly folded
equivalent of 𝑥(𝑛) is 𝑥((−𝑛))𝑁 is marked on the circumference of the circle in anticlockwise
direction.
Example: Let 𝑥(𝑛) = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓 }, 𝑥 ′ (𝑛) = 𝑥((−𝑛))6 = {𝑎, 𝑓, 𝑒, 𝑑, 𝑐, 𝑏} is as shown in
figure (i) and (j).

Symmetrical properties of DFT

1. DFT of real-valued sequences (Neither circularly odd nor circularly even)
The signal 𝑥(𝑛) is real-valued sequences consists of N samples, and it is neither circularly odd
nor circularly even.

48
 Prepared by Dr.Harish M S, AIT

The its N-point DFT is 𝑋(𝑘)

𝑁−1

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑛=0

Take conjugate on both sides, we get 𝑋 ∗ (𝑘) = ∑𝑁−1 ∗ −𝑛𝑘

𝑛=0 𝑥 (𝑛)𝑊𝑁
𝑁−1

𝑋 𝑘) = ∑ 𝑥 ∗ (𝑛)𝑊𝑁−𝑛𝑘 WNnN
∗(

𝑛=0
𝑁−1
∗( (𝑁−𝑘)𝑛
𝑋 𝑘) = ∑ 𝑥(𝑛)𝑊𝑁 = X(N − k)
𝑛=0

𝑋 ∗ (𝑘) = X(N − k) = X((−k))N

|X(N − k)| = |X(K)|, ∠𝑋(𝑁 − 𝑘) = −∠𝑋(𝑘)
If 𝑥(𝑛) is real and consists of N sequences, then its DFT are conjugating symmetrical about
𝑁
point 2 .

Problem: Compute the 4 point DFT of 𝑥(𝑛) = {1, 2, 3, 4} if 𝑥 (𝑛) is real.

Solution: The N-point DFT of 𝑥(𝑛) is 𝑋(𝑘)
𝑁−1

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑛=0
3

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊4𝑛𝑘 0 ≤ 𝑘 ≤ 3
𝑛=0

𝑋 (𝑘 ) = 1 + 2𝑊4𝑘 + 3𝑊42𝑘 + 4𝑊43𝑘 = {10, −2 + 2𝑗, −2, −2 − 2𝑗}

Problem: Compute the 5 point DFT of 𝑥(𝑛) = {1, 2, 3, 4,5} if x(n) is real.
Solution: The N-point DFT of 𝑥(𝑛) is 𝑋(𝑘)
𝑁−1

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑛=0

49
 Prepared by Dr.Harish M S, AIT

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊5𝑛𝑘 0 ≤ 𝑘 ≤ 4
𝑛=0

𝑋 (𝑘) = 1 + 2𝑊5𝑘 + 3𝑊52𝑘 + 4𝑊53𝑘 + 5𝑊54𝑘

= {15, −2.5 + 3.44𝑗, −2.5 + 0.812𝑗, −2.5 − 0.812𝑗, −2.5 − 3.44𝑗}

Problem: The first five points of the eight point DFT of a real valued sequence are
{0.25, 0.125 − 𝑗0.3018, 0, 0.125 − 𝑗0.0518, 0}.Determine the remaining three points.
Solution: 𝑋 (0) = 0.25, 𝑋(1) = 0.125 − 𝑗0.3018, 𝑋(2) = 0, 𝑋(3) = 0.125 −
𝑗0.0518, 𝑋 (4) = 0
The remaining three points𝑋(5), 𝑋(6) and 𝑋(7) are determined using symmetry property
𝑋 ∗ (𝑘) = X(N − k)
𝑋 ∗ (𝑘) = X(8 − k)
𝑋(𝑘) = 𝑋 ∗ (8 − k)
𝑋 (5) = 𝑋 ∗ (8 − 5) = 𝑋 ∗ (3) = 0.125 + 𝑗0.0518
𝑋 (6) = 𝑋 ∗ (8 − 6) = 𝑋 ∗ (2 ) = 0
𝑋(7) = 𝑋 ∗ (8 − 7) = 𝑋 ∗ (1) = 0.125 + 𝑗0.3018
Problem: A 174-point DFT of a real valued sequence 𝑥(𝑛) has the following DFT samples.
𝑋 (0) = 11, 𝑋 (9) = −3.4 + 𝑗5.9, 𝑋 (𝑘1 ) = 7.7 + 𝑗2.4, 𝑋(51) = 5 − 𝑗1.6, 𝑋(𝑘2 ) = 8.7 +
𝑗4.9, 𝑋 (87) = 4.5, 𝑋(113) = 8.7 − 𝑗4.9, 𝑋 (𝑘3 ) = 5 + 𝑗1.6, 𝑋 (162) = 7.7 − 𝑗2.4, and 𝑋 (𝑘4 ) =
−3.4 − 𝑗5.9. Remaining DFT samples are zero, determine the values of 𝑘1 , 𝑘2 , 𝑘3 𝑎𝑛𝑑 𝑘4
Solution: 𝑋 (𝑘1 ) = 7.7 + 𝑗2.4 and 𝑋(162) = 7.7 − 𝑗2.4
Since 𝑋(𝑘) = 𝑋 ∗ (N − k)
𝑋 ∗ (174 − k) = 𝑋 ∗ (k)
174 − 𝑘1 = 162,
∴ 𝑘1 = 174 − 162 = 12
𝑘2 = 174 − 113 = 61

50
 Prepared by Dr.Harish M S, AIT

𝑘3 = 174 − 51 = 123
𝑘4 = 174 − 9 = 165
Problem: Let 𝑋(𝑘)0 ≤ 𝑘 ≤ 10 be the 11-point DFT of real sequence x (n). The even samples of
X (k) are𝑋 (0) = 4, 𝑋 (2) = −1 + 𝑗3, 𝑋 ( 4) = 2 + 𝑗5, 𝑋 (6) = 9 − 𝑗6, 𝑋(8) = −5 −
𝑗8, 𝑋 (10) = √3 − 𝑗2, , determine the missing samples.
Solution:
𝑋(𝑘) = 𝑋 ∗ (N − k)
𝑋(1) = 𝑋 ∗ (11 − 1) = 𝑋 ∗ (10) = √3 + 𝑗2
𝑋(3) = 𝑋 ∗ (11 − 3) = 𝑋 ∗ (8) = −5 + 𝑗8
𝑋(5) = 𝑋 ∗ (11 − 5) = 𝑋 ∗ (6) = 9 + 𝑗6
𝑋(7) = 𝑋 ∗ (11 − 7) = 𝑋 ∗ (4) = 2 − 𝑗5
𝑋(9) = 𝑋 ∗ (11 − 9) = 𝑋 ∗ (2) = −1 − 𝑗3
2. DFT of real and even sequences (DFT of circularly real and even sequences)
Let 𝑥(𝑛) consists of N samples, be a real and even. The N-point DFT of 𝑥(𝑛) is 𝑋(𝑘)
𝑁−1

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 = 𝑋𝑅 (𝑘) + 𝑗𝑋𝐼 (𝑘)0 ≤ 𝑘 ≤ 𝑁 − 1

𝑛=0
𝑁−1
−𝑗2𝜋𝑛𝑘
𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑒 𝑁

𝑛=0
𝑁−1
2𝜋𝑛𝑘 2𝜋𝑛𝑘
𝑋(𝑘) = ∑ 𝑥(𝑛){cos( ) − 𝑗sin( )}
𝑁 𝑁
𝑛=0
𝑁−1 𝑁−1
2𝜋𝑛𝑘 2𝜋𝑛𝑘
𝑋(𝑘) = ∑ 𝑥(𝑛) cos( ) − 𝑗 ∑ 𝑥(𝑛) sin ( )
𝑁 𝑁
𝑛=0 𝑛=0
2𝜋𝑛𝑘 2𝜋𝑛𝑘
because 𝑥(𝑛) is even, sin ( )odd, its product is𝑥(𝑛) sin ( )odd, its summation for one
𝑁 𝑁
2𝜋𝑛𝑘 2𝜋𝑛𝑘
period is zero and cos ( )is even, and the product is 𝑥(𝑛) con ( )is even, then
𝑁 𝑁
𝑁−1
2𝜋𝑛𝑘
∴ 𝑋 (𝑘) = ∑ 𝑥(𝑛) cos( ) = 𝑋𝑅 (𝑘)0 ≤ 𝑘 ≤ 𝑁 − 1
𝑁
𝑛=0

𝑋(𝑘), is purely real and even

Since imaginary part𝑋𝐼 (𝑘) = 0 , then IDFT is

51
 Prepared by Dr.Harish M S, AIT

𝑁−1
1 2𝜋𝑛𝑘
𝑥(𝑛) = ∑ 𝑋 (𝑘) cos ( ) 0 ≤ 𝑛 ≤𝑁 − 1
𝑁 𝑁
𝑘=0

8, 2, 6, 2
Problem: Find the 4-point DFT of 𝑥(𝑛) = { }
↑
8, 2, 6, 2
Solution:The given signal𝑥(𝑛) = { } is circularly even, it will satisfies the condition
↑
𝑥(𝑛) = 𝑥(𝑁 − 𝑛) 1 ≤ 𝑛 ≤ 𝑁 − 1, and DFT sequences are purely real
𝑥 (1) = 𝑥 (3) = 2
𝑥 (2) = 𝑥 (2) = 6

𝑁−1

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 0 ≤ 𝑘 ≤ 𝑁 − 1
𝑛=0
3

𝑋 (𝑘) = ∑ 𝑥(𝑛)𝑊4𝑛𝑘 0 ≤ 𝑘 ≤ 3
𝑛=0

𝑋 (𝑘 ) = 𝑥(0)𝑊40 + 𝑥(1)𝑊4𝑘 + 𝑥(2)𝑊42𝑘 + 𝑥(3)𝑊43𝑘

𝑋(𝑘) = 8𝑊40 + 2𝑊4𝑘 + 6𝑊42𝑘 + 2𝑊43𝑘 = {18, 2, 10, 2}, is purely real and even
3. DFT of real and odd sequences (DFT of circularly real and odd sequences)
Let 𝑥(𝑛) consists of N samples, be a real and circularly odd. The N-point DFT of 𝑥(𝑛) is 𝑋(𝑘)
𝑁−1

𝑋(𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 = 𝑋𝑅 (𝑘) + 𝑗𝑋𝐼 (𝑘)0 ≤ 𝑘 ≤ 𝑁 − 1

𝑛=0

52
 Prepared by Dr.Harish M S, AIT

𝑁−1
−𝑗2𝜋𝑛𝑘
𝑋(𝑘) = ∑ 𝑥(𝑛)𝑒 𝑁

𝑛=0
𝑁−1
2𝜋𝑛𝑘 2𝜋𝑛𝑘
𝑋 (𝑘) = ∑ 𝑥(𝑛){cos( ) − 𝑗sin( )}
𝑁 𝑁
𝑛=0
𝑁−1 𝑁−1
2𝜋𝑛𝑘 2𝜋𝑛𝑘
𝑋 (𝑘) = ∑ 𝑥(𝑛) cos( ) − 𝑗 ∑ 𝑥(𝑛) sin ( )
𝑁 𝑁
𝑛=0 𝑛=0
2𝜋𝑛𝑘 2𝜋𝑛𝑘
Because 𝑥(𝑛) is odd, cos ( )even, its product is𝑥(𝑛) cos ( )odd, its summation for
𝑁 𝑁
2𝜋𝑛𝑘 2𝜋𝑛𝑘
one period is zero, and sin ( )is odd, and the product 𝑥(𝑛) sin ( )is even then
𝑁 𝑁
𝑁−1
2𝜋𝑛𝑘
∴ 𝑋 (𝑘) = −𝑗 ∑ 𝑥(𝑛) sin( ) = −𝑗𝑋𝐼 (𝑘) 0≤ 𝑘 ≤𝑁−1
𝑁
𝑛=0

𝑋(𝑘), is purely imaginary and odd

Since real part is𝑋𝑅 (𝑘) = 0 , then IDFT is
𝑁−1
1 2𝜋𝑛𝑘
𝑥(𝑛) = 𝑗 ∑ 𝑋(𝑘) sin ( ) 0 ≤ 𝑛 ≤𝑁 −1
𝑁 𝑁
𝑘=0

0, −2, −3 , 3, 2
Problem: Find the 5-point DFT of 𝑥(𝑛) = { }
↑
Solution:The given signal𝑥(𝑛) = {0, −2, −3 , 3, 2} is real and circularly odd it will satisfies the
condition 𝑥(𝑁 − 𝑛) = −𝑥(𝑛), its DFTs are purely imaginary.

The N-point DFT of 𝑥(𝑛) is 𝑋(𝑘) = ∑𝑁−1 𝑛𝑘

𝑛=0 𝑥(𝑛)𝑊𝑁 0≤𝑘 ≤ 𝑁−1

53
 Prepared by Dr.Harish M S, AIT

𝑋 (𝑘) = ∑ 𝑥 (𝑛)𝑊5𝑛𝑘 = 𝑥(0)𝑊50 + 𝑥(1)𝑊5𝑘 + 𝑥(2)𝑊52𝑘 + 𝑥 (3)𝑊53𝑘 + 𝑥(4)𝑊54𝑘

𝑛=0

𝑋(𝑘) = 0 − 2𝑊5𝑘 − 3𝑊52𝑘 + 3𝑊53𝑘 + 3𝑊54𝑘

𝑋(𝑘) = {0, 𝑗7.33, −𝑗3.3, 𝑗3.3, −𝑗7.33}
4. DFT of purely imaginary sequences
Consider an imaginary signal 𝑥(𝑛) = 𝑗𝑥𝐼 (𝑛) consists of N sequences. The N-point DFT of 𝑥(𝑛)
is
𝑁−1

𝑋(𝑘) = ∑ 𝑥(𝑛)𝑊𝑁𝑛𝑘 0≤𝑘 ≤𝑁−1

𝑛=0
𝑁−1 𝑁−1
2𝜋𝑛𝑘 2𝜋𝑛𝑘
= 𝑗 ∑ 𝑥𝐼 (𝑛)𝑊𝑁𝑛𝑘 = 𝑗 ∑ 𝑥𝐼 (𝑛){cos( ) − 𝑗𝑠𝑖𝑛( )}
𝑁 𝑁
𝑛=0 𝑛=0
𝑁−1 𝑁−1
2𝜋𝑛𝑘 2𝜋𝑛𝑘
𝑋(𝑘) = 𝑗 ∑ 𝑥𝐼 (𝑛) cos( ) + ∑ 𝑥𝐼 (𝑛) 𝑠𝑖𝑛( )
𝑁 𝑁
𝑛=0 𝑛=0

𝑋 (𝑘) = 𝑋𝑅 (𝑘) + 𝑗𝑋𝐼 (𝑘)

𝑁−1
2𝜋𝑛𝑘
𝑋𝑅 (𝑘) = ∑ 𝑥𝐼 (𝑛) 𝑠𝑖𝑛( )
𝑁
𝑛=0
𝑁−1
2𝜋𝑛𝑘
𝑋𝐼 (𝑘 ) = ∑ 𝑥𝐼 (𝑛) 𝑐𝑜𝑠( )
𝑁
𝑛=0
2𝜋𝑛𝑘
If𝑥𝐼 (𝑛) is odd, then the product 𝑥𝐼 (𝑛)𝑐𝑜𝑠( ) is odd, thus 𝑋𝐼 (𝑘 ) = 0 and hence 𝑋(𝑘) is
𝑁
2𝜋𝑛𝑘
purely real. On the other hand, if 𝑥𝐼 (𝑛) is even, then the product 𝑥𝐼 (𝑛)𝑠𝑖𝑛( ) is odd, thus
𝑁

𝑋𝑅 (𝑘 ) = 0 and hence 𝑋(𝑘) is purely imaginary. The symmetrical properties given above may be
summarized as follows.

x(n) = xRe (n) + xRo (n) + jxIe (n) + jxIo (n)

X(k) = XRe (k) + X Ro (k) + jXIe (k) + jXIo (k)

Problem: Check if the sequences are even or odd and state their DFTs
i. (1,1,1,0,0,0,1,1)
ii. (1,1,0 0,0,0, −1, −1)
54
 Prepared by Dr.Harish M S, AIT

iii. (0, 1, 1,0, 0, 0, −1, −1)

iv. (0, 1, 1, 0, 0, 0, 1, 1)
Solution:
i. Let𝑥1 (𝑛) = (1,1,1,0,0,0,1,1), and 𝑁 = 8, if we mark 𝑥1 (𝑛) on the circumference of the
circle, it is observed that 𝑥1 (𝑛) is symmetric about point zero. Therefore 𝑥1 (𝑛) is real and
circularly even, thus its DFT sequences are real and even .i.e.
𝑋1 (𝑘) = (5, 2.4, − 1, −0.41, 1, −0.41, 1, 2.4)

ii. Let𝑥2 (𝑛) = (1,1,0,0,0,0, −1, −1), and 𝑁 = 8, if we mark 𝑥2 (𝑛) on the circumference of
the circle, it is observed that 𝑥2 (𝑛) is neither symmetric nor antisymmetric about point
zero. Therefore 𝑥2 (𝑛) is neither circularly even nor circularly odd, thus its DFT
sequences are complex .i.e.
𝑋2 (𝑘) = (0, 1 − 𝑗2.414, 2 − 2𝑗, 1 − 𝑗0.414, 0,
1 + 𝑗0.414, 2 + 2𝑗, 1 + 𝑗2.414)

55
 Prepared by Dr.Harish M S, AIT

iii. Let𝑥3 (𝑛) = (0,1,1,0,0,0, −1, −1), and 𝑁 = 8, if we mark 𝑥3 (𝑛) on the circumference of
the circle, it is observed that 𝑥3 (𝑛) is antisymmetric about point zero. Therefore 𝑥3 (𝑛) is
real and circularly odd, thus its DFT sequences are purely imaginary .i.e.
𝑋2 (𝑘) = (0, 𝑗3.414, −2𝑗, − 𝑗0.585, 0, −𝑗0.585, 2𝑗, 𝑗3.414)

56
 Prepared by Dr.Harish M S, AIT

iv. Let𝑥4 (𝑛) = (0,1,1,0,0,0,1,1), and 𝑁 = 8, if we mark 𝑥4 (𝑛) on the circumference of the
circle, it is observed that 𝑥4 (𝑛) is symmetric about point zero. Therefore 𝑥4 (𝑛) is
circularly even, thus its DFT sequences are real .i.e.
𝑋4 (𝑘) = 4.0000 1.4142 − 2.0000 − 1.4142 0 − 1.4142 − 2.0000 1.4142

Problem: Check if the sequences are even or odd and state their DFTs

57
 Prepared by Dr.Harish M S, AIT

i. (2,2,2,0,0,0,2,2)
ii. (2,2,0 0,0,0, −2, −2)
iii. (0, 2, 2,0, 0, 0, −2, −2)
iv. (0, 2, 2, 0, 0, 0, 2, 2)
Multiplication of two DFTs and circular convolution
Suppose that we have two finite-duration sequences of length N, 𝑥1 (𝑛) and 𝑥2 (𝑛). Their
respective N-point DFTs are
𝑁−1

𝑋1 (𝑘) = ∑ 𝑥1 (𝑛) 𝑊𝑁𝑛𝑘 0 ≤ 𝑘 ≤ 𝑁 − 1

𝑛=0
𝑁−1

𝑋2 (𝑘) = ∑ 𝑥2 (𝑙) 𝑊𝑁𝑙𝑘 0 ≤ 𝑘 ≤ 𝑁 − 1

𝑙=0

If we multiply the two DFTs together, as a result 𝑋3 (𝑘)

𝑋3 (𝑘) = 𝑋1 (𝑘)𝑋2 (𝑘) 0≤𝑘 ≤𝑁−1
The IDFT of 𝑋3 (𝑘) is 𝑥3 (𝑚)
1 𝑁−1
𝑥 3 (𝑚 ) = ∑ 𝑋3 (𝑘)𝑊𝑁−𝑚𝑘
𝑁 𝑘=0

1 𝑁−1
𝑥 3 (𝑚 ) = ∑ 𝑋1 (𝑘)𝑋2 (𝑘)𝑊𝑁−𝑚𝑘
𝑁 𝑘=0
𝑁−1 𝑁−1
1 𝑁−1
𝑥 3 (𝑚 ) = ∑ [∑ 𝑥1 (𝑛) 𝑊𝑁𝑛𝑘 ] [∑ 𝑥2 (𝑙) 𝑊𝑁𝑙𝑘 ] 𝑊𝑁−𝑚𝑘
𝑁 𝑘=0
𝑛=0 𝑙=0

Interchange the order of summation we get

𝑁−1 𝑁−1
1 𝑁−1
𝑥 3 (𝑚 ) = ∑ 𝑥1 (𝑛) ∑ 𝑥2 (𝑙) [∑ 𝑊𝑛𝑛𝑘 𝑊𝑛𝑙𝑘 𝑊𝑁−𝑚𝑘 ]
𝑁 𝑛=0
𝑙=0 𝑘=0
𝑁−1 𝑁−1
1 𝑁−1
(𝑛+𝑙−𝑚)𝑘
𝑥 3 (𝑚 ) = ∑ 𝑥1 (𝑛) ∑ 𝑥2 (𝑙) [∑ 𝑊𝑁 ]
𝑁 𝑛=0
𝑙=0 𝑘=0
𝑁−1 𝑁−1
1 𝑁−1 2𝜋
𝑥 3 (𝑚 ) = ∑ 𝑥1 (𝑛) ∑ 𝑥2 (𝑙) [∑ 𝑒 −𝑗 𝑁 (𝑚−𝑛−𝑙)𝑘 ]
𝑁 𝑛=0
𝑙=0 𝑘=0

2𝜋
−𝑗 (𝑚−𝑛−𝑙)𝑘 2𝜋(𝑚−𝑛−𝑙)𝑘 2𝜋(𝑚−𝑛−𝑙)𝑘
Consider ∑𝑁−1
𝑘=0 𝑒
𝑁 = ∑𝑁−1
𝑘=0 {cos − 𝑗 𝑠𝑖𝑛 }
𝑁 𝑁

58
 Prepared by Dr.Harish M S, AIT

If (𝑚 − 𝑛 − 𝑙) is an integer multiple of 𝑁 then

𝑁−1
2𝜋(𝑚 − 𝑛 − 𝑙)𝑘 2𝜋(𝑚 − 𝑛 − 𝑙)𝑘
} = {𝑁 𝑙 =𝑚−𝑛+𝑁
∑ {cos − 𝑗 𝑠𝑖𝑛
𝑁 𝑁 0 otherwise
𝑘=0

Therefore 𝑚 − 𝑛 − 𝑙 = −𝑝𝑁, 𝑙 = 𝑚 − 𝑛 + 𝑝𝑁 , p is an integer; it may be positive or

negative, if 𝑝 = 1, then 𝑙 = 𝑚 − 𝑛 + 𝑁 = ((𝑚 − 𝑛))𝑁
𝑁−1

∴ 𝑥3 (𝑚) = ∑ 𝑥1 (𝑛)𝑥3 ((𝑚 − 𝑛))𝑁 0 ≤ 𝑚 ≤ 𝑁 − 1

𝑛=0

The above expression is an equation for circular convolution since 𝑥2 (𝑛) is circularly
folded. Thus weconclude that multiplication of the DFTs of two sequences is equivalent to
the circular convolution of the two sequences in the time domain. Therefore if
𝑁−𝑃𝑜𝑖𝑛𝑡 𝐷𝐹𝑇
𝑥1 (𝑛) ↔ 𝑋1 (𝑘)
𝑁−𝑃𝑜𝑖𝑛𝑡 𝐷𝐹𝑇
And 𝑥2 (𝑛) ↔ 𝑋2 (𝑘) then
𝑁−𝑃𝑜𝑖𝑛𝑡 𝐷𝐹𝑇
𝑥1 (𝑛) ⊛ 𝑥2 (𝑛) ↔ 𝑋1 (𝑘)𝑋2 (𝑘)
Problem: Perform the circular convolution of the following two sequences 𝑥1 (𝑛) =
2,1, 2, 1 1,2, 3, 4
{ } and 𝑥2 (𝑛) = { }.
↑ ↑
2,1, 2, 1 1,2, 3, 4
Solution: 𝑥1 (𝑛) = { } and 𝑥2 (𝑛) = { }.
↑ ↑
𝑁−1

𝑥1 (𝑛) ⊛ 𝑥2 (𝑛) = 𝑥3 (𝑚) = ∑ 𝑥1 (𝑛)𝑥2 ((𝑚 − 𝑛))𝑁 0≤𝑚≤𝑁−1

𝑛=0
3

𝑥3 (𝑚) = ∑ 𝑥1 (𝑛)𝑥2 ((𝑚 − 𝑛))4 0≤𝑚≤3

𝑛=0

The signal 𝑥1 (𝑛) and 𝑥2 (𝑛) are graphed as shown in figure 2.41(a) and (b) respectively

59
 Prepared by Dr.Harish M S, AIT

Now 𝑥3 (𝑚) is obtained by circularly convolving 𝑥1 (𝑛) and 𝑥2 (𝑛)

For 𝑚 = 0
3

𝑥3 (0) = ∑ 𝑥1 (𝑛)𝑥2 ((−𝑛))4

𝑛=0

The signal 𝑥2 ((−𝑛))4 is simply the folded version of 𝑥2 (𝑛) and graphed on a circle as
shown in figure 2.42 (c)

𝑥3 (0) = 14

For 𝑚 = 1
3

𝑥3 (1) = ∑ 𝑥1 (𝑛)𝑥2 ((1 − 𝑛))4

𝑛=0

The signal 𝑥2 ((1 − 𝑛))4 is obtained simply the sequence 𝑥2 ((−𝑛))4 shifted one sample in
anticlockwise direction as shown in figure2.43 (d)

60
 Prepared by Dr.Harish M S, AIT

𝑥3 (1) = 16
For 𝑚 = 2
3

𝑥3 (2) = ∑ 𝑥1 (𝑛)𝑥2 ((2 − 𝑛))4

𝑛=0

The signal 𝑥2 ((2 − 𝑛))4 is obtained simply the sequence 𝑥2 ((−𝑛))4 shifted two samples in
anticlockwise direction as shown in figure 2.44 (f)

𝑥3 (2) = 14

For 𝑚 = 3
3

𝑥3 (3) = ∑ 𝑥1 (𝑛)𝑥2 ((3 − 𝑛))4

𝑛=0

The signal 𝑥2 ((3 − 𝑛))4 is obtained simply the sequence 𝑥2 ((−𝑛))4 shifted three samples in
anticlockwise direction as shown in figure 2.45 (g).

61
 Prepared by Dr.Harish M S, AIT

𝑥3 (3) = 16
14,16,14,16
∴ 𝑥 3 (𝑛 ) = { }
↑
Using tabulation method

m x1(n) x2((m-n))4 x3(m)

0 2,1, 2, 1 1,4, 3, 2 14
{ } { }.
↑ ↑

1 2,1, 2, 1 2, 1,4,3 16
{ } { }
↑ ↑

2 2,1, 2, 1 3,2,1,4 14
{ } { }
↑ ↑

3 2,1, 2, 1 4,3,2,1 16
{ } { }
↑ ↑

Using DFT method

𝑋3 (𝑘) = 𝑋1 (𝑘)𝑋2 (𝑘)
𝑋1 (𝑘) = 2 + 𝑊4𝑘 + 2𝑊42𝑘 + 𝑊43𝑘
𝑋2 (𝑘) = 1 + 2𝑊4𝑘 + 3𝑊42𝑘 + 4𝑊43𝑘
𝑋3 (𝑘) = 𝑋1 (𝑘)𝑋2 (𝑘) = (2 + 𝑊4𝑘 + 2𝑊42𝑘 + 𝑊43𝑘 )(1 + 2𝑊4𝑘 + 3𝑊42𝑘 + 4𝑊43𝑘 )

62
 Prepared by Dr.Harish M S, AIT

𝑋3 (𝑘) = 2 + 4𝑊4𝑘 + 6𝑊42𝑘 + 8𝑊43𝑘 + 𝑊4𝑘 + 2𝑊42𝑘 + 3𝑊43𝑘 + 4𝑊44𝑘 + 2𝑊42𝑘 + 4𝑊43𝑘
+ 6𝑊44𝑘 + 8𝑊45𝑘 + 𝑊43𝑘 + 2𝑊44𝑘 + 3𝑊45𝑘 + 4𝑊46𝑘
We know that 𝑊40 = 𝑊44𝑘 , 𝑊4𝑘 = 𝑊45𝑘 , 𝑊42𝑘 = 𝑊46𝑘
𝑋3 (𝑘) = 2 + 4𝑊4𝑘 + 6𝑊42𝑘 + 8𝑊43𝑘 + 𝑊4𝑘 + 2𝑊42𝑘 + 3𝑊43𝑘 + 4𝑊40 + 2𝑊42𝑘 + 4𝑊43𝑘 + 6𝑊40
+ 8𝑊4𝑘 + 𝑊43𝑘 + 2𝑊40 + 3𝑊4𝑘 + 4𝑊42𝑘
𝑋3 (𝑘 ) = 14 + 16𝑊4𝑘 + 14𝑊42𝑘 + 16𝑊43𝑘
14,16,14,16
𝑥 3 (𝑚 ) = { }
↑
Problem: Given 𝑥(𝑛) = [1,2,3,4] and ℎ(𝑛) = [1,2,2], compute
i. Circular convolution
ii. Linear convolution
iii. Linear convolution using circular convolution
Solution: 𝑥(𝑛) = [1,2,3,4] and ℎ(𝑛) = [1,2,2, 0]
i. Circular convolution
𝑁−1

𝑥 (𝑛) ⊛ ℎ(𝑛) = 𝑥3 (𝑚) = ∑ 𝑥(𝑛)ℎ((𝑚 − 𝑛))𝑁 0≤𝑚 ≤𝑁−1

𝑛=0
3

𝑥3 (𝑚) = ∑ 𝑥(𝑛)ℎ((𝑚 − 𝑛))4 0≤𝑚≤3

𝑛=0

𝑥3 (𝑚) = 𝑥(0)ℎ((𝑚))4 + 𝑥 (𝑛)ℎ((𝑚 − 1))4 + 𝑥(𝑛)ℎ((𝑚 − 2))4 + 𝑥(𝑛)ℎ((𝑚 − 3))4

𝑥3 (𝑚) = 𝑥(0)ℎ(4 + 𝑚) + 𝑥(𝑛)ℎ(3 + 𝑚) + 𝑥 (𝑛)ℎ(2 + 𝑚) + 𝑥(𝑛)ℎ(1 + 𝑚)
𝑥3 (0) = 𝑥(0)ℎ(4 ) + 𝑥(𝑛)ℎ(3 ) + 𝑥(𝑛)ℎ(2 ) + 𝑥 (𝑛)ℎ(1 )
𝑥3 (0) = 𝑥(0)ℎ(0 ) + 𝑥(𝑛)ℎ(3 ) + 𝑥(𝑛)ℎ(2 ) + 𝑥 (𝑛)ℎ(1 )
𝑥3 (0) = 1 × 1 + 2 × 0 + 3 × 2 + 4 × 2 = 15
𝑥3 (1) = 𝑥 (0)ℎ(5) + 𝑥(𝑛)ℎ(4) + 𝑥(𝑛)ℎ(3) + 𝑥 (𝑛)ℎ(2)
𝑥3 (1) = 𝑥 (0)ℎ(1) + 𝑥(𝑛)ℎ(0) + 𝑥(𝑛)ℎ(3) + 𝑥 (𝑛)ℎ(2)
𝑥3 (1) = 11 × 2 + 2 × 1 + 3 × 0 + 4 × 2 = 12
𝑥3 (2) = 𝑥 (0)ℎ(6) + 𝑥(𝑛)ℎ(5) + 𝑥(𝑛)ℎ(4) + 𝑥 (𝑛)ℎ(3)
𝑥3 (2) = 𝑥 (0)ℎ(2) + 𝑥(𝑛)ℎ(1) + 𝑥(𝑛)ℎ(0) + 𝑥 (𝑛)ℎ(3)
𝑥3 (2) = 11 × 2 + 2 × 2 + 3 × 1 + 4 × 0 = 9
𝑥3 (3) = 𝑥 (0)ℎ(7) + 𝑥(𝑛)ℎ(6) + 𝑥(𝑛)ℎ(5) + 𝑥 (𝑛)ℎ(4)

63
 Prepared by Dr.Harish M S, AIT

𝑥3 (3) = 𝑥 (0)ℎ(3) + 𝑥(𝑛)ℎ(2) + 𝑥(𝑛)ℎ(1) + 𝑥 (𝑛)ℎ(0)

𝑥3 (3) = 11 × 0 + 2 × 2 + 3 × 2 + 4 × 1 = 14
ii. Linear convolution 𝑥(𝑛) = [1,2,3,4] and ℎ(𝑛) = [1,2,2, ]
∞

𝑦 ( 𝑛 ) = 𝑥 (𝑛 ) ∗ ℎ (𝑛 ) = ∑ 𝑥 (𝑘 )ℎ(𝑛 − 𝑘 ) −∞ ≤𝑛 ≤∞
𝑘=−∞

Number of samples in 𝑦(𝑛) is 𝑁1 + 𝑁2 − 1 = 6

Starting point of 𝑦(𝑛) is 𝑦𝑙 = 𝑥𝑙 + ℎ𝑙 = 0 + 0 = 0
Terminating point of 𝑦(𝑛) is 𝑦ℎ = 𝑥ℎ + ℎℎ = 3 + 2 = 5
3

∴ 𝑦 (𝑛 ) = ∑ 𝑥 (𝑘 )ℎ(𝑛 − 𝑘 ) 0≤𝑛≤5
𝑘=0

𝑦(𝑛) = 𝑥(0)ℎ(𝑛) + 𝑥(1)ℎ(𝑛 − 1) + 𝑥(2)ℎ(𝑛 − 2) + 𝑥 (3)ℎ(𝑛 − 3)

𝑦(0) = 𝑥 (0)ℎ(0) + 𝑥(1)ℎ(−1) + 𝑥(2)ℎ(−2) + 𝑥(3)ℎ(−3) = 1 × 1 + 2 × 0 + 3 × 0 + 4 × 0
=1
𝑦(1) = 𝑥(0)ℎ(1) + 𝑥(1)ℎ(0) + 𝑥 (2)ℎ(−1) + 𝑥 (3)ℎ(−2) = 1 × 2 + 2 × 1 + 3 × 0 + 4 × 0
=4
𝑦(2) = 𝑥 (0)ℎ(2) + 𝑥(1)ℎ(1) + 𝑥(2)ℎ(0) + 𝑥 (3)ℎ(−1) = 1 × 2 + 2 × 2 + 3 × 1 + 4 × 0 = 9
𝑦(3) = 𝑥(0)ℎ(3) + 𝑥(1)ℎ(2) + 𝑥(2)ℎ(1) + 𝑥(3)ℎ(0) = 1 × 0 + 2 × 2 + 3 × 2 + 4 × 1 = 14
𝑦(4) = 𝑥(0)ℎ(4) + 𝑥(1)ℎ(3) + 𝑥(2)ℎ(2) + 𝑥(3)ℎ(1) = 1 × 0 + 2 × 0 + 3 × 2 + 4 × 2 = 14
𝑦(5) = 𝑥(0)ℎ(5) + 𝑥(1)ℎ(4) + 𝑥 (2)ℎ(3) + 𝑥(3)ℎ(2) = 1 × 0 + 2 × 0 + 3 × 0 + 4 × 2 = 8
1,4,9,14,14,8
∴ 𝑦 (𝑛 ) = [ ]
↑
iii. Linear convolution using circular convolution𝑥(𝑛) = [1,2,3,4] and ℎ(𝑛) = [1,2,2, ]
∞

𝑦 ( 𝑛 ) = 𝑥 (𝑛 ) ∗ ℎ (𝑛 ) = ∑ 𝑥 (𝑘 )ℎ(𝑛 − 𝑘 ) −∞ ≤𝑛 ≤∞
𝑘=−∞

For the linear convolution using circulation convolution, we have to perform 𝑁 ≥ 𝑁1 +

𝑁2 − 1 = 4 + 3 − 1 = 6 point circulation
𝑋3 (𝑘) = 𝑋 (𝑘)𝐻(𝑘)
𝑋(𝑘) = 1 + 2𝑊6𝑘 + 3𝑊62𝑘 + 4𝑊63𝑘
𝐻 (𝑘) = 1 + 2𝑊6𝑘 + 2𝑊62𝑘
𝑋3 (𝑘) = 𝑋(𝑘)𝐻 (𝑘 ) = (1 + 2𝑊6𝑘 + 3𝑊62𝑘 + 4𝑊63𝑘 )(1 + 2𝑊6𝑘 + 2𝑊62𝑘 )

64
 Prepared by Dr.Harish M S, AIT

𝑋3 (𝑘) = 1 + 2𝑊6𝑘 + 2𝑊62𝑘 + 2𝑊6𝑘 + 4𝑊62𝑘 + 4𝑊63𝑘 + 3𝑊62𝑘 + 6𝑊63𝑘 + 6𝑊64𝑘 + 4𝑊63𝑘
+ 8𝑊64𝑘 + 8𝑊65𝑘
1,4, 9,14, 14, 8
𝑥 3 (𝑚 ) = [ ]
↑
2𝜋𝑛 2𝜋𝑛
Problem: Determine the N-point circular convolution of 𝑥1 (𝑛) = 𝑐𝑜𝑠 and 𝑥2 (𝑛) = sin
𝑁 𝑁

Solution: 𝑥1 (𝑛) ⊛ 𝑥2 (𝑛) = 𝑥3 (𝑚) = ∑𝑁−1

𝑛=0 𝑥1 (𝑛 )𝑥2 ((𝑚 − 𝑛 ))𝑁 0≤𝑚≤𝑁−1

𝑥3 (𝑚) = 𝐼𝐷𝐹𝑇{𝑋3 (𝑘)} = 𝐼𝐷𝐹𝑇{ 𝑋1 (𝑘)𝑋2 (𝑘 )}

𝑁 𝑁
𝑋1 (𝑘) = 𝛿 (𝑘 − 1) + 𝛿(𝑘 − 𝑁 + 1)
2 2
𝑁 𝑁
𝑋2 (𝑘) = 𝛿(𝑘 − 1) − 𝛿(𝑘 − 𝑁 + 1)
2𝑗 2𝑗
𝑋3 (𝑘) = 𝑋1 (𝑘)𝑋2 (𝑘)
𝑁 𝑁 𝑁 𝑁
= { 𝛿 (𝑘 − 1) + 𝛿 (𝑘 − 𝑁 + 1)} { 𝛿 (𝑘 − 1) − 𝛿(𝑘 − 𝑁 + 1)}
2 2 2𝑗 2𝑗
𝑁 𝑁
𝑋3 (𝑘) = × {𝛿 (𝑘 − 1) − 𝛿(𝑘 − 𝑁 + 1)}
2 2𝑗
𝑁 2𝜋𝑛
𝑥 3 (𝑚 ) = sin
2 𝑁

65