ECC robustness comparison

Probability that the exact message is recovered, vs. channel noise level. 100 trials/cell. Each cell holds three configurations: left = M=32 @ N=8000 (250×), middle = M=100 @ N=8000 (80×), right = M=100 @ N=25008 (250×, rate-matched to the left). Sub-cells shaded red→green; the best method per row (per config) is outlined.

left M=32@8000: Rep 250× · RS(500,2) · BCH t=1503 · RM(2,9)  |  middle M=100@8000: Rep 80× · RS(500,7) · BCH t=1469 · RM(3,9)  |  right M=100@25008: Rep 250× · RS(1563,7) · BCH t=1783 (field-capped) · RM(3,9)×48

BSC — random bit flips

Erasure channel

How each method works

Repetition

Each message bit is transmitted N/M times; the decoder takes a majority vote over the copies (over the non-erased copies on the erasure channel). No structure beyond replication — but at very low rate that is already remarkably strong.

Extended Hamming(8,4)

A classic linear block code: 4 data bits → 8 coded bits (7 Hamming bits + 1 overall parity), minimum distance 4 — single-error-correcting, double-error-detecting (SECDED). The base codeword is repeated to fill N; the decoder collapses repeats by majority, then syndrome-corrects one bit error per block.

Reed–Solomon

A maximum-distance-separable (MDS) code over GF(2¹⁶) with 16-bit symbols. Decoding: syndromes → Berlekamp–Massey → Chien search → Forney (plus erasures). MDS ⇒ any k symbols suffice (great for bursts) — but a 16-bit symbol dies if any one of its bits is hit, so it is weak against independent bit/erasure noise.

Spread / random linear

A sparse random linear code: each output bit is the XOR of 3 random message bits. Decoded by information-set decoding (solve M equations exactly over GF(2)) followed by greedy bit-flip polishing, over many restarts. Weight must be odd, else the all-ones vector is undecodable.

BCH (shortened binary)

A cyclic, bit-level code over GF(2¹³) whose generator has 2t consecutive roots, guaranteeing correction of any t bit errors. Decoding: syndromes → Berlekamp–Massey → Chien (binary, no Forney). Bounded-distance: perfect up to t errors, then a sharp cliff. The field limits the codeword to 8191 bits, so it can't use the full 25008 (right column) — not truly rate-matched there. Errors-only, so erasures hurt it.

RM(1) + FHT

First-order Reed–Muller / biorthogonal (Hadamard) code, minimum distance 2^m-1. Decoded by a single Fast Hadamard Transform — the peak transform coefficient is the closest codeword (near-maximum-likelihood). The classic low-rate / deep-space code (Mariner). Blocks carry m+1 bits each, repeated and soft-combined.

RM(r,m) general

Higher-order Reed–Muller, dimension Σ_i≤r C(m,i), distance 2^m-r. Decoded by the recursive Plotkin (|u|u+v|) soft-decision algorithm. More flexible than RM(1) but a higher rate per block, so slightly weaker.

LDPC + belief propagation

Low-density parity-check code — here a Repeat-Accumulate construction decoded by iterative belief propagation (normalized min-sum). The modern workhorse (WiFi, 5G, DVB-S2). A basic RA(2) + min-sum instance — untuned; a well-designed irregular LDPC would do better.

Polar + SC

Arıkan's polar code: channel polarization concentrates reliability onto a subset of synthetic bit-channels; the message rides the most reliable ones, the rest are frozen. Decoded by successive cancellation. Plain SC (no list); construction is puncturing-aware. Heavy puncturing (right column, 32768→25008) still hurts; a list decoder (SCL) would help.

Fountain / LT

A rateless code: each output bit is the XOR of a Robust-Soliton-random subset of message bits. Decoded by peeling. Near-optimal on the erasure channel (its design target); not an error-correcting code on the BSC.