Tanner Graph

定义 Definition

Tanner graph（坦纳图）：一种用于表示线性分组码（尤其是 LDPC 码）的二分图。图中通常包含两类节点：变量节点（对应码字比特）和校验节点（对应奇偶校验约束）；边表示某个比特参与某个校验方程。它常用于理解与执行迭代译码算法（如置信传播/和积算法）。

发音 Pronunciation (IPA)

/tnr rf/

例句 Examples

A Tanner graph shows how bits connect to parity checks.
坦纳图展示了比特如何与奇偶校验约束相连接。

Using the Tanner graph of an LDPC code, the decoder iteratively passes messages between variable nodes and check nodes to estimate the transmitted codeword.
利用 LDPC 码的坦纳图，译码器在变量节点与校验节点之间迭代传递信息，以估计发送的码字。

词源 Etymology

该术语源自美国学者 Robert Michael Tanner 的工作；他在 20 世纪 80 年代提出用二分图来表示码的约束结构，这种图结构后来被广泛称为 Tanner graph。

相关词 Related Words

• Bipartite Graph
• Factor Graph
• Parity-Check Matrix
• LDPC Code
• Belief Propagation
• Sum-Product Algorithm
• Check Node
• Variable Node

文学与作品 Literary Works

• R. M. Tanner, A recursive approach to low complexity codes（1981）提出并使用坦纳图思想来描述码结构。
• David J. C. MacKay, Information Theory, Inference, and Learning Algorithms（2003）在 LDPC 码与迭代译码章节中频繁使用 Tanner graph。
• T. Richardson & R. Urbanke, Modern Coding Theory（2008）系统讲解 Tanner graph、稀疏图码与密度演化。
• F. R. Kschischang, B. J. Frey, H.-A. Loeliger, Factor Graphs and the Sum-Product Algorithm（2001）讨论与 Tanner graph 密切相关的因子图与和积算法。