Low-density parity-check code

提供: tezos-wiki
2018年4月13日 (金) 03:20時点における65.131.255.108 (トーク)による版 (→‎Decoding)
移動先: 案内、 検索

情報理論では、低密度パリティチェック（LDPC は線形 エラー訂正符号、雑音伝送チャネルを介してメッセージを送信する方法。 LDPCはスパースなbipartite graphを使って構築されます。 LDPCコードは、容量接近コードであり、ノイズしきい値を非常に近い値に設定できるような実用的な構成が存在することを意味します（またはバイナリ消去チャンネル）を対称無記憶チャンネルの理論的最大値（[[シャノン - ハートレー定理|シャノン限界]）に変換する。雑音閾値は、チャネル雑音の上限を定義し、これまでは、情報損失の可能性が所望のように小さくすることができる。反復的なbelief propagation技術を使用して、LDPC符号は、そのブロック長さに対して時間的にデコードすることができる。

LDPC符号は、壊れやすいノイズの存在下で、帯域幅またはリターンチャネル制約リンク上で信頼性が高く効率的な情報転送を必要とするアプリケーションでますます使用されています。 LDPCコードの実装は、他のコード、特にターボコードの実装に比べて遅れています。ターボコードの基本特許は2013年8月29日に期限切れとなりました。[US5446747＆lt; nowiki＆gt;＆lt; nowiki＆gt;]

LDPCコードは1960年にMassachusetts Institute of Technologyで博士論文のLDPCコンセプトを開発した[Robert G. Gallager]の名誉で、 "'Gallager codes' としても知られています。

歴史

1963年にGallagerによって最初に開発されたときに実際に実行することは現実的ではなく、LDPCコードは1996年に再発見されるまで忘れられていた。Turbo codeは1993年に発見された容量接近コードの別のクラスで、 1990年代後半には[Deep Space Network]や[Satellite communication]などのアプリケーションに使用されていました。しかし、低密度パリティチェックコードの進歩により、エラーフロアおよび高いコードレート範囲のパフォーマンスに関してターボコードを上回り、ターボコードはより低いコードレートのみに適応だとされるようになりました。

アプリケーション

2003年に、不規則反復積算（IRA）スタイルのLDPCコードは、デジタルテレビの衛星伝送用の新しいDVB-S2規格の誤り訂正コードになるために、6つのターボコードを破った。 DVB-S2選択委員会は、並列デコーダアーキテクチャではなく、はるかに効率の低いシリアルデコーダアーキテクチャを使用してターボコード提案のデコーダ複雑性推定を行った。

これにより、ターボコード提案はLDPC提案のフレームサイズの1/2のフレームサイズを使用するように強制された。 2008年、LDPCは[ITU-T] G.hn標準のための畳み込みターボ符号を[前方誤り訂正]（FEC）システムとして打ち勝った。 G.hnは、（特に1.0Gbit / sに近いデータレートで動作する場合に）復号化の複雑さがより低く、所望の動作範囲において、提案されたターボ符号が有意なエラーフロアを示すため、ターボ符号に対してLDPC符号を選択​​した。

また、10ギガビット/秒のデータをツイストペアケーブル経由で送信する10GBase-TイーサネットにもLDPCコードが使用された。 2009年現在、LDPCコードは、ハイスループット（HT）PHY仕様の802.11nおよび802.11acのオプション部分としてWi-Fi 802.11標準の一部。

いくつかのOFDMシステムは、低ビット誤り率 sであってもLDPC訂正内符号を過ぎた時折の誤り（「エラーフロア」）を修正する追加の外部誤り訂正を追加する。 例えば： LDPC符号化変調（RS-LCM）によるリードソロモン符号は、リードソロモンの外部符号を使用する。 DVB-S2、DVB-T2およびDVB-C2規格はすべて、BCHコード外部コードを使用して、LDPC復号後の残留誤差をモップアップする。

操作上の使用

LDPC符号は機能的にスパースパリティ検査行列によって定義される。この疎行列は、しばしばランダムに生成され、[[希薄性]の制約を受け、 LDPCコード構築 後で議論されます。これらのコードは、1962年にRobert Gallagerによって最初に設計されました。

以下は、 Forney's factor graph notationを使用した例示的なLDPC符号のグラフ断片である。このグラフでは、グラフの最上部にある「n」個の変数ノードは、グラフの最下部にある制約ノード（「 n 〜 'k' '）に接続されています。

これは、（ n 、＆nbsp; k ）LDPCコードをグラフィカルに表現する一般的な方法です。有効なメッセージのビットは、グラフの一番上の T 'に置かれると、グラフィカルな制約を満たします。具体的には、変数ノード（ '='記号の付いたボックス）に接続するすべての行は同じ値を持ち、因子ノード（ '+'記号の付いたボックス）に接続するすべての値は[[モジュラ算術|モジュロ] ] 2つをゼロにする（換言すると、それらは偶数に合わなければならない、または奇数の偶数がなければならない）。

なし ピクチャから出る任意のラインを無視すると、有効なコードワード（すなわち、000000,011001,110010,101011,111100,100101、001110,010111）に対応する8つの可能な6ビットストリングが存在する。このLDPCコードフラグメントは、6ビットとして符号化された3ビットメッセージを表す。ここでは、冗長性を使用して、チャネルエラーから回復する機会を増やしています。これは（6、＆nbsp; 3）線形コードで、「n」＆nbsp; =＆nbsp; 6、「k」＆nbsp; =＆nbsp; 3です。

ピクチャから出て行くラインを再び無視すると、このグラフフラグメントを表すパリティ検査行列は、

：＆lt;数学＆gt; \ mathbf {H} = \ begin {pmatrix} 1＆1＆1＆1 && 0＆0＆1＆1＆1＆apos;＆apos;＆ 1＆0＆0＆1＆1 && \ end {pmatrix}。 ＆lt; / math＆gt;

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

この例では、8個のコードワードは、パリティ検査行列 'H' をこの形式に入れることによって得ることができる。 I_ {n-k} \ end {bmatrix}＆lt; / math＆gt; GF（2）の基本的な[行操作]を介して： ：<math> \ mathbf {H} = \ begin {pmatrix} 1＆1＆1＆1 && 0＆0＆1＆1＆1＆apos;＆apos;＆ 1＆0＆0＆1＆1 && \ end {pmatrix} _1 \ sim \ begin {pmatrix} 1＆1＆1＆1 && 0＆0＆1＆1＆1＆apos;＆apos;＆ 0＆1＆1＆0 && \ end {pmatrix} _2 \ sim \ begin {pmatrix} 1＆1＆1＆1 && 0＆1＆1＆0 && 0＆0＆1＆1＆1＆apos;＆apos;＆ \ end {pmatrix} _3 \ sim \ begin {pmatrix} 1＆1＆1＆1 && 0＆1＆1＆0 && 1＆1＆amp; 0＆lt; 0＆ \ end {pmatrix} _4。 ＆lt; / math＆gt;

ステップ1：H.

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

ステップ3：行2と3を入れ替えます。

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

これから、生成行列 'G' は、＆lt; math＆gt; \ begin {bmatrix} I_k | P \ end {bmatrix}＆lt; / math＆gt; （これの特別の場合、バイナリコードであることに留意すべきである（P = -P / math））、

：<math> \ mathbf {G} = \ begin {pmatrix} 1＆0＆0＆1＆1＆apos;＆apos;＆ 0＆1＆1＆1＆1 0＆0＆1＆1＆1 && \ end {pmatrix}。 ＆lt; / math＆gt;

最後に、8つの可能なすべての3ビット文字列に 'G' を掛けることによって、8つの有効なコードワードがすべて得られる。例えば、ビット列「101」の符号語は、

：＆lt;数学＆gt; \ begin {pmatrix} 1＆0＆1 \\ \ end {pmatrix} \ cdot \ begin {pmatrix} 1＆0＆0＆1＆1＆apos; 0＆1＆1＆1＆1 0＆0＆1＆1＆1 && \ end {pmatrix} = \ begin {pmatrix} 1＆0＆1＆0＆1＆1 \ end {pmatrix}。 ＆lt; / math＆gt;

チェックとして、 'G' の行空間は、 と直交して、<math> G H ^ T = 0＆lt; / math＆gt;

ビットストリング「101」は、符号語「101011」の最初の3ビットとして検出される。

エンコーダの例

図1は、ほとんどのLDPCエンコーダの機能コンポーネントを示しています。

[[ファイル：ext_38dKJsdjh_LDPCエンコーダ]図.png | thumb | none | 500px | 1. LDPCエンコーダ]]

フレームの符号化の間に、入力データビット（D）が繰り返され、一組の構成エンコーダに分配される。構成エンコーダは典型的にはアキュムレータであり、各アキュムレータはパリティシンボルを生成するために使用される。元のデータ（S 0、K-1 / sub）の単一のコピーがパリティビット（P）とともに送信されて、符号シンボルを構成する。各構成エンコーダからのSビットは廃棄される。

パリティビットは、別の構成コード内で使用されてもよい。

DVB-S2レート2/3符号を使用する例では、符号化されたブロックサイズは43200データビット（K = 43200）および21600パリティビット（M = 21600）を有する64800シンボル（N = 64800）である。各構成符号（検査ノード）は、8データビットを符号化する第1のパリティビットを除いて16データビットを符号化する。第1の4680データビットは13回繰り返され（13個のパリティ符号で使用される）、残りのデータビットは3個のパリティ符号（不規則LDPC符号）で使用される。

比較のために、典型的なターボ符号は、通常、並列に構成された2つの構成符号を使用し、その各々はデータビットの入力ブロック（K）全体を符号化する。これらの構成エンコーダは、フレームの1つのコピーをインターリーブするコードインターリーバによって分離された中程度の深さ（8または16状態）の再帰的畳み込み符号（RSC）である。

これとは対照的に、LDPCコードは、それぞれが入力フレームのごく一部を符号化する多数の低奥行成分符号（累算器）を並列に使用する。多くの構成コードは、反復および分配操作を介して接続された、低深度（2状態）の「畳み込み符号」とみなすことができる。反復および分配動作は、ターボ符号におけるインタリーバの機能を実行する。

様々な構成コードの接続および各入力ビットの冗長度のレベルをより正確に管理する能力は、LDPC符号の設計においてより柔軟性を与え、場合によってはターボ符号よりも良好な性能をもたらす可能性がある。ターボコードは低コードレートではLDPCよりも優れた性能を示しているようですが、少なくとも低レートコードの性能はターボコードでは容易です。

実際問題として、アキュムレータを形成するハードウェアは、符号化プロセス中に再利用される。すなわち、パリティビットの第1セットが生成され、パリティビットが記憶されると、同じアキュムレータハードウェアが、パリティビットの次のセットを生成するために使用される。

デコード

他の符号と同様に、2進対称チャネル上のLDPC符号の[最尤復号]はNP完全問題である。有用なサイズのNP完全コードに対して最適な復号を実行することは実用的ではない。

しかしながら、反復的な[信念伝搬]復号に基づく準最適技術は、優れた結果をもたらし、実際に実施することができる。準最適復号化技法は、LDPCを構成する各パリティ検査を独立した単一パリティ検査（SPC）符号として見る。各SPCコードは、 SOVA、 BCJRなどの soft-in-soft-out（SISO） ]、[最大事後推定| MAP]]、およびそれらの他の派生物。各SISO復号化からの軟判定情報は、同じ情報ビットの他の冗長なSPC復号化と相互チェックされ更新される。その後、各SPCコードは、更新された軟判定情報を用いて再び復号される。このプロセスは、有効なコードワードが達成されるか、または復号化が完了するまで反復される。この種の復号化は、しばしば和 - 積復号と呼ばれる。

