Real-time processing

A filter that runs live gets its samples one at a time, and it must remember the last few. Below, an 8-point moving average keeps its last 8 inputs in a ring of 8 slots. Watch the write head come back to slot 0 at $n=8$ .

A circular buffer: the write head goes round

The last 8 inputs of an 8-point moving average, x[n] = n, in 8 slots.

n = 0: x[0] = 0 goes into slot 0. The other slots are still empty (0).

sample n

write slot

0 mod 8 = 0

y[n]

0.00

Describe this picture

Two panels and no control, for the last 8 inputs of an 8-point moving average, $x[n]=n$ , in 8 slots. The first is a ring of 8 boxes, with the slot numbers 0 to 7 outside it. Each box holds its value, such as “x[3] = 3”, and the newest value is in bold. An arrow, the write head, points at slot $n\bmod8$ . The second panel draws the outputs $y[n]$ , from 0 to 9, against the sample $n$ from 0 to 11, as stems with square heads. The readouts are the sample $n$ , the write slot and $y[n]$ .

Every slot starts at 0, which is the rule $x[n]=0$ before the start. The clip lasts 14 s and writes one sample a second; each write turns the head and drops the value in, with a blank caption. At $n=0$ , $x[0]=0$ goes into slot 0, and the other slots are still empty. Each hold names the step, such as “n = 5: slot 5 gets x[5] = 5; y = 15/8 = 1.88.” At 7.5 s all 8 slots are full, and $y[7]=(0+1+\dots+7)/8=3.50$ . From $n=8$ to 11 the head is back at slot 0 and overwrites the oldest inputs, $x[0]$ to $x[3]$ ; the slots then hold $x[4]$ to $x[11]$ , nothing was shifted, and $y[11]=7.50$ . A bracket over the stems from $n=8$ to 11 reads “slots 0 to 3 again”.

A circular buffer: the write head goes round

Most filters on this site so far ran on a stored signal: all of $x[n]$ was there before we started. A filter in a phone call or a guitar pedal cannot wait for that. Its samples arrive one at a time, and each output must be ready before the next sample comes. That is real-time processing.

Take the 8-point moving average of Simple smoothing filters (18.2):

y[n]=\frac18\sum_{k=0}^{7}x[n-k].

To compute it, the filter must remember its last 8 inputs. The obvious way keeps them in a row and shifts the row along by one place every sample. That is 8 writes per sample: 7 old values move, and the new one goes in at the front.

There is a cheaper way. Keep the 8 inputs in 8 numbered slots, and let each new sample overwrite the oldest one. Nothing moves. Sample $n$ goes into slot $n\bmod8$ , the remainder of Properties of the DFT (13.3). The slot to write next is the write index. This arrangement is a circular buffer.

The picture at the top of the page fills such a buffer with $x[n]=n$ , one sample at a time. Watch $n=8$ . The head is back at slot 0, and $x[0]$ is gone, overwritten by $x[8]$ . That is right, because the average no longer needs it. It is like a clock’s hour hand: after 12 it comes round to 1 again.

The same idea works for any FIR filter with $N_h$ taps. Its $N_h$ slots hold the last $N_h$ inputs. The filter writes the new input into its slot and reads the older ones from theirs:

\begin{aligned} \text{slot of }x[n]&=n\bmod N_h,\\ \text{slot of }x[n-k]&=(n-k)\bmod N_h. \end{aligned}

Each sample costs one write instead of $N_h$ . The delay boxes in the diagrams of Filter structures (21.1) are a delay line, and a circular buffer is how a program stores one.

The maths behind it · cyclic shifts

Shifting the stored inputs along by one place, with the oldest coming round to the front, is a cyclic shift: the permutation matrix of 13.3, the identity with its columns rotated. A circular buffer applies that permutation to the slot numbers instead of to the values, so no data moves.

Smaller blocks: less latency, more load

A computer’s sound system does not hand you samples one by one. It collects them into a block of $N$ samples, then calls your function once with the whole block, and your function returns a block of outputs. That call is a callback. At sample rate $f_s$ , a block lasts

\text{block duration}=\frac{N}{f_s}.

While your callback works on one block, the sound system plays the outputs of the previous one. So the callback must finish before those run out. That moment is its deadline. If it misses it, the output has nothing to play, and you hear a click or a gap: a dropout.

How long does a sample wait? A sample at the start of a block waits one block for the block to fill. The block is then processed while the next one fills, and played after that. So the wait is about two blocks, and I call it the latency. Keeping two blocks in flight like this is called double buffering:

\text{latency}\approx\frac{2N}{f_s}.

Fast convolution (14.3) counted only the first block, the wait to fill. A live system pays the second one too, for its processing and hand-over.

