Tanner圖

Tanner圖發展背景

低密度校驗(Low Density Parity Check, LDPC)碼是一種基於稀疏矩陣的奇偶校驗碼。Gallager 於1962年首先發現了這種碼，故又稱Gallager碼。由於當時的計算機處理能力與相關理論的薄弱，這種優秀的碼並沒有在科學界引起足夠的重視。

1981年，Tanner提出了用圖模型來描述碼字的概念，從而將LDPC碼的校驗矩陣對應到被成為Tanner圖的雙向二部圖上，採用Tanner 圖構造的LDPC碼，通過並行解碼可以顯著地降低解碼複雜度。

1993年Turbo碼的問世與成功使Mackay、Neal、Spielman和Sipser等 “又重新提出了”LDPC碼。Mackay和Neal利用隨機構造的Tanner圖研究了LDPC碼的性能，發現採用和積解碼算法的正則LDPC碼具有和Turbo碼相似的解碼性能，在長碼時甚至超過了Turbo碼。Spielman和Sipser提出了基於二部擴展圖的擴展碼。在對擴展碼的研究中，他們證明了一個隨機構造的Tanner圖以很大的機率為好的擴展圖，而由好的擴展圖構造的線性糾錯碼是漸進好碼，從而證明了採用隨機Tanner圖構造的LDPC碼以很大機率是漸進好碼。

Tanner圖簡介

Tanner圖是由Mr Tanner在1981在論文中提出來的，是研究低密度校驗碼的重要工具。

Tanner圖表示的是 LDPC 的校驗矩陣。Tanner圖中的循環是由圖中的一群相互連線在一起的頂點所組成的。循環以這群頂點中的一個同時作為起點和終點，且只經過每個頂點一次。循環的長度定義為它所包含的連線的數量；而圖形的圍長，也成為圖形的尺寸，定義為圖中最小的循環長度。

Tanner圖包含兩類頂點： n個碼字比特頂點（稱為比特頂點），分別與校驗矩陣的各列對應； m個校驗方程頂點（稱為校驗節點），分別與校驗矩陣的各行對應。校驗矩陣的每行表示一個校驗方程，每列代表一個碼字比特。如果一個碼字比特包含在相應的校驗方程中，那么就用一條連線將所涉及的比特節點和校驗節點連起來，所以Tanner圖中的連線數與校驗矩陣中的1的個數相同。比特節點用圓形節點表示，校驗節點用方形節點表示。