Overlap-Add-Fold

Overview

A software-defined radio captures far more spectrum than the one station you want to hear, so a receiver has to cut that station out and lower the sample rate before it can demodulate anything. In the United States, broadcast FM channels are 200 kHz wide,^[1] so a 2 MS/s capture holds ten of them and carries ten times more samples than one station needs.

The Multi-FM Receiver does this job with a single Filter block. This flowgraph splits that block into its steps, fast convolution by FFT, spectral folding, and overlap-add, and gives each step its own block. It tunes to 96.9 MHz, cuts out 97.3 MHz and 96.5 MHz at 200 kS/s each, and plays 96.5 MHz while a waterfall shows it. Running it needs an antenna for the FM broadcast band, stations 400 kHz on either side of the tuned frequency, speakers or headphones, and a radio supported by SoapySDR, such as an RTL-SDR.

How it works

The radio delivers eight batches of 8,000 samples per update, 32 ms of signal. Filter Taps designs two 101-tap Blackman-windowed sinc filters with their half-amplitude points at ±100 kHz,^[2] shifted to +400 kHz and $-400$ kHz.

Convolving 8,000 samples with 101 taps produces 8,100 outputs, so the batches and the filters are both zero padded to 8,100 before their FFTs. Without the padding, the filter's tail would wrap around to the start of the batch. Multiplying the two spectra filters every batch. Expand Dims gives the radio spectrum a channel axis of length one, so Multiply broadcasts one radio transform against both filters.

Keeping every tenth sample in time is the same as averaging the ten 810-bin segments of the spectrum,^[3]

where $P$ is the filtered spectrum and $Y$ the spectrum of the decimated signal. Fold does exactly this, so the inverse FFT runs on 810 points and the output rate is 200 kS/s. The filter has already removed what would otherwise land on the station, and because ±400 kHz is a multiple of 200 kHz, both stations fold down to 0 Hz.

Decimation also shrinks the 100-sample tail to 10 samples. Unpad splits each 810-sample result into 800 samples for this batch and that tail, and Overlap Add adds the tail to the start of the next batch.^[4] The result matches convolving the stream with each filter and keeping every tenth sample. Slice then picks one channel, which feeds the FM Demodulator and Audio block, as in the Simple FM Receiver, and a Spectrum Engine and Waterfall.

What to look for

The notes on the canvas quote the tensor shape at each stage.

The waterfall shows the selected channel after overlap-add, 200 kHz wide, with the station centered as a band that widens and narrows with the program. Its frequency axis stays centered on 96.9 MHz, because the radio's tuning passes through every block unchanged, so read it as a window around 96.5 MHz. A station that is not exactly 400 kHz from the tuned frequency sits off center, or is missing.

For a kernel of $M + 1$ taps, the transition from passband to stopband is about $4/M$ of the sample rate wide,^[2] which is 80 kHz for these 101 taps. Attenuation starts about 60 kHz from the channel's center and is down to 1% about 140 kHz out, so only the nearest edge of a neighbor 200 kHz away leaks in. The Multi-FM Receiver's 51 taps give 160 kHz. In fast convolution the extra taps cost little, since the transform grows only from 8,050 to 8,100 points.

Changing Slice from [:, 1, :] to [:, 0, :] switches the audio and the waterfall together to 97.3 MHz.

For a deeper treatment of fast convolution and decimation, see the sources below.

Going further

To measure what overlap-add fixes, give a Python block two inputs and no outputs, connect the first to the Unpad block's Output port, not its Pad port, and the second to the Overlap Add output, and paste the code below. If you change the taps, set TAIL to Unpad's Pad Size. It compares the power in the first 10 samples of each batch with the rest, averaged over 31 updates, about one second. Before overlap-add the start of each batch reads low, because it is missing the previous batch's tail. After it the ratio is close to 0 dB.

import numpy as np

UPDATES = 31
TAIL = 10

_EDGE = np.zeros(2)
_REST = np.zeros(2)
_CALLS = 0


def compute(ctx):
    global _EDGE, _REST, _CALLS
    for i in range(2):
        power = np.abs(np.asarray(ctx.inputs[i])) ** 2
        _EDGE[i] += power[..., :TAIL].mean()
        _REST[i] += power[..., TAIL:].mean()
    _CALLS += 1
    if _CALLS % UPDATES == 0:
        ratio = 10 * np.log10(np.maximum(_EDGE, 1e-30) / np.maximum(_REST, 1e-30))
        print(f"Batch start: {ratio[0]:+.1f} dB before, {ratio[1]:+.1f} dB after overlap-add")
        _EDGE[:] = 0.0
        _REST[:] = 0.0

Frequency can change freely. Each Center must be a multiple of 200 kHz, or its station folds down away from 0 Hz, and no more than 800 kHz from the tuned frequency, so the station's whole channel stays inside the capture. The Filter block in the Multi-FM Receiver adds a per-channel shift before folding, which lifts that limit.

The sizes are tied to the number of taps. With $N$ taps the radio's Pad adds $N - 1$ zeros, the filter's Pad adds 7,999, one less than the batch length, Fold's Size is the padded length divided by 10, and Unpad removes $(N - 1)/10$ samples. Both $N - 1$ and the batch length must be multiples of 10, so the tail survives decimation whole and every batch starts on the decimated grid.

Filter Taps' Sample Rate must match the radio's. Fold's Size, not Bandwidth, sets the output rate, so the FM Demodulator and Audio sample rates must follow it.

The block catalog, tensors, and the Python block reference cover the blocks and shapes used here.

References