Burst error-correcting code
コーディング理論では、バースト誤り訂正符号は、互いに独立して発生するのではなく、連続する多数のビットに生じる誤りであるバースト誤りを訂正する方法を採用している。
ランダムエラーを修正するための多くのコードが設計されています。しかしながら、チャネルは、短い間隔で局在するエラーを導入することがある。このような誤りはバースト（多数の連続したビットで発生するため[[バースト誤り]と呼ばれる）で発生する。バーストエラーの例は、記憶媒体に広範囲に見出すことができる。これらのエラーは、ディスク上の傷や無線チャネルの場合の雷のストロークなどの物理的な損傷によるものです。彼らは独立していません。それらは空間的に集中しがちである。 1つのビットにエラーがある場合、隣接するビットも壊れている可能性があります。ランダムエラーを修正するために使用される方法は、バーストエラーを修正するのに非効率的である。
目次
定義[編集]
フレーム付き|中央|長さのバースト5 長さ<math> \ ell </ math> 'のバーストは、
ここで、符号語は、以下のように表される。が送信され、<数学式> Y = C + Eとして受信される。そして、誤差ベクトルは、以下の式で表される。は、長さのバーストと呼ばれる。 <数学> E mathの非ゼロ成分が、は、<math> \ ell </ math>に限定される。連続するコンポーネント。例えば、<数学> E =（0 \ textbf {1000011} 0）</ math>は、長さのバーストである。ここで、は、長さのバーストである。
この定義はバーストエラーが何であるかを説明するには十分ですが、バーストエラー修正用に開発されたツールの大半はサイクリックコードに依存しています。これは我々の次の定義を動かす。
長さの周期的バーストは、以下の式で表される。
： 'Proof' <math> w </ math>は、<math> E </ math>のハミングウェイト（または非ゼロエントリの数）とする。次に、<数学> E math＆gt;厳密には【数1】となる。エラーの説明。ここで、w = 0,1、...、mathについては、証明するものは何もありません。したがって、以下の式が成り立つと仮定する。記述が同一ではないことを示しています。我々は、＆lt; math＆gt; E＆lt; / math＆gt;パターン内に出現することになるので、<数学> E math＆gt;パターンに含まれていない場合、最後のゼロでないエントリの後に始まり、パターンの最初のゼロではないエントリの直前に続くゼロの循環実行を形成します。この実行に対応する索引の集合をゼロ実行と呼びます。我々は直ちに、各バースト記述がそれに関連したゼロランを有し、各ゼロランが不連続であることを観察する。我々は、＆lt; math＆gt; w＆lt; / math＆gt;ゼロランであり、それぞれが互いに素である場合には、合計で、＆lt; math＆gt; n-w＆/ math＆gt;すべてのゼロランにおける明確な要素。一方、私たちは：
- ＆lt;数学＆gt; \ begin {align}
n-w = \ text {0の数} E＆=（n - \ mathrm {length}（P_1））+（n - \ mathrm {length}（P_2））\\ ＆= 2n - \ left（\ mathrm {length}（P_1）+ \ mathrm {length}（P_2）\ right）\\ ＆\ geqslant 2n - （n + 1）&& \ mathrm {length}（P_1）+ \ mathrm {length}（P_2）\ leqslant n + 1 \\ = = n-1 \ end {align}＆lt; / math＆gt; これは、＆lt; math＆gt;とは矛盾します。＆lt; / math＆gt;従って、バーストエラー記述は同一である。
上記の定理の必然的は、長さ<math> \ tfrac {1} {2}（n + 1）のバーストに対して2つの異なるバースト記述を持つことができないことである。
バースト誤り訂正のためのサイクリック符号[編集]
Cyclic code sは、以下のように定義される。【数1】を考える。 <math> \ mathbb {F} _q </ math>の要素としてのシンボルさて、単語を多項式と考えることができます。これは、<math> \ mathbb {F} _q、＆lt; / math＆gt;単語の個々の記号は多項式の異なる係数に対応する。巡回符号を定義するために、生成多項式と呼ばれる固定多項式を選択します。この巡回符号の符号語は、この生成多項式で割り切れるすべての多項式である。
コードワードは、次式の多項式である。【数1】【数2】ここで、生成多項式g（x）/ mathは、次の数式を有する：【数1】である。次数の多項式は以下の通りである。【数1】【数2】 g（x）</ math>で割り切れる、 （x）を乗算した結果。次式の多項式によって定義される。【数1】【数2】本発明者らは、以下を有する。【数1】q ^ {n-r}そのような多項式。それらの各々はコードワードに対応する。したがって、<math> k = n-r </ math>巡回符号の場合。
サイクリック・コードは、長さのすべてのバーストを検出することができる。本発明者らは、後に、任意の（n、k）個のビットのバースト誤り検出能力が、コードは、上から\ math \ leqslant n-k＆lt; / math＆gt;によって限定される。サイクリック・コードは、バースト・エラー検出に最適と考えられます。これは、この上限を満たしているためです。
： '定理（サイクリックバースト訂正能力）' 次数の生成多項式を有するすべての巡回符号は、は、長さのすべてのバーストを検出することができる。
： 'Proof。' 長さのバーストを追加すると、＆lt; rathslant r＆/ math＆gt; （すなわち、<math> g（x）</ math>で割り切れる多項式）に変換すると、その結果はコードワードにならない（すなわち、対応する多項式は<math> g（x））を計算する。長さのバーストが存在しないことを示すことは十分である。は、【数1】によって割り切れる。このようなバーストは、以下の形式を有する。ここで、は、次式のように表される。ここで、\ deg（b（x））＆lt; r。＆lt; / math＆gt;したがって、以下の数式（1）のように表すことができる。は、【数1】によって割り切れない。 （後者は次数を有するため、r≠m）。 （x）とすると、以下のようになる。は、<math> x </ math>によって割り切れない。 （そうでなければ、すべてのコードワードは<math> 0 </ math>で始まる）。したがって、<数学> x ^ i </数学>は、【数1】によって割り切れない。同じように。
上記の証拠は、巡回符号におけるバースト誤り検出/訂正のための単純なアルゴリズムを提案している：送信されたワード（すなわち、次数の多項式）が与えられた場合、分割されたときにこのワードの残りを計算する（x）/ mathによって計算される。余りがゼロである場合（すなわち、単語が<math> g（x）</ math>で割り切れる場合）、それは有効なコードワードである。それ以外の場合は、エラーを報告してください。このエラーを修正するには、この剰余を送信ワードから差し引きます。減算結果は、以下の式で割り切れることになる。g（x）</ math> （すなわち、有効な符号語になる）。
巡回符号は、バースト誤り検出の上界（＆lt; math＆gt; ell \ lslant nk = r / math＆gt;）によって、長さが「全部」のバーストを検出することができないことを知っている。 ; r </ math>である。しかし、サイクリック符号は、実際には、長さ<数>の「最大」バーストを検出することができる。 r </ math>である。これは、バーストが<math> g（x）</ math>で割り切れる場合にのみ検出が失敗するためである。バイナリアルファベットには、2 ^ {\ ell-2}＆lt; / math＆gt;長さ<math> \ ell </ math>のバーストである。これらのうち、<math> 2 ^ {\ ell-2-r} </ math>は、【数1】によって割り切れる。したがって、長さのすべてのバーストにわたって均一な分布を仮定して、検出失敗確率は非常に小さい（τ2 { - r}τm /τmath）。 バーストを異なるコセットに分類することによって、効率的なバースト誤り訂正符号を設計するのに役立つ巡回符号に関する基本的な定理を検討する。
「線形符号」は、「線形符号」である。「線形符号」は、線形符号であり、は、長さ| rslant | ell | / math |のバーストエラーがすべて訂正された場合、<math> \ ell </ math> - バーストエラー訂正コードである。は、[数1] C [math]の異なるcosetにある。
\ mathbf {e} _2＆lt; / math＆gt; \ mathbf {e} _1、\ mathbf {e} _2＆lt; / math＆gt;長さ<math>の別個のバーストエラーでなければならない。 \ leqslant \ ell＆lt; / math＆gt;これはコードの同じコセット内にある。それから、＆lt; math＆gt; \ mathbf {c} = \ mathbf {e} _1 - \ mathbf {e} _2＆lt; / math＆gt;コードワードです。したがって、もし我々が＆lt; math＆gt; \ mathbf {e} _1、＆lt; / math＆gt; \ mathbf {0}＆lt; / math＆gt;に解読することができます。または<math> \ mathbf {c} </ math>。対照的に、全てのバースト誤りが、もし、すべてのバースト誤りが、 ＆lt; math＆gt; \ mathbf {e} _2＆lt; / math＆gt;同じコセットに存在しない場合、各バーストエラーはシンドロームによって決定されます。このエラーは、そのシンドロームによって訂正することができます。このようにして、線形符号は次のようになる。は、長さ| rslant | ell | / math |のバーストエラーがすべて訂正された場合に限り、かつ、 <数学> C <数学>の異なるコセットにある。
： '定理（バーストエラーコードワード分類）' '線形の誤り訂正符号であってもよい。次に、長さ<math> \ leqslant 2 \ ell </ math>の長さの非ゼロバーストは、コードワードにすることができます。
： '証明' '<math> c </ math>長さのバーストを有するコードワードとすることができる。【数2】したがって、それは、以下のパターンを有する。（0,1、u、v、1,0）</ math>ここで、<math> u </ math> ＆lt;数学＆gt; v＆lt;数学＆gt;は、長さが＆lt; math＆gt; \ leqslant \ ell -1の単語である。＆lt; / math＆gt;したがって、単語w =（0,1、u、0,0,0）</ math>は、 c-w =（0,0,0、v、1,0）</ math>は、2つのバーストの長さであり、 \ leqslant \ ell＆lt; / math＆gt;となります。バイナリ線形コードの場合、それらは同じコセットに属します。これは、Distinct Cosets Theoremと矛盾するので、長さ＆lt; math＆gt; \ leqslant 2 \ ell＆/ math＆gt;コードワードにすることができます。
バーストエラー訂正の境界[編集]
バーストエラーの検出と修正の上限[編集]
上限は、決して超えられないエラー検出能力の限界を意味します。ここで、<math>（n、k）</ math>長さ</ math> \ leqslant \ ellのすべてのバーストエラーを検出することができるコード。求めるべき自然な質問は以下の通りである。与えられた<math> n </ math> ＆lt; math＆gt; k＆lt; / math＆gt;とは、最大＆lt; math＆gt;私たちはそれ以上に達成できないのですか？言い換えれば、長さ<math> \ ell </ math>の長さの上限は何ですか？ （n、k）＆lt; / math＆gt;を使用して検出することができるバーストの数は、コード？以下の定理は、この質問に対する答えを提供する。
：バースト誤り検出能力（バースト誤り検出能力）：バースト誤り検出能力は、コードは<math> \ ell \ leqslant n-kです。＆lt; / math＆gt; ： 'Proof' まず、コードは長さのすべてのバーストを検出することができることを観測する。 2つのコードワードが長さのバーストによって異なる場合にのみ、およびそのコードワードの長さが異なる。ここで、2つのコードワードがあるとする。ここで、mathは、mathbf {c} _1＆lt; / math＆gt; ＆lt; math＆gt; \ mathbf {c} _2＆lt; / math＆gt; mathbf {b}＆lt; / math＆gt;とは異なるバーストである。長さ</ math> \ leqslant \ ell </ math>の長さである。 <math> \ mathbf {c} _1 </ math>を受信すると、送信された単語が本当に<math> \ mathbf {c} _1 </ math> \ mathbf {c} _2＆lt; / math＆gt;であるかどうかを判断する。バーストエラー<math> \ mathbf {b}＆lt; / math＆gt;送信中に発生したここで、2つの符号語ごとに、長さのバースト以上に異なると仮定する。送信された符号語<math> \ mathbf {c} _1 </ math> \ mathbf {b}＆lt; / math＆gt;というバーストによってヒットされます。長さ<math> \ ell </ math>の場合、それは別の有効なコードワードに変化することはない。それを受け取ると、これは＆lt; math＆gt; \ mathbf {c} _1＆lt; / math＆gt; ＆lt; math＆gt; \ mathbf {b}。＆lt; / math＆gt;上記の知見により、2つのコードワードが第1のn-1個のシンボルを共有することはできないことがわかる。シンボル。なぜなら、他のすべての＆lt; math＆gt; \ ell＆/ math＆gt;それらは、長さ<math> \ ellのバーストによって依然として異なるようになるであろう。従って、符号語の数は以下のようになる。は、以下の式を満足する。【数18】は、【数18】を満たす。 ＆lt; math＆gt; \ log_q＆lt; / math＆gt;を適用すると、両側に並び替えると、<math> \ ell \ leqslant n-k </ math>がわかります。
ここで、同じ問題を繰り返すが、誤り訂正のために：与えられた<math> n </ math> ＆lt; math＆gt; k＆lt; / math＆gt;の長さの上限は何ですか？ ＆lt; math＆gt;（n、k）＆lt; / math＆gt;関数を使用して訂正できるバーストの数は、コード？以下の定理は、この質問に対する予備的な答えを提供する。
「バースト誤り訂正能力」とは、「バースト誤り訂正能力」である。「バースト誤り訂正能力」とは、バースト誤り訂正能力である。符号は、【数1】を満たすことを特徴とする請求項1に記載の方法。
： 'Proof' まず、コードは長さのすべてのバーストを修正することができることを観察します。\ leqslant \ ell＆/ math＆gt; 2つのコードワードが長さの2つのバーストの合計によって異なる場合にのみ、そして、そのコードワードの長さは、長さ| leqslant | ellである。ここで、2つの符号語【数18】が、 ＆lt; math＆gt; \ mathbf {c} _2＆lt; / math＆gt;は、バーストによって異なる。<math> \ mathbf {b} _1＆lt; / math＆gt; ＆lt; math＆gt; \ mathbf {b} _2＆lt; / math＆gt;長さ</ math> \ leqslant \ ell </ math>各。 <math> \ mathbf {c} _1 </ math>を受信すると、 math＆gt; \ mathbf {b} _1＆lt; / math＆gt;と衝突すると、それは\ mathbf {c} _2＆lt; / math＆gt;バースト<math> - \ mathbf {b} _2 </ math>によって打たれる。送信された単語が<math> \ mathbf {c} _1 </ math>かどうかは分かりません。または、<math> \ mathbf {c} _2 </ math>。ここで、2つの符号語ごとに、2つ以上の長さのバーストが異なると仮定する。送信された符号語<math> \ mathbf {c} _1 </ math>長さ<math> \ ell </ math>のバーストによって打たれると、別のバーストによってヒットした別のコードワードのようには見えない。それぞれの符号語について、<math> \ mathbf {c}、</ math> <math> B（\ mathbf {c}）＆lt; / math＆gt;は、<math> \ mathbf {c}＆lt; / math＆gt;と異なるすべての単語の集合を表す。長さ<math> \ leqslant \ ellのバースト分だけ増加する。ここで、<math> B（\ mathbf {c}）＆lt; / math＆gt; <math> \ mathbf {c}＆lt; / math＆gt;を含む。自体。上記の観察により、我々は、2つの異なるコードワードについて、以下の式が成り立つことを知っている。【数1】ここで、 \ mathbf {c} _j、B（\ mathbf {c} _i）＆lt; / math＆gt; ＆lt; math＆gt; B（\ mathbf {c} _j）＆lt; / math＆gt;互いに素である。我々は、以下を有する。【数1】コードワード。したがって、次のように表すことができます。<math> q ^ k | B（\ mathbf {c}）| \ leqslant q ^ n </ math>。さらに、我々は、【数1】を有している。【数2】【数3】【数4】【数5】後者の不等式を前者の式に差し込むことにより、基底をとると、qは次のようになる。対数と並べ替え、上記の定理を得る。 より強力な結果がRieger境界によって与えられる：
： '定理（Rieger bound）' <math> \ ell＆lt; / math＆gt; （n、k）/ mathのバースト誤り訂正能力である。線形ブロック符号とすると、【数1】は、【数2】である。
： 'Proof。' '長さの任意のバーストパターンを修正することができる任意の線形コードは以下の通りである。は、長さのバーストを有することができない。【数2】【数3】コードワードとして。それが長さのバーストを有していた場合には、次式が成り立つ。コードワードとして、その後、長さのバーストが得られる。コードワードを長さのバーストパターンに変更することができる。このバーストパターンは長さのバーストエラーを生成することによっても得ることができる。このバーストエラーは長さ| ell | / math |である。すべてのゼロ符号語で。ベクトルが第1の2次の零点で非零である場合、ベクトルは、それらの差が長さのバーストのコードワードではないように、アレイの異なるサブセットからのものでなければならない[2]、[3]。この条件を保証するために、そのようなサブセットの数は少なくともベクトルの数に等しい。したがって、サブセットの数は、少なくとも【数1】となる。したがって、我々は、少なくとも【数1】を有する。そうでなければ、2つのそのような多項式の差は、長さが2のバーストの和であるコードワードとなる。【数1】ここで、したがって、これはRieger Boundを証明します。
上記のリーガー境界を達成する線形バースト誤り訂正符号は、最適バースト誤り訂正符号と呼ばれる。
バースト誤り訂正の更なる限界[編集]
多段階バースト訂正（MPBC）のための線形ブロックコードの達成可能なコードレートには、複数の上限がある。このような境界の1つは、すべてのサブブロック内の最大訂正可能な周期的バースト長、または等価的に、各フェーズバースト内の最小エラーフリー長またはギャップに関する制約に制約される。この境界は、単一バースト訂正の境界の特別な場合に低減されると、周期バースト長がブロック長の半分未満であるとき、Abramson境界（バースト誤り訂正のためのハミング境界の結果）である。
（1）{2}（n + 1）、＆lt; / math＆gt; 2進アルファベットには、<数学> n2 ^ {\ ell-1} + 1 </ math>長さ| n | / math |のベクトルである。これは、長さ<math> \ leqslant \ ell </ math>のバーストである。== 一般に、巡回符号はバースト誤りを検出するための強力なツールであるが、ここでは良好な単一バースト誤り訂正能力を有する「消火符号」という2進巡回符号のファミリについて検討する。例えば、長さ<math> \ ell </ math>の単一バーストにより、受信されたコードワードが有する全てのエラーは、一定のスパン内にあることを意味する。数字。
p（x）</ math>とする。次の次数の[既約多項式]とする。 mathbb {F} _2＆lt; / math＆gt;とし、<math> p </ math>は、p（x）の期間とする。数式（1）の周期は、実際には多項式の最小正の整数であると定義される。 （x）| x ^ r-1となるようにする。 <math> \ ell </ math>とする。は、以下の式を満足する正の整数であることが好ましい。そして、【数1】となる。 <math> p </ math>で割り切れない場合、<math> p </ math>は、p（x）の期間である。火災コードを定義する＆lt; math＆gt; G＆lt; / math＆gt;次の生成多項式によって求められます。
（x）=左（x ^ {2 \ ell -1} +1 \ right）p（x）。
ここで、<数学> G </数学>は、<math> \ ell </ math> - バースト誤り訂正符号である。
（p（x）、x ^ {2 \ ell-1} +1 \ right）= 1であることを特徴とする請求項1に記載の方法。
： '証明' 'とする。d（x）</ math> 2つの多項式の最大公約数とする。ここで、P（x）</ math>は、は、既約ではないので、【数1】は、 （p（x））/ mathである。以下のように仮定する。【数1】【数2】ここで、 （x）= c d（x）/ math ...いくつかの定数については以下のようになる。c c / math。但し、（1 / c）p（x）/ mathは、は、【数2】の約数であり、x ^ {2 \ ell -1} + 1 /ここで、d（x）</ math>は、は、【数2】の約数であり、x ^ {2 \ ell -1} + 1÷mathである。しかし、これは、以下の仮定と矛盾する。【数1】は、x ^ {2 \ ell -1} + 1を除算しない。このようにして、以下のようになる。【数1】【数2】補題を証明する。 【数2】が補題p（x）| p（x）| xのp次の多項式であるならば、 ^ k-1＆lt; / math＆gt; ＆lt; math＆gt; p | k＆lt; / math＆gt;
（1 + x ^ p + x ^ {1）}とすると、【数1】【数2】となる。 2p} + \ ldots + x ^ {k / p}）</ math>。したがって、<数学関数> p（x）| x ^ k-1である。
：ここで、＆lt;数学＆gt; p（x）| x ^ k-1 </ math>。そして、<math> k \ geqslant p </ math>。ここで、<math> k </ math>は、は、<math> p </ math>によって割り切れる。 <math> k </ math>上で誘導することによって計算される。基底の場合k = p </ math>続く。したがって、<math> k> p </ math>。我々は、以下のことを知っている：【数1】 （それは期間<数学> p <数学>を有するので）両方を分ける
（1 + x + \ ldots + x ^ {p-1} \ right）\ quad \ text {and} \ quad x ^ k - 1 =（x-1）\ left（1 + x + \ ldots + x ^ {k-1} \ right）。
：ただし、<数学関数> p（x）</ math> （1 + x + ldots + x ^ {p-1}）</ math>の両方を分割しなければならない。 （1 + x + \ ldots + x ^ {k-1}）・math＆gt;したがって、最後の2つの多項式、すなわち、【数1】の差をまた分割する。そして、以下のようになる。【数1】ここで、p（x） （1 + x + \ cdots + x ^ {p-k-1}）/ mathを除算する。最後に、以下の式もまた除算する。【数1】【数2】【数3】【数4】【数5】【数6】をさらに除算する。帰納仮説により、<math> p | k-p </ math>、<math> p | k / mathである。
補題2に当てはまることは、以下のようになることである。すなわち、p（x）= x ^ p-1であるからである。は、期間p <math>を有する場合、<数学> p（x）</ math> <math> x ^ k-1 </ math>は、 ＆lt; math＆gt; p | k＆lt; / math＆gt;
【数1】【数2】【数3】【数3】【数4】【数5】【数6】【数7】【数8】【数8】【数8】【数8】【数8】【数8】である。シンボルエラー。ここで、バイナリRS符号<Math> G '</ math>を構築する。 <数学> G <数学>から。各シンボルは、＆lt; math＆gt; \ lceil \ log_2（255）\ rceil = 8＆lt; / math＆gt;ビット。したがって、バイナリRSコードは、<math> [2040,1784,33] _2 </ math>そのパラメータとして。それは長さの任意の単一のバーストを訂正することができる。
インターリーブドコード[編集]
インタリーブは、畳み込み符号をランダム誤り訂正器からバースト誤り訂正器に変換するために使用される。インタリーブされたコードの使用の背後にある基本的な考え方は、受信機でシンボルをジャングルすることです。これは、密接に位置する受信された誤りのバーストのランダム化につながり、次いで、ランダムチャネルの分析を適用することができる。したがって、送信機におけるインターリーバによって実行される主な機能は、入力シンボルシーケンスを変更することである。受信機では、デインタリーバは受信したシーケンスを変更して、元の変更されていないシーケンスを送信機に戻す。
インターリーバのバースト誤り訂正能力[編集]
： 'Theorem' 'あるコードのバースト誤り訂正能力が<math> \ ell、</ math>そのラムダ・インターリーブ・インターリーブのバースト誤り訂正能力は、<math> \ lambda \ ellである。 ： 'Proof：' 私たちが＆lt; math＆gt;（n、k）＆lt; / math＆gt; ＆lt; / math＆gt; \ leqslant \ ellのすべてのバーストを訂正することができるコード。 インターリーブは、＆lt; math＆gt;（\ lambda、\ lambda k）＆lt; / math＆gt;長さのすべてのバーストを修正することができるコードは、次のようになる。任意の与えられた＆lt; math＆gt; \ lambda / math＆gt;インターリービングを使用して任意の長さのメッセージを符号化したい場合には、まず、それを長さ<lathda> \ lambda k </ math>のブロックに分割する。我々は、＆lt; math＆gt; \ lambda k＆lt; / math＆gt;各ブロックのエントリーは、＆lt; math＆gt; \ lambda \ times k＆lt; / math＆gt;行優先順序を使用して行列を作成します。次に、各行を＆lt; math＆gt;（n、k）＆lt; / math＆gt;コード。私たちが得ることは、＆lt; math＆gt; \ lambda \ times n＆lt; / math＆gt;マトリックス。今、この行列が読み出され、列の大きな順に送信されます。トリックは、長さのバーストが発生した場合には、h <math> h </ math>送信されたワードにおいては、各行は、およそ| math> \ tfrac {h} {\ lambda} / math＆gt; （より具体的には、各行は、少なくとも<math> \ lfloor \ tfrac {h} {\ lambda} \ rfloor </ math>および最大でも\ lceil \ tfrac {h } {\λ} \ rceil＆lt; / math＆gt;）。 <math> h \ leqslant \ lambda \ ell、</ math> ＆lt; math＆gt; \ tfrac {h} {\ lambda} \ leqslant \ ell＆lt; / math＆gt; <math>（n、k）</ math>は、コードは各行を修正できます。したがって、インターリーブされた＆lt; math＆gt;（\ lambda、\ lambda k）コードは、長さのバーストを修正することができる。逆に、＆lt; math＆gt; h＆gt; \ lambda \ ell、＆lt; / math＆gt;少なくとも1つの行は、<math> \ tfrac {h} {\ lambda} / math＆gt; math>（n、k）</ math>とすると、コードがそれらを修正するのに失敗することがあります。したがって、インターリーブされた（誤り訂正符号）の誤り訂正能力は、コードは正確には＆lt; math＆gt; \ lambda \ ellです。＆lt; / math＆gt;インターリーブされたコードのBEC効率は、元の（n、k）と同じままである。コード。これは、 次のようになる。【数1】【数2】【数3】【数4】【数5】【数6】
ブロックインタリーバ[編集]
下の図は、4 x 3インターリーバを示しています。 フレーム付き|センター|ブロックインタリーバの例
上記インタリーバは、ブロックインターリーバと呼ばれる。ここで、入力シンボルは、行に順次書き込まれ、出力シンボルは、列を順次読み取ることによって得られる。したがって、これは、M \ timesN / mathの形である。アレイ。一般に、<Nath> N </ math>は、コードワードの長さです。
ブロックインタリーバの容量 '：' m '> M'回N </ math>ブロックインターリーバおよび長さのバーストは、以下のようになる。エラー数の上限は<math> \ tfrac {\ ell} {M}である。＆lt; / math＆gt;これは、出力列を賢く読んでおり、行数が<math> M </ math>であることから明らかである。最大の誤り訂正能力のための上記の定理により、以下のようになる。許容される最大バースト長は<Math> Mtである。 <math> Mt + 1 </ math>のバースト長の場合、デコーダは失敗する可能性がある。
ブロックインターリーバの効率（<γ> /γ</ math>）： 'デコーダがインタリーバメモリに失敗する可能性のあるバースト長の比率を取ることによって発見される。このようにして、<math> \ gamma </ math>として
【数1】【数2】【数3】【数4】【数5】【数6】 ブロックインタリーバの欠点：図から明らかなように、列は連続して読み込まれ、受信者は完全なメッセージを受け取った後でなければ1行しか解釈できません。また、受信機は、受信されたシンボルを格納するためにかなりの量のメモリを必要とし、完全なメッセージを格納しなければならない。したがって、これらの要因は2つの欠点、1つは待ち時間であり、もう1つは記憶装置（かなり大きな量のメモリ）である。これらの欠点は、以下に説明する畳み込みインタリーバを用いることによって回避することができる。
畳み込みインタリーバ[編集]
クロスインタリーバは、マルチプレクサ - デマルチプレクサシステムの一種である。このシステムでは、遅延線が徐々に長さを増加させるために使用される。遅延線は、基本的に、ある時間だけ信号を遅延させるために使用される電子回路である。ここで、nは整数である。は、遅延線の数であり、<数学> d <数学>各遅延線によって導入される記号の数とする。したがって、連続入力間の分離= <math> nd </ math>符号語の長さをmとすると、符号語の長さをLとする。したがって、入力コードワード内の各記号は異なる遅延線上にある。長さ<math> \ ell </ math>のバーストエラーとする。発生する。連続するシンボル間の分離は<math> ndであるので、</ math>デインタリーブされた出力が含むことができるエラーの数は、<math> \ tfrac {\ ell} {nd + 1}である。上記の定理により、許容できる最大バースト長は、（n-d + 1）（t-1）までの誤り訂正能力のために、【数18】までである。バースト長さが（n-d + 1）（t-1）+ 1のとき、<math>デコーダが失敗することがあります。 framed | center |畳み込みインタリーバの例 framed | center |デインタリーバの例
'インターリーバの効率（<math> \ gamma </ math>）：' これは、デコーダがインタリーバメモリに失敗する可能性があるバースト長の比を取ることによって見出される。この場合、インタリーバのメモリは、
（0 + 1 + 2 + 3 + \ cdots +（n-1））d = \ frac {n（n-1）} {2} dである。
このようにして、<math> \ gamma </ math>次のように：
（n-1）} {2}とすると、以下のようになる。
'インターリーバの性能：' '上記インターリーバの図に示されているように、出力は各遅延線の終わりに生成された対角線のシンボルに過ぎません。この場合、入力マルチプレクサスイッチが約半分のスイッチングを完了すると、受信機で第1行を読み取ることができる。したがって、最初の行を読み取るには、受信側に最大約半分のメッセージを格納する必要があります。これにより、ストレージ要件が大幅に半減します。最初の行を読み取るのに半分のメッセージしか必要とされないので、待ち時間も半分に短縮され、これはブロックインタリーバを上回る良好な改善である。したがって、総インターリーバメモリは、送信機と受信機との間で分割される。
アプリケーション[編集]
コンパクトディスク[編集]
誤り訂正符号なしでは、デジタルオーディオは技術的に実現可能ではない。 リードソロモン符号は、すべてのビットが間違っているシンボルを訂正できるのと同じように、単一のビットエラーで壊れたシンボルを訂正できます。これにより、RS符号はバースト誤りを訂正するのに特に適している。
CDプロセスは、以下のサブプロセスのシーケンスとして抽象化することができます。 - ＆gt;信号源のチャネル符号化 - ＆gt;マスターディスクを作成し、ユーザーディスクを作成し、再生中にユーザーディスクに埋め込まれた信号を感知するメカニカルサブプロセス - チャンネル - ＆gt;ユーザディスクから感知された信号を復号する このプロセスはバーストエラーとランダムエラーの両方を受けます。＆lt; ref name = "Algebraic Error Control Codes" /＆gt;バーストエラーは、ディスク材料（アルミニウム反射膜の欠陥、透明ディスク材料の反射率不良）、ディスク製造（ディスク形成およびディスク切断中の欠陥）、ディスク取り扱い（スクラッチ - 一般に薄い、放射状および直交する記録の方向）と再生機構の違いがある。ランダムエラーには、再構築された信号波のジッタと信号の干渉によるものが含まれます。 CIRC（[クロスインターリーブドリードソロモン符号|クロスインターリーブドリードソロモン符号]）は、CD処理における誤り検出及び訂正の基礎となる。これは、エラーバーストを最大3,500ビット（CD表面に見られるように長さ2.4mm）まで修正し、マイナースクラッチに起因する可能性のある最大12,000ビット（8.5＆nbsp; mm）のエラーバーストを補正します。
'エンコーディング：' 音波はサンプリングされ、A / Dコンバータによってデジタル形式に変換されます。音波は振幅（44.1＆nbsp; kHzまたは44,100ペア、ステレオサウンドの左右のチャンネルごとに1つ）でサンプリングされます。ある時点での振幅には、長さ16のバイナリ列が割り当てられる。したがって、各サンプルは、以下の2つのバイナリベクトルを生成する。または4 4 \ mathbb {F} _2 ^ {8} </ math>データのバイト。録音された1秒ごとに44,100＆nbsp; 32 = 1,411,200ビット（176,400バイト）のデータが生成されます。＆lt; ref name = "Lin、Shu" /＆gt; 1.41 Mbit / sのサンプリングされたデータストリームは、最終的に1.88 Mbit / sのストリームに変換されるエラー訂正システムを通過します。
エンコーダの入力は、24個の8ビットシンボル（A / D変換器から12個の16ビットサンプル、左右のデータ（音源）から6個ずつ）の入力フレームから構成されます。フレームは、＆lt;数学＆gt; L_1 R_1 L_2 R_2 \ lots L_6 R_6＆lt; / math＆gt;ここで、＆lt;数学＆gt; L_i＆lt; / math＆gt; <数式> R_i＆lt; / math＆gt;は、＆lt; math＆gt; i ^ {th} </ math>からの左右チャンネルからのバイトである。フレームのサンプル。
最初に、バイトは置換されて、<math> L_1 L_3 L_5 R_1 R_3 R_5 L_2 L_4 L_6 R_2 R_4 R_6 </ math>で表される新しいフレームを形成する。ここで、L_i、R_iは、それぞれ、を表す。ここで、L_i、R_iは、 2つの介在フレームの後のフレームからの左右のサンプル。
次に、これらの24個のメッセージシンボルは、（m + mathbb {F} _ {256} / math）にわたって短縮されたRS符号であるC2（28,24,5）リードソロモン符号を使用して符号化される。これは、最小距離5である2エラー訂正である。これにより、4バイトの冗長性、<math> P_1 P_2 </ math>が追加される。新たなフレームを形成する：L_1 L_3 L_5 R_1 R_3 R_5 P_1 P_2 L_2 L_4 L_6 R_2 R_4 R_6 </ math>。得られた28シンボルコードワードは、28インターリーブシンボルにつながる（28.4）クロスインタリーバを通過する。これらはC1（32,28,5）RS符号に通され、結果として32個の符号化出力シンボルの符号語が得られる。次のコードワードの偶数番目のシンボルを有するコードワードの奇数番目のシンボルの更なる再編成は、上記の4フレーム遅延インターリーブの後にまだ存在する可能性のある短いバーストを分割するために行われる。したがって、24個の入力シンボルごとに、32個の出力シンボルがあり、これは、 R = 24/32である。最後に、制御および表示情報の1バイトが追加されます。＆lt; ref name = "Lin、Shu" /＆gt;次に、33バイトの各々は、EFM（8〜14変調）及び3マージビットの加算を介して17ビットに変換される。したがって、6つのサンプルのフレームは、33バイト×17ビット（561ビット）となり、合計24ビットの同期ビットと3つのマージングビットが合計588ビットとなる。 'Decoding：' CDプレーヤー（CIRCデコーダ）は、32個の出力シンボルデータストリームを受け取ります。このストリームは、デコーダD1を最初に通過する。デコード方法を決定し、製品性能を最適化することは、CDシステムの個々の設計者次第です。最小距離の存在5、D1デコーダは、それぞれ、<math> e </ math>の組み合わせを修正することができる。 ＆lt;数学＆gt; f＆lt; / math＆gt; ＆lt; ref name = "Lin、Shu" /＆gt;となるような、ほとんどの復号化ソリューションでは、D1は単一エラーを訂正するように設計されています。また、1つ以上のエラーが発生した場合、このデコーダは28回の消去を出力します。後段のデインターリーバは、これらの消去を28個のD2コードワードにわたって分配する。やはりほとんどのソリューションでは、D2は消去のみを処理するように設定されています（よりシンプルで安価なソリューション）。 4回以上の消去が発生すると、D2によって24回の消去が出力される。その後、誤り隠蔽システムは、訂正不能シンボルの場合には（隣接シンボルから）補間を試み、そのような誤りシンボルに対応する音声が消音される。
'CIRCのパフォーマンス：＆lt; ref name = "Algebraic Error Control Codes" /＆gt;' CIRCは単純な線形補間によって長いバストエラーを隠します。 2.5＆nbsp; mmのトラック長（4000ビット）は、完全に修正可能な最大バースト長です。 7.7＆nbsp; mmトラック長（12,300ビット）は、補間可能な最大バースト長です。サンプル補間レートは、ビット誤り率（Bit Error Rate：BER）= 10 ^ { - 4} / mathで10時間ごとに1である。およびBER = 10 ^ { - 3}での1分当たり1000個のサンプル。検出不可能なエラーサンプル（クリック）：BER = <数学> 10 ^ { - 3} <数学>で750時間ごとに1未満BER = 10 ^ { - 4} / mathで無視できる。
