CAN207 Signals and Systems

Part 2 – Discrete-Time Signals and Systems

Lecture-D5
Discrete Fourier Transform (DFT)

Zhao Wang
Zhao.wang@xjtlu.edu.cn
Room EE322

1
Content
• 1. Definition of DFT
– 1.1 DFT definition
– 1.2 DFT: synthesis and analysis equations
– 1.3 Relationships among CTFT, DTFT and DFT
• 2. Computation of DFT
– 2.1 Computing DFT based on twiddle factor
• 3. DFT Properties
– 3.1 Periodicity
– 3.2 Parseval’s theorem
• 4. Circular Convolution
– 4.1 Circular shift
– 4.2 Circular reversal
– 4.3 Circular convolution
– 4.4 Linear convolution VS circular convolution
2
1.1 From DTFT to DFT
• DTFT is an important tool in digital signal processing, as it
provides the spectral content of a discrete time signal.
– However, the computed spectrum, X(ω) is a continuous function
of ω, and therefore cannot be computed using a computer
– We need a method to compute the spectral content of a discrete
time signal and have a spectrum – actually a discrete function
• A straightforward solution: Simply sample the frequency
variable ω of the DTFT in frequency domain in the [0, 2π]
interval.
– If we want N points in the frequency domain, then we divide ω in
the [0, 2π] interval into N equal intervals.
– Then the discrete values of ω are 0, 2π/N, 2*2π/N, 3*2π/N, …,
(N-1)*2π/N
3
1.1 Discrete Fourier Transform (DFT)
• The simplest relation between a length-N sequence x[n], defined for
0≤n≤N-1, and its DTFT X(ω) is obtained by uniformly sampling
X(ω) on the ω-axis 0≤ω≤2π with
2 k
k  , k  0, 1, ... , N  1
N
• From the definition of DTFT, we thus have
 j 2 k  N  1 j
2 kn

 
X k   X e j
 k  2  k /N
 X  e N    x[n]e N , k  0, 1, ... , N  1
  n0
 
• Using the notation WN  e  j 2 /N , the DFT is usually expressed as
N 1
Twiddle factor
X k    x[n] WNkn , k  0, 1, ... , N  1
n0

4
1.1 Twiddle Factor WN
• The twiddle factor WN is important in DFT
= = [ ] ,0 ≤ ≤ −1

– Complex exponential wheel

Imaginary Imaginary Imaginary
Imaginary

W40 W40 W42 W40

1 Real 1 Real 1 Real

W4 1 W41

1 Real Z-plane Z-plane Z-plane

Imaginary Imaginary

N=4 W4 3 W43

Z-plane N=8 W42 W40

1 Real
W42 W44
W40 1 Real

W4 1 W41

Z-plane Z-plane 5
1.2 Inverse Discrete Fourier Transform (IDFT)
• The IDFT is defined as
N 1 2 kn
1 j
x[n] 
N
 X[ k ]e N , k  0, 1, ... , N  1
k 0

• Using the notation WN  e j 2 /N , the IDFT is usually

expressed as
1 N 1  kn
x[n]  
N k 0
X[ k ]WN , k  0, 1, ... , N  1

• To verify the above expression, we multiply both sides of

/
IDFT equation by and sum the result from n=0
to N-1.

6
1.2 DFT Pair
• The analysis equation
N 1
kn
X k    x[ n ] WN , k  0, 1, ... , N  1
n 0

• The synthesis equation

N 1
1  kn
x[n] 
N
 X[ k ]WN , k  0, 1, ... , N  1
k 0

• The DFT pair is denoted as x[n]  X[k]

7
1.3 CTFT  DTFT  DFT
Time ( ) [ ] [ ]
Domain
CTFT DTFT DFT
Frequency
Domain ( ) ( ) [ ]

8
1.3 DTFT from DFT
• DTFT is a continuous transform. Sampling the DTFT at
regularly spaced intervals around the unit circle gives the
DFT.
• Just like we can reconstruct a continuous time signal from
its samples, DTFT can also be interpolated from its DFT
samples, as long as the number of points N at which DFT
is computed is equal to or larger than the samples of the
original signal.
– That is, given the N-point DFT X[k] of a length-N sequence x[n],
its DTFT X(ω) can be uniquely determined from X[k]

