Channel Coding: Hamming Distance, Code Rate, ARQ vs FEC

A channel flips bits. Channel coding is the deliberate insertion of redundancy so that the flipped version of a legal message is still recognisable — or repairable — as that message. The whole subject reduces to one geometric fact and one economic one: legal codewords must be far apart in Hamming distance for errors to be survivable, and every bit of distance you buy is paid for in code rate. Everything after that — block versus convolutional, systematic versus not, retransmit versus repair — is engineering around those two quantities under a hard ceiling that Shannon proved in 1948 and called channel capacity.

The distance geometry #

Take all $2^n$ binary strings of length $n$ as points in a hypercube. A code $\mathcal{C}$ is a chosen subset of them; only those are legal. The Hamming distance $d(x,y)$ is the number of positions in which two strings differ, and the code's minimum distance is

$$d_{\min} = \min_{x \neq y \in \mathcal{C}} d(x,y)$$

A channel that flips $t$ bits moves a codeword $t$ steps through the cube. Two consequences follow directly:

$$\text{detect any } \le d_{\min}-1 \text{ errors}, \qquad \text{correct any } \le \left\lfloor \frac{d_{\min}-1}{2} \right\rfloor \text{ errors}$$

Detection needs only that the corrupted point is not another codeword — so anything short of a full $d_{\min}$-step walk is caught. Correction needs the corrupted point to remain strictly closer to the true codeword than to any other, which halves the budget. You cannot do both at full strength simultaneously: a decoder configured to correct $t$ errors detects only $d_{\min} - t - 1$ beyond that.

Erasures — positions known to be unreliable rather than silently wrong — are cheaper, because the decoder already knows where to look:

$$2t + e \le d_{\min} - 1$$

Distance is a property of the code and its length #

The most useful concrete illustration is the Ethernet frame check sequence, because it is the code most engineers assume they understand. IEEE 802.3 uses the degree-32 polynomial

$$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$$

A CRC is a shortened cyclic code, and its minimum distance degrades as the message grows. Koopman computed it exactly for every data-word length up to 131 072 bits:

At an Ethernet MTU — a 12 112-bit data word — the code sits in the HD = 4 band. Koopman's weight computation at that length is $W_2 = 0$, $W_3 = 0$, $W_4 = 223\,059$: all two- and three-bit errors are caught, and there are exactly 223 059 distinct four-bit patterns that slip through undetected.

Code rate, and what it costs #

$$R = \frac{k}{n}, \qquad 0 < R \le 1$$

$k$ information symbols in, $n$ channel symbols out. Rate is the price tag, and it is charged in one of two currencies depending on what is scarce:

• Bandwidth-limited link — holding the information rate $R_b$ fixed, the channel symbol rate rises by $1/R$. A rate-1/2 code doubles the occupied spectrum.
• Power-limited link — holding the bandwidth fixed, the information rate drops by $R$, and the energy available per channel symbol falls: $E_s/N_0 = R \cdot E_b/N_0$. The code must win back more than it spent.

The net win is coding gain: the reduction in required $E_b/N_0$ for a target error rate, already net of the rate penalty. This is why a code is never evaluated at fixed $E_s/N_0$ — that comparison flatters low-rate codes for free.

Real deployed rates cluster far higher than textbook examples suggest, because bandwidth and spectral efficiency are usually the binding constraints:

Note the shape of that list: the rate falls only where power, not bandwidth, is the scarce resource. A spacecraft at the edge of the solar system will happily spend six channel bits per information bit; a 10 Gb/s copper link will not spend more than 19%.

The ceiling: Shannon #

Everything above is a construction. Shannon's 1948 result says what constructions can possibly achieve, and it is startlingly strong. His Theorem 11: given a channel of capacity $C$ and a source of entropy $H$ per second, if $H \le C$ there exists a coding system transmitting with arbitrarily small frequency of errors; if $H > C$ the equivocation cannot be pushed below $H - C$.

That is a phase transition, not a gradient. Below capacity, error probability can be driven to zero without lowering the rate; above it, no code helps. For the band-limited AWGN channel his Theorem 17 gives the number:

$$C = W \log_2\!\left(1 + \frac{P}{N}\right) \quad \text{bits/s}$$

Setting spectral efficiency $\eta = R_b/W$ and substituting $P/N = \eta \, E_b/N_0$ gives $\eta = \log_2(1 + \eta \, E_b/N_0)$, so

$$\frac{E_b}{N_0} \ge \frac{2^{\eta}-1}{\eta}, \qquad \lim_{\eta \to 0} \frac{2^{\eta}-1}{\eta} = \ln 2 \approx -1.59\ \text{dB}$$

