Sines & Spectra

1 Superposition: signals add

Air is a linear medium to a very good approximation: when two sounds occur at once, the pressure deviation at any point and instant is the sum of the deviations each sound would produce alone. Microphones and speakers are also approximately linear. A recording of several simultaneous sources is therefore the sample-by-sample sum of the recordings of each source. A mixture of pure tones is

$A_1, A_2, A_3$ are the amplitudes of the components and $f_1, f_2, f_3$ their frequencies in hertz. The factor $2\pi$ converts cycles to radians: $f\,t$ counts elapsed cycles, and the sine function takes an angle parameterization ↗.

The mixer below synthesizes this sum and plays it. One audible consequence is worth isolating before anything else, because it shows that the equation makes testable predictions. When two components have equal amplitude and nearly equal frequency, the sum-to-product identity applies (one of the standard trigonometric identities, stated here without proof; section 3's rotating-point picture is the tool that makes such identities geometric):

The right side is a single tone at the average frequency whose amplitude is modulated by a slow cosine. The envelope peaks twice per cosine cycle, so the loudness rises and falls $|f_1 - f_2|$ times per second. The identity therefore predicts that a 440 Hz tone and a 444 Hz tone together pulse exactly 4 times per second. The beats preset sets these values, the readout computes $|f_1 - f_2|$, and the pulsing is audible while the sum plays.

2 Amplitude, frequency, and phase

Section 1 used sinusoids with two parameters. The general sinusoid has three:

$A$ is the amplitude (the size of the swing), $f$ is the frequency in hertz, and $\varphi$ is the phase, an angle offset in radians parameterization ↗. Adding $\varphi$ inside the sine shifts the waveform earlier in time by $\varphi / (2\pi f)$ seconds, without changing its shape, amplitude, or frequency. The widget's first readout computes this time shift from the slider values.

In the widget below, the dim trace is a fixed reference sinusoid ($A = 0.70$, $f = 3$ Hz, $\varphi = 0^\circ$) and the bright trace is adjustable. Matching the reference's amplitude and frequency and then dragging the phase slider shows what phase is: the same waveform, slid along the time axis. At $\varphi = 360^\circ$ the two traces coincide again, because a full-cycle shift is no shift at all.

Phase matters to everything that follows for one reason: a recording can begin at any instant, so the phase of every component in a real signal is arbitrary and unknown. A procedure that measures “how much 5 Hz is in this signal” must return the same answer for every possible $\varphi$. Sections 5–7 build such a procedure.

3 The rotating-point picture

All three parameters of a sinusoid describe one geometric object. A point moves around a circle of radius $A$ at $f$ revolutions per second, starting at angle $\varphi$. Its height above the circle's center at time $t$ is $A\sin(2\pi f t + \varphi)$, which is the general sinusoid of section 2. Its horizontal position is $A\cos(2\pi f t + \varphi)$. The demo records both coordinates while the point rotates: the vertical projection, traced to the right, is the sine wave; the horizontal projection, traced downward, is the cosine wave, which is the same waveform a quarter cycle ahead.

The correspondence runs both directions. Every sinusoid can be regarded as a rotating point seen edge-on, with amplitude as the radius, frequency as the rotation rate, and phase as the starting angle. The circle returns twice in this course: in section 7, where a pair of measurements traces exactly this circle, and in section 11, where the DFT's internal values lie on it.

4 Building waveforms from harmonics

Sections 1–3 treated sinusoids as components to be summed. This section substantiates the claim that they are sufficient components: sums of sinusoids can reproduce any repeating waveform to any desired accuracy. For a waveform that repeats with period $1/f_0$, the only sinusoids needed are the harmonics, the sinusoids at whole-number multiples of the fundamental frequency $f_0$:

$m$ counts harmonics: $m = 1$ is the fundamental, $m = 2$ the second harmonic at twice the frequency, and so on. The amplitudes $A_m$ and phases $\varphi_m$ specify the waveform completely. Only multiples of $f_0$ appear because any other frequency would fail to repeat with period $1/f_0$. This expansion is the Fourier series; this course demonstrates it rather than proving it.

The demo targets three standard waveforms. A square wave, for example, is built from odd harmonics with amplitudes proportional to $1/m$. The slider sets how many harmonics are included: with one, the sum is a plain sinusoid; with a few, the flat tops and steep edges emerge; with twenty, the square wave is unmistakable. The remaining ripple concentrates at the jumps and narrows as harmonics are added without disappearing entirely, an effect known as the Gibbs phenomenon, visible here as small overshoots at each edge.

The same sum is audible. The audio plays the partial sum at a 110 Hz fundamental, and adding harmonics sharpens the timbre from a pure tone toward a buzz while the pitch stays fixed: pitch follows the fundamental, and timbre follows the harmonic amplitudes and phases. The reverse problem is now concrete: given a recorded waveform, recovering the $A_m$ and $\varphi_m$ that built it. That measurement is the subject of Part II.

5 Correlation: measuring similarity

Part II begins with the basic measurement. The resemblance between a signal and a template waveform is measured by multiplying them pointwise and averaging the products. Where the two have the same sign (both positive or both negative) the products are positive; where they disagree, the products are negative. A template that stays aligned with the signal produces a large average; one that drifts in and out of alignment cancels itself. The widget shows this directly: the bottom band is the pointwise product, and the readout is its average.

$x[n]$ is the $n$-th sample of the signal, $g[n]$ the $n$-th sample of the template, and $N$ the number of samples in the window. This quantity is the correlation of x with g, and it is the number the widget's readout has been computing. Every measurement in the rest of this course is a correlation with some template.

6 Orthogonality: one frequency at a time

Section 5's widget suggests a pattern: mismatched whole-cycle frequencies do not merely correlate weakly; they correlate to exactly zero. The product-to-sum identity $\sin A \sin B = \tfrac{1}{2}[\cos(A-B) - \cos(A+B)]$ explains why: the product of two sinusoids is a pair of cosines at the difference and sum frequencies, and a cosine averaged over a whole number of its own cycles is zero. When the frequencies differ, both cosines average away. When they match, the difference-frequency cosine is $\cos 0 = 1$, a constant that survives:

Both frequencies are whole numbers of cycles per window. The zero case is called orthogonality, and the idea is general: two signals are orthogonal whenever their correlation is exactly zero, so that a correlation against one registers nothing of the other. Different whole-cycle frequencies form one orthogonal pair; section 7 uses another, sine and cosine at the same frequency. Orthogonality's value here comes from superposition (section 1) plus one line of algebra (correlation distributes over sums): the correlation of a sum of components with one template is the sum of the correlations of the components taken separately, and orthogonality removes every term except the matching one. A correlation against frequency $k$ therefore measures the $k$-component alone, regardless of what else the signal contains.

The demo applies this to a fixed mixture of three sinusoids: amplitudes 0.80, 0.50, and 0.30 at 4, 11, and 17 cycles per window. Correlating against one template frequency at a time gives $A/2$ at each match (the $1/2$ from the equation above, scaled by the component's amplitude) and zero everywhere else. Doubling each correlation recovers the amplitudes themselves. Sweeping $k$ by hand fills in a bar chart one measurement at a time; the “run all” button completes it. The result is the full set of component amplitudes, reconstructed by correlation alone. A chart of recovered amplitude against frequency is called a spectrum.

7 The phase problem and the two-template fix

Section 6's sweep worked because every component had phase zero. Section 2 established that real phases are arbitrary, and the sine template fails on exactly this point: for a signal $A\sin(2\pi f t + \varphi)$, setting $\varphi$ to $90^\circ$ drives the sine correlation to zero even though the frequency matches, because $\sin A \cos A = \tfrac{1}{2}\sin 2A$ also averages to zero over whole cycles. A component shifted by $90^\circ$ therefore produces zero correlation with the sine template and the largest possible correlation with the cosine template. Correlating against both gives two numbers that trade off as the phase turns:

Whatever $\varphi$ is, the two correlations are the legs of a right triangle with hypotenuse $A/2$, so the amplitude is recovered from the pair: $A = 2\sqrt{\langle x,\sin\rangle^2 + \langle x,\cos\rangle^2}$. In the widget, the recovered-amplitude readout holds constant while the phase slider sweeps; this is the phase-independent measurement that section 2 required.

The widget also plots the pair $(\langle x,\sin\rangle,\ \langle x,\cos\rangle)$ as a point in a plane. As the phase slider turns, the point travels a circle of radius $A/2$ at angle $\varphi$; this is section 3's rotating point, reappearing as measurement data. A pair of numbers that is naturally one point calls for arithmetic on points, which is what complex numbers provide complex numbers ↗. Written as a complex number, the unit-circle point at angle $\theta$ is $e^{i\theta}$ by Euler's formula Euler's formula ↗, and the two correlations combine into a single correlation against a complex template:

The complex template $e^{-i 2\pi f t} = \cos(2\pi f t) - i \sin(2\pi f t)$ carries the cosine in its real part and the sine, negated, in its imaginary part, so one correlation computes both numbers at once. Its magnitude is the $A/2$ just measured, and its angle differs from $\varphi$ by a fixed quarter turn, so it determines $\varphi$; the plane above orders its axes as (sine, cosine) precisely so that the plotted point lands at angle $\varphi$. The concept pages build $e^{i\theta}$ from the ground up; a reader new to complex numbers can read the two linked pages (complex numbers first, then Euler's formula, about twelve minutes) and rejoin here. The lesson itself only requires the two facts demonstrated here: the pair recovers $A$ at any phase, and the pair is one complex number.

8 The discrete Fourier transform

Every piece is now in place. Section 6 swept a sine template across frequencies and read off a spectrum; section 7 replaced the sine template with the complex template so that the answer is the same at every phase. Running that phase-independent measurement at every whole-cycle frequency $k$, using sums rather than averages, is the discrete Fourier transform:

The exponent is built from the inside out: $n/N$ is the fraction of the window elapsed at sample $n$; $kn/N$ is the number of cycles the $k$-cycle template has completed at that point; $2\pi$ converts cycles to radians parameterization ↗; and $e^{-i(\cdot)}$ is section 7's complex template at that angle Euler's formula ↗. The DFT is $N$ correlations, one per template frequency, each computed as in sections 5–7.

Two bookkeeping facts connect $X[k]$ to the spectrum charts already drawn. The first is scaling: section 7 measured $A/2$ using an average, while the DFT uses a sum, which is $N$ times larger, so a component of amplitude $A$ produces $|X[k]| = \tfrac{N}{2} A$. The chart below divides by $N/2$ and reads directly in amplitude units, which is why a slider set to 0.80 produces a bar of height 0.80. The second is range. Each slot of the output, called a bin, holds the measurement at one whole-cycle frequency, and bin $k = 0$ holds the signal's average value. For real-valued signals the bins above $N/2$ mirror those below, and one mechanism explains the whole arrangement: a real sinusoid of amplitude $A$ correlates equally with the templates at $k$ and $N-k$, which visit the same template values in opposite directions (standard texts call the upper half the negative frequencies), so its energy splits evenly between the two bins. That even split is the origin of section 7's $A/2$, the reason the chart's divisor recovers $A$, and the source of the mirror symmetry. The “show all bins” toggle displays the upper half. The informative range is $k = 0$ to $N/2$, and adjacent bins are one cycle per window apart, so a longer window gives finer frequency resolution at the cost of merging everything that happens inside the window into one spectrum.

The noise slider adds an independent random value to every sample. Random noise spreads its energy approximately evenly across all bins, while a sinusoid concentrates its energy in one bin, so a tone that is invisible in the waveform view remains plainly visible in the spectrum.

9 Filtering in the frequency domain

A signal expressed as bins can be edited per bin. A filter multiplies each bin by a gain $H[k]$:

$H[k] = 1$ keeps bin $k$, $H[k] = 0$ removes it, and intermediate values attenuate it. An ideal low-pass filter sets $H[k] = 1$ up to a cutoff bin and $0$ above it; its mirror image, a high-pass filter, zeroes the bins below a cutoff instead, which removes a low rumble while keeping everything above it. An equalizer applies a smoothly varying $H[k]$.

Edited bins are only useful if they can be converted back into samples, which requires inverting the transform. The inverse DFT rebuilds each sample from the bins:

The structure matches the forward transform with the rotation direction reversed and a $1/N$ normalization. Forward then inverse returns the original samples exactly: the DFT is a change of representation, which is what makes editing in the middle exact. The demo below runs precisely this forward–edit–inverse chain to draw the filtered waveform.

In the demo, a melody carries an added 5.2 kHz tone. The chart shows the chain on a 128-sample signal with components at 4, 11, and 52 cycles per window. The audio applies a steep low-pass filter to the real melody, with the cutoff following the slider during playback. Sweeping the cutoff below 52 on the chart (5.2 kHz in the audio) removes the added tone; sweeping further begins to remove the melody's own upper harmonics. Section 4 showed that timbre is carried by those harmonics, so removing them audibly dulls the sound; that dulling is the trade-off every equalizer makes.

10 The cost of the direct DFT

Part IV begins by counting operations. Each output $X[k]$ is a sum of $N$ terms, and each term is one complex multiplication; with $N$ outputs, the direct DFT costs $N \times N = N^2$ multiply–add operations. The count grows with the square of the window length: doubling $N$ quadruples the work.

The second figure corresponds to one second of CD-rate audio: about two billion operations per second of input, for a single spectrum. A live display recomputing the spectrum 60 times per second multiplies this again. The chart below plots the $N^2$ cost (red) against $N \log_2 N$ (cyan), the cost of the algorithm derived in sections 11–12; both axes are logarithmic, so each gridline is a factor of 1,000. The race button measures both on this machine, on the same input, and confirms that the outputs match.

11 Roots of unity: the template values repeat

The cost collapse comes from a property of the DFT's template values, visible on section 3's circle. The template value at frequency $k$, sample $n$ is $e^{-i 2\pi k n / N}$ Euler's formula ↗, and its angle is always a whole-number multiple of $2\pi/N$. Every template value the DFT ever uses is therefore one of just $N$ fixed points on the unit circle, the $N$-th roots of unity:

$W_N$ is one step clockwise around the circle, a rotation of $1/N$ of a turn; raising it to the power $kn$ takes $kn$ steps, because multiplying unit complex numbers adds their angles complex numbers ↗. Only the remainder of $kn$ after dividing by $N$ matters, because $N$ steps return to the start. For $N = 8$, the entire transform draws its values from the 8 points shown below.

Four facts about this lattice of points, each visible in the widget, underlie the FFT:

Each frequency traces an orbit. The template at frequency $k$ visits the points in steps of $k$. At $k = 1$ the orbit uses all 8 points; at $k = 2$ it uses only 4 of them, skipping every other point. Frequencies $k$ and $N - k$ trace the same points in opposite directions, which is the mirror symmetry observed in section 8's “all bins” toggle.

A half turn negates. Points half a lattice apart are opposite: $W_N^{\,j + N/2} = -W_N^{\,j}$. Advancing any template value by half the window negates it.

Squaring halves the lattice. Squaring every point doubles its angle, and the 8 points land exactly on the 4 points of the half-size lattice, two onto one: $(W_8^{\,j})^2 = W_4^{\,j \bmod 4}$. Sampling a template at every second sample squares its step, so the even-indexed samples of an $N$-point transform draw their template values entirely from the $N/2$-point lattice. This is the fact the FFT exploits.

Half-size orbits repeat. On the half-size lattice a full revolution takes only $N/2$ steps, so any quantity built from that lattice is periodic in $k$ with period $N/2$: stepping the frequency by $N/2$ carries the orbit exactly once around, back to its starting point. Section 12 uses this fact when one half-size result must serve two output frequencies.

12 The fast Fourier transform

The algorithm follows from section 11. The DFT sum splits over even-indexed and odd-indexed samples:

The first line separates even and odd indices, substituting $n = 2m$ and $n = 2m{+}1$. In the even sum the exponent's step doubles, and by section 11's squaring fact the doubled step lives on the half-size lattice: $e^{-i 2\pi k (2m)/N} = e^{-i 2\pi k m/(N/2)}$, the exponent of an $N/2$-point DFT. The odd sum factors out one constant by the exponential's addition law, $e^{a+b} = e^a e^b$ (the property that survives extension to complex inputs Euler's formula ↗), leaving $e^{-i 2\pi k/N} = W_N^{\,k}$, called the twiddle factor; what remains is then also an $N/2$-point DFT. $E[k]$ and $O[k]$ denote those half-size transforms of the even and odd samples.

Section 11's half-turn fact turns one computation into two outputs:

Raising $k$ by $N/2$ leaves $E$ and $O$ unchanged, because an $N/2$-point DFT repeats with period $N/2$ (section 11's fourth fact), and it advances the twiddle factor by half a turn, which negates it (section 11's second fact). One twiddle multiplication therefore yields both $X[k]$ and $X[k + N/2]$, as a sum and a difference. This multiply–add–subtract unit is called a butterfly.

The same split applies recursively to $E$ and $O$ until the pieces are single samples, whose one-point DFT is the sample itself. Each of the $\log_2 N$ levels performs $N/2$ twiddle multiplications, for a total of $\tfrac{N}{2}\log_2 N$ instead of $N^2$, which is the cyan curve in section 10's chart. At $N = 8$ the counts are 12 and 64. The diagram below is the complete $N = 8$ computation; the slider reveals it one stage at a time.

The analyzer below runs the same FFT on 2,048 samples during every screen frame of playback. At 60 frames per second this is about 0.7 million twiddle multiplications per second, at $(N/2)\log_2 N = 11{,}264$ per transform; the direct DFT would require about 250 million per second for the same display.

★ Final quiz

Ten questions are drawn from a larger bank; retaking the quiz draws a fresh set. The best grade is saved with course progress, and every answer includes the reasoning.