Sparse Parity-Check Codes and Iterative Decoding

A code is a set of codewords, and the practical question is how to describe one compactly enough to decode it and how to decode it fast enough to matter. Algebraic codes answer the first question with structure, such as a generator polynomial over a finite field, and the second with an algorithm that exploits that structure. Sparse-graph codes answer both differently: the code is defined by a parity-check matrix that is mostly zeros, and decoding is a message-passing procedure whose cost per iteration is linear in the number of edges rather than in the cube of the block length.

The code as the null space of a sparse matrix

A binary linear code is the set of vectors $x \in {0,1}^n$ satisfying $Hx^T = 0$ over GF(2), for some parity-check matrix $H$ with $m$ rows. Each row is a parity constraint: the XOR of the entries in its support must be zero. The code’s rate is $(n - \text{rank}(H))/n$, which for a full-rank $H$ is $1 - m/n$. A low-density code chooses $H$ with a small constant number of ones per column, typically 3, and a row weight chosen to set the rate.

The Tanner graph is the bipartite graph with a variable node per column and a check node per row, and an edge wherever $H$ has a one. A column weight of 3 means every variable participates in three checks. The graph’s girth, the length of its shortest cycle, matters because message passing is exact only on trees; cycles cause messages to return to their origin and inflate confidence. Random sparse graphs have few short cycles by construction, which is why random construction is not a compromise but a design choice.

The code is defined by $H$, but encoding requires a generator matrix $G$ whose rows span the null space of $H$, so that $GH^T = 0$. For a random sparse $H$ the systematic form is generally dense, so encoding costs $O(n^2)$ unless the matrix is designed with structure. The standard fix is to constrain $H$ to an approximate lower-triangular form so that the parity bits can be computed by back-substitution, which restores near-linear encoding at a small cost in code quality. This is the one place where the sparse construction is deliberately compromised.

The codes used in practice are irregular: rather than a fixed column weight, the design specifies a degree distribution, a fraction of columns of each weight. Irregular ensembles can be tuned to a better threshold than regular ones, and the price is that the analysis becomes a fixed-point condition on a distribution rather than a single number.

Belief propagation on the graph

Decoding estimates each bit from the channel output and from the constraints. The sum-product algorithm passes messages along edges: a variable node sends each check its current belief about its own value, excluding the information that check previously provided; a check node sends each variable the probability that the parity constraint is satisfied given the other variables’ beliefs.

In the log domain the check update is a soft XOR. For a check of degree $d$ receiving log-likelihood ratios $\lambda_1, \ldots, \lambda_{d-1}$ from its other neighbours, the message to neighbour $i$ is

$$2 \operatorname{artanh}!\left(\prod_{j \ne i} \tanh \frac{\lambda_j}{2}\right)$$

which is exact for a tree and is the source of both the method’s power and its numerical fragility. The product of hyperbolic tangents underflows for large negative inputs, so implementations use the min-sum approximation, replacing the product with the minimum magnitude and the product of signs. Min-sum costs a constant per edge instead of a transcendental, at a small loss in accuracy that is usually recovered by a normalization or offset factor.

def check_update(llrs):
    """llrs: incoming LLRs from all neighbours but one. Returns outgoing LLR."""
    sign = 1.0
    mag = float('inf')
    for v in llrs:
        if v < 0:
            sign = -sign
        a = abs(v)
        if a < mag:
            mag = a
    return sign * mag          # min-sum approximation

def variable_update(channel_llr, incoming):
    return channel_llr + sum(incoming)

The variable update is a plain sum because log-likelihood ratios from independent observations add. Under the usual convention, an LLR is $\log\frac{P(\text{bit} = 0)}{P(\text{bit} = 1)}$, so a positive value votes for 0 and the sign of a check message is the product of the signs of its inputs. For an antipodal mapping $y = 1 - 2x$ over a binary-input AWGN channel with noise variance $\sigma^2$, the channel LLR is $2y/\sigma^2$, which means the decoder needs an estimate of the noise level; a mismatch between the assumed and true $\sigma^2$ degrades performance but does not break the algorithm.

Decoding proceeds for a fixed number of iterations, or until the hard decisions satisfy all parity checks. The check on satisfaction is cheap, one pass over the edges, and it is the only reliable stopping criterion, since the decoder has no access to the transmitted message.

Why the threshold exists

For a large random sparse graph, the density of messages in the decoder converges to a fixed-point distribution that can be tracked analytically, a technique called density evolution. The tracking yields a threshold: a channel noise level below which the message distributions converge to the all-correct fixed point, and above which they converge to a fixed point with residual error.

