Ferkans — Interactive Telecom Tutor

Definition:
Low-Density Parity-Check (LDPC) Code

An LDPC code is a linear block code defined by a sparse parity-check matrix $\mathbf{H}$ — one in which the number of ones per row and column is much smaller than the block length $n$ .

A regular $(d_v, d_c)$ -LDPC code has exactly $d_v$ ones in every column and $d_c$ ones in every row of $\mathbf{H}$ , with $d_v \ll n$ and $d_c \ll n$ . The code rate satisfies

$R_c = 1 - \frac{d_v}{d_c}$

An irregular LDPC code allows variable column weights and row weights, described by degree distributions $\lambda(x)$ and $\rho(x)$ . Irregular codes can be optimised to approach capacity more closely than regular codes.

The sparsity of $\mathbf{H}$ is critical: it enables low-complexity iterative decoding and allows density evolution analysis.

,

Definition:
Tanner Graph

The Tanner graph of an LDPC code is a bipartite graph with two types of nodes:

Variable nodes $v_1, \ldots, v_n$ : one for each codeword bit.
Check nodes $c_1, \ldots, c_{n-k}$ : one for each parity-check equation (row of $\mathbf{H}$ ).

An edge connects variable node $v_j$ to check node $c_i$ if and only if $H_{ij} = 1$ . The degree of variable node $v_j$ is $d_v(j)$ (the column weight), and the degree of check node $c_i$ is $d_c(i)$ (the row weight).

Short cycles (especially cycles of length 4, called 4-cycles) degrade iterative decoding performance by correlating the messages.

The Tanner graph provides both a visual representation and the computational structure for belief-propagation decoding.

Belief Propagation (Message Passing) Decoding

Belief propagation (BP) decoding operates on the Tanner graph by

iteratively passing messages along edges:

Initialisation:

Each variable node

v_j

sends its channel LLR

L_{\text{ch}}(j)

to all connected check nodes.

Check-node update (for each check node $c_i$ ):

L_{c_i \to v_j} = 2\tanh^{-1}\!\left(\prod_{j' \in \mathcal{N}(i) \setminus j} \tanh\!\left(\frac{L_{v_{j'} \to c_i}}{2}\right)\right)

Variable-node update (for each variable node $v_j$ ):

L_{v_j \to c_i} = L_{\text{ch}}(j) + \sum_{i' \in \mathcal{M}(j) \setminus i} L_{c_{i'} \to v_j}

Decision:

After each iteration, compute the total LLR:

L_{\text{total}}(j) = L_{\text{ch}}(j) + \sum_{i \in \mathcal{M}(j)} L_{c_i \to v_j}

Make hard decisions:

\hat{c}_j = 0

if

L_{\text{total}}(j) \geq 0

,

else

\hat{c}_j = 1

. Stop if

\mathbf{H}\hat{\mathbf{c}}^T = \mathbf{0}

or the maximum number of iterations is reached.

,

Theorem: Capacity-Approaching Design via Density Evolution

Density evolution tracks the probability density of the messages in BP decoding as the block length $n \to \infty$ (assuming a cycle-free graph). Under this analysis:

The decoder converges (error probability $\to 0$ ) if and only if the SNR exceeds a threshold $\sigma^*$ that depends on the degree distributions $(\lambda, \rho)$ .
By optimising the degree distributions, the threshold can be made arbitrarily close to the Shannon limit.

Richardson and Urbanke (2001) showed that irregular LDPC codes designed via density evolution can achieve rates within 0.0045 dB of the binary-input AWGN channel capacity.

With infinite block length and no cycles, each message in BP is independent. Density evolution exploits this independence to analytically track how the message distributions evolve, predicting whether decoding will succeed.

Proof

Concentration theorem

For a randomly chosen LDPC code from the ensemble defined by $(\lambda, \rho)$ , the decoder's empirical message distribution concentrates around the density-evolution prediction as $n \to \infty$ .

Threshold characterisation

Density evolution computes the error probability after $\ell$ iterations, $p^{(\ell)}$ , recursively. The threshold is the supremum of noise levels for which $p^{(\ell)} \to 0$ as $\ell \to \infty$ . $\blacksquare$

,

Iterative Decoding Animation

Watch belief-propagation or turbo decoding converge iteration by iteration. The animation shows how the LLR histogram evolves from a noisy, uncertain distribution toward confident binary decisions.

Parameters

Code type

Eb/N0 (dB)2

Maximum iterations20

Example: A Simple (8, 4) LDPC Code

Consider the (8, 4) LDPC code with parity-check matrix

$\mathbf{H} = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}$

(a) Draw the Tanner graph and identify the variable/check node degrees.

(b) Verify that $\mathbf{H}$ is sparse and determine the code rate.

(c) Run one iteration of BP decoding given channel LLRs $\mathbf{L}_{\text{ch}} = [+3, -1, +2, +4, -2, +1, +3, -1]$ .

Solution

Tanner graph

The Tanner graph has 8 variable nodes ( $v_1$ to $v_8$ ) and 4 check nodes ( $c_1$ to $c_4$ ). Each column has weight 2 ( $d_v = 2$ ) and each row has weight 4 ( $d_c = 4$ ). This is a regular (2, 4)-LDPC code.

Code parameters

Rate: $R_c = 1 - d_v/d_c = 1 - 2/4 = 1/2$ .

