Skip to content

Delay-Doppler Search

A bank search: the map, the coarse straddle and the refine

What you're seeing

A code delayed by 37 samples arrives on a carrier 1.3 code bins off nominal, 15 dB under the noise in every sample. DelayDoppler correlates each of 16 code periods against the code and runs a slow-time FFT down every delay column, which gives a map of Doppler rows by delay columns. bank_detect searches the carrier too.

Left: the map at the best coarse carrier. The ringed cell is the detection: delay column 37, a Doppler row off zero. Everything else is the map's noise floor, 15 to 25 dB down.

Centre: the straddle, and the refine. The grey curve is the strongest cell's power under each carrier of an eighth-bin grid; its peak is the best the search can do. The orange dots are the coarse grid's half-bin steps: the true carrier (the red line, 1.3 bins) falls between two of them, so the best coarse carrier sits below the curve's peak. The green square is the refine: a quarter-bin step at the candidate's own cell, back on top.

Right: what the straddle costs. The coarse grid sits a few tenths of a dB below the best carrier, and the refine closes most of that (the script prints the numbers and asserts the ordering). The refine is 2 * ny * nx multiply-adds per carrier, with no FFT.

How it works

A delay-Doppler map corrects no carrier within a code period, so a carrier d code bins off costs the Dirichlet factor of d (about 0.9 dB at a quarter bin, 3.9 dB at half a bin, 19 dB at 0.9 bin, and a null at a whole bin): an unknown offset is searched. A bank corrects each frame to the nearest carrier of its grid, so what it loses is the factor of the residual to that carrier. The bank makes one map per carrier on a coarse grid, and every carrier shares the frame's row transforms, so a half-bin grid costs half what a quarter-bin grid does. Each candidate is then refined at its own cell:

import numpy as np

from doppler.spectral import DelayDoppler

NX, NY, DELAY = 128, 16, 37  # code length, periods per frame, code delay
CARRIER_BINS = 1.3  # the carrier, in code bins (1 / NX cycles/sample)
SNR_DB = -15.0  # per sample; the map's gain is NY * NX = 33 dB
NO_RATES = np.empty(0, np.complex64)

rng = np.random.default_rng(2683)
code = rng.choice(np.array([-1.0, 1.0]), NX).astype(np.complex64)


def noise() -> np.ndarray:
    n = rng.standard_normal(NY * NX) + 1j * rng.standard_normal(NY * NX)
    return (n / np.sqrt(2)).astype(np.complex64)


m = np.arange(NY * NX)
signal = np.tile(np.roll(code, DELAY), NY) * np.exp(
    2j * np.pi * CARRIER_BINS / NX * m
)
x = (10 ** (SNR_DB / 20) * signal + noise()).astype(np.complex64)

The thresholds come from noise-only frames, as a detector's must: the strongest coarse cell in 50 noise frames sets the candidate threshold, and the confirm threshold sits a little above it.

dd = DelayDoppler(code, ny=NY)
COARSE = (-4, 5)  # carriers g / (2 NX): -2 to +2.5 bins, on half bins

# Thresholds from noise alone: the strongest coarse cell in 50 noise frames,
# with margin, for the candidate; the confirm a little above it.
floor = max(
    float(dd.bank_power_max(noise(), 2, *COARSE, NO_RATES)[0].max())
    for _ in range(50)
)
t_candidate, t_confirm = 1.2 * floor, 1.5 * floor

power, g, rate, row, col = dd.bank_detect(
    x, 2, 4, *COARSE, t_candidate, t_confirm, NO_RATES
)
coarse_peak = float(dd.bank_power_max(x, 2, *COARSE, NO_RATES)[0].max())

print("record  delay  Doppler row  carrier (bins)  refined / coarse peak")
for k in range(len(power)):
    print(
        f"  {k}      {col[k]:3d}      {row[k]:3d}          {g[k] / 4:+5.2f}"
        f"           {power[k] / coarse_peak:.3f}"
    )

One record comes back, at the code's delay, on the quarter-bin carrier nearest 1.3 bins, and stronger than the coarse grid saw it. The curve in the centre panel is one single-carrier bank per step of an eighth-bin grid:

# What the straddle looks like: the strongest cell's power under each carrier
# of an eighth-bin grid (-2 to +3 bins), one single-carrier bank apiece.
fine = np.arange(-16, 25)
curve = np.array(
    [
        float(dd.bank_power_max(x, 8, int(g), int(g), NO_RATES)[0].max())
        for g in fine
    ]
)
best = float(curve.max())
loss_coarse = 10 * np.log10(coarse_peak / best)  # dB below the best carrier
loss_refined = 10 * np.log10(float(power[0]) / best)
print(
    f"best carrier on the eighth-bin grid: {fine[np.argmax(curve)] / 8:+.3f} "
    f"bins; coarse grid {loss_coarse:+.2f} dB, refined {loss_refined:+.2f} dB"
)

Trying many hypotheses in one batch

One batch of eight hypotheses, and the winner's map

A bank is what a batch of corrected frame copies computes, without the copies. When the hypotheses are frames of your own (a different carrier removed from each copy, say), hand them over as one batch:

import numpy as np

from doppler.spectral import DelayDoppler

NX, NY, DELAY = 128, 16, 37  # code length, periods per frame, code delay
OFFSET_BINS = 2.4  # true carrier offset, in code bins (1 / NX cycles/sample)
STEP_BINS, H = 0.5, 8  # hypothesis spacing and count

rng = np.random.default_rng(2683)
code = rng.choice(np.array([-1.0, 1.0]), NX).astype(np.complex64)

m = np.arange(NY * NX)
rx = np.tile(np.roll(code, DELAY), NY) * np.exp(
    2j * np.pi * OFFSET_BINS / NX * m
)
removed = STEP_BINS * np.arange(H)
batch = np.concatenate(
    [rx * np.exp(-2j * np.pi * r / NX * m) for r in removed]
).astype(np.complex64)

Left: each hypothesis's own peak-to-mean. The one that left the signal most compact (green) is the one nearest the true 2.4 bins. Right: that hypothesis's map, with the delay found at column 37.

dd = DelayDoppler(code, ny=NY, nthreads=0)  # 0: every core
peak, row, col, mean = dd.execute_peaks(batch)
ratio = peak / mean
best = int(np.argmax(ratio))

print("hypothesis  removed (bins)  peak/mean  delay")
for h in range(H):
    print(
        f"  {h:2d}          {removed[h]:4.1f}        {ratio[h]:8.1f}   "
        f"{col[h]:3d}"
    )
print(
    f"best: hypothesis {best} ({removed[best]:.1f} bins removed; "
    f"true offset {OFFSET_BINS})"
)

power, which = dd.execute_power_max(batch)
cell = int(np.argmax(power))
print(
    f"strongest cell over all maps: delay {cell % NX}, "
    f"from hypothesis {which[cell]}"
)

execute_peaks ranks the hypotheses by each map's own statistics; execute_power_max keeps, cell by cell, the strongest map and which one it was. Neither touches the object's dwell.

These commands run from a clone of the repository at the release you installed; the make targets and the ./build/ binaries are not in the wheel. Skip this if you already have one:

git clone --branch v0.81.0 https://github.com/doppler-dsp/doppler && cd doppler

Run it

In a virtual environment (see Get it for why, and for Debian and Ubuntu's one extra package):

python3 -m venv .venv && . .venv/bin/activate
pip install "doppler-dsp[examples]"   # matplotlib + scipy, once
python -m doppler.examples.delay_doppler_bank_demo
python -m doppler.examples.delay_doppler_batch_demo
./build/native/examples/delay_doppler_bank_demo      # the C twins
./build/native/examples/delay_doppler_batch_demo

See the Delay-Doppler Search guide for the map, the batch calls and the bank in words, and the Spectral API for every method.