SPCコードの復号化は、しばしば「チェックノード」処理と呼ばれ、変数のクロスチェックは、しばしば「可変ノード」処理と呼ばれる。

実用的なLDPC復号器の実装では、SPC符号の組が並列に復号されてスループットが向上する。

対照的に、バイナリ消去チャネルに対する信念伝搬は​​、反復制約満足からなる場合に特に簡単です。

例えば、上記の例の有効コードワード101011が2進消去チャネルを介して送信され、受信された第1および第4のビットが消去されて受信され、？⁠01？⁠11が得られると考える。送信されたメッセージはコード制約を満たさなければならないので、メッセージはファクタグラフの上部に受信メッセージを書き込むことによって表すことができる。

この例では、最初のビットは、それに接続されているすべての制約が複数の未知ビットを持っているため、まだ回復できません。メッセージの復号化を進めるためには、消去されたビットの1つのみに接続する制約を識別しなければならない。この例では、第2の制約のみで十分である。第2の制約を調べると、その位置のゼロだけが制約を満たすため、第4のビットはゼロでなければならない。

その後、この手順が反復されます。第4ビットの新しい値は、以下に示すように第1ビットを回復するために第1制約と組み合わせて使用​​できるようになりました。これは、最初のビットが左端の制約を満たすビットでなければならないことを意味します。