Every callback has two costs. A fixed one comes with each call, whatever $N$ is: starting up, fetching the filter’s state, handing the block back. The other grows with the number of samples. I use a made-up but realistic plug-in as a model: 0.2 ms per call plus 4 µs per sample.

\begin{aligned} \text{processing time}&=0.2\ \text{ms}\\ &\quad+N\cdot4\ \mu\text{s}. \end{aligned}

The share of each block’s time that goes on processing is the load:

\text{load}=\frac{\text{processing time}}{\text{block duration}}.

Above 100 %, a block takes longer to process than to play, so every deadline is missed. The instrument below draws this at $f_s=48$ kHz. Its numbers come from the model above, not from a measurement of your own browser. Watch the latency and the load as the blocks shrink.

Smaller blocks: less latency, more load

Audio at 48 kHz in blocks of N samples. Model: each callback costs 0.2 ms plus 4 µs per sample.

512 samples: a block lasts 10.67 ms and its processing 2.25 ms, a load of 21.1 %. Latency, two blocks: 21.33 ms.

block N

512 samples (10.67 ms)

latency

21.33 ms

load

21.1 %

Block size N8

Describe this picture

One timeline for audio at 48 kHz in blocks of $N$ samples, with the model that each callback costs 0.2 ms plus 4 µs per sample. On the time axis, in ms, sits a row of blocks, outlined rectangles each $N/f_s$ long, labelled with $N$ when they are wide enough. Inside each block a filled bar shows its processing time. A block whose bar is longer than the block itself is outlined thick, with a cross at the end of its bar, and the first such block is labelled “late: dropout”; a late bar runs into the next block, so late bars take turns in an upper and a lower lane. Under the row, a bracket two blocks long is labelled “latency”. The readouts are the block size $N$ (with its duration), the latency and the load.

The clip lasts 14 s, with a blank caption while the blocks split or the axis zooms. The axis first runs from 0 to 24 ms, which holds two blocks of 512: a block lasts 10.67 ms and its processing 2.25 ms, a load of 21.1 %, and the latency, two blocks, is 21.33 ms. Then the blocks split in four. At 5.25 s, 128 samples, Web Audio’s own block: latency 5.33 ms, load 26.7 %. The blocks split in four again, and the axis zooms in 16 times, to 0 to 1.5 ms, so that two blocks of 32 fill it as two of 512 did. At 9 s, 32 samples: latency 1.33 ms, but the fixed 0.2 ms per call is now most of the work, a load of 49.2 %. At the end, 8 samples: each block lasts 0.17 ms but needs 0.23 ms, a load of 139.2 %, with a latency of 0.33 ms; every block is late and the sound drops out, and below 12 samples this model cannot keep up. After the clip the slider “Block size N” takes the powers of two from 8 to 1024; the arrow keys step one power of two, and Home and End jump to 8 and 1024. At 512, 128, 32 and 8 the caption is the clip’s; at the other sizes it has one form, such as “16 samples: latency 0.67 ms, load 79.2 %.” Blocks of 8 to 32 are drawn on the zoomed axis, 0 to 1.5 ms, 64 to 512 on 0 to 24 ms, and 1024 on 0 to 48 ms. The choice is kept in the link, as budget.N.

At 8 samples the processing bar is longer than the block. The latency is tiny, but nothing plays.

After the clip, set the block size yourself with the slider. Try 1024: the latency grows to 42.67 ms, but the load only falls to 20.1 %.

Why does the load stop falling? Put $f_s=48$ kHz into the two formulas, with times in ms, so a block lasts $N/48$ ms:

\begin{aligned} \text{load}&=\frac{0.2+0.004N}{N/48}\\ &=\frac{9.6}{N}+0.192. \end{aligned}

The fixed cost gives $9.6/N$ , which halves each time the block doubles. The per-sample cost gives 0.192 whatever the block, because 4 µs of work for each of 48 000 samples is 0.192 s of every second. So no block size brings this plug-in below 19.2 %.

The load reaches 100 % when $9.6/N=0.808$ , at $N=11.88$ . That is why this model cannot keep up below 12 samples. Choosing a block size is a trade: small enough for your latency budget, large enough to keep the load safely under 100 %.

The maths behind it · percentiles and queues

A callback does not take the same time on every call. Real systems size their buffers for a high percentile of the processing time, not its mean. Queueing theory adds a warning: waiting grows sharply as the load nears 100 %. In the simplest queue, a job waits on average one job’s time at 50 % load, and nine at 90 %.

What fits on a processor

The second question is whether the work fits at all. Choosing FIR or IIR (20.6) counted multiplies per sample. Multiply that by the sample rate and you get multiplies per second, which you can compare with what a processor can do.

Take a 100 MHz microcontroller that does one multiply-add per clock cycle: one multiply and one add, the step of a sum such as $\sum_k h[k]\,x[n-k]$ . At 48 kHz it has $100\,000\,000/48\,000=2083$ cycles for each sample. At 8 kHz it has 12 500.

