低密度パリティ検査符号

情報理論において、低密度パリティ検査( LDPC )符号は線形 誤り訂正符号であり、ノイズの多い伝送チャネルを介してメッセージを送信する方法です。 ^{[1] [2]} LDPC 符号は、スパースタナー グラフ(二部グラフのサブクラス) を使用して構築されます。^[3] LDPC 符号は容量接近符号であり、対称メモリレス チャネルの理論上の最大値 (シャノン限界)に非常に近いノイズしきい値を設定できる実用的な構成が存在することを意味します。ノイズしきい値はチャネル ノイズの上限を定義し、この上限までは情報が失われる確率を必要なだけ小さくすることができます。反復確率伝播技術を使用すると、LDPC 符号はブロック長に線形な時間でデコードできます。

LDPC コードは、1960 年にマサチューセッツ工科大学の博士論文で LDPC の概念を考案したRobert G. GallagerにちなんでGallager コードとも呼ばれています。 ^{[4] [5]}しかし、LDPC コードでは計算コストのかかる反復復号化が必要となるため、何十年も使われていませんでした。1993 年に新しく発明されたターボ コードにより、反復復号化を行うコードが当時使用されていた他のコードよりはるかに優れていることが実証されましたが、ターボ コードには特許が取得されており、使用料が必要でした。これにより、同様のパフォーマンスを持つことが示されたものの、はるかに古く特許も取得されていない LDPC コードに新たな関心が集まりました。^[6]現在、ターボ コードの基本特許は失効していますが (2013 年 8 月 29 日)、^{[7] [8]} LDPC コードは技術的なメリットから今でも使用されています。

LDPC符号は理想的な組み合わせ特性を持つことが示されています。Gallagerは博士論文で、LDPC符号が2元体上の線形符号のギルバート・ヴァルシャモフ境界を高い確率で達成することを示しました。2020年には、GallagerのLDPC符号がリスト復号能力を達成し、一般体上の線形符号のギルバート・ヴァルシャモフ境界も達成することが示されました。^[9]

1963年にギャラガーが初めて開発した当時は実装が非現実的であったため、^[10] LDPC符号は1996年に彼の研究が再発見されるまで忘れ去られていました。 ^{[11] 1993年に発見された容量に近づく別の種類の符号である} ターボ符号は、1990年代後半に深宇宙ネットワークや衛星通信などのアプリケーションで使用される符号化方式として選ばれました。その後、LDPC符号は同様のパフォーマンスを持つ特許フリーの代替手段として再び注目を集めました。^[6]それ以来、低密度パリティチェック符号の進歩により、高符号率範囲でのエラーフロアとパフォーマンスの点でターボ符号を上回り、ターボ符号は低符号率にのみ適したものになりました。^[12]

2003年、不規則反復累積（IRA）スタイルのLDPCコードが6つのターボコードに勝利し、デジタルテレビ向けの新しいDVB-S2規格のエラー訂正コードになりました。^[13] DVB-S2選定委員会は、並列デコーダアーキテクチャではなく、はるかに効率の悪いシリアルデコーダアーキテクチャを使用して、ターボコード提案のデコーダ複雑度の見積もりを行いました。これにより、ターボコード提案では、LDPC提案のフレームサイズの半分程度のフレームサイズを使用する必要がありました。^{[引用が必要]}

2008年、LDPCはITU-T G.hn標準の前方誤り訂正（FEC）システムとして畳み込みターボ符号に勝利しました。 ^[14] G.hnは、デコードの複雑さが低い（特に1.0Gbit/sに近いデータレートで動作する場合）ことと、提案されたターボ符号が望ましい動作範囲で大きなエラーフロアを示したことから、ターボ符号よりもLDPC符号を選択​​しました。 ^[15]

LDPCコードは、ツイストペアケーブルを介して10ギガビット/秒でデータを送信する10GBASE-Tイーサネットにも使用されています。2009年現在、LDPCコードは、高スループット（HT）PHY仕様の802.11nおよび802.11acのオプション部分として、 Wi-Fi 802.11標準の一部でもあります。 ^{[16] LDPCは、} 802.11ax（Wi-Fi 6）の必須部分です。 ^[17]

一部のOFDMシステムでは、低いビット エラー レートでも LDPC 訂正内部コードを通過する偶発的なエラー (「エラー フロア」) を修正する追加の外部エラー訂正が追加されます。

