低密度パリティ検査符号(LDPC)
- 提唱者
- Robert Gallager
- 年
- 1962
- 種類
- linear error-correcting code
- 系統
- Coding theory
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
ロバート・ギャラガーによって1962年に考案され、1990年代にマッケイによって再発見されたLDPC符号は、疎なパリティ検査行列によって定義される線形誤り訂正符号である。反復的な信念伝播復号により、シャノン限界から0.4 dB以内の性能を達成し、現代の無線通信(WiFi-6、5G NR、デジタルビデオ放送)の標準となっている。ターボ符号とは異なり、LDPC符号はより洗練されたグラフ理論的構造と、より成熟した理論的解析を持つ。
手法の背後にある直感
標準的な線形符号は密なパリティ検査行列を使用するため、復号は計算集約的になる。LDPC符号はこの逆を行う。パリティ検査行列は疎(ほとんどのエントリはゼロ)であり、各パリティ検査はわずかなビットしか関与しない。受信側では、変数ノードが送信ビットを表し、チェックノードがパリティ制約を表す二部グラフが構築される。復号は、このグラフ上での反復的なメッセージ伝播となる。各変数ノードは隣接ノードから情報を収集し、ビット値に関する信念を更新し、洗練された推定値を送り返す。疎性により、高速な収束とシャノン限界に近い性能が保証される。
歴史学
ギャラガーは1962年にLDPC符号を発明したが、理論は実用的な実装に遅れをとっていた。1995年にマッケイが再発見し、シミュレーションを通じてシャノン限界に近い性能を示した。2000年代には、効率的な符号化、復号、グラフ構築アルゴリズムが開発された。LDPC符号は、より優れた性能とクリーンな構造のため、新しいシステムではターボ符号よりも普及し、WiFi-6 (802.11ax, 2021) および5G NR標準 (2018) で採用された。
使うべき場面
LDPC符号は、より優れた性能とシンプルなアーキテクチャのため、現代のシステムではターボ符号よりも好まれる。広いSNR範囲(閾値クリフなし)でLDPCを使用する。低SNRから高SNRまでうまく機能する。LDPCはWiFi-6、衛星、5G NRの標準である。レガシー互換性でターボ符号が必要な場合以外は、LDPCを避ける必要はない。LDPCは、符号構造が分離可能であるため、非常に短いパケット(>30ビット)にも適している。
限界と注意点
- 非常に長い符号(>10kビット)では、グラフ構築と行列ストレージが複雑になる
- 性能は小規模なグラフ構造(周長、吸収集合)に敏感であり、慎重な設計が必要
- 信念伝播はループ状グラフを仮定するが、グラフにはサイクルが存在し、最適解への収束は保証されない
- 復号遅延(反復回数)はSNRに対して対数的に増加する。一部の古典的符号のようなゼロ遅延ではない
- メッセージの量子化(固定小数点ハードウェア)が性能に影響を与える。慎重なビット割り当てが必要
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- シャノン限界から0.4 dB以内(ターボ符号よりわずかに優れる)の性能
- ターボ符号よりもシンプルなグラフ理論的構造、よりクリーンな理論的解析
- 反復復号は、ターボ符号のようなクリフ状の閾値挙動を回避する
- グラフ構築による柔軟な符号設計、特定のアプリケーションへの適合が容易
- 効率的な並列復号ハードウェア、メッセージ伝播はVLSI/GPU実装に適している
- 長符号語と中程度の短さの符号語の両方にうまく機能する
応用
- WiFi-6 (802.11ax): LDPCが信頼性の高いデータ配信を提供する、高スループット無線ローカルエリアネットワーク
- 5G NR: 4Gのターボ符号に代わり、データチャネルと制御チャネルの両方のチャネル符号化
- 衛星通信: デジタルビデオ放送 (DVB-S2) および深宇宙ミッションで長符号語LDPCを使用
- 電力線通信 (PLC): ノイズの多い電力線網での堅牢なデータ伝送
- フラッシュメモリシステム: 頻繁なリフレッシュによる摩耗なしのNANDフラッシュストレージの誤り訂正
使い方
使い方
情報ビットは疎なパリティ検査行列Hを用いて符号化される。符号化ビットは、cを符号語とすると、H*c = 0 (mod 2) の解である。
パリティ検査行列Hは、疎(例えば、各行/列が定数で低重み3-5)になるように構造化されている。この構造は効率的な符号化に利用される。
符号化ビットはノイズのあるチャネルを介して送信され、受信ビットはソフト値(尤度比または対数尤度比)となる。
二部グラフが構築される。左側のノード=変数ノード(ビット)、右側のノード=チェックノード(パリティ方程式)。エッジは、変数をそれらが現れるチェックに接続する。
反復信念伝播:変数ノードはチェックノードからのメッセージを集約し、ビット推定値を更新し、洗練されたメッセージを送り返す。反復後、ハード判定が行われる。パリティ検査が満たされれば、復号は成功である。
よくある落とし穴
- 短いサイクルを持つ設計不良な疎グラフの使用。短いサイクルは信念伝播の振動を引き起こす
- 収束を超えた過剰な反復。改善なしに無駄な反復は電力を浪費する
- 最小和復号が和積復号と同等であると仮定すること。近似は、特に低SNRで性能低下を招く
- 有限長効果の無視。漸近解析用に設計されたグラフは、短いパケットでは性能が低下する可能性がある
- ハードウェア実装における量子化の考慮不足。浮動小数点シミュレーションと固定小数点現実の違い
よくある質問
一般的な線形符号と比較して、LDPC復号はなぜそれほど効率的なのですか?
パリティ検査行列の疎性により、各ビットはわずか数個のパリティ検査にしか関与しない。復号時、二部グラフ上のメッセージ伝播は、符号長ではなく、エッジ数に対して線形である。密な符号の場合、復号には符号長に対して3乗の行列逆算が必要になる。疎性により、復号は準線形となり、長符号に対して実用的になる。
吸収集合とは何ですか?なぜ重要ですか?
吸収集合は、信念伝播復号をトラップし、正しい解への収束を妨げる可能性のあるグラフの小さな部分集合である。これらは、エラーフロア(低SNRでのBERの非指数的減少)の主な原因である。符号設計者は、慎重なグラフ構築によって短い吸収集合を回避する。分析ツール(例:停止集合分析)は、問題のある構造を特定する。
LDPC符号は極性符号(Polar codes)と比較してどうですか?
どちらもシャノン限界に近い性能を達成する。極性符号は再帰構造を持ち、無限符号長での逐次消去復号下で証明可能な最適性を持つ。LDPC符号はより柔軟で、経験的には有限長性能が優れている。5G NRは、制御チャネル(短いパケット)に極性符号を、データチャネル(長いパケット)にLDPCを使用し、それぞれの符号の強みを活かしている。
LDPC符号において、グラフの周長(girth)はなぜ重要ですか?
周長は、二部グラフにおける最短サイクルの長さである。短いサイクル(周長 < 6)は、信念伝播が相関した情報を使用する原因となり(メッセージがループバックする)、性能を低下させる。高周長符号(周長 ≥ 6)は、相関をより良く断ち切る。符号はしばしば、疎性制約の下で周長を最大化するように設計される。
関連する手法
参考文献
Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.
DOI 文献を開くコピーしました。Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.
DOI 文献を開くコピーしました。