「Low-density parity-check code」の版間の差分

提供: tezos-wiki
移動先: 案内、 検索
細 (1版 をインポートしました)
 
(2人の利用者による、間の13版が非表示)
1行目: 1行目:
−
In [[information theory]], a '''low-density parity-check''' ('''LDPC''') '''code''' is a [[Linear code|linear]] [[error correcting code]], a method of transmitting a message over a [[signal noise|noisy]] transmission channel. An LDPC is constructed using a sparse [[bipartite graph]]. LDPC codes are [[:Category:capacity-approaching codes|capacity-approaching codes]], which means that practical constructions exist that allow the noise threshold to be set very close (or even ''arbitrarily'' close on the [[binary erasure channel]]) to the theoretical maximum (the [[Shannon-Hartley theorem|Shannon limit]]) for a symmetric memoryless channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative [[belief propagation]] techniques, LDPC codes can be decoded in time linear to their block length.
+
[[情報理論]]では、低密度パリティチェック（LDPCは[[線形コード|線形]] [[エラー訂正符号]]、[[信号雑音|雑音]]伝送チャネルを介してメッセージを送信する方法。
  
−
LDPC codes are finding increasing use in applications requiring reliable and highly efficient information transfer over bandwidth or return channel-constrained links in the presence of corrupting noise. Implementation of LDPC codes has lagged behind that of other codes, notably [[turbo code]]s. The fundamental patent for Turbo Codes expired on August 29, 2013.[https://www.google.com/patents/US5446747 [US5446747<nowiki>]</nowiki>]
+
LDPCはスパースな[[bipartite graph]]を使って構築されます。
  
−
LDPC codes are also known as '''Gallager codes''', in honor of [[Robert G. Gallager]], who developed the LDPC concept in his doctoral dissertation at the [[Massachusetts Institute of Technology]] in 1960.
+
LDPCコードは、[[Category：容量接近コード|容量接近コード]]であり、ノイズしきい値を非常に近い値に設定できるような実用的な構成が存在することを意味したり、[[バイナリ消去チャンネル]]を対称無記憶チャンネルの理論的最大値[シャノン - ハートレー定理|シャノン限界]に変換する。
  
−
==History==
+
雑音閾値はチャネル雑音の上限を定義し、情報損失の可能性が所望のように小さくすることができる。反復的な[[belief propagation]]技術を使用して、LDPC符号は、そのブロック長さに対して時間的にデコードすることができる。
−
Impractical to implement when first developed by Gallager in 1963, LDPC codes were forgotten until his work was rediscovered in 1996. [[Turbo code]]s, another class of capacity-approaching codes discovered in 1993, became the coding scheme of choice in the late 1990s, used for applications such as the [[Deep Space Network]] and [[satellite communication]]s. However, the advances in low-density parity-check codes have seen them surpass turbo codes in terms of [[error floor]] and performance in the higher [[code rate]] range, leaving turbo codes better suited for the lower code rates only.
 
  
−
==Applications==
+
LDPC符号は壊れやすいノイズの存在下で、帯域幅またはリターンチャネル制約リンク上で信頼性が高く、効率的な情報転送を必要とするアプリケーションでますます使用されています。
−
In 2003, an irregular repeat accumulate (IRA) style LDPC code beat six turbo codes to become the error correcting code in the new [[DVB-S2]] standard for the satellite transmission of [[digital television]]. The DVB-S2 selection committee made decoder complexity estimates for the Turbo Code proposals using a much less efficient serial decoder architecture rather than a parallel decoder architecture.
 
  
−
This forced the Turbo Code proposals to use frame sizes on the order of one half the frame size of the LDPC proposals. In 2008, LDPC beat convolutional turbo codes as the [[forward error correction]] (FEC) system for the [[ITU-T]] [[G.hn]] standard. G.hn chose LDPC codes over turbo codes because of their lower decoding complexity (especially when operating at data rates close to 1.0 Gbit/s) and because the proposed turbo codes exhibited a significant [[error floor]] at the desired range of operation.
+
LDPCコードの実装は、他のコード、特に[[ターボコード]]の実装に比べて遅れています。ターボコードの基本特許は2013年8月29日に期限切れとなりました。[https://www.google.com/patents/US5446747 [US5446747＆lt; nowiki＆gt;]＆lt; nowiki＆gt;]
  
−
LDPC codes are also used for [[10GBase-T]] Ethernet, which sends data at 10 gigabits per second over twisted-pair cables. As of 2009, LDPC codes are also part of the [[Wi-Fi]] 802.11 standard as an optional part of [[802.11n]] and [[802.11ac]], in the High Throughput (HT) PHY specification.
+
LDPCコードは1960年に[[Massachusetts Institute of Technology]]で博士論文のLDPCコンセプトを開発した[Robert G. Gallager]の名誉で、 "'Gallager codes' ''としても知られています。
  
−
Some [[OFDM]] systems add an additional outer error correction that fixes the occasional errors (the "error floor") that get past the LDPC correction inner code even at low [[bit error rate]]s.
+
==歴史==
−
For example:
+
1963年にGallagerによって最初に開発されたときに実際に実行することは現実的ではなく、LDPCコードは1996年に再発見されるまで忘れられていた。
−
The [[Reed-Solomon code]] with LDPC Coded Modulation (RS-LCM) uses a Reed-Solomon outer code.
 
−
The DVB-S2, the DVB-T2 and the DVB-C2 standards all use a [[BCH code]] outer code to mop up residual errors after LDPC decoding.
 
  
−
==Operational use==
+
[[Turbo code]]は1993年に発見された容量接近コードの別のクラスで、 1990年代後半には[Deep Space Network]や[Satellite communication]などのアプリケーションに使用されていました。しかし、低密度パリティチェックコードの進歩により、[[エラーフロア]]および高い[[コードレート]]範囲のパフォーマンスに関してターボコードを上回り、ターボコードはより低いコードレートのみに適応だとされるようになりました。
−
LDPC codes functionally are defined by a sparse [[parity-check matrix]]. This [[sparse matrix]] is often randomly generated, subject to the [[sparsity]] constraints—[[#Code construction|LDPC code construction]] is discussed [[#Code construction|later]]. These codes were first designed by Robert Gallager in 1962.
 
  
−
Below is a graph fragment of an example LDPC code using [[factor graph|Forney's factor graph notation]]. In this graph, ''n'' variable nodes in the top of the graph are connected to (''n''−''k'') constraint nodes in the bottom of the graph.
+
==アプリケーション==
 +
2003年に、不規則反復積算（IRA）スタイルのLDPCコードは、[[デジタルテレビ]]の衛星伝送用の新しい[[DVB-S2]]規格の誤り訂正コードになるために、6つのターボコードを破った。 DVB-S2選択委員会は並列デコーダアーキテクチャではなく、はるかに効率の低いシリアルデコーダアーキテクチャを使用してターボコード提案のデコーダ複雑性推定を行った。
  
−
This is a popular way of graphically representing an (''n'', ''k'') LDPC code. The bits of a valid message, when placed on the '''T's''' at the top of the graph, satisfy the graphical constraints. Specifically, all lines connecting to a variable node (box with an '=' sign) have the same value, and all values connecting to a factor node (box with a '+' sign) must sum, [[modular arithmetic|modulo]] two, to zero (in other words, they must sum to an even number; or there must be an even number of odd values).
+
これにより、ターボコード提案はLDPC提案のフレームサイズの1/2のフレームサイズを使用するように強制された。 2008年、LDPCは[ITU-T] [[G.hn]]標準のための畳み込みターボ符号を[前方誤り訂正]（FEC）システムとして打ち勝った。
  
−
[[Image:ldpc code fragment factor graph.svg|none]]
+
G.hnは、（特に1.0Gbit / sに近いデータレートで動作する場合に）復号化の複雑さがより低く、所望の動作範囲において提案されたターボ符号が有意な[[エラーフロア]]を示すため、ターボ符号に対してLDPC符号を選択​​した。
−
Ignoring any lines going out of the picture, there are eight possible six-bit strings corresponding to valid codewords: (i.e., 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). This LDPC code fragment represents a three-bit message encoded as six bits. Redundancy is used, here, to increase the chance of recovering from channel errors. This is a (6, 3) [[linear code]], with ''n'' = 6 and ''k'' = 3.
 
  
−
Once again ignoring lines going out of the picture, the parity-check matrix representing this graph fragment is
+
また、10ギガビット/秒のデータをツイストペアケーブル経由で送信する[[10GBase-T]]イーサネットにもLDPCコードが使用された。 2009年現在、LDPCコードは、ハイスループット（HT）PHY仕様の[[802.11n]]および[[802.11ac]]のオプション部分として[[Wi-Fi]] 802.11標準の一部。
  
−
:<math>
+
いくつかの[[OFDM]]システムは、低[[ビット誤り率]] sであってもLDPC訂正内符号を過ぎた時折の誤り（「エラーフロア」）を修正する追加の外部誤り訂正を追加する。
−
\mathbf{H} =
 
−
\begin{pmatrix}
 
−
1 & 1 & 1 & 1 & 0 & 0 \\
 
−
0 & 0 & 1 & 1 & 0 & 1 \\
 
−
1 & 0 & 0 & 1 & 1 & 0 \\
 
−
\end{pmatrix}.
 
−
</math>
 
  
−
In this matrix, each row represents one of the three parity-check constraints, while each column represents one of the six bits in the received codeword.
+
例えば：
 +
LDPC符号化変調（RS-LCM）による[[リードソロモン符号]]は、リードソロモンの外部符号を使用する。
 +
DVB-S2、DVB-T2およびDVB-C2規格はすべて、[[BCHコード]]外部コードを使用して、LDPC復号後の残留誤差をモップアップする。
  
−
In this example, the eight codewords can be obtained by putting the [[parity-check matrix]] '''H''' into this form <math>\begin{bmatrix} -P^T | I_{n-k} \end{bmatrix}</math> through basic [[row operations]] in [[GF(2)]]:
+
==操作上の使用==
−
:<math>\mathbf{H}
+
LDPC符号は機能的にスパース[[パリティ検査行列]]によって定義される。この[[疎行列]]は、しばしばランダムに生成され、[[希薄性]の制約を受け、[[＃コード構築| LDPCコード構築]] [[＃コード構築|後で]]議論されます。これらのコードは、1962年にRobert Gallagerによって最初に設計されました。
 +
 
 +
以下は、[[factor graph | Forney's factor graph notation]]を使用した例示的なLDPC符号のグラフ断片である。このグラフでは、グラフの最上部にある「n」個の変数ノードは、グラフの最下部にある制約ノード（「 '' n ''〜 '' k''）に接続されています。
 +
 
 +
これは、（ '' n ''、＆nbsp; '' k ''）LDPCコードをグラフィカルに表現する一般的な方法です。有効なメッセージのビットは、グラフの一番上の '' T '' に置かれると、グラフィカルな制約を満たします。
 +
 
 +
具体的には、変数ノード（ '='記号の付いたボックス）に接続するすべての行は同じ値を持ち、因子ノード（ '+'記号の付いたボックス）に接続するすべての値は[[モジュラ算術|モジュロ] ] 2つをゼロにする（換言すると、それらは偶数に合わなければならない、または奇数の偶数がなければならない）。
 +
 
 +
[[画像：ldpcコード断片係数graph.svg |なし]]
 +
ピクチャから出る任意のラインを無視すると、有効なコードワード（すなわち、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}
+
\ begin {pmatrix}
−
1 & 1 & 1 & 1 & 0 & 0 \\
+
1＆1＆1＆1 &&
−
0 & 0 & 1 & 1 & 0 & 1 \\
+
0＆0＆1＆1＆1＆apos;＆apos;＆
−
1 & 0 & 0 & 1 & 1 & 0 \\
+
1＆0＆0＆1＆1 &&
−
\end{pmatrix}_1
+
\ end {pmatrix} _1
−
\sim
+
\ sim
−
\begin{pmatrix}
+
\ begin {pmatrix}
−
1 & 1 & 1 & 1 & 0 & 0 \\
+
1＆1＆1＆1 &&
−
0 & 0 & 1 & 1 & 0 & 1 \\
+
0＆0＆1＆1＆1＆apos;＆apos;＆
−
0 & 1 & 1 & 0 & 1 & 0 \\
+
0＆1＆1＆0 &&
−
\end{pmatrix}_2
+
\ end {pmatrix} _2
−
\sim
+
\ sim
−
\begin{pmatrix}
+
\ begin {pmatrix}
−
1 & 1 & 1 & 1 & 0 & 0 \\
+
1＆1＆1＆1 &&
−
0 & 1 & 1 & 0 & 1 & 0 \\
+
0＆1＆1＆0 &&
−
0 & 0 & 1 & 1 & 0 & 1 \\
+
0＆0＆1＆1＆1＆apos;＆apos;＆
−
\end{pmatrix}_3
+
\ end {pmatrix} _3
−
\sim
+
\ sim
−
\begin{pmatrix}
+
\ begin {pmatrix}
−
1 & 1 & 1 & 1 & 0 & 0 \\
+
1＆1＆1＆1 &&
−
0 & 1 & 1 & 0 & 1 & 0 \\
+
0＆1＆1＆0 &&
−
1 & 1 & 0 & 0 & 0 & 1 \\
+
1＆1＆amp; 0＆lt; 0＆
−
\end{pmatrix}_4.
+
\ end {pmatrix} _4。
−
&lt;/math&gt;
+
＆lt; / math＆gt;
  
−
Step 1: H.
+
ステップ1：H.
  
−
Step 2: Row 1 is added to row 3.
+
ステップ2：行1が行3に追加されます。
  
−
Step 3: Row 2 and 3 are swapped.
+
ステップ3：行2と3を入れ替えます。
  
−
Step 4: Row 1 is added to row 3.
+
ステップ4：行1が行3に追加されます。
  
−
From this, the [[generator matrix]] '''G''' can be obtained as &lt;math&gt;\begin{bmatrix} I_k | P \end{bmatrix}&lt;/math&gt; (noting that in the special case of this being a binary code &lt;math&gt;P = -P&lt;/math&gt;), or specifically:
+
これから、[[生成行列]] '' 'G' ''は、＆lt; math＆gt; \ begin {bmatrix} I_k | P \ end {bmatrix}＆lt; / math＆gt; （これの特別の場合、バイナリコードであることに留意すべきである（P = -P / math））、
  
−
:&lt;math&gt;\mathbf{G}
+
：<math> \ mathbf {G}
 
=
 
=
−
\begin{pmatrix}
+
\ begin {pmatrix}
−
1 & 0 & 0 & 1 & 0 & 1 \\
+
1＆0＆0＆1＆1＆apos;＆apos;＆
−
0 & 1 & 0 & 1 & 1 & 1 \\
+
0＆1＆1＆1＆1
−
0 & 0 & 1 & 1 & 1 & 0 \\
+
0＆0＆1＆1＆1 &&
−
\end{pmatrix}.
+
\ end {pmatrix}。
−
&lt;/math&gt;
+
＆lt; / math＆gt;
  
−
Finally, by multiplying all eight possible 3-bit strings by '''G''', all eight valid codewords are obtained. For example, the codeword for the bit-string '101' is obtained by:
+
最後に、8つの可能なすべての3ビット文字列に '' 'G' ''を掛けることによって、8つの有効なコードワードがすべて得られる。例えば、ビット列「101」の符号語は、
  
−
:&lt;math&gt;
+
：＆lt;数学＆gt;
−
\begin{pmatrix}
+
\ begin {pmatrix}
−
1 & 0 & 1 \\
+
1＆0＆1 \\
−
\end{pmatrix}  
+
\ end {pmatrix}
−
\cdot
+
\ cdot
−
\begin{pmatrix}
+
\ begin {pmatrix}
−
1 & 0 & 0 & 1 & 0 & 1 \\
+
1＆0＆0＆1＆1＆apos;
−
0 & 1 & 0 & 1 & 1 & 1 \\
+
0＆1＆1＆1＆1
−
0 & 0 & 1 & 1 & 1 & 0 \\
+
0＆0＆1＆1＆1 &&
−
\end{pmatrix}
+
\ end {pmatrix}
 
=
 
=
−
\begin{pmatrix}
+
\ begin {pmatrix}
−
1 & 0 & 1 & 0 & 1 & 1 \\
+
1＆0＆1＆0＆1＆1
−
\end{pmatrix}.
+
\ end {pmatrix}。
−
&lt;/math&gt;
+
＆lt; / math＆gt;
  
−
As a check, the row space of '''G''' is orthogonal to '''H''' such that &lt;math&gt; G H^T = 0 &lt;/math&gt;
+
チェックとして、 '' 'G' ''の行空間は、 '' '' ''と直交して、<math> G H ^ T = 0＆lt; / math＆gt;
  
−
The bit-string '101' is found in as the first 3 bits of the codeword '101011'.
+
ビットストリング「101」は、符号語「101011」の最初の3ビットとして検出される。
  
−
== Example Encoder ==
+
==エンコーダの例==
  
−
Figure 1 illustrates the functional components of most LDPC encoders.
+
図1は、ほとんどのLDPCエンコーダの機能コンポーネントを示しています。
  
−
[[File:ext_38dKJsdjh_LDPC encoder Figure.png|thumb|none|500px|Fig. 1. LDPC Encoder]]
+
[[ファイル：ext_38dKJsdjh_LDPCエンコーダ]図.png | thumb | none | 500px | 1. LDPCエンコーダ]]
  
−
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&lt;sub&gt;0,K-1&lt;/sub&gt;) is transmitted with the parity bits (P) to make up the code symbols. The S bits from each constituent encoder are discarded.
+
フレームの符号化の間に、入力データビット（D）が繰り返され、一組の構成エンコーダに分配される。構成エンコーダは典型的にはアキュムレータであり、各アキュムレータはパリティシンボルを生成するために使用される。元のデータ（S 0、K-1 / sub）の単一のコピーがパリティビット（P）とともに送信されて、符号シンボルを構成する。各構成エンコーダからのSビットは廃棄される。
  
−
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).
+
DVB-S2レート2/3符号を使用する例では、符号化されたブロックサイズは43200データビット（K = 43200）および21600パリティビット（M = 21600）を有する64800シンボル（N = 64800）である。各構成符号（検査ノード）は、8データビットを符号化する第1のパリティビットを除いて16データビットを符号化する。第1の4680データビットは13回繰り返され（13個のパリティ符号で使用される）、残りのデータビットは3個のパリティ符号（不規則LDPC符号）で使用される。
  
−
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.
+
比較のために、典型的なターボ符号は、通常、並列に構成された2つの構成符号を使用し、その各々はデータビットの入力ブロック（K）全体を符号化する。これらの構成エンコーダは、フレームの1つのコピーをインターリーブするコードインターリーバによって分離された中程度の深さ（8または16状態）の再帰的畳み込み符号（RSC）である。
  
−
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.
+
これとは対照的に、LDPCコードは、それぞれが入力フレームのごく一部を符号化する多数の低奥行成分符号（累算器）を並列に使用する。多くの構成コードは、反復および分配操作を介して接続された、低深度（2状態）の「畳み込み符号」とみなすことができる。反復および分配動作は、ターボ符号におけるインタリーバの機能を実行する。
  
−
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.
+
様々な構成コードの接続および各入力ビットの冗長度のレベルをより正確に管理する能力は、LDPC符号の設計においてより柔軟性を与え、場合によってはターボ符号よりも良好な性能をもたらす可能性がある。ターボコードは低コードレートではLDPCよりも優れた性能を示しているようですが、少なくとも低レートコードの性能はターボコードでは容易です。
  
−
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.
+
実際問題として、アキュムレータを形成するハードウェアは、符号化プロセス中に再利用される。すなわち、パリティビットの第1セットが生成され、パリティビットが記憶されると、同じアキュムレータハードウェアが、パリティビットの次のセットを生成するために使用される。
  
−
==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.
+
他の符号と同様に、[[2進対称チャネル]]上のLDPC符号の[最尤復号]は[[NP完全]]問題である。有用なサイズのNP完全コードに対して最適な復号を実行することは実用的ではない。
  
−
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 decoder|soft-in-soft-out]] (SISO) techniques such as [[Soft output Viterbi algorithm|SOVA]], [[BCJR algorithm|BCJR]], [[Maximum a posteriori estimation|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.
+
しかしながら、反復的な[信念伝搬]復号に基づく準最適技術は、優れた結果をもたらし、実際に実施することができる。準最適復号化技法は、LDPCを構成する各パリティ検査を独立した単一パリティ検査（SPC）符号として見る。各SPCコードは、[[Soft output Viterbi algorithm | SOVA]]、[[BCJR algorithm | BCJR]]などの[[Soft-in soft-out decoder | soft-in-soft-out]]（SISO） ]、[最大事後推定| MAP]]、およびそれらの他の派生物。各SISO復号化からの軟判定情報は、同じ情報ビットの他の冗長なSPC復号化と相互チェックされ更新される。その後、各SPCコードは、更新された軟判定情報を用いて再び復号される。このプロセスは、有効なコードワードが達成されるか、または復号化が完了するまで反復される。この種の復号化は、しばしば和 - 積復号と呼ばれる。
  
−
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.
+
SPCコードの復号化は、しばしば「チェックノード」処理と呼ばれ、変数のクロスチェックは、しばしば「可変ノード」処理と呼ばれる。
  
−
In a practical LDPC decoder implementation, sets of SPC codes are decoded in parallel to increase throughput.
+
実用的なLDPC復号器の実装では、SPC符号の組が並列に復号されてスループットが向上する。
  
−
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 ?&#8288;01?&#8288;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.
+
例えば、上記の例の有効コードワード101011が2進消去チャネルを介して送信され、受信された第1および第4のビットが消去されて受信され、？⁠01？⁠11が得られると考える。送信されたメッセージはコード制約を満たさなければならないので、メッセージはファクタグラフの上部に受信メッセージを書き込むことによって表すことができる。
  
−
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.
+
この例では、最初のビットは、それに接続されているすべての制約が複数の未知ビットを持っているため、まだ回復できません。メッセージの復号化を進めるためには、消去されたビットの1つのみに接続する制約を識別しなければならない。この例では、第2の制約のみで十分である。第2の制約を調べると、その位置のゼロだけが制約を満たすため、第4のビットはゼロでなければならない。
  
−
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.
+
その後、この手順が反復されます。第4ビットの新しい値は、以下に示すように第1ビットを回復するために第1制約と組み合わせて使用​​できるようになりました。これは、最初のビットが左端の制約を満たすビットでなければならないことを意味します。
  
−
[[Image:ldpc code fragment factor graph w erasures decode step 2.svg|none]]
+
[[画像：ldpcコードフラグメントファクタグラフw消滅デコードステップ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 number]]s, which express probabilities and likelihoods of belief.
+
したがって、メッセージは反復的に復号されることができる。他のチャネルモデルでは、変数ノードとチェックノードの間で渡されるメッセージは[[実数]]であり、信念の確率と可能性を表しています。
  
−
This result can be validated by multiplying the corrected codeword '''r''' by the parity-check matrix '''H''':
+
この結果は、訂正されたコードワード '' 'r' ''にパリティ検査行列 '' 'H' ''を掛けて検証することができる。
  
−
:&lt;math&gt;\mathbf{z} = \mathbf{Hr}
+
：<math> \ mathbf {z} = \ mathbf {Hr}
−
=  
+
=
−
\begin{pmatrix}
+
\ begin {pmatrix}
−
1 & 1 & 1 & 1 & 0 & 0 \\
+
1＆1＆1＆1 &&
−
0 & 0 & 1 & 1 & 0 & 1 \\
+
0＆0＆1＆1＆1＆apos;＆apos;＆
−
1 & 0 & 0 & 1 & 1 & 0 \\
+
1＆0＆0＆1＆1 &&
−
\end{pmatrix}
+
\ end {pmatrix}
  
−
\begin{pmatrix}
+
\ begin {pmatrix}
 
1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\
 
1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\
−
\end{pmatrix}
+
\ end {pmatrix}
  
 
=
 
=
−
\begin{pmatrix}
+
\ begin {pmatrix}
 
0 \\ 0 \\ 0 \\
 
0 \\ 0 \\ 0 \\
−
\end{pmatrix}.
+
\ end {pmatrix}。
−
&lt;/math&gt;
+
＆lt; / math＆gt;
  
−
Because the outcome '''z''' (the [[Decoding methods#Syndrome decoding|syndrome]]) of this operation is the three &times; one zero vector, the resulting codeword '''r''' is successfully validated.
+
この操作の結果 '' 'z' ''（[Decoding methods＃Syndrome decoding | syndrome]）は3回であるため、 1つのゼロベクトル、得られたコードワード '' 'r' ''は首尾よく検証される。
  
−
After the decoding is completed, the original message bits '101' can be extracted by looking at the first 3 bits of the codeword.
+
復号化が完了した後、元のメッセージビット「101」は、符号語の最初の3ビットを見ることによって抽出することができる。
  
−
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.
+
例示的であるが、この消去例は、実質的にすべての商用LDPCデコーダにおいて使用される軟判定復号または軟判定メッセージ通過の使用を示していない。
  
−
=== 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.
+
近年、可変ノードおよび制約ノード更新のための代替スケジュールの影響を研究するために多大な労力が費やされています。 LDPC符号を復号するために使用された元の技術は、「フラッディング」として知られていました。このタイプの更新では、変数ノードを更新する前に、すべての制約ノードを更新する必要があり、その逆も必要でした。後のVila Casadoらの研究では、可変ノードが最新の利用可能なチェックノード情報で更新される代替的な更新技術が研究された。
  
−
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.
+
これらのアルゴリズムの背後にある直感は、値が最も変化する可変ノードが最初に更新する必要があるノードであることです。 [対数尤度比]（LLR）の大きさが大きく、ある更新から次の更新まで大きく変化しない高信頼性ノードは、符号および大きさがより広く変動する他のノードと同じ頻度で更新を必要としない。
−
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)
+
これらのスケジューリングアルゴリズムは、フラッディングを使用する場合よりも収束速度が速く、エラーフロアが低くなります。これらのより低いエラーフロアは、情報付き動的スケジューリング（IDS）能力によって達成され、
  
−
When nonflooding scheduling algorithms are used, an alternative definition of iteration is used. For an (''n'',&nbsp;''k'') LDPC code of rate ''k''/''n'', a full ''iteration'' occurs when ''n'' variable and ''n''&nbsp;&minus;&nbsp;''k'' constraint nodes have been updated, no matter the order in which they were updated.
+
非フロイドスケジューリングアルゴリズムが使用される場合、反復の代替定義が使用される。レート '' k '' / '' n ''のLDPC符号（ '' n ''、＆nbsp; '' k ''）に対して、 '' n ''変数と ' 'n' '＆nbsp;＆nbsp;' 'k' '制約ノードは更新された順序に関係なく更新されました。
  
−
=== Lookup table decoding ===
+
===ルックアップテーブルの復号化===
−
It is possible to decode LDPC codes on a relatively low-power microprocessor by the use of [[lookup table]]s.
+
[[ルックアップテーブル]]を使用して、比較的低電力のマイクロプロセッサ上のLDPCコードを解読することが可能である。
  
−
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).
+
LDPCのようなコードは一般に、長いブロック長を有する高電力プロセッサ上に実装されるが、低電力プロセッサと短いブロック長（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).
+
したがって、所定の入力ビットに基づいて出力ビットを事前計算することが可能である。 'n'個のエントリ（ブロック長1024ビット、これは1024ビット長）を含むテーブルが生成され、さまざまな入力状態（エラーとノン・エラーの両方）のすべての可能なエントリが含まれます。
  
−
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.
+
ビットが入力されると、FIFOレジスタに加算され、FIFOレジスタの値は、事前計算された値から関連する出力をテーブルで検索するために使用されます。
  
−
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&nbsp;MHz PIC chip.
+
この方法では、プロセッサのオーバーヘッドがほとんどなく、ルックアップテーブル用のメモリのコストが僅かで、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]].
+
大きなブロックサイズの場合、LDPC符号は、一般にまず最初にデコーダの動作を調べることによって構成される。ブロックサイズが無限になるにつれて、LDPCデコーダは復号化が確実に達成され、それを超えて復号化が達成されない、[[崖の効果]]と呼ばれる雑音閾値を有することが示される。このしきい値は、チェックノードおよびアークからのアークの最良の割合を変数ノードから見つけることによって最適化することができます。この閾値を視覚化するための近似的なグラフィカルなアプローチは[[EXITチャート]]です。
  
−
The construction of a specific LDPC code after this optimization falls into two main types of techniques:
+
この最適化の後の特定のLDPC符号の構成は、2つの主なタイプの技術に分類される。
  
−
*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.
+
組合せアプローチは、小さなブロックサイズのLDPC符号の特性を最適化するために、または単純な符号器で符号を生成するために使用することができる。
  
−
Some LDPC codes are based on [[Reed–Solomon code]]s, such as the RS-LDPC code used in the [[10 Gigabit Ethernet]] standard.
+
いくつかのLDPC符号は[[10ギガビットイーサネット（登録商標）]]規格で使用されるRS-LDPC符号のような[[リードソロモン符号]]に基づいている。
−
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]].
+
ランダムに生成されたLDPCコードと比較して、[[DVB-S2]]規格で使用されるLDPCコードなどの構造化LDPCコードは、より単純で低価格のハードウェア、特にH行列が[[巡回行列]]。
  
