Fourier Analysis - Signal Processing for Communications - page 93

W to reduce the number of operations to N log .Inmatrixformthisis

equivalent to decomposing W into the product of a series of matrices with
mostly zero or unity elements. The algorithmic details of the FFT can be
found in the bibliography; we canmention, however, that the FFT algorithm
is particularly efficient for data lengths which are a power of 2 and that, in
general, the more prime factors the data length can be decomposed into,
the more efficient the FFT implementation.

( N )

l g r , y i d . , © , L s

4.7.3 Cosmetics: Zero-Padding

FFT algorithms are tailored to the specific length of the input signal. When
the input signal's length is a large prime number or when only a subset of
FFT algorithms is available (when, for instance, all we have is the radix-2
algorithm, which processes input vectors with lengths of a power of 2) it is
customary to extend the length of the signal to match the algorithmic re-
quirements. This is usually achieved by zero padding , i.e. the length- N data
vector is extended to a chosen length M by appending zeros to it.

Now, the maximum resolution of an N -point DFT, i.e. the separation be-
tween frequency components, is 2

( M − N )

N . By extending the signal to a longer
length M , we are indeed reducing the separation between frequency com-
ponents. One may think that this artificial increase in resolution allows the
DFT to show finer details of the input signal's spectrum. It is not so.
The M -point DFT X ( M ) of an N -point data vector x ,obtainedviazero-
padding, can be obtained directly from the “canonical” N -point DFT of the
vector X ( N ) via a simple matrix multiplication:

π/

X ( M ) = M M , N X ( N ) (4.86)

where the M × N matrix M M , N is given by

M M , N = W M W N
where W N is the standard DFTmatrix and W M is the M N matrix obtained

by keeping just the first N columns of the standard DFT matrix W M .The
fundamental meaning of (4.86) is that, by zero padding, we are adding no
information to the spectral representation of a finite-length signal. Details
of the spectrum which were not apparent in an N -point DFT are still not
apparent in a zero-padded version of the same. It can be shown that (4.86)
is a form of Lagrangian interpolation of the original DFT samples; therefore
the zero-padded DFT is more attractive in a “cosmetic” fashion since the
new points, when plotted, show a smooth curve between the original DFT
points (and this is how plots such as the one in Figure 4.18 are obtained).

×