Web Simulation 

  

 

 

 

LDPC Tanner Graph Tutorial 

A Tanner graph is the bipartite graph form of an LDPC parity-check matrix H. Columns become variable nodes representing codeword bits. Rows become check nodes representing parity equations. A 1 in H(i,j) becomes an edge between check node ci and variable node vj.

This page focuses on visualization and interaction. The same LDPC object is shown in three synchronized views: the parity-check matrix, the Tanner graph, and the syndrome/message-passing readout. Changing any matrix cell immediately creates or removes an edge, and flipping a bit immediately changes the check-node status.

Background: for the broader LDPC theory, refer to this note.

Sections

Mathematical foundation

1. Matrix to graph mapping

For an m × n parity-check matrix H, create n variable nodes v0 ... vn-1 and m check nodes c0 ... cm-1. If H(i,j) = 1, draw an edge between ci and vj; if H(i,j) = 0, there is no edge. Because LDPC matrices are sparse, every node connects to only a small number of neighbors.

2. Parity-check meaning

Each check node represents one XOR equation: for row i, the connected variable bits must satisfy Hi cT = 0. A check node is ok when the XOR of its connected bits is even, and bad when it is odd. The full syndrome is:

z = H cT mod 2

The codeword is valid only when z is the all-zero vector.

Worked example (default Regular small LDPC preset). H has 4 rows and 8 columns, so c = [v0 v1 v2 v3 v4 v5 v6 v7] and z = [z0 z1 z2 z3]T. If row c0 = [1 1 0 0 1 0 0 0], the 1s select v0, v1, v4, so c0 = v0 XOR v1 XOR v4.

With c = [1 0 0 1 1 0 1 0]: v0=1, v1=0, v4=1, so c0 = 1 XOR 0 XOR 1 = 0 → ok. Flip v0 to 0 (c = [0 0 0 1 1 0 1 0]): c0 = 0 XOR 0 XOR 1 = 1 → bad. Since c3 is also connected to v0, it fails too, giving syndrome z = [1 0 0 1]T.

So c0 and c3 fail while c1 and c2 pass. The suspicious bit is the variable node shared by the failed checks — here, v0.

3. Message-passing mechanism

LDPC decoding uses local messages along Tanner graph edges. Variable nodes start with channel evidence, often represented as a log-likelihood ratio (LLR). A positive LLR favors bit 0, and a negative LLR favors bit 1. Variable nodes send reliability messages to check nodes. Check nodes send parity-based opinions back. After several iterations, variable nodes combine the channel evidence and incoming check messages to make hard decisions.

Edge-message sign in this simulator. The yellow number on each Tanner graph edge is a reliability message whose sign follows the usual LLR convention:

positive message ⇒ favors bit 0
negative message ⇒ favors bit 1

At the first variable-to-check stage, each variable node sends its channel LLR to every connected check node. If a bit has LLR magnitude 4, then v = 0 ⇒ +4.0 and v = 1 ⇒ −4.0.

The per-bit LLR slider and input next to each variable node specify the reliability for that specific received bit. In a real receiver, the LDPC decoder normally receives an LLR vector:

LLR = [LLR0 LLR1 LLR2 ... LLRn-1]

where LLRi belongs to the specific coded bit vi. Therefore a code with 8 variable nodes has 8 input LLR values. Positive LLRi means vi is more likely 0, negative LLRi means vi is more likely 1, and the magnitude indicates confidence.

For the default received/estimated vector:

c = [1 0 0 1 1 0 1 0]

the initial variable-to-check signs are:

v0=-4.0, v1=+4.0, v2=+4.0, v3=-4.0, v4=-4.0, v5=+4.0, v6=-4.0, v7=+4.0

During the check-to-variable stage, the check node sends a parity opinion back to one target variable. The sign is determined from all the other connected variable messages:

even number of negative incoming messages ⇒ positive output
odd number of negative incoming messages ⇒ negative output

Equivalently, the check-node output sign is the product of the signs from the other connected variable messages. A positive output suggests the target variable should be 0; a negative output suggests 1. The simulator uses a simplified min-sum magnitude: the output magnitude is the weakest reliability among the other connected messages.

4. Why the graph matters

The Tanner graph makes the LDPC mechanism visible: errors disturb only nearby checks first, messages travel only along existing edges, and cycles can cause messages to return to the same variables after a few iterations. This is why matrix sparsity and graph structure are central to LDPC performance.

Simulation

The interactive simulator is below. Use the controls to explore the concepts described above.

H matrix (click cell to toggle edge)

Received bits and per-bit LLR

Tanner graph (click variable/check, hover edge)

Event log

Visual convention: circles are variable nodes, squares are check nodes, yellow edge labels are reliability messages, green checks pass, and red checks fail. A 1 in H is exactly one graph edge.

Usage instructions

  1. Preset: Select a small LDPC parity-check matrix. The graph and matrix are two views of the same H matrix.
  2. H matrix: Click any 0 or 1 cell. A 1 creates an edge between that row's check node and that column's variable node. A 0 removes the edge.
  3. Received bits and LLR: Click a bit button or a variable node to flip the received bit. Edit the number beside it to set that bit's LLR directly. Positive LLR favors 0; negative LLR favors 1.
  4. Step Fwd / Step Bwd / Run: Animate the decoding cycle: channel evidence, variable-to-check messages, check-to-variable messages, and hard decision with syndrome update. Step buttons stop the animation before stepping.
  5. Inject Error: Flip one random received bit and observe which checks fail. This is the easiest way to see how a local bit error becomes a graph pattern.

Parameters

  • Preset: Defines the initial H matrix and received bit vector.
  • Per-bit LLR: Individual LLR values represent the actual LLR vector used by the Tanner graph messages.
  • Animation: Controls the four-stage message-passing view.
  • Actions: Injects a bit error or reloads the selected preset.

Limitations

  • Tiny didactic codes. Presets are small (e.g. 4×8) so the bipartite graph stays readable. Real LDPC codes have thousands of nodes, and their decoding behavior (waterfall/error-floor) cannot be seen at this scale.
  • Simplified min-sum, illustrative magnitudes. Check-to-variable magnitudes use a simplified "weakest other message" rule. There is no scaling/offset min-sum correction or true sum-product (tanh) update, so the numeric reliabilities are pedagogical, not BER-accurate.
  • Sign-focused messages. The animation emphasizes message signs and a single magnitude; full LLR arithmetic, message damping, and a proper iteration schedule are abstracted away.
  • Cycles shown, not handled. The graph reveals short cycles, but the demo does not quantify how girth degrades convergence, nor does it implement layered/flooding schedule differences.
  • No channel model. LLRs are entered by hand rather than derived from a modulation + AWGN channel, so the link between SNR and reliability is not demonstrated.
  • Fixed, editable H. You can toggle H cells freely, which may produce matrices that are not valid/sparse LDPC codes; the tool does not check rank, rate, or degree distribution.