Digital Signal Processing

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering

National Institute of Technology Andhra Pradesh
Tadepalligudem, Andhra Pradesh
India

Jan 15, 2023

Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Lecture #1: Frequency Domain Representation of Signals

References:

Oppenheim and Schafer, Discrete-time Signal Processing , [Chapter 8]

Proakis and Monolakis Digital Signal Processing : Principles, Algorithms and

Applications, [Chapter 6]

Sanjit K. Mitra, Digital Signal Processing, A Computer based Approach,

[Chapter 3]

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Outline of the lecture

Discrete-Time Fourier Transform (DTFT)

Discrete-Time Fourier Series (DTFS)

Discrete-Fourier Transform (DFT)

Circular Shifting and Circular Convolution

Properties of DFT
Applications of DFT
Linear Convolution
Filtering of long data sequences
Frequency domain filtering
Spectral Analysis using DFT
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Outline

1 Discrete-Time Fourier Transform

2 Discrete-Time Fourier Series

3 Discrete Fourier Transform

4 Circular Shifting and Circular Convolution

5 Properties of DFT

6 Applications of DFT

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete-Time Fourier Transform

Consider a discrete-time signal x[n]. The frequency domain

representation of x[n] is given as
∞
X
X (e jω ) = x[n]e −jωn
n=−∞

X (e jω ) is a complex function of a continuous variable ω. So we need

to plot real part Xre (e jω ) = Re{X (e jω )} and imaginary part
Xim (e jω ) = Im{X (e jω )} with respect to ω separately.

In practice, we usually sketch the magnitude |X (e jω )| and phase

Θ(ω) = ∠X (e jω ) with respect to ω separately. These are known as
magnitude spectrum and phase spectrum of the sequence x[n]
respectively.

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete-Time Fourier Transform

X (e jω ) is periodic with period 2π. Therefore, it is sufficient to
specify DTFT X (e jω ) over any interval of 2π. We usually consider
an interval of 0 ≤ ω < 2π or −π ≤ ω < π.

If the sequence x[n] is real valued, then X (e jω ) shows Hermitian

symmetry i.e. magnitude is an even function and phase is an odd
function of ω.

In this case, we usually consider an interval of 0 ≤ ω < π only, since

we can determine the magnitude and phase for the interval
−π ≤ ω < 0 using the values in 0 ≤ ω < π.
The sequence x[n] can be obtained using inverse discrete-time
Fourier transform (IDTFT) as
Z π
1
x[n] = X (e jω )e jωn dω
2π −π
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete-Time Fourier Transform

Example 1 x[n] = δ[n]
∞
X
X (e jω ) = δ[n]e −jωn = 1
n=−∞
n
Example 2 x[n] = a u[n] for |a| < 1
∞
X
X (e jω ) = an u[n]e −jωn
n=−∞
X∞
n −jωn
= a e
n=0
X∞
= (ae −jω )n
n=0
1
=
1 − ae −jω
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete-Time Fourier Transform

We can plot the magnitude and phase spectrum of the signal in the
second example using MATLAB. (a = 0.5)

Figure: DTFT (Frequency domain representation)

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Convergence Condition

X (e jω ) involves summation over infinite values, the infinite series

may or may not converge for all x[n]. DTFT of a sequence x[n] is
said to exist if the series converges in some sense.

Uniform Convergence : Let us define a partial sum

N
X
XN (e jω ) = x[n]e −jωn
n=−N

For uniform convergence of X (e jω ), we must have

LimN→∞ XN (e jω ) = X (e jω ) for all ω

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Uniform Convergence

The condition for uniform convergence of X (e jω ) is that the

sequence x[n] must be absolutely summable.
∞
X
|x[n]| < ∞
n=−∞

We can show that if the sequence x[n] is an absolutely summable

sequence, DTFT X (e jω ) converges uniformly for all values of ω.
This is a sufficient condition for the existence of DTFT.

Most of the signals encountered in practice are of finite duration and

finite amplitude values. These sequences are absolutely summable
and their DTFT exist (converge uniformly)

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Mean-Square Convergence
Some sequences may not be absolutely summable but may be square
summable i.e. sequences with finite energy
∞
X
|x[n]|2 < ∞
n=−∞

For such sequences, DTFT converges in the mean-square sense, i.e.

the absolute value of the error E (ω) = X (e jω ) − XN (e jω ) is not zero
for all ω.

However, for mean square convergence, the total energy of the error
E (ω) must approach zero as the N goes to ∞.
Z π
LimN→∞ |XN (e jω ) − X (e jω )|2 dω = 0
π
jω
However, X (e ) is no longer guaranteed to be bounded for such
sequences.
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Mean-Square Convergence (Example)