• How?
9
1.3 DTFT from DFT by Interpolation

= [ ]

1
= [ ]

1
= [ ]

−2
11− 1 sin 2
=
−2
1− sin
2 10
1.3 DTFT from DFT by Interpolation cont.
−2
sin
2
= [ ]
−2
sin
2

2
= [ ] Φ( − )

Where Φ =

• This is the desired relation expressing ( ) in terms of X[k];

• Φ is called the interpolating polynomial with:
1, =0
Φ =
0, 1≤ ≤ −1
11
1. Wrap up
• Discrete Fourier Transform
– Analyses equation
– Syntheses equation

• Relationship between DFT and DTFT

– From DTFT to DFT
• Frequency domain sampling  Time domain periodic
– From DFT to DTFT
• Time domain windowing  Frequency domain interpolation

12
2.1 Computing DFT
• For any given k, the DFT is computed by multiplying each
x[n] with each of the complex exponentials WNnk  e  j 2 nk /N
and then adding up all these components
• If, for example, we wish to compute an 8-point DFT, the
complex exponentials are 8 unit vectors placed at equal
distances from each other on the unit circle
Complex exponential wheel

N 1
kn
X k    x[ n ] W N , k  0, 1, ... , N  1
n0

13
Example 1
• Find the DFT of a 4-point sequence
x4[k]={1,1,1,1; k=0,1,2,3}

14
Example 2
• Find the 8-point DFT of the zero-padded sequence
x8[k]={1,1,1,1,0,0,0,0; k=0,1,2,3,4,5,6,7}

15
Compare Example 1 and 2
• Find the DTFT of x4[k] and x8[k]
3
= 2 + 2cos
2 2

• = { , 1,1,1}
= ( ) ,

• = { , 1,1,1,0,0,0,0}
= ( ) ,

16
Compare Example 1 and 2

= ( ) = ( )

• Zero-padded sequence provides more sampling points

in frequency domain, i.e. more details in the spectrum.
17
Other DFT Pairs
• Example 3:
1, =0
= =
0, other

• Example 4:
1, =
= − =
0, other

• Example 5:
2
= cos , 0≤ ≤ −1

18
3. DFT Properties
• Like the DTFT, the DFT also satisfies a number of
properties which are useful in signal processing
• Some of these properties are essentially identical to those of
the DTFT, while some others are somewhat different

19
3.1 Periodicity in DFT
• DFT is periodic in both time and frequency domains
– Even though the original time domain sequence to be transformed
is not periodic!
• Periodicity can be explained by
– Mathematically: both the analysis and synthesis equations are
periodic by N.
N 1 2 k ( n  N ) N 1 2 kn
1 j 1 j
x[n  N ] 
N
 X[ k ]e N 
N
 X[ k ]e N  x[n]
k 0 k 0

N 1 2 ( k  N ) n N 1 2 kn
j j
X[ k  N ]   x[n]e N   x[n]e N  X[ k ]
k 0 k 0

– From the complex exponential wheel: there are only N vectors

around a unit circle, the transform will repeat itself every N points.
20
3.2 Parseval’s relation
• Similar to DTFT, DFT also holds the Parseval’s
relation:
1
[ ] = [ ]

– The energy conservation in time and frequency domain is

valid for DFT too.

21
Symmetry relations
• There are some very complex symmetry relations

22
4.1 Circular shift
• A circularly shifted sequence is
denoted by −
– modulo operation;
– L is the amount of shift;
– N is the length of the previously
determined base interval
• To obtain a circularly shifted
sequence:
– first linearly shift the sequence by L
– then rotate the sequence in such a
manner that the shifted sequence
remain in the same interval originally
defined by N.
23
4.1 Circular shift
• To obtain a circularly shifted sequence:
− , ≤ ≤ −1
− =
− + , 0≤ ≤