Equivalently: $R_c = k/n = 4/8 = 1/2$ .

The matrix is sparse: only 16 ones out of $4 \times 8 = 32$ entries (50% density), which is denser than practical LDPC codes but illustrates the concept.

One BP iteration

Variable-to-check (initialisation): Each variable node sends its channel LLR to connected check nodes. E.g., $v_1$ (connected to $c_1, c_2, c_3$ ) sends $L = +3$ to each.

Check-to-variable: Each check node computes outgoing messages using the $\tanh$ rule. For example, $c_1$ (connected to $v_1, v_2, v_3, v_4$ ) sends to $v_1$ :

$L_{c_1 \to v_1} = 2\tanh^{-1}(\tanh(-0.5)\tanh(1)\tanh(2))$ $\approx 2\tanh^{-1}(-0.46 \times 0.76 \times 0.96) \approx -0.72$

After one iteration, the updated LLRs show initial refinement of the bit estimates. $\blacksquare$

Quasi-Cyclic LDPC Codes in 5G NR

Practical LDPC codes in standards use quasi-cyclic (QC) structure: the parity-check matrix is composed of circulant permutation matrices (or zero matrices) of size $Z \times Z$ . This structure enables:

Efficient encoding in $O(n)$ time using the dual-diagonal or raptor-like structure.
High-throughput hardware decoding with $Z$ -fold parallelism.
Rate compatibility through puncturing and extending.

The 5G NR LDPC code uses two base graphs: BG1 (for large transport blocks, up to $n = 66 \times Z$ with $Z$ up to 384) and BG2 (for small blocks).

Quick Check

Which of the following is a key advantage of LDPC codes over turbo codes for high-throughput applications?

LDPC codes always have larger minimum distance

LDPC belief-propagation decoding is inherently parallelisable

LDPC codes require fewer iterations to converge

LDPC codes were invented more recently

Correction:

LDPC belief-propagation decoding is inherently parallelisable

BP decoding updates all variable/check nodes simultaneously, enabling massive parallelism in hardware. Turbo decoding requires sequential trellis processing, limiting throughput.

Why This Matters: LDPC Codes in Wi-Fi and 5G NR

LDPC codes are deployed in major wireless standards:

Wi-Fi (IEEE 802.11n/ac/ax/be): LDPC codes with block lengths 648, 1296, and 1944 bits at rates 1/2, 2/3, 3/4, and 5/6. Mandatory in 802.11ax (Wi-Fi 6) for high-throughput modes.
5G NR (data channels): QC-LDPC codes replace turbo codes from 4G LTE. Two base graphs support transport block sizes from 40 to 8448 bits. The quasi-cyclic structure with lifting size $Z$ enables decoder throughputs exceeding 20 Gbps.
DVB-S2/T2 (digital TV): LDPC codes with block length 64800 operating within 0.7-1.0 dB of the Shannon limit.

⚠️Engineering Note

LDPC Decoder Throughput and Latency in 5G NR

Practical LDPC decoder implementations in 5G NR base stations must achieve throughputs exceeding 20 Gbps to support eMBB peak rates. Key implementation constraints include:

Parallelism: QC-LDPC structure enables $Z$ -fold parallelism (with $Z$ up to 384), processing $Z$ variable/check nodes simultaneously per clock cycle.
Iterations: Typically 5-15 BP iterations suffice; more iterations increase latency without significant gain. Early termination (checking syndrome after each iteration) saves power.
Quantisation: Fixed-point arithmetic (5-6 bits per LLR) is standard. Below 4 bits, performance degrades noticeably ( $> 0.1$ dB loss).
Memory: Storing soft LLRs for HARQ soft combining requires significant buffer memory — up to 3.4 Mbits per UE for 16 parallel HARQ processes.

Practical Constraints

•
Decoder throughput must exceed 20 Gbps for eMBB peak rates
•
LLR quantisation to 5-6 bits with < 0.1 dB performance loss
•
HARQ soft buffer memory up to 3.4 Mbits per UE
•
Latency budget of ~1 ms for HARQ round-trip

📋 Ref: 3GPP TS 38.212, TS 38.214

Key Takeaway

Modern iterative codes (turbo, LDPC, polar) operate within 1 dB of the Shannon limit — a feat that seemed impossible before 1993. The key enabler is iterative decoding on sparse graphs, which achieves near-ML performance at complexity linear in the block length per iteration. 5G NR uses LDPC for data (high throughput via parallelism) and polar codes for control (short blocks with CA-SCL).

LDPC Code

A linear block code defined by a sparse parity-check matrix, enabling efficient iterative decoding via belief propagation. Can be designed to approach channel capacity.

Tanner Graph

A bipartite graph representation of a parity-check matrix, with variable nodes (coded bits) and check nodes (parity equations) connected by edges corresponding to non-zero entries in $\mathbf{H}$ .

Belief Propagation

An iterative message-passing algorithm that computes approximate marginal probabilities on a factor graph. Used as the standard decoding algorithm for LDPC codes.

Density Evolution

An analytical technique that tracks the probability density of messages in belief-propagation decoding as block length tends to infinity, used to determine decoding thresholds and optimise degree distributions.

Low-Density Parity-Check (LDPC) Codes

Definition: Low-Density Parity-Check (LDPC) Code

Definition: Tanner Graph