Tanner Graphs

How Tanner graphs represent sparse parity-check matrices and why graph structure matters to iterative decoding.

A Tanner graph is a bipartite graph representation of a parity-check matrix. Variable nodes correspond to code symbols and check nodes correspond to parity constraints. An edge exists wherever the matrix has a non-zero entry.

Core idea

This graph view makes the sparse structure of LDPC codes intuitive and exposes the neighbourhoods through which iterative messages travel. Cycle length, node degree, local connectivity and repeated substructures can influence how quickly information becomes independent or reinforced. The graph is therefore closely connected to practical decoder behaviour.

Engineering relevance

Graph metrics are useful, but no single metric is enough. Two graphs with the same girth can have very different trapping-set or absorbing-set populations. Equivalent parity-check matrices can describe the same code while changing the Tanner graph and therefore the behaviour of a particular iterative decoder.

Key points

  • Variable nodes represent code symbols; check nodes represent parity equations.
  • Edges correspond directly to non-zero parity-check entries.
  • Short cycles can correlate iterative messages.
  • Equivalent matrix representations can create different Tanner graphs for the same code.
Public technical resource

This page explains established concepts and engineering principles. Proprietary JobMettle methods and internal ThinkQuick technology are not disclosed.