[ ] −1 −4
= +5 = +2
24
4.2 Circular reversal
• Circular reversal of length-N sequence x[n]:
0, =0
− =
− , 1≤ ≤ −1

[ ] −

25
4.3 Circular convolution
• The convolution operation involves folding and shifting, we
need to redefine the convolution for circularly shifted signals:

= ⊛ = −

• Expressed in matrix form, take N=4 as an example:

26
4.3 Circular convolution
• Example: Compute circular convolution of the following
sequences x[n]=[1 2 3 4], h[n]=[5 6 7]

– Circular convolution: [ ] ⊛ ℎ[ ]: 4-point

– Linear convolution:
∗ℎ = {5, 16, 34, 52, 45, 28}

6-point
5-point

27
4.4 Linear VS circular convolution
• All LTI systems are based on the principle of linear convolution, as
the output of an LTI system is the linear convolution of the system
impulse response and the input to the system, which is equivalent to
the product of the respective DTFTs in the frequency domain.
• However, if we use DFT instead of DTFT (so that we can compute it
using a computer), then the result appear to be invalid:
– DTFT is based on linear convolution, and DFT is based on circular
convolution, and they are not the same!
– For starters, they are not even of equal length: For two sequences of
length N and M, the linear convolution is of length N+M-1, whereas
circular convolution of the same two sequences is of length max(N,M),
where the shorter sequence is zero padded to make it the same length as
the longer one.

28
4.4 Linear VS circular convolution (cont.)
• Is there any relationship between the linear and circular
convolutions? Can one be obtained from the other?
• YES!
– FACT: If we zero pad both sequences x[n] and h[n], so that they
are both of length N1+N2-1, then linear convolution and circular
convolution result in identical sequences
– Furthermore: If the respective DFTs of the zero padded
sequences are X[k] and H[k], then the inverse DFT of X[k]∙H[k]
is equal to the linear convolution of x[n] and h[n]
– Note that, normally, the inverse DFT of X[k].H[k] is the circular
convolution of x[n] and h[n]. If they are zero padded, then the
inverse DFT is also the linear convolution of the two.

29
4.4 Computing convolution using DFT
• We can compute the output signal using no time domain
operation: the inverse DFT of X[k]∙H[k] is equal to the
linear convolution of x[n] and h[n].

• To ensure that one gets linear convolution, both sequences

in the time domain must be zero padded to appropriate
length L=N+M-1 as follows

30
4.4 Linear VS circular convolution (cont.)
• Compute circular convolution of x[n] = [ , 2, 3, 4], h[n]=[5,
6, 7], by appropriately zero padding the two:
– 1. Zero pad signals with length L=N1+N2-1=6:
• = [ , 2, 3, 4, 0, 0]
•ℎ = [ , 6, 7, 0, 0, 0]
– 2. Performing circular convolution using formula:

= ⊛ℎ = ℎ [ − ]

– 3. The solution

= = ∗ ℎ[ ] = ℎ[ − ]

31
4. Wrap up
• Facts about circular convolution:
– Circular convolution ≠ Linear convolution
– Linear convolution => sequence processed by system
= ∗ ℎ[ ]
– DFT multiplication (in FD) = circular convolution (in TD)
[ ] [ ] = [ ] ⊛ ℎ[ ]

• How to use DFT multiplication to get sequence

processed by system?
– Zero-padding  DFT  multiplication  IDFT

32
Lect-D5 Practices
• Exercise 1. Calculate the linear convolution and
circular convolution of the following sequence:
– a) {x[k]}={1, 2, 1}, {h[k]}={1, 0, 2, 0, 1};
– b) {x[n]}={1, 2, 1}, {h[n]}={1, 0, 2, 0, 1};

33
Lect-D5 Practices
• Exercise 2. Let x n , 0 ≤ n ≤ N − 1, be a length-N
sequence with an N-point DFT X , 0 ≤ k ≤ N − 1.
– a) Determine the N-point DFTs of the following length-N
sequence in terms of X[k]:
= − + −
where m1 and m2 are positive integers less than N;
– b) Determine the N-point IDFTs of the following length-N
sequence in terms of x[n]:
, for
Gk =
0, for

34