the absolute floor for reliable communication at any rate. Modern codes get genuinely close: DVB-S2 states quasi-error-free operation (packet error ratio below $10^{-7}$) at about 0.7 dB to 1 dB from the Shannon limit, and the DSN specifies its CCSDS turbo codes as performing within approximately 0.8 dB of the theoretical limit at BER $10^{-6}$.

Systematic or not #

A code is systematic when the $k$ information symbols appear unchanged in the codeword and the $n-k$ parity symbols are appended. RS(255, 223) as flown is systematic; so are the CCSDS turbo and LDPC codes; so is every CRC-protected frame.

The reasons are operational, not mathematical:

• Forensics. The DSN handbook calls out the systematic property as useful precisely because corrupted data can still be read out when decoding fails outright.
• Zero-cost fast path. A receiver on a clean channel can pass the payload straight through and use the parity only to verify.
• Rate-compatible puncturing. Parity symbols can be dropped and later re-sent (see hybrid ARQ below) without disturbing the information positions.

Non-systematic codes still appear where the encoder's structure demands it: a classical non-recursive convolutional encoder emits only parity streams, and interleaved turbo codes emit the information bits but not contiguously, so the raw output is not directly readable.

Block codes and convolutional codes #

IEEE 802.11 is the canonical convolutional deployment: a $K = 7$, rate-1/2 mother code with octal generators 133/171, punctured to 2/3, 3/4 and 5/6. Binary convolutional coding remains mandatory in every 802.11 device — it protects the preamble of every compliant frame — while LDPC is optional, even though LDPC now carries the high-throughput data. Deep space uses the same $K = 7$, rate-1/2 code (connection vectors 1111001 and 1011011) as its CCSDS inner code.

That last row of the table is the load-bearing one. Viterbi decoding fails in bursts, because a decoder that takes a wrong branch stays wrong for several constraint lengths. A block code that tolerates $t$ symbol errors anywhere is the natural partner. Hence concatenation: RS(255, 223) outside, convolutional inside. The DSN handbook states the design intent plainly — the combination "provides good burst-error correction with minimal bandwidth expansion".

flowchart LR
  S["Source bits"] --> O["Outer code<br/>RS(255,223)"]
  O --> I["Interleaver<br/>depth I"]
  I --> C["Inner code<br/>conv. K=7, r=1/2"]
  C --> M["Modulator"]
  M --> CH(("Noisy<br/>channel"))
  CH --> D["Viterbi decoder<br/>(bursty output)"]
  D --> DI["De-interleaver"]
  DI --> RS["RS decoder"]
  RS --> OUT["Sink"]

RS(255, 223) is worth working through as the arithmetic check on everything above. It is a maximum-distance-separable code over $GF(2^8)$: with $n-k = 32$ parity symbols it attains $d_{\min} = n-k+1 = 33$, hence

$$t = \left\lfloor \frac{33-1}{2} \right\rfloor = 16 \text{ symbol errors per codeword}$$

Sixteen wrong bytes out of 255, wherever they fall — and because the unit is a byte, a burst that destroys 16 consecutive bytes costs the same as 16 scattered ones.

Interleaving: manufacturing independence #

Codes are designed against independent errors. Real channels produce clumps — a scratch, a fade, a Viterbi excursion. Interleaving reorders symbols before transmission so that a contiguous physical burst lands as isolated symbol errors spread across many codewords. It buys nothing on a memoryless channel; on a bursty one it is the difference between working and not.

The cost is latency and buffering, and it is unavoidable: the de-interleaver cannot emit a codeword until every one of its symbols has arrived, so the delay is the interleaver span.

Deep space. The CCSDS/DSN scheme runs $I$ RS encoders in parallel over an interleaving depth $I \in [1,8]$; at $I = 5$ a codeblock carries $5 \times 223 = 1115$ information symbols followed by $5 \times 32 = 160$ parity symbols, and the information symbols stay in original order — the interleaved code remains systematic. Maximum payload per codeblock runs from 1784 bits at $I = 1$ to 14 272 bits at $I = 8$.

Compact disc. CIRC is the more aggressive design, and ECMA-130 specifies it exactly: an outer encoder C2 producing an RS(28, 24) code, then an inner encoder C1 producing RS(32, 28) — C1 sits closest to the channel — both over $GF(2^8)$ generated by $P(x) = x^8+x^4+x^3+x^2+1$, with three delay sections between and around them. The middle section is a 28-way delay line of $0, 4, 8, \ldots, 108$ frame times. Consequently the longest delay any byte experiences between encoder input and output is 108 frame times and the shortest is 3 — so the 24 bytes that entered as one frame leave smeared across a hundred-odd frames of track.

