Low-density parity-check code

情報理論では、低密度パリティチェック（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ビットとして検出される。

Example Encoder

Figure 1 illustrates the functional components of most LDPC encoders.

ファイル:Ext 38dKJsdjh LDPC encoder Figure.png

Fig. 1. LDPC Encoder

During the encoding of a frame, the input data bits (D) are repeated and distributed to a set of constituent encoders. The constituent encoders are typically accumulators and each accumulator is used to generate a parity symbol. A single copy of the original data (S_0,K-1) is transmitted with the parity bits (P) to make up the code symbols. The S bits from each constituent encoder are discarded.

The parity bit may be used within another constituent code.

In an example using the DVB-S2 rate 2/3 code the encoded block size is 64800 symbols (N=64800) with 43200 data bits (K=43200) and 21600 parity bits (M=21600). Each constituent code (check node) encodes 16 data bits except for the first parity bit which encodes 8 data bits. The first 4680 data bits are repeated 13 times (used in 13 parity codes), while the remaining data bits are used in 3 parity codes (irregular LDPC code).

For comparison, classic turbo codes typically use two constituent codes configured in parallel, each of which encodes the entire input block (K) of data bits. These constituent encoders are recursive convolutional codes (RSC) of moderate depth (8 or 16 states) that are separated by a code interleaver which interleaves one copy of the frame.

The LDPC code, in contrast, uses many low depth constituent codes (accumulators) in parallel, each of which encode only a small portion of the input frame. The many constituent codes can be viewed as many low depth (2 state) 'convolutional codes' that are connected via the repeat and distribute operations. The repeat and distribute operations perform the function of the interleaver in the turbo code.

The ability to more precisely manage the connections of the various constituent codes and the level of redundancy for each input bit give more flexibility in the design of LDPC codes, which can lead to better performance than turbo codes in some instances. Turbo codes still seem to perform better than LDPCs at low code rates, or at least the design of well performing low rate codes is easier for Turbo Codes.

As a practical matter, the hardware that forms the accumulators is reused during the encoding process. That is, once a first set of parity bits are generated and the parity bits stored, the same accumulator hardware is used to generate a next set of parity bits.

Decoding

As with other codes, the maximum likelihood decoding of an LDPC code on the binary symmetric channel is an NP-complete problem. Performing optimal decoding for a NP-complete code of any useful size is not practical.

However, sub-optimal techniques based on iterative belief propagation decoding give excellent results and can be practically implemented. The sub-optimal decoding techniques view each parity check that makes up the LDPC as an independent single parity check (SPC) code. Each SPC code is decoded separately using soft-in-soft-out (SISO) techniques such as SOVA, BCJR, MAP, and other derivates thereof. The soft decision information from each SISO decoding is cross-checked and updated with other redundant SPC decodings of the same information bit. Each SPC code is then decoded again using the updated soft decision information. This process is iterated until a valid code word is achieved or decoding is exhausted. This type of decoding is often referred to as sum-product decoding.

The decoding of the SPC codes is often referred to as the "check node" processing, and the cross-checking of the variables is often referred to as the "variable-node" processing.

In a practical LDPC decoder implementation, sets of SPC codes are decoded in parallel to increase throughput.

In contrast, belief propagation on the binary erasure channel is particularly simple where it consists of iterative constraint satisfaction.

For example, consider that the valid codeword, 101011, from the example above, is transmitted across a binary erasure channel and received with the first and fourth bit erased to yield ?⁠01?⁠11. Since the transmitted message must have satisfied the code constraints, the message can be represented by writing the received message on the top of the factor graph.

In this example, the first bit cannot yet be recovered, because all of the constraints connected to it have more than one unknown bit. In order to proceed with decoding the message, constraints connecting to only one of the erased bits must be identified. In this example, only the second constraint suffices. Examining the second constraint, the fourth bit must have been zero, since only a zero in that position would satisfy the constraint.

