タナーグラフ

符号理論において、マイケル・タナーにちなんで名付けられたタナーグラフは、誤り訂正符号を指定する制約または方程式を記述するために使用される二部グラフです。符号理論では、タナーグラフは短いコードから長いコードを構築するために使用されます。エンコーダとデコーダの両方がこれらのグラフを広範に使用します。

^{タナーグラフは、マイケル・タナー[1]}によって、再帰的手法を用いて小さな誤り訂正符号からより大きな誤り訂正符号を作成する手段として提案されました。彼はエリアスの手法を積符号に一般化しました。

Tanner は、より大きなコードを構築するために使用されているコードの特定の特性に関係なく、これらのグラフから取得されるコードの下限について議論しました。

タナーグラフは、サブコードノードと数字ノードに分割されます。線形ブロックコードの場合、サブコードノードはパリティチェック行列H の行を表します。数字ノードは行列 H の列を表します。対応する行と列の交差点にゼロ以外のエントリが存在する場合、エッジがサブコードノードを数字ノードに接続します。

タナーは次の境界を証明した。

得られた線形コードのレートを、数字ノードの次数を、サブコードノードの次数をとする。各サブコードノードがレートr = k/nの線形コード(n,k)に関連付けられている場合、コードのレートは次の式で制限される。 ${\displaystyle R}$${\displaystyle m}$${\displaystyle n}$

${\displaystyle R\geq 1-(1-r)m\,}$

これらの再帰的手法の利点は、計算的に扱いやすいことです。タナーグラフのコーディングアルゴリズムは実際には非常に効率的ですが、漸近的に良いコードを許容しないことが知られているサイクルフリーグラフを除いて収束することが保証されていません。^[2]

Zemor のデコード アルゴリズムは、コード構築に対する再帰的な低複雑性のアプローチであり、Tanner グラフに基づいています。

• マイケル・タナーの原著論文
• マイケル・タナーのページ