Field Guide · algorithm

Also known as: LDPC code, low-density parity-check code, Gallager code

A low-density parity-check (LDPC) code is a linear block code defined by a sparse parity-check matrix — one with very few 1s — decoded by passing probabilistic messages back and forth on a bipartite graph until they settle.1 First described by Gallager in 1962 and rediscovered in the 1990s, LDPC codes reach within a fraction of a decibel of the Shannon limit while decoding with cheap, parallelisable arithmetic, which is why they now carry the highest-throughput channels in Wi-Fi, 5G, and satellite.2

check nodes (parity equations) variable nodes (code bits)
An LDPC code is a Tanner graph: each check node enforces one parity equation over the few bits it touches, and decoding passes soft messages along the sparse edges.

How it works

The code is fully specified by its parity-check matrix H: a valid codeword is any bit vector that satisfies every parity equation (every row of H). “Low density” means each equation involves only a handful of bits and each bit appears in only a handful of equations. Draw a Tanner graph with one variable node per code bit and one check node per parity equation, connecting them wherever H has a 1 — the graph is sparse.

Decoding is iterative belief propagation (the sum-product algorithm):

  • Each variable node starts with the channel’s soft estimate (an LLR) of its bit.
  • Variable nodes send their beliefs to the check nodes they touch; each check node combines the incoming messages to tell every connected bit what value would make its parity equation hold.
  • Bits gather these hints, update their beliefs, and send again. As with turbo decoding, each message carries only extrinsic information — a node never echoes back what a neighbour just told it.
  • After each round the current hard decisions are checked against H; when all parity equations are satisfied (or an iteration cap is hit) decoding stops.

Because the graph is sparse and every node’s update is local, the whole thing parallelises beautifully in hardware. A cheaper approximation, min-sum, replaces the exact check-node math with a minimum and a sign product, trading a small loss for much simpler logic.

Variants

Codes are called regular when every bit and every check has the same number of edges, and irregular when the degrees vary — carefully chosen irregular degree distributions give the best threshold performance. Practical standards use quasi-cyclic LDPC codes, whose H is built from small circulant blocks so the same hardware handles many block lengths and rates, and rate is adapted by adding or shortening parity blocks rather than heavy puncturing.

Relevance to SDR

LDPC codes protect the data channels of 5G NR, the high-throughput modes of Wi-Fi (802.11n/ac/ax), DVB-S2/S2X satellite broadcast, and 10GBASE-T Ethernet — almost always paired with OFDM waveforms. They are a capacity-approaching alternative to turbo codes and polar codes, differing mainly in graph structure and decoder. The land-mobile and aviation formats GopherTrunk decodes rely on block and convolutional FEC rather than LDPC, so GT does not implement an LDPC decoder; it is documented here as a pillar of modern forward error correction in broadband and satellite systems.

Sources

  1. Low-density parity-check code — Wikipedia, for the sparse-matrix definition and belief-propagation decoding. ↩

  2. Low-density parity-check codes — R. G. Gallager, IRE Trans. Information Theory (1962), the originating work. ↩

See also