Corr2D hypothesis bank: operation order¶

A bank of hypotheses on one frame, many carrier offsets each with several Doppler-rate weightings, shares every stage that does not depend on the hypothesis. This page sets the order the rest runs in, and how a carrier offset between whole bins is applied. It serves #2683 (batch maps and reductions on Corr2D/DelayDoppler) and #2670 (acq's rate search on DelayDoppler's primitive). §1–§4 are pinned by a prototype that make docs-check runs. §5 times them in C, from preamble-short codes to 1023, and shows that the order of the stages, not the method, is what sets the cost. The bank mixes per fraction. §6 splits the grid in two: it detects on \(L_d = 2\) and refines each candidate to \(L_r = 4\), which matches \(L = 4\)'s sensitivity for 44% less work.

1. The question¶

A hypothesis bank runs one frame through many hypotheses: carrier offsets, each with several Doppler-rate weightings. Run every hypothesis through the whole pipeline and the cost is the pipeline times the hypothesis count. But every stage before the power is linear, so the stages commute, and the order they run in is free. This page fixes that order, and how a carrier offset between whole bins is applied.

DelayDoppler's pipeline for one frame of \(n_y\) periods of \(n_x\) samples, with code \(c\), a carrier correction \(f\) and a slow-time weight \(w_r\) per period \(r\):

where \(x_r[n]\) is period \(r\) and \(n\) counts within it, \(0 \le n < n_x\).

2. Ordering rules¶

1. Non-linear last. Power, max and any statistic come after every linear stage.
2. Share the prefix. What does not depend on the hypothesis runs once per frame: the row FFT always, and the row correlation when only \(w\) varies.
3. Carrier outer, rate inner. \(f\) acts on the row spectrum before the reference multiply, so each carrier hypothesis pays the row inverses. \(w_r\) is a per-period scalar, so it commutes with the per-period transforms and each rate hypothesis can share them. Since #2752 step 2.3 the map that runs it is the library's one delay-Doppler map (acq-surface §18), which takes the order with fewer transforms for a call's carriers per fraction and rates. Rows first, each carrier's inverses are shared by its rates and a rate pays only the slow-time FFT. Slow first, a fraction's slow time is shared by its whole-bin carriers and a rate pays their rows. A bank with many rates runs rows first.
4. The carrier is corrected within a period only. The mix restarts at every period (\(n\) counts within the period, above). The phase a carrier adds between periods is slow-time Doppler, which the slow-time FFT measures. Leaving it alone puts a signal on the same, absolute Doppler row under every carrier hypothesis, so a pointwise reduction across carrier hypotheses compares like cells.

3. Carrier offsets on a \(1/(L\,n_x)\) grid¶

A whole-bin offset \(k/n_x\) is a circular roll of each row's spectrum. An offset between whole bins is reached exactly in one of two ways. Both are pinned equal to the full pipeline in §4.

Zero-pad, then roll. Pad each row to \(M = L\,n_x\) and transform once. The offset \(g/M\) is then a stride-\(L\) gather, and its whole-bin part is just where the gather starts:

Mix per fraction. Write \(g = L k + j\). Mix each row by \(e^{-j 2\pi j n / M}\) for each of the \(L\) fractions \(j\), take an \(n_x\)-point FFT of each, and roll by \(k\).

Mixing per fraction does fewer operations, by \(\log_2 n_x / \log_2 (L\,n_x)\). Zero-pad then roll makes one pass and one plan. §5 times both; the bank mixes per fraction.

An offset between grid points takes the nearest one, and loses the Dirichlet factor of the residual within a period. The worst case is half a grid step, which is \(\mathrm{sinc}(1/(2L))\) to within \(10^{-4}\). At \(n_x = 512\):

4. What the prototype pins¶

