Loading article…
低密度パリティチェック（LDPC）符号（ギャラガー符号とも呼ばれる）は、 1960年に初めて提案された誤り訂正符号の一種です。密接に関連するターボ符号とともに、1990年代後半から符号理論と情報理論において注目を集めています。現在、これらの符号は無線通信からフラッシュメモリストレージまで、幅広い用途で広く使用されています。ターボ符号とともに、従来の誤り訂正符号と比較して桁違いの性能向上を実現し、符号理論に革命をもたらしました。[ 1 ]
LDPC符号は、もともと1960年にロバート・G・ギャラガーによって考案されました。ギャラガーは、マサチューセッツ工科大学での博士論文[ 2 ]の中でこの符号を考案しました。[ 3 ] [ 4 ]当時、この符号は、反復復号アルゴリズム（線形複雑度であるにもかかわらず）が利用可能なハードウェアにとって計算コストが高すぎたため、ほとんど無視されていました。1990年代半ばに、ハードウェアの改良により実用的になったことと、ターボ符号に代わる高性能で特許のない代替手段となったことから、再び注目を集めるようになりました。
LDPC符号の性能において中心となるのは、反復的な信念伝播復号アルゴリズムへの適応性である。このアルゴリズムの下では、LDPC符号は、多くのチャネルの理論的な限界（容量）[ 5 ]に低い計算コストで近づくように設計することができる。
LDPC 符号への関心が再び高まったのは、密接に関連するターボ符号の発明(1993 年) の後であり、その反復復号アルゴリズムは当時使用されていた他の符号よりも優れた性能を示した。LDPC 符号はその後 1996 年に再発見された。 [ 6 ] 当初、業界で LDPC 符号がターボ符号よりも好まれたのは、後者に対する特許関連の制約が原因だった。[ 7 ] 発見以来、LDPC 符号の進歩により、エラー フロアと高コード レート範囲での性能の点でターボ符号を上回り、ターボ符号は低コード レートに適しているようになった。[ 8 ] ターボ符号の基本特許は 2013 年に失効したが、[ 9 ] [ 10 ]多くの場合、LDPC 符号は技術的な利点から依然として好まれている。
LDPC 符号に対する理論的な関心は、数学的解析への適合性からも生じている。Gallager は博士論文で、LDPC 符号が二元体上の線形符号に対する Gilbert–Varshamov 限界を高い確率で達成することを示した。二元消去チャネル上では、符号列はチャネル容量に任意に近いレートで設計され、復号誤り確率は確実にゼロになり、復号複雑度は線形である。[ 11 ] 2020 年に、Gallager の LDPC 符号がリスト復号容量 を達成し、一般体上の線形符号に対する Gilbert–Varshamov 限界も達成することが示された。[ 12 ]
理論的には、LDPC符号の解析は、固定符号化率でブロック長が増加する符号系列に焦点を当てています。これらの系列は通常、特定のチャネルセットに合わせて設計されます。適切に設計された系列の場合、信念伝播における復号誤差は、チャネル容量に非常に近い符号化率において、しばしば極めて小さく（ブロック長とともにゼロに近づく）なることが証明できます。さらに、これはブロック長に対して線形な複雑さで実現できます。
この理論的な性能は、疎なタナーグラフ（特殊化された二部グラフ）に基づく柔軟な設計方法を用いることで可能になる。[ 13 ]
LDPCコードアンサンブルは、統計物理学の手法を用いて解析されてきた。村山、カバシマ、サード、ビセンテは、スピンシステム類似性とレプリカ法を用いて正則LDPCコードを研究し[ 14 ]、その後の研究でこの解析をガロア体上のLDPCコードに拡張した[ 15 ]。
2013 年以降、LDPC コードは量子コンピュータのエラー訂正手段としても提案されており、エラー訂正に必要な追加の量子ビットが少ないことが、Gottesman、ストラスブール大学、Alice & Bobらによって実証されている。[ 16 ] [ 17 ] [ 18 ] [ 19 ] 2025 年の研究では、量子偏光解消チャネル用のLDPC-CSS量子コードが報告されており、数値復号性能はハッシュ限界に近づき、復号の複雑さは物理量子ビットの数に比例する。[ 20 ]
2003年、不規則繰り返し累積（IRA）スタイルのLDPC符号が6つのターボ符号を破り、デジタルテレビの新しいDVB-S2規格の誤り訂正符号となった。[ 21 ]この決定は、並列化の容易さやエラーフロアなどの技術的要因[ 22 ] 、およびLDPCの特許フリーの状態[ 23 ]に基づいていた。
2008年、LDPCはITU-T G.hn規格の前方誤り訂正（FEC）システムとして畳み込みターボ符号を凌駕した。 [ 24 ] G.hnは、LDPC符号の復号複雑度が低い（特に1.0 Gbit/sに近いデータレートで動作する場合）ことと、提案されたターボ符号が望ましい動作範囲で大きな誤りフロアを示したことから、ターボ符号よりもLDPC符号を選択した。 [ 25 ]
LDPC コードは、ツイストペアケーブルを介して毎秒 10 ギガビットでデータを送信する10GBASE-Tイーサネットにも使用されます。2009 年現在、LDPC コードは、高スループット (HT) PHY 仕様の802.11nおよび802.11acのオプション部分としてWi-Fi 802.11 規格の一部にもなっています。 [ 26 ] LDPC は802.11ax (Wi-Fi 6)の必須部分です。[ 27 ]
OFDMシステムの中には、低ビット誤り率でもLDPC訂正内部符号を通過してしまう時折発生する誤り（「エラーフロア」）を修正する追加の外部誤り訂正を追加するものがあります。例えば、 LDPC符号化変調を用いたリード・ソロモン符号（RS-LCM）は、リード・ソロモン外部符号を使用します。[ 28 ] DVB-S2、DVB-T2、およびDVB-C2規格はすべて、LDPC復号後の残留誤りを掃き出すためにBCH符号外部符号を使用します。 [ 29 ]
5G NRは制御チャネルに極性符号を、データチャネルにLDPCを使用します。 [ 30 ] [ 31 ]
LDPC コードは商用ハードディスク ドライブで成功を収めていますが、SSDでそのエラー訂正機能を最大限に活用するには、従来とは異なるきめ細かいフラッシュ メモリ センシングが必要となり、メモリの読み出しレイテンシが増加します。LDPC-in-SSD [ 32 ]は、レイテンシの増加を非常に小さく抑えながら LDPC を SSD に展開する効果的なアプローチであり、LDPC-in-SSD を現実のものにしています。それ以来、LDPC は主要なストレージ ベンダーによって、消費者向けグレードとエンタープライズ グレードの両方の商用 SSD に広く採用されています。多くの TLC (およびそれ以降) SSD は LDPC コードを使用しています。まず高速なハード デコード (バイナリ消去) が試みられ、より低速だがより強力なソフト デコードにフォールバックすることができます。[ 33 ]
LDPC コードは、機能的には疎なパリティ検査行列によって定義されます。この疎行列は、疎性制約に従ってランダムに生成されることが多く、LDPC コードの構成については後述します。これらのコードは、1960 年に Robert Gallager によって初めて設計されました。[ 4 ]
以下は、 Forneyのファクターグラフ表記法を用いたLDPCコードの例[ 34 ]のグラフ断片です。このグラフでは、グラフ上部のn個の変数ノードが、グラフ下部の( n - k )個の制約ノードに接続されています。
これは、( n , k ) LDPC コードをグラフィカルに表現する一般的な方法です。有効なメッセージのビットをグラフ上部のTに配置すると、グラフィカルな制約を満たします。具体的には、変数ノード ("=" 記号の付いたボックス) に接続するすべての線は同じ値を持ち、因子ノード ("+" 記号の付いたボックス) に接続するすべての値は、 2 を法として合計すると 0 になります (つまり、合計が偶数になるか、奇数の値が偶数個存在する必要があります)。
画面外に伸びる線を無視すると、有効な符号語に対応する 8 つの 6 ビット文字列が存在します (つまり、000000、001110、010111、011001、100101、101011、110010、111100)。この LDPC 符号断片は、6 ビットでエンコードされた 3 ビットメッセージを表しています。ここでは、チャネルエラーからの回復の可能性を高めるために冗長性が使用されています。これは、 n = 6、k = 3の(6, 3)線形符号です。
再び画面外に伸びる線を無視すると、このグラフ断片を表すパリティチェック行列は次のようになります。
この行列では、各行は3つのパリティチェック制約の1つを表し、各列は受信符号語の6ビットのうちの1つを表します。
この例では、パリティ検査行列H をこの形式にすることで 8 つのコードワードが得られます。GF(2)における基本的な行操作を通して：
ステップ 1: H.
ステップ2：1行目を3行目に加えます。
ステップ3：2行目と3行目を入れ替えます。
ステップ4：1行目を3行目に加えます。
これから、生成行列Gは次のように得られる。（これはバイナリコードであるという特殊なケースに留意する）)、または具体的には：
最後に、考えられる8つの3ビット文字列すべてにGを乗算することで、8つの有効な符号語すべてが得られます。たとえば、ビット文字列「101」の符号語は次のように得られます。
どここれは、mod 2 乗算の記号です。
確認として、Gの行空間はHと直交しており、。
入力ビット列「101」は、単位行列の存在により、コードワード「101011」の最初の3ビットとして検出されます。符号語の末尾の3ビット「011」はパリティビットです。
考えられるすべてのメッセージの各ビットは、前のセクションで定義したG行列との直接乗算によって生成できます。しかし、この方法は実際にはほとんど使用されず、符号化の容易さを考慮してコードが選択されます。実際には、入力ビットはそのまま出力にコピーされ、チェックビットは一連のエンコーダで計算されます。理論的には、チェックビットごとに1つのエンコーダが必要ですが、実際には、再利用可能なエンコーダを選択することでハードウェアコストが削減されます。
フレームの符号化中、入力データビット（D）は繰り返し処理され、構成エンコーダのセットに分配されます。構成エンコーダは通常アキュムレータであり、各アキュムレータはパリティシンボルを生成するために使用されます。元のデータ（S 0,K-1）の単一コピーがパリティビット（P）とともに送信され、コードシンボルが構成されます。各構成エンコーダからのSビットは破棄されます。
パリティビットは、他の構成コード内で使用される場合がある。
DVB-S2レート 2/3 コードを使用した例では、エンコードされたブロック サイズは 64800 シンボル (N=64800) で、43200 データ ビット (K=43200) と 21600 パリティ ビット (M=21600) で構成されます。各構成コード (チェック ノード) は、最初のパリティ ビットを除いて 16 データ ビットをエンコードし、最初のパリティ ビットは 8 データ ビットをエンコードします。最初の 4680 データ ビットは 13 回繰り返され (13 個のパリティ コードで使用)、残りのデータ ビットは 3 つのパリティ コード (不規則 LDPC コード) で使用されます。[ 35 ]
比較のために説明すると、従来のターボ符号は通常、並列に配置された2つの構成要素符号を使用し、それぞれが入力ブロック（K）全体のデータビットを符号化します。これらの構成要素符号器は、中程度の深さ（8状態または16状態）の再帰的畳み込み符号（RSC）であり、フレームのコピーを1つインターリーブする符号インターリーバによって分離されています。
一方、LDPC符号は、多数の低深度構成符号（アキュムレータ）を並列に用い、各構成符号は入力フレームのごく一部のみを符号化します。これらの多数の構成符号は、繰り返し演算と分配演算によって接続された多数の低深度（2状態）「畳み込み符号」と見なすことができます。繰り返し演算と分配演算は、ターボ符号におけるインターリーバの役割を果たします。
さまざまな構成要素コードの接続と各入力ビットの冗長性のレベルをより正確に管理できる能力により、LDPC コードの設計に柔軟性が増し、場合によってはターボコードよりも優れたパフォーマンスが得られる可能性があります。ターボコードは、低コードレートでは依然として LDPC よりも優れたパフォーマンスを発揮するか、少なくとも、優れたパフォーマンスを発揮する低レートコードの設計はターボコードの方が容易です。[ 36 ] [ 37 ]
実際には、アキュムレータを構成するハードウェアは、エンコード処理中に再利用されます。つまり、最初のパリティビットセットが生成されて保存されると、同じアキュムレータハードウェアを使用して次のパリティビットセットが生成されます。
他のコードと同様に、バイナリ対称チャネル上のLDPCコードの最尤復号はNP完全問題であり、[ 38 ] 3次元マッチングからの還元によって示されています。したがって、広く信じられているようにP != NPと仮定すると、任意の有用なサイズのコードに対して最適な復号を実行することは実用的ではありません。
しかしながら、反復的な信念伝播復号に基づく準最適解法は優れた結果をもたらし、実際に実装可能である。準最適復号法では、LDPCを構成する各パリティチェックを独立した単一パリティチェック（SPC）コードとみなす。各SPCコードは、 SOVA、BCJR、MAPなどのソフトイン・ソフトアウト（SISO）技術、およびその派生技術を用いて個別に復号される。各SISO復号からのソフト判定情報は、同じ情報ビットの他の冗長SPC復号と相互チェックされ、更新される。その後、各SPCコードは更新されたソフト判定情報を用いて再度復号される。このプロセスは、有効な符号語が得られるか、復号が尽きるまで繰り返される。このタイプの復号は、しばしば積和復号と呼ばれる。
SPCコードの解読はしばしば「チェックノード」処理と呼ばれ、変数の相互チェックはしばしば「変数ノード」処理と呼ばれます。
実用的なLDPCデコーダの実装では、スループットを向上させるために、SPCコードのセットが並列に復号される。
対照的に、バイナリ消去チャネルにおける信念伝播は、反復的な制約充足から構成されるため、特に単純である。
例えば、上記の例にある有効な符号語101011がバイナリ消去チャネルを介して送信され、最初のビットと4番目のビットが消去されて?01?11として受信されたとします。送信されたメッセージは符号制約を満たしているはずなので、受信したメッセージを因子グラフの一番上に書き込むことでメッセージを表すことができます。
この例では、最初のビットはまだ復元できません。なぜなら、それに接続されているすべての制約に、未知のビットが複数含まれているからです。メッセージの復号を進めるには、消去されたビットのうち1つだけに接続されている制約を特定する必要があります。この例では、2番目の制約だけで十分です。2番目の制約を調べると、4番目のビットはゼロだったはずです。なぜなら、その位置にゼロがある場合にのみ、制約が満たされるからです。
この手順を繰り返します。4ビット目の新しい値は、最初の制約と組み合わせて、以下に示すように1ビット目を復元するために使用できます。つまり、最も左の制約を満たすには、1ビット目が1でなければなりません。
したがって、メッセージは反復的に復号化できます。他のチャネルモデルでは、変数ノードとチェックノード間で渡されるメッセージは実数であり、これは確率と信憑性を表します。
この結果は、修正された符号語rにパリティチェック行列Hを乗じることで検証できます。
この演算の結果z（症候群）は3×1のゼロベクトルであるため、結果として得られる符号語rは正常に検証されます。
復号が完了した後、符号語の最初の3ビットを調べることで、元のメッセージビット「101」を抽出できます。
この消去の例は説明的なものですが、事実上すべての市販LDPCデコーダで使用されているソフトデシジョン復号やソフトデシジョンメッセージパッシングの使用法は示していません。
2010 年以降、可変ノードと制約ノードの更新の代替スケジュールの影響を研究する作業も数多く行われてきました。LDPC コードの復号に使用されていた元の手法は、フラッディングとして知られていました。このタイプの更新では、可変ノードを更新する前に、すべての制約ノードを更新する必要があり、その逆も同様でした。Vila Casado らによる後の研究[ 39 ] [ 40 ]では、利用可能な最新のチェックノード情報で可変ノードを更新する代替更新手法が研究されました。
これらのアルゴリズムの背後にある直感は、値が最も変動する変数ノードが最初に更新する必要があるということです。対数尤度比(LLR) の大きさが大きく、更新ごとに大きく変化しない高信頼性ノードは、符号と大きさがより大きく変動する他のノードと同じ頻度で更新する必要はありません。[ 40 ]これらのスケジューリングアルゴリズムは、フラッディングを使用するものよりも収束速度が速く、エラーフロアが低くなっています。これらの低いエラーフロアは、Informed Dynamic Scheduling (IDS) [ 39 ]アルゴリズムが、近似コードワードのトラップセットを克服する能力によって実現されています。 [ 41 ]
非フラッディングスケジューリングアルゴリズムを使用する場合、反復の別の定義が使用されます。レートがk / nの ( n , k ) LDPC コードの場合、n個の変数ノードとn − k 個の制約ノードが更新されたときに、完全な反復が発生します。これは、更新された順序に関係なく適用されます。
ブロックサイズが大きい場合、LDPC コードは一般的にデコーダの動作を最初に調べて構築されます。ブロックサイズが無限大に近づくと、LDPC デコーダには、デコードが確実に達成されるノイズ閾値と、それを超えるとデコードが達成されないノイズ閾値があることが示されます[ 42 ] 。これは一般的にクリフ効果と呼ばれています。この閾値は、チェックノードからのアークと可変ノードからのアークの最適な比率を見つけることで最適化できます。この閾値を視覚化するための近似的なグラフィカルアプローチは、EXIT チャートです。[ 43 ]
この最適化後の特定のLDPCコードの構築は、主に2種類の手法に分類されます。[ 43 ]
擬似乱数アプローチによる構築は、ブロックサイズが大きい場合、ランダムな構築が良好な復号性能をもたらすという理論的結果に基づいています。[ 6 ]一般に、擬似乱数コードは複雑なエンコーダを持ちますが、最良のデコーダを持つ擬似乱数コードは単純なエンコーダを持つことができます。[ 44 ]理論上の限界である無限ブロックサイズで期待される望ましい特性が有限ブロックサイズで実現されるように、さまざまな制約が適用されることがよくあります。[ 43 ]
組み合わせ論的手法を用いることで、小ブロックサイズのLDPC符号の特性を最適化したり、単純なエンコーダを持つ符号を作成したりすることができる。
LDPC 符号の中には、 10 ギガビット イーサネット規格で使用される RS-LDPC 符号のように、リード・ソロモン符号に基づいているものもあります。[ 45 ]ランダムに生成された LDPC 符号と比較して、DVB-S2規格で使用される LDPC 符号のような構造化された LDPC 符号は、よりシンプルで低コストのハードウェアを持つことができます。特に、H 行列が巡回行列となるように構築された符号はそうです。[ 46 ]
LDPCコードを構築するもう1つの方法は、有限形状を使用することです。この方法は、 2001年にY. Kouらによって提案されました。[ 47 ]
LDPC コードは、ターボコードなどの他の強力な符号化方式と比較できます。[ 48 ]一方、ターボコードのBER性能は、低コード制限の影響を受けます。[ 49 ] LDPC コードには最小距離の制限がないため、[ 50 ]間接的に、LDPC コードはターボコードよりも比較的高いコードレート(例えば 3/4、5/6、7/8) でより効率的になる可能性があります。ただし、LDPC コードは完全な代替ではありません。ターボコードは、低いコードレート (例えば 1/6、1/3、1/2) で最良のソリューションです。[ 36 ] [ 37 ]
今のところ、設計と証明によるコードを実現している機能は1つしかない。
