低密度パリティ検査符号
低密度パリティ検査符号(ていみつどぱりてぃけんさふごう、英語: 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によって初めて設計された。 疎グラフ符号も参照のこと。
この節の加筆が望まれています。 |
参照編集
人物編集
理論編集
応用編集
文献例編集
- 和田山 正:「誤り訂正技術の基礎」、森北出版、ISBN 978-4627817319 (2010/7/6)。※ 第13章、第14章。
- 萩原 学:「符号理論: デジタルコミュニケーションにおける数学」、日本評論社、ISBN 978-4535786646(2012年8月10日)。※ 第9章。
- 萩原 学:「進化する符号理論」、日本評論社、ISBN 978-4535787971 (2016年9月9日)。※ 第6章。
外部リンク編集
- The on-line textbook: Information Theory, Inference, and Learning Algorithms, by en:David J.C. MacKay, discusses LDPC codes in Chapter 47.
さまざまな場面でLDPC符号のエンコード、デコード、シミュレートが利用できる。
- The Error Correcting Codes (ECC) Page
- LDPC Codes in Python and C
- tutorial on LDPC + source code
- www.turbocoding.be Here you can find an online LDPC coding program
- Software in C for LDPC codes (by R. Neal)
- LDPC AL-FEC codec in C++