Skip to content

Tanner Graphs and Code Structure

Prerequisites And Diagnostic Checks

You can treat this chapter as covered if you can:

  • turn a parity-check matrix into a bipartite graph
  • identify variable nodes and check nodes
  • read row weight and column weight as degrees
  • state the LDPC condition

Concrete Motivation

A matrix tells you which constraints exist. A Tanner graph tells you how those constraints are wired.

For Conjecture 3, this graph is the "guest" structure that must be emulated by physical hardware. It is the thing whose expansion creates demand.

Worked Example Before Abstraction

Take a small parity-check matrix. Put one variable node for each column and one check node for each row. Draw an edge when the matrix entry is 1.

Now row weight is check degree, and column weight is variable degree.

This is the first point where coding theory becomes geometry.

Formal Takeaway

A Tanner graph is a bipartite graph encoding the support pattern of a parity-check matrix.

A code is LDPC when the Tanner graph has bounded variable and check degrees independent of block length. This is the mathematical form of local check complexity.

The relevant Conjecture 3 family is not merely sparse. It is sparse and expanding. Sparsity makes the checks locally defined; expansion makes the code powerful; the same expansion makes the code hard to route on 2D hardware.

What This Does And Does Not Prove

The Tanner graph does not by itself prove good distance. It provides the graph where distance-related expansion hypotheses can be stated.

Active Recall

  • How do you draw a Tanner graph from H?
  • Why is bounded row weight a hardware-friendly condition?
  • Why is bounded degree not enough for good distance?

Next-Step Handoff

The next layer is expansion: what graph property turns sparse checks into strong codes, and why does it clash with grids?