Computation of the DFT of

Real Sequences
• In most practical applications, sequences of
interest are real
• In such cases, the symmetry properties of
the DFT given in Table 3.7 can be exploited
to make the DFT computations more
efficient

1
Copyright © 2001, S. K. Mitra
N-Point DFTs of Two Length-N
Real Sequences
• Let g[n] and h[n] be two length-N real
sequences with G[k] and H[k] denoting their
respective N-point DFTs
• These two N-point DFTs can be computed
efficiently using a single N-point DFT
• Define a complex length-N sequence
x[n] = g [n] + j h[n]
• Hence, g[n] = Re{x[n]} and h[n] = Im{x[n]}
2
Copyright © 2001, S. K. Mitra
N-Point DFTs of Two Length-N
Real Sequences
• Let X[k] denote the N-point DFT of x[n]
• Then, from Table 3.6 we arrive at
G[k ] = 1 { X [k ] + X * [〈− k 〉 N ]}
2
H [k ] = 1
{ X [k ] − X * [〈− k 〉 N ]}
2j
• Note that
X * [〈− k 〉 N ] = X * [〈 N − k 〉 N ]
3
Copyright © 2001, S. K. Mitra
N-Point DFTs of Two Length-N
Real Sequences
• Example - We compute the 4-point DFTs of
the two real sequences g[n] and h[n] given
below
{g [n]} = {1 2 0 1}, {h[n]} = {2 2 1 1}
↑ ↑

• Then {x[n]} = {g [n]} + j{h[n]} is given by

{x[n]} = {1 + j 2 2 + j 2 j 1 + j}
↑
4
Copyright © 2001, S. K. Mitra
N-Point DFTs of Two Length-N
Real Sequences
• Its DFT X[k] is
 X [0] 1 1 1 1  1 + j 2   4 + j 6 
 X [1]  1 − j − 1 j  2 + j 2  2 
 X [2] = 1 − 1 1 − 1   j  =  − 2 
 X [3] 1 j − 1 − j   1 + j   j 2 

• From the above

X * [ k ] = [ 4 − j 6 2 − 2 − j 2]
• Hence
5
X * [ 〈 4 − k 〉 4 ] = [ 4 − j 6 − j 2 − 2 2]
Copyright © 2001, S. K. Mitra
N-Point DFTs of Two Length-N
Real Sequences
• Therefore
{G[k ]} = {4 1 − j − 2 1 + j}
{H [k ]} = {6 1 − j 0 1 + j}

verifying the results derived earlier

6
Copyright © 2001, S. K. Mitra
 2N-Point DFT of a Real
Sequence Using an N-point DFT
• Let v[n] be a length-2N real sequence with
an 2N-point DFT V[k]
• Define two length-N real sequences g[n]
and h[n] as follows:
g [n] = v[2n], h[n] = v[2n + 1], 0 ≤ n ≤ N
• Let G[k] and H[k] denote their respective N-
point DFTs

7
Copyright © 2001, S. K. Mitra
 2N-Point DFT of a Real
Sequence Using an N-point DFT
• Define a length-N complex sequence
{x[n]} = {g [n]} + j{h[n]}
with an N-point DFT X[k]
• Then as shown earlier
G[k ] = 1
{ X [k ] + X * [〈− k 〉 N ]}
2

H [k ] = 1
{ X [k ] − X * [〈− k 〉 N ]}
2j

8
Copyright © 2001, S. K. Mitra
 2N-Point DFT of a Real
Sequence Using an N-point DFT
2 N −1
• Now V [k ] = ∑ nk
v[n]W2 N
n =0
N −1 N −1
= ∑ v[ 2 n ]W2N +
2 nk
∑ v[2n + 1]W2(N2 n +1)k
n =0 n =0
N −1 N −1
= ∑ nk
g [n]WN + ∑ nk k
h[n]WN W2 N
n =0 n =0
N −1 N −1
= ∑ g[n]WN + W2 N ∑ h[n]WN , 0 ≤ k
nk k nk
≤ 2N −1
9 n =0 n =0
Copyright © 2001, S. K. Mitra
 2N-Point DFT of a Real
Sequence Using an N-point DFT
• i.e.,
V [k ] = G[〈 k 〉 N ] + W2 N H [〈 k 〉 N ], 0 ≤ k ≤ 2 N − 1
k

• Example - Let us determine the 8-point

