**NOTE: THIS DOCUMENT IS OBSOLETE, PLEASE CHECK THE NEW
VERSION:** "Mathematics of the Discrete
Fourier Transform (DFT), with Audio Applications --- Second
Edition", by Julius
O. Smith III, W3K
Publishing, 2007, ISBN 978-0-9745607-4-8. - Copyright ©
*2017-09-28* by Julius O. Smith III -
Center for Computer Research
in Music and Acoustics (CCRMA), Stanford University

- ... sample.
^{1.1} - Note that the definition of has
changed unless the
sampling rate really is 1, and the definition of has
changed no matter what the sampling rate is, since when ,
, not .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... unknowns.
^{2.1} - ''Linear'' in this context means that the unknowns are
multiplied only by constants--they may not be multiplied by each
other or raised to any power other than (e.g.,
not squared or cubed or raised to the power).
Linear systems of equations in unknowns are very easy to solve compared to
*nonlinear*systems of equations in unknowns. For example, Matlab or Mathematica can easily handle them. You learn all about this in a course on*Linear Algebra*which is highly recommended for anyone interested in getting involved with signal processing. Linear algebra also teaches you all about*matrices*which we will only introduce briefly in this course.To give you a simple first exposure, here's how the linear system of equations

looks in matrix form:

and this can be written in higher level form as

where denotes the two-by-two matrix above, and and denotes the two-by-one vectors. The solution to this equation is then

The general two-by-two matrix inverse is given by

