A linear time-invariant system is fully described by one short list of numbers, its impulse response. Know that list and you can predict the output for any input by sliding and adding.
Learn why filters, echoes, rooms and smoothers all do one operation, convolution, and why the Fourier basis turns that operation into plain multiplication.
Clap once in a stairwell and the sound lasts a second, as a train of echoes. Here is that clap, as a row of numbers. Pick a system, pick an input, then tap any spike of the input to change it. Watch the output y appear as a sum of shifted, scaled copies of the system’s impulse response. Then we build, piece by piece, why that works and what it buys us: convolution, rooms, circulant matrices, the DFT and measuring a system with a chirp.
You need a little arithmetic with lists of numbers and the idea of a matrix. We build the rest from zero.
Based on the Lecture 5 deck (28 September 2020) of Stanford EE269: Signal Processing for Machine Learning, taught by Mert Pilanci. Course slides. Every idea is re-taught here in our own words and devices. It builds on the DFT and discrete signals.
Toy signals of 24 samples, computed live in your browser. Teal stems are the input you edit (tap one: 0, 1, 0.5, −0.5), the warm stems are the impulse response, blue stems are the output, and the small teal dots are the pieces x[k]h[n−k] that add up to each output sample. Move your pointer along the plot to choose which output sample the read-out explains.
Chapter 0
See that a filter, a room, a smoother and a predictor are all the same kind of thing, and ask what we would need to know to predict any of them
You put on headphones with a bass boost. A song goes in. A different song comes out: the same tune, with the low notes louder. Somewhere between your phone and your ear, something took one stream of numbers and made another.
Now clap your hands in a stairwell. The clap is short, but the sound you hear lasts a second, with echoes. The stairwell took your clap and made something longer. Again, one signal went in and a different one came out.
Stanford’s EE269, taught by Mert Pilanci, opens its fifth lecture with exactly this picture. It is the picture behind every filter, every audio effect and every noise canceller you will meet in this course. This chapter names its parts. The rest of the lesson answers one question about it.
A microphone measures air pressure many times a second. Each measurement is one number. Write the numbers in order and you have a discrete signal: a list with a number for every whole-number position. We write the list x[n], where n is the index (the position: 0, 1, 2, and so on) and x[5] is the sixth number. Each number is a sample.
Pictures work the same way. A row of pixel brightnesses is a signal. A day of temperature readings is a signal. A stock’s closing prices are a signal. Our discrete signals lesson goes deeper; this is all we need here.
The lecture draws a box with an arrow in and an arrow out. A signal x[n] enters, the system does something to it, and a signal y[n] leaves. We write the box as T, so y[n] = T{x[n]}. Read it as “y is what T makes of x”.
The slide gives one sentence of definition: a system is a processing operation performed on the signal. It names three examples. A natural system is one the world gives you, such as a room, a guitar body or a cable. A designed filter is one an engineer builds on purpose, such as a bass boost. A predictor is one that guesses the next sample from the earlier ones.
That is a very wide net. Try six small systems on the same input. The input is a slow wave with a fast ripple on top, like a song with a little hiss.
Teal is the input, blue is what the system makes of it. Choose a system, then move your pointer along the plot to pick one output sample and see exactly how it was made.
Illustrative input of 48 samples: a slow wave (period 24 samples, height 0.6) plus a fast ripple (period 5 samples, height 0.25). The smoother averages the last 4 samples, the echo adds 0.6 times the sample from 6 steps ago, the running total adds every sample so far, the edge finder subtracts the previous sample, the squarer squares each sample and the clipper limits each sample to between −0.5 and 0.5.
Look at what each box does to the same input. The smoother removes the ripple and keeps the wave. The echo lays a quieter copy of the wave on top of itself, six steps later. The running total turns the wave into a slowly drifting curve. The edge finder keeps only the ripple, because it reacts to change. The squarer makes everything positive. The clipper flattens the peaks.
The first four feel alike: each builds the output from a few input samples. The last two feel different. The squarer and the clipper treat a big sample very differently from a small one. Chapter 1 turns that feeling into a test.
Here is the real problem. Suppose a stranger hands you a sealed box and says it is a system. You want to predict its output for any input you may ever feed it. How many tests must you run?
For a general system, the answer is: infinitely many. Nothing stops a box from doing something odd for one particular signal. It could smooth every input except one special song, and for that song play a different tune. You would only learn that by feeding it that exact song. Testing a million inputs tells you nothing about the million-and-first.
So a fully general system cannot be described by finite testing. This is not a small problem. It is why engineers never study “systems” in general. They study restricted families of systems, where a short list of tests is enough.
The answer takes the whole lecture to build, but you can hold it in one sentence. The two promises are linearity (a sum of inputs gives the sum of outputs) and time invariance (the box behaves the same today as tomorrow). A system that keeps both is a linear time-invariant system, written LTI. For an LTI system, the single measurement is the response to one sharp click, the impulse response h[n].
From there the story has a second act. We will see that the operation an LTI system performs is always the same one, called convolution. We will turn it into a matrix. And we will find that one special family of signals, the complex waves of the Fourier basis, pass through every LTI system unchanged in shape. That is why the Fourier transform sits at the centre of signal processing.
The lesson follows the lecture’s slides in order. The instrument at the top of the page is the whole result in miniature: the output is a sum of shifted, scaled copies of h. Each chapter explains one part of it.
Chapter 1
Learn the first promise a system can make, prove it for the moving average, and meet three useful systems that break it
You are in a recording studio. A singer and a guitarist are on separate microphones, and both signals go through a reverb unit. You can mix the two microphones first and send the mix through the reverb. Or you can send each microphone through its own reverb and mix afterwards.
Do the two ways sound the same? For a real reverb, yes, and engineers rely on it every day. They can tweak the singer alone, then add the guitar, and nothing changes in the singer’s part. That promise has a name: linearity.
Say it with symbols. Two inputs x1[n] and x2[n] go through the same system T and give outputs y1[n] and y2[n]. Now feed the system a mix: c1 times the first plus c2 times the second, where the weights c1 and c2 are any numbers. The lecture’s definition says the system is linear if the output is the same mix of the outputs.
The one equation packs two small rules together. Homogeneity says that scaling the input scales the output: double the volume going in, get double the volume coming out. Additivity says that the output for a sum is the sum of the outputs. Set c2 = 0 and you get homogeneity. Set both weights to 1 and you get additivity.
The lecture picks one example to prove: the moving average. It averages the last M values of a signal. In symbols, y[n] = (1/M)(x[n] + x[n−1] + … + x[n−M+1]). Traders use it to smooth a jumpy price. The lecture’s slide shows a stock chart with a smooth average line drawn through it, and small arrows where the price crosses the line.
Start with a small case so you can see the numbers. Take M = 3, the two inputs x1 = [1, 2, 3, 4] and x2 = [0, 3, 0, 3], and the weights c1 = 2, c2 = −1. We check the output at n = 2.
One example is not a proof, so here is the general argument, the one the lecture sets up. Write the system applied to the mix, then pull the weights out of the sum.
T{c1x1 + c2x2}[n] = (1/M) ∑k=0M−1 (c1x1[n−k] + c2x2[n−k]) = c1·(1/M)∑x1[n−k] + c2·(1/M)∑x2[n−k] = c1y1[n] + c2y2[n]
The proof works for a reason you can reuse. The moving average is a sum of input samples, each multiplied by a fixed number. Sums and fixed multipliers both pass through a mix. So any system that builds each output from a fixed weighted sum of input samples is linear. Averages, differences, echoes and running totals all qualify. This one fact covers most of the filters you will ever write.
Now run the superposition test as a machine. Two fixed inputs go in with weights you choose. The device processes the mix, then mixes the processed parts, and shows both results on top of each other.
Warm line: process the mix. Blue dashes: mix the processed parts. Green means the lines coincide. Red bars appear where they do not. Try each system, then drag the weights.
Illustrative inputs of 32 samples: x1 is a triangle wave of height 1.2, x2 is a pulse train of height 1. The moving average uses 3 samples, the weighted sum is 3x[n] + 2x[n−1] − x[n−2], the clipper limits samples to at most 1, and signals are zero before the first sample.
The moving average and the weighted sum always sit on the green line, whatever you do with the weights. The other four break it, and each in its own way. Let us see why with numbers you can check by hand.
Squaring. Take x = [1, 2]. Then T{x} = [1, 4]. Double the input to [2, 4] and the output is [4, 16], not 2T{x} = [2, 8]. Homogeneity fails: the output grows with the square of the input.
Clipping. A clipper keeps a sample at or below 1. Feed it 0.8 and you get 0.8. Feed it 1.6 and you get 1, not 2 × 0.8 = 1.6. Clipping saves a speaker from a spike, but it ruins homogeneity for loud signals.
The median filter. It outputs the middle value of three neighbouring samples. A lone spike [0, 1, 0] vanishes: the middle value is 0. The same goes for a lone spike at the next position. But add those two inputs and you get two spikes side by side, [0, 1, 1], and the median is 1. Additivity fails: 0 + 0 is not 1. People love the median filter because it deletes a single bad sample (a click, a dead pixel) without blurring.
All three are valuable. None of them is wrong. They just lose the superposition promise, so every tool in this lesson stops working on them.
Linearity gives you a way to divide and conquer. If you can write a hard input as a sum of easy pieces, you only need the system’s answer to each easy piece. Add the answers and you have the answer to the hard input. The whole lecture is the search for the best easy pieces. Chapter 3 picks the simplest possible one, a single spike.
Look at the failure the way a debugger would. The symptom: you run a mixing plugin on the full band and the singer sounds fine, but when you mute the guitar the singer sounds different. The measurement: process the mix, process each part, and compare. A gap means the plugin is nonlinear, and the gap’s size is its price. The fix: you cannot restore superposition, so you check it, accept the interaction, and keep the loud levels under the point where the clipper acts.
Chapter 2
Learn the second promise, check it by shifting an input, and spot the systems that secretly read the clock
Stand in an empty hall and clap once. You hear a short burst of echoes. Walk to the other end of the hall, wait five seconds, and clap again. You hear the same burst of echoes, five seconds later.
The hall does not know what time it is. It treats a clap at second 0 exactly as it treats a clap at second 5. That is the second promise a system can make. The lecture calls it time invariance, and some books call it shift invariance. Both names mean the same thing.
To delay (or shift) a signal by n0 samples means to slide the whole list to the right. The new list x[n−n0] at position n holds what the old list held at position n−n0. A time-invariant system has a simple property: delaying the input by any amount just delays the output by the same amount.
Here is the test in two steps. First delay the input, then run the system. Second, run the system, then delay the output. Time invariance says the two results are the same list. If they differ anywhere, the system reads the clock somewhere.
Take the 3-point moving average and delay the input by n0 = 2. The input x = [1, 2, 3, 4] at positions 0 to 3 becomes the same numbers at positions 2 to 5. Compute the output at n = 5 of the delayed input: (4 + 3 + 2)/3 = 3.
Now take the original output at n = 3 and see where it landed: y[3] = (4 + 3 + 2)/3 = 3, and a delay of 2 moves it to position 5. The values match. In general, the average at time n looks only at x[n], x[n−1], …, always measured from n. The formula never mentions n by itself, only the gaps between n and the samples it reads. Move everything by n0 and the gaps stay the same.
The slide asks about the accumulator, a running total of every sample so far: y[n] = ∑k=−∞n x[k]. It has infinite memory. Is it time-invariant? The slide leaves the check as a question, so let us do it.
One warning for real code. If a running total starts at a fixed clock time, say “add up everything since 9:00”, the 9:00 is a place on the clock. Shift the input and the total still starts at 9:00. That version is not time-invariant. The version above works only because it starts “at the beginning of time”.
Three common systems are not time-invariant, and each has a different tell.
Multiply by the index. Let y[n] = n · x[n]. Delay the input first and the output is n · x[n−n0]. Delay the output instead and you get (n−n0) · x[n−n0]. The factor n is a clock reading, so the two disagree by n0 · x[n−n0].
Modulation. Let y[n] = x[n] cos(ωn). This is how a radio puts a message on a carrier wave, and the cosine is a clock that runs forever. Delay the input and the cosine does not move with it.
Downsampling. Let y[n] = x[2n], keeping every second sample. Delay the input by 1 and the output reads x[2n−1]. Delay the old output by 1 and it reads x[2n−2]. Different samples, so different outputs. A delay of one sample in the input does not produce a clean delay in the output.
Check all of this with the machine below. Slide the input in time and watch whether the output slides with it.
Warm line: process, then delay the output. Blue dashes: delay the input, then process. Red bars mark any sample where the two disagree. Choose a system, then drag the delay.
Illustrative input: a smooth bump of 16 samples placed in the middle of a 48-sample buffer, so every delay from −6 to 6 fits inside it. The moving average uses 4 samples, modulation uses cos(0.7n), and the accumulator sums from the start of the buffer, where the input is already zero.
Drag the delay to zero and every system agrees with itself, which is no test at all. Move it away from zero and the first two stay perfect while the other three tear. In the multiply-by-n case the gap grows with the position, because the factor n keeps growing.
Time invariance is a statement about the rule, not about the signal. A time-invariant system can give a loud output now and a quiet one later, if the input changes. What it cannot do is change its own behaviour. Now see what goes wrong when a real system drifts. The symptom: a speakerphone cancels its echo well when you start a call, then lets it through when you walk across the room. The measurement: record the room’s response every second and compare. The numbers drift, so the room is not time-invariant over the call. The fix is a filter that re-learns the response all the time; adaptive filters do exactly that.
Chapter 3
Break any signal into single spikes, use both promises, and see that one short list of numbers describes the whole system
A sonar operator sends out a single sharp ping and listens. What comes back tells her the shape of the seabed, the wreck on it and the fish above it. She does not need to send a song. One ping contains the system’s whole character.
This chapter proves why a ping is enough. The proof has three moves: break the input into spikes, process each spike, add the results. Each move uses one of the two promises. Watch for which.
The simplest signal that is not silence is a single 1 in a sea of zeros. We call it the unit impulse, written δ[n] (the Greek letter delta). It is 1 at position 0 and 0 everywhere else. Think of one camera flash in a dark room, or one hand clap.
The impulse response of a system is its output when the input is that single spike. We write it h[n]. In symbols: δ[n] → T → h[n]. For the 3-point moving average, the spike 1 at position 0 gives h = [1/3, 1/3, 1/3]: the spike is inside the average for exactly three outputs, and each time it counts one third.
Now use the second promise. Time invariance says that a delayed input gives a delayed output. A spike at position k, written δ[n−k], is just the unit spike delayed by k. So its output is the impulse response delayed by k.
δ[n−k] → T → h[n−k] (time invariance, for every k)
The lecture calls the next idea the delta basis. Take any signal, for example x = [2, −1, 3]. It is a 2 at position 0, a −1 at position 1 and a 3 at position 2. In spike language:
x[n] = 2·δ[n] − 1·δ[n−1] + 3·δ[n−2]
Nothing is lost: put the three scaled spikes on top of each other and you get back exactly the list. For a signal that runs forever, there is one spike term per sample, so the lecture writes it as a sum over all positions k.
Now feed the pile of spikes to the system. We apply T to both sides and use the two promises one at a time.
Read the result in words. The output is a sum of copies of h. Each copy starts at the position of an input sample and is scaled by that sample’s height. That is the picture you have been playing with in the instrument at the top of the page: the dots are the copies, and the blue stems are their sum.
Let the system be an echo with h = [1, 0, 0.5]: the sound itself, then silence, then a half-height repeat two steps later. Let the input be x = [2, −1, 3]. There are three copies of h to lay down.
The output is y = [2, −1, 4, −0.5, 1.5], five numbers from a three-number input and a three-number response. We will see why the length is 3 + 3 − 1 in the next chapter.
Now return to the problem from Chapter 0. For an LTI system we measure h once, by sending one spike. After that, the formula above predicts the output for every input we will ever try. The lecture’s slide puts it in one line: LTI systems are entirely described by their impulse response.
Try it. The machine below has a hidden system. It measures the impulse response by sending a spike, then predicts the output to your input from that list alone, and compares the prediction with the real system.
Warm stems: the impulse response measured from one spike. Blue stems: the real output for your input. Green rings: the output predicted from the warm list alone. Try all four systems, then change the loudness.
Illustrative: the input is the list [1, −0.5, 1.5, 0, 1] times the loudness. The smoother averages 3 samples, the echo adds 0.6 times the sample from 3 steps ago, the edge finder subtracts the previous sample and the squarer squares each sample. The prediction uses only the impulse response and the formula y[n] = ∑ x[k]h[n−k].
For the first three, the prediction lands on the real output exactly, at every loudness. For the squarer the measurement is itself misleading. A spike of height 1 squared is still 1, so the measured h looks like “do nothing”. Yet a loud input comes out as its square. The squarer broke the first promise, so one measurement cannot describe it.
Look at the failure with the debugger’s three steps. The symptom: your predicted output is close for quiet signals and wrong for loud ones. The measurement: compare prediction and truth at two loudnesses; if the gap grows with loudness, linearity is failing. The fix: measure h again at the loudness you care about, and treat the answer as valid only near that loudness.
Chapter 4
Turn the sum of copies into a recipe you can run for any output sample, and learn its name and its rules
A bell hangs in a tower. A bell ringer strikes it three times: hard, soft, medium. Each strike rings out and fades the same way. At any moment, what you hear is not one ring but a pile: the fading tail of the first strike, the fading tail of the second, and the fresh start of the third.
To work out what you hear at time n, you ask of every earlier strike: how old is it now, and how loud is a ring of that age? Then you add the answers. That question, “how old?”, is the heart of this chapter.
Chapter 3 ended with y[n] = ∑k x[k] h[n−k]. The lecture now gives this sum its own name and symbol. It is the convolution of x with h, written with a star: y = x ∗ h. Two signals go in, one comes out.
There are two ways to read the sum, and they give the same numbers. The push view is Chapter 3’s: every input sample pushes a scaled copy of h forward, and you add the copies. The pull view is the bell story’s: to get the output at n, pull a weighted sample from each input position, with the weight set by the gap. The pull view gives a recipe for a single output sample.
Here is the pull view as steps. To compute y[n]:
Work one with a list that is not symmetric, so the flip matters. Let x = [1, 2, 3] and h = [3, 2, 1], and find y[2]. Flipping h gives [1, 2, 3]. Slide it so that its last entry, the original h[0] = 3, sits above x[2]. The pairs are: x[0]h[2] = 1·1, x[1]h[1] = 2·2, x[2]h[0] = 3·3. Add: 1 + 4 + 9 = 14.
The older input sample x[0] meets the last entry of h, the tail. That is right: it struck long ago, so only the faint tail of its ring is left. Skip the flip and you would pair the oldest sample with the loudest part of the ring, which is wrong.
Use the machine below to run the recipe on the lecture’s own kind of example: the list [1, 2, 3, 4] through a 3-point average. Drag the position, or press play, and watch the flipped h slide across.
Teal: the input x. Warm: h, flipped and placed at position n. Blue rings: the products. Blue stems: the output so far. Pick an h, then drag n or press play.
The input is the list [1, 2, 3, 4] from the lecture’s setting. Each choice of h is a toy. The output is computed exactly with the convolution sum, and its length is the input length plus the h length minus one.
For the average at n = 3 the products are 4/3, 3/3, 2/3 and they add to 3. At the start and end of the output, the flipped list only half-overlaps the input, so fewer terms add up. That is why the output is longer than the input: it ramps in as the list slides on, and ramps out as it slides off.
Check all six outputs for the average by hand. They are y = [1/3, 1, 2, 3, 7/3, 4/3] ≈ [0.33, 1.00, 2.00, 3.00, 2.33, 1.33]. The full output has 4 + 3 − 1 = 6 samples: the list slides over positions where it overlaps the input at least once.
Convolution behaves like multiplication in four ways you will use constantly.
It commutes. x ∗ h = h ∗ x. Substitute m = n − k in the sum and the roles swap. So it does not matter which list you call the signal and which the system. It distributes over addition, which is linearity again. It is associative: (x ∗ h1) ∗ h2 = x ∗ (h1 ∗ h2), which Chapter 9 turns into a rule for chaining systems. And the spike is its identity: x ∗ δ = x, because the system that does nothing has h = δ.
The cost is easy to count. Each output sample needs one multiply per entry of h. So an input of N samples and a response of M samples costs about N · M multiplies. A 10-second recording at 48,000 samples a second through a 2-second reverb is 480,000 × 96,000, about 46 billion multiplies. Chapter 8 shows a shortcut.
The slide ends with a line about Hilbert spaces, which are vector spaces that carry an inner product: a way to multiply two vectors into one number, here the sum of products of matching entries. The line says that x1 ∗ x2[n] = 〈x1∗[n−k], x2[k]〉: the output at n is the inner product of x2 with a flipped, shifted copy of x1 (the star on x1 means complex conjugate, which does nothing for real signals).
An inner product is large when two lists line up. So the output is large wherever the signal looks like a flipped copy of h. This is how a pattern detector works, and it is why the layers of a convolutional network, which slide a small filter across an image, are called convolutions. (They skip the flip in practice, which makes them a close cousin called cross-correlation; our convolutional networks lesson goes on from here.)
pythonimport numpy as np def convolve(x, h): N, M = len(x), len(h) y = np.zeros(N + M - 1) # output length N + M - 1 for n in range(N + M - 1): for k in range(N): if 0 <= n - k < M: # h[n-k] exists only inside the overlap y[n] += x[k] * h[n - k] # one product of the pull view return y x = np.array([1, 2, 3, 4]); h = np.ones(3) / 3 assert np.allclose(convolve(x, h), np.convolve(x, h)) # [0.33 1. 2. 3. 2.33 1.33]
Chapter 5
Hear convolution in a space you can drag a speaker around in, and see why a room counts as an LTI system
A sound engineer walks into a stone cathedral with a balloon. She stands at the altar, pops it, and records the next four seconds with a microphone at the back. Back in her studio she can now make any voice sound as if it were singing in that cathedral. She never needs the choir.
The recording of the pop is the room’s impulse response. The trick she plays is convolution. The lecture’s twelfth slide shows exactly this setting, a room drawn from above, with a source, a microphone and the paths between them, under the title “Convolution with acoustic impulse response”.
A sound leaves a speaker, bounces around, and reaches a microphone. The microphone signal is the speaker signal after the room has done something to it. So the room is a system, and the speaker signal is its input.
Is it linear? Air carries two sounds at once without them interfering, as long as the sounds are not so loud that the air itself behaves oddly. A voice plus a guitar in the air is the sum of the two alone. Is it time-invariant? Yes, as long as nobody moves, no door opens and the air stays still. Both promises hold well enough, and the room is called LTI for a fixed source and microphone position.
Chapter 3 then applies: the room is completely described by the response to one clap, and every other sound is a sum of shifted, scaled copies of that response. The acoustic impulse response is the name of that list for a particular source position and microphone position.
Why does a clap in a room leave many copies of itself? Because sound takes many routes. One route is the straight line from speaker to microphone: the direct sound. Others bounce off a wall first, then arrive later and quieter. Each route is a spike in the impulse response. Two things set its place and height.
The delay is the path length divided by the speed of sound, about 343 metres per second in room-temperature air. The gain falls as the path gets longer, in proportion to one over the distance, and drops again at every bounce, because walls absorb some sound. We call the fraction a wall reflects its reflectivity, a number below 1.
A neat trick finds the longer routes. A bounce off a wall sounds the same as a straight path from a mirror copy of the speaker, standing behind that wall. This is the image-source method. Mirror the speaker in all four walls to get the first echoes. Mirror those mirrors for second bounces, and so on.
Take a room 6 metres wide and 4 metres deep. Put the speaker at (1.5, 1.0) and the microphone at (4.5, 3.0), in metres. The direct path runs 3 metres across and 2 metres up, so its length is √(3² + 2²) = 3.61 m. At 343 m/s it takes 3.61 / 343 = 10.5 ms.
Now mirror the speaker in the bottom wall (the line y = 0). The image sits at (1.5, −1.0). Its distance to the microphone is √(3² + 4²) = 5.00 m, so the echo arrives after 5.00 / 343 = 14.6 ms. That is 4.1 ms after the direct sound. Its height, with a wall reflectivity β, is β / 5.00 against 1 / 3.61 for the direct sound. At β = 0.8 the echo is 0.8 × 3.61 / 5.00 = 0.58 times as loud as the direct sound.
Repeat for the other three walls and then for every deeper mirror. After many bounces the spikes crowd so close together that the ear hears a smooth tail rather than separate echoes. That tail is reverberation.
The device below does this for you, in both directions. It draws the room from above, and builds the impulse response from the mirror images. Drag the speaker and the microphone around. Press the buttons to hear a hand clap with and without the room.
Drag the teal speaker or the blue microphone inside the room. The lower plot shows one stem for every sound route: its delay and how loud it arrives, relative to the direct sound. Raise the reflectivity to make the walls hard and the tail long.
A 6 m by 4 m room, sound speed 343 m/s, every wall with the same reflectivity, routes counted up to 7 mirror images in each direction. This is the image-source method for a flat, rectangular room: a toy that ignores air absorption and the way walls colour the sound. The clap is a short burst of noise, sampled at 16,000 Hz, and the room version is its convolution with the response shown.
Listen to the second button after dragging the microphone far from the speaker. The direct sound gets quieter and arrives later, while the tail stays nearly the same. That is why a distant voice in a hall sounds washed out: the reverberant tail becomes a bigger share of what you hear. Dragging the reflectivity to its top end gives a long, ringing tail; to its low end, a dry, dead room.
Three jobs rest on this one idea. Convolution reverb plugins store the responses of real spaces and convolve your recording with them. Echo cancellation on a video call estimates the room’s response between your speaker and your microphone, convolves the far-end voice with it, and subtracts the result, so the far person does not hear themselves. Our acoustic echo cancellation lesson builds it. Dereverberation goes the other way: it tries to undo the room. Chapter 9 explains why that is hard.
Look at where the idea fails. The symptom: your echo canceller works with the laptop on the desk and fails when you pick it up. The measurement: record the response once with the laptop on the desk, once in your hands, and compare the stems. The delays and heights have moved. The room plus laptop stopped being time-invariant. The fix is the same as in Chapter 2: re-estimate the response all the time, which is what adaptive filters do.
Chapter 6
Wrap the signal into a loop of N samples, write convolution as a matrix times a vector, and see what the wrap does to the ends
Picture a record spinning on a turntable. The groove has no start and no end. If you walk the groove for one full turn you are back where you began. A signal on a record is a list that wraps around: after the last sample comes the first one again.
Real computers hold finite lists, and the DFT you met in the DFT lesson treats a list of N samples as exactly this kind of loop. To use the DFT on systems we need convolution in a loop too. The lecture calls it circular convolution.
One small tool first. The modulo operation, written mod N, gives the remainder after dividing by N. On a clock with 12 hours, 14 o’clock is 2 o’clock, because 14 mod 12 = 2. And −1 o’clock is 11, because −1 mod 12 = 11. Modulo wraps any whole number back onto the numbers 0, 1, …, N−1.
For a signal of length N = 4, the positions are 0, 1, 2, 3. Position −1 is the same as position 3, and position 4 is the same as position 0. A circular shift slides every sample one place to the right, and the sample that falls off the end reappears at the start.
Circular convolution is the convolution sum with every index read modulo N. The lecture writes it with a circled star.
Now an example with every number. Take the lecture’s kind of input, x = [1, 2, 3, 4], and the 3-point average, written on a loop of N = 4 by adding a zero: h = [1/3, 1/3, 1/3, 0]. The first output sample reads h at the gaps 0, −1, −2, −3, which wrap to positions 0, 3, 2, 1.
Compare with the ordinary convolution from Chapter 4, which had six samples: 0.33, 1.00, 2.00, 3.00, 2.33, 1.33. The circular answer is [2.67, 2.33, 2, 3]. The last two ordinary samples did not vanish. They wrapped around and landed on the first two: 0.33 + 2.33 = 2.67 and 1.00 + 1.33 = 2.33. Samples 2 and 3 were untouched.
Every output sample is a weighted sum of the input samples. That is exactly what a matrix times a vector does. So circular convolution is y = Hx, where x and y are vectors of length N and H is an N × N matrix. Row n of H holds the weights that output n puts on each input: entry (n, k) is h[(n−k) mod N].
The lecture prints the matrix: the first column is h[0], h[1], …, h[N−1], and every column below the first is the previous column pushed down by one, with the bottom entry wrapped to the top. Equivalently, every row is the row above it pushed right by one. A matrix with this pattern is called circulant. For our example it is
H = (1/3) · [[1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 0], [0, 1, 1, 1]]
and multiplying it by [1, 2, 3, 4] gives the four numbers above. A whole filter has been packed into one list of N numbers, the first column, and the matrix repeats that list around the loop. Circulant matrices are special. Chapter 7 shows that they all share the same eigenvectors, whatever h is.
The machine below uses the same x and h. Change the loop length N and watch the matrix and the output. For N of 6 or more, the loop is long enough and circular matches linear. For less, the tail wraps.
Top: the circulant matrix H, with the row you choose lit. Bottom: blue stems are the circular output, grey rings are the ordinary six-sample output. Shrink the loop below 6 and watch the tail fold onto the start.
The input is [1, 2, 3, 4] and h is [1, 1, 1] divided by 3, both padded with zeros to length N. The ordinary output has 6 samples. Each circular output is the sum of every ordinary output whose position is the same modulo N.
The rule you can read off the device is general. The circular output equals the ordinary output with every sample past position N−1 added back onto the start. This folding is called time aliasing. To get the ordinary output from a circular one, choose N at least as long as len(x) + len(h) − 1 and pad both lists with zeros to that length.
Take the failure the usual three-step way. The symptom: after filtering with the DFT, the first few output samples contain a faint copy of the end of the signal. The measurement: compare against the ordinary convolution; the difference sits exactly on the wrapped samples. The fix: zero-pad both lists so the loop is long enough, or process long signals in blocks, a method called overlap-add.
Chapter 7
Find the one family of signals that comes out of any circulant system with its shape intact, and see why that family is the DFT
Play a pure 440 Hz tone through a bass boost, a room, a telephone line or a tone control. You hear the same pitch. It may come out louder, quieter, or a little late, but it is still 440 Hz. You never hear an A turn into a B flat.
Most signals do change shape in a system. A sharp click goes in and a smeared echo comes out. A pure wave is special: it is the one kind of signal that passes through any LTI system as itself, only scaled and slid. This chapter proves it, and the lecture’s fourteenth slide holds the key formulas.
When you multiply a vector by a matrix, you usually get a vector that points in a new direction. Rotating, stretching and shearing all do that. But for each matrix there are a few special vectors that keep their direction. The matrix only stretches them. A vector v that satisfies Hv = λv is an eigenvector of H, and the stretch factor λ is its eigenvalue. (Our eigenvalues lesson goes deeper.) For a vector of complex numbers, the stretch factor can be complex too, and a complex factor means “stretch and turn”.
Why do we want eigenvectors? Because a matrix acts on them in the simplest way possible: one multiplication. If we can write every input as a mix of eigenvectors, then we can find the output by scaling each part, which is much easier than a full matrix multiply.
The lecture names a family of vectors, the Fourier basis. Vector number k has the entry
Here is the complex exponential in two sentences. The number ejθ equals cos θ + j sin θ, a point on a circle of radius 1 at angle θ. As n grows, θ = 2πnk/N grows, and the point spins at a steady rate, k turns per N samples. The Fourier vectors are the DFT’s own basis from the DFT lesson: k = 0 is a flat line, k = 1 is one wave across the whole window, and so on.
Feed the Fourier vector wk to the circular system. Sample n of the output is ∑m h[(n−m) mod N] · wk[m].
So H wk = H[k] wk. The Fourier vector is an eigenvector of every circulant matrix, and the eigenvalue is the DFT of h. The reason is step 2: delaying a complex exponential only multiplies it by a constant, so a system built from delays and sums just multiplies it by a constant too. The slide prints the same fact the other way round, as wkH H = H[k] wkH, with the vector on the left. Same number H[k].
Use h = [1/3, 1/3, 1/3, 0] and N = 4. Compute H[1] = ∑ h[l] e−j2πl/4 = (1/3)(1 + e−jπ/2 + e−jπ) = (1/3)(1 − j − 1) = −j/3. Its size is 1/3 and its angle is −90°. The other three: H[0] = 1, H[2] = 1/3, H[3] = +j/3.
Check it on the matrix itself. The vector w1 = (1/2)[1, j, −1, −j]. Row 0 of H is (1/3)[1, 0, 1, 1], so (Hw1)[0] = (1/3)(1/2)(1 − 1 − j) = −j/6. The prediction is H[1] w1[0] = (−j/3)(1/2) = −j/6. They match. Row 1 is (1/3)[1, 1, 0, 1], giving (1/6)(1 + j − j) = 1/6, and the prediction is (−j/3)(j/2) = 1/6. They match again.
The complex number H[k] has a size and an angle. Its size, |H[k]|, is the gain: how much louder or quieter wave number k comes out. Its angle is the phase: how far the wave is slid along in time. The whole list H[0], …, H[N−1] is called the frequency response of the system. Our smoother has gain 1 at k = 0 (a steady level passes untouched) and gain 1/3 at k = 1. It lets slow waves through and shrinks fast ones, which is exactly what smoothing means.
Compare that with a signal that is not a Fourier vector. A single spike comes out as h, a shape with its own wiggles. It is a mix of all the Fourier vectors, each scaled differently, so the mix changes shape.
The device below circularly convolves three kinds of input with a system on a loop of 16 samples. For each it tries to explain the output as the input times one complex number. For a Fourier wave this works to machine precision. For anything else it fails, and the size of the failure is shown.
Teal: the real part of the input. Blue: the real part of the output. Purple dashes: the input times the best single complex number. If the dashes sit on the blue, the input is an eigenvector. The bars show the system’s gain at each wave number.
Loop length N = 16. The smoother averages 4 samples, the echo is h = 1 at 0, 0.6 at 5 and 0.3 at 10, the edge finder is h = [1, −1] and the bump is [1, 2, 3, 2, 1] divided by 9. The random input is a fixed seeded list. Fit error is the length of (output minus best scaled input) divided by the length of the output.
Pick the smoother and wave number 2. The output is the input shrunk to 0.65 of its height and slid, with a fit error of 0.00. Switch to the spike and the fit error jumps, because the output is the whole shape of h. This is also a useful test for real systems. The symptom: you play a pure tone and a new tone appears at the output. The measurement: the output spectrum has a line at a frequency the input lacked. An LTI system can never do that, because every wave stays a wave of its own frequency. So the system is nonlinear (distortion) or time-varying (modulation), and Chapter 1 and Chapter 2 tell you which test to run.
Chapter 8
Turn a whole convolution into one multiply per frequency, see the matrix that says so, and filter a noisy signal by drawing its response
Look at a graphic equalizer on a hi-fi: a row of sliders, one for each band of pitch, from deep bass to bright treble. Push the bass slider up and only the bass gets louder. Each slider multiplies one band by its own number and leaves the rest alone.
That picture is exactly what the lecture proves in its fifteenth and sixteenth slides. Filtering with any LTI system is a graphic equalizer: split the signal into waves, scale each wave by its slider, and put the waves back together. The sliders are the numbers H[k] from Chapter 7.
Chapter 7 gave us a family of eigenvectors, the Fourier vectors w0, …, wN−1. They are orthonormal: each has length 1 and any two are at right angles, like the three axes of a room. So any signal x is a unique mix of them, with weights X[k]. Those weights are the DFT of x.
That is the lecture’s statement, in one line each way:
This is the convolution theorem: convolution in time is multiplication in frequency. Two long, messy sums became one multiplication per slider. A note on units: the lecture’s Fourier vectors have length 1, so its X[k] carries a factor 1/√N, while H[k] is the plain sum from Chapter 7. A software FFT usually leaves out the 1/√N on all three transforms, and the rule Y = H·X still holds.
Slide 16 states it with matrices. Stack the conjugate Fourier vectors wkH as the rows of one matrix F. Multiplying a signal by F is the DFT. The row form of the eigenvector fact then reads, all rows at once,
Read the right-hand matrix equation as a three-step machine: F moves you into frequency, the diagonal scales each frequency, FH moves you back. This is called diagonalizing the circulant matrix. A diagonal matrix is the easiest kind to use, so every question about H now becomes a question about N scalars.
Take x = [1, 2, 3, 4] and the smoother on a loop of 4. The plain DFT of x is X = [10, −2 + 2j, −2, −2 − 2j], and from Chapter 7 the sliders are H = [1, −j/3, 1/3, j/3]. Multiply them one by one.
Y[0] = 10, Y[1] = (−j/3)(−2 + 2j) = (2 + 2j)/3, Y[2] = −2/3, Y[3] = (2 − 2j)/3
The inverse DFT of the first sample is y[0] = (1/4)(10 + (2+2j)/3 − 2/3 + (2−2j)/3) = (1/4)(32/3) = 8/3 ≈ 2.67. That is exactly the circular output from Chapter 6. The second sample works the same way and gives 7/3. Two roads, one answer.
Now use the rule as an engineer would. The input below is a clean tone, a second tone at a higher pitch, and a layer of hiss, all on a loop of 64 samples. You draw the sliders H[k] by choosing a filter shape and a cutoff. The device multiplies the spectrum, goes back to time, and also runs the slow N² convolution with the equivalent h to prove both agree.
Top: purple bars are the input’s spectrum, the warm line is the filter’s gain H[k] at each frequency, and the blue bars are the output’s spectrum. Bottom: the input in teal, the output in blue. Choose a filter shape and drag the cutoff.
Illustrative signal: a tone at wave number 3 (height 1), a tone at wave number 11 (height 0.6) and fixed seeded hiss, N = 64. The low-pass and high-pass pass or block the wave numbers up to the cutoff (and their mirror images), the band-pass keeps those within 3 of the cutoff and the notch blocks those within 2. The slow route computes the sum y[n] = ∑ x[k] h[(n−k) mod 64] with h found by the inverse DFT of H.
Set the low-pass cutoff to 7 and the high tone and most of the hiss disappear, leaving the clean low tone. The two routes agree to about 10−16, which is just the rounding error of the computer. Switch to the notch with cutoff 3 and the low tone disappears while the high one survives.
The multiplication is cheap, but the DFT itself costs N² if done naively. The fast Fourier transform (FFT) computes it in about N log2 N steps (see the FFT lesson). The recipe is: FFT both lists, multiply, inverse FFT. For N = 65,536, direct convolution is about 4.3 billion multiplies, while three FFTs of that size cost very roughly three million operations: about a thousand times fewer. The exact ratio depends on the code, so treat it as an order of magnitude.
It also has a catch you already know from Chapter 6. The product of two DFTs gives a circular convolution. To get the ordinary one, pad both lists with zeros to at least len(x) + len(h) − 1 before transforming. A brick-wall filter like the ones above has a h that rings on and on, and the wrap makes its ringing leak into the other end of the loop. Smooth filter shapes ring far less.
Chapter 9
Chain two systems by multiplying their spectra, then try to undo a blur by dividing, and see why noise fights back
A photographer shakes the camera a little: the picture is blurred. Then the lens turns out to have a smudge: the picture is blurred again. Two blurs, one after the other. Is the result a different, bigger blur? And can you sharpen the photo and get the original scene back?
Both questions have clean answers once you think in frequencies. The lecture’s seventeenth slide answers the first. The second follows straight from it, and has a catch that every engineer who has tried to “enhance” a photo has met.
The slide draws x[n] → h1[n] → h2[n] → y[n]. The first system makes H1x. The second acts on that, so y = H2H1x, a product of two circulant matrices. Now bring in Chapter 8. Move to the Fourier side by applying F.
F y = F H2 H1 x = diag(H2[0:N−1]) F H1 x = diag(H2[0:N−1]) diag(H1[0:N−1]) F x
Each step is one use of F H = diag(H[k]) F: first for H2, then for H1. Two diagonal matrices multiply by multiplying their diagonals, entry by entry. So Y[k] = H2[k] · H1[k] · X[k].
Three facts fall out. Cascading multiplies the sliders. The chain behaves as a single system with H[k] = H1[k]H2[k]. The order does not matter, since numbers commute: H2H1 = H1H2. And the combined impulse response is the convolution h1 ⊛ h2, because that is what multiplies spectra. A quick check: two 2-point averages, [1/2, 1/2] each, give [1/2, 1/2] ⊛ [1/2, 1/2] = [1/4, 1/2, 1/4], a wider, softer smoother. Blurring twice is blurring once with a wider blur.
Now the second question. Suppose the blur h1 is known and you hold only the blurred result y. Can you recover x? The slide’s formula points the way: Y[k] = H1[k] X[k], so divide.
This is deconvolution: the reverse of convolution. The slide stops at the cascade, but this step is its direct consequence: undoing a system is the same as cascading it with a system whose sliders are 1/H[k], so that every product is 1. Sound reasoning, with a trap in it.
A blur works by shrinking fast waves. A Gaussian blur of width 2 samples on a loop of 64 has H[k] near 1 for slow waves and about 10−9 for the fastest ones. The fast waves in the blurred photo are almost, but not exactly, zero. Real recordings carry some noise n, and the noise has fast waves in it too. The recording is Y[k] = H[k]X[k] + N[k], and the division gives
X̂[k] = Y[k]/H[k] = X[k] + N[k]/H[k]
The first term is the original. The second is the noise divided by a tiny number. Where H[k] is 10−9, noise a thousand times smaller than the picture becomes a million times bigger than it. The recovered signal is buried.
In the debugger’s three steps. The symptom: the “sharpened” signal is wild noise, and the more noise in the recording, the worse it gets. The measurement: plot the gain 1/|H[k]| against frequency. It explodes at exactly the frequencies where the blur removed information. The fix: divide only where it is safe. A common recipe is the regularized inverse, X̂[k] = H∗[k] Y[k] / (|H[k]|² + λ), where H∗ is the complex conjugate and λ is a small positive number. Where |H| is large the formula behaves like 1/H. Where |H| is tiny it gives up and returns almost zero. This is the idea behind Wiener filtering and Tikhonov regularization, which this lesson does not derive.
Teal: the sharp original. Blue: the blurred, noisy recording. Green: your recovery. Purple line, top: the blur’s gain at each frequency on a log scale. Start with no noise, then add some, then switch to the regularized inverse.
Toy signal: a loop of 64 samples holding a block of height 1, a narrow spike and a ramp. The blur is a circular Gaussian of the chosen width in samples. The noise levels are none, 0.001, 0.003, 0.01, 0.03 and 0.1 (standard deviation per sample, fixed seeded hiss). The regularized inverse uses λ = 0.001. The error is the root mean square difference between the recovery and the original.
With no noise, even the plain inverse recovers the original to many digits. Add the smallest noise and it collapses; the error becomes larger than the signal itself. The regularized inverse stays calm, and trades a little sharpness for it. Raising the blur width makes everything worse, because more frequencies fall into the dead zone of H.
The same maths sits behind sharpening a blurry photo, removing the room from a recording (dereverberation) and equalizing a long cable. In each, the honest statement is: you can undo a system only as far as it did not erase information beneath the noise.
Chapter 10
Learn two ways to find a system’s impulse response in practice, and see why a sweeping tone beats a sharp click when noise is around
You want to know how a concert hall treats sound. Chapter 3 says: send one sharp spike and record what comes back. So you fire a starter pistol and record. The result is a mess. The bang is loud, but the hall’s faint tail is lost in the hiss of the microphone and the rumble of the street. The tail is where the reverb lives.
The lecture ends with this practical problem in two slides: how do you estimate h[n] for a real system? The first slide gives the obvious answer. The second gives a cleverer one.
The eighteenth slide says: generate an approximation to δ[n]. It shows two plots. The first is a narrow spike in continuous time. The second is the discrete impulse, a single stem of height 1 among zeros.
In a computer, the ideal spike is easy: a list that is 1 at position 0 and 0 elsewhere. In the real world no speaker can make an infinitely short, infinitely tall bang. A balloon pop, a spark, a clap or a very short click is the closest you get. It is an approximation, short enough that the system cannot tell it from a spike.
When the probe is a spike, the answer comes for free. Since p = δ, the output is y = h ∗ δ = h. The recording is the impulse response, plus whatever noise the microphone added. That is the weakness: a spike is brief, so it carries little energy. Noise has the same size whether your probe is brief or long.
The nineteenth slide offers the alternative: a signal that sweeps the frequency from low to high. It shows a wave that starts as a slow swing and keeps getting faster until it is a blur. This is a chirp, named for the rising whistle of a bird.
The chirp excites one frequency after another, spending a short stretch of time at each. Over its whole length it touches every frequency the system can pass. The recording is no longer h itself, but a long, smeared version of it: y = h ∗ p where p is the chirp. We undo that smear with Chapter 9: divide the spectra.
Chapter 9 warned that dividing by a tiny number multiplies the noise. So a good probe has a P[k] that is never tiny: it must carry energy at every frequency we care about. A spike does (its spectrum is flat). A chirp does too (it spends time at each frequency). A probe that skips a band, say a single tone, would leave P[k] near zero everywhere else, and the estimate at those frequencies would be pure noise.
Real speakers have a peak limit, a loudest sample they can play without distorting. Say it is 1. A spike of height 1 has energy, the sum of squared samples, of exactly 1. A chirp of N = 128 samples at the same peak of 1 is a cosine all the way through, so its energy is about 128 × 1/2 = 64 (the exact value for the chirp in the device below is 68). It has about 64 times the energy at the same peak.
By Parseval, which says that energy in time equals energy in frequency, a chirp has |P[k]| ≈ √(N/2) = 8 at each frequency, while a spike has |P[k]| = 1. When we divide by P[k], the noise is divided by 8 for the chirp and by 1 for the spike. The estimate is about 8 times closer to the truth, or 20 log10 8 ≈ 18 dB better. Both methods have the same peak and the same noise. Only the energy, and how it is spread, changed.
A worked example with noise of 0.2 per sample: the spike’s estimate of every tap is off by about 0.2. A tap of height 0.18 is smaller than the noise and is lost. The chirp’s estimate is off by about 0.2 / 8 = 0.025, so the 0.18 tap shows up clearly. Try it.
The hidden impulse response has six echoes. Top: the probe you send, always with a peak height of 1. Bottom: warm rings are the true response, blue stems are your estimate from the noisy recording. Choose a probe and raise the noise.
Illustrative: a loop of 128 samples, six echoes of height 1, 0.6, −0.45, 0.3, 0.18 and −0.1, and fixed seeded Gaussian noise scaled by the slider and added to the recording. The chirp is cos(πn²/(2N)), which sweeps from 0 to half the sampling rate. The estimate divides spectra with a tiny safety term. Error is root mean square over all 128 taps.
At a noise of 0.2 the pulse estimate is a forest of noise taller than the small echoes, with an error of about 0.21 per tap. The chirp estimate has an error of about 0.027, and all six echoes stand clear. The ratio of 8 holds at any noise level, because noise and probe scale together. Set the noise to zero and both are exact, which shows that the difference is purely about noise.
Measuring a system by probing it and dividing is called system identification. Audio engineers measure rooms, loudspeakers and microphones this way, commonly with swept tones. The same idea sits inside the echo canceller from Chapter 5, which learns the response while you talk instead of sending a probe. Our adaptive filters lesson shows how.
The symptom to remember: an impulse response measured with a short click looks noisy and its tail is flat hiss. The measurement: repeat the click several times and average, or compare with a chirp measurement; the tails disagree. The fix: send a longer probe with the same peak and divide, so that each frequency has more energy against the same noise.
Chapter 11
Review the whole lecture on one page: the numbers, a checklist, the core code, and where the ideas lead next
You can now rebuild the fifth lecture of Stanford’s EE269 from memory. It asks one question: what two promises let a short measurement predict a system’s output for every input? Linearity and time invariance answer it. Everything after follows by calculation.
A system turns a signal into a signal. It is linear if a mix of inputs gives the same mix of outputs, and time-invariant if a delayed input gives a delayed output. An LTI system is both. Write the input as a pile of spikes and use both promises, and the output is the input convolved with the impulse response h, the output for one spike. On a loop of N samples, convolution is a circulant matrix. Its eigenvectors are the Fourier vectors, with the DFT of h as eigenvalues, so in frequency the whole system is one multiply per wave: Y[k] = H[k]X[k]. Chains multiply their spectra. Undoing a system divides, which fails where the system erased the signal below the noise. And to measure h in practice, send a chirp, which carries far more energy than a click at the same peak.
| What | Number | Why it matters |
|---|---|---|
| Convolution length | N + M − 1 (4 + 3 − 1 = 6) | The flipped response overlaps the input at that many positions |
| Echo example | h = [1, 0, 0.5], x = [2, −1, 3], y = [2, −1, 4, −0.5, 1.5] | Three scaled copies of h, added column by column |
| Circular, N = 4 | [2.67, 2.33, 2, 3] against six ordinary samples | The tail wraps onto the start unless N ≥ len(x) + len(h) − 1 |
| Smoother’s sliders, N = 4 | H = [1, −j/3, 1/3, j/3] | Steady level passes, fast waves shrink to a third |
| Room 6 m by 4 m | direct 3.61 m at 10.5 ms; first echo 5.00 m at 14.6 ms | Each route is one spike of the impulse response |
| Blur of width 2 on 64 samples | smallest gain about 5 × 10−9 | Dividing by it multiplies noise about two hundred million times |
| Chirp against pulse, same peak | energy 68 against 1; error 8 times smaller (18 dB) | More energy at every frequency against the same noise |
| Direct against FFT convolution, N = 65,536 | about 4.3 billion against a few million operations | Order of magnitude only; it depends on the code |
| Term | Meaning | Chapter |
|---|---|---|
| Superposition | T of a mix equals the mix of the T’s | 1 |
| Time invariance | Delay the input, delay the output the same | 2 |
| Impulse response h[n] | The output for a single spike | 3 |
| Convolution | Flip, slide, multiply, add; y = x ∗ h | 4 |
| Circulant matrix | Every row is the row above, pushed right by one, wrapped | 6 |
| Frequency response H[k] | The DFT of h; the gain and slide of each wave | 7 |
| Convolution theorem | Convolution in time is multiplication in frequency | 8 |
| Deconvolution | Undo a system by dividing spectra, with care | 9 |
| Chirp | A tone that sweeps from low to high frequency | 10 |
pythonimport numpy as np def fft_filter(x, h): # Ch 4 + 8: y = x * h as Y[k] = H[k] X[k] N = len(x) + len(h) - 1 # zero-pad so the loop is long enough (Ch 6) return np.fft.irfft(np.fft.rfft(x, N) * np.fft.rfft(h, N), N) def deconv(y, h, lam=1e-3): # Ch 9: regularized inverse, never plain 1/H H = np.fft.rfft(h, len(y)) return np.fft.irfft(np.conj(H) * np.fft.rfft(y) / (abs(H)**2 + lam), len(y)) def measure(y, p, eps=1e-3): # Ch 10: h from a probe p (a chirp) and the recording y P, Y = np.fft.fft(p), np.fft.fft(y) return np.real(np.fft.ifft(Y * np.conj(P) / (abs(P)**2 + eps * np.mean(abs(P)**2)))) # circular recording x = np.array([1, 2, 3, 4.]); h = np.ones(3) / 3 assert np.allclose(fft_filter(x, h), np.convolve(x, h)) # [0.33 1. 2. 3. 2.33 1.33]
Run the two lines of the last assert in your head: both sides give six numbers, because the padded loop has length 6. Replace N with 4 and they disagree on the first two samples, exactly as Chapter 6 showed.
This lecture is the base of nearly everything that follows in the course. The DFT you met earlier is the change of coordinates that diagonalizes every LTI system. The cepstrum and MFCC features of the next lesson take a logarithm to turn this lesson’s product of spectra into a sum, which separates a voice from the room around it. Stationary signals, adaptive filters and the convolutional layers of neural networks all use the same sliding sum. Convolution is the shared operation; the Fourier basis is why it is cheap to analyse.
The course is Stanford EE269, Signal Processing for Machine Learning, taught by Mert Pilanci. This lesson follows the Lecture 5 deck of 28 September 2020 and re-teaches it with our own examples and devices. Course site: web.stanford.edu/class/ee269. Slides: the course slides page.
Now press Present or Teach and explain, from memory, why one clap tells you everything about a room, and why the Fourier vectors pass through it unchanged in shape. Then go back to the instrument at the top, choose the echo, tap the input into a pattern of your own, and say which copies of the echo add up to a chosen output sample.