Field Guide · person

Also known as: Robert Gallager, Robert G. Gallager

Robert Gallager (born 1931) is an American electrical engineer and information theorist who invented low-density parity-check (LDPC) codes and made foundational contributions to the theory of reliable communication.12 His LDPC codes, introduced in his 1960 doctoral thesis, are among the most powerful forward error correction schemes known and are used across modern wireless and storage systems.

bits checks
An LDPC code is defined by a sparse parity-check matrix, drawn here as a Tanner graph linking code bits to a few parity checks each.

Life and work

Gallager earned his doctorate from MIT in 1960 and spent his career there, becoming a professor of electrical engineering and a leading figure in the information-theory community. His thesis introduced LDPC codes together with the iterative decoding idea that makes them work; the codes were so far ahead of the hardware of the day that they were largely set aside for three decades before being rediscovered in the 1990s.1 He also wrote influential texts on information theory and on data networks, and won the Claude E. Shannon Award and the U.S. National Medal of Science.

Contribution

An LDPC code is a linear block code defined by a parity-check matrix that is sparse — each parity equation involves only a handful of the code’s bits, and each bit participates in only a few equations. That sparsity is the whole trick. It lets the code be decoded by iterative message passing (belief propagation) over the bipartite “Tanner graph” of bits and checks: each check node and bit node repeatedly exchanges its best estimate of the bit values, and the estimates converge toward a valid codeword after a few rounds.2 Because the graph is sparse, each iteration is cheap, so very long, very strong codes become decodable in practice.

Gallager also contributed the theory of error exponents, quantifying how the probability of a decoding error falls off as block length grows for a channel operated below its Shannon capacity — a sharpening of Claude Shannon’s existence results into rate-versus-reliability trade-offs.

Legacy

For decades LDPC codes were a mathematical curiosity, too expensive to decode with the electronics of the 1960s. Their rediscovery — spurred by the arrival of turbo codes and cheap iterative-decoding hardware — made them the error-correction method of choice for systems that must operate close to the Shannon limit. Gallager’s iterative-decoding idea, once exotic, is now standard engineering.

Relevance to SDR

LDPC codes are everywhere in modern digital radio: Wi-Fi (802.11n/ac/ax), 5G NR data channels, DVB-S2 and DVB-T2 broadcasting, 10-Gigabit Ethernet, and flash-memory controllers all rely on them to squeeze reliable throughput out of noisy channels. They sit alongside turbo codes and polar codes as the capacity-approaching family that displaced older convolutional schemes for high-rate links. The land-mobile trunking protocols GopherTrunk targets (P25, DMR, NXDN, TETRA) predate this family and use simpler block and convolutional codes, so GopherTrunk itself does not decode LDPC, but the codes are foundational to the broader software-radio landscape.

Sources

  1. Robert G. Gallager — Wikipedia, for biography, awards, and the 1960 thesis. ↩ ↩2

  2. Low-density parity-check code — Wikipedia, for the sparse parity-check structure and iterative decoding. ↩ ↩2

See also