and the inverse exists whenever (which is called the*determinant*of the matrix ) is nonzero. For larger matrices, numerical algorithms are used to invert matrices, such as used by Matlab based on LINPACK [2]. An initial introduction to matrices and linear algebra can be found in [3].. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... numbers
^{2.2} - multiplication, addition, division, distributivity of
multiplication over addition, commutativity of multiplication and
addition.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... numerical:
^{2.3} - unless you have the optional Maple package for symbolic
mathematical manipulation
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... transients.
^{3.1} - One joke along these lines, due, I'm told, to Professor
Bracewell, is that ''since the telephone is bandlimited to 3kHz,
and since bandlimited signals cannot be time limited, it follows
that one cannot hang up the telephone''.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... delay
^{4.1} - Group
delay and phase
delay are covered in the CCRMApublication
[1]
as well as in standard signal processing references [7].
In the case of an AM or FM broadcast signal which is passed through
a filter,
the
*carrier wave*is delayed by the*phase delay*of the filter, while the*modulation signal*is delayed by the*group delay*of the filter. In the case of additive synthesis, group delay applies to the amplitude envelope of each sinusoidal oscillator, while the phase delay applies to the sinusoidal oscillator waveform itself.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... bel
^{4.2} - The ''bel'' is named after Alexander Graham Bell, the inventor
of the telephone.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... intensity,
^{4.3} *Intensity*is physically*power per unit area*. Bels may also be defined in terms of*energy*, or*power*which is energy per unit time. Since sound is always measured over some*area*by a microphone diaphragm, its physical power is conventionally normalized by area, giving intensity. Similarly, the*force*applied by sound to a microphone diaphragm is normalized by area to give*pressure*(force per unit area).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
^{4.4} - The bar was originally defined as $10^-6$ atmospheres, but now
it is defined to be exactly 1 $dyne/cm^2$.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... equivalents
^{4.5} - Adapted from S. S. Stevens, F. Warshofsky, and the Editors of
Time-Life
Books,
*Sound and Hearing*, Life Science Library, Time-Life Books, Alexandria, VA, 1965, p. 173.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... distortion'').
^{4.6} - Companders (compresser-expanders) essentially ''turn down'' the
signal gain when it is ''loud'' and ''turn up'' the gain when it is
''quiet''. As long as the input-output curve is monotonic (such as
a log characteristic), the dynamic-rangecompression
can be undone (expanded).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... 0.
^{4.7} - Computers use bits, as opposed to the more familiar decimal
digits, because they are more convenient to implement in digital
hardware. For example, the
*decimal numbers*0, 1, 2, 3, 4, 5 become, in binary format, 0, 1, 10, 11, 100, 101. Each*bit*position in binary notation corresponds to a power of 2, e.g., ; while each*digit*position in decimal notation corresponds to a power of 10, e.g., . The term ''digit'' comes from the same word meaning ''finger.'' Since we have ten fingers (digits), the term ''digit'' technically should be associated only with decimal notation, but in practice it is used for others as well. Other popular number systems in computers include*octal*which is base 8 (rarely seen any more, but still specifiable in any C/C++ program by using a leading zero, e.g., decimal = 111,101,101 binary), and*hexadecimal*(or simply ''hex'') which is base 16 and which employs the letters A through F to yield 16 digits (specifiable in C/C++ by starting the number with ''0x'', e.g., 0x1ED = decimal = 1,1110,1101 binary). Note, however, that the representation within the computer is still always binary; octal and hex are simply convenient*groupings*of bits into sets of three bits (in octal) or four bits (in hex).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... processors.
^{4.8} - This information is subject to change without notice. Check
your local compiler documentation.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... feedback
^{4.9} - Normally, quantization error is computed as , where is
the signal being quantized, and is the quantized value, obtained by rounding to the
nearest representable amplitude. Filtered error feedback uses
instead the formula , where
denotes a filtering operation which ''shapes'' the quantization
noise
spectrum. An excellent article on the use of round-off error
feedback in audio digital filters is
[11].
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
''endianness'':
^{4.10} - Thanks to Bill Schottstaedt for help with this table.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...,
^{4.11} - The notation denotes a
*half-open interval*which includes but not .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ....
^{4.12} - Another term commonly heard for ''significand'' is
''mantissa.'' However, this use of the term ''mantissa'' is not the
same as its previous definition as the fractional part of a
logarithm. We will therefore use only the term ''significand'' to
avoid confusion.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... bias.
^{4.13} - By choosing the bias equal to half the numerical dynamic range
of (thus
effectively inverting the sign bit of the exponent), it becomes
easier to compare twofloating-point
numbers in hardware: the entire floating-point word can be
treated by the hardware as one giant integer for numerical
comparison purposes. This works because negative
exponents correspond to floating-point numbers less than 1 in
magnitude, while. positive exponents correspond to floating-point
numbers greater than 1 in magnitude.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... CODEC
^{4.14} - CODEC is an acronym for ''COder/DECoder''.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... (LTI
^{5.1} - A system is
said to be
*linear*if for any two input signals and , we have . A system is said to be*time invariant*if , where . This subject is developed in detail in [1].. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... filter.
^{5.2} - Technically, this is the
*feedforward comb filter*, also called the ''inverse comb filter'' [14]. The longer names are meant to distinguish it from the*feedback comb filter*(defined as ''the'' comb filter in Dodge and Jerse [15]). In the feedback comb filter, the delay output is fed*back*around the delay line and summed with the delay input instead of the input being fed*forward*around the delay line and summed with its output. The frequency response of the feedforward comb filter is the inverse of that of the feedback comb filter (one will cancel the effect of the other), hence the name ''inverse comb filter.'' When the delay in the feedforward comb filter is varied slowly over time, the*flanger effect*is obtained. Flanging was originally achieved by mixing the outputs of two LP record turntables and changing their relative speeds by alternately touching the ''flange'' of each turntable to slow it down.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... name.
^{5.3} - While there is no reason it should be obvious at this point,
the comb-filter gain varies in fact sinusoidally between
and
. It
looks more "comb" like on a dB amplitude
scale, which is more appropriate for audio applications.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... dc
^{5.4} - ''dc'' means ''direct current'' and is an electrical
engineering term for ''frequency
''.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... dB.
^{5.5} - Recall that a gain factor is
converted to
*decibels*(dB) by the formula .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... signal.
^{5.6} - In complex variables, ''analytic'' just means differentiable of
all orders. Therefore, one would expect an ''analytic
signal'' to simply be any signal which is differentiable of all
orders at any point in time, i.e., one that admits a fully valid
Taylor expansion about any point in time. However,
*all*bandimited signals (being sums of finite-frequency sinusoids) are analytic in the complex-variables sense. Therefore, the signal processing term ''analytic signal'' is somewhat of a misnomer. It is included in this chapter only because it is a commonly used term in engineering practice.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... shift.
^{5.7} - This operation is actually used in some real-world AM and FM
radio receivers (particularly in digital radio receivers). The
signal comes in centered about a high ''carrier frequency'' (such
as 101 MHz for radio station FM 101), so it looks very much like a
sinusoid at frequency 101 MHz. (The frequency modulation only
varies the carrier frequency in a relatively tiny interval about
101 MHz. The total FM bandwidth including all the FM ''sidebands''
is about 100 kHz. AM bands are only 10kHz wide.) By delaying the
signal by 1/4 cycle, a good approximation to the imaginary part of
the analytic signal is created, and its instantaneous amplitude and
frequency are then simple to compute from the analytic signal.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
^{5.8} - If were
constant, this would be exact.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...demodulation
^{5.9} *Demodulation*is the process of recovering the modulation signal. For amplitude modulation (AM), the modulated signal is of the form , where is the ''carrier frequency'', is the amplitude envelope (modulation), is the modulation signal we wish to recover (the audio signal being broadcast in the case of AM radio), and is the modulation index for AM.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
^{5.10} - The notation denotes a single
*sample*of the signal at sample , while the notation or simply denotes the*entire signal*for all time.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... projection
^{5.11} - The coefficient of projection of a signal onto
another signal
can be thought of as a measure of how much of is
present in . We
will consider this topic in some detail later on.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
^{6.1} - We'll use an underline to emphasize the vector interpretation,
but there is no difference between and
. For purposes of this course, a
*signal*is the same thing as a vector.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... vector.
^{6.2} - You might wonder why the norm
of is not written as .
There would be no problem with this since
is undefined. However, the historically adopted notation is instead
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... filter.
^{7.1} - More precisely, is a length finite-impulse-response
(FIR) digital filter. See §8.7
for related discussion.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... computed,
^{7.2} - We call this the
*digital sinc function*to distinguish it from the*sinc function*.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... element
^{7.3} - We are now using as an integer counter, not as .
This is standard notational practice.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... argument.
^{7.4} - Alternatively, it can be extended to the complex case by
writing , so that includes a conjugation of the elements of . This
difficulty arises from the fact that matrix
multiplication is really defined without consideration of
conjugation or transposition at all, making it unwieldy to express
in terms of inner
products in the complex case, even though that is perhaps the
most fundamental interpretation of a matrix
multiply.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... spectra
^{8.1} - A spectrum is mathematically identical to a signal, since both
are just sequences of
complex numbers. However, for clarity, we generally use
''signal'' when the sequence index is considered a time index, and
''spectrum'' when the index is associated with successive frequency
samples.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... convolution.
^{8.2} - To simulate acyclic convolution,
as is appropriate for the simulation of sampled continuous-time
systems, sufficient zero
padding is used so that nonzero samples do not ''wrap around''
as a result of the shifting of in the
definition of convolution. Zero padding is discussed later in this
reader.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ....
^{8.3} -
Matched filtering is briefly discussed in §8.8.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... times.
^{8.4} - You might wonder why we need this since all indexing is defined
modulo already.
The answer is that formally expresses a mapping from the space of
length signals to
the space of length signals.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... transform
^{8.5} - The discrete cosine transform (DCT) used often in applications
is actually defined somewhat differently, but the basic principles
are the same
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... transform
^{8.6} - The FFT is just a fast implementation of the DFT.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... Dual
^{8.7} - In general, the
*dual*of any Fourier operation is obtained by interchanging time and frequency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... domain,
^{8.8} - The inverse DFT of the rectangular window here is an
aliased, discrete-time counterpart of the
*sinc function*which is defined as ''.'' The sinc function is covered inMusic 420.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... system
^{8.9} - We use the term ''system'' interchangeably with ''filter.''
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... domain.
^{8.10} - Note that we normally say the sampling rate in the time domain
must be higher than
*twice*the highest frequency in the frequency domain. From the point of view of this course, however, we may say instead that sampling rate in the time domain must be greater than the*full spectral bandwidth*of the signal, including both positive andnegative frequencies. From this simplified point of view, ''sampling rate = bandwidth supported.''. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ....
^{A.1} - Mathematically, can be allowed to be nonzero over points
provided that the set of all such points have
*measure zero*in the sense of Lesbegue integration. However, such distinctions do not arise for practical signals which are always finite in extent and which therefore have continuous Fourier transforms. This is why we specialize Shannon's Sampling Theorem to the case of continuous-spectrum signals.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .