The Mathematics of the Digital Modes

The intermediate guide — every operating principle, with the theory and one worked example

The middle rung of the ladder: after the Beginner's Tour (no maths, pure intuition), before or alongside Protocol Commonalities (the engineer's systems view) and the full reproduction specs (every constant, for implementers).

The Beginner's Tour tells you what each mode does. Commonalities tells you why the designs keep reaching for the same dozen parts. This document answers the question in between, the one you hit the first time you open a spec and meet a phrase like "syndromes, Berlekamp–Massey, Chien search": how does that actually work — and can I see the numbers?

So here is the deal this document makes with you. For every operating principle used anywhere in the catalogue — modulation, correlation, synchronisation, information theory, CRCs, Hamming codes, finite fields, Reed–Solomon, Viterbi, LDPC, interleaving, scrambling, source coding — you get three things:

The idea, in plain language, connected to what you already saw in the Tour.
The maths, derived honestly but gently. Nothing is "it can be shown that"; if a result matters, you watch it happen.
One worked example with real numbers, small enough to check by hand. Every worked example in this document has been verified by machine against the arithmetic — if you redo one on paper and get a different answer, the error is on your side of the paper.

What you need to bring: comfortable algebra, a memory of what a sine wave and a logarithm are, and patience for one new object (the finite field — §7) that looks strange for about two pages and then becomes a friend. Complex numbers appear early; we build the intuition we need and no more.

