疎グラフ符号

疎グラフ符号(そぐらふふごう、Sparse graph code) は、疎グラフで表現される符号のことである。

任意の線形符号はグラフとして表現され、送信されたビット列を表現するセットと送信されたビット列が満たさなければならない制約を表現する別のセットの2つの節のセットを有する。 最新段階の正統的な誤り訂正符号は疎グラフを基にしており、シャノン限界に迫ることが成し遂げられている。 典型的な疎グラフ符号にはGallagerの低密度パリティ検査符号がある。

外部リンク

• The on-line textbook: Information Theory, Inference, and Learning Algorithms en:David J.C. MacKayの手による。Chapters 47-50で疎グラフ符号を議論する。
• Encyclopedia of Sparse Graph Codes