This procedure is then iterated. The new value for the fourth bit can now be used in conjunction with the first constraint to recover the first bit as seen below. This means that the first bit must be a one to satisfy the leftmost constraint.

ファイル:Ldpc code fragment factor graph w erasures decode step 2.svg

Thus, the message can be decoded iteratively. For other channel models, the messages passed between the variable nodes and check nodes are real numbers, which express probabilities and likelihoods of belief.

This result can be validated by multiplying the corrected codeword r by the parity-check matrix H:

<math>\mathbf{z} = \mathbf{Hr}

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

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

= \begin{pmatrix} 0 \\ 0 \\ 0 \\ \end{pmatrix}. </math>

Because the outcome z (the syndrome) of this operation is the three × one zero vector, the resulting codeword r is successfully validated.

After the decoding is completed, the original message bits '101' can be extracted by looking at the first 3 bits of the codeword.

While illustrative, this erasure example does not show the use of soft-decision decoding or soft-decision message passing, which is used in virtually all commercial LDPC decoders.

Updating node information

In recent years, there has also been a great deal of work spent studying the effects of alternative schedules for variable-node and constraint-node update. The original technique that was used for decoding LDPC codes was known as flooding. This type of update required that, before updating a variable node, all constraint nodes needed to be updated and vice versa. In later work by Vila Casado et al., alternative update techniques were studied, in which variable nodes are updated with the newest available check-node information.

The intuition behind these algorithms is that variable nodes whose values vary the most are the ones that need to be updated first. Highly reliable nodes, whose log-likelihood ratio (LLR) magnitude is large and does not change significantly from one update to the next, do not require updates with the same frequency as other nodes, whose sign and magnitude fluctuate more widely. These scheduling algorithms show greater speed of convergence and lower error floors than those that use flooding. These lower error floors are achieved by the ability of the Informed Dynamic Scheduling (IDS)

When nonflooding scheduling algorithms are used, an alternative definition of iteration is used. For an (n, k) LDPC code of rate k/n, a full iteration occurs when n variable and n − k constraint nodes have been updated, no matter the order in which they were updated.

Lookup table decoding

It is possible to decode LDPC codes on a relatively low-power microprocessor by the use of lookup tables.

While codes such as the LDPC are generally implemented on high-power processors, with long block lengths, there are also applications which use lower-power processors and short block lengths (1024).

Therefore, it is possible to precalculate the output bit based upon predetermined input bits. A table is generated which contains n entries (for a block length of 1024 bits, this would be 1024 bits long), and contains all possible entries for different input states (both errored and nonerrored).

As a bit is input, it is then added to a FIFO register, and the value of the FIFO register is then used to look up in the table the relevant output from the precalculated values.

By this method, very high iterations can be used, with little processor overhead, the only cost being that of the memory for the lookup table, such that LDPC decoding is possible even on a 4.0 MHz PIC chip.

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

• Robert G. Gallager
• Richard Hamming
• Claude Shannon
• David J. C. MacKay
• Irving S. Reed

Theory

• Belief propagation
• Graph theory
• Hamming code
• Linear code
• Sparse graph code
• Expander code

Applications

• G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable)
• 802.3an (10 Giga-bit/s Ethernet over Twisted pair)
• CMMB(China Multimedia Mobile Broadcasting)
• DVB-S2 / DVB-T2 / DVB-C2 (Digital video broadcasting, 2nd Generation)
• DMB-T/H (Digital video broadcasting)
• WiMAX (IEEE 802.16e standard for microwave communications)
• IEEE 802.11n-2009 (Wi-Fi standard)
• DOCSIS 3.1

Other capacity-approaching codes

• Turbo codes
• Serial concatenated convolutional codes
• Online codes
• Fountain codes
• LT codes
• Raptor codes
• Repeat-accumulate codes (a class of simple turbo codes)
• Tornado codes (LDPC codes designed for erasure decoding)
• Polar codes

Source

http://wikipedia.org/