LDPC Codes

Low Density Parity Check codes, commonly called LDPC codes, are a class of linear block error-correcting codes that achieve performance remarkably close to the theoretical Shannon limit. Originally proposed by Robert Gallager in 1962 and rediscovered in the 1990s, LDPC codes have become the backbone of modern communication standards including 5G, Wi-Fi 6, and DVB-S2.

Understanding LDPC codes is essential for GATE aspirants and students studying advanced digital communications, as these codes represent the state of the art in channel coding and are frequently referenced in questions on error control coding and channel capacity.

Core Concept Explanation

An LDPC code is defined entirely by its parity check matrix H, which is sparse, meaning the vast majority of entries are zeros. A valid codeword c satisfies H times c equals zero over GF(2). The sparsity of H is what gives LDPC codes their name and their power: it allows iterative decoding algorithms to work efficiently.

The graphical representation of an LDPC code is called a Tanner graph, a bipartite graph with two types of nodes. Variable nodes represent the bits of the codeword. Check nodes represent the parity check equations. An edge connects variable node i to check node j if and only if H[j][i] equals 1.

A regular LDPC code has every variable node with the same degree dv (column weight) and every check node with the same degree dc (row weight). An irregular LDPC code allows varying degrees, which enables even better performance by concentrating high-degree nodes where they help most in decoding.

The code rate of an LDPC code with parity check matrix H of size m x n is at least (n - m) / n, assuming all rows of H are linearly independent. For a regular (dv, dc) LDPC code, the rate is 1 - dv/dc.

Mathematical Expression

For a binary LDPC code, the n-bit codeword vector c must satisfy the matrix equation H multiplied by c equals 0 (mod 2). If H is an m x n matrix, there are m parity check equations. The minimum distance of the code is related to the girth (length of the shortest cycle) in the Tanner graph: longer girth leads to better distance properties and better decoding performance.

The belief propagation algorithm, also called the sum-product algorithm, is the standard iterative decoder for LDPC codes. Each variable node computes a log-likelihood ratio (LLR) based on the received channel value and messages from neighboring check nodes. Each check node updates messages to variable nodes based on the current variable node LLRs. This process repeats until all parity checks are satisfied or a maximum iteration count is reached.

The check node update rule in LLR domain is: LLR from check node j to variable node i equals 2 times arctanh of the product of tanh(LLR_k / 2) for all variable nodes k connected to j except i. The variable node update simply sums its channel LLR with all incoming check node messages.

Practical Understanding

LDPC codes are capacity-approaching codes. A well-designed LDPC code with iterative decoding can operate within 0.1 dB of the Shannon limit on an AWGN channel, which is extraordinary performance that turbo codes and classical algebraic codes cannot match at large block lengths.

The block length n of practical LDPC codes is typically large, ranging from a few hundred to tens of thousands of bits. Longer codes generally perform better but require more decoder complexity and latency. In 5G NR standards, LDPC codes are used for the data channel (PDSCH and PUSCH) with base graphs BG1 and BG2 covering a range of code rates and block lengths.

One important practical consideration is the error floor phenomenon. At high SNR, the bit error rate curve of some LDPC codes flattens instead of continuing to fall steeply. This is caused by trapping sets, small subgraphs in the Tanner graph where iterative decoding gets stuck. Good LDPC code design avoids short cycles and harmful trapping sets.

Given:
LDPC code rate R = 1/2, block length n = 1000 bits, dv = 3, dc = 6

Why this formula applies:
For a regular (dv, dc) LDPC code, code rate R = 1 - dv/dc

Formula:
R = 1 - dv / dc
m = n * (1 - R)  [approximate number of check nodes]

Substitution:
R = 1 - 3/6 = 1 - 0.5 = 0.5
m = 1000 * (1 - 0.5) = 1000 * 0.5 = 500

Calculation:
Code rate = 0.5 (confirms rate-1/2 code)
Number of check nodes m = 500
Number of variable nodes n = 1000
Total edges in Tanner graph = n * dv = 1000 * 3 = 3000
(Also = m * dc = 500 * 6 = 3000, consistent check)

Final Answer:
Rate = 0.5, m = 500 check nodes, 3000 edges in Tanner graph

Exam Tip: For a regular (dv, dc) LDPC code, always use R = 1 - dv/dc to find rate instantly. Also remember that the total edges in the Tanner graph equals both n times dv and m times dc simultaneously, giving a useful consistency check in numerical problems.

• LDPC codes are defined by a sparse parity check matrix H; sparsity enables efficient iterative decoding.
• The Tanner graph is a bipartite graph where edges correspond to 1s in H; short cycles degrade decoding performance.
• Belief propagation (sum-product algorithm) passes LLR messages between variable and check nodes iteratively until parity checks pass.
• Regular LDPC codes have uniform degree dv and dc; irregular codes with optimized degree distributions can approach Shannon capacity more closely.
• Error floors at high SNR are caused by trapping sets and are a key design challenge in practical LDPC systems.

Quick Revision

• LDPC codes: linear block codes with sparse H matrix; near-Shannon-limit performance via iterative decoding.
• Rate formula for regular (dv, dc) LDPC: R = 1 - dv/dc.
• Tanner graph: bipartite, variable nodes (circles) and check nodes (squares), edges = 1s in H.
• Decoding: belief propagation (sum-product); iterates until H times c = 0 or max iterations reached.
• Total edges = n times dv = m times dc (useful consistency check).
• Error floor phenomenon: BER curve flattening at high SNR due to trapping sets.
• Applications: 5G NR (BG1, BG2), Wi-Fi 6 (802.11ax), DVB-S2.