The threshold is a property of the ensemble of graphs, not of any particular graph. It is computed for the degree distributions, meaning the fractions of columns of each weight, and optimizing over those distributions produces irregular codes whose threshold lies within a small fraction of a decibel of capacity for the binary-input AWGN channel. That closeness is the substantive result: it says that a code with linear-time decoding and a sparse description can approach the Shannon limit, which algebraic codes with bounded-distance decoding cannot.

The threshold behaviour is sharp in the block length. For a fixed ensemble, the error probability as a function of noise falls steeply near the threshold, and the width of the transition shrinks as the block length grows. At finite block length the transition is smeared, and the relevant engineering quantity is the block error rate at a specified noise level rather than the threshold itself.

The connection to the capacity formula is direct, though the argument runs through mutual information rather than through the threshold. The threshold is the noise level below which the decoder’s messages converge to certainty; the gap between that level and the noise level at which the mutual information between input and output of the channel drops to the code’s rate is what is measured in decibels. Mutual Information and the Capacity of a Noisy Channel gives the capacity side of that comparison.

Error floors and trapping sets

Below the threshold, the block error rate does not continue to fall at the rate the threshold analysis predicts. It flattens into an error floor, and the mechanism is graph structure rather than channel noise.

A trapping set is a small subgraph in which a fixed set of variable nodes remains incorrect while all checks are satisfied or nearly so. Once the decoder enters such a configuration, messages reinforce the wrong values and further iterations do not help. The smallest trapping sets dominate the floor: a set of $a$ variable nodes connected to exactly $b$ odd-degree check nodes, with $a$ and $b$ both small, is a stable wrong fixed point for a range of channel values.

The floor’s height depends on the minimum distance of the code and on the number of low-weight codewords, both of which are properties of the specific graph rather than of the ensemble. Random construction controls these only in expectation, and the variance across instances is large enough that two codes with the same degree distribution can have floors differing by orders of magnitude. Constructions that avoid small trapping sets, such as structured graphs from finite geometries or designs with controlled girth, trade some threshold performance for a lower floor.

The standard mitigation is a concatenated or cascaded structure: an outer code with strong minimum distance handles the residual errors that the inner decoder leaves. This is why several deployed systems use a sparse inner code and a short algebraic outer code, and why the outer code’s job is not to correct the channel’s errors but the inner decoder’s failures.

Where sparse-graph codes sit relative to algebraic ones

The comparison is not a matter of one being better. Algebraic codes have guaranteed minimum distance, bounded-distance decoding with a known correction radius, and algebraic structure that makes erasure decoding exact. A Reed–Solomon code over GF(256) has block length $n \le 255$, dimension $k = n - 2t$, and corrects any $t$ symbol errors with $2t$ parity symbols; $d = n - k + 1$ meets the Singleton bound with equality, so no code over the same alphabet with the same $n$ and $k$ can offer a larger minimum distance. That guarantee is unconditional and does not depend on a graph.

Sparse codes have no such guarantee. Their minimum distance is a random variable, their decoding is suboptimal whenever the graph has cycles, and their performance is characterized by thresholds and floors rather than by a correction radius. In exchange they operate at noise levels far beyond what bounded-distance decoding reaches, and their decoding cost is linear per iteration rather than quadratic or cubic in block length.

The practical division follows. Storage systems and optical transport, where errors arrive in bursts and erasure locations are known, use Reed–Solomon because the algebraic guarantee matches the failure model. Wireless links and satellite channels, where errors are dense and the channel is close to Gaussian, use sparse codes because the threshold is what matters. The LZ77, LZ78, and the Shift from Symbols to Substrings article describes the analogous division on the compression side, where a format’s structural guarantee and its average-case rate are also different things.

Finite-length behaviour and the cost of iteration

The asymptotic story is clean; the deployed one is not. Three effects dominate at the block lengths actually used.

Iteration count. Decoding cost is the number of iterations times the number of edges, and the number needed grows as the noise approaches the threshold. A decoder that stops after a fixed small number of iterations loses performance exactly where the code is most valuable, so practical decoders use a layered schedule, which propagates information from all edges sooner than the flooding schedule and therefore converges in fewer iterations of the same per-edge work, together with an early-termination check.

Quantization. Messages are often stored in a handful of bits rather than full precision, because storing a full-precision value per edge over millions of edges is expensive in memory and in bandwidth to the decoder’s memories. The quantization loss is small at high SNR and grows near the threshold, where the message distribution is broad and the decoder is sensitive to the tails.

Short blocks. Threshold analysis is asymptotic in block length. At a few thousand bits, the gap to capacity is dominated by the finite-length penalty rather than by the code’s design, and the penalty scales with the inverse square root of the block length. This is the same term that appears in the finite-block-length analysis of channel capacity, and it is why short-packet systems cannot reach the rates that long-block analysis promises.