Digital Signal Processing 9.3 The Fast Fourier Transform (FFT) 211
Part A | 9.3
used in practice, the parallel realization corresponds to
the following transfer function decomposition
H.z/ D
m
Y
kD1
p
0k z
2
C
p
1k z C
p
2k
z 2 C m 1k z C m 2k
;
D h 0 C
m
Y
kD1
p 0
1k z C
p 0
2k
z 2 C m 1k z C m 2k
;
D h
0
0 C
m
Y
kD1
p 00
0k z
2
C
p 00
1k z
z 2 C m 1k z C m 2k
:
(9.65)
The above is also known as the partial-fraction decomposition. This equation indicates three alternative
forms of the parallel realization, where the last two are
canonic with respect to the number of multiplier elements.
It should be mentioned that each second-order block
in the cascade and parallel forms can be realized by any
of the existing distinct structures, as, for instance, one
of the direct forms shown in Fig. 9.20.
All these digital filter realizations present different
properties when one considers practical finite-precision
implementations; that is, the quantization of the coefficients and the finite precision of the arithmetic operations, such as additions and multiplications. In fact, the
analysis of the finite-precision effects in the distinct realizations is a fundamental step in the overall process of
designing any digital filter [9.2].
9.3 The Fast Fourier Transform (FFT)
The FFT (fast Fourier transform) algorithm is a faster
version of the discrete Fourier transform (DFT). FFT
utilizes some clever algorithms to do the same thing as
the DFT, but in much less time [9.2].
The DFT is extremely important in the area of frequency (spectral) analysis because it takes a discrete
signal in the time domain and transforms that signal
into its discrete frequency domain representation. Without a discrete-time to discrete-frequency transform we
would not be able to compute the Fourier transform
with a microprocessor or DSP-based (DSP: Digital Signal Processor) system [9.1, 2, 4–6].
It is the speed and discrete nature of the FFT that
allows us to analyze a signal’s spectrum, as will soon
become evident.
9.3.1 Review of Integral Transforms
We first give a review of the integral transforms that
have been used in the text, possibly in their unilateral
(single-side) version.
The bilateral Laplace transform
X.s/ D Lfx.t/g D
C1 Z
1
x.t/e
st dt; x.t/
L
X.s/ :
(9.66)
The continuous-time Fourier transform
X.i!/ D F fx.t/g D
C1 Z
1
x.t/e
i!t dt; x.t/
F
X.i!/ :
(9.67)
The bilateral Z-transform
X.z/ D Zfx.n/g
D
C1 X
nDD1
x.n/z
n
; x.n/
Z
X.z/ :
(9.68)
The Laplace transform is used to obtain a pole-zero representation of a continuous-time signal or system, x.t/,
in the s-plane. Similarly, the Z-transform is used to find
a pole-zero representation of a discrete-time signal or
system, x.n/, in the z-plane.
The continuous-time Fourier transform can be
found by evaluating the Laplace transform form at s D
i!. The picture can be extended by introducing the
discrete-time Fourier transform (DTFT). The DTFT can
be found by evaluating the Z-transform at z D exp.i˝/,
as follows
X.e
i˝
/ D
C1 X
nDD1
x.n/e
i˝n
; x.n/
DTFT
X.e
i˝
/ :
(9.69)
One needs to point out here that the frequency variable ˝ is in normalized units of radians per sample
rather than absolute units of rad=s, which apply to !
appearing in the standard Fourier transform. This can
be justified by recollecting that sequences x.n/ are generated by sampling a continuous-time signal x.t/ at
a certain sampling rate f s . In this respect, the DTFT can
be viewed as a discrete approximation of the Fourier
Part A | 9.3
used in practice, the parallel realization corresponds to
the following transfer function decomposition
H.z/ D
m
Y
kD1
p
0k z
2
C
p
1k z C
p
2k
z 2 C m 1k z C m 2k
;
D h 0 C
m
Y
kD1
p 0
1k z C
p 0
2k
z 2 C m 1k z C m 2k
;
D h
0
0 C
m
Y
kD1
p 00
0k z
2
C
p 00
1k z
z 2 C m 1k z C m 2k
:
(9.65)
The above is also known as the partial-fraction decomposition. This equation indicates three alternative
forms of the parallel realization, where the last two are
canonic with respect to the number of multiplier elements.
It should be mentioned that each second-order block
in the cascade and parallel forms can be realized by any
of the existing distinct structures, as, for instance, one
of the direct forms shown in Fig. 9.20.
All these digital filter realizations present different
properties when one considers practical finite-precision
implementations; that is, the quantization of the coefficients and the finite precision of the arithmetic operations, such as additions and multiplications. In fact, the
analysis of the finite-precision effects in the distinct realizations is a fundamental step in the overall process of
designing any digital filter [9.2].
9.3 The Fast Fourier Transform (FFT)
The FFT (fast Fourier transform) algorithm is a faster
version of the discrete Fourier transform (DFT). FFT
utilizes some clever algorithms to do the same thing as
the DFT, but in much less time [9.2].
The DFT is extremely important in the area of frequency (spectral) analysis because it takes a discrete
signal in the time domain and transforms that signal
into its discrete frequency domain representation. Without a discrete-time to discrete-frequency transform we
would not be able to compute the Fourier transform
with a microprocessor or DSP-based (DSP: Digital Signal Processor) system [9.1, 2, 4–6].
It is the speed and discrete nature of the FFT that
allows us to analyze a signal’s spectrum, as will soon
become evident.
9.3.1 Review of Integral Transforms
We first give a review of the integral transforms that
have been used in the text, possibly in their unilateral
(single-side) version.
The bilateral Laplace transform
X.s/ D Lfx.t/g D
C1 Z
1
x.t/e
st dt; x.t/
L
X.s/ :
(9.66)
The continuous-time Fourier transform
X.i!/ D F fx.t/g D
C1 Z
1
x.t/e
i!t dt; x.t/
F
X.i!/ :
(9.67)
The bilateral Z-transform
X.z/ D Zfx.n/g
D
C1 X
nDD1
x.n/z
n
; x.n/
Z
X.z/ :
(9.68)
The Laplace transform is used to obtain a pole-zero representation of a continuous-time signal or system, x.t/,
in the s-plane. Similarly, the Z-transform is used to find
a pole-zero representation of a discrete-time signal or
system, x.n/, in the z-plane.
The continuous-time Fourier transform can be
found by evaluating the Laplace transform form at s D
i!. The picture can be extended by introducing the
discrete-time Fourier transform (DTFT). The DTFT can
be found by evaluating the Z-transform at z D exp.i˝/,
as follows
X.e
i˝
/ D
C1 X
nDD1
x.n/e
i˝n
; x.n/
DTFT
X.e
i˝
/ :
(9.69)
One needs to point out here that the frequency variable ˝ is in normalized units of radians per sample
rather than absolute units of rad=s, which apply to !
appearing in the standard Fourier transform. This can
be justified by recollecting that sequences x.n/ are generated by sampling a continuous-time signal x.t/ at
a certain sampling rate f s . In this respect, the DTFT can
be viewed as a discrete approximation of the Fourier