ARQ: retransmit instead of repair #

The alternative to repairing errors is detecting them and asking again. All ARQ needs is an error-detecting code (a CRC) and a feedback channel. Three schemes, and the difference between them is entirely about how much the sender must redo:

These are not textbook abstractions. ITU-T X.25's LAPB carries both as supervisory frames: REJ "request[s] transmission of I frames starting with the frame numbered N(R)" — go-back-N — while SREJ requests "retransmission of one or more (not necessarily contiguous) I frames", with the information field listing individual sequence numbers and span lists. The standard forbids mixing them on one link.

ARQ's costs are not only throughput. RFC 3366 warns that retransmission delay is not free at higher layers: "Effects such as increased transit delay, jitter, and re-ordering are cumulative when performed on multiple links", and it discourages perfect persistence (retry until success) precisely because it "does not provide a clear upper bound on the maximum retransmission delay" — an unbounded link-layer retry turns a lossy link into a variable-latency one, which is worse for real-time traffic and confuses TCP's own congestion control.

ARQ vs FEC: how the choice is actually made #

The decision procedure is short:

1. Is there a feedback path, and does a round trip fit the deadline? If not, FEC, and the discussion is over. A rover on Mars sits between about 6 and 44 minutes of round-trip light time (0.37–2.67 AU at 499 s/AU); a scratch on a disc has no return channel at all. Both are pure-FEC problems.
2. Is the error rate low and bursty, or high and steady? Rare errors make FEC's permanent tax look expensive and ARQ's occasional retry look cheap — which is why Ethernet ships a CRC and no FEC on short copper, and drops the frame. A persistently noisy channel inverts this: retransmissions also get corrupted, and throughput falls off a cliff.
3. Is the residual error rate requirement tighter than FEC alone can guarantee? Then you need detection on top of correction regardless — the DSN's 16-bit CRC over turbo-decoded frames is exactly this.
4. Is jitter acceptable? FEC's latency is constant; ARQ's is a random variable. For interactive audio and video, that alone often settles it.

Hybrid ARQ #

Modern wireless refuses to choose. Hybrid ARQ transmits FEC-coded blocks with a CRC; the receiver decodes, checks, and requests a retransmission only on failure — and crucially, keeps the failed block.

• Type I discards the failed block and re-sends the same coded block. Simple, and it throws away information the receiver already paid to receive.
• Type II (incremental redundancy) sends different parity on the retransmission. The receiver combines soft values across attempts, so the effective code rate falls with each try. The link adapts its rate to the channel automatically, without ever measuring it.

5G NR implements this concretely. Data channels use quasi-cyclic LDPC with two base graphs — BG1 for $K \le 8448$ at rates $1/3 \le R \le 8/9$, BG2 for $K \le 3840$ at $1/5 \le R \le 2/3$ — and rate-matching reads out of a circular buffer at one of four redundancy versions (RV 0–3), each starting at a different offset. Retransmissions send a different RV. Soft combining is normative, not an implementation choice: TS 38.321 instructs the physical layer to combine the newly received data with what is already in the soft buffer for that transport block and re-attempt decoding. Control channels use polar codes rather than LDPC, because short-block performance is what matters there; CRC lengths are chosen per channel — CRC24A for transport blocks above 3824 bits, CRC16 below, CRC6 and CRC11 for uplink control.

Because a stop-and-wait HARQ process must idle while awaiting its ACK, standards run many processes in parallel — LTE permits a maximum of 8 downlink HARQ processes per serving cell in the baseline configuration, and NR raises that to 16 per cell in both directions. The parallelism is what recovers the throughput that stop-and-wait would otherwise destroy.

Where each shows up #

Read that table vertically and the pattern is clean. Broadcast and storage get pure FEC, because they have no return path. Short, clean, low-latency links get pure detection, because the cheapest repair is to drop the frame and let a higher layer notice. Long-lived bidirectional radio links get hybrid ARQ, because the channel varies by orders of magnitude and nothing static is right for all of it.

Reading list within the bank #

The algebra behind the concrete codes lives in block codes and cyclic codes; the field arithmetic those need is in finite fields. Channel coding adds redundancy while entropy coding removes it — they are inverse operations applied in that order for a reason, and compressing after coding destroys the code. The capacity bound itself belongs to entropy, and the constellation whose symbols these codes protect belongs to digital modulation.