低密度パリティ検査符号
LDPC符号は送信したい0または1の情報列にパリティ検査行列:Hを掛け合わせる事で求められる。例えば、簡単にするために以下のように3行6列の小さい検査行列Hを考える:
H = ( 1 1 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 ) {\displaystyle \mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}}
LDPC符号は偶数パリティ条件を満たすように作られる。例えば上記行列Hの場合、行方向に1がある箇所に着目し:
x1 + x2 + x3 + x4 = 0
x3 + x4 + x6 = 0
x1 + x4 + x5 = 0
を満たすようにx1~x6の符号を作る。ここで+記号は排他的論理和である。この検査行列の例で、x1=1, x2=0, x3=1の情報列を送信したい場合、その偶数パリティー条件を満たすようにx4=0, x5=1, x6=1と計算される。{1,0,1,0,1,1}が最終的に送信される符号となる。LDPCは復号時の計算を簡単にするため、このパリティ検査行列として疎行列(1の数が少ない、疎)を用いる。これらの符号は1962年にGallagerによって初めて設計された。
低密度パリティ検査符号(ていみつどパリティけんさふごう、英語: low-density parity-check code、LDPC code)は、誤り訂正符号の1つで、ノイズのある通信チャンネルを通してメッセージを通信する手法のひとつである。
LDPCは、情報伝送レートの理論上の上限値であるシャノン限界に極めて近いレートを達成した最初の符号であった。 1963年に開発されたときは実装が実用的ではなかったので、LDPC符号は忘れ去られてしまった。 その後50年あまりにわたる符号理論の歴史のなかで様々な誤り訂正符号が提案されてきたが、 LDPCは今日においても最も効率的な符号であり続けている。
情報技術が爆発的に成長し、高効率な伝送符号の開発に商業的関心が高まっている。 LDPC符号の実装はターボ符号などに比べて遅れていたが、ソフトウェア特許による妨害のないことがLDPCへの興味をひきつけた。2003年には、6つのターボ符号を破り、デジタルテレビの衛星通信の標準となった。
1960年代にMITの博士論文内でLDPCのコンセプトを打ち出したRobert G. Gallagerをたたえて、Gallager符号としても知られる。