例えば、LDPC符号化変調方式のリード・ソロモン符号（RS-LCM）はリード・ソロモン外部符号を使用します。 ^[18] DVB-S2、DVB-T2、DVB-C2の各規格では、LDPC復号後の残留エラーを消去するためにBCH符号外部符号を使用します。 ^[19]

5G NRは制御チャネルに極性符号を使用し、データチャネルにLDPCを使用する。^{[20] [21]}

LDPC コードは商用ハードディスクドライブでは成功を収めていますが、SSDでそのエラー訂正機能を最大限に活用するには、従来とは異なるきめ細かいフラッシュメモリセンシングが必要であり、メモリ読み取りレイテンシが増加します。LDPC-in-SSD ^[22]は、非常に小さなレイテンシ増加で SSD に LDPC を導入する効果的なアプローチであり、これにより SSD での LDPC が現実のものとなります。それ以来、LDPC は主要なストレージベンダーによってカスタマーグレードとエンタープライズグレードの両方で商用 SSD に広く採用されてきました。多くの TLC (およびそれ以降) SSD は LDPC コードを使用しています。最初に高速ハードデコード (バイナリ消去) が試行され、これはより遅いがより強力なソフトデコードにフォールバックする可能性があります。^[23]

LDPC コードは機能的にはスパースなパリティ検査行列によって定義されます。このスパース行列はスパース制約に従ってランダムに生成されることが多く、LDPC コードの構築については後で説明します。これらのコードは 1960 年に Robert Gallager によって初めて設計されました。^[5]

以下は、 Forney の因子グラフ表記法を使用した LDPC コードの例のグラフ フラグメントです。このグラフでは、グラフの上部にあるn 個の変数ノードが、グラフの下部にある ( n − k ) 個の制約ノード に接続されています。

これは、( n ,  k ) LDPC コードをグラフィカルに表現する一般的な方法です。有効なメッセージのビットは、グラフの上部にあるTに配置されると、グラフィカルな制約を満たします。具体的には、変数ノード (「=」記号の付いたボックス) に接続するすべての線は同じ値を持ち、因子ノード (「+」記号の付いたボックス) に接続するすべての値は、2 を法として合計が 0 になる必要があります (つまり、合計が偶数になるか、奇数が偶数である必要があります)。

図から外れた線を無視すると、有効なコードワードに対応する 6 ビットの文字列は 8 つあります (つまり、000000、011001、110010、101011、111100、100101、001110、010111)。この LDPC コード フラグメントは、6 ビットとしてエンコードされた 3 ビット メッセージを表します。ここでは、チャネル エラーからの回復の可能性を高めるために冗長性が使用されています。これは (6, 3)線形コードで、n  = 6、k  = 3 です。

再び図から外れる線を無視すると、このグラフ断片を表すパリティ検査行列は次のようになる。

${\displaystyle \mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&0&1&0\\\end{pmatrix}}.}$

このマトリックスでは、各行は 3 つのパリティ チェック制約の 1 つを表し、各列は受信したコードワードの 6 ビットの 1 つを表します。

この例では、パリティ検査行列 HをGF(2)の基本的な行演算によってこの形式にすることで、8つのコードワードを取得できます。 ${\displaystyle {\begin{bmatrix}-P^{T}|I_{nk}\end{bmatrix}}}$

${\displaystyle \mathbf {H} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&0\\\end{pmatrix}}_{1}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\0&1&1&0&1\\\end{pmatrix}}_{2}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&0\\0&1&1&0&1&0\\0&0&1&1&0&1\\\end{pmatrix}}_{3}\sim {\begin{pmatrix}1&1&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\\\end{pmatrix}}_{4}.}$

ステップ1: H.

ステップ 2: 行 1 が行 3 に追加されます。

ステップ 3: 行 2 と 3 が入れ替わります。

ステップ 4: 行 1 が行 3 に追加されます。

これから、生成行列 G は次のように得られます(これがバイナリ コードである特殊なケースであることに注意)。具体的には、 ${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}}$${\displaystyle P=-P}$

${\displaystyle \mathbf {G} ={\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}.}$

最後に、8 つの可能な 3 ビット文字列すべてにGを掛けると、8 つの有効なコードワードがすべて得られます。たとえば、ビット文字列 '101' のコードワードは次のように得られます。

${\displaystyle {\begin{pmatrix}1&0&1\\\end{pmatrix}}\odot {\begin{pmatrix}1&0&0&1&0&1\\0&1&0&1&1&1\\0&0&1&1&1&0\\\end{pmatrix}}={\begin{pmatrix}1&0&1&0&1&1\\\end{pmatrix}}}$、