−
Yet another way of constructing LDPC codes is to use [[finite geometry|finite geometries]]. This method was proposed by Y. Kou ''et al.'' in 2001.
+
LDPCコードを構築するさらに別の方法は、[[有限幾何学|有限幾何]]を使用することです。この方法は2001年にY. Kouらによって提案された。
  
−
== See also ==
+
== 関連項目==
  
 
=== People ===
 
=== People ===
255行目: 270行目:
 
*[[Polar code (coding theory)|Polar codes]]
 
*[[Polar code (coding theory)|Polar codes]]
  
−
==Source==
+
==ソース==
  
 
[http://wikipedia.org/ http://wikipedia.org/]
 
[http://wikipedia.org/ http://wikipedia.org/]

2018年4月25日 (水) 08:21時点における最新版

情報理論では、低密度パリティチェック（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デコードが可能な非常に高い反復を使用できます。

コード構築[編集]

大きなブロックサイズの場合、LDPC符号は、一般にまず最初にデコーダの動作を調べることによって構成される。ブロックサイズが無限になるにつれて、LDPCデコーダは復号化が確実に達成され、それを超えて復号化が達成されない、崖の効果と呼ばれる雑音閾値を有することが示される。このしきい値は、チェックノードおよびアークからのアークの最良の割合を変数ノードから見つけることによって最適化することができます。この閾値を視覚化するための近似的なグラフィカルなアプローチはEXITチャートです。

この最適化の後の特定のLDPC符号の構成は、2つの主なタイプの技術に分類される。

  • 疑似ランダムアプローチ
  • コンビナトリアルアプローチ

擬似ランダムアプローチによる構築は、大きなブロックサイズの場合、ランダム構造が良好な復号性能を与えるという理論的結果に基づいている。無限ブロックサイズの理論上の限界で期待される所望の特性が有限ブロックサイズで生じることを保証するために、様々な制約が適用されることが多い。

組合せアプローチは、小さなブロックサイズのLDPC符号の特性を最適化するために、または単純な符号器で符号を生成するために使用することができる。

いくつかのLDPC符号は10ギガビットイーサネット（登録商標）規格で使用されるRS-LDPC符号のようなリードソロモン符号に基づいている。 ランダムに生成されたLDPCコードと比較して、DVB-S2規格で使用されるLDPCコードなどの構造化LDPCコードは、より単純で低価格のハードウェア、特にH行列が巡回行列。

LDPCコードを構築するさらに別の方法は、有限幾何を使用することです。この方法は2001年にY. Kouらによって提案された。

関連項目[編集]

People[編集]

Theory[編集]

Applications[編集]

Other capacity-approaching codes[編集]

ソース[編集]

http://wikipedia.org/

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