Sparse Graph Code¶

An error-correcting code whose sparse graph defines local parity-check or redundant-symbol generation relations for recovery under a stated error or erasure model.

Version: v1 · 2026-10-07 · History
Domain-specific #: 14019
Domain group: Formal Sciences
Origin domain: Information Theory
Subdomain: Coding Theory → Information Theory
Aliases: Sparse-graph code

Core Idea¶

A sparse graph code is an error-correcting code whose sparse graph defines local coding relations. For Gallager low-density parity-check codes, edges link codeword bits to parity checks. In Luby and colleagues' erasure construction, edges link message bits to redundant check bits formed by XOR. Both use graph-local redundancy for recovery, but the graph and decoder do different jobs.[^{ref-6a3aa941c162][}ref-60ffc5e293db]

Sparse incidence can support cheap local operations. It does not guarantee that every decoder converges, runs in linear total time, or approaches channel capacity. Those claims require the construction, channel and decoding assumptions of a particular result.[^{ref-6a3aa941c162][}ref-60ffc5e293db]

Scope of Application¶

Use the term for a specified redundant error- or erasure-correcting code whose sparse graph actually defines its local parity or generation relations. MacKay reports Gallager-code experiments on noisy channels, including a Gaussian model. Luby and colleagues analyze a sparse irregular construction for known-position erasures. Neither cited study by itself documents a deployed wireless or broadcast system.[^{ref-6a3aa941c162][}ref-60ffc5e293db]

Clarity¶

In an LDPC Tanner graph, a check node expresses a parity condition on a valid codeword. In Luby's graph, a check bit is a generated XOR of neighboring message bits. Likewise, soft updates from noisy observations differ from peeling a known erasure when one missing neighbor remains. The same word “check” does not make the two graph relations identical.[^{ref-6a3aa941c162][}ref-60ffc5e293db]

Manages Complexity¶

The graph isolates local neighborhoods instead of requiring every symbol to interact directly with every other symbol. Sparse parity checks make iterative probability updates feasible in MacKay's studied case; Luby's known check bit can recover one erased neighbor by XOR, and that step can propagate. Graph degrees, cycles, channel observations and stopping configurations still govern a particular design's behavior.[^{ref-6a3aa941c162][}ref-60ffc5e293db]

Abstract Reasoning¶

Identify information symbols, added redundancy, the channel or erasure model, and the decoder. Then inspect what each graph edge means and whether those code-defining relations are sparse. If the graph is only a diagram of a dense rule, or if there is no defined recovery target, it does not establish this family. Change the corruption model and the decoder's claim must be checked again.[^{ref-6a3aa941c162][}ref-60ffc5e293db]

Knowledge Transfer¶

The family test transfers literally from Gallager parity-check codes to Luby's erasure-generation code: sparse local relations govern redundancy and enable a specified recovery process. The decoder and performance guarantees do not transfer unchanged. Outside error correction, a sparse computation graph is only an analogy. Prime Sparse Coding means few active representational units, a different kind of sparsity.[^{ref-6a3aa941c162][}ref-60ffc5e293db]

Example¶

MacKay's Gallager code. A very sparse parity-check matrix connects codeword bits and check constraints; MacKay tests sum-product decoding with noisy Gaussian-channel observations. Mapped roles: information/redundancy → binary source and codewords; sparse incidence → parity-check graph; coding relation → valid codewords satisfy checks; recovery → iterative probability updates for the studied channel. His optimal-decoding capacity-existence result is separate from practical-decoder experiments.[^ref-6a3aa941c162]

Luby and colleagues' erasure code. A sparse irregular bipartite graph links message bits and XOR check bits. A known check bit with exactly one unknown neighbor reveals that missing bit. Mapped roles: information/redundancy → message and check bits; sparse incidence → irregular bipartite graph; coding relation → neighborhood XOR; recovery → known-erasure peeling. Linear-time and near-optimal recovery claims belong to the specified construction and probabilistic analysis.[^ref-60ffc5e293db]

Relationships to Other Abstractions¶

Current abstraction Sparse Graph Code Domain-specific

Parents (1) — more general patterns this builds on

Sparse Graph Code is a kind of Error-Correcting Code Domain-specific

Every admitted sparse graph code is an error-correcting code with a sparse graph of local coding relations.

Hierarchy path (1) — routes to 1 parentless root

Sparse Graph Code → Error-Correcting Code → Encoding And Decoding → Transformation → Function (Mapping)

Neighborhood in Abstraction Space¶

Sparse Graph Code sits in a sparse region of the domain-specific corpus (95^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

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

Not to Be Confused With¶

A few active bits do not make a sparse graph error-correcting code. LDPC and Tornado are narrower neighboring code families. A parity-check graph and a generator/check-bit graph share sparse incidence but not identical edge semantics. The staged strict DAG parent is Error-Correcting Code, which is broader because it need not have sparse local graph relations.[^{ref-6a3aa941c162][}ref-60ffc5e293db]

References¶

[^ref-6a3aa941c162]: David J. C. MacKay, Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Transactions on Information Theory 45, no. 2 (1999), pp. 399–431. Original research paper via university-hosted copy; especially Abstract and Introduction pp. 399–400, sparse parity-check construction pp. 400–403, decoding pp. 407–409, and channel simulations pp. 414–419. Optimal-decoder existence and practical-decoder experiments are distinct claims. [^ref-60ffc5e293db]: Michael Luby, Michael Mitzenmacher, M. Amin Shokrollahi and Daniel A. Spielman, Efficient Erasure Correcting Codes, IEEE Transactions on Information Theory 47, no. 2 (2001), pp. 569–584. Original author-hosted research paper; especially §II-A and Fig. 1 pp. 570–571, §II-B erasure recovery, and §§III–IV degree-sequence and conditional performance analysis. The check-bit XOR graph is not an LDPC parity-check graph.