ここで はmod 2 の乗算の記号です。 ${\displaystyle \odot}$

確認のため、Gの行空間はHに直交し、${\displaystyle G\odot H^{T}=0}$

ビット文字列「101」は、コードワード「101011」の最初の 3 ビットとして見つかります。

フレームのエンコード中、入力データ ビット (D) が繰り返され、一連の構成エンコーダに分配されます。構成エンコーダは通常、アキュムレータであり、各アキュムレータはパリティ シンボルの生成に使用されます。元のデータ (S _0,K-1 ) の 1 つのコピーがパリティ ビット (P) とともに送信され、コード シンボルが作成されます。各構成エンコーダからの S ビットは破棄されます。

パリティ ビットは別の構成コード内で使用される場合があります。

DVB-S2 レート 2/3 コードを使用した例では、エンコードされたブロック サイズは 64800 シンボル (N=64800)、データ ビットは 43200 (K=43200)、パリティ ビットは 21600 (M=21600) です。各構成コード (チェック ノード) は、8 データ ビットをエンコードする最初のパリティ ビットを除き、16 データ ビットをエンコードします。最初の 4680 データ ビットは 13 回繰り返され (13 のパリティ コードで使用)、残りのデータ ビットは 3 つのパリティ コード (不規則な LDPC コード) で使用されます。

比較すると、従来のターボ コードでは通常、並列に構成された 2 つの構成コードが使用され、各コードでデータ ビットの入力ブロック (K) 全体がエンコードされます。これらの構成エンコーダーは、フレームの 1 つのコピーをインターリーブするコード インターリーバーによって分離された、中程度の深さ (8 または 16 状態) の再帰畳み込みコード (RSC) です。

対照的に、LDPC コードは、多数の低深度構成コード (アキュムレータ) を並列に使用し、各コードが入力フレームのごく一部だけをエンコードします。多数の構成コードは、繰り返し操作と分散操作を介して接続された多数の低深度 (2 状態)「畳み込みコード」として考えることができます。繰り返し操作と分散操作は、ターボ コードのインターリーバの機能を実行します。

さまざまな構成コードの接続と各入力ビットの冗長性のレベルをより正確に管理する機能により、LDPC コードの設計の柔軟性が向上し、場合によってはターボ コードよりも優れたパフォーマンスを実現できます。ターボ コードは、低いコード レートでは依然として LDPC よりもパフォーマンスが優れているように見えます。少なくとも、パフォーマンスの優れた低レート コードの設計はターボ コードの方が簡単です。

実際には、アキュムレータを構成するハードウェアは、エンコード処理中に再利用されます。つまり、最初のパリティ ビット セットが生成され、パリティ ビットが保存されると、同じアキュムレータ ハードウェアを使用して次のパリティ ビット セットが生成されます。

他のコードと同様に、バイナリ対称チャネル上のLDPCコードの最大尤度復号はNP完全問題であり、 ^[24] 3次元マッチングからの縮減によって示されています。したがって、広く信じられているようにP != NPと仮定すると、任意のサイズの任意のコードに対して最適な復号を実行することは現実的ではありません。

ただし、反復的なビリーフ プロパゲーションデコードに基づく準最適な手法は、優れた結果をもたらし、実際に実装できます。準最適なデコード手法では、LDPC を構成する各パリティ チェックを独立した単一パリティ チェック (SPC) コードと見なします。各 SPC コードは、SOVA、BCJR、MAP 、およびその他の派生的なソフト入力ソフト出力(SISO) 手法を使用して個別にデコードされます。各 SISO デコードからのソフト決定情報は、同じ情報ビットの他の冗長 SPC デコードとクロスチェックされ、更新されます。次に、更新されたソフト決定情報を使用して、各 SPC コードが再度デコードされます。このプロセスは、有効なコードワードが得られるまで、またはデコードが尽きるまで繰り返されます。このタイプのデコードは、多くの場合、合計積デコードと呼ばれます。

SPC コードのデコードは「チェック ノード」処理と呼ばれることが多く、変数のクロスチェックは「変数ノード」処理と呼ばれることがよくあります。

実際の LDPC デコーダの実装では、スループットを向上させるために SPC コードのセットが並列にデコードされます。

対照的に、バイナリ消去チャネル上の信念伝播は、反復的な制約充足で構成されるため、特に単純です。

