LDPC符号 - waxwing_k @ ウィキ

LDPC符号とは，誤り訂正符号の一種である．

• LDPC符号は，非常に疎な検査行列により定義される線形符号である．
  • 疎な行列とは，行列内の非零要素の数が非常に少ない行列を指す．

• 歴史的な流れ
  • 1960年代にGallagerによって提案
  • 大数の法則に基づく情報理論的手法（ランダム符号）と，ベイズ的手法（グラフィカルモデル上での確立伝播アルゴリズム）の融合で生まれた．

LDPC符号の定義

正則LDPC符号を定義する

m行n列の（広義の）検査行列Hのどの列のハミング重みもwcであり，どの行のハミング重みもwrであるとする．
さらにwc<<mであるとき，検査行列Hにより定義される符号Cを正則LDPC符号と呼ぶ．

特徴

• LDPC符号とsum-product復号法により得られる復号特性がターボ符号の性能に匹敵
• ランダム性
• 低密度性
• 符号長が長いと，よりよい性能となる．
• 様々な符号長，符号化率の符号を容易に構成可な柔軟性
• エラーフロア現象がほとんど生じない
• 復号法
  • sum-product復号法
    • 時間計算量は符号長について線形時間
    • 並列アルゴリズムなので，並列分散型ハードウェア実装に向き

Gallagerによる構成法

• 検査行列をいくつかのブロックに分ける
• 第1サブブロックを決める
• 第2, 第3・・・サブブロックについては第1サブブロックの列置換したものを用いる
• 各行，各列の重みは均一になる
• このような検査行列をレギュラーLDPC符号という