低密度パリティ検査符号

ウィキペディア

低密度パリティ検査符号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/11/27 19:11 UTC 版)

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

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

情報技術が爆発的に成長し、高効率な伝送符号の開発に商業的関心が高まっている。 LDPC符号の実装はターボ符号などに比べて遅れていたが、ソフトウェア特許による妨害のないことがLDPCへの興味をひきつけた。2003年には、6つのターボ符号を破り、デジタルテレビの衛星通信の標準となった。

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

符号化

LDPC符号は送信したい0または1の情報列にパリティ検査行列:Hを掛け合わせる事で求められる。例えば、簡単にするために以下のように3行6列の小さい検査行列Hを考える：

$\mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}$ この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。