Notation, once: $\oplus$ is XOR (addition modulo 2). $\mathrm{GF}(q)$ is the finite field with $q$ elements (§7). $\log$ is base-2 unless written $\ln$. $j=\sqrt{-1}$ (engineers' convention). Decibels: $x$ in dB means $10\log_{10}x$.

The route:

Part	Question it answers
1	What is a signal, mathematically?
2	How do you find a known signal in noise — optimally?
3	Why do FSK/PSK/chirps/OFDM work, and what do they cost?
4	How does a receiver find where and when?
5	How many bits can a channel carry at all?
6	How does a CRC catch errors?
7	How can parity bits correct errors?
8	What is GF(2^m) and why do strong codes need it?
9	How does algebra locate an error it has never seen?
10	How does Viterbi decode a stream?
11	How does belief propagation approach the Shannon limit?
12	What do interleavers and scramblers do, exactly?
13	How do varicode, packing, and vocoders squeeze the message?
14	Put it all together: FT8 audited against Shannon.

Part 1 — A signal is a number that spins

1.1 The phasor: why radio maths is complex-number maths

The idea. A pure tone is usually written $\cos(2\pi ft)$. That form is awkward: phase and frequency are trapped inside a trig function. The fix that unlocks everything is to represent the tone as a rotating point in the plane:

\[e^{j2\pi ft} = \cos(2\pi ft) + j\sin(2\pi ft)\]

Picture a clock hand of length 1 spinning anticlockwise $f$ times per second. The cosine you'd see on a scope is just its shadow on the horizontal axis. The two coordinates of the spinning hand are the I (in-phase) and Q (quadrature) samples your SDR hands you — an IQ stream is this spinning point, sampled.

        Q (imaginary)
        │     ● ←— the sample: amplitude = length,
        │    ╱        phase = angle, frequency = how
        │   ╱ θ       fast the angle advances
        └──╱────────  I (real)

The maths that pays rent. Multiplying two exponentials adds their exponents:

\[e^{j2\pi f_1 t}\cdot e^{j2\pi f_2 t} = e^{j2\pi(f_1+f_2)t}\]

So multiplication shifts frequency. Every mixer, every "tune to the signal" step, every de-chirp in LoRa, every FM discriminator is this one line. Three instant consequences you'll use all through this document:

Tuning: multiply the IQ stream by $e^{-j2\pi f_0t}$ and a signal at $f_0$ moves to 0 Hz, where it's easy to filter and slow to sample.
Instantaneous frequency is the rate the angle turns: $f(t)=\frac{1}{2\pi}\frac{d}{dt}\arg x(t)$. Differentiate the unwrapped phase of an FSK signal and the bits fall out — that's the discriminator AIS uses, one line of numpy.
Amplitude and phase separate cleanly: $|x|$ ignores phase (what an OOK/ISM envelope detector measures), $\arg x$ ignores amplitude (what a PSK demodulator measures).

1.2 Noise, and how much of it you get

Receiver noise is modelled as AWGN — additive white Gaussian noise. "White" means it has the same power density at every frequency: a constant $N_0$ watts per hertz of bandwidth. That per-hertz framing is the single most useful accounting convention in radio, because it makes noise power proportional to how much spectrum you choose to listen to:

\[N = N_0 B\]

Halve your bandwidth $B$ and you halve the noise power — while a narrowband signal's power stays put. Hold that thought; it is the entire secret of the weak-signal modes (§2.2).

Two SNR-like quantities appear everywhere, and confusing them costs real debugging time:

SNR — signal power over noise power in some stated bandwidth. WSJT-X reports SNR in a 2500 Hz reference bandwidth, which is why FT8 can decode at "−21 dB": in its actual 50 Hz occupied bandwidth that same signal is 17 dB less buried.
$E_b/N_0$ — energy per information bit over noise density. This one is fair across modes with different rates and bandwidths, so it's the currency all coding theory is priced in. Conversion: $E_b/N_0 = \frac{P}{N_0 R_b}$ where $R_b$ is the information bit rate. We'll use it to audit FT8 against Shannon in Part 14.

Part 2 — Detection: correlation against noise

2.1 Correlation, the one operation

The idea. Almost every receiver question — is my sync word here? which tone was sent? where does the frame start? — reduces to: how similar is the received chunk to a template I know? The measure of similarity is the correlation (an inner product):

\[c = \sum_n r[n]\,s^*[n]\]

Multiply the received samples by the conjugate of the template, sum. If the signal is present and aligned, every term adds coherently (all pointing the same way); noise terms point in random directions and mostly cancel. Signal grows like $N$, noise like $\sqrt{N}$ — so the longer you correlate, the better you hear.

2.2 The matched filter — and why it is optimal

The maths. Suppose the received signal is $r = s + n$ (template $s$, AWGN $n$), and you're allowed one linear operation — a filter $h$ — before deciding. The SNR of the filter's output is

\[\mathrm{SNR} = \frac{\left|\sum h\,s\right|^2}{\frac{N_0}{2}\sum|h|^2}.\]

The Cauchy–Schwarz inequality says $\left|\sum h\,s\right|^2 \le \sum|h|^2 \sum|s|^2$, with equality exactly when $h \propto s^*$. So the best possible filter is a time-reversed conjugate copy of the thing you're looking for — the matched filter — and the best achievable SNR is

\[\mathrm{SNR}_{\max} = \frac{2E_s}{N_0},\]

which depends only on the symbol's energy $E_s = \sum|s|^2$, not its shape. That last clause is worth reading twice: you can spend energy as a short loud pulse or a long quiet tone — detection performance is identical. The weak-signal modes choose long and quiet.

Two everyday disguises of the matched filter:

The receive half of a root-raised-cosine pulse-shaping pair (M17, LRPT, DVB-S) is the matched filter for the transmit half — one filter both bounds the spectrum and maximises SNR.
An FFT is a whole bank of matched filters, one per tone. Which brings us to the weak-signal superpower.

2.3 The FFT bin as a matched filter: buying dB with time

The maths. A DFT bin computes exactly $\sum_n r[n]e^{-j2\pi kn/N}$ — the correlation of the received block against a pure tone. If a tone of power $P$ lasts $T$ seconds, its bin collects signal energy $PT$. The bin's width is $1/T$ Hz, so it collects noise power $N_0/T$... and the ratio is

\[\mathrm{SNR}_{\text{bin}} = \frac{PT}{N_0} = \frac{E_s}{N_0}.\]

Doubling the symbol time halves the bin width, halves the noise in the bin, and adds 3 dB of sensitivity — for free, paid only in speed. This one line is the design rationale of the entire WSJT-X family:

Worked example. FT8's symbols last 0.16 s, so its FFT bins are $1/0.16 = 6.25$ Hz wide. A decoder that instead had to listen in the full 2500 Hz voice channel would admit $2500/6.25 = 400$ times more noise power — $10\log_{10}400 = 26$ dB. That is how a signal reported at −21 dB "below the noise" is, in the only bandwidth that matters (its own bin), comfortably above it: $-21 + 26 = +5$ dB. No magic — just bookkeeping about where the noise is allowed in.

2.4 Orthogonality: how close can two tones be?

Two tones can be told apart perfectly only if they are orthogonal — their correlation over one symbol is zero:

\[\int_0^T e^{j2\pi f_1 t}\,e^{-j2\pi f_2 t}\,dt = \int_0^T e^{j2\pi \Delta f\,t}\,dt = 0 \quad\Longleftrightarrow\quad \Delta f = \frac{k}{T},\ k\in\mathbb{Z}\setminus\{0\}\]

(the integral of a complex exponential over a whole number of turns is zero). So the minimum spacing for tones you detect by energy (non-coherently, taking $|{\cdot}|$) is $\Delta f = 1/T$ — and that's exactly why FT8's tone spacing (6.25 Hz) equals its symbol rate (1/0.16 s): the 8 tones land in adjacent, non-interfering FFT bins.

If the receiver tracks phase (coherent detection), only the real part of the correlation must vanish, and $\Delta f = \frac{1}{2T}$ suffices — half the spacing, same distinguishability. That halved spacing is MSK (minimum-shift keying), the ancestor of the GMSK used by AIS. (Check the two claims numerically: at $\Delta f = 1/T$ the complex integral is 0; at $1/(2T)$ its magnitude is $2/\pi \approx 0.64$ but its real part is 0.)

2.5 How often you'll be wrong: the Q function

The maths. After matched filtering, deciding a bit is deciding which side of a threshold a Gaussian-distributed number fell on. The tail probability of a unit Gaussian,

\[Q(x) = P(\mathcal{N}(0,1) > x),\]

is therefore the universal currency of error rates. For BPSK (two antipodal points $\pm\sqrt{E_b}$, distance $2\sqrt{E_b}$ apart):

\[P_b = Q\!\left(\sqrt{\tfrac{2E_b}{N_0}}\right).\]

Worked example. At $E_b/N_0 = 5$ dB ($=10^{0.5}=3.16$): $P_b = Q(\sqrt{6.32}) = Q(2.51) = 5.9\times10^{-3}$ — one bit in 170. At 7 dB: $7.7\times10^{-4}$. At 9.6 dB: $1\times10^{-5}$ — the classic textbook operating point. Notice the shape: each extra dB buys roughly an order of magnitude once you're on the steep part of the curve. This steepness is why a coding gain of "only" 6 dB (Parts 9–11) is transformative.

The same geometric picture prices every constellation: error probability is governed by the minimum distance between constellation points at fixed average energy. QPSK's four points keep the same per-bit distance as BPSK (its two bits ride independent I and Q axes — 2 bits/symbol free of charge, the best bargain in the catalogue). Pack 16 points into the same average power (16-QAM) and $d_{\min}^2$ drops by a factor 5 — you pay $10\log_{10}5 = 7$ dB for the extra two bits per symbol. That number is the whole story of why DVB-S2 reserves its dense constellations for strong links, and why HF keyboard modes stay at 2–8 points.

Gray coding, the free refinement: label neighbouring points with bit patterns that differ in exactly one bit, so the overwhelmingly-most-likely error (nearest neighbour) costs one bit, not several. The map is one line of algebra, $g = b \oplus (b \gg 1)$: binary 000→000, 001→001, 010→011, 011→010, 100→110… — walk the sequence and adjacent entries always differ by one bit. LoRa applies it to chirp bins, FT8 to its 8 tones, every QAM mode to its grid.

Part 3 — The modulations, mathematically

Part 1 of Commonalities walks the modulation zoo qualitatively; here we do the maths for the four mechanisms that carry everything in the catalogue: keyed tones, shaped phase, chirps, and OFDM.

3.1 FSK and MFSK: detection by energy

An $M$-tone FSK receiver is $M$ matched filters (= one FFT), followed by argmax of $|{\cdot}|$. Because the decision uses only magnitudes, it never needs phase — which is why FSK works through ionospheric phase churn that destroys PSK, and why every HF teleprinter descendant (RTTY, NAVTEX, Olivia, DominoEX/Thor) is FSK at heart. The price of ignoring phase is ~1 dB versus coherent detection — almost always worth it on HF.

Each symbol carries $\log_2 M$ bits, but the deep reason for large $M$ isn't rate — it's that one symbol's whole energy backs every bit, and long symbols ride the $E_s/N_0$ bin trick of §2.3. JT65 and Q65 take this to 65 tones of ~0.6–4 s each — and then pick a code whose symbols are the same 64-ary alphabet the demodulator measures (§9, §11.5), so nothing is lost translating.

3.2 Continuous phase and Gaussian shaping: GFSK/GMSK/C4FM

Snapping between two oscillators makes the phase jump; a phase discontinuity has energy at all frequencies — splatter. The cure is generative: build the signal in the phase domain,

\[\varphi(t) = 2\pi\!\int_0^t f(\tau)\,d\tau,\qquad x(t) = e^{j\varphi(t)},\]

where $f(\tau)$ is the bit-driven frequency trajectory, pre-smoothed by a Gaussian filter. The signal is then continuous by construction (an integral can't jump), and the Gaussian's bandwidth-time product $BT$ is the knob: smaller $BT$ = tighter spectrum but each symbol smears into its neighbours (ISI). AIS runs GMSK at $BT=0.4$; FT8 shapes its 8-FSK at $BT=2.0$ (gentle — the tones barely overlap); P25's C4FM and M17 put four deviation levels (±1, ±3) through a Nyquist filter, giving 2 bits per symbol on unmodified FM hardware. In code, the whole transmitter is: phase = cumsum(freq); iq = exp(1j*phase).

3.3 The chirp: LoRa's algebra

The idea. A LoRa symbol sweeps linearly across the whole bandwidth $B$, and the data is where in the sweep it starts (cyclically). One symbol carries $\mathrm{SF}$ bits by choosing among $2^{\mathrm{SF}}$ start offsets.

The maths. A base up-chirp over symbol time $T_s$ is $u(t)=e^{j\pi \frac{B}{T_s}t^2}$ (its instantaneous frequency, the derivative of phase $/2\pi$, is $\frac{B}{T_s}t$ — a straight ramp). A data symbol $s$ starts the ramp offset by $f_s = s\cdot\frac{B}{2^{\mathrm{SF}}}$. The receiver multiplies by the conjugate base chirp $u^*(t)$ — and the quadratic terms cancel:

\[\underbrace{e^{j\pi\frac{B}{T_s}t^2}e^{j2\pi f_s t}}_{\text{received chirp}}\cdot \underbrace{e^{-j\pi\frac{B}{T_s}t^2}}_{\text{de-chirp}} = e^{j2\pi f_s t}\]

— a pure tone at $f_s$. One FFT, one argmax, symbol decoded. All the energy that was smeared across $B$ collapses into one bin: the processing gain is the ratio of spread bandwidth to bin width, $2^{\mathrm{SF}}$ — i.e. $10\log_{10}2^{\mathrm{SF}}$ = 21 dB at SF7, 36 dB at SF12. That's how a $2 radio decodes below the noise floor.

The same algebra hands you synchronisation for free: a carrier offset of $c$ bins shifts a de-chirped up-chirp's peak by $c-s$ (with $s$ the timing offset in samples), but a down-chirp's by $c+s$. LoRa's preamble contains both kinds; add and subtract the two peak positions and both unknowns pop out in closed form — see the LoRa modem spec for the exact recipe.

3.4 OFDM: multipath defeated by the DFT

The idea. Echoes (multipath) smear each symbol into the next. Rather than equalise a fast single-carrier signal, DAB, HamDRM, Mercury and FreeDV send hundreds of slow symbols in parallel on closely-spaced subcarriers — generated all at once by an inverse FFT.

The maths, in three steps.

Orthogonality: subcarriers spaced $1/T$ satisfy $\sum_{n=0}^{N-1} e^{j2\pi kn/N}e^{-j2\pi mn/N} = 0$ for $k\ne m$ (a geometric series summing a whole number of turns — same integral as §2.4, discretised). Overlapping spectra, zero crosstalk.
The channel is a convolution: multipath means $y = h * x$ (each echo a delayed, scaled copy). Convolutions are messy — unless they're circular, in which case the DFT diagonalises them: $Y_k = H_k X_k$. Per subcarrier, the whole channel collapses to one complex multiply.
The cyclic prefix is the trick that makes it circular: copy the last $L$ samples of each symbol onto its front. As long as the longest echo is shorter than the prefix, the linear convolution the physics performs is indistinguishable, inside the FFT window, from a circular one. So step 2 legitimately applies, and equalisation is $\hat X_k = Y_k/H_k$ — estimated from known pilot cells sprinkled through the grid.

The bill: peak-to-average power (hundreds of carriers occasionally add in phase), and acute sensitivity to frequency error — a CFO of even a fraction of the subcarrier spacing tilts every carrier into its neighbour and the orthogonality of step 1 dissolves. OFDM modes therefore spend lavishly on sync (DAB's null symbol, DRM's pilots).

MT63 adds a twist worth knowing exists: it spreads each character across all 64 subcarriers with a Walsh transform (§11.6), so a notch that deletes several carriers dents every character slightly instead of destroying a few outright.

Part 4 — Synchronisation: the mathematics of where and when

4.1 What makes a good sync word

A sync pattern is found by sliding correlation (§2.1), so its quality is its autocorrelation: correlate the pattern against shifted copies of itself. You want a thumbtack — a tall spike at zero shift, near-zero everywhere else, so alignment is unambiguous.

Worked example. The 7-bit Barker sequence + + + − − + −:

shift	0	1	2	3	4	5	6
correlation	7	0	−1	0	−1	0	−1

Peak 7, every sidelobe magnitude ≤ 1 — a 17 dB spike-to-sidelobe ratio from 7 bits. Real sync words are chosen the same way (long, flat autocorrelation, and unlike anything the payload can produce): P25's 48-bit frame sync, the CCSDS marker 0x1ACFFC1D that LRPT hunts through all four QPSK phase rotations, HDLC's 0x7E flag (kept unique by bit-stuffing) framing AIS and APRS.

4.2 Costas arrays: a thumbtack in two dimensions

Weak-signal modes must find their signal in time and frequency at once, so FT8 syncs on a pattern in the time–frequency plane — 7 symbols using 7 tones, one per column:

tone 6  ·  ·  ·  ·  #  ·  ·
tone 5  ·  ·  ·  ·  ·  #  ·
tone 4  ·  ·  #  ·  ·  ·  ·        the FT8 Costas array
tone 3  #  ·  ·  ·  ·  ·  ·        (3, 1, 4, 0, 6, 5, 2)
tone 2  ·  ·  ·  ·  ·  ·  #
tone 1  ·  #  ·  ·  ·  ·  ·
tone 0  ·  ·  ·  #  ·  ·  ·
        t₀ t₁ t₂ t₃ t₄ t₅ t₆

A Costas array is a permutation (one mark per row and column) with a stronger property: the displacement vector between every pair of marks is distinct — among the $\binom{7}{2}=21$ pairs above, no (Δt, Δtone) repeats. Consequence: shift the pattern by any nonzero (Δt, Δf) and lay it over itself, and at most one mark can coincide (two coincident marks would be two pairs sharing a displacement). So the 2-D autocorrelation is 7 at the origin and ≤ 1 everywhere else — a perfect thumbtack, machine- checked for this array. The receiver correlates its waterfall against the array across a grid of candidate (time, frequency) cells; the aligned cell scores 7-for-7 while every wrong cell scores ≤ 1, and coarse acquisition needs no separate frequency search at all. FT8 sends the array three times (start/middle/end, so drift between them is measurable); FT4 uses four different 4×4 arrays; JS8 keys its submodes by which arrays it uses.

4.3 Estimating frequency and timing as numbers

Sync words locate a frame; tracking needs continuous estimates. Nearly all of them are one small idea each:

Frequency = phase slope. A residual carrier offset $\Delta f$ makes the received constellation rotate at a constant rate: $\arg(r[n]\,r^*[n-1]) = 2\pi\Delta f T_s$. Average that quantity and you have a frequency estimator (used at acquisition everywhere from Inmarsat-C to the WSJT-X fine-sync stages).
The Costas loop (carrier phase, for PSK): you can't lock a PLL to a BPSK signal directly because the modulation keeps flipping the phase by π. The Costas trick is an error signal that is blind to the data: $e = \Im(r)\cdot\Re(r)$ for BPSK (squaring away the ±1), fed through a loop filter into an NCO. LRPT and DVB-S run one; PSK31 sidesteps the need entirely by encoding data in phase changes (differential — at the price that one symbol error corrupts two decisions, since each decision reuses the previous symbol as its reference).
The Gardner detector (symbol timing): sample at twice the symbol rate and compute $e = \Re\{x^*_{\text{mid}}\,(x_{\text{cur}}-x_{\text{prev}})\}$. If you're sampling on time, the midpoint sample sits on the symbol transition and averages to zero; early or late, its sign says which way to nudge. It works before carrier lock (phase cancels in the product) — which is exactly the property you need during acquisition.

The rigid-clock alternative: FT8 dispenses with tracking loops entirely — both ends slave to UTC in 15 s slots, and the Costas correlation pins what remains. Removing the need for a loop is itself a design technique.

Part 5 — Information theory: the rules of the game

5.1 Entropy: how many bits a message truly contains

The idea. Information is surprise. A symbol that was certain to appear tells you nothing; a rare one tells you a lot. Shannon quantified it: a symbol of probability $p$ carries $\log_2(1/p)$ bits, and a source's average,

\[H = \sum_i p_i \log_2 \frac{1}{p_i}\ \text{bits/symbol},\]

is its entropy — a hard floor on lossless compression. No encoder, however clever, can average below $H$; good ones get close (worked example in §13.2).

English text runs ≈ 4.1 bits/letter by single-letter frequencies (far less with context), which is why sending 8-bit ASCII on a weak-signal channel is paying double, and why PSK31's varicode, JS8's Huffman+dictionary, and the WSJT-X 77-bit pack exist (§13).

5.2 Capacity: the speed limit, and the −1.59 dB floor

Shannon's second gift is an exact ceiling on what any channel can carry:

\[C = B\log_2\!\left(1+\frac{P}{N_0B}\right)\ \text{bits/s}\]

for bandwidth $B$, signal power $P$, noise density $N_0$. Below $C$, arbitrarily reliable communication is possible (that's the astonishing part — errors can be driven to zero without driving rate to zero); above it, impossible. Two limits are worth internalising:

Bandwidth-rich, power-poor (the weak-signal regime): as $B\to\infty$, $C \to \frac{P}{N_0}\log_2 e$. Even with infinite bandwidth, power caps your rate. Setting the energy per bit $E_b = P/C$ at that limit gives the famous floor:

\[\frac{E_b}{N_0} > \ln 2 = 0.693 = \mathbf{-1.59\ dB.}\]

Below −1.59 dB per information bit, no scheme — no code, no modulation, nothing — can work. Every real mode's distance above this floor is its remaining inefficiency, a number we'll compute for FT8 in Part 14.
Power-rich, bandwidth-poor (satellite TV): capacity grows only as $\log(1+\mathrm{SNR})$ — each extra bit/s/Hz costs ~3 dB more power. Hence DVB-S2's ladder of constellations and code rates, climbing exactly as far up as the link budget allows.

Coding gain, the metric the FEC parts of this document are priced in: the reduction in required $E_b/N_0$ at a fixed error rate, relative to uncoded transmission. Uncoded BPSK needs 9.6 dB for $10^{-5}$ (§2.5); a good LDPC system does it around 1–2 dB. That ~8 dB is a >6× power saving, conjured from structure alone.

Part 6 — The CRC: error detection as polynomial division

6.1 Bits as polynomials

Treat a bit string as the coefficients of a polynomial over GF(2) — arithmetic where addition is XOR and there are no carries: $10100111 \mapsto x^7+x^5+x^2+x+1$. In this world, addition and subtraction are the same operation ($1+1=0$), and long division works exactly like school division except each subtraction step is an XOR.

A CRC with generator $g(x)$ of degree $r$: append $r$ zero bits to the message $m(x)$ (i.e. form $m(x)\cdot x^r$), divide by $g(x)$, and transmit the $r$-bit remainder in those positions. The receiver divides the whole received block by $g(x)$: a clean block leaves remainder zero, because by construction the transmitted block is an exact multiple of $g(x)$.

6.2 Worked example

Message 10100111 (0xA7), generator $g(x) = x^3+x+1$ = 1011 ($r=3$). Append 000 and divide (each step: XOR the generator under the leftmost surviving 1):

  1 0 1 0 0 1 1 1 0 0 0      ← message · x³
  1 0 1 1
  ---------
  0 0 0 1 0 1 1 1 0 0 0
        1 0 1 1
        -------
  0 0 0 0 0 0 0 1 0 0 0
                1 0 1 1
                -------
  0 0 0 0 0 0 0 0 0 1 1      → remainder 011

Transmit 10100111 + 011. Receiver divides 10100111011 by 1011 → remainder 000: clean. Flip any single bit of the transmission and the remainder goes nonzero (a single flip changes the received polynomial by $x^i$, and $g(x)$ with more than one term can't divide a lone $x^i$). That's the whole mechanism — the CRCs in the catalogue differ only in width and generator: FT8's CRC-14 0x2757, AX.25's CRC-16 0x1021/0x8408 (AIS, APRS), ADS-B's CRC-24 0xFFF409. (The fully pinned parameter table — init values, final XORs, bit orders, and the traps between them — is Commonalities Appendix B.3.)

6.3 What a CRC provably catches

The algebra buys specific guarantees, each one line:

Every burst up to $r$ bits long. A burst starting at position $i$ of length $\le r$ is $x^i b(x)$ with $\deg b < r = \deg g$. Since $g$ doesn't divide $x^i$ (it has a nonzero constant term) and can't divide the lower-degree $b$, the remainder is nonzero. This is the CRC's signature strength, and why widths are chosen against expected burst lengths.
All odd numbers of bit errors, if $(x+1)$ divides $g(x)$ — every multiple of $(x+1)$ has even weight (it evaluates to 0 at $x=1$).
Any 2 random flips, as long as $g(x)$ is primitive with period exceeding the message length ($x^i + x^j = x^j(x^{i-j}+1)$, and a primitive $g$ divides $x^n+1$ only at its full period).
Everything else with probability $1 - 2^{-r}$ — a random corruption lands on a multiple of $g(x)$ one time in $2^r$.

The other job a CRC does in the modern modes: it polices the FEC. An LDPC decoder that converges to the wrong codeword produces a perfectly plausible message — the CRC is what catches the lie (FT8 checks CRC-14 after every LDPC decode; the deliberate cross-mode incompatibilities like JS8's final-XOR-42 are in the Commonalities table).

In implementations you'll meet the same division as a shift register (XOR $g$ in whenever the bit leaving the register is 1) or a 256-entry table processing a byte at a time — identical algebra, different unrolling.

Part 7 — Block codes: distance, spheres, and syndromes

7.1 Distance is everything

The idea. Error correction is possible when the valid codewords are far apart. The Hamming distance $d$ between two words is the number of positions where they differ; a code's minimum distance $d_{\min}$ is the closest any two codewords come. If $d_{\min} = 2t+1$, then even after $t$ flips the received word is still nearer its true codeword than any other — so "round to the nearest codeword" corrects any $t$ errors:

\[t = \left\lfloor \frac{d_{\min}-1}{2} \right\rfloor.\]

The crudest code makes the point. Repetition ×3 (send each bit three times, majority-vote): $d_{\min}=3$, corrects 1. At a raw bit error rate of $p=0.01$, a voted bit fails only if ≥2 copies flip: $3p^2(1-p)+p^3 = 3.0\times10^{-4}$ — a 33× improvement, bought with a brutal 3× rate cost. All of coding theory is the search for a cheaper way to buy distance.

7.2 Linear codes: the syndrome trick

A linear code is one where the XOR of any two codewords is a codeword. That structure gives you the whole toolkit:

Encoding is a matrix multiply over GF(2): $c = mG$ (generator matrix $G$).
Validity is a matrix multiply: $c$ is a codeword iff $Hc^\top = 0$ (parity-check matrix $H$).
And the pivotal fact: receive $r = c \oplus e$ (error pattern $e$) and compute the syndrome $s = Hr^\top = Hc^\top \oplus He^\top = He^\top$ —

the syndrome depends only on the error, not on the message. All the noise information is concentrated into a few bits, and decoding becomes "look up which error pattern produces this syndrome". Every algebraic decoder in this document — Hamming, BCH, Reed–Solomon, and (softly) LDPC — is a strategy for inverting $s = He^\top$.

7.3 The Hamming code, worked end to end

The Hamming(7,4) construction picks $H$'s columns to be the numbers 1–7 in binary. Then for a single error at position $i$, the syndrome is column $i$ — i.e. the syndrome literally spells out the error's address.

Lay out the codeword as p1 p2 d1 p3 d2 d3 d4 (parities at the power-of-two positions 1, 2, 4). Each parity covers the positions whose binary index contains its bit:

$p_1$ covers positions 1,3,5,7 → $p_1 = d_1\oplus d_2\oplus d_4$
$p_2$ covers positions 2,3,6,7 → $p_2 = d_1\oplus d_3\oplus d_4$
$p_3$ covers positions 4,5,6,7 → $p_3 = d_2\oplus d_3\oplus d_4$

Worked example. Data 1011 ($d_1{=}1, d_2{=}0, d_3{=}1, d_4{=}1$): $p_1 = 1\oplus0\oplus1 = 0$, $p_2 = 1\oplus1\oplus1 = 1$, $p_3 = 0\oplus1\oplus1 = 0$ → codeword 0110011. Now flip position 5 in transit: received 0110111. The receiver recomputes the three checks:

check	covers	parity of received
$s_1$	1,3,5,7	$0\oplus1\oplus1\oplus1$	= 1
$s_2$	2,3,6,7	$1\oplus1\oplus1\oplus1$	= 0
$s_4$	4,5,6,7	$0\oplus1\oplus1\oplus1$	= 1

Syndrome $(s_4s_2s_1) = 101_2 = \mathbf{5}$. Flip bit 5 back: 0110011. Corrected — the error was never found by search; its address was computed.

7.4 Perfect codes and the sphere bound

How good can a code be? Around each codeword, draw the "sphere" of words within distance $t$ — for Hamming(7,4), each sphere holds $1+7 = 8$ words (the word plus its 7 single-flip neighbours). Sixteen codewords × 8 = 128 = $2^7$: the spheres tile the entire space with no gaps — the code is perfect; not one bit of redundancy is wasted.

Perfect codes are vanishingly rare — beyond the Hamming family, exactly one nontrivial binary one exists, and the catalogue uses it: Golay(23,12), correcting $t=3$: $\binom{23}{0}+\binom{23}{1}+\binom{23}{2}+ \binom{23}{3} = 1+23+253+1771 = 2048 = 2^{11}$, and $2^{12}$ codewords × $2^{11}$ = $2^{23}$ exactly. P25 wraps its control words in Golay; M17 protects its LICH chunks with the extended (24,12) version.

In the catalogue. Hamming(8,4) guards every LoRa header nibble (the CR setting picks the payload's variant); P25 uses (15,11) and (10,6) throughout its control layer. Small codes for small fields — for payloads under fire, we need error budgets of dozens of symbols, and for that we need better arithmetic (next Part) and the big algebraic codes (Part 9).

Part 8 — The finite field: arithmetic with a safety net

8.1 Why we need it

Binary codes correct bits; real channels often smash runs of bits (a fade, a lightning crash, one corrupted FFT symbol). If we could do algebra on whole symbols — say, 6- or 8-bit chunks — then one burst would count as just one or two symbol errors. But that algebra needs division to work reliably (the decoders in Part 9 solve equations), and ordinary integers mod 256 won't do: $2\times128 \equiv 0$, so division breaks. We need a number system with $2^m$ elements where every nonzero element has an inverse: the finite field $\mathrm{GF}(2^m)$.

8.2 Building GF(8), completely

Elements: the eight 3-bit patterns, viewed as polynomials of degree < 3 (e.g. $6 = 110 = x^2+x$). Addition = XOR (add coefficients mod 2) — every element is its own negative. Multiplication: multiply the polynomials, then reduce modulo a chosen primitive polynomial — here $p(x) = x^3+x+1$ — using the rule $x^3 = x+1$ whenever degree spills to 3.

The magic of a primitive modulus: the powers of $\alpha = x$ (= the pattern 010 = 2) visit every nonzero element before repeating:

$\alpha^0$	$\alpha^1$	$\alpha^2$	$\alpha^3$	$\alpha^4$	$\alpha^5$	$\alpha^6$	$(\alpha^7)$
1	2	4	3	6	7	5	1 again

(Watch $\alpha^3$: $x\cdot x^2 = x^3 = x+1$ = 011 = 3. Then $\alpha^4 = x\cdot(x{+}1) = x^2{+}x$ = 6, and so on.)

Now multiplication is just exponent addition mod 7: $5\times7 = \alpha^6\cdot\alpha^5 = \alpha^{11} = \alpha^4 = 6$. Division subtracts exponents. Every nonzero element has an inverse ($\alpha^{-i} = \alpha^{7-i}$), so linear equations solve exactly as in school algebra — the safety net is up.

In code this is two lookup tables (alpha_to[], log[]) and a couple of adds — which is all a Reed–Solomon decoder's inner loop contains. The production fields work identically, just bigger: $\mathrm{GF}(64)$ with $x^6+x+1$ (JT65, Q65, P25's NID), $\mathrm{GF}(256)$ with $x^8+x^4+x^3+x^2+1$ (DAB, DVB-S, LRPT, ARDOP).

Part 9 — Reed-Solomon and BCH: algebra that finds the error

9.1 The idea: codewords with prescribed roots

Encode the message as a polynomial $c(x)$ over $\mathrm{GF}(2^m)$, constructed so that it evaluates to zero at $2t$ chosen points $\alpha, \alpha^2, \ldots, \alpha^{2t}$ (achieved by making $c(x)$ a multiple of $g(x) = (x{+}\alpha)(x{+}\alpha^2)\cdots(x{+}\alpha^{2t})$). The receiver evaluates what it got at those same points. Clean codeword → all zeros. Errors $e(x)$ → the evaluations

\[S_i = r(\alpha^i) = c(\alpha^i) + e(\alpha^i) = e(\alpha^i)\]

depend only on the errors (the syndrome trick of §7.2, now with teeth): $2t$ equations in the error positions and values. The decoder's job is to solve them. A code with $n-k = 2t$ parity symbols corrects any $t$ symbol errors — and since a symbol is $m$ bits, a single burst of $m$ bits costs just one correction. That's why RS owns the burst-error world.

9.2 A complete worked decode: RS(7,3) over GF(8)

$n=7$, $k=3$, $2t=4$ parity symbols, corrects $t=2$. Using the GF(8) of §8.2, roots $\alpha^1..\alpha^4$:

\[g(x) = (x{+}\alpha)(x{+}\alpha^2)(x{+}\alpha^3)(x{+}\alpha^4) = x^4 + 3x^3 + x^2 + 2x + 3.\]

Encode message symbols $(2, 3, 4)$ systematically: divide $m(x)\cdot x^4$ by $g(x)$ and append the remainder as parity. Result (coefficients of $x^6$ down to $x^0$):

\[c = (2,\ 3,\ 4,\ \underbrace{7,\ 5,\ 0,\ 6}_{\text{parity}})\]

(You can verify $c(\alpha^i)=0$ for $i=1..4$ with the log table — every term is two lookups.)

The channel strikes twice: add 5 to the $x^5$ coefficient (3→6) and 4 to the $x^1$ coefficient (0→4). Received: $r = (2, 6, 4, 7, 5, 4, 6)$. The receiver knows none of this — it sees only $r$. Watch it reconstruct everything:

Step 1 — Syndromes. Evaluate $r$ at the four roots:

\[S_1 = r(\alpha) = 5,\quad S_2 = r(\alpha^2) = 2,\quad S_3 = r(\alpha^3) = 6,\quad S_4 = r(\alpha^4) = 2.\]

Nonzero → errors exist.

Step 2 — Locate (the key equation). Suppose two errors at unknown locations $X_1=\alpha^{j_1}$, $X_2=\alpha^{j_2}$. Define the error-locator polynomial $\sigma(x) = (1{+}X_1x)(1{+}X_2x) = 1 + \sigma_1x + \sigma_2x^2$ — its roots are the inverses of the error locations. The syndromes obey a linear recurrence driven by $\sigma$:

\[S_3 + \sigma_1S_2 + \sigma_2S_1 = 0, \qquad S_4 + \sigma_1S_3 + \sigma_2S_2 = 0.\]

Two equations, two unknowns, field arithmetic — solve:

\[\det = S_2^2 + S_1S_3 = 2^2 + 5\cdot6 = 4 + 3 = 7,\qquad \sigma_1 = \frac{S_2S_3 + S_1S_4}{\det} = 5,\qquad \sigma_2 = \frac{S_3^2 + S_2S_4}{\det} = 5.\]

So $\sigma(x) = 1 + 5x + 5x^2$. (Sanity check against the truth the decoder doesn't know: $\sigma_1$ should be $X_1{+}X_2 = \alpha^5{+}\alpha^1 = 7{+}2 = 5$ ✓ and $\sigma_2 = X_1X_2 = \alpha^6 = 5$ ✓.)

Step 3 — Chien search. Find $\sigma$'s roots by brute force — evaluate at every nonzero field element (in hardware, a cheap systolic sweep): $\sigma(\alpha^2) = 0$ and $\sigma(\alpha^6) = 0$. Roots are inverse locations, so the errors sit at $\alpha^{-2} = \alpha^5$ and $\alpha^{-6} = \alpha^1$: positions $x^5$ and $x^1$. Correct.

Step 4 — Forney (the values). Form the evaluator $\Omega(x) = S(x)\,\sigma(x) \bmod x^4$ where $S(x) = S_1 + S_2x + S_3x^2 + S_4x^3$; here everything above degree 1 cancels: $\Omega(x) = 5 + 5x$. The error value at location $X$ is

\[e = \frac{\Omega(X^{-1})}{\sigma'(X^{-1})},\]

and in characteristic 2 the formal derivative $\sigma'(x) = \sigma_1 = 5$ (the $2\sigma_2x$ term vanishes — even coefficients are zero mod 2). So:

at $X_1 = \alpha^5$: $\Omega(\alpha^2) = 5 + 5\cdot4 = 5 + 2 = 7$, $e_1 = 7/5 = \alpha^{5-6} = \alpha^6 = \mathbf{5}$ ✓
at $X_2 = \alpha^1$: $\Omega(\alpha^6) = 5 + 5\cdot5 = 5 + 7 = 2$, $e_2 = 2/5 = \alpha^{1-6} = \alpha^2 = \mathbf{4}$ ✓

XOR the values back at the located positions: $(2,6{\oplus}5,4,7,5,4{\oplus}4,6) = (2,3,4,7,5,0,6)$ — the codeword, exactly. Two errors, in unknown places, with unknown values, undone by four evaluations and a 2×2 solve.

9.3 Scaling up: Berlekamp–Massey and friends

For $t=2$ we solved the key equation by hand; for JT65's $t=25$ that's a 25×25 system, and the Berlekamp–Massey algorithm solves it incrementally instead — it synthesises the shortest recurrence (equivalently: the shortest LFSR, §12.2) that explains the syndrome sequence, in $O(t^2)$. The pipeline syndromes → BM → Chien → Forney is the universal algebraic decoder; write it once and it serves every BCH and RS code in the catalogue. (ARDOP adds a wise epilogue: re-check the syndromes after correcting, and refuse any "success" that needed more than $t$ — a guard against confidently mis-corrected garbage.)

BCH codes are the binary siblings: same construction and same decoder over $\mathrm{GF}(2^m)$, but the codeword bits are just bits — so they correct $t$ bit errors with fine-grained overhead. The catalogue's spread:

Code	$t$	Guards	Mode
BCH(31,21), gen `0x769`	2	every 32-bit word	POCSAG
BCH(63,16)	11	the network ID	P25
RS(63,12) over GF(64)	25	the whole message	JT65
RS(204,188)	8	each MPEG packet	DVB-S
RS(255,223), dual basis	16	each space frame	LRPT/CCSDS

Look at JT65's row the way its designer did: 63 symbols, 12 carry message — the other 51 exist to let 25 of 63 symbols (40%!) be wrong. On an EME path where most of every transmission is destroyed, that's not overhead; that's the mode.

Part 10 — Convolutional codes and Viterbi: the best path through a trellis

10.1 The encoder: three flip-flops and two XORs

Instead of coding blocks, stream the bits through a $K$-stage shift register and transmit XOR taps of its contents. Our worked code is the classic $K=3$ pair $G_0 = 111$, $G_1 = 101$ ("(7,5)" in octal): for each input bit $x$ with the two previous bits $a,b$ in the register,

\[\text{out} = (\;x\oplus a\oplus b,\quad x\oplus b\;)\]

— rate 1/2, and every input bit influences 3 consecutive output pairs. That smearing-out is the code's strength: to corrupt a bit's evidence you must hit several places at once.

The encoder is a 4-state machine (states = last two bits $ab$). Worked encode of message 1 0 1 1 plus two flush zeros (to return the register to state 00):

in	state before	out
1	00	11
0	10	10
1	01	00
1	10	01
0	11	01
0	01	11

Transmitted: 11 10 00 01 01 11.

10.2 Viterbi: decoding as shortest path

The idea. Unroll the state machine in time — the trellis: 4 states per column, one column per symbol, edges = the transitions the encoder could have made, each edge labelled with the 2 bits the encoder would have emitted. Any transmitted sequence is a path; decoding = find the path whose labels differ from what we received in the fewest places. Checking every candidate path costs exponentially more with every added symbol; Viterbi's dynamic-programming insight makes it linear: paths that meet at the same state have identical futures, so at every merge you may keep only the cheaper arrival — the survivor — and discard the rest, forever. Cost: $2^{K-1}$ states × 2 edges per symbol, regardless of message length.

Worked decode. Corrupt two of the twelve bits: received 11 10 ⟨1⟩0 0⟨0⟩ 01 11 (errors at the marked positions — pair 3 should be 00, pair 4 should be 01). Run the trellis, tracking each state's cheapest path metric (accumulated Hamming distance):

after pair	rx	S00	S01	S10	S11
1	11	2	–	0	–
2	10	3	0	3	2
3	10	1	3	1	2
4	00	1	2	3	2
5	01	2	2	2	3
6	11	2

The flush bits force the ending state to 00; trace the survivor back from S00 (metric 2 — exactly the number of channel errors, both absorbed en route) and the path reads input bits 1 0 1 1 0 0 — the message, both errors corrected, having examined just 48 edges. On a longer message the saving becomes astronomical: that's the entire trick.

10.3 Soft decisions: the free 2 dB

Hamming distance treats every received bit as equally trustworthy — but the demodulator knows more: a sample near the decision threshold is a shrug, one far from it is an oath. Replace "count disagreements" with "sum log-likelihoods" (add $\log P(r|{\rm edge\ bit})$ per edge) and Viterbi runs unchanged on the new metric — now maximum-likelihood against the analog channel. The gain is ~2 dB, the cheapest 2 dB in radio, and the reason every spec in the catalogue insists the demapper deliver LLRs, not bits (the same principle powers LDPC, §11). The relation $\mathrm{LLR} = \log\frac{P(b{=}0|r)}{P(b{=}1|r)}$ — sign = the bit, magnitude = the confidence — is defined once in §11.2 and used by every soft decoder alike.

10.4 Variations in the catalogue

The generator constants travel. The $K=7$ pair octal 171/133 decodes DVB-S, LRPT/CCSDS, DAB, and (relabelled 0x6D/0x4F) Thor and RVQ-Voice; M17 and TETRA run $K=5$. One Viterbi core, many modes.
Puncturing: delete output bits by a fixed pattern to raise the rate; the decoder re-inserts them as "no information" erasures (LLR 0) and the same trellis decodes the whole rate family — DVB-S's 1/2 through 7/8, TETRA's RCPC, M17.
$K=32$ (WSPR, JT4; generators 0xF2D05351/0xE4613C47): $2^{31}$ states make Viterbi impossible. The stack (sequential) decoder explores the code tree best-first, ranking partial paths by the Fano metric — log-likelihood minus a per-bit bias so that longer paths compare fairly against shorter ones — always extending the current best. Decode effort becomes a random variable (fast at good SNR, explosive at bad), acceptable only because the messages are ~50–72 bits. The reward: the asymptotic gain of a constraint length no Viterbi code approaches.
Errors exit in bursts. When Viterbi does fail, it emits a run of wrong bits (a wrong survivor takes several symbols to remerge). That output statistics profile is exactly what Reed–Solomon eats for breakfast — hence the classic concatenation inner-Viterbi + outer-RS (DVB-S, LRPT), with an interleaver between (§12.1) to finish the job.

Part 11 — LDPC and belief propagation: decoding by gossip

11.1 The code is a graph

A low-density parity-check code is nothing exotic: a linear code (§7.2) whose parity-check matrix $H$ is deliberately sparse. Draw it as a Tanner graph — bit nodes on one side, check nodes on the other, an edge wherever $H$ has a 1. Our toy (6,3) code:

   c0 ●───● b0                    ⎡ 1 1 0 1 0 0 ⎤   c0 = b0 ⊕ b1 ⊕ b3
      ├───● b1                H = ⎢ 0 1 1 0 1 0 ⎥   c1 = b1 ⊕ b2 ⊕ b4
      └───● b3                    ⎣ 1 0 1 0 0 1 ⎦   c2 = b0 ⊕ b2 ⊕ b5
   c1 ●───● b1
      ├───● b2      each check node wires to the bits in its row of H;
      └───● b4      b0, b1, b2 each sit on two checks, b3, b4, b5 on one
   c2 ●───● b0
      ├───● b2
      └───● b5

A valid codeword satisfies all checks. Decoding is a constraint-satisfaction negotiation: each bit has an opinion (from the channel), each check knows a rule its bits must obey, and they trade messages until the story is consistent.

11.2 The message algebra

Beliefs travel as LLRs: $L = \log\frac{P(b=0)}{P(b=1)}$ — sign is the leaning (positive = "0"), magnitude is the confidence, and crucially, independent evidence adds. Two rules move messages along edges:

Bit node: total belief = channel LLR + sum of incoming check messages. (When replying to a particular check, exclude that check's own message — never sell someone their own gossip back.)
Check node to bit $i$: "your value must make my parity even, so my evidence about you is what the others jointly imply." The exact combination rule for a parity constraint is the "boxplus": $L_{\text{out}} = 2\,\mathrm{atanh}\!\prod_{j\ne i} \tanh(L_j/2)$. Its cheap, remarkably good approximation is min-sum:

\[\text{sign} = \prod_{j\ne i}\mathrm{sign}(L_j), \qquad \text{magnitude} = \min_{j\ne i}|L_j|\]

— the parity of the others' leanings, believed only as strongly as the shakiest witness. (A chain of evidence is as strong as its weakest link — the maths agrees.)

11.3 Worked example: one iteration rescues a bit

Send codeword $(1,1,0,0,1,1)$ (check it against the three rules above — each has two 1s). The channel delivers five bits confidently and one weakly wrong: bit 2 is truly 0 (should be positive) but arrives as $-0.5$:

\[L^{\text{ch}} = (-4,\ -4,\ \mathbf{-0.5},\ +4,\ -4,\ -4)\]

Check-to-bit messages (min-sum): each check tells each of its bits the XOR-consistent opinion of its other two. For bit 2, listen to its two checks:

$c_1$ knows $b_1 (-4)$ and $b_4 (-4)$: both are "1", so $b_2$ must be "0" to keep the parity even → message $(-)\cdot(-)\cdot\min(4,4) = \mathbf{+4}$.
$c_2$ knows $b_0 (-4)$ and $b_5 (-4)$: likewise → $\mathbf{+4}$.

Bit 2's posterior: $-0.5 + 4 + 4 = \mathbf{+7.5}$ — the weak wrong channel reading is outvoted by two independent parity arguments, and the hard decision flips to the correct 0. The full posterior vector after this single iteration is $(-7.5, -7.5, +7.5, +8.0, -3.5, -3.5)$: all six signs correct, syndrome zero, decode complete. (Note the honest detail: bits 4 and 5 lost a little confidence — their checks also heard the wobbly $-0.5$ and passed on doubt, $+0.5$ each. Gossip carries uncertainty in both directions; iteration lets the network settle it.)

Real decodes repeat this exchange until every parity is satisfied or an iteration cap hits — FT8 budgets ~25 iterations, FST4W 40.

11.4 Why sparse, and why it wins

Belief propagation is exactly correct on a tree (each message really is independent evidence). Real codes have cycles, so BP is an approximation — but sparsity makes cycles long, so gossip completes many hops before your own rumour returns disguised as news, and the approximation stays honest. That's the "low-density" in the name, and the design craft lives in the graph: FT8's (174,91) gives every bit node exactly 3 checks (522 edges; check nodes average ~6.3), enough connectivity to propagate, sparse enough to trust. With well-designed graphs, LDPC operates within a fraction of a dB of the Shannon bound of §5.2 — which is why everything designed since ~2010 uses it: FT8/FT4, JS8 (174,87), FST4 (240,101), DVB-S2 (with a staircase structure making encoding linear-time), Mercury (N=1600, rates 1/16–14/16), FreeDV 700D/E.

Two practical notes that recur in every spec: the graph ships as two adjacency tables (Mn: which checks touch each bit; Nm: which bits touch each check) — the largest constants in the repo — and the decoder must be fed soft LLRs; hard-slicing first throws away the ~2 dB that Parts 10.3 and 2.5 fought for.

11.5 Non-binary: Q65's QRA code

Q65 plays the same game with messages that are probability vectors over GF(64) rather than scalar LLRs: its (65,15) repeat-accumulate code's symbols are the 64-ary tones the demodulator measures, so FFT bin energies feed the decoder directly — no lossy symbol→bit marginalisation. Check nodes must convolve 64-long distributions; the fast Walsh–Hadamard transform (next section) does it in $64\log 64$ operations. Costly per edge, but modulation and code speaking one alphabet is worth several dB at the EME extreme.

11.6 Walsh–Hadamard codes: orthogonality as FEC

The Hadamard matrix doubles recursively, each row orthogonal to every other:

\[H_1 = [1],\qquad H_{2n} = \begin{bmatrix} H_n & H_n \\ H_n & -H_n \end{bmatrix}\]

Encode 3 bits as one of $H_8$'s rows; decode by correlating against all rows — one fast Walsh–Hadamard transform — and take the argmax. Because the rows are orthogonal (dot-product 0), noise must be enormous to make the wrong row win: this is a low-rate, high-distance block code with a built-in soft decoder.

Worked example. Send row 5 of $H_8$ = + − + − − + − +; add Gaussian noise of σ = 1.2 per chip (comparable to the signal!). One received realisation correlates against the 8 rows as $(0.6,\ 7.0,\ 2.1,\ 5.6,\ 4.7,\ \mathbf{8.8},\ 0.6,\ 1.0)$ — row 5 wins cleanly. Olivia sends each character as a [64,7] Walsh codeword smeared across its MFSK tones; MT63 spreads every character across all 64 OFDM carriers the same way; DVB-S2 protects its frame descriptor (the bits that tell you how to decode everything else) with Reed–Muller — a Walsh cousin — for the same reason: when a field must survive anything, orthogonality is the bluntest, surest instrument.

Part 12 — Conditioning: permutations and pseudo-randomness

12.1 Interleaving: spending latency to buy independence

Every decoder in Parts 9–11 was priced against scattered errors, but real channels deliver bursts. An interleaver is a pure permutation — zero redundancy added — that makes the channel look scattered to the code.

The arithmetic. Write a block interleaver as a $d \times w$ matrix: fill it by rows, transmit it by columns. Symbols that were adjacent in the written order are now $d$ transmission slots apart — so a channel burst of length $b$ comes back from the de-interleaver diced into isolated fragments of at most $\lceil b/d \rceil$ consecutive symbols. Worked example: a depth-7 interleaver feeding codewords of the DVB-S kind (one RS(204,188) codeword per row, $t=8$): a 21-symbol burst — fatal to any single codeword — de-interleaves to 3 errors in each of 7 codewords, trivially corrected. JT65 runs the same permutation as a 7×9 matrix over its one RS codeword, spreading a fade's damage evenly across the block instead of letting it gouge one region. The price is fundamental: you cannot decode until the matrix fills — interleaving is latency, which is why real-time voice (M17, P25) interleaves within-frame only, while one-way broadcast goes deep (DAB's 384 ms time interleave).

Variants, same maths: LoRa interleaves diagonally across (chirp, bit-position) so time and frequency diversity couple; DVB-S's Forney interleaver gets block-like spread from staggered delay lines at a fraction of the latency; NAVTEX and marine DSC send every character twice with a fixed offset — a 2-way time-diversity "interleaver" that is the entire FEC of those modes.

12.2 LFSRs and m-sequences: deterministic noise

The machine. A linear-feedback shift register: $n$ bits of state; each step outputs one bit and feeds back the XOR of fixed taps. If the taps form a primitive polynomial (§8.2's star property, reappearing), the state walks through all $2^n - 1$ nonzero states before repeating: an m-sequence.

Worked example. Taps $x^3 + x^2 + 1$, seed 111:

\[\mathtt{1110010\ |\ 1110010\ |\ \ldots}\]

period $2^3-1 = 7$, containing four 1s and three 0s (near-balance), runs distributed like coin flips, and — the property everything hangs on — a two-valued autocorrelation: 7 at zero shift, exactly −1 at every other shift. It looks like noise to any correlator, yet costs three flip-flops.

Why every mode carries one. XOR the data with an m-sequence (whitening/scrambling) and long runs of identical bits vanish — timing recovery gets transitions to chew on, the spectrum loses its DC spike, and the receiver undoes it by XORing with the same sequence (self-inverse). DVB-S uses $x^{15}{+}x^{14}{+}1$, DAB $x^9{+}x^5{+}1$, CCSDS/LRPT $x^8{+}x^7{+}x^5{+}x^3{+}1$, LoRa an 8-bit variant. TETRA seeds its scrambler with the network colour code — descramble cleanly and you've simultaneously verified you're on the right network. And none of this is secrecy: the sequence is public and keyless. Meshtastic's AES-CTR looks identical in structure (XOR with a generated stream) but its stream comes from a keyed cipher — same shape, opposite purpose. The question that distinguishes them: where does the stream come from, and is that secret?

(One more place the LFSR earns a living: Berlekamp–Massey (§9.3) is literally "find the shortest LFSR that generates this sequence" — the same object decodes Reed–Solomon.)

Part 13 — Source coding: spending fewer bits in the first place

Every bit not spent on the payload is a bit of energy the FEC can spend on reliability (§5.1 set the floor; this Part approaches it).

13.1 Variable-length codes and the prefix property

Give frequent symbols short codewords — but then how do you know where one ends? A code is instantly decodable if no codeword is a prefix of another; the Kraft inequality $\sum 2^{-\ell_i} \le 1$ tells you exactly which length menus are achievable, and entropy (§5.1) bounds the average.

PSK31's varicode solves the framing problem with a twist: no codeword contains 00, so 00 itself is the inter-character gap — self-delimiting from any starting point, mid-stream. The actual table walks the frequency order: space = 1, e = 11, t = 101, o = 111, a = 1011 … A = 1111101, NUL = 1010101011. Common text averages well under half the cost of fixed 8-bit characters — and a corrupted bit resynchronises at the next 00 instead of shearing the whole stream.

13.2 Huffman coding, worked

Huffman's algorithm builds the optimal prefix code: repeatedly merge the two least probable items into one node. Toy alphabet — E (0.4), T (0.2), A (0.2), O (0.1), space (0.1):

merge the two lightest, repeat:            read the codes off the tree:

  O(.1) + _(.1)     → (O_)(.2)                E   11        T   00
  T(.2) + A(.2)     → (TA)(.4)                A   01        O   100
  (O_)(.2) + E(.4)  → (O_E)(.6)               _   101
  (TA)(.4) + (O_E)(.6) → root(1.0)

Average length $= 0.4{\cdot}2 + 0.2{\cdot}2 + 0.2{\cdot}2 + 0.1{\cdot}3 + 0.1{\cdot}3 = 2.20$ bits vs. entropy $H = 2.12$ bits — within 4% of the theoretical floor, from a half-page algorithm. JS8 runs exactly this idea at scale (a Huffman character table plus a 262k-word dictionary), so a common word costs a couple of symbols.

13.3 Packing: a message as one big number

When the message space is small and enumerable, skip codewords entirely: number every possible message and send the number. This is mixed-radix arithmetic. A standard amateur callsign is (letter/digit)(letter/digit)(digit)(letter)(letter)(letter) with blanks allowed in three positions — count them:

\[37 \times 36 \times 10 \times 27 \times 27 \times 27 = 262{,}177{,}560 < 2^{28} = 268{,}435{,}456.\]

So 28 bits carry any callsign — versus 48 bits as ASCII. The WSJT-X 77-bit payload is this trick applied ruthlessly to the whole QSO grammar (two callsigns, a grid/report, message type); M17 packs callsigns base-40 into 48 bits; AIS bit-packs its position reports into 168 bits. The tradeoff is brittleness — flip one bit of a packed integer and you get a different valid message, no redundancy inside to object — which is why packed payloads always travel under heavy FEC and a CRC.

13.4 Voice: model the throat, not the waveform

PCM speech is ~64 kbit/s at 8 bits/sample; the digital-voice modes ship 1.6–4.4 kbit/s. No waveform coder gets there — instead they transmit the parameters of a model of speech production: the vocal tract is a slowly-changing filter excited by either a pitch buzz (voiced) or noise (unvoiced).

The maths (linear prediction). Model each sample as a weighted sum of the previous $p$: $\hat x_n = \sum_{k=1}^{p} a_k x_{n-k}$. Choosing $a_k$ to minimise the mean squared error $E[(x_n-\hat x_n)^2]$ — expand, differentiate, set to zero — yields the normal equations: they involve the signal only through its autocorrelation $r_k$:

\[\sum_k a_k\, r_{|i-k|} = r_i,\qquad i = 1..p.\]

The Toeplitz structure lets Levinson–Durbin solve them in $O(p^2)$, building the order-$p$ predictor from the order-$(p{-}1)$ one. Worked example, order 2 with $r = (1.0,\ 0.5,\ 0.2)$: first-order reflection coefficient $k_1 = r_1/r_0 = 0.5$, residual energy $E_1 = 1-k_1^2 = 0.75$; then $k_2 = (r_2 - k_1 r_1)/E_1 = -0.067$, giving $a = (0.533,\ -0.067)$ and $E_2 = 0.747$. The predictor "explains" 25% of the signal's energy; only the residual and the coefficients need transmitting. Real coders use $p \approx 10$, convert the $a_k$ to line spectral frequencies (an equivalent form that stays stable under quantisation error and interpolates smoothly between frames), and quantise those.

That front end is universal; the codecs differ in how they encode the excitation: Codec2 (M17, FreeDV) sends pitch, voicing, and spectral magnitudes in 700–3200 bit/s; IMBE/MBE (P25, the native vocoder) splits the spectrum into bands with per-band voiced/unvoiced decisions; RVQ-Voice keeps the classical front end and quantises the spectral envelope with a residual vector quantiser — a cascade of small codebooks, each encoding the error of the previous stage, neural-codec style. Different back ends, same Levinson–Durbin heart.

Part 14 — The whole link, by the numbers

Time to audit a real mode against everything above. FT8, end to end:

The bit pipeline. 77 payload bits (§13.3 packing) + 14 CRC bits (§6) = 91 → LDPC(174,91) (§11) doubles them to 174 coded bits → split into 58 three-bit Gray-coded (§2.5) groups → 8-GFSK tones (§3.2) at 6.25 Hz spacing. Add 21 Costas sync symbols (§4.2): 79 symbols × 0.16 s = 12.64 s per transmission, in a 50 Hz footprint.

The information rate: $R_b = 77 / 12.64 = 6.09$ bit/s.

The energy audit at the decode threshold. Take a signal at FT8's advertised limit, −21 dB SNR in the 2500 Hz reference bandwidth (§1.2). Its power-to-noise-density ratio:

\[P/N_0 = 10^{-2.1}\times 2500 = 19.9\ \text{Hz (i.e. } 13\ \text{dB-Hz)}\]

\[\frac{E_b}{N_0} = \frac{P/N_0}{R_b} = \frac{19.9}{6.09} = 3.3 = \mathbf{5.1\ dB}\]

The verdict of Part 5: the absolute floor is −1.59 dB (§5.2); FT8 decodes ~6.7 dB above it. Where does the gap go? Roughly: ~1 dB to non-coherent FSK detection (§3.1), ~27% of the airtime to sync symbols (§4.2) ≈ 1.4 dB, a fraction of a dB to the LDPC's distance from capacity (§11.4) plus the CRC's 14 bits, and the remainder to using 8-ary tones rather than an unconstrained input alphabet. Nothing is mysterious; every dB is a design decision you have now met, and you can run the same audit on any row of the periodic table.

And the capacity cross-check: at $P/N_0 = 19.9$ Hz in a 50 Hz band, Shannon allows $C = 50\log_2(1 + 19.9/50) = 24$ bit/s. FT8 uses 6.09 — one quarter of the theoretical maximum, spent deliberately on sync robustness, decode simplicity, and margin. Engineering is the art of choosing which dB to give away.

Where to go next

Downward for rigor: every constant and table in this document is pinned, verified, and reproduced in the per-protocol specs — the RS(63,12) decoder in jt65.md, the full FT8 LDPC tables in ft8-ft4.md, the WSPR $K=32$ stack decoder in wspr.md.
Sideways for systems judgment: Protocol Commonalities — which technique to pick when, what each costs, and the periodic table of who uses what.
Backward for intuition: the Beginner's Tour, if any section here moved too fast.

Every worked example above (the CRC division, Hamming syndrome, GF(8) tables, the full RS(7,3) decode, the Viterbi trellis, the LDPC iteration, the Walsh decode, the Costas array property, the LFSR sequence, the Huffman tree, Levinson–Durbin, and the FT8 link budget) has been verified by machine computation against the arithmetic shown.

check	covers	parity of received
\(s_1\)	1,3,5,7	\(0\oplus1\oplus1\oplus1\)	= 1
\(s_2\)	2,3,6,7	\(1\oplus1\oplus1\oplus1\)	= 0
\(s_4\)	4,5,6,7	\(0\oplus1\oplus1\oplus1\)	= 1