Channel Capacity and Error-Correcting Codes

Before 1948 the assumption was obvious: push data faster down a noisy wire and errors rise, so reliability must be bought with slowness. Shannon proved otherwise. Theorem 11, in section 13 of A Mathematical Theory of Communication (Bell System Technical Journal, vol. 27, 1948), states that for a channel of capacity $C$ and a source of entropy $H$ per second:

If $H \le C$ there exists a coding system such that the output of the source can be transmitted over the channel with an arbitrarily small frequency of errors.

Below capacity, errors can be driven as close to zero as you like. Above it, they cannot. There is a wall, and up against it there is no penalty at all.

Shannon's proof is famously non-constructive. He gets the result, in his words, "not by exhibiting a coding method having the desired properties, but by showing that such a code must exist in a certain group of codes." He proved good codes exist without producing one. The next 45 years of coding theory were spent finding them.

Two capacity formulas carry most of the practical weight.

The binary symmetric channel. Each bit flips independently with probability $p$. Capacity is $C = 1 - H(p)$ bits per channel use. At $p = 0.1$, $H(0.1) = 0.4690$, so $C = 0.5310$. Roughly half your bits survive as usable information. This follows directly from the symmetric-channel result in section 16 of Shannon's paper, though he never writes the binary case out himself.

The bandwidth version. Shannon gave the continuous form in Communication in the Presence of Noise (Proceedings of the IRE, vol. 37, no. 1, January 1949, pp. 10-21), as Theorem 2:

$C = B \log_2 \left(1 + \frac{S}{N}\right)$

A 20 MHz Wi-Fi channel at 20 dB signal-to-noise ratio gives $20 \times \log_2(101) = 133$ Mbit/s. Every marketing number above that line is aggregation, wider channels, or more antennas, never better coding.

The name honours R. V. L. Hartley, whose Transmission of Information (BSTJ, vol. 7, no. 3, July 1928, pp. 535-563) supplied the bandwidth half two decades earlier.

The naive way to survive noise is repetition. Send every bit three times, majority-vote at the far end, and you can fix any single flip.

send 1 -> 111 ; receive 101 -> majority vote -> 1

It works, and it is terrible. You pay 3 bits to carry 1, a rate of 1/3, and you still only fix one error per triple. Repetition spends redundancy on each bit separately, so the bits never help each other.

Good codes make redundancy collective. Each check bit constrains an overlapping subset of the data bits, so a single error violates a distinctive combination of checks, and that combination names the culprit. The same 3 redundant bits that protect 1 bit under repetition protect 4 bits under Hamming's scheme, and still correct any single error.

Redundancy is not about how much you add. It is about how cleverly the additions overlap.

Richard Hamming published Error Detecting and Error Correcting Codes in the Bell System Technical Journal, vol. XXIX, no. 2, April 1950, pp. 147-160. He opens by naming the itch: he was "led to the study given in this paper from a consideration of large scale computing machines in which a large number of operations must be performed without a single error in the end result."

The IEEE Computer Society's account of the origin has him in 1947 with a relay computer that had been running unattended since Friday evening, finding it had halted on a detected error and thrown the work away. His reaction: "if a machine can find out that there is an error, why can't it locate where it is and change the setting of the relay from one to zero or zero to one?"

The construction is elegant. Number the positions 1 to 7. Put check bits at the powers of two, positions 1, 2 and 4, and data everywhere else. Check bit 1 covers all positions whose index has bit 0 set, that is 1, 3, 5, 7. Check bit 2 covers 2, 3, 6, 7. Check bit 4 covers 4, 5, 6, 7.

Encode the data nibble 1011. Data goes to positions 3, 5, 6, 7; check bits are chosen for even parity over their coverage sets.

positions:  1  2  3  4  5  6  7
data:       .  .  1  .  0  1  1

c1 over {3,5,7} = 1 xor 0 xor 1 = 0
c2 over {3,6,7} = 1 xor 1 xor 1 = 1
c4 over {5,6,7} = 0 xor 1 xor 1 = 0

codeword:   0  1  1  0  0  1  1

Now flip position 5 in transit, giving 0 1 1 0 1 1 1. The receiver recomputes each parity over its full set:

s1 over {1,3,5,7} = 0 xor 1 xor 1 xor 1 = 1
s2 over {2,3,6,7} = 1 xor 1 xor 1 xor 1 = 0
s4 over {4,5,6,7} = 0 xor 1 xor 1 xor 1 = 1

syndrome = s4 s2 s1 = 101 binary = 5

The syndrome is not a flag. It is the address of the broken bit. Flip position 5 back and the codeword is exact. Every single-bit error in positions 1 through 7 produces its own position number, and a clean codeword produces syndrome 0.

Every stage of the Hamming path, from data nibble to repaired codeword:

Hamming derived a bound on how efficient this can be: you need $2^k > n + 1$, where $k$ is the number of check bits and $n$ the total length. Count the sphere-packing for the (7,4) code:

16 valid codewords x (1 correct + 7 single-error patterns) = 128
total 7-bit strings                                       = 128

Every one of the 128 possible received words sits in exactly one codeword's neighbourhood, with nothing left over. That makes the Hamming (7,4) code perfect, a rare property. Its minimum distance is 3, which is what buys single-error correction. Add one more parity bit for distance 4 and you get SECDED: single error correction, double error detection.

That is not history. It is the memory in production servers right now. As Synopsys described in October 2020, ECC DIMMs add 8 bits to every 64, making the DDR4 modules in enterprise servers 72 bits wide, and "the ECC SECDED mechanism allows the controller to correct any single-bit error and detect double-bit errors." A 1950 paper, running under every serious database on Earth.

Hamming codes fix scattered single bits. Real damage is rarely scattered. A scratch, a dust particle, a bad flash block: these destroy runs of adjacent bits.