The running spec of Filter specifications (18.1) runs at 8 kHz. 20.6 met it with a 26-tap FIR filter and an order-5 elliptic IIR filter costing 11 multiplies. A biquad of Audio equalisers and biquads (20.5) has five coefficients, so by 20.6’s count it costs 5 multiplies.

Job	Multiplies per sample	Sample rate	Multiplies per second	Share of 100 MHz
running spec, FIR, 26 taps	26	8 kHz	208 000	0.21 %
running spec, IIR, order 5	11	8 kHz	88 000	0.09 %
stereo 10-band equaliser, one biquad a band	10 × 5 × 2 = 100	48 kHz	4.8 million	4.8 %
reverb, FIR with 4096 taps	4096	48 kHz	197 million	197 %

Both running-spec filters use well under 1 % of this small processor. The equaliser takes about 5 %. The reverb needs nearly twice what the processor can do, so run directly it does not fit.

Fast convolution (14.3) rescues it, at a price. In blocks of 4096, with an FFT of 8192 points, 14.3’s formula gives 112 multiplies per output, about 5.4 % of the processor. But each block now waits 85.3 ms to fill: the block latency is back.

Worked example

1. The buffer index. An 8-slot ring receives sample $n=1000$ . It goes to slot $1000\bmod8=0$ , because $1000=125\cdot8$ . The input 5 samples earlier, $x[995]$ , is in slot $995\bmod8=3$ , because $995=124\cdot8+3$ .

2. Latency and load. Take blocks of 16 at 48 kHz. A block lasts $16/48=0.33$ ms, and the latency is two blocks, 0.67 ms. Processing takes $0.2+16\cdot0.004=0.264$ ms, so the load is $0.264/(16/48)=79.2$ %. The whole model, block size by block size:

Block N (samples)	Block duration	Processing	Latency	Load
8	0.17 ms	0.23 ms	0.33 ms	139.2 %
16	0.33 ms	0.26 ms	0.67 ms	79.2 %
32	0.67 ms	0.33 ms	1.33 ms	49.2 %
64	1.33 ms	0.46 ms	2.67 ms	34.2 %
128	2.67 ms	0.71 ms	5.33 ms	26.7 %
256	5.33 ms	1.22 ms	10.67 ms	23.0 %
512	10.67 ms	2.25 ms	21.33 ms	21.1 %
1024	21.33 ms	4.30 ms	42.67 ms	20.1 %

Suppose your latency budget is 5 ms. Two blocks must fit in it, so $N\le0.005\cdot48\,000/2=120$ , and the largest power of two is 64: 2.67 ms of latency at a load of 34.2 %.

3. Cycles. A 100 MHz processor at 48 kHz has $100\,000\,000/48\,000=2083$ cycles per sample. At 8 kHz it has 12 500, and the running spec’s 26-tap FIR uses 26 of them, 0.21 %.

Where you’ll meet this

Audio interfaces and their drivers let you choose a buffer size, usually from about 64 to 1024 samples. Musicians recording live pick a small one for low latency; mixing a finished song, they pick a large one so that nothing drops out.

In a browser, the Web Audio API’s AudioWorklet processes 128 frames per call by default, where a frame is one sample for each channel. At 48 kHz that block lasts 2.67 ms.

A hearing aid has a delay budget of about 10 ms in all (18.1). The buffers get only part of it, because the filters’ own delay and the converters take their share. So hearing aids use short blocks, or process sample by sample.

Microcontroller libraries such as Arm’s CMSIS-DSP give their filters a block size and a state buffer that holds the last inputs between calls. Many DSP chips compute $n\bmod N_h$ in hardware, so a circular buffer costs nothing extra there.

Real-time processing returns later: polyphase filters cut the work of a rate change (Polyphase structures, 22.4), adaptive filters update their taps sample by sample (Adaptive filters: LMS, 26.3), and effects run live in Audio effects (29.2).

Reference card

Quantity	Formula	Notes
Circular buffer	write slot $n\bmod N_h$ ; read $x[n-k]$ at slot $(n-k)\bmod N_h$	nothing shifts
Block duration	$N/f_s$	128 at 48 kHz: 2.67 ms
Latency (double buffering)	about $2N/f_s$	plus the converters’ own delay
Load	processing time / block duration	above 100 %: dropouts
Model of this page	$0.2$ ms $+\,N\cdot4$ µs per call; load $9.6/N+0.192$ at 48 kHz	100 % at $N=11.88$
Cost	multiplies per sample × $f_s$	compare with the processor’s rate
Cycles per sample	clock rate / $f_s$	100 MHz at 48 kHz: 2083

Real-time processing

First, the picture

A circular buffer: the write head goes round

Smaller blocks: less latency, more load

What fits on a processor

Worked example

Where you’ll meet this

Reference card