Digital Signal Processing: (Part-1)

Digital Signal Processing
Chapter-4:
Discrete Fourier Transform
(DFT)
(Part-1)
Dr. Anjaneyulu Pattem

4.1 Discrete Fourier Series (DFS)
4.1.1 Definition
4.1.2 Examples
4.2 Discrete Fourier Transform (DFT)
4.2.1 Definition
4.2.2 Examples
4.3 Properties of DFT
4.3.1. Periodicity, Linearity and Symmetries
4.3.2 Circular shift
4.3.3 Time reversal
4.3.4 Time shifting
4.3.5 Frequency shifting
4.3.6 Multiplication of two DFTs and Convolution
4.3.7 Circular Convolution
4.3.8 Correlation
2
Introduction
Fourier series and Fourier transforms are defined for continuous

signals in periodic and aperiodic nature respectively.
There is a difference in between analog and discrete signals.
In analog signals the range of frequencies is from -∞ to + ∞, where
as in the case of a discrete signal, the frequency range is from –π to
+π.
Therefore, in order to apply Fourier series and Fourier transforms
theory to a discrete finite length signal, this signal is made into a
format, considering range of frequencies, and then definition for
Fourier series and Fourier transforms are obtained.
Obtaining definitions for Fourier series and Fourier transforms
for a finite length discrete signal is described in the following
sections.
3
A signal x(n) of finite length (L) is made periodic in N, by

periodically repeating x(n), then Fourier series theory can be
applied.
Thus if Fourier coefficients are obtained from a periodic signal
in the transformation, then periodic signal should be obtained
from the Fourier coefficients in the inverse transformation.
This is possible when periodicity, N, of the signal, is made larger
than the length of the signal, L, as shown in the following figure.
If N is less than L, then x(n) can’t be recovered from the
coefficients, X(k), since samples are lost in this case, as shown in
the following figure.
Nature of x(n) and xp(n) for the conditions of N>L and N<L are
illustrated in the figure.
4
5
A discrete periodic signal can be represented in discrete Fourier

series in terms of summation of complex exponentials given as
where the complex exponentials are
These exponentials can be shown as periodic as given below:
6
Obtaining DFS coefficients
DFS coefficients, Xp (k), from periodic sequence, xp(n), can be