なし

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

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

：<math> \ mathbf {z} = \ mathbf {Hr} = \ begin {pmatrix} 1＆1＆1＆1 && 0＆0＆1＆1＆1＆apos;＆apos;＆ 1＆0＆0＆1＆1 && \ end {pmatrix}

\ begin {pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ \ end {pmatrix}

= \ begin {pmatrix} 0 \\ 0 \\ 0 \\ \ end {pmatrix}。 ＆lt; / math＆gt;

この操作の結果 'z' （[Decoding methods＃Syndrome decoding | syndrome]）は3回であるため、 1つのゼロベクトル、得られたコードワード 'r' は首尾よく検証される。

復号化が完了した後、元のメッセージビット「101」は、符号語の最初の3ビットを見ることによって抽出することができる。

例示的であるが、この消去例は、実質的にすべての商用LDPCデコーダにおいて使用される軟判定復号または軟判定メッセージ通過の使用を示していない。

ノード情報の更新

近年、可変ノードおよび制約ノード更新のための代替スケジュールの影響を研究するために多大な労力が費やされています。 LDPC符号を復号するために使用された元の技術は、「フラッディング」として知られていました。このタイプの更新では、変数ノードを更新する前に、すべての制約ノードを更新する必要があり、その逆も必要でした。後のVila Casadoらの研究では、可変ノードが最新の利用可能なチェックノード情報で更新される代替的な更新技術が研究された。

これらのアルゴリズムの背後にある直感は、値が最も変化する可変ノードが最初に更新する必要があるノードであることです。 [対数尤度比]（LLR）の大きさが大きく、ある更新から次の更新まで大きく変化しない高信頼性ノードは、符号および大きさがより広く変動する他のノードと同じ頻度で更新を必要としない。 これらのスケジューリングアルゴリズムは、フラッディングを使用する場合よりも収束速度が速く、エラーフロアが低くなります。これらのより低いエラーフロアは、情報付き動的スケジューリング（IDS）能力によって達成され、

非フロイドスケジューリングアルゴリズムが使用される場合、反復の代替定義が使用される。レート k / n のLDPC符号（ n 、＆nbsp; k ）に対して、 n 変数と ' 'n' '＆nbsp;＆nbsp;' 'k' '制約ノードは更新された順序に関係なく更新されました。

ルックアップテーブルの復号化

ルックアップテーブルを使用して、比較的低電力のマイクロプロセッサ上のLDPCコードを解読することが可能である。

LDPCのようなコードは一般に、長いブロック長を有する高電力プロセッサ上に実装されるが、低電力プロセッサと短いブロック長（1024）を使用するアプリケーションも存在する。

したがって、所定の入力ビットに基づいて出力ビットを事前計算することが可能である。 'n'個のエントリ（ブロック長1024ビット、これは1024ビット長）を含むテーブルが生成され、さまざまな入力状態（エラーとノン・エラーの両方）のすべての可能なエントリが含まれます。

ビットが入力されると、FIFOレジスタに加算され、FIFOレジスタの値は、事前計算された値から関連する出力をテーブルで検索するために使用されます。

この方法では、プロセッサのオーバーヘッドがほとんどなく、ルックアップテーブル用のメモリのコストが僅かで、4.0＆nbsp; PICチップでもLDPCデコードが可能な非常に高い反復を使用できます。

Code construction

For large block sizes, LDPC codes are commonly constructed by first studying the behaviour of decoders. As the block size tends to infinity, LDPC decoders can be shown to have a noise threshold below which decoding is reliably achieved, and above which decoding is not achieved, colloquially referred to as the cliff effect. This threshold can be optimised by finding the best proportion of arcs from check nodes and arcs from variable nodes. An approximate graphical approach to visualising this threshold is an EXIT chart.

The construction of a specific LDPC code after this optimization falls into two main types of techniques:

  • Pseudorandom approaches
  • Combinatorial approaches

Construction by a pseudo-random approach builds on theoretical results that, for large block size, a random construction gives good decoding performance. Various constraints are often applied to help ensure that the desired properties expected at the theoretical limit of infinite block size occur at a finite block size.

Combinatorial approaches can be used to optimize the properties of small block-size LDPC codes or to create codes with simple encoders.

Some LDPC codes are based on Reed–Solomon codes, such as the RS-LDPC code used in the 10 Gigabit Ethernet standard. Compared to randomly generated LDPC codes, structured LDPC codes—such as the LDPC code used in the DVB-S2 standard—can have simpler and therefore lower-cost hardware—in particular, codes constructed such that the H matrix is a circulant matrix.

Yet another way of constructing LDPC codes is to use finite geometries. This method was proposed by Y. Kou et al. in 2001.

See also

People

Theory

Applications

Other capacity-approaching codes

Source

http://wikipedia.org/

「http://tezos-wiki.jp/wiki/index.php?title=Low-density_parity-check_code&oldid=19715」から取得