Chapter 2 found one setting in which a numerical scheme for the wave equation is exact: the leapfrog scheme in one dimension at Courant number 1. This chapter takes that result seriously. If the scheme is exact, its grid is doing nothing but moving numbers one node along per step, and a computation that only moves numbers along can be done without the grid.

The grid is a delay line#

At $\lambda = 1$ the solution on the grid is $u_j^n = F(j-n) + G(j+n)$: a right-moving sequence and a left-moving one, each shifted by one node per step. At a fixed end each is reflected into the other with a change of sign. So the whole state of the string is two sequences of length $N$ travelling in opposite directions, which is two delay lines joined at their ends by inverting reflections; this is the digital waveguide of Smith (1992). Following one sample round the loop, it travels $2N$ nodes and is inverted twice, so it returns unchanged after $2N$ steps, and the signal at any node repeats itself with period $2N$ samples. The pitch is $f_s/(2N)$.

A signal that repeats itself with period $D$ needs no grid at all. It needs a buffer holding one period and the rule

which costs one operation per sample instead of $N$.

The lab runs Chapter 2's scheme at $\lambda = 1$ for one second of sound on grids from 25 to 3200 intervals, seeds the loop with the first $2N$ samples of the result, and lets the loop run on its own for the rest of the second. The two recordings agree to a relative difference of about $10^{-11}$, the rounding error of the leapfrog run. The cost is the point. On this machine the leapfrog scheme takes time proportional to $N$, about a second at $N = 3200$, while the loop takes about a millisecond whatever the length, which at $N = 3200$ is a factor of several hundred; in the browser it is larger still. The comparison is not quite fair to the grid, which also computes the displacement everywhere along the string, but a listener only hears one point.

A string that decays#

A lossless loop rings for ever. Karplus and Strong (1983) observed that putting a two-point average inside it,

makes it sound like a plucked string. The average is a filter with gain $\cos(\omega/2f_s)$ at angular frequency $\omega$, which is one at zero frequency and falls towards the Nyquist frequency, so each partial loses a little on every trip round the loop and the high partials lose more. It also delays every frequency by exactly half a sample, so the loop's length is $P + \tfrac12$ samples and its pitch is $f_s/(P + \tfrac12)$.

The decay this gives is fixed by the filter and the pitch together. The fundamental loses a factor $\cos(\pi f_0/f_s)$ per period, so it takes

seconds to fall by 60 dB. Every octave up, the decay time falls by a factor of eight.

The tuning problem#

The loop's length is a whole number of samples plus one half, so the pitches it can play are $f_s/(P + \tfrac12)$ and nothing in between. For a note of frequency $f$ the desired length is $D = f_s/f$, and rounding it to the nearest available length leaves an error of up to half a sample in $D$, which is a pitch error of up to $866/D$ cents. At A2, $D = 401$ and the worst case is about two cents. At C7, $D = 21$ and it is about forty. At the top of the piano, $D = 10.5$ and it is about eighty.

The remedy is a delay of a fraction $\eta$ of a sample, and the script offers two. Linear interpolation between two taps, $(1-\eta)y_{n-P} + \eta\,y_{n-P-1}$, has exactly the right delay at low frequency but is itself a low-pass filter, so it adds to the loop's loss by an amount that depends on $\eta$. A first-order allpass filter,

has gain exactly one at every frequency, so it adds no loss, and a delay that is $\eta$ at low frequency and drifts away from it towards the Nyquist frequency (Jaffe and Smith 1983).

The measurements, one note on every third key from C2 to C8, confirm all three statements. With the loop rounded to a whole length, the pitch error is within 2 cents up to about 260 Hz, grows roughly in proportion to the note's frequency above that, and reaches 47 cents at F♯7, nearly a quarter-tone. Both fractional delays fix it: the worst error with linear interpolation is 0.14 cents and with the allpass 0.63 cents, both at the top of the keyboard, where a partial at a sizeable fraction of the sampling rate sees the filters' frequency-dependent delay.

The decay plot shows the price of each. The whole-sample loop and the allpass decay identically, along a line of slope $-3$: a C2 would ring for about 9700 seconds, nearly three hours, an A4 for 32 seconds, a C6 for 2.4 seconds and a C8 for 36 milliseconds. None of these is what a real string does, and the enormous spread is the best-known weakness of the plain Karplus–Strong string. Linear interpolation cuts the decay time by up to a half, erratically from note to note, because its loss depends on $\eta$, which jumps as the note changes.

The scale is played high up, from C6 to C8, where the differences are. Against the exact-pitch reference, played by modal synthesis with the same decay per partial, the whole-sample loop is audibly out of tune on several notes. The two tuned versions are close to the reference in pitch, and differ from each other mainly in how long the notes ring.

What this chapter establishes#

In one dimension an exact scheme can be run without its grid, and the result costs one operation per sample. This is why digital waveguides and Karplus–Strong strings, rather than finite-difference grids, are what synthesisers actually use for strings and tubes. The price is that the loop's length is quantised, and a fractional-delay filter is needed to play in tune; the allpass is the usual choice because it adds no loss.

The limitations are as clear as the strengths. The waveguide needs a uniform medium, so that waves travel at one speed, and a geometry in which they travel along lines. A stiff string, whose partials are sharp by an amount that grows with frequency, needs further filters in the loop, and a membrane or a room cannot be reduced to a loop at all: in two and three dimensions waves spread in every direction and there is no Courant number at which the leapfrog scheme is exact. That is where Part II begins.