How does belief propagation decode LDPC codes?

BP decoding operates on the Tanner graph representation of the LDPC parity-check matrix H. The graph has N variable nodes (one per code bit) and M check nodes (one per parity equation). Edges connect variable node i to check node j if H[j][i] = 1. Each iteration has two half-steps: 1) Check-to-variable messages: each check node c computes a message to each connected variable node v, representing the check's belief about v given all other connected variables. Using the sum-product rule: L(c→v) = 2·arctanh(∏_{v'≠v} tanh(L(v'→c)/2)). This computes the parity constraint's influence on the bit probability. 2) Variable-to-check messages: each variable node v computes a message to each connected check node c by summing its channel LLR (from the demodulator) with all incoming check messages except from c: L(v→c) = L_channel(v) + Σ_{c'≠c} L(c'→v). After each iteration, a hard decision is made: if the total LLR (channel + all check messages) is positive, the bit is decoded as 0; if negative, decoded as 1. Decoding terminates when all parity checks are satisfied (syndrome = 0) or the maximum iteration count is reached.

What is the difference between sum-product and min-sum decoding?

Sum-product (SP) is the exact BP algorithm using the full tanh/arctanh computation: L(c→v) = 2·arctanh(∏ tanh(L_i/2)). This is computationally expensive because tanh and arctanh require lookup tables or CORDIC implementations in hardware. Min-sum (MS) is a simplified approximation: L(c→v) = (∏ sign(L_i)) × min(|L_i|). This replaces the tanh product with a minimum operation, which is much cheaper in hardware (comparators instead of multipliers). Performance cost: min-sum loses 0.2-0.5 dB compared to sum-product. Normalized min-sum (NMS): L(c→v) = α × (∏ sign(L_i)) × min(|L_i|), where α ≈ 0.75-0.85, recovers 0.1-0.2 dB of the loss. Offset min-sum (OMS): L(c→v) = (∏ sign(L_i)) × max(min(|L_i|) - β, 0), where β ≈ 0.15-0.5, provides similar recovery. In practice, all commercial LDPC decoder ASICs use min-sum variants (NMS or OMS) because the area and power savings are substantial: 3-5x fewer gates and 2-3x lower power than sum-product implementations.

How many iterations are needed and what determines convergence?

Iteration count depends on code structure, SNR, and required error performance: Low SNR (near threshold): 20-50 iterations needed. Many bits have uncertain LLRs, requiring more message exchanges to resolve ambiguity. Error floor region (high SNR): 5-10 iterations suffice. Most bits have high-confidence channel LLRs; the decoder mainly corrects a few weak bits. Typical configurations: 5G NR LDPC: 6-25 iterations (base graph 1, max code rate). Wi-Fi 6/7 LDPC: 10-30 iterations. DVB-S2: 50 iterations max (concatenated BCH outer code cleans residual errors). Convergence is guaranteed on tree-like graphs (no cycles). Real LDPC codes have cycles of length ≥ 4 (girth), which can cause oscillation (trapping sets). Short cycles (girth 4) degrade performance; modern LDPC code design ensures minimum girth ≥ 6. Early termination: checking the syndrome (H×decoded = 0) after each iteration allows stopping early when decoding succeeds, saving average power. Typical early termination saves 30-60% of iterations at operating SNR.

Channel Coding

Belief Propagation

/bih-LEEF prop-uh-GAY-shun/

Iterative message-passing algorithm on Tanner graphs for LDPC/turbo decoding. Variable nodes (code bits) and check nodes (parity equations) exchange LLRs. Sum-product: L = 2·arctanh(∏tanh(L_i/2)). Min-sum approximation: L = (∏sign)×min(|L_i|), 0.2 to 0.5 dB loss but 3 to 5x fewer gates. Converges in 5 to 50 iterations. Used in 5G NR LDPC, Wi-Fi 6/7, DVB-S2. Performance: 0.5 to 1.0 dB from Shannon limit.

Iterations: 5–50

Gap to Shannon: 0.5–1 dB

Standard: 5G/Wi-Fi/DVB

Understanding Belief Propagation

Belief propagation is the engine inside every modern channel decoder. When a 5G phone receives data, the demodulator produces soft information (LLRs) for each bit, indicating both the estimated value and the confidence level. BP takes these noisy estimates and iteratively refines them using the code's parity structure, converging on the most likely transmitted codeword.

The algorithm works because parity check equations create dependencies between code bits: if a check node knows that all but one of its connected bits are correct, it can infer the remaining bit. By iterating these local inferences across the entire code graph, global consistency emerges, correcting bit errors far beyond what any single parity check could achieve alone.

BP Message Equations

Check-to-Variable (sum-product):
L(c→v) = 2·arctanh(∏_v'≠v tanh(L(v'→c)/2))

Check-to-Variable (min-sum):
L(c→v) = (∏ sign(L_i)) × min(|L_i|)
NMS: × α (α ≈ 0.75–0.85)
OMS: max(min − β, 0) (β ≈ 0.15–0.5)

Variable-to-Check:
L(v→c) = L_ch(v) + ∑_c'≠c L(c'→v)

Decision:
L_total(v) = L_ch(v) + ∑_c L(c→v)
Decode: bit = 0 if L_total > 0, else 1

Decoder Algorithm Comparison

Algorithm	Complexity	Gap to SP	Hardware
Sum-product (SP)	High (tanh LUT)	0 dB (reference)	Large area/power
Min-sum (MS)	Low (comparators)	0.2–0.5 dB	3–5x smaller
Normalized MS	Low + multiply	0.05–0.3 dB	~3x smaller
Offset MS	Low + subtract	0.05–0.3 dB	~3x smaller

Common Questions

Frequently Asked Questions

How does BP decode LDPC?

Iterates on Tanner graph: check nodes send parity beliefs via tanh product, variable nodes sum channel LLR + all check messages. Hard decision each iteration; stop when syndrome = 0 or max iterations reached.

Sum-product vs. min-sum?

SP: exact but expensive (tanh/arctanh). MS: comparators only, 3 to 5x fewer gates, 0.2 to 0.5 dB worse. NMS/OMS recover 0.1 to 0.2 dB with scaling/offset. All commercial ASICs use MS variants.

Iterations needed?

Low SNR: 20 to 50. High SNR: 5 to 10. Early termination (syndrome check) saves 30 to 60% of iterations at operating SNR. Min girth ≥6 prevents oscillation from short cycles.

Related Terms

← Bel Bell State →

Channel Coding

Precision RF Components

RF Essentials provides precision terminations and custom waveguide assemblies for baseband test systems, BER measurement equipment, and channel emulation platforms.

Request a Quote