Consider a sequence
(
sin(ω0 n)
πn −∞ < n < ∞, n ̸= 0
x[n] = ω0
π n=0
This is a finite energy sequence (square summable). We can show
that the energy of the sequence is ωπc . However. it is not absolutely
summable.
The DTFT of the sequence x[n] is given as
(
1 0 ≤ ω ≤ ω0
X (e jω ) =
0 ω0 < ω ≤ π
Now, consider the finite sum
N
X sin(ω0 n) jωn
XN (e jω ) = e
πn
n=−N
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Mean-Square Convergence (Example)

XN (e jω ) does not converge to X (e jω ) uniformly for all values of ω

but converges to X (e jω ) in the mean square sense.

The number of ripples increase as N increases, with the height of the

largest ripple remaining same for all values of N. (See next slide)

As N tends to infinity, the following condition holds indicating mean

square convergence
Z π
LimN→∞ |XN (e jω ) − X (e jω )|2 dω = 0
π

The oscillatory behavior of XN (e jω ) approximating X (e jω ) in the

mean square sense at the point of discontinuity is called as Gibbs
Phenomenon.

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Mean-Square Convergence (Example)

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete-Time Fourier transform

The DTFT can also be defined for a certain class of signals which
are neither absolutely summable nor square summable.

For example constant sequence x[n] = 1, unit step sequence

x[n] = u[n], exponential sequence x[n] = e jω0 n and sinusoidal
sequence x[n] = cos(ω0 n)

For such sequences, DTFT representation always include Dirac delta

function δ(ω). However, such DTFTs do not converge in the usual
sense and are not continuous functions of ω.

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete-Time Fourier transform

Example - Consider x[n] = e jω0 n − π ≤ ω0 ≤ π

The given sequence is neither absolutely summable, nor square

summable. However, its DTFT can be given using δ(ω) as
∞
X
X (e jω ) = 2πδ(ω − ω0 + 2πk)
k=−∞

X (e jω ) is a periodic function of ω with period 2π and is called a

periodic impulse train. Using, inverse DTFT we can easily show that
x[n] is indeed a complex exponential. Try that

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Common DTFT Pairs

∞
X
δ[n] ←→ 2πδ(ω + 2πk)
k=−∞
∞
1 X
u[n] ←→ + πδ(ω + 2πk)
1 − e −jω
k=−∞
∞
X
e jω0 n ←→ 2πδ(ω − ω0 + 2πk)
k=−∞
1
an u[n], (|a| < 1) ←→
1 − ae −jω
1
(n + 1)an u[n], (|a| < 1) ←→
(1 − ae −jω )2

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DTFT

The following DTFT properties are useful in digital signal processing

applications. We will use the following DTFT pairs.

x[n] ←→ X (e jω )
y [n] ←→ Y (e jω )

Linearity : For arbitrary constants α and β

αx[n] + βy [n] ←→ αX (e jω ) + βY (e jω )

Time Reversal :
x[−n] ←→ X (e −jω )

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DTFT

Time Shifting DTFT of a delayed sequence (n0 integer)

x[n − n0 ] ←→ e jωn0 X (e jω )

Frequency shifting

e jω0 n x[n] ←→ X e j(ω−ω0 )

Differentiation in Frequency domain

dX (e jω )
nx[n] ←→ j
dω
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DTFT
Convolution DTFT of the convolution sum of two sequences is given
by the product of their DTFTs.
x[n] ∗ y [n] ←→ X (e jω )Y (e jω )
Modulation DTFT of the product of two sequences is given by the
convolution integral of their DTFTs.
Z π
1
x[n]y [n] ←→ X (e jθ )Y (e j(ω−θ) )dθ
2π −π
Parseval’s Theorem DTFT of the sum of the sample-by-sample
product of two sequences is given by an integral of the product of
their DTFTs.
∞ Z π
X 1
x[n]y ∗ [n] ←→ X (e jω )Y ∗ (e jω )dω
n=−∞
2π −π

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Energy Density Spectrum

The total energy of a finite energy signal can be given as
∞ Z π
X 1
Ex = |x[n]|2 = |X (e jω )|2 dω
n=−∞
2π −π

The quantity
Sxx (e jω ) = |X (e jω )|2
is called the Energy density spectrum of the sequence. The energy
of the sequence can be obtained by integrating the area under the
curve in the range −π ≤ ω ≤ π.
Example The energy of a causal exponential sequence
x[n] = an u[n] |a| < 1 can be computed as
∞ Z π  2
X
2 1  1 
Ex = |x[n]| = 
jω
 dω
n=−∞
2π −π
 1 − ae 

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Symmetry Properties of DTFT

x[n] = xreal [n] + jximag [n] ←→ X (e jω ) = Xreal (e jω ) + jXimag (e jω )

The following symmetry relations are useful
x[−n] ←→ X (e −jω )
x ∗ [n] ←→ X ∗ (e −jω )
x ∗ [−n] ←→ X ∗ (e jω )
 
1
xreal [n] ←→ Xcs (e jω ) = X (e jω ) + X ∗ (e −jω )
2
 
1
jximag [n] ←→ Xca (e jω ) = X (e jω ) − X ∗ (e −jω )
2
 
1 ∗
xcs [n] = x[n] + x [−n] ←→ Xreal (e jω )
2
 
1 ∗
xca [n] = x[n] − x [−n] ←→ jXimag (e jω )
2
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Symmetry Properties for Real sequences

The following symmetry relations are useful
x[−n] ←→ X (e −jω )
 
1
xev [n] = x[n] + x[−n] ←→ Xreal (e jω )
2
 
1
xodd [n] = x[n] − x[−n] ←→ jXimag (e jω )
2
X (e jω ) shows Hermitian symmetry i.e. magnitude and real parts are
even functions and phase and imaginary parts are odd functions of ω.
X (e jω ) = X ∗ (e −jω )
Xreal (e ) jω
= Xreal (e −jω )
Ximag (e jω ) = −Ximag (e −jω )
|X (e jω )| = |X (e −jω )|
∠X (e jω ) = −∠X (e −jω )
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Outline

1 Discrete-Time Fourier Transform

2 Discrete-Time Fourier Series

3 Discrete Fourier Transform

4 Circular Shifting and Circular Convolution

5 Properties of DFT

6 Applications of DFT

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Representation of Periodic Sequences

Consider a periodic sequence x̃[n] with period N. We can write as

x̃[n] = x̃[n + rN] for all any integer r , n

Any periodic sequence can be written as a weighted combination of

harmonically related complex exponential sequences. i.e. frequencies
of the exponential sequences are integer multiple of fundamental
frequency 2π/N

We can represent the periodic sequence x̃[n] as

N−1 N−1
1 X 1 X 2π
x̃[n] = X̃ [k]ek [n] = X̃ [k]e j N kn
N N
k=0 k=0

Note We will denote periodic signals by˜over the symbols.

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete-Time Fourier Series

Note that, ek [n] is periodic with period N

ek [n] = ek+N [n] any integer k, n

Only N harmonically related complex exponential sequences are

required for the discrete-time Fourier series (DTFS) representation
of a periodic sequence

Any set of N, periodic complex exponential signals, can be chosen.

However, we usually use 0 ≤ k ≤ N − 1. The DTFS of the periodic
sequence x̃[n] is given as
N−1 N−1
1 X 2π 1 X
x̃[n] = X̃ [k]e j N kn = X̃ [k] WN−kn
N N
k=0 k=0

2π
where we use the notation WN = e j N

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete-Time Fourier Series

X̃ [k] are called the DTFS coefficients of the sequence x̃[n]. X̃ [k]
can be determined as
N−1 N−1
2π
X X
X̃ [k] = x̃[n]e −j N kn = x̃[n]WNkn
n=0 n=0

This is known as the analysis equation. X̃ [k] is also periodic with

period N.

The proof of the above equation is quite straight forward using the
orthogonality of the set of complex exponential sequences.
N−1
(
1 X ∗ 1 k − r = mN for integer m
ek [n]er [n] =
N n=0 0 otherwise

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete Time Fourier Series

To summarize, DTFS analysis and synthesis equations are written as

N−1
1 X
x̃[n] = X̃ [k]WN−kn Synthesis Equation
N
k=0
N−1
X
X̃ [k] = x̃[n]WNkn Analysis Equation
n=0

2π
where WN = e j N

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DTFS of a Periodic Impulse Train

Consider a periodic impulse train x̃[n] with period N
∞
X
x[n] = δ[n − rN]
r =−∞

Figure: Periodic Impulse Train

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DTFS of a Periodic Impulse Train

For, one period, signal x̃[n] is simply an impulse signal δ[n]. The
DTFS coefficients can be written as
N−1
X
X̃ [k] = x̃[n]e −j2πkn/N k = 0, 1, . . . , N − 1
n=0
N−1
X
= δ[n]e −j2πkn/N k = 0, 1, . . . , N − 1
n=0
= 1 for k = 0, 1, . . . , N − 1

The DTFS representation of x̃[n] is given as

N−1 N−1
1 X 2π 1 X j 2π kn
x̃[n] = X̃ [k]e j N kn = e N
N N
k=0 k=0

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DTFS of a Periodic Rectangular Pulse Train

Consider a periodic rectangular pulse train x̃[n] with period N as
shown in Fig. below. For, one period, the signal x̃[n] is given as
(
1 for n = 0, 1, 2, 3
x̃p [n] =
0 for n = 4, 5, 6, 7

Figure: Periodic Rectangular Pulse Train

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DTFS of a Periodic Rectangular Pulse Train

The DTFS coefficients can be written as
7
X
X̃ [k] = x̃[n]e −j2πkn/8 k = 0, 1, . . . , 7
n=0
3
X
= e −j2πkn/8
n=0
1 − e −jπk sin(πk/2)
= = e −j3πk/8
1 − e jπk/4 sin(πk/8)
The DTFS representation of x̃[n] is given as
N−1 N−1
1 X j 2π kn 1 X j 2π kn
x̃[n] = X̃ [k]e N = e N
N N
k=0 k=0

The magnitude and phase of X̃ [k] can be plotted using MATLAB.

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DTFS

The following DTFS properties are useful in digital signal processing

applications. We will use the following DTFS pairs. x̃[n] and ỹ [n]
are two periodic sequences with period N.

x̃[n] ←→ X̃ [k]
ỹ [n] ←→ Ỹ [k]

Linearity For arbitrary constants α and β

αx̃[n] + β ỹ [n] ←→ αX̃ [k] + β Ỹ [k]

Duality
X̃ [n] ←→ N x̃[−k]

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DTFS

Time Shifting DTFS of a delayed sequence (m integer)

x̃[n − m] ←→ WNkm X̃ [k]

Frequency shifting

WN−nl x̃[n] ←→ X̃ [k − l]

Periodic Convolution The periodic convolution of two periodic

sequences with perion N is defined as
N−1
X
z̃[n] = x̃[m]ỹ [n − m]
m=0

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DTFS

The periodic convolution z[n] is also periodic with period N.

The periodic convolution of periodic sequences corresponds to

product of the corresponding periodic discrete Fourier series
coefficients
N−1
X
x̃[m]ỹ [n − m] ←→ X̃ [k]Ỹ [k]
m=0

The product of two periodic sequences corresponds to the periodic

convolution of corresponding periodic discrete Fourier series
coefficients
N−1
X
x̃[n]ỹ [n] ←→ X̃ [l]Ỹ [k − l]
l=0

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Symmetry Properties of DTFS

x̃[n] = x̃real [n] + j x̃imag [n] ←→ X̃ [k] = X̃real [k] + j X̃imag [k]
The following symmetry relations are useful

x̃ ∗ [n] ←→ X̃ ∗ [−k]
x̃ ∗ [−n] ←→ X̃ ∗ [k]
 
1
x̃real [n] ←→ X̃cs [k] = X̃ [k] + X̃ ∗ [−k]
2
 
1
j x̃imag [n] ←→ X̃ca [k] = X̃ [k] − X̃ ∗ [−k]
2
 
1 ∗
x̃cs [n] = x̃[n] + x̃ [−n] ←→ X̃real [k]
2
 
1 ∗
x̃ca [n] = x̃[n] − x̃ [−n] ←→ j X̃imag [k]
2
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Symmetry Properties for Real sequences

The following symmetry relations are useful
x̃[−n] ←→ X ∗ [k]
 
1
x̃ev [n] = x̃[n] + x̃[−n] ←→ X̃real [k]
2
 
1
x̃odd [n] = x̃[n] − x̃[−n] ←→ j X̃imag [k]
2
X̃ [k] shows Hermitian symmetry i.e. magnitude and real parts are
even functions and phase and imaginary parts are odd functions of k.
X̃ [k] = X̃ ∗ [−k]
X̃real [k] = X̃real [−k]
X̃imag [k] = −X̃imag [k]
|X̃ [k]| = |X̃ [−k]|
∠X̃ [k] = −∠X̃ [−k]
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Fourier Transform of Periodic Sequences

Periodic sequences are neither absolute summable nor square

summable. So their DTFTs do not converge in the usual sense.

However, introduction of the Dirac delta function δ(ω) allows us to

bring periodic sequences in the framework of DTFT.

DTFT of a periodic sequence is a an impulse train in the frequency

domain with impulse values proportional to the DTFS coefficients.

DTFT of x̃[n] is given as

∞  
jω
X 2π 2π
X̃ (e ) = X̃ [k]δ ω − k
N N
k=−∞

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Fourier Transform of Periodic Sequences

The DTFT X̃ (e jω ) is periodic with period 2π. We can show that
X̃ (e jω ) is the Fourier transform representation of x̃[n] by showing
that the inverse Fourier transform of X̃ (e jω ) is equal to x̃[n] (Try
that)
Example : Consider a periodic impulse train x̃[n] with period N
∞
X
x̃[n] = δ[n − rN]
r =−∞

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing Figure: Periodic Impulse Train
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Fourier Transform of Periodic Sequences

First we need to find the values of DTFS coefficients X̃ [k] of the

periodic sequence x̃[n] and then substituting X̃ [k] values in the
X̃ (e jω ).

We have already shown that X̃ [k] = 1 for all k. So X̃ (e jω ) is

given as
∞  
jω
X 2π 2π
X̃ (e ) = X̃ [k]δ ω − k
N N
k=−∞
∞  
X 2π 2π
= δ ω− k
N N
k=−∞

2π
which is an impulse train in the frequency domain with spacing N .

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Outline

1 Discrete-Time Fourier Transform

2 Discrete-Time Fourier Series

3 Discrete Fourier Transform

4 Circular Shifting and Circular Convolution

5 Properties of DFT

6 Applications of DFT

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Fourier Transform of a Finite Length Signal

Consider a finite length sequence x[n], 0 ≤ n ≤ N − 1. Suppose we
convolve the sequence x[n] with the periodic impulse train p̃[n]
∞
X
p̃[n] = δ[n − rN]
r =−∞

The resulting periodic sequence x̃[n] is given as

x̃[n] = x[n] ∗ p̃[n]
X∞
= x[n − rN]
r =−∞

Now, the Fourier transform of a periodic sequence x̃[n] is given as

∞  
jω
X 2π 2π
X̃ (e ) = X̃ [k]δ ω − k
N N
k=−∞

where X̃ [k] are the DTFS coefficients of x̃[n].

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Fourier Transform of a Finite Length Signal

We can also write the Fourier transform as the multiplication of
DTFTs of x[n] and p̃[n] as
∞  
jω jω jω jω
X 2π 2π
X̃ (e ) = X (e )P̃(e ) = X (e ) δ ω− k
N N
k=−∞
∞    
X 2π j2πk/N 2π
= X e δ ω− k
N N
k=−∞

By comparing the two expression of X̃ (e jω ), we can see that

 
j2πk/N
X̃ [k] = X e = X (e jω )|ω= 2π
N k

Summary : The DTFS coefficients X̃ [k] of a periodic sequence x̃[n]

are equally spaced samples of the DTFT X (e jω ) of a finite length
sequence x[n] obtained by extracting one period of x̃[n]
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Dircrete Fourier Transform (One Interpretation)

Consider an aperiodic sequence x[n] with DTFT X (e jω ). Consider a
periodic sequence x̃[n] whose DTFS coefficients are X̃ [k]. Let X̃ [k]
are equal to the samples of X (e jω ) over one period of 2π at
∆ω = 2π N i.e.
X̃ [k] = X (e jω )|ω= 2π
N k

X̃ [k] are also equal to the samples of X (z) at N equally spaced

samples on the unit circle i.e.

X̃ [k] = X (z)| 2π k
z=e j N

Now, we want to find the periodic sequence x̃[n] whose DTFS

coefficients are X̃ [k]. Using DTFS synthesis equation we can write
N−1
1 X
x̃[n] = X̃ [k]e j2πkn/N
N
k=0
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Dircrete Fourier Transform (One Interpretation)

With some mathematical maipulation we can show that
X∞
x̃[n] = [n − rN]
r =−∞

We see that the samples of the DTFT of an aperiodic sequence x[n]

can be thought of as DTFS coefficients of a periodic sequence x̃[n]
obtained through summing periodic replicas of x[n].

Summary If a sequence x[n] is of finite length L and we take

sufficient number N ≥ L equally spaced samples of the DTFT of
x[n] then x[n] is recoverable from the periodic sequence x̃[n].
Otherwise there will be time aliasing.

In other words, if x[n] is of finit duration L, we don’t need to know

X (e jω ) for all values of ω. If we know N ≥ L samples of X (e jω ), we
can recover x[n] from these samples. These N samples are called the
Discrete Fourier Transform of x[n].
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Relation between DTFT and DTFS

Example We consider a periodic rectangular pulse train x̃[n] with

period N = 8 used in example before. We will try to demonstrate
the relation between the Fourier Series Coefficients and the Fourier
Transform of one Period.

We computed the DTFS coefficients earlier as

sin(πk/2)
X̃ [k] = e −j3πk/8
sin(πk/8)

The periodic signal x̃[n] for one period is given as

(
1 for n = 0, 1, 2, 3
x[n] =
0 for otherwise

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Relation between DTFT and DTFS

Example (Contd.) The DTFT X (e jω ) of x[n] is given as

3
X sin(2ω)
X (e jω ) = e −jωn = e −j3ω/2
n=0
sin(ω/2)

2π 2π
Let us sample the X (e jω ) over one period of 2π at ∆ω = N = 8

sin(πk/2)
X (e jω )|ωk = 2π
N k
= e −j3πk/8
sin(πk/8)

We can see that the samples of the Fourier transform is same as the
Fourier series coefficients of the periodic extension of the signal.

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Relation between samples of DTFT and DTFS coefficients

Figure: Samples of DTFT and DTFS coefficients

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete Fourier Transform (DFT)

Consider a finite length signal x[n] 0 ≤ n ≤ N − 1 of length N. We

construct a periodic extension of the sequence
∞
X
x̃[n] = x[n − rN]
r =−∞
= x[n modulo N]
= x[((n))N ] Notation

The signal x[n] can be extracted from x̃[n] as

(
x̃[n] for n = 0, 1, . . . , N − 1
x[n] =
0 otherwise

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete Fourier Transform (DFT)

The DTFS coefficients X̃ [k] of x̃[n] are given as
N−1
X
X̃ [k] = x[n]e −j2πkn/N
n=0

X̃ [k] is periodic with period N, we extract for one period as

(
X̃ [k] for n = 0, 1, . . . , N − 1
X [k] =
0 otherwise

X [k] is called the discrete Fourier transform (DFT) of the sequence

x[n]. Now X̃ [k] can be written as

X̃ [k] = X [k modulo N]
= X [((k))N ] Notation
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Discrete Fourier Transform (DFT)

The N-point DFT of a finite length sequence x[n] is given as

N−1
X N−1
X
X [k] = x[n]e −j2πkn/N = x[n]WNkn k = 0, 1, . . . , N − 1
n=0 n=0

This is called as Analysis equation, DFT values are equal to the

samples of the DTFT.

The sequence x[n] can be recovered from X [k] using N-point IDFT
(Synthesis equation)
N−1 N−1
1 X 1 X
x[n] = x[n]e j2πkn/N = x[n]WN−kn k = 9, 1, . . . , N − 1
N N n=0
k=0

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DFT Example
Example Consider x[n] = [1 1 1 1 1] is a length N = 5 sequence.
N−1
X
X [k] = x[n]e −j2πkn/N k = 0, 1, . . . , N − 1
n=0
4
X 1 − e −j2πk
= e −j2πkn/4 =
n=0
1 − e −j2πk/5
= 5 for k = 0 and 0 for k = 1, 2, 3, 4

We can show that the DFT coefficients are equal to the one period
of DTFS coefficients of the periodic extension of x[n].

We can also show that the DFT coefficients are equal to the N = 5
equally spaced samples of the DTFT over one period at
ωk = 2π5 k for k = 0, 1, . . . , 4
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DFT Example (contd.)

Figure: Illustration of the DFT

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DFT Example (contd.)

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Figure: Illustration of the DFT
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DFT as a Linear Transform

Consider an N-point (length N) sequence x[n] and its N-point DFT
is given as column vectors

xN = [x[0] x[1] · · · x[N − 2] x[N − 1]T

XN = [X [0] X [1] · · · X [N − 2] X [N − 1]T

We can write the DFT and IDFT equations as Matrix operations

(linear transformation) as

XN = WN xN
−1 1 ∗
xN = WN XN = W XN
N N
The N × N DFT matrix WN is a unitary (orthogonal) matrix i.e.
∗
WN WN = NIN
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DFT as a Linear Transform

The N × N DFT matrix WN is written as

1 1 1 ··· 1
 
1 WN1 WN2 ··· WNN−1 
WN =  .. .. ..
 

. . ··· . 
2(N−1) (N−1)(N−1)
1 WNN−1 WN ··· WN

We can simplify the DFT matrix using the following properties

k+N/2
WN = −WNk for all integer k
WNk+rN = WNk for all integer r , k

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

DFT and IDFT Matrices

The 4 × 4 DFT matrix W4 is given as

 0
W40 W40 W40

W4
W40 W41 W42 W43 
W4 = 
W40

W42 W44 W46 
W40 W43 W46 W49

We can simplify the 4 × 4 DFT matrix as

 
1 1 1 1
1 −j −1 j 
W4 =  
1 −1 1 −j 
1 j −1 −j

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Outline

1 Discrete-Time Fourier Transform

2 Discrete-Time Fourier Series

3 Discrete Fourier Transform

4 Circular Shifting and Circular Convolution

5 Properties of DFT

6 Applications of DFT

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Shift of a Sequence

Consider a finite length sequence x[n], 0 ≤ n ≤ N − 1. The
corresponding periodic sequence x̃[n] formed by periodic extension
of x[n] is given as
∞
X
x̃[n] = x]n − rN] = x[((n))N ]
r =−∞

Suppose we wish to shift this periodic sequence in time as

x̃1 [n] = x̃[n − m]

Now, the finite duration sequence x1 [n] given as

(
x̃1 [n] 0 ≤ n ≤ N − 1
x1 [n] =
0 otherwise
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Shift of a Sequence

Now, what is the relation between x[n] and x1 [n]? x1 [n] does not
correspond to the linear shift of x[n] as both the sequence are
confined in the interval 0 ≤ n ≤ N − 1.

x1 [n] corresponds to the circular-shift of x[n] denoted as

x1 [n] = x[[((n − m))N ]

= x[((n − m) modulo N)]

Circular shift of a finite-duration N-point sequence is equivalent to

the linear shift of its periodic extension.

Circular shift of a sequence of length N by m points in one direction

is equivalent to (N − m) points in other direction.

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Shift of a Sequence

Figure: Circular Shift of a Sequence

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Shift of a Sequence

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing Figure: Circular Shift of a Sequence
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Shift of a Sequence

An N-point sequence is called circularly even if it is symmetric about

point zero on the circle.

x[((N − n))N ] = x[((n))N ] 1≤n ≤N −1

An N-point sequence is called circularly odd if it is antisymmetric

about point zero on the circle.

x[((N − n))N ] = −x[((n))] 1≤n ≤N −1

The circular time reversal of an N-point sequence is obtained by

reversing its samples around the point zero on the circle. (reading
the sequence counterclock wise on circle)

x[((−n))N ] = x[((N − n))N ] 0≤n ≤N −1

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Convolution

Consider the two N-point sequences x1 [n] and x2 [n]. The circular
convolution of the sequences is given as
N−1
X
x3 [n] = x1 [n] ⊛ x2 [n] = x1 [m]x2 [((n − m))N ] 0≤n ≤N −1
N
m=0

It can be shown that the circular convolution of two N-point

sequences is equivalent to the periodic convolution of their periodic
extensions.
N−1
X
x̃3 [n] = x̃1 [m]x̃2 [n − m] 0≤n ≤N −1
m=0

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Convolution (Example)

Consider the two N-point sequences x[ n] and x2 [n] given as

x1 [n] = [2 1 2 1]
x2 [n] = [1 2 3 4]

Find the N = 4 point circular convolution of these sequences.

The algorithm for computing circular convolution yCC [n] for each
n, (0 ≤ n ≤ N − 1) is as follows
S1: Circular time reverse the sequence x2 [m]
S2: Circularly shift the time reversed sequence (clock wise) by n
S3: Multiply the sequence x1 [m] and the sequence in S2 to obtain a
product sequence
S4: Summing the values of the product sequence

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Convolution (Example (Contd))

Now, applying the procedure, the circularly time reversed
x2 [((−m))N ] is given as
x2 [((−m))4 ] = [1 4 3 2]
P3
yCC [0] = m=0 x1 [m]x2 [((−m))4 ] = 14

x2 [(−(m − 1)4 )] = [2 1 4 3]
P3
yCC [1] = m=0 x1 [m]x2 [(−(m − 1))4 ] = 16

x2 [(−(m − 2)4 )] = [3 2 1 4]
P3
yCC [2] = m=0 x1 [m]x2 [(−(m − 2))4 ] = 14

x2 [(−(m − 3)4 )] = [4 3 2 1]
P3
yCC [3] = m=0 x1 [m]x2 [(−(m − 1))4 ] = 16

yCC [n] = [14 16 14 16]

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Outline

1 Discrete-Time Fourier Transform

2 Discrete-Time Fourier Series

3 Discrete Fourier Transform

4 Circular Shifting and Circular Convolution

5 Properties of DFT

6 Applications of DFT

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DFT

The following DFT properties are useful in digital signal processing

applications. We will use the following DFT pairs. x[n] and y [n] are
two causal sequences with length N.

x[n] ←→ X [k]
y [n] ←→ Y [k]

Linearity For arbitrary constants α and β

αx[n] + βy [n] ←→ αX [k] + βY [k]

Duality
X [n] ←→ Nx[((−k))N ] 0≤k ≤N −1

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DFT

Circular Time Shifting

x[((n − m))N ] ←→ WNkm X [k]

Circular Frequency shifting

WNln x[n] ←→ X [((k − l))N ]

Periodicity The DFT coefficients X [k] are periodic with period N

X [k + rN] = X [k] 0≤k ≤N −1 for all integer r

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Properties of DFT
N-point Circular convolution The circular convolution of two
sequences corresponds to product of the corresponding DFTs
N−1
X
x[n] ⊛ y [n] = x[m]y [((n − m))N ] ←→ X [k]Y [k]
N
m=0

Modulation The product of two periodic sequences corresponds to

the circular convolution of corresponding DFT sequences
N−1
1 X
x[n]y [n] ←→ X [l]Y [((k − l))N ]
N
l=0

Parseval’s Relation
N−1 N−1
X 1 X
|x[n]|2 = |X [k]|2
n=0
N
k=0
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Symmetry Properties of DTFT

x[n] = xreal [n] + jximag [n] ←→ X [k] = Xreal [k] + jXimag [k]
The following symmetry relations are useful

x ∗ [n] ←→ X ∗ [((−k))N ] = X ∗ [N − k]
x ∗ [((−n))N ] ←→ X ∗ [k]
 
1
xreal [n] ←→ Xcs [k] = X [k] + X ∗ [((−k))N ]
2
 
1
jximag [n] ←→ Xca [k] = X [k] − X ∗ [((−k))N ]
2
 
1 ∗
xcs [n] = x[n] + x [((−n))N ] ←→ Xreal [k]
2
 
1 ∗
xca [n] = x[n] − x [((−n))N ] ←→ jXimag [k]
2
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Symmetry Properties for Real sequences

The following symmetry relations are useful
x[((−n))N ] ←→ X ∗ [k]
 
1
xev [n] = x[n] + x[((−n))N ] ←→ Xreal [k]
2
 
1
xodd [n] = x[n] − x[((−n))N ←→ jXimag [k]
2
X [k] shows Hermitian symmetry i.e. magnitude and real parts are
even functions and phase and imaginary parts are odd functions of k.
X [k] = X ∗ [((−k))N ]
Xreal [k] = Xreal [((−k))N ] = Xreal [N − k]
Ximag [k] = −Ximag [((−k))N ] = −Ximag [N − k]
|X [k]| = |X [((−k))N ]| = |X [N − k]|
∠X [k] = −∠X [((−k))N ] = −∠X [N − k]
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Convolution using Linear Convolution

Consider two finite length sequences x1 [n] and x2 [n] of length N.
The N-point circular convolution is given as
N−1
X
yCC [n] = x1 [n] ⊛ x2 [n] = x1 [m]x2 [((n − m))N ] 0≤n ≤N −1
N
m=0
We can determine the circular convolution as linear convolution of
the two sequences followed by time aliasing. First, we compute the
linear convolution as
∞
X
yLC [n] = x1 [n] ∗ x2 [n] = x1 [m]x2 [n − m]
m=−∞

Compute the periodic extension of yLC [n] and window the result
between 0 ≤ n ≤ N − 1. This will give us the N-point circular
convolution ∞
X
yCC [n] = yLC [n − rN] 0≤n ≤N −1
r =−∞
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Circular Convolution using Linear Convolution

Figure: Circular Convolution using Linear Convolution

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Outline

1 Discrete-Time Fourier Transform

2 Discrete-Time Fourier Series

3 Discrete Fourier Transform

4 Circular Shifting and Circular Convolution

5 Properties of DFT

6 Applications of DFT

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Linear Convolution using DFT

We know that circular convolution in the time domain corresponds to

the multiplication in the DFT domain. Further, circular convolution
can be interpreted as linear convolution followed by time aliasing.

We can combine these two approaches to develop an algorithm for

the linear convolution using DFT method
∞
X
yLC [n] = x1 [n] ∗ x2 [n] = x1 [m]x2 [n − m]
m=−∞

Consider x[n] and h[n] be two finite length causal sequences with
length L and M respectively. We wish to find the linear convolution
of these sequences as
yLC [n] = x[n] ∗ h[n]

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Linear Convolution using DFT

We saw that yCC [n], can be written as periodic repetition of yLC [n]
followed by windowing between 0 ≤ n ≤ N − 1. We can recover
yLC [n] from yCC [n], when there is no overlapping in periodic
repletion of yLC [n] i.e. N ≥ L + M − 1

Algorithm :

S1: Zero pad (Insert zeros) the sequences x[n] and h[n] to make
their length N where N ≥ L + M − 1. Let us denote new sequences
xe [n] and he [n].

S2: Take N point DFT of xe [n] and he [n] as Xe [k] and He [k]

S3 : Multiply Y [k] = He [k]Xe [k] k = 0, 1, · · · , N − 1

S3 : Take N-point IDFT of Y [k] to get yLC [n]

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Linear Convolution using DFT

Figure: Linear Convolution using DFT

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Filtering of Long Data Sequences

Consider FIR filtering as shown in figure below. The input sequence

x[n] is of length K and filter impulse response is of length M.

Figure: Linear FIR Filtering

In some applications, K is very long e.g speech processing by an FIR

filter. This result in significant delay in processing.

In such applications, the approach of linear convolution using DFT is

impractical for real time signal processing.

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Filtering of Long Data Sequences

For such applications, the following approach is used.

Segment the input signal x[n] into blocks of fixed length L

Do convolution of each block xi [n] with h[n] to get output blocks

yi [n] (Use DFT method explained earlier)

Combine all output blocks to get y [n] = x[n] ∗ h[n]

There are two different approaches depending on how we segment

the input sequence and combine the output blocks.

Overlap-Add Method

Overlap-Save Method

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Overlap-Add Method
Key Idea The linear convolution is additive i.e.

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

The input sequence is segmented into non-overlapping blocks of

fixed length L as
∞
X
x[n] = xi [n − iL]
i=0

where xi [n] is the ith block of length L given as

xi [n] = x[n + iN] for n = 0, 1, . . . , N − 1

Then each block xi [n] is filtered (linearly convolved) with h[n] to

compute output block yi [n] using DFT method as explained earlier.
The length of yi [n] is L + M − 1
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Overlap-Add Method

The output blocks yi [n] must be combined appropriately to generate

the desired y [n]
y [n] = x[n] ∗ h[n]
Using the additive property of convolution we can show that
∞
X
y [n] = yi [n − iL]
i=0

where yi [n] = xi [n] ∗ h[n] is the ith output block of length L+M-1

Generate y [n] by overlapping the last M − 1 samples of yi [n] with

the first M − 1 samples of yi+1 [n] and adding the result.

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Overlap-Add Method

Figure: Input Segmentation

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Overlap-Add Method

Figure: Output block combining

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Overlap-Save Method
Key Idea N-point circular convolution of a length N sequence xi [n]
with a length M, (N > M) sequence h[n] will generate ycc,i [n] such
that
(
incorrect for n = 0, 1, . . . , M − 2
yCC ,i [n] =
yLC ,i [n] for n = M − 1, M, . . . , N − 1

The first M − 1 samples of yCC ,i [n] are incorrect and must be

discarded.

The remaining N − M + 1 samples of yCC ,i [n] correspond to the

correct linear convolution and must be saved.
The previous output block yCC ,i−1 [n] must provide these discarded
samples of linear convolution. We get these by appending last M − 1
samples of previous input block xi−1 [m] to the beginning of next
input block xi [n].
V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Overlap-Save Method

The input signal x[n] is segmented into overlapping blocks of length

N = L + M − 1. The last M − 1 samples of i − 1th block overlap
with first M − 1 samples of ith block. For first block, add M − 1
zeros in the beginning.

xi [n] = x[n + i(N − M + 1)] for 0 ≤ n ≤ N − 1

Compute N point circular convolution of xi [n] and h[n] to get yi [n]

of length N = L + M − 1. Now discard the first M − 1 samples of
yi [n] as these give the incorrect result.

Generate y [n] by appending the remaining L samples of each yi [n] to

get the desired output y [n] = x[n] ∗ h[n].

V. Praksh Singh, PhD

Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Overlap-Save Method

Figure: Input Segmentation

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing
Discrete-Time Fourier Transform Discrete-Time Fourier Series Discrete Fourier Transform Circular Shifting and Circular Convolution Properties of DFT

Overlap-Save Method

Figure: Output block combining

V. Praksh Singh, PhD
Department of Electronics & Comunication Engineering National Institute of Technology Andhra Pradesh Tadepalligudem, Andhra Pradesh India
Digital Signal Processing