Part VII · Applications · Lesson 20

Finding an echo

Codes that look like noise but line up with themselves in only one place.

You’ll learn: how a receiver finds a known signal buried in noise, why a difference set makes every wrong guess look the same, and why the best such codes are the Singer sets with $q = 2$.

Listening for an echo

A radar sends out a pattern of pulses and listens for the echo. The echo comes back late, and the delay tells how far away the target is. But the echo is weak and arrives buried in noise. A sonar, a GPS receiver, and a sound engineer measuring a concert hall all face the same problem: where, in all this noise, is my pattern, and how late is it?

The receiver keeps a copy of the pattern, the template. It slides the template along what it received, and at each shift it measures how well the two match. The shift with the best match is its guess for the delay.

Codes of +1 and −1

Our pattern is a code: a list of $v$ numbers, each $+1$ or $-1$, sent over and over. Write $s_0, s_1, \dots, s_{v-1}$ for its entries, and $r_0, r_1, \dots, r_{v-1}$ for what arrives.

Below, the code is hidden in the received signal at a delay you don’t know. Drag the template shift slider and watch the score: at most shifts it hovers near zero, and at one shift it jumps. Press Find the echo to let the receiver pick the best shift, then try more noise, a longer code, or a random code.

The two charts at the bottom compare each code with an exact copy of itself, with no noise. The m-sequence code of length $v$ scores $v$ when lined up and exactly $-1$ at every other shift. The random code scores $v$ when lined up too, but its other scores wander up and down. Those bumps are false echoes waiting to happen: add noise, and one of them can beat the real peak.

Why the floor is flat

The m-sequence code is built from a difference set $D$, a set of $k$ points on a clock with $v$ hours in which every nonzero difference occurs $\lambda$ times (λ is the Greek letter lambda; see Lesson 1). Put $s_i = -1$ when $i$ is in $D$, and $s_i = +1$ otherwise.

Compare the code with itself shifted by $t$, a shift that is not $0 \pmod v$. Entry by entry, the product is $+1$ where the two agree and $-1$ where they disagree. They disagree exactly at the points that are in one of $D$ and $D + t$ but not in the other. By Lesson 2, $D$ and $D + t$ share exactly $\lambda$ points, so each has $k - \lambda$ points the other lacks: $2(k - \lambda)$ disagreements in all, and $v - 2(k - \lambda)$ agreements. So

The score at every wrong shift is the same number. (For the codes of 0s and 1s in Lesson 19, the same counting gives $k$ at shift 0 and $\lambda$ everywhere else.)

Which difference sets make good codes?

We want the wrong shifts to score as little as possible compared with the peak $v$. Here is $v - 4(k - \lambda)$ for a few Singer sets:

For the planes, the wrong-shift score is $q^2 - 3q + 1$, which grows quickly: planar Singer sets with large $q$ are poor $\pm 1$ codes. (They do better in the on/off settings of Lessons 19 and 21–23.) But for the Singer sets of $\mathrm{PG}(m, 2)$ from Lesson 16, $k - \lambda = 2^{m-1}$, so $4(k - \lambda) = 2^{m+1} = v + 1$, and every wrong shift scores exactly $-1$ against a peak of $v$.

Those are the codes in the widget. They are called maximal-length sequences, or m-sequences, and a shift register makes them: a row of bits that moves along one place per tick, with a few of the bits added (mod 2) to make the next one. As Lesson 16 explains, the positions of the 0s in one period form the Singer set. For length 7 the bits are 1, 0, 0, 1, 0, 1, 1: the 0s sit at $\{1, 2, 4\} = \{0, 1, 3\} + 1$.

Where these codes work

• Radar. Sending a long coded pulse and correlating the echo against it is called pulse compression. A 1986 Raytheon patent uses maximal-length shift-register codes for this, and a 1979 ITT patent uses a maximal-length code precisely because its periodic correlation sidelobes are constant at $-1$.
• Measuring sound. Play an m-sequence (it sounds like hiss) through a loudspeaker, record it with a microphone, and correlate. Because the code’s own correlation is a single spike, the result is the room’s echo pattern itself. D. D. Rife and J. Vanderkooy described this in 1989, and it became the basis of a commercial analyser used to measure loudspeakers and rooms.
• GPS, with a twist. Each GPS satellite’s C/A code adds together, bit by bit, two m-sequences of length 1023 made by 10-bit shift registers. Each of the two is a Singer-type sequence, but their sum is a Gold code, which is not a difference set: its correlation takes three values instead of two. That trade buys something a single m-sequence can’t give: the codes of different satellites look unlike each other, so a receiver can pick out each one.
• Scrambling data. The DARC data channel for FM radio (Lesson 21) mixes its bits with an m-sequence of period 511 from the shift register with polynomial $x^9 + x^4 + 1$, a step called scrambling.

Look at the $(15, 7, 3)$ set in the difference set workbench: every difference occurs exactly 3 times, which is what makes the floor flat.

Sources

• S. W. Golomb and G. Gong, Signal Design for Good Correlation, Cambridge University Press, 2005: m-sequences and cyclic difference sets.
• Q. Xiang, a survey of two-level autocorrelation sequences, on their equivalence with cyclic difference sets.
• J. D. Collins (Raytheon), “Processing arrangement for pulse compression radar,” US patent 4,566,010 (1986). Google Patents
• J.-C. A. Debuisser (ITT), “Autocorrelation sidelobe suppression device for a continuous periodic phase-coded signal,” US patent 4,156,876 (1979). Google Patents
• D. D. Rife and J. Vanderkooy, “Transfer-function measurement with maximum-length sequences,” Journal of the Audio Engineering Society 37 (1989), 419. AES library
• GPS interface specification change notice IRN-IS-200N-003 (2023), describing the C/A code as the sum of two 1023-chip sequences. gps.gov PDF
• ITU-R Recommendation BS.1194-2 (1998), the DARC system. ITU PDF