DFT V[k] of the length-8 real sequence
{v[n]} = {1 2 2 2 0 1 1 1}
↑

• We form two length-4 real sequences as

follows
10
Copyright © 2001, S. K. Mitra
 2N-Point DFT of a Real
Sequence Using an N-point DFT
{g [n]} = {v[2n]} = {1 2 0 1}
↑
{h[n]} = {v[2n + 1]} = {2 2 1 1}
↑
• Now
V [k ] = G[〈 k 〉 4 ] + W8k H [〈 k 〉 4 ], 0 ≤ k ≤ 7
• Substituting the values of the 4-point DFTs
G[k] and H[k] computed earlier we get
11
Copyright © 2001, S. K. Mitra
 2N-Point DFT of a Real
Sequence Using an N-point DFT
V [0] = G[0] + H [0] = 4 + 6 = 10
V [1] = G[1] + W8 H [1]
1
− jπ / 4
= (1 − j ) + e (1 − j ) = 1 − j 2.4142
V [2] = G[2] + W82 H [2] = −2 + e − jπ / 2 ⋅ 0 = −2
V [3] = G[3] + W8 H [3]
3
− j 3π / 4
= (1 + j ) + e (1 + j ) = 1 − j 0.4142
V [4] = G[0] + W84 H [0] = 4 + e − jπ ⋅ 6 = −2
12
Copyright © 2001, S. K. Mitra
 2N-Point DFT of a Real
Sequence Using an N-point DFT
V [5] = G[1] + W8 H [1]
5
− j 5π / 4
= (1 − j ) + e (1 − j ) = 1 + j 0.4142
− j 3π / 2
V [6] = G[2] + W8 H [2] = −2 + e
6
⋅ 0 = −2

V [7] = G[3] + W8 H [3]

7

− j 7π / 4
= ( + j) + e
1 (1 + j ) = 1 + j 2.4142

13
Copyright © 2001, S. K. Mitra
 Linear Convolution Using the
DFT
• Linear convolution is a key operation in
many signal processing applications
• Since a DFT can be efficiently implemented
using FFT algorithms, it is of interest to
develop methods for the implementation of
linear convolution using the DFT

14
Copyright © 2001, S. K. Mitra
 Linear Convolution of Two
Finite-Length Sequences
• Let g[n] and h[n] be two finite-length
sequences of length N and M, respectively
• Denote L = N + M − 1
• Define two length-L sequences
 g [n], 0 ≤ n ≤ N −1
g e [n ] = 
 0, N ≤ n ≤ L −1
 h[n], 0 ≤ n ≤ M −1
he [n] = 
 0, M ≤ n ≤ L −1
15
Copyright © 2001, S. K. Mitra
 Linear Convolution of Two
Finite-Length Sequences
• Then
y L [n] = g [n] * h[n] = yC [n] = g [n] L h[n]
• The corresponding implementation scheme
is illustrated below
g[n] Zero-padding g e [n] ( N + M − 1) −
with point DFT
Length-N ( M − 1) zeros ( N + M − 1) − y L [n]
×
h[n] Zero-padding he [n] ( N + M − 1) − point IDFT
with
Length-M ( N − 1) zeros point DFT Length- ( N + M − 1)
16
Copyright © 2001, S. K. Mitra
Linear Convolution of a Finite-
Length Sequence with an
Infinite-Length Sequence
• We next consider the DFT-based
implementation of
M −1
y[n] = ∑ h[l] x[n − l] = h[n] * x[n]
l =0
where h[n] is a finite-length sequence of
length M and x[n] is an infinite length (or a
finite length sequence of length much
17
greater than M)
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• We first segment x[n], assumed to be a
causal sequence here without any loss of
generality, into a set of contiguous finite-
length subsequences xm [n] of length N each:
∞
x[n] = ∑ xm [n − mN ]
m =0
where
 x[n + mN ], 0 ≤ n ≤ N − 1
xm [n] = 
 0, otherwise
