低密度パリティ検査符号のソースを表示

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

<!--LDPCだけでなくその他の誤り訂正符号も完全な情報伝送を保証することはできないが、情報を失う確率は任意に小さくできなければならない。-->
LDPCは、情報伝送レートの理論上の上限値である[[シャノン＝ハートレーの定理|シャノン限界]]に極めて近いレートを達成した最初の符号であった。
[[1963年]]に開発されたときは[[実装]]が実用的ではなかったので、LDPC符号は忘れ去られてしまった。
その後50年あまりにわたる[[符号理論]]の歴史のなかで様々な誤り訂正符号が提案されてきたが、
LDPCは今日においても最も効率的な符号であり続けている。
<!--3分の1の効果をもつものを作り出すことに失敗した[[情報理論]]の30年以上を経てもLDPCは残り、
開発されたときから今日（2006年）まで、理論上もっとも効率的である。-->
<!--The next 30 or so years of [[information theory]] failed to produce anything one-third as effective and LDPC remains, in theory, the most effective developed to date (2006).  -->

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

1960年代に[[マサチューセッツ工科大学|MIT]]の博士論文内でLDPCのコンセプトを打ち出したRobert G. Gallagerをたたえて、Gallager符号としても知られる。

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

:<math>
\mathbf{H} = 
\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 0 \\
\end{pmatrix}
</math>

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によって初めて設計された。

==復号==
LDPC符号を復号する方法として、対数尤度比(log-likelihood ratio: [[尤度関数|LLR]])を使った繰り返し復号の概要を述べる。詳しい方法は文献を参照されたい。
LLRは「送信信号x=1の時に受信信号yを観測する確率:P(y|x=1)」と「送信信号x=0の時にyを観測する確率:P(y|x=0)」の比を取り、さらに対数をとったものである。つまりLLRがプラスあるいはマイナスに大きくなるほど、正しく送信信号を当てれそうで、反対に0に近くなるほどあやふやになる推定の尤度の指標である。LDPCの復号は検査行列HをベースにLLRを徐々に高めていく繰り返しを伴うプロセスである。

===LLRの初期値===
まず、受信信号yをベースに受信時のLLR、受信LLRを求める。これはyに比例した値となり以降の繰り返し復号に使われる。

===行方向の計算===
次に検査行列の行（横）方向で1が立っている場所のみに着目し、受信LLRとは異なる新たなLLR、外部LLR（2次元の行列）を計算する。例えば、上記の検査行列Hで1行目に着目した時に、1,2,3,4列目に1が立っている。1行目1列の外部LLRは、自分自身（1列目）を除いたその他の列、2,3,4列目の受信LLRをベースに計算される。その計算式は簡単に言えば2項の掛け算であり、1項目は1もしくは-1の離散値、2項目は正の連続値でいずれも受信LLRの関数である。1項目は検査行列の偶数パリティ条件を計算してると捉えても良い。

===列方向の計算===
次に検査行列の列（縦）方向で1が立っている場所に着目し、事前LLRを計算する。事前LLRは次の繰り返しで外部LLRを計算する時に受信LLRと共に使われる。（外部LLR同様に）自分自身を除き、列方向の外部LLRの総和から求められる。

===送信信号の推定===
外部LLRをベースに送信信号を推定する。例えば、LLRが正の場合1、負の場合0といった風である。この推定の結果が、検査行列と辻褄が合う（推定した信号が全て偶数パリティー条件を満たす）場合、復号を終了する。そうでない場合、行方向の計算に戻るが、このとき外部LLRを受信LLRだけでなく事前LLRと足し合わせて計算する。これをループして計算する。ループの上限に達した時も復号を終了する。

== 文献例 ==
* 和田山 正：「誤り訂正技術の基礎」、森北出版、ISBN 978-4627817319 (2010/7/6)。※ 第13章、第14章。
* 萩原 学：「符号理論: デジタルコミュニケーションにおける数学」、日本評論社、ISBN 978-4535786646（2012年8月10日)。※ 第9章。
* 萩原 学：「進化する符号理論」、日本評論社、ISBN 978-4535787971 (2016年9月9日)。※ 第6章。

==関連項目==
===人物===
*{{仮リンク|ロバート・G・ギャラガー|en|Robert G. Gallager}}
*[[リチャード・ハミング]]
*[[クロード・シャノン]]

===理論===
*[[誤り検出訂正]]
*[[ハミング符号]]
*[[グラフ理論]]
*[[確率伝搬法]]{{enlink|Belief propagation}}

===応用===
*[[デジタルビデオブロードキャスティング]]
*[[WiMAX]]

== 外部リンク ==
* [http://satcom.jp/67/technologyreviewj.pdf 高速衛星通信に適した誤り訂正符号, 岡本英二]
* [http://www.inference.phy.cam.ac.uk/mackay/itila/ The on-line textbook: Information Theory, Inference, and Learning Algorithms], by [[:en:David J.C. MacKay]], discusses LDPC codes in Chapter 47.
* [http://www.eccpage.com/ The Error Correcting Codes (ECC) Page]
* [http://freshmeat.net/projects/pycodes/ LDPC Codes in Python and C]
* [https://web.archive.org/web/20051215055130/http://geilenkotten.homeunix.org/wikicoding/index.php/LDPC_codes tutorial on LDPC + source code]
* [http://www.turbocoding.be/ www.turbocoding.be] Here you can find an online LDPC coding program
* [http://www.cs.utoronto.ca/~radford/ldpc.software.html Software in C for LDPC codes] (by R. Neal)
* [http://planete-bcast.inrialpes.fr/ LDPC AL-FEC codec in C++]<!-- 
{{翻訳中}} -->

{{Computer-stub}}

{{デフォルトソート:ていみつとはりていけんさふこう}}
[[Category:誤り検出訂正]]