Sundararaja D. The Discrete Fourier Transform. Theory, Algorithms and Applications
Подождите немного. Документ загружается.
Glossary
Algorithm A systematic procedure that provides a solution to a problem.
Aliasing The impersonating of high frequency sinusoids as low frequency
sinusoids in the frequency-domain representation of a signal due to
sampling the signal, in the time-domain, with a sampling interval
that is not small enough. A similar phenomenon occurs in the
time-domain.
Angular frequency
2-K
times the cyclic frequency. For continuous-time
signals, the unit is radians per second. For discrete signals, the unit
is radians per sample.
Bit-reversed order The order obtained by reversing the bits of the binary
representation of a set of naturally ordered decimal digits.
Complex amplitude A complex number containing the amplitude and
phase of a complex sinusoid.
Complex conjugate The complex number obtained by negating the imag-
inary part of a complex number.
Complex number An ordered pair of real numbers consisting, respec-
tively, of the a;-axis and y-axis components of a vector. The ar-axis
component is referred as the real part of the complex number and
the
y-axis
component is referred as the imaginary part.
Complex signal An ordered pair of real signals.
Continuity A signal x(t) is said to be continuous at t = to, if it is denned
throughout \t
—
to\ < St for some positive St and lim
t
_>.t
0
x(t) =
x(t
0
).
Continuous-time signal A signal that is defined at all instants of time.
365
366 Glossary
Cosine waveform The projection, on the x-axis from time t = — oo to
t = oo, of a point moving with uniform angular velocity in the
counterclockwise direction around a circle with center at the origin
such that the longest projection on the positive side of the x-axis
occurs at time t — 0. The radius of the circle and the angular
velocity, respectively, are the amplitude and angular frequency of
the waveform.
Cyclic frequency The reciprocal of the period of a periodic signal. For
continuous-time signal the unit is Hz (cycles per second). For dis-
crete signals the unit is cycles per sample. Note that the cyclic
frequency of a discrete signal is equal to the reciprocal of its period
only if the waveform makes one cycle during a period. Otherwise,
the cyclic frequency is equal to the ratio of the number of cycles
during a period and the period.
Decimation-in-frequency DFT algorithm A type of algorithm in which
the given input data is combined to form several smaller groups of
input data, the DFT of each of which represents mutually exclusive
groups of the frequency coefficients of the given input data.
Decimation-in-time DFT algorithm A type of algorithm in which the
frequency coefficients of smaller DFTs of mutually exclusive groups
of input data are combined to form the frequency coefficients of the
given input data.
Digital signal A signal that is defined only at discrete intervals of time
and its amplitude defined only at certain discrete values.
Discrete complex sinusoid x(n) = e-
7
^*™: With k and N integers, a
periodic set of complex numbers having real and imaginary parts,
respectively, the sample values of cos(^fcn) and sin(^-/cn).
Discrete Fourier transform A transformation that yields an TV—point
frequency-domain sequence corresponding to an N—point time-
domain sequence. The JV-point frequency-domain sequence, called
the frequency coefficients, represents the time-domain sequence in
terms of a set of harmonically related discrete sinusoids.
Discrete signal A signal that is defined only at discrete intervals of time.
Fourier series The representation of a continuous-time periodic signal in
terms of a set of infinite sinusoids having harmonically related fre-
quencies.
Glossary 367
Fourier transform The representation of a continuous-time aperiodic sig-
nal in terms of a set of infinite sinusoids with continuum of frequen-
cies.
Frequency coefficient The amplitude and phase (or the amplitudes of
the cosine and sine components) of a sinusoid at a given frequency.
Frequency-domain signal representation The representation of a sig-
nal in terms of its frequency components.
Fundamental harmonic The sinusoidal component of an arbitrary peri-
odic signal whose period is the same as that of the signal.
Harmonic Any of the sinusoidal components of a periodic signal.
Harmonic (Fourier) analysis The decomposition of an arbitrary peri-
odic waveform into its constituent harmonically related sinusoids.
Harmonically related sinusoids A set of sinusoids whose frequencies
are an integral multiple of the frequency of the fundamental har-
monic.
Harmonic (Fourier) synthesis The building up of a complex periodic
waveform by summing a set of harmonically related sinusoids.
In-place computation The implementation of an algorithm in which the
memory required for storing the data values is equal to the size of
the input data.
Leakage effect The leakage of energy to adjacent frequencies in the spec-
trum of a signal due to the selection of an inappropriate record
length in the time-domain. A similar phenomenon occurs in the
time-domain.
Linear time-invariant system A system which obeys the superposition
theorem and the response of which, for a specific input signal, does
not change with time.
Periodic sequence A sequence x{n) is periodic with a period N if x(n +
aN) = x(n), where a is any integer.
Phase shift The phase shift of a sinusoid is the amount of right or left shift
a cosine waveform has to be shifted in order to get the sinusoid.
Picket-fence effect The inability of the DFT to present the continuous
spectrum of an aperiodic signal due to the representation of fre-
quency components only at discrete intervals.
PM DFT algorithms A family of fast DFT algorithms in which the com-
putation of a form of the DFT equation, with the input and output
quantities represented as vectors, is decomposed into several stages
of computation.
368
Glossary
Radix-2 algorithm A type of algorithm in which a problem is split into
two smaller independent problems of the same type, each of half
the size, recursively from the input or output end. The solution of
two smaller problems are combined to form the solution of a larger
problem.
SFG The signal-flow graph (SFG) is a pictorial description of an algorithm
using nodes and arrows and it is the most effective way of describing
DFT algorithms.
Sine function The general form of the sine function, which is even, is
s
'"^ ', having a peak value of unity at t
—
0 and a waveform similar
to an exponentially damped sinusoid at either side of the origin. It
has zero crossings at points where t is equal to an integral multiple
of 7r.
Sine waveform A cosine waveform with a phase shift of
—
f radians or
-90 degrees.
Sinusoid A cosine or a sine waveform with arbitrary phase shift. A linear
combination of the sine and cosine waveforms of the same frequency.
Time-domain signal representation The representation of a signal in
terms of its amplitude at instants of time.
Twiddle factor A complex number that is a root of unity.
Windows A set of special functions used to modify a truncated time-
domain signal in order to reduce the leakage of energy to adjacent
frequencies in its frequency-domain representation. Windows are
also used in the frequency-domain.
Uniform convergence For a given tolerance 6 > 0, for all t in the given
interval, there exists an N such that \x(t)
—
x
n
(t)\
< 5, for n> N,
where x
n
(t) is the series representation of x(t) with the first n
terms.
Unit circle The circle with center at the origin and radius one.
Zero padding When modeling a finite aperiodic time-domain signal, padding
with zeros at the end makes the signal more closer to the true signal
and reduces the frequency increment making the spectrum denser.
It can be used in the frequency-domain also. Zero padding is also
used to simulate a linear convolution by a circular convolution.
Index
aliasing, 197, 226, 254
folding frequency, 227
folding of frequencies, 229
highest frequency component, 227
reducing the aliasing effect, 231
sampling frequency, 227
sampling rate, 227
sampling theorem, 227
time-domain, 228
antihermitian symmetry, 71
basis functions
DCT, 304
DFT, 40
DWT, 314
NDHT, 320
SDHT, 326
bit-reversal, 343
algorithm, 345
bit-reversed order, 128, 344
number system, 343
butterfly computation, 123
complete representation, 58
complex amplitude, 22
complex exponential function, 22, 46,
199,
337
complex numbers, 333
argument, 335
exponential form, 335
imaginary part, 334
imaginary unit, 334
magnitude, 335
operations
addition, 334
conjugation, 335
multiplication, 335
subtraction, 334
polar form, 335
real part, 334
rectangular form, 334
roots,
336
complex plane, 333
computation of a single DFT
coefficient, 130
computational complexity, 341
continuous-time signal, 7
convergence, 251
convolution
circular, 289
frequency-domain, 84
time-domain, 83
linear, 288
simulation by DFT, 290
overlap-save method, 292
convolution, 2-D
circular, 296
spatial frequency-domain, 209
spatial time-domain, 208
linear, 295
369
370
Index
overlap-save method, 296
correlation, 298
circular
auto,
85, 210
cross,
85, 209
cosine function, 8, 12, 47, 200, 337
DCT, see discrete cosine transform
decimation-in-frequency, 114, 132
decimation-in-time, 108, 132
DFT, see discrete Fourier transform
digital signal, 8
Dirichlet conditions, 249
discontinuity, 251
discrete cosine transform
basis functions, 305
orthogonality, 304
computation using the DFT, 306
computational complexity, 309
definition, 305
discrete cosine transform, 2-D, 309
discrete Fourier transform
basis functions, 40
center-zero format, 43
complex exponential, 46
computation with vectors, 101
dc,
45
definition, 37, 38
direct computation, 51
direct implementation, 51
frequency increment, 40
Hann function, 49
impulse, 44
kernel matrix, 43
properties
see properties of the DFT
real data
algorithm for complex data,
163
single real data set, 169
two real data sets, 166
real sinusoid, 46
rectangular waveform, 49
vector format, 96, 99, 100
discrete Fourier transform, 2-D
center-zero format, 196
complex exponential, 199
computation
algorithms, 212
real data, 217
row-column method, 202
definition, 195
impulse, 197
properties
see properties of the 2-D DFT
real sinusoid, 199
discrete signal, 7
discrete Walsh transform, 313
basis functions, 314
definition, 313
orthogonality, 315
PM DWT algorithm, 316
sequency, 314
discrete Walsh transform, 2-D, 318
DWT, see discrete Walsh transform
Euler's identity, 337
even function, 15, 71
even half-wave symmetry, 71
finality of coefficients, 57
Fourier analysis, 32
Fourier Series, 1-D, 249
aliasing effect, 254
approximatation by DFT, 253
continuous-time frequency, 257, 260
convergence, 251
Dirichlet conditions, 249
exponential form, 250
Gibbs phenomenon, 251, 261
sample value at a discontinuity, 257
trigonometric form, 250
waveform reconstruction , 259
Fourier Series, 2-D, 262
Fourier synthesis, 32, 35
Fourier transform, 1-D, 273
approximation by DFT, 277
complex exponential, 276
Index
371
dc signal, 276
definition, 276
impulse, 276
limiting case of the FS, 273
pulse, 275, 277
real sinusoid, 276
relation between FS and FT, 275,
277
signal reconstruction, 281
Fourier transform, 2-D, 282
frequency composition
1-D real signals, 37
2-D real signals, 196
frequency-domain, 10
Gibbs phenomenon, 251, 261
Hamming window, 240
Hann window, 239
hermitian symmetry, 71
IDFT, see inverse discrete Fourier
transform
impulse, 9
inverse discrete Fourier transform
center-zero format, 43
computation using DFT, 104, 111
definition, 37, 39
direct computation, 51
vector format, 104
inverse discrete Fourier transform,
2-D
center-zero format, 196
definition, 195
inverse discrete Walsh transform
definition, 316
inverse naturally ordered discrete
Hadamard transform, 322
inverse sequency ordered discrete
Hadamard transform, 326
l'hopital's
rule, 263, 356
leakage effect, 231
frequency response
DFT, 235
rectangular and Hann
windows, 240
Multiplication of the signal with a
rectangular window, 233
reduction of leakage, 244
spectral resolution, 241
windows, see windows
least squares error, 55-57, 257
naturally ordered discrete Hadamard
transform, 320
basis functions, 320
definition, 320
kernel generation, 321
PM NDHT algorithm, 322
naturally ordered discrete Hadamard
transform, 2-D, 323
NDHT, see naturally ordered discrete
Hadamard transform
odd function, 15, 71
odd half-wave symmetry, 71
orthogonality, 24, 26
complex exponential, 26
cosines over half-cycles, 304
trigonometric functions, 24
Walsh function, 315
overlap-save method, 292, 296
Parseval's theorem, 90, 212
periodicity, 62
phase shift, 11, 12
picket-fence effect, 244
denser spectrum, 245
PM DFT Algorithms, classification,
114
PM DIF DFT algorithms
2 x 1 PM DIF DFT algorithm, 134
butterfly, 134
computational stages, 135
2 x 2 PM DIF DFT algorithm, 154
butterfly, 157
computational stages, 157
372
Index
it x 1 PM DIF DFT algorithms, 132
butterfly, 133
computational stages, 134
PM DIF DFT Algorithms,
fundamentals, 112
2 x 1 PM DIF DFT algorithm, 114
compression of data vectors, 113
shift of transform vectors, 112
PM DIF RIDFT algorithms
2 x 1 PM DIF RIDFT algorithms,
180
butterfly, 183
computational stages, 184
special butterflies, 184
2 x 2 PM DIF RIDFT algorithms,
190
butterfly, 190
computational stages, 191
special butterflies, 192
storage of data, 176
PM DIT DFT algorithms
2 x 1 PM DIT DFT algorithm, 125
butterfly, 125
computation of a single DFT
coefficient, 130
computational complexity, 135
computational stages, 126
flow chart description, 141
implementation issues, 148
reordering of the input data,
128
2 x 2 PM DIT DFT algorithm, 151
butterfly, 153
computational complexity, 158
computational stages, 154
6 x 1 PM DIT DFT algorithm, 138
butterfly, 139
computational complexity, 140
computational stages, 140
tixlPM DIT DFT algorithms,
122
butterfly, 123
computational stages, 124
PM DIT DFT Algorithms,
fundamentals, 106
2 x 1 PM DIT DFT algorithm, 108
shift of data vectors, 106
zero padding of data vectors, 107
PM DIT RDFT algorithms
2 x 1 PM DIT RDFT algorithms,
176
butterfly, 177
computational stages, 178
special butterflies, 178
2 x 2 PM DIT RDFT algorithms,
187
butterfly, 187
computational stages, 187
special butterflies, 189
comparison with DFT algorithms,
193
storage of data, 175
prime-factor DFT algorithm, 139, 347
properties of the 2-D DFT
complex conjugates, 208
convolution, see convolution
correlation, see correlation
difference, 210
image rotation, 210
linearity, 205
Parseval's theorem, 212
periodicity, 205
reversal property, 207
separable signals, 211
spatial circular shift of a spectrum,
206
spatial circular shift of an image,
206
sum and difference of sequences,
210
symmetry, 207
properties of the DFT
circular shift of a spectrum, 66
circular shift of a time sequence, 62
complex conjugates, 81
DFT of overlapping segments, 66
DFT twice in succession, 70
duality, 71
Index
373
linearity, 61
padding the data with zeros, 86
at the end, 86
in between the samples, 89
Parseval's theorem, 90
periodicity, 62
signal defined over a finite range,
80
sum and difference of sequences, 85
symmetry, complex signal, 78
even, 78
even half-wave, 80
odd, 80
odd half-wave, 80
symmetry, imaginary signal, 75
even, 76
even half-wave, 76
odd, 76
odd half-wave, 78
symmetry, real signal, 72
even, 74
even half-wave, 75
odd, 74
odd half-wave, 75
time-reversal, 69
rectangular window, 236
roots of unity, 40, 336
rotating vector, 339
row-column method, 202, 309
sampling frequency, 227
sampling rate, 227
sampling theorem, 227
SDHT, see sequency ordered discrete
Hadamard transform
sequency, 314
sequency ordered discrete Hadamard
transform, 325
basis functions, 326
definition, 325
PM SDHT algorithm, 327
sequency ordered discrete Hadamard
transform, 2-D, 328
signal
continuous-time, 7
digital, 8
discrete, 7, 9
signal representation
frequency-domain, 10, 11
time-domain, 7, 10, 11
signal-flow graph, 97
sine function, 240, 252
sine function, 8, 12, 47, 200, 337
sinusoid, 11
amplitude, 11-13
angular frequency, 12
complex, 21, 22
cosine, 8, 12
cyclic frequency, 12
even function, 15
harmonically related, 19
harmonics, 19
highest frequency, 18
odd function, 15
orthogonality, 24, 26
period, 12
periodicity, 17, 18
phase shift, 11-13
phase-shifted cosine, 12
phase-shifted sine, 12
polar form, 12
rectangular form, 14
representation with a rotating
vector, 337
representation with two rotating
vectors, 339
sine,
8, 12
sum of sinusoids, 16, 19, 20, 22
sinusoidal representation of signals
advantages, 54
sinusoidal surface, 196
spectral density, 275
spectral resolution, 241
spectrum, 23
amplitude and phase, 23
real and imaginary parts, 23
symmetry