LDPC符号とは？原理・設計・実装・最新動向を徹底解説
エバープレイ編集部はじめに — LDPC符号の位置付け
低密度パリティ検査（LDPC: Low-Density Parity-Check）符号は、シャノン限界に極めて近い性能を示す誤り訂正符号の一群です。1962年にロバート・ギャラガー（R. Gallager）が提案した後、一時期注目が薄れていましたが、1990年代後半からの反復復号アルゴリズムと計算機性能の向上により再び脚光を浴び、通信規格や衛星放送、記憶媒体、5Gなど幅広い分野で採用されています。本稿では、LDPC符号の基礎から設計指針、デコーダの実装課題、最新の研究動向まで詳しく解説します。
LDPC符号の基本構造
LDPC符号は低密度のパリティ検査行列 H（多くのゼロと少数の1を持つ行列）で定義されます。符号長 n と情報長 k に対して H は (n-k)×n 行列で、符号語 x は Hx^T = 0 を満たします。H の「低密度」性により、効率的な反復アルゴリズム（メッセージ伝搬）が可能になります。
タナーグラフ（Tanner graph）と直感
H を二部グラフ（タナーグラフ）で表現すると、変数ノード（符号ビット）とチェックノード（パリティ検査）を辺で結びます。各辺は対応する H の 1 を示します。反復復号では、ノード間で対数尤度比（LLR）やメッセージをやり取りして誤りを訂正します。グラフのサイクル長（特に短いサイクル＝ギャップ）は性能に大きく影響します。
復号アルゴリズム
代表的な復号法は以下の通りです。
- 和積（sum-product）アルゴリズム（SPA）: ベルヌーイ確率やLLRを用いる最も情報理論的に正確な近似的手法。計算精度が高いが複雑度も大きい。
- 最小和（min-sum）アルゴリズム: SPA の近似で計算量を削減。補正係数（normalized/offset min-sum）を用いて性能劣化を補うことが多い。
- スケジューリング: フラッディング（同期）とレイヤード（逐次）方式。レイヤードは収束を早め、反復回数を減らせるため実装上有利。
- 早期終了と信頼度判定: 実系ではCRC併用やパリティ検査により早期停止を導入し平均処理量を低減する。
性能特性：ウォーターフォール領域とエラーフロア
LDPC符号性能は一般に2つの領域で説明されます。高BERから急速に落ちる"ウォーターフォール"領域では、設計次第でシャノン限界に非常に近づけます。一方で低BERの"エラーフロア"領域では、トラッピングセットや短いサイクルによる局所的な復号失敗が支配的になります。エラーフロア対策は短ブロック長や高信頼度要求の適用で重要になります。
設計手法：正則と不正則、プロトグラフ
LDPCには正則（variable/checkノードの次数が均一）と不正則（次数分布を設計するもの）があります。不正則設計は密度進化やEXITチャートを用いて最適化され、より良い閾値性能を得られます。また、プロトグラフやQC（巡回）LDPCは構造化されており、ハードウェア実装や効率的なエンコードに有利です。PEG（Progressive Edge Growth）アルゴリズムや代数的構成も短周期・高ゲイ（girth）を実現するために用いられます。
エンコード方法
LDPCのエンコードは直接的にはジェネレータ行列 G を使いますが、G を求める計算は高コストです。QC-LDPC や階層的構造を持つ符号では、循環行列を利用して線形複雑度に近いエンコードが可能になります。システマティック符号化により、情報ビットをそのまま出力に含めることでパケット構造やFECとの連携が容易になります。
ハードウェア実装の要点
実装ではメモリ帯域・パラレル度・量子化ビット幅が性能と資源のトレードオフになります。一般に4〜6ビットのLLR量子化が多くの用途で十分な性能を示します。並列度を高めるとスループットは上がりますが、配線・メモリ衝突や消費電力の問題が出ます。レイヤードスケジューリングや早期終了、メッセージ圧縮が実装上の工夫として有効です。
規格での採用例
- DVB-S2: 衛星放送で高性能なLDPC+BCH 連接符号が採用されています。
- IEEE 802.11n/ac/ax（Wi‑Fi）: LDPC をオプションでサポートし、高速通信で利用されます。
- 3GPP 5G NR: データチャネル（eMBBなど）に LDPC を採用。コントロール系には極性符号（Polar）が使われています。
最新動向と研究課題
近年は空間結合型LDPC（SC-LDPC）が"しきい値飽和"によりさらに良い性能を示すことが知られており、実装可能な形での最適化が進んでいます。また、短ブロック長での最適設計、エラーフロアの理論的解析と緩和、低消費電力デコーダのアーキテクチャ、新たな規格要求に合わせたQC/プロトグラフ設計などが活発に研究されています。さらに、機械学習を用いた復号アルゴリズムの改良や、複合チャネル（フェージングや非ガウス雑音）に対する堅牢化も注目分野です。
長所と短所のまとめ
- 長所: シャノン限界に近い性能、柔軟な設計（長さ・レート・構造）、並列実装による高スループット。
- 短所: 短ブロックでの性能劣化やエラーフロア問題、実装におけるメモリ・配線の複雑さ、最適設計の難しさ。
実践的な設計のポイント
規格対応や製品設計では、目標BER/FER、遅延・スループット、実装リソース、消費電力を同時に満たす必要があります。まずはプロトグラフやQC構造を用いて設計の自由度を担保し、密度進化やシミュレーションで閾値を評価、最後にハードウェア実装での量子化・スケジューリング・メモリ配置の最適化を行います。エラーフロア対策としては、短いサイクルの除去、サブグラフ解析、または高信頼度の再伝送制御を検討します。
まとめ
LDPC符号は理論的にも実用的にも極めて重要な誤り訂正技術であり、適切な設計と実装により高い信頼性とスループットを両立できます。シャノン限界に近い性能、規格での広範な採用、そして現在も進化を続ける研究領域として、通信・放送・記憶メディア分野での必須知識と言えるでしょう。
参考文献
- R. G. Gallager, "Low-Density Parity-Check Codes", 1962 (原著)
- T. Richardson and R. Urbanke, "Modern Coding Theory", Cambridge University Press
- T. Richardson, A. Shokrollahi, R. Urbanke, "Design of capacity-approaching irregular low-density parity-check codes", 2001
- ETSI EN 302 307 (DVB-S2 標準)
- 3GPP TS 38.212 (5G NR: Multiplexing and channel coding)
- Wikipedia: Low-density parity-check code (概説)
投稿者プロフィール