たとえば、上記の例の有効なコードワード 101011 がバイナリ消去チャネルを介して送信され、最初のビットと 4 番目のビットが消去されて ?01?11 が生成された状態で受信された場合を考えます。送信されたメッセージはコード制約を満たしている必要があるため、受信したメッセージを因子グラフの上部に書き込むことでメッセージを表すことができます。

この例では、最初のビットはまだ復元できません。これは、それに接続されているすべての制約に 1 つ以上の不明なビットがあるためです。メッセージのデコードを続行するには、消去されたビットの 1 つだけに接続されている制約を識別する必要があります。この例では、2 番目の制約だけで十分です。2 番目の制約を調べると、その位置の 0 だけが制約を満たすため、4 番目のビットは 0 であったに違いありません。

この手順は繰り返し実行されます。4 番目のビットの新しい値は、以下に示すように、最初の制約と組み合わせて使用​​して最初のビットを復元できます。つまり、左端の制約を満たすには、最初のビットが 1 でなければなりません。

したがって、メッセージは反復的にデコードできます。他のチャネル モデルでは、変数ノードとチェック ノード間で渡されるメッセージは実数であり、確率と信念の尤度を表します。

この結果は、訂正されたコードワードrにパリティ検査行列Hを掛けることによって検証できる。

${\displaystyle \mathbf {z} =\mathbf {H\odot r} ={\begin{pmatrix}1&1&1&1&0&0\\0&0&1&1&0&1\\1&0&0&1&1&0\\\end{pmatrix}}\odot {\begin{pmatrix}1\\0\\1\\0\\1\\1\\\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\\end{pmatrix}}.}$

この演算の結果z (シンドローム) は 3 × 1 のゼロベクトルなので、結果として得られるコードワードr は正常に検証されます。

デコードが完了すると、コードワードの最初の 3 ビットを調べることで、元のメッセージ ビット「101」を抽出できます。

この消去例は説明的ではありますが、ほとんどすべての市販の LDPC デコーダーで使用されているソフト決定デコードまたはソフト決定メッセージ パッシングの使用は示されていません。

近年^{[いつ? ]}、変数ノードと制約ノードの更新の代替スケジュールの効果を研究する研究も盛んに行われてきました。LDPC コードのデコードに使用された元の手法はフラッディングとして知られていました。このタイプの更新では、変数ノードを更新する前にすべての制約ノードを更新する必要があり、その逆も同様です。Vila Casado らによる後の研究[25]では、^変数ノードが最新の利用可能なチェックノード情報で更新される代替更新手法が研究されました。^[要出典]

これらのアルゴリズムの背後にある直感は、値が最も変化する変数ノードが最初に更新される必要があるというものです。対数尤度比(LLR) の大きさが大きく、更新ごとに大きく変化しない信頼性の高いノードは、符号と大きさがより大きく変動する他のノードと同じ頻度で更新する必要はありません。^{[要出典]これらのスケジューリング アルゴリズムは、フラッディングを使用するものよりも収束速度が速く、エラー フロアが低くなっています。これらのエラー フロアの低さは、Informed Dynamic Sc​​heduling (IDS) [25]}アルゴリズムが、近いコードワードのトラッピング セットを克服する 能力によって実現されています。^[26]

非フラッディングスケジューリングアルゴリズムを使用する場合、反復の別の定義が使用されます。レートk / nの ( n ,  k ) LDPC コードの場合、n個の変数とn  −  k 個の制約ノードが更新されると、更新順序に関係なく完全な反復が発生します。 ^{[引用が必要]}

ブロックサイズが大きい場合、LDPC コードは一般に、まずデコーダの動作を研究することによって構築されます。ブロックサイズが無限大に近づくにつれて、LDPC デコーダには、それ以下では確実にデコードが達成され、それを超えるとデコードが達成されないノイズしきい値があることが示されます。 ^[27]俗に崖効果と呼ばれます。このしきい値は、チェックノードからのアークと変数ノードからのアークの最適な割合を見つけることで最適化できます。このしきい値を視覚化する近似的なグラフィカルなアプローチは、 EXIT チャートです。^[要出典]

この最適化後の特定のLDPCコードの構築は、主に2つのタイプの技術に分類されます。^{[引用が必要]}

• 疑似ランダムアプローチ
• 組み合わせアプローチ

疑似ランダムアプローチによる構築は、大きなブロックサイズの場合、ランダム構築により良好な復号性能が得られるという理論的結果に基づいています。^[11]一般に、疑似ランダムコードには複雑なエンコーダがありますが、最良のデコーダを備えた疑似ランダムコードには単純なエンコーダがあります。^[28]理論上の無限ブロックサイズの限界で期待される望ましい特性が有限ブロックサイズでも確実に発生するようにするために、さまざまな制約が適用されることがよくあります。^[要出典]