18
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• Thus we can write
∞
y[n] = h[n] * x[n] = ∑ ym [n − mN ]
m =0
where
ym [n] = h[n] * xm [n]
• Since h[n] is of length M and xm [n] is of
length N, the linear convolution h[n] * xm [n]
is of length N + M − 1
19
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• As a result, the desired linear convolution
y[n] = h[n] * x[n] has been broken up into a
sum of infinite number of short-length
linear convolutions of length N + M − 1
each: ym [n] = xm [ n] L h[n]
• Each of these short convolutions can be
implemented using the DFT-based method
discussed earlier, where now the DFTs (and
the IDFT) are computed on the basis of
( N + M − 1) points
20
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• There is one more subtlety to take care of
before we can implement
∞
y[n] = ∑ ym [n − mN ]
m =0
using the DFT-based approach
• Now the first convolution in the above sum,
y0 [n] = h[n] * x0 [n], is of length N + M − 1
and is defined for 0 ≤ n ≤ N + M − 2
21
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• The second short convolution y1[n] =
h[n] * x1[n] , is also of length N + M − 1
but is defined for N ≤ n ≤ 2 N + M − 2
• There is an overlap of M − 1 samples
between these two short linear convolutions
• Likewise, the third short convolution y2 [n] =
h[n] * x2 [n] , is also of length N + M − 1
but is defined for 0 ≤ n ≤ N + M − 2

22
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• Thus there is an overlap of M − 1 samples
between h[n] * x1[n] and h[n] * x2 [n]
• In general, there will be an overlap of M − 1
samples between the samples of the short
convolutions h[n] * xr −1[n] and h[n] * xr [n]
for
• This process is illustrated in the figure on
the next slide for M = 5 and N = 7
23
Copyright © 2001, S. K. Mitra
 Overlap-Add Method

24
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
Add

Add

25
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• Therefore, y[n] obtained by a linear
convolution of x[n] and h[n] is given by
y[n] = y0 [n], 0≤n≤6
y[n] = y0 [n] + y1[n − 7], 7 ≤ n ≤ 10
y[n] = y1[n − 7], 11 ≤ n ≤ 13
y[n] = y1[n − 7] + y2 [n − 14], 14 ≤ n ≤ 17
y[n] = y2 [n − 14], 18 ≤ n ≤ 20
•
•
•

26
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• The above procedure is called the overlap-
add method since the results of the short
linear convolutions overlap and the
overlapped portions are added to get the
correct final result
• The function fftfilt can be used to
implement the above method

27
Copyright © 2001, S. K. Mitra
 Overlap-Add Method
• Program 3_6 illustrates the use of fftfilt
in the filtering of a noise-corrupted signal
using a length-3 moving average filter
• The plots generated by running this program
is shown below
8
s[n]
y[n]
6
Amplitude

-2
0 10 20 30 40 50 60
28 Time index n
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• In implementing the overlap-add method
using the DFT, we need to compute two
( N + M − 1)-point DFTs and one ( N + M − 1)-
point IDFT since the overall linear
convolution was expressed as a sum of
short-length linear convolutions of length
( N + M − 1) each
• It is possible to implement the overall linear
convolution by performing instead circular
29 convolution of length shorter than ( N + M − 1)
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• To this end, it is necessary to segment x[n]
into overlapping blocks xm [n], keep the
terms of the circular convolution of h[n]
with xm [n] that corresponds to the terms
obtained by a linear convolution of h[n] and
xm [n] , and throw away the other parts of
the circular convolution

30
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• To understand the correspondence between
the linear and circular convolutions,
consider a length-4 sequence x[n] and a
length-3 sequence h[n]
• Let yL [n] denote the result of a linear
convolution of x[n] with h[n]
• The six samples of y L [n] are given by

31
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
y L [0] = h[0]x[0]
y L [1] = h[0]x[1] + h[1]x[0]
y L [2] = h[0]x[2] + h[1]x[1] + h[2]x[0]
y L [3] = h[0]x[3] + h[1]x[2] + h[2]x[1]
y L [4] = h[1]x[3] + h[2]x[2]
y L [5] = h[2]x[3]

