LDPC — Low-Density Parity-Check Code

What is it?

LDPC codes are linear block codes with a sparse parity-check matrix (most entries are 0). This sparsity enables a powerful decoding algorithm: iterative message passing on a bipartite graph called a Tanner graph.

Unlike Hamming codes (which decode in one step via syndrome lookup), LDPC decodes iteratively — variable nodes and check nodes exchange messages until they converge on a valid codeword. This makes LDPC codes approach the Shannon limit (the theoretical maximum channel capacity).

LDPC codes were invented by Robert Gallager in his 1963 MIT PhD thesis, but were forgotten for 30 years because computers weren't powerful enough to decode them. Rediscovered in the 1990s, they now power most modern digital communication.

Concrete Example: (10,5) Code

Our puzzle uses a small (10,5) regular LDPC code: 5 data bits + 5 parity bits. Each check node connects to 4 variable nodes; each variable node connects to 2 check nodes.

H matrix (5 checks × 10 variables):
    1 1 0 1 0 1 0 0 0 0   # check 0: v0⊕v1⊕v3⊕v5 = 0
    0 1 1 0 1 0 1 0 0 0   # check 1: v1⊕v2⊕v4⊕v6 = 0
    0 0 1 1 0 1 0 1 0 0   # check 2: v2⊕v3⊕v5⊕v7 = 0
    0 0 0 0 1 0 1 1 1 0   # check 3: v4⊕v6⊕v7⊕v8 = 0
    1 0 0 0 0 0 0 1 0 1   # check 4: v0⊕v7⊕v9 = 0

The Tanner graph has variable nodes (v0-v9, circles) connected to check nodes (c0-c4, squares) where H has a 1. Decoding:

1. Start with the noisy codeword as variable nodes' initial values
2. Each check node computes whether its parity equation is satisfied
3. Each variable node counts how many connected checks are violated
4. Flip any variable bit where > half its checks are violated
5. Repeat until all checks pass or max iterations reached

How It Works

1. Encoding: split message into 5-bit chunks. Compute parity bits so that H·c^T = 0 using Gaussian elimination over GF(2)
2. Channel: noise flips bits — the decoder receives a corrupted codeword
3. Bit-flipping: iteratively identify unreliable bits (those whose connected checks disagree most) and flip them
4. Convergence: when all check equations are satisfied, the codeword is valid — extract the data bits

Solving The Puzzle

def ldpc_decode(noisy, H, max_iters=50):
    n = len(noisy)
    m = len(H)
    for _ in range(max_iters):
        # Compute check node values
        checks = []
        for r in range(m):
            val = 0
            for c in range(n):
                if H[r][c]:
                    val ^= noisy[c]
            checks.append(val == 0)  # True if satisfied
        
        if all(checks):
            break  # converged
        
        # Flip variable nodes with > threshold violated checks
        threshold = 1  # flip if > 1 violated check connected
        for c in range(n):
            violated = 0
            total = 0
            for r in range(m):
                if H[r][c]:
                    total += 1
                    if not checks[r]:
                        violated += 1
            if violated > total // 2:
                noisy[c] ^= 1
    
    return noisy[:k]  # first k bits = data

Difficulty Table

Real-World Applications

• 5G NR: LDPC codes are the channel coding standard for 5G data channels
• WiFi 6 (802.11ax): Uses LDPC codes for reliable high-throughput transmission
• DVB-S2/DVB-T2: Satellite and terrestrial digital TV standards use LDPC
• NASA: Deep space missions adopted LDPC for near-Shannon-limit performance
• 10GBASE-T Ethernet: LDPC codes enable 10 Gbps over twisted pair copper