# Footnotes

## GUIDE: Mathematics of the Discrete Fourier Transform (DFT) - Julius O. Smith III. Footnotes

It appears that you are using AdBlocking software. The cost of running this website is covered by advertisements. If you like it please feel free to a small amount of money to secure the future of this website.

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].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... numbers2.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... 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''.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... delay4.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 themodulation 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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bel4.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 somearea 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 givepressure (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$.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... equivalents4.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. Eachbit position in binary notation corresponds to a power of 2, e.g., ; while eachdigit 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 includeoctal 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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... feedback4.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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... CODEC4.14
CODEC is an acronym for ''COder/DECoder''.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... (LTI5.1
A system is said to belinear 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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... dc5.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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...demodulation5.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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... projection5.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 thedigital sinc function to distinguish it from the sinc function .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... element7.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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... spectra8.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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... transform8.5
The discrete cosine transform (DCT) used often in applications is actually defined somewhat differently, but the basic principles are the same
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... transform8.6
The FFT is just a fast implementation of the DFT.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... Dual8.7
In general, thedual 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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... system8.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 thefull 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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.