LDPC Codes

Low-Density Parity-Check codes — from Gallager's forgotten thesis to the backbone of modern wireless, storage, and broadcast systems.

Roadmap

Gallager's 1962 Thesis

What Makes a Parity-Check Matrix "Low Density"?

Tanner Graphs

Regular vs Irregular LDPC Codes

Constructing LDPC Codes

Building an LDPC Matrix in Python

import numpy as np
from scipy.sparse import csr_matrix

def gallager_ldpc(n, dv, dc):
    """
    Construct a regular (dv, dc)-LDPC parity-check matrix
    using Gallager's random construction.

    n  = code length (number of variable nodes)
    dv = column weight (variable node degree)
    dc = row weight (check node degree)
    """
    assert (n * dv) % dc == 0, "n*dv must be divisible by dc"
    m = (n * dv) // dc  # number of check nodes
    rate = 1.0 - dv / dc

    # Build base submatrix: m/dv rows, each row has dc consecutive 1s
    rows_per_section = m // dv
    H = np.zeros((m, n), dtype=int)

    # First section: identity-like structure
    for i in range(rows_per_section):
        for j in range(dc):
            H[i, i * dc + j] = 1

    # Remaining sections: random column permutations
    for section in range(1, dv):
        perm = np.random.permutation(n)
        for i in range(rows_per_section):
            for j in range(dc):
                col = perm[i * dc + j]
                H[section * rows_per_section + i, col] = 1

    print(f"LDPC({n},{n-m}): rate={rate:.3f}, "
          f"dv={dv}, dc={dc}, density={dv/m:.4f}")
    return csr_matrix(H)

# Example: (3,6)-regular LDPC code, rate 1/2
H = gallager_ldpc(n=1200, dv=3, dc=6)
print(f"H shape: {H.shape}, nnz: {H.nnz}, "
      f"density: {H.nnz/(H.shape[0]*H.shape[1]):.4f}")

Encoding LDPC Codes

Belief Propagation Decoding

Sum-Product Algorithm: Step by Step

def bp_decode(H, llr_channel, max_iter=50):
    m, n = H.shape
    # Messages: variable-to-check and check-to-variable
    v2c = np.zeros((m, n))  # only nonzero where H[i][j]=1
    c2v = np.zeros((m, n))

    # Initialize v2c messages with channel LLRs
    for i, j in zip(*H.nonzero()):
        v2c[i, j] = llr_channel[j]

    for iteration in range(max_iter):
        # Check node update (tanh rule)
        for i in range(m):
            vn_indices = H[i].nonzero()[1]
            for j in vn_indices:
                product = 1.0
                for j2 in vn_indices:
                    if j2 != j:
                        product *= np.tanh(v2c[i, j2] / 2.0)
                c2v[i, j] = 2.0 * np.arctanh(np.clip(product, -0.9999, 0.9999))

        # Variable node update
        total_llr = llr_channel.copy()
        for j in range(n):
            cn_indices = H[:, j].nonzero()[0]
            total_llr[j] = llr_channel[j] + sum(c2v[i, j] for i in cn_indices)
            for i in cn_indices:
                v2c[i, j] = total_llr[j] - c2v[i, j]

        # Hard decision and syndrome check
        decoded = (total_llr < 0).astype(int)
        if np.all((H @ decoded) % 2 == 0):
            return decoded, iteration + 1
    return decoded, max_iter

Min-Sum Algorithm

Message Passing: A Visual Walk-Through

Density Evolution & Threshold Analysis

Capacity-Approaching Performance

LDPC in Wi-Fi Standards

LDPC in 5G NR

LDPC in DVB-S2 / DVB-S2X

LDPC in 10GBase-T Ethernet

Quasi-Cyclic LDPC for Hardware

Girth, Cycles, and Trapping Sets

QC-LDPC Construction in Python

import numpy as np

def build_qc_ldpc(base_matrix, Z):
    """
    Construct a QC-LDPC parity check matrix from a base matrix.

    base_matrix: 2D array where entry a_ij is a shift value
                 (-1 means zero block)
    Z: lifting factor (circulant block size)
    """
    mb, nb = base_matrix.shape
    H = np.zeros((mb * Z, nb * Z), dtype=int)

    for i in range(mb):
        for j in range(nb):
            shift = base_matrix[i, j]
            if shift >= 0:
                # Create Z x Z identity matrix shifted by 'shift'
                block = np.roll(np.eye(Z, dtype=int), shift, axis=1)
                H[i*Z:(i+1)*Z, j*Z:(j+1)*Z] = block

    return H

# Example: Simple rate-1/2 QC-LDPC
# Base matrix (3 x 6, rate = 1 - 3/6 = 1/2)
base = np.array([
    [ 0,  1,  3, -1,  2, -1],
    [-1,  0,  2,  1, -1,  3],
    [ 2, -1, -1,  3,  0,  1]
])

Z = 8  # Lifting factor
H = build_qc_ldpc(base, Z)
print(f"QC-LDPC H: {H.shape[0]} x {H.shape[1]}")
print(f"Rate: {1 - H.shape[0]/H.shape[1]:.3f}")
print(f"Column weights: {H.sum(axis=0)[:Z]}")
print(f"Row weights: {H.sum(axis=1)[:Z]}")
print(f"Density: {H.sum() / H.size:.4f}")

LDPC in the Coding Landscape

LDPC Codes: Summary