Skip to content

Low-Density Parity-Check Code

A linear error-correcting block code specified by sparse parity-check constraints on its valid codewords.

Version
v1 · 2026-10-03 · History
Domain-specific #
13405
Aliases
Ldpc Code

Core Idea

A low-density parity-check (LDPC) code is a linear error-correcting block code defined through sparse parity constraints. For a binary code, a matrix \(H\) selects valid codewords \(c\) by \(Hc^\mathsf{T}=0\) over \(\mathrm{GF}(2)\). Rows are checks, columns are codeword positions, and nonzero entries describe their local variable–check graph. The sparse representation distinguishes this code family; belief-propagation decoding is a possible use, not part of the code's definition.[ref-6a3aa941c162][ref-4d6c6554b742]

Scope of Application

Gallager's random regular construction fixes low row and column weights when dimensions permit. Other LDPC matrices have irregular degrees or deliberately structured base graphs. 3GPP New Radio specifies a lifted base-graph LDPC construction for wireless channel coding, while flash-memory research studies LDPC-protected blocks with soft information from multiple cell reads. Those settings share sparse parity-check codewords but not one physical channel, decoder, or error rate.[ref-6a3aa941c162][ref-4d6c6554b742][ref-ce76077962eb][ref-e8fa3359a466]

Clarity

The valid-word set and a sparse parity-check representation must both be identified. An unrelated sparse matrix, a graph without parity equations, a decoder alone, or a generic dense linear code is insufficient. A dense matrix formed by row operations on a known sparse \(H\) may still describe the same LDPC code; not every equivalent representation must look sparse. The code dimension is \(n-\operatorname{rank}(H)\), so dependent check rows do not each reduce the rate.[^ref-6a3aa941c162]

Manages Complexity

Sparse checks describe a large valid-word set through local equations rather than enumerating every codeword. The same incidence relation lets implementations organize inference around variable–check neighborhoods. But low graph density alone does not ensure easy decoding or near-capacity behavior: matrix design, channel, decoder, blocklength, and observation quality all matter.[ref-6a3aa941c162][ref-4d6c6554b742]

Abstract Reasoning

Each binary row of \(H\) requires an even sum of its participating codeword bits. The intersection of those row constraints is the linear code. Holding \(H\) fixed while changing the decoder or replacing a wireless receiver with a storage-read model preserves code identity; removing evidence of a sparse parity-check representation removes the LDPC classification. Regular and irregular degree patterns are variants, not competing definitions.[ref-6a3aa941c162][ref-4d6c6554b742]

Knowledge Transfer

The transferable abstraction is a codeword set governed by local sparse parity checks. Wireless standards transfer it through specified base graphs and lifting; flash systems transfer it to stored blocks whose read errors require correction. Receiver likelihoods, cell-voltage quantization, and iteration budgets do not transfer with the code. Nor does success in one channel prove a universal performance guarantee.[ref-ce76077962eb][ref-e8fa3359a466][^ref-6a3aa941c162]

[^ref-6a3aa941c162]: David J. C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices”, IEEE Transactions on Information Theory 45(2) (1999), pp. 399–431, especially §§I.B–I.C and II–III, directly inspected. [^ref-4d6c6554b742]: GUAVA project, reference manual §5.8, “Low-Density Parity-Check Codes”, directly inspected for regular/irregular variants. [^ref-ce76077962eb]: 3GPP, TS 38.212 V16.11.0, NR; Multiplexing and channel coding (ETSI, April 2023), §5.3.2 and tables 5.3.2-1–2, directly inspected. [^ref-e8fa3359a466]: Jiadong Wang, Thomas Courtade, Hari Shankar and Richard D. Wesel, “Soft Information for LDPC Decoding in Flash: Mutual-Information Optimized Quantization”, IEEE GLOBECOM (2011), abstract and §§I–II, directly inspected.

Neighborhood in Abstraction Space

Low-Density Parity-Check Code sits in a moderately populated region (47th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Storage & Lookup Data Structures (21 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08