組み合わせアプローチは、小さなブロックサイズの LDPC コードの特性を最適化したり、単純なエンコーダーを使用してコードを作成したりするために使用できます。^{[引用が必要]}

LDPCコードの中には、 10ギガビットイーサネット規格で使用されているRS-LDPCコードなど、リード・ソロモンコードをベースにしたものもあります。^{[29]ランダムに生成されたLDPCコードと比較して、} DVB-S2規格で使用されているLDPCコードなどの構造化LDPCコードは、特にH行列が巡回行列になるように構築されたコードでは、より単純で低コストのハードウェアを使用できます。^[30]

LDPC符号を構築するもう一つの方法は有限幾何学を使うことである。この方法は2001年にY. Kouらによって提案された。^[31]

LDPC コードは、他の強力な符号化方式、例えばターボコードと比較することができます。^[32]一方で、ターボコードのBERパフォーマンスは、低コード制限の影響を受けます。^[33] LDPC コードには最小距離の制限がありません。^{[34]これは間接的に、LDPC コードがターボコードよりも比較的高い}コードレート(例: 3/4、5/6、7/8)で効率的である可能性があることを意味します。ただし、LDPC コードは完全な代替品ではありません。ターボコードは、より低いコードレート (例: 1/6、1/3、1/2) での最適なソリューションです。^{[35] [36]}

• リチャード・ハミング
• クロード・シャノン
• デビッド・J・C・マッケイ
• アーヴィング・S・リード
• マイケル・ルビー

• グラフ理論
• ハミングコード
• スパースグラフコード
• エクスパンダーコード

• G.hn/G.9960 (電力線、電話線、同軸ケーブルを介したネットワークに関する ITU-T 標準)
• 802.3anまたは 10GBASE-T (ツイストペア経由の 10 ギガビット/秒イーサネット)
• CMMB (中国マルチメディア移動放送)
• DVB-S2 / DVB-T2 / DVB-C2 (デジタルビデオ放送、第2世代)
• DMB-T/H（デジタルビデオ放送）^[37]
• WiMAX (マイクロ波通信の IEEE 802.16e 規格)
• IEEE 802.11n-2009 ( Wi-Fi規格)
• ドクシス3.1
• ATSC 3.0（次世代北米地上デジタル放送）
• 3GPP (5G-NR データ チャネル)

• ファウンテンコード
• LTコード
• オンラインコード
• ラプターコード
• 繰り返し累積コード（単純なターボコードの一種）
• シリアル連結畳み込み符号
• トルネードコード（消失訂正復号用に設計されたLDPCコード）
• ターボコード

これまでのところ、設計と証明によってコードを実現する機能は 1 つしかありません。

• 極性コード

• 低密度パリティ検査コードの紹介 (Sarah J Johnson、2010 年)
• LDPC コード – 簡単なチュートリアル (Bernhard Leiner 著、2005)
• LDPC コード (TU Wien) 2019 年 2 月 28 日にWayback Machineにアーカイブされました
• MacKay, David JC (2003 年 9 月 25 日)。「47. 低密度パリティ チェック コード」。情報理論、推論、学習アルゴリズム。ケンブリッジ大学出版局。557 ～ 573 ページ。ISBN 9780521642989。
• Guruswami, Venkatesan (2006). 「低密度パリティチェックコードの反復復号化」arXiv : cs/0610022。
• LDPC コード: 入門 (Amin Shokrollahi 著、2003 年)
• LDPC コードのビリーフプロパゲーション復号法 (Amir Bennatan、プリンストン大学)
• ターボおよび LDPC コード: 実装、シミュレーション、標準化 (ウェストバージニア大学)
• 情報理論とコーディング (Marko Hennhöfer、2011 年、TU Ilmenau) - 74 ～ 78 ページで LDPC コードについて説明しています。
• LDPCコードとパフォーマンス結果
• DVB-S.2 リンク (LDPC コーディングを含む) (MatLab)
• LDPC コードのエンコード、デコード、シミュレーション用のソース コードは、さまざまな場所から入手できます。
  • C言語によるバイナリ LDPC コード
  • Python用バイナリ LDPC コード(コア アルゴリズムは C)
  • MATLABの LDPC エンコーダと LDPC デコーダ
  • 高速 LDPC シミュレーションのためのC++11の高速前方誤り訂正ツールボックス (AFF3CT)