32
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• If we append h[n] with a single zero-valued
sample and convert it into a length-4
sequence he [n], the 4-point circular
convolution yC [n] of he [n] and x[n] is given
by
yC [0] = h[0]x[0] + h[1]x[3] + h[2]x[2]
yC [1] = h[0]x[1] + h[1]x[0] + h[2]x[3]
yC [2] = h[0]x[2] + h[1]x[1] + h[2]x[0]
yC [3] = h[0]x[3] + h[1]x[2] + h[2]x[1]
33
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• If we compare the expressions for the
samples of y L [n] with the samples of yC [n] ,
we observe that the first 2 terms of yC [n] do
not correspond to the first 2 terms of yL [n] ,
whereas the last 2 terms of yC [n] are
precisely the same as the 3rd and 4th terms
of yL [n] , i.e.,
y L [0] ≠ yC [0], y L [1] ≠ yC [1]
y L [2] = yC [2], y L [3] = yC [3]
34
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• General case: N-point circular convolution
of a length-M sequence h[n] with a length-N
sequence x[n] with N > M
• First M − 1 samples of the circular
convolution are incorrect and are rejected
• Remaining N − M + 1 samples correspond
to the correct samples of the linear
convolution of h[n] with x[n]
35
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• Now, consider an infinitely long or very
long sequence x[n]
• Break it up as a collection of smaller length
(length-4) overlapping sequences xm [n] as
xm [n] = x[n + 2m], 0 ≤ n ≤ 3, 0 ≤ m ≤ ∞
• Next, form
wm [n] = h[n] 4 xm [n]
36
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• Or, equivalently,
wm [0] = h[0]xm [0] + h[1]xm [3] + h[2]xm [2]
wm [1] = h[0]xm [1] + h[1]xm [0] + h[2]xm [3]
wm [2] = h[0]xm [2] + h[1]xm [1] + h[2]xm [0]
wm [3] = h[0]xm [3] + h[1]xm [2] + h[2]xm [1]
• Computing the above for m = 0, 1, 2, 3, . . . ,
and substituting the values of xm [n] we
37 arrive at
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
w0 [0] = h[0]x[0] + h[1]x[3] + h[2]x[2] ← Reject
w0 [1] = h[0]x[1] + h[1]x[0] + h[2]x[3] ← Reject
w0 [2] = h[0]x[2] + h[1]x[1] + h[2]x[0] = y[2] ← Save
w0 [3] = h[0]x[3] + h[1]x[2] + h[2]x[1] = y[3] ← Save

w1[0] = h[0]x[2] + h[1]x[5] + h[2]x[4] ← Reject

w1[1] = h[0]x[3] + h[1]x[2] + h[2]x[5] ← Reject
w1[2] = h[0]x[4] + h[1]x[3] + h[2]x[2] = y[4] ← Save
w1[3] = h[0]x[5] + h[1]x[4] + h[2]x[3] = y[5] ← Save
38
Copyright © 2001, S. K. Mitra
 Overlap-Save Method

w2 [0] = h[0]x[4] + h[1]x[5] + h[2]x[6] ← Reject

w2 [1] = h[0]x[5] + h[1]x[4] + h[2]x[7] ← Reject

w2 [2] = h[0]x[6] + h[1]x[5] + h[2]x[4] = y[6] ← Save

w2 [3] = h[0]x[7] + h[1]x[6] + h[2]x[5] = y[7] ← Save

39
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• It should be noted that to determine y[0] and
y[1], we need to form x−1[n]:
x−1[0] = 0, x−1[1] = 0,
x−1[2] = x[0], x−1[3] = x[1]
and compute w−1[n] = h[n] 4 x−1[n] for 0 ≤ n ≤ 3
reject w−1[0] and w−1[1] , and save w−1[2] = y[0]
and w−1[3] = y[1]

40
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• General Case: Let h[n] be a length-N
sequence
• Let xm [n] denote the m-th section of an
infinitely long sequence x[n] of length N
and defined by
xm [ n] = x[n + m( N − m + 1)], 0 ≤ n ≤ N − 1
with M < N

41
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• Let wm [n] = h[n] N xm [n]
• Then, we reject the first M − 1 samples of wm [n]
and “abut” the remaining N − M + 1 samples of
wm [n] to form y L [n], the linear convolution of
h[n] and x[n]
• If ym [n] denotes the saved portion of wm [n] ,
i.e.
 0, 0≤n≤ M −2
ym [ n ] = 
42 wm [n], M − 1 ≤ n ≤ N − 2
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• Then
y L [n + m( N − M + 1)] = ym [n], M −1 ≤ n ≤ N −1
• The approach is called overlap-save
method since the input is segmented into
overlapping sections and parts of the results
of the circular convolutions are saved and
abutted to determine the linear convolution
result
43
Copyright © 2001, S. K. Mitra
 Overlap-Save Method
• Process is illustrated next

44
Copyright © 2001, S. K. Mitra
 Overlap-Save Method

45
Copyright © 2001, S. K. Mitra