Also known as: m-sequence, MLS, maximum-length sequence, PN sequence
A maximal-length sequence (m-sequence) is the longest non-repeating binary sequence that an n-stage linear-feedback shift register can generate — period 2ⁿ − 1 — and it has a near-ideal two-valued autocorrelation that makes it behave like random noise while being fully deterministic.1 These pseudo-noise (PN) properties make the m-sequence the foundational building block of spread-spectrum codes, scramblers, and channel-measurement waveforms.
How it works
An LFSR shifts its bits each clock and feeds back the XOR of certain tap positions into the input. The register has 2ⁿ possible states, but the all-zeros state is a dead end (it produces only zeros), so the best any n-stage LFSR can do is cycle through all 2ⁿ − 1 non-zero states before repeating. It achieves that maximum period precisely when the feedback taps correspond to a primitive polynomial over GF(2) — that is the defining condition for a maximal-length sequence.
Over one full period an m-sequence has three “randomness” properties that make it look like a coin-flip stream:
- Balance — the number of 1s exceeds the number of 0s by exactly one.
- Run distribution — runs of consecutive equal bits follow the geometric distribution expected of random data.
- Two-valued autocorrelation — correlated against a shifted copy of itself (bits mapped to ±1), it returns the full length N at zero shift and exactly −1 at every other shift. That flat, single-valued sidelobe floor is the key property: it lets a matched-filter correlator pinpoint code phase unambiguously, and it is what a spread-spectrum receiver exploits to despread its wanted signal.
The weakness is that a single m-sequence is linear: observing only 2n consecutive output bits reveals the taps (via the Berlekamp–Massey algorithm), so on its own it is cryptographically worthless and, for multi-user systems, different-length shifts of one m-sequence can cross-correlate badly.
Variants and derived codes
Because a lone m-sequence has poor cross-correlation, richer families are built from it: XOR-ing two preferred m-sequences yields a Gold code family with bounded mutual interference (the GPS/CDMA workhorse), and a related construction gives Kasami codes. Where a strictly ±1 sidelobe floor and very short length are needed instead, the distinct Barker codes are used.
Relevance to SDR
M-sequences and their derivatives are everywhere in RF: they seed the Gold codes of GPS and CDMA, act as scrambling/whitening sequences in DVB, GSM, and digital voice framing, provide the excitation for channel sounding (their flat autocorrelation makes correlating the received sequence a direct impulse-response measurement), and serve as pilot/sync patterns.
Within GopherTrunk’s land-mobile targets, LFSR-generated PN sequences appear as scramblers that whiten payload data (for example the pseudo-random scrambling in some digital voice frames) — the scanner reproduces the same PN generator to de-scramble before decoding. GopherTrunk does not implement a spread-spectrum despreading correlator, since its protocols are narrowband, but the m-sequence machinery documented here is directly relevant to its de-scrambling and sync-detection code.
Sources
-
Maximum length sequence — Wikipedia, for the 2ⁿ−1 period, primitive-polynomial condition, and two-valued autocorrelation. ↩