obtained as given below:
xp(n) is given as
Multiplying both sides with exponentials in the above equation,
`
7
DFS
Rearranging the right handed term in the above equation,
The term can be shown as
Thus when k-r=0, or k=r, the DFS coefficients, X(k) are

obtained as
Or
8
4.1.1 Definition
It can be noted that DFS coefficients are periodic in N as shown

in the following expression:
Now the DFS pair is given as
9
4.1.2: Examples Example-1
Calculate DFS coefficients for the periodic signal
where
Solution: (consider nature of impulse signal)

By definition, DFS coefficients for the periodic signal are given
as
10
DFT can be obtained by sampling Fourier transform of a finite

length signal, at frequencies, ωk = (2 πk/N), as given in the
following sequence of equations,
FT of signal:
DFT coefficients are obtained, when FT is sampled at
ωk= (2 πk/N),
x(n) whose length is L, and periodic in N.
11
4.2.1 DFT Definition
Sequence x(n) is obtained from the coefficients, X(k) similar to

DFS pair, and is given as
Thus the set of coefficients X(k) is called as DFT,
And the expression for sequence, x(n) is called as IDFT.
12
4.2.1 DFT Definition
Definition of DFT pair:
where WN is called as twiddle factor, which is an exponential

given by
13
DFT Pair in Matrix Form
14
Values of Twiddle Factors
Example:(prop.6)
WN calculated
For WN kN
WN kN = e (-j2π/N) kN
= e (-j2π)k
= (1)k =1,
since e (-j2π) =1
WN kN = 1
15
Example-2
Calculate DFT for the sequence

Solution: using
16
Twiddle factors
17
4.3 Properties of DFT
Definitions of DFT pair:
18
4.3.1. Periodicity and Linearity
Periodicity
Linearity
19
Circular Shift
x(n) and xp(n) are related as
Now a new signal xp’(n) is obtained from xp(n)
Then new signal, x’(n) and original signal, x(n) are related as
20
Circular Shift
For example k=2, N=4, the new sequence is given as
And the values of the new signal in terms of x(n) are obtained as
The above values can be obtained by representing x(n) on a

circle, and then shifting the circle by k units.
21
Graphical representation of Circular Shift
This circular shift is identified from the two circles shown in the
bottom (figure-e) of the following figure.
22
Graphical representation of Circular Shift
23
Symmetric sequences
For circularly even symmetric
For finite signals circularly odd symmetric
Time reversal
24
symmetry
Equivalent definitions for periodic signals are given as
25
Symmetry properties of DFT
For complex sequence and DFT coefficients,
Real and imaginary parts of coefficients and sequences are given

as
26
symmetry
For real valued sequences
Real and even sequences:
27
symmetry
Real and odd sequences:
Purely imaginary sequences:
28
symmetry
29
4.3.1. Multiplication of two DFTs and
Circular Convolution
DFTs of two sequences x1(n) and x2(n0 are given as
Now multiplication of the two DFTs is, let it be, X3(k), given as
Inverse DFT, x3(n) is obtained from X3(k) as given below:
30
IDFT of DFT X3(k) is given as
Rearranging the three exponentials in one term and simplifying
31
With substitution of
And from the power series equation,
When l=m-n, then x3(n) is obtained as
RHS of the equation is similar to convolution, and is called as

Circular convolution.
32
Example-3
Calculate circular convolution of the two sequences.
Solution: by definition
33
Example-3 graphical calculation
34
Example-3
35
Example-3
36
Example-4: Graphical calculation
37
38
Time reversal
39
Time reversal
Proof:
40
Circular time shift
Proof:
41
Circular time shift
42
Circular frequency shift
similar to time shift, frequency shift can be proved changing the

roles of time and frequency.
43
Complex conjugate properties
It can be proved similar to the following

IDFT of X*(k) is obtained as x*(N-n)
44
Circular Correlation
If the DFTs are defined for x(n) and y(n),
Then
Proof: circular correlation is given as
45
Circular Correlation
It is represented as
Also it is in similar to circular convolution. Hence proof of

circular convolution can be applied for proof of circular
correlation.
Thus circular correlation is given as
46
Multiplication of two sequencies
If
And
Then
Proof can be shown based on circular convolution and from

changing the roles of time and frequency.
47
Parsevals theorem
For complex valued sequences x(n) and y(n)
then
48
Parsevals theorem
It can be shown that
And also
Then rxy(l) is obtained
through IDFT as
Evaluating the above at l=0, proves the theorem.

when
49
50

Digital Signal Processing: (Part-1)

Uploaded by

Copyright:

Available Formats

Digital Signal Processing: (Part-1)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Digital Signal Processing: (Part-1)

Uploaded by

Copyright:

Available Formats

Digital Signal Processing

Dr. Anjaneyulu Pattem

Fourier series and Fourier transforms are defined for continuous

A signal x(n) of finite length (L) is made periodic in N, by

A discrete periodic signal can be represented in discrete Fourier

where the complex exponentials are

These exponentials can be shown as periodic as given below:

DFS coefficients, Xp (k), from periodic sequence, xp(n), can be

Multiplying both sides with exponentials in the above equation,

Rearranging the right handed term in the above equation,

The term can be shown as

Thus when k-r=0, or k=r, the DFS coefficients, X(k) are

It can be noted that DFS coefficients are periodic in N as shown

Now the DFS pair is given as

Calculate DFS coefficients for the periodic signal

Solution: (consider nature of impulse signal)

DFT can be obtained by sampling Fourier transform of a finite

x(n) whose length is L, and periodic in N.

Sequence x(n) is obtained from the coefficients, X(k) similar to

Thus the set of coefficients X(k) is called as DFT,

And the expression for sequence, x(n) is called as IDFT.

Definition of DFT pair:

where WN is called as twiddle factor, which is an exponential

Calculate DFT for the sequence

Definitions of DFT pair:

x(n) and xp(n) are related as

Now a new signal xp’(n) is obtained from xp(n)

For example k=2, N=4, the new sequence is given as

The above values can be obtained by representing x(n) on a

For circularly even symmetric

For finite signals circularly odd symmetric

Equivalent definitions for periodic signals are given as

For complex sequence and DFT coefficients,

Real and imaginary parts of coefficients and sequences are given

For real valued sequences

Real and even sequences:

Real and odd sequences:

Purely imaginary sequences:

Inverse DFT, x3(n) is obtained from X3(k) as given below:

IDFT of DFT X3(k) is given as

Rearranging the three exponentials in one term and simplifying

And from the power series equation,

When l=m-n, then x3(n) is obtained as

RHS of the equation is similar to convolution, and is called as

Calculate circular convolution of the two sequences.

similar to time shift, frequency shift can be proved changing the

It can be proved similar to the following

If the DFTs are defined for x(n) and y(n),

Proof: circular correlation is given as

Also it is in similar to circular convolution. Hence proof of

Thus circular correlation is given as

Proof can be shown based on circular convolution and from

For complex valued sequences x(n) and y(n)

It can be shown that

Evaluating the above at l=0, proves the theorem.

You might also like