Prev
Unit 10 · Lesson 10-3
Spread Spectrum and Correlation
1h 30m1300 XP

Spread Spectrum and Correlation

Correlation and the matched filter, pseudo-random codes, processing gain, direct-sequence spread spectrum, and GPS acquisition in code phase and Doppler

11 August 1942 — a patent from Hollywood
Hedy Lamarr is a Hollywood film star. She had learned, at her first husband's arms deals, that navies wanted radio-guided torpedoes — and that radio guidance could be jammed. With the composer George Antheil, whose Ballet Mécanique had tried to synchronise several player pianos, she worked out a way to defeat jamming: transmitter and receiver hop together among many frequencies in a pre-arranged pattern, kept in step like the piano rolls. US Patent 2,292,387 is granted on 11 August 1942, under her legal name, Hedy Kiesler Markey. The Navy rejects the idea as too large to fit in a torpedo (Hedy Lamarr). Spread spectrum became foundational decades later; Bluetooth, Wi-Fi and GPS use principles related to it, and in 1997 Lamarr received the Electronic Frontier Foundation's Pioneer Award (Hedy Lamarr). Every GPS satellite spreads its signal with a 1023-chip code repeating every millisecond (GPS signals), and it arrives at your receiver about 19 dB below the thermal noise in a 2 MHz band (TU Delft, GNSS receivers). Correlation finds it anyway.
Derivation
The matched filter
Look for a known shape s[n]s[n], NN samples long, in white noise of variance σ2\sigma^2. Pass the received signal through a filter hh and sample at the moment the pulse would end. The signal part of the output is ∑kh[k] s[N−1−k]\sum_k h[k]\,s[N-1-k]; the noise part has variance σ2∑kh[k]2\sigma^2\sum_k h[k]^2. By the Cauchy–Schwarz inequality,
SNRout=(∑kh[k] s[N−1−k])2σ2∑kh[k]2≤∑ks[k]2σ2=Esσ2,\text{SNR}_{\text{out}} = \frac{\big(\sum_k h[k]\,s[N-1-k]\big)^2}{\sigma^2\sum_k h[k]^2} \le \frac{\sum_k s[k]^2}{\sigma^2} = \frac{E_s}{\sigma^2},
with equality when h[k]=s[N−1−k]h[k] = s[N - 1 - k]: the filter is the pulse reversed in time. Filtering with it is correlating with the template, and the output SNR is the pulse's energy over the noise variance — NN times the per-sample SNR. In the lab a 255-chip pulse at −10 dB per sample is found at exactly the right sample: a gain of 10log⁡10255=24.110\log_{10}255 = 24.1 dB.
💡Pseudo-random codes
A good code looks like noise but correlates like a spike. Maximal-length sequences, generated by an nn-stage shift register with feedback, have period 2n−12^n - 1, are almost perfectly balanced, and have a circular autocorrelation of 2n−12^n - 1 at zero lag and exactly −1-1 at every other lag. For n=10n = 10 the lab finds 1023 chips, 511 of one sign and 512 of the other, and a 60.2 dB peak-to-sidelobe ratio. GPS combines two 10-stage shift registers into Gold codes, a family whose members also correlate weakly with each other, so that every satellite can share one frequency ([GPS signals]({GPSS})).
💡Direct-sequence spread spectrum
Multiply slow data by a fast code and the spectrum spreads to roughly the chip rate. At the receiver, multiplying by the same code, correctly aligned, despreads the wanted signal back into its narrow band while spreading everything else — noise, jammers, other users — across the wide one. The processing gain is about the ratio of chip rate to data rate: GPS's 1.023 million chips per second carry 50 bits per second ([GPS signals]({GPSS})), a ratio of about 20 000, or 43 dB. That is how a signal some 20 dB below the noise ends up comfortably above it after correlation.
📐Acquiring a satellite
A receiver knows each satellite's code but not its code phase — where in its 1023-chip cycle the arriving code is — nor its Doppler shift, which the satellite's motion makes several kilohertz. Acquisition searches both: for each Doppler bin, wipe off that carrier offset and correlate with the local code at every phase at once, by FFT. In the lab, the code of PRN 1 — whose first ten chips, 1440 in octal, match the interface specification — arrives 20 dB below the noise with a phase of 317 chips and a Doppler of +2500 Hz. A search over 21 bins finds both exactly, with a coherent gain of 33.1 dB from one millisecond of data.
We can only see a short distance ahead, but we can see plenty there that needs to be done.
– Alan Turing, "Computing Machinery and Intelligence" (1950), quoted on Wikiquote
🕰Player pianos and radio
Antheil's Ballet Mécanique (1923–24) had tried to start four player pianos at once with matching rolls so that they played in time; the frequency-hopping patent used the same kind of mechanism, miniaturised, to keep transmitter and receiver in step. Lamarr and Antheil submitted the idea to the National Inventors Council in late December 1940, and Caltech's Samuel Mackeown advised on its electrical design (Hedy Lamarr).
⚠Correlation needs the right Doppler
A residual carrier offset Δf\Delta f rotates the signal's phase by 2πΔfT2\pi\Delta f T during a correlation of length TT, and the correlation shrinks by ∣sinc⁡(ΔfT)∣|\operatorname{sinc}(\Delta f T)|. For T=1T = 1 ms, an offset of 500 Hz costs about 4 dB and 1 kHz wipes the signal out — which is why acquisition searches Doppler in bins a few hundred hertz wide.
💡Where signals and systems go next
From here the subject branches. Control builds on poles, feedback and state (Units 7 and 8) into state-space and optimal control. Signal processing continues into adaptive filters and the Kalman filter. Communications goes on to information theory, coding and modern modulation. Navigation combines everything in this lesson with orbits and clocks. Each is a course of its own — and each starts from the ideas you now have.
📚Further reading
  • Pratap Misra and Per Enge, Global Positioning System: Signals, Measurements, and Performance (2nd ed., Ganga-Jamuna Press, 2006).
  • GPS signals on Wikipedia — the C/A codes and how they are generated.
  • Hedy Lamarr on Wikipedia.
↓But there is a problem
This course began with a sound recorded in 1860 that no one could play back for a century and a half, and it ends with a signal from space that is weaker than the noise around it and is found every time. Between them lie the same few ideas, used again and again: signals as functions, systems as operators, frequency as the natural language of linear systems, and the transforms that move between time and frequency. The signals around you — radio, sound, vibration, light, data — are all now open to you. Go and read them.