低密度パリティ検査符号

低密度パリティ検査符号（ていみつどぱりてぃけんさふごう、英語: low-density parity-check code、LDPC code）は、誤り訂正符号の1つで、ノイズのある通信チャンネルを通してメッセージを通信する手法のひとつである。

LDPCは、情報伝送レートの理論上の上限値であるシャノン限界に極めて近いレートを達成した最初の符号であった。 1963年に開発されたときは実装が実用的ではなかったので、LDPC符号は忘れ去られてしまった。その後50年あまりにわたる符号理論の歴史のなかで様々な誤り訂正符号が提案されてきたが、 LDPCは今日においても最も効率的な符号であり続けている。

情報技術が爆発的に成長するのに伴い、高効率な情報伝送符号の開発に対する商業的関心も相応に高まっている、というのも、信号の品質から電池の寿命に至るあらゆるものが、符号の性質の影響を受けるからである。 LDPC符号の実装は重要なターボ符号などの符号に比べて遅れていたとはいえ、ソフトウェア特許による妨害のないことがほかの符号からLDPCへ興味をひきつけ、LDPC符号は高い効率のデータ伝送手法の開発マーケットにおいて標準に位置づけられる。 2003年には、6つのターボ符号を破り、デジタルテレビの衛星通信の標準となった。

LDPC符号は、1960年代にMITでの博士論文内でLDPCのコンセプトを打ち出したRobert G. Gallagerをたたえて、Gallager符号としても知られる。

機能編集

LDPCは線形符号であるが、パリティ検査行列として疎行列を用いる。この疎行列はランダムに生成される。理論的に最適な復号はNP完全だが、確率伝播法に基づく準最適な復号法があり、最適な復号に対するよい近似を与えている。これらの符号は、1962年にGallagerによって初めて設計された。疎グラフ符号も参照のこと。