corr2d-hypotheses-measurements/prototype.py states the full pipeline in numpy and checks it against the shipped DelayDoppler first, so every other comparison is against what ships. It then runs both orderings over a grid of signed whole and fractional offsets. The stimuli use continuous offsets and delays, because a signal placed on the grid hides the droop and the straddle. make docs-check runs it with --check. A claim that fails, or a table here that differs from what the prototype renders, fails the gate.

5. Cost¶

Op counts per frame at the request's geometry: \(n_y = 64\), \(n_x = 512\), \(n_{y,\text{out}} = 64\) (assumed; #2683 does not state it), 4 carrier hypotheses (\(L = 4\)) by 12 rate hypotheses. Units are millions of \(N \log_2 N\) per FFT.

Counted, ordering cuts the work about 3x, and about 78% of what is left is the slow-time FFT.

Op counts are not times. Real code lengths are \(2^n - 1\), where an FFT is slowest; \(L\,n_x\) changes the length's factors; the gathers and mixes are memory-bound; and a pool splits each stage its own way. So the harness native/validation/corr2d_hypothesis_order.c times one whole frame through three pipelines. The first is the full pipeline: every hypothesis mixed, weighted and run through the shipped DelayDoppler. The other two are the ordered pipelines, one per method of §3. Every pipeline folds all its maps into one accumulator, and CTest holds the three equal to \(10^{-4}\). The carriers are the \(L\) fractions of one whole bin; whole-bin offsets cost both methods the same roll. One run, rendered by corr2d-hypotheses-measurements/record.py:

On one thread:

On a pool, at the default \(L = 4\), each time beside the same pipeline's time on one thread:

What the run shows:

1. Ordering is the lever; the method is not. On one thread the two methods of §3 are within 7% of each other in every row, and within 3% at the powers of two. The full pipeline is 1.5–6.5x slower. The gap is widest at the \(2^n - 1\) lengths, where it pays a slow row FFT twice per map and an ordered pipeline pays once per carrier.
2. The bank mixes per fraction. Mixing needs only \(n_x\)-point row plans, which Corr2D already keeps per worker, and holds one fraction's spectra at a time. Zero-pad then roll needs an \(L\,n_x\)-point plan per worker and a row buffer \(L\) times the frame, for no gain on one thread. On a pool it is ahead here only because it makes one forward dispatch where this harness's mix makes \(L\). The bank's row stage dispatches once for all fractions.
3. Dispatch once per carrier, never once per map. A dp_pool_run wakes every helper and waits for each, whatever the work (#2696). Its cost therefore grows with the pool, and at these map sizes it is larger than the work of most stages. That is why the shipped full pipeline, at two dispatches per map, is slower on every pool than on one thread. The ordered pipelines' slow-time stage dispatches once per carrier, with the rates split across workers and innermost in the tile loop. Each correlated tile is then read once per carrier.
4. Short frames run on one thread. Even dispatched once per carrier, an ordered frame is slower on any pool than on one thread at every length up to 256: 1.5–2.5x on 4 workers from 127 to 256, and 3–8x at 32 and 64. Preambles are that short. At 512 it breaks even on 4 workers and loses on 18; only at 1023 does it gain (0.6–0.94x). So the bank splits one frame across workers only at long codes, and a batch spreads whole frames across workers instead.
5. The slow-time FFT is the next target. It is most of an ordered frame: 87–93% at the powers of two, and 50–72% at the \(2^n - 1\) lengths.
6. \(L\) is a loss budget, not a speed choice; the default is 4. An ordered frame's time grows in proportion to \(L\) at every length, since every carrier costs the same. \(L = 4\) holds the worst loss to 0.22 dB (§3) for twice the time of \(L = 2\), which at \(n_x = 64\) is 0.31 ms a frame against 0.15.

6. Detect coarse, refine the candidate¶

\(L\) buys sensitivity only at the moment of detection. After a detection, the fraction is resolved at one cell, where it costs almost nothing. So the bank detects on a coarse grid and refines each candidate on the fine grid:

1. Detect on \(L_d = 2\): half the carrier hypotheses of \(L = 4\), so half the bank. Its threshold is set for a candidate rate (here \(10^{-2}\) per search), not for the final \(P_{fa}\).
2. Refine each candidate at its cell only: the two fine hypotheses (\(L_r = 4\)) on either side of the coarse one that found it, at the same delay and Doppler row. That is a time-domain correlation at one lag and a slow-time DFT at one row: \(2\,n_y\,n_x\) multiply-adds a candidate, with no FFT.
3. Confirm on the refined value, against a threshold that sets the final \(P_{fa}\).

The fraction a caller gets back is \(L_r\)'s, so what \(L = 4\) resolved, the refine still resolves. What changes is the cost.

Measured by the bank's characterization (spectral/tests/characterization/corr2d_bank/characterize.py, through bank_power_max and bank_detect): a repeated 511-chip PN m-sequence, 64 periods, at a uniform delay, whole bins \(k \in \{-1, 0, 1\}\), in the shipped AWGN. Every detector's thresholds come from its own 20,000 noise-only frames at \(P_{fa} = 10^{-3}\) per search, and the oracle corrects the exact carrier at L = 4's threshold. Pd is at the SNR where the oracle detects about 0.9, 1,000 trials a row, with Wilson 95% intervals:

On fresh noise each held its rate: \(1.00 \times 10^{-3}\), \(0.95 \times 10^{-3}\) and \(1.00 \times 10^{-3}\) (intervals \([0.6, 1.5] \times 10^{-3}\)). At the worst fraction \(L = 2\) alone loses detections and detect-and-refine does not: it matches \(L = 4\). Noiseless, the worst case loses the full sinc(1/4), 0.912 dB, exactly as §3 says; in noise \(L = 2\) alone loses less (the de-risk prototype put it at 0.37 dB of SNR), because two coarse hypotheses straddle the signal and their max claws some back, and half the cells lower its threshold. The refine recovers the rest.

Cost. By §5's run at \(n_x = 512\) with 12 rates on one thread, an \(L = 2\) frame is 1.84 ms against \(L = 4\)'s 3.31 ms: 44% less. The shipped bank measures the same at 64 x 512 with no rates (bench_corr2d_core.c, bench_bank, one thread, aarch64): 12 carriers in 1.11 ms, 6 in 0.54 ms, 48%. The refine adds 0.17 ms a candidate, three fine carriers at \(2\,n_y\,n_x\) multiply-adds each, so bank_detect with one candidate runs in 0.71 ms. Against the frame batch of 12 hand-corrected copies a caller would otherwise build, 1.35 ms before the copies, the bank is 1.21x: the row FFT is shared per fraction, and the slow-time stage is not.

The bank, as shipped. \(L\) splits into \(L_d\) (the search, default 2) and \(L_r\) (the resolution, default 4). §5's "the default is 4" stays true of the resolution. A caller who wants one stage sets \(L_d = L_r\). dp_correlator_bank_fold hands every hypothesis map to a C reducer; dp_correlator_bank_power_max and dp_correlator_bank_detect are bound as bank_power_max and bank_detect on Corr2D and DelayDoppler. On the fast path and DelayDoppler with a native delay axis, the refine is a time-domain correlation at the cell's lag and one Doppler DFT; anywhere else it makes the fine map and reads the cell. Every path runs a bank, and only those two share work. A bank runs on the calling thread (#2716 is splitting hypotheses across workers).

Where this is certified. The Corr2D report's §2.11 holds five limits: the bank equals the corrected batch on every path; it leaves the dwell alone and refuses what it should; the loss between grid points is at most sinc(1/(2L)), and exactly that half a step out; bank_detect names the fine carrier, and its refine is the fine bank's own value; and every detector holds its \(P_{fa}\), with detect-and-refine matching \(L = 4\), at a small scale. The full-geometry Monte Carlo is src/doppler/spectral/tests/characterization/corr2d_bank/characterize.py, run by make characterize, with its fast twin per push.