Elec4621:

Signal Processing 2
Chapter 4: The Discrete Fourier
Transform
Dr. D. S. Taubman
March 18, 2011

1 Denition
Recall that the Discrete Time Fourier Transform (DTFT) is dened on sequences
of innite extent according to
4
[
ˆx̂($) = x[n]ejn$ , for    $   (1)
n=4

with the inverse DTFT given by

]  ] 
1
x[n] = d$ · ˆx̂($)ejn$ (2)
(2)2  

Although x[n] is a sequence dened only at integer coordinates, n, its DTFT,

ˆx̂($), is a continuous function over $ 5 [, ]. Moreover, if x [n] is obtained
by Nyquist sampling a continuous signal, x (t), ˆx̂ ($) is both the DTFT of x [n]
and the FT (Fourier Transform) of x (t).
By contrast, the Discrete Fourier Transform (DFT) involves a nite number
of discrete frequencies. It is dened only for sequences, x[n], of nite support,
e.g., 0  n < N , where N is the length of the sequence. It is not necessary for us
to start the indices, n, from 0, but this is the most common convention. With
this convention, the N -point DFT and its inverse are given by the following
equations:
N1
[ 2nk
X[k] = x[n]ej N , 0k<N
n=0
N1
1 [ 2nk
x [n] = X [k] ej N , 0n<N
N
k=0

1
c
?Taubman, 2003 ELEC4621: The DFT Page 2

The complex exponentials involved in the forward and inverse DFT are used
so commonly in signal processing that it becomes convenient to dene the special
symbol,
 2
WN = ej N
 2 k 2k
Noting that WNk = ej N = ej N , the DFT and its inverse may be expressed
as
N1
[
X [k] = x[n]WNnk
n=0
N1
1 [
x [n] = X [k] WNnk
N
k=0

Note also that WNk k=0,1,...,N 1 are the N complex roots of unity.
We may also express the DFT in vector notation as follows. Let wk denote
the vector (sequence) whose elements are
2nk
wk [n] = WNnk = ej N

Then the DFT may be expressed as

X [k] = kx, wk l
and the inverse DFT may be expressed as
N1
1 [
x= X[k]wk
N
k=0

This formulation provides great insight into the DFT operation. It indicates
that the vectors, wk , form a basis for the set of all length N input sequences,
x. Moreover, this basis is orthogonal, so that kwi , wj l = 0 for i 9= j.
It is often convenient to work with orthonormal basis sets. To this end,
dene
1
w3 k = s wk
N
These form an orthonormal basis for the set of input sequences, as may be seen
by rewriting the DFT in a normalized form, with
1
X 3 [k] = s X[k] = kx, wk3 l (3)
N
and
N1
[
x = X 3 [k]w3 k (4)
k=0
N1
[
= kx, wk3 lw3 k
k=0
c
?Taubman, 2003 ELEC4621: The DFT Page 3

In this form we can clearly see that the input vector (sequence), x is just being
written as the sum of its projections, kx, wk3 lw3 k , onto the orthonormal basis
vectors, w3 k .

2 Relationship Between DFT and DTFT

The DFT and DTFT are closely related; in fact, under appropriate conditions,
they are equivalent, which is the foundation for much of the usefulness of the
DFT. Let x[n] denote a nite support sequence, which is equal to zero every-
where except in the region, 0  n < N . The N -point DFT of the nite sequence,
restricted to this region may be written
N1
[ 2nk
X [k] = x[n]ej N

n=0
# $
4
[ 
j$n 
= x[n]e  (5)
n=4

$= 2
N k

So the DFT, X [k], is a sampling of the spectrally continuous DTFT, ˆx̂($) at

the locations $ = 2 N k.
Although this relationship is mathematically correct, it violates the conven-
tion that ˆx̂ ($) is dened only on   $  , which is required to impart the
correct interpretation to discrete frequency1 . To correct this problem, dene
 
x 1
x mod 2 / x  2 +
2 2

where exf is the oor function, rounding its argument down to the largest
integer, no larger than x. Note that   x mod 2 < . Now, since x mod 2
diers from x by a multiple of 2, the mathematical equivalence in equation (5)
also gives
# 4 $
[ 
j$n 
X [k] = x[n]e  = ˆx̂ ($)|$=( 2 k) mod 2 (6)
n=4
 N
$=( N k) mod 2
2

The fact that the DFT is a sampled version of the DTFT and that the
DFT is invertible means that this sampled representation must contain all the
information in the spectrally continuous DTFT, provided of course, that the
signal is zero outside the region over which the DFT is taken. In the general case,
where x[n] has innite support, we can still sample the spectrally continuous
1 The interpretation of frequency in the discrete domain derives from the fact that the FT

and the DTFT are identical for Nyquist band-limited signals. Although some people prefer to
dene the DTFT as having a periodically repeating spectrum, this confuses the relationship
between discrete and continuous signals —— it requires the introduction of impulse sequences
and other mathematical anomalies that are best avoided.
c
?Taubman, 2003 ELEC4621: The DFT Page 4

DTFT, ˆx̂($), and associate these samples with a hypothetical DFT, dened by
X 3 [k] = ˆx̂ ($)|$=( 2 k) mod 2 . In this case, however, the inverse DFT of X 3 [k]
N
is given by [
x3 [n] = x[n + mN ], 0  n < N
m
This is a time-domain aliasing relationship. It is the analog of frequency aliasing
which occurs when a signal is sampled too coarsely in the time domain; in this
case, the aliasing occurs when a signal is sampled too coarsely in the frequency
domain. Time-domain aliasing can easily occur if we are not careful when
using the DFT (usually through an FFT implementation) to implement ltering
operations, as we shall see shortly.

3 Filtering with the DFT

The DFT provides an e!cient tool for implementing FIR digital lters. This
fact is a direct consequence of the relationship between the DFT and the DTFT.
Let h [n] denote the impulse response of a causal FIR lter of order M . Thus
h [n] has region of support 0  n  M . We would like to lter an input signal,
x [n], to obtain
[M
y[n] = h[m]x[n  m]
m=0
To begin, we shall suppose that the input signal, x[n], also has nite support
with Nx samples, given by 0  n < Nx . It follows, that after ltering, the output
signal, y[n], will be zero outside the region 0  n < Nx + M . Thus, selecting
N = Nx + M
we see that both x [n] and y [n] are zero outside the region 0  n < N , mean-
ing that their N -point DFT’’s are sampled copies of their respective DTFT’’s.
The DFT/DTFT equivalence relationship of equation (6) may then be invoked,
yielding
Y [k] = yˆˆ ($)|$=( 2 k) mod 2
N
k l
= ˆx̂ ($) ˆĥ ($)
$=( 2
N k) mod 2
k l
= X [k] × ˆĥ ($)
$=( 2
N k ) mod 2

= X [k] H [k] , 0  k < N

Notice that we have not appealed to any specic properties of the DFT itself,
other than its relationship to the DTFT. It is the DTFT’’s convolution theorem
which is at work here. We will discuss a separate, related convolution theorem
for the DFT which applies to ““circular”” convolution; however, it is important
to distinguish between circular convolution and true convolution —— the latter is
usually the goal in ltering applications.
c
?Taubman, 2003 ELEC4621: The DFT Page 5

3.1 Overlap-Add-Save Method

We have shown that true ltering of a nite length sequence, x [n], by a nite
support lter, h [n], is equivalent to multiplication of their N -piont DFT’’s, so
long as N is at least as large as the sum of the lter order, M , and the input
sequence length, Nx . In Section 5, we will demonstrate a fast implementation for
the DFT (known as the FFT) which allows an N -point DFT to be computed
using only N log2 N real-valued multiplications. These two observations are
the basis of a number of related strategies for implementing large FIR lters
e!ciently.
The DFT size, N , is generally limited by practical considerations such as
delay, memory and (to a lesser extent) computation, while the input signals of
interest often have unbounded length. In this section, we describe the overlap-
add-save method for ltering an unbounded input sequence, x [n], using bounded
DFT operations.
The DFT size, N , is xed, and the input signal is broken into nite length
segments, xp [n], each with Nx = N  M samples. Specically,

x [n + pNx ] 0  n < Nx
xp [n] =
0 otherwise

Evidently, x [n] is the sum of its translated segments,

[
x [n] = xp [n  pNx ] (7)
p

This segmented representation of x [n] is illustrated in Figure 1.

From our earlier discussion, we know that each segment, xp [n], may be
ltered using the N -point DFT, yielding ltered output yp [n] with

Yp [k] = Xp [k] H [k] , 0k<N

From equation (7), together with linearity and time invariance of ltering, we
see that the complete ltered signal may be formed as a sum of the translated,
ltered segments as [
y [n] = yp [n  pNx ]
p

Importantly, the support of each ltered segment, yp [n], is not restricted to the
same interval, 0  n < Nx , but occupies all N samples. Thus, the nal M sam-
ples from each ltered output segment overlap the rst M samples from the next
ltered output segment, as shown in Figure 1. The overlapping contributions
must be added.
The complete ltering procedure may be summarized as follows:

1. Determine the segment length, Nx , from Nx = N  M .

2. For each input segment, xp [n],
c
?Taubman, 2003 ELEC4621: The DFT Page 6

n=0 n = Nx n = 2N x n = 3N x n = 4N x n = 5N x

x[n ]

x0 [ n ] x1[n < N x ] x2 [ n < 2 N x ] x3 [ n < 3 N x ] x4 [ n < 4 N x ]

y0 [n ] y2 [n < 2 N x ] y4 [n < 4 N x ]

y1[n < N x ] y3 [ n < 3N x ]

Figure 1: Segmentation of an unbounded input signal, x [n], into segments of

length Nx , for DFT-based ltering using the overlap-add-save method. The
overlapping portions of the ltered output sections are identied by the shaded
bars.

(a) Compute the N -point DFT, Xp [k]. Note that the last M samples of
xp [n] are always zero; it has at most Nx non-zero samples.
(b) Find Yp [k] from Yp [k] = Xp [k] × H [k]. The factors, H [k], are xed
for all segments and generally computed ahead of time.
(c) Find yp [n] by taking the inverse DFT of Yp [k].
(d) Add the last M samples of yp1 [n] (saved in the previous segment’’s
““save”” step) to the rst M samples of yp [n], yielding the modied
ltered output, yp3 [n].
(e) Output the rst Nx samples of yp3 [n], saving the remaining M samples
in a temporary buer for use in step (2.d) when processing the next
segment.

Evidently, the algorithm calls for an M -sample save buer, in addition to an

N -sample buer for performing the various DFT operations.
To understand the computational advantages of DFT-based ltering, observe
that the algorithm generates Nx new samples after processing each segment.
To generate these samples, an N -point DFT and an N -point IDFT must be
performed, having a combined cost of 2N log2 N real-valued multiplications (see
Section 5). Multiplication of Xp [k] by H [k] need only be performed over half of
the DFT coe!cients, due to conjugate symmetry, Yp [k] = Yp [N  k], for a total
c
?Taubman, 2003 ELEC4621: The DFT Page 7

cost of N/2 complex-valued multiplications, or 2N real-valued multiplications.

The total number of multiplications2 per output sample is then
2N log2 2N 2N
= log2 2N
Nx N M
Example 1 A 1024-point DFT/IDFT processor is available for use in a lter-
ing application, involving an order M = 128 FIR lter. The total number of
multiplications required per output sample is
2048
log2 2048 = 25.14
1024  128
By constrast, direct application of the lter requires 128 multiplications per out-
put sample.

Some consideration should conrm the fact that DFT-based techniques are
most interesting when working with very high order FIR lters. As an example,
to simulate the acoustic environment of a typical music hall might require lters
with many thousands of taps. In this case, the potential computational savings
from a DFT-based implementation can be enormous.

4 Properties of the DFT

Conjugate Symmetry: When the input sequence, x[n], is real-valued, as is
almost invariably the case for image processing applications,

X[k] = X  [N  k]

where the superscript,  , denotes complex conjugation as always.

Circular Convolution: Recall that the DFT is dened only on 0  n < N .
The circular convolution of two sequences, x[n] and h[n], on this interval
is dened by
N
[ 1
y[n] = x [k] h [(n  k) mod N ]
k=0
N
[ 1
= h [k] x [(n  k) mod N ]
k=0

In the DFT domain, circular convolution is always equivalent to multipli-

cation, i.e.
Y [k] = X[k] · H[k]
but the conditions under which circular convolution and true convolution
are identical are those discussed in Section 3.
2 A similar number of additions is required, but multiplications are generally more costly

than additions, as discussed in the previous lecture.

c
?Taubman, 2003 ELEC4621: The DFT Page 8

Dual of Convolution: Suppose we multiply two sequences, x[n] and y[n], in

the time domain to obtain u[n] = x[n] · y[n]. In the DFT domain, this
operation is eqivalent to circular convolution. Specically,
N1
1 [
U [k] = X [p] Y [(k  p) mod N ] (8)
N p=0

Energy: Parseval’’s relation states, essentially, that the energy or power in the
time domain is equal to the energy in the Fourier domain. For the DFT,
Parseval’’s relation is
N1
[ N1
1 [
2
|x [n]| = |X [k]|2
n=0
N
k=0

This may be derived easily from the normalized vector space interpretation
of the DFT and its inverse in equations (3) and (4).
Extended Parseval Relationship: An extended form of Parseval’’s relation-
ship, for two arbitrary sequences, x[n] and y[n], states that
N1
[ N1
1 [
x [n] y  [n] = X [k] Y  [k]
n=0
N
k=0

5 Fast Algorithms for the DFT

Although fast DFT algorithms can be developed for arbitrary N , the savings are
greatest and the development simplest when N is a power of 2. For this reason,
let N = 2r for some r. The basic FFT (Fast Fourier Transform) algorithm is
based on the observation that X[k] may be written as
r
2[ 1  
j2kn
X[k] = x[n] exp
n=0
2r
2r1
[1  
j2kn
= x[2n] exp
n=0
2r1
2r1
[1    
j2kn j2k
+ x[2n + 1] exp · exp
n=0
2r1 2r

Now let xe [n] = x[2n] denote the even sub-sequence of x[n] and let xo [n] =
x[2n+1] denote the odd sub-sequence. The DFT of each of these sub-sequences,
Xe [k] and Xo [k], is dened for 0  k < 2r1 . The above formula becomes
+
Xe [k] + W2k
r Xo [k] for 0  k < 2r1 ,
X[k] =
Xe [k  2r1 ] + W2k
r Xo [k  2
r1
] for 2r1  k < 2r .
c
?Taubman, 2003 ELEC4621: The DFT Page 9

where we have used the notation,

2
WN = ej N

introduced previously.
r1
Finally, noting that W2kr = W22r +k , we may express the 2r -point DFT
of x [n] in terms of the 2r1 -point DFT’’s of its even and odd sub-sequences as
follows
   
 X [k]r1  = Xe [k] + W2k
r Xo [k]
, 0  k < 2r1 (9)
X k+2 Xe [k]  W2k
r Xo [k]

Now suppose that a 2r -point FFT requires Cr operations per sample, or a total
of 2r Cr opreations. The following recursive description of the algorithm allows
us to compute its complexity in a straightforward manner:

1. Compute Xe [k] and Xo [k] for 0  k < 2r1 . The number of operations
required for this step is 2r Cr1 .
2. Multiply Xo [k] by W2k r for 0  k < 2r1 , to obtain X03 [k]. We assume
that the factors, W2k
r , have been computed and stored in advance, which
is reasonable because they do not depend upon the signal, x[n]. This step
requires 2r1 complex-valued multiplications.
3. For 0   k < 2r1 compute X[k] = Xe [k] + Xo3 [k] and
X k + 2r1 = Xe [k]  Xo3 [k]. This step requires 2r complex-valued ad-
ditions/subtractions3 .

In terms of complex-valued multiplications, the operation count thus satises

1
2r Cr = 2r Cr1 + 2r
2
1 1
= 2r Cr2 + 2r + 2r
2 2
..
.
r r
= 2
2
The number of complex-valued additions is twice as large, i.e. r2r . These
complexities are usually expressed in terms of the dimension, N = 2r . So
that the number of complex-valued multiplications required to compute the
N -point DFT using this simple FFT algorithm is N2 log2 (N ), while the num-
ber of complex-valued additions is N log2 (N ). Compare this with the direct
computation of the FFT which requires N 2 complex-valued multiplications and
additions.
3 Since the complexity of additions is identical to the complexity of subtractions, we lump

them together and generally refer to both as additions.

c
?Taubman, 2003 ELEC4621: The DFT Page 10

5.1 Real-Valued Sequences

In the above formulation, the input sequence, its DFT and all numerical op-
erations are complex-valued. In practice, we normally work with real-valued
input sequences, x [n], whose DFT satises the conjugate symmetry property,
X [k] = X  [N  k]. We can exploit this symmetry to reduce the overall com-
plexity.
One simple way to do this is to observe that at each stage of the FFT
algorithm we need only compute X [k] over the range 0  k < N2 , using values
of Xe [k] and Xo [k] in the range 0  k < N4 . The relevant update relationships
are readily derived from equation (9) as
   
X [k]  Xe [k] + W2k
r Xo [k]
=
X 2r1  k Xe [k]  W2kr Xo [k]
 
Xe [k] + W2kr Xo [k]
=   , 0  k < 2r2
Xe [k]  W2k r Xo [k]

The complexity of these calculations is identical to that of the full complex-

valued calculations described previously, except that there are only half as many
of them. Finally, observing that a complex-valued multiplication requires four
real-valued multiplications and a complex-valued addition requires two real-
valued additions, we nd that the complexity of an N -point real-valued FFT
is

N log2 N real-valued multiplications, and

N log2 N real-valued additions

It is worth noting that there are many variations on the basic FFT algorithm, as
described here. In fact, there is at least one entire book, which deals exclusively
with fast Fourier transform algorithms. Common to all these algorithms is the
fact that the complexity of an N -point DFT has order N log2 N .