Irving Reed and Gustave Solomon's answer, Polynomial Codes Over Certain Finite Fields (Journal of the Society for Industrial and Applied Mathematics, vol. 8, no. 2, June 1960, pp. 300-304), works over symbols rather than bits, typically bytes in the field $GF(256)$. A burst that wrecks 8 consecutive bits damages one or two symbols, not eight errors.

Reed-Solomon codes are MDS, maximum distance separable, meaning they achieve the best possible minimum distance for their size: $d = n - k + 1$. Verify it against a real spec. ECMA-267 (3rd edition, April 2001, clause 18) defines the DVD as two nested Reed-Solomon codes:

RS(208,192,17):  208 - 192 + 1 = 17  OK
RS(182,172,11):  182 - 172 + 1 = 11  OK

The gotcha that matters most in practice: an RS(n,k) code corrects $n-k$ erasures but only $(n-k)/2$ errors. An erasure is a symbol you know is missing; an error is a wrong symbol masquerading as right. Knowing the location is worth exactly a factor of two.

Compact discs. IEC 60908 (2nd edition, February 1999, clause 16.3) specifies cross-interleaved Reed-Solomon coding with two codes over $GF(2^8)$: "C1 is a (32,28) Reed-Solomon Code" and "C2 is a (28,24) Reed-Solomon Code." C1 decodes first, C2 second, and interleaving between them spreads a physical scratch across many codewords so no single one is overwhelmed. Lane, Van Dommelen and Cada (IEEE Transactions on Education, vol. 44, no. 1, February 2001, pp. 47-60) put the fully correctable burst at about 4000 data bits, roughly 2.5 mm of track.

QR codes. ISO/IEC 18004 defines four levels, and section 5.1(f) of the 2024 edition gives their capacities as L 7%, M 15%, Q 25%, H 30%. Be precise here, because popular articles routinely are not: those percentages are of symbol codewords, not of physical area. Masahiro Hara's team at Denso Wave announced the format in 1994, and this is why a logo pasted over the middle of a QR code still scans.

Deep space. CCSDS 130.1-G-3 (June 2020) records that "the Voyager code consists of the recommended concatenation of the (255, 223) RS code with the (7,1/2) convolutional code," Reed-Solomon on the outside. That code corrects up to 16 bad bytes in every 255.

Hamming and Reed-Solomon are algebraic: they guarantee exact correction up to a threshold and fail beyond it. They also sit well short of capacity. Closing that gap took until 1993.

Turbo codes. Berrou, Glavieux and Thitimajshima, Near Shannon limit error-correcting coding and decoding (Proceedings of ICC '93, vol. 2, pp. 1064-1070), used two concatenated recursive encoders separated by a 256 by 256 interleaver, with decoders passing probabilistic beliefs back and forth. At rate 1/2 with 18 iterations they reported bit error rates below $10^{-5}$ at an $E_b/N_0$ of 0.7 dB. The community reaction, as Costello and Forney later recorded, was "it can't be true; they must have made a 3 dB error."

LDPC codes turned out to be older than the excitement. Robert Gallager described them in IRE Transactions on Information Theory (vol. 8, no. 1, January 1962, pp. 21-28), from a dissertation completed in 1960 and published as an MIT Press monograph in 1963. They were then largely ignored until MacKay and Neal revived them in Electronics Letters (vol. 32, no. 18, August 1996), MacKay noting it is "remarkable that they have been generally neglected since 1963."

Polar codes (Arikan, IEEE Transactions on Information Theory, vol. 55, no. 7, July 2009, pp. 3051-3073) are the first construction proved to achieve capacity, with encoding and decoding both $O(N \log N)$.

These are not laboratory curiosities. 3GPP TS 38.212, the 5G NR multiplexing and channel coding specification, assigns them by channel type:

The split is a design argument about block length. Data blocks are long, where LDPC's parallel decoding wins on throughput; control messages are short, where polar codes hold their advantage. 5G's LDPC uses two base graphs, BG1 at 46 by 68 for larger blocks up to 8448 bits, and BG2 at 42 by 52 for smaller ones up to 3840 bits.

Wi-Fi took the same direction earlier and more cautiously: IEEE 802.11n, published October 2009, added LDPC as an optional alternative to its mandatory convolutional coding, and later amendments widened where it is required rather than replacing what came before. Both coexist in shipping silicon.

Distributed storage faces the same question with different economics. A lost disk is an erasure: you know precisely which shard vanished. That is the favourable case from two steps ago, so the full $n-k$ redundancy is available.

Apache Hadoop's 3.0.0 documentation states the comparison bluntly: "the default 3x replication scheme in HDFS has 200% overhead in storage space," while "standard encodings like Reed-Solomon (10,4) have a 1.4x space overhead." Their worked case: six blocks cost 18 under 3x replication and 9 under RS(6,3).

So why replicate at all? Repair cost. Replacing a lost replica means copying one block from one peer. Rebuilding a lost RS shard means reading $k$ shards from $k$ different machines and recomputing. Dimakis and colleagues (IEEE Transactions on Information Theory, vol. 56, no. 9, September 2010) put the sting precisely: to regenerate one fragment of size $M/k$, you must move $M$ bits, the entire object.

That cost drives real designs. Microsoft's Local Reconstruction Codes (Huang et al., USENIX ATC 2012) deployed LRC(12,2,2) at 1.33x overhead specifically to cut how many fragments a repair must read. Meta's f4 (OSDI 2014) moved 65 PB of BLOBs from an effective replication factor of 3.6 down to 2.8 or 2.1. Backblaze reported in May 2024 that it runs 17/3, 16/4 and 15/5 shard ratios, choosing more parity for larger drives because larger drives take longer to rebuild.