バースト誤り訂正符号

バーストエラーの簡潔な定義があると便利な場合が多く、その定義にはエラーの長さだけでなく、パターンや位置も含まれる。バースト記述はタプルとして定義される。${\displaystyle (P,L)}$どこ${\displaystyle P}$エラーのパターン（つまり、エラーパターンの最初の非ゼロエントリから始まり、最後の非ゼロシンボルで終わる記号列）であり、${\displaystyle L}$これは、コードワード上でバーストが見つかる位置です。^{[ 1 ]}

例えば、エラーパターンのバースト記述${\displaystyle E=(010000110)}$は${\displaystyle D=(1000011,1)}$。このような記述は一意ではないことに注意してください。${\displaystyle D'=(11001,6)}$同じバーストエラーを記述します。一般に、非ゼロ成分の数が${\displaystyle E}$は${\displaystyle w}$、 それから${\displaystyle E}$持つことになる${\displaystyle w}$異なるバースト記述はそれぞれ異なる非ゼロエントリから始まります${\displaystyle E}$。ただし、以下の定理でバースト記述の曖昧さによって生じる問題を解決するには、まず定義が必要です。

定義。特定のエラーパターンにおけるシンボルの数。${\displaystyle y,}$は、${\displaystyle \mathrm {長さ} (y).}$

上記の定理の帰結として、長さのバーストに対して2つの異なるバースト記述を持つことはできない。$\displaystyle {\tfrac {1}{2}}(n+1).}$

上限とは、エラー検出能力の限界を意味し、それを超えることは決してできません。${\displaystyle (n,k)}$長さのすべてのバーストエラーを検出できるコード${\displaystyle \leqslant \ell .}$当然の疑問は、${\displaystyle n}$そして${\displaystyle k}$最大は${\displaystyle \ell }$私たちが決して超えることのできない長さの上限は何か？言い換えれば、長さの上限は何か？${\displaystyle \ell }$あらゆる方法で検出できるバースト${\displaystyle (n,k)}$コード？次の定理がこの質問への答えを提供します。

さて、今度は同じ質問をエラー訂正について繰り返します。${\displaystyle n}$そして${\displaystyle k}$長さの上限は何ですか${\displaystyle \ell }$あらゆる方法で修正できるバースト${\displaystyle (n,k)}$コード？次の定理は、この質問に対する予備的な答えを提供する。

リーガー限界によって、より強力な結果が得られる。

定義。上記のリーガー限界を達成する線形バースト誤り訂正符号を最適バースト誤り訂正符号と呼ぶ。

多重位相バースト訂正（MPBC）用の線形ブロック符号の達成可能な符号化率には、複数の上限が存在する。そのような上限の1つは、各サブブロック内の最大訂正可能巡回バースト長、または同等に、各位相バースト内の最小無誤り長またはギャップに対する制約である。この上限は、単一バースト訂正の上限という特殊なケースに縮小すると、巡回バースト長がブロック長の半分未満の場合、アブラムソン上限（バースト誤り訂正のハミング上限の系）となる。 ^{[ 3 ]}

述べる。${\displaystyle r=n-k}$これはコードの冗長性と呼ばれ、アブラムソン境界の別の定式化では次のようになります。${\displaystyle r\geqslant \lceil \log _{2}(n+1)\rceil +\ell -1.}$

させて ${\displaystyle x^{i}a(x)}$そして${\displaystyle x^{j}b(x)}$次数が の多項式である ${\displaystyle \ell _{1}-1}$そして${\displaystyle \ell _{2}-1}$長さのバーストを表す${\displaystyle \ell _{1}}$そして ${\displaystyle \ell _{2}}$それぞれ${\displaystyle \ell _{1},\ell _{2}\leqslant \ell .}$整数${\displaystyle i,j}$これらはバーストの開始位置を表し、コードのブロック長よりも小さい。矛盾を避けるために、 ${\displaystyle x^{i}a(x)}$そして${\displaystyle x^{j}b(x)}$同じ剰余類に属する。すると、${\displaystyle v(x)=x^{i}a(x)+x^{j}b(x)}$は有効なコードワードです（両方の項が同じ剰余類に属しているため）。一般性を失うことなく、${\displaystyle i\leqslant j}$除法の定理により、次のように書くことができます。${\displaystyle j-i=g(2\ell -1)+r,}$整数の場合${\displaystyle g}$そして${\displaystyle r,0\leqslant r<2\ell -1}$多項式を書き直す${\displaystyle v(x)}$次のように： $${\displaystyle v(x)=x^{i}a(x)+x^{i+g(2\ell -1)+r}=x^{i}a(x)+x^{i+g(2\ell -1)+r}+2x^{i+r}b(x)=x^{i}\left(a(x)+x^{b}b(x)\right)+x^{i+r}b(x)\left(x^{g(2\ell -1)}+1\right)}$$

2回目の操作で、次の用語を導入したことに注目してください。 ${\displaystyle 2x^{i+r}b(x)}$. 消防法は、 ${\displaystyle \mathbb {F} _{2}}$我々の仮定によれば、${\displaystyle v(x)}$は有効なコードワードであり、したがって、 の倍数でなければならない。${\displaystyle g(x)}$前述の通り、${\displaystyle g(x)}$相対的に素数であり、${\displaystyle v(x)}$で割り切れる必要がある${\displaystyle x^{2\ell -1}+1}$. 導出された最後の式を詳しく見てみると${\displaystyle v(x)}$私たちは気づきました${\displaystyle x^{g(2\ell -1)}+1}$は割り切れる${\displaystyle x^{2\ell -1}+1}$（補題２の系より）したがって、${\displaystyle a(x)+x^{b}b(x)}$は${\displaystyle x^{2\ell -1}+1}$または${\displaystyle 0}$除法定理を再び適用すると、多項式が存在することがわかります。${\displaystyle d(x)}$学位取得${\displaystyle \delta }$すなわち、 $${\displaystyle a(x)+x^{b}b(x)=d(x)(x^{2\ell -1}+1)}$$

すると、次のように書けるでしょう。 $${\displaystyle {\begin{aligned}\delta +2\ell -1&=\deg \left(d(x)\left(x^{2\ell -1}+1\right)\right)\\&=\deg \left(a(x)+x^{b}b(x)\right)\\&=\deg \left(x^{b}b(x)\right)&&\deg(a(x))=\ell _{1}-1<2\ell -1\\&=b+\ell _{2}-1\end{aligned}}}$$

両辺の次数を等しくすると、 ${\displaystyle b=2\ell -\ell _{2}+\delta .}$以来 ${\displaystyle \ell _{1},\ell _{2}\leqslant \ell }$結論 ${\displaystyle b\geqslant \ell +\delta ,}$これは、 ${\displaystyle b>\ell -1}$そして ${\displaystyle b>\delta }$展開図では次の点に注目してください。 $${\displaystyle a(x)+x^{b}b(x)=1+a_{1}x+a_{2}x^{2}+\dots +x^{\ell _{1}-1}+x^{b}\left(1+b_{1}x+b_{2}x^{2}+\dots +x^{\ell _{2}-1}\right).}$$ 用語 ${\displaystyle x^{b}}$現れますが、 ${\displaystyle \delta <b<2\ell -1}$結果として得られる式${\displaystyle d(x)(x^{2\ell -1}+1)}$含まない ${\displaystyle x^{b}}$、 したがって${\displaystyle d(x)=0}$そしてその後${\displaystyle a(x)+x^{b}b(x)=0.}$これは以下を必要とする ${\displaystyle b=0}$、 そして ${\displaystyle a(x)=b(x)}$我々はさらに分割を修正することができる${\displaystyle j-i}$による${\displaystyle g(2\ell -1)}$反映する${\displaystyle b=0,}$それは${\displaystyle j-i=g(2\ell -1)}$を代入して${\displaystyle v(x)}$私たちに与える、 $${\displaystyle v(x)=x^{i}b(x)\left(x^{j-1}+1\right).}$$

以来${\displaystyle \deg(b(x))=\ell _{2}-1<\ell }$、 我々は持っています${\displaystyle \deg(b(x))<\deg(p(x))=m}$。 しかし${\displaystyle p(x)}$還元不可能である、したがって ${\displaystyle b(x)}$そして${\displaystyle p(x)}$互いに素でなければならない。${\displaystyle v(x)}$はコードワードです。${\displaystyle x^{j-1}+1}$で割り切れる必要がある${\displaystyle p(x)}$で割り切れないため${\displaystyle x^{2\ell -1}+1}$。 したがって、${\displaystyle j-i}$の倍数でなければならない${\displaystyle p}$しかし、それはまた、${\displaystyle 2\ell -1}$これは、それがの倍数でなければならないことを意味する。${\displaystyle n={\text{lcm}}(2\ell -1,p)}$しかし、それはまさにコードのブロック長です。したがって、${\displaystyle j-i}$の倍数にはなれません${\displaystyle n}$両方ともより小さいので${\displaystyle n}$したがって、${\displaystyle v(x)}$暗号語であることは誤りであり、したがって${\displaystyle x^{i}a(x)}$そして${\displaystyle x^{j}b(x)}$これらは異なるコセットに属し、それぞれ固有の症候群を呈するため、治療可能である。

上記のセクションで提示された理論に基づいて、 ${\displaystyle 5}$-バーストエラー訂正火災コード。火災コードを構築するには、既約多項式が必要であることを覚えておいてください。${\displaystyle p(x)}$整数${\displaystyle \ell }$は、コードのバースト誤り訂正能力を表しており、次の性質を満たす必要があります。 ${\displaystyle 2\ell -1}$は、${\displaystyle p(x)}$これらの要件を念頭に置いて、既約多項式を考えます。${\displaystyle p(x)=1+x^{2}+x^{5}}$、そして${\displaystyle \ell =5}$。 以来${\displaystyle p(x)}$は原始多項式であり、その周期は${\displaystyle 2^{5}-1=31}$確認します${\displaystyle 2\ell -1=9}$は割り切れません${\displaystyle 31}$。 したがって、 $${\displaystyle g(x)=(x^{9}+1)\left(1+x^{2}+x^{5}\right)=1+x^{2}+x^{5}+x^{9}+x^{11}+x^{14}}$$ は防火コード生成器です。コードのブロック長は、の最小公倍数を評価することによって計算できます。${\displaystyle p}$そして${\displaystyle 2\ell -1}$。 言い換えると、${\displaystyle n={\text{lcm}}(9,31)=279}$したがって、上記の火災コードは、あらゆる長さのバーストを修正できる循環コードである。${\displaystyle 5}$またはそれ以下。

させて${\displaystyle G}$になる${\displaystyle [255,223,33]}$RSコードオーバー${\displaystyle \mathbb {F} _{2^{8}}}$このコードはNASAがカッシーニ・ホイヘンス探査機で 採用した。^{[ 6 ]}これは修正が可能で、${\displaystyle \lfloor 33/2\rfloor =16}$シンボルエラー。次にバイナリRSコードを構築します。${\displaystyle G'}$から${\displaystyle G}$各記号は以下のように記述されます。${\displaystyle \lceil \log _{2}(255)\rceil =8}$ビット。したがって、バイナリRSコードには${\displaystyle [2040,1784,33]_{2}}$そのパラメータとして。長さの単一バーストを修正することが可能です。${\displaystyle l=121}$。

下の図は、4×3のインターリーバを示しています。

上記のインターリーバはブロックインターリーバと呼ばれます。ここでは、入力シンボルは行に順次書き込まれ、出力シンボルは列を順次読み取ることによって得られます。したがって、これは次の形式になります。${\displaystyle M\times N}$配列。一般的に、${\displaystyle N}$は符号語の長さです。

ブロックインターリーバの容量：${\displaystyle M\times N}$ブロックインターリーバと長さのバースト${\displaystyle \ell ,}$エラー数の上限は${\displaystyle {\tfrac {\ell }{M}}.}$これは、出力を列ごとに読み込んでおり、行数が${\displaystyle M}$上記の定理により、誤り訂正容量は${\displaystyle t,}$最大バースト長は${\displaystyle Mt.}$バースト長の場合${\displaystyle Mt+1}$デコーダーが故障する可能性があります。

ブロックインターリーバの効率（${\displaystyle \gamma }$):デコーダがインターリーバメモリで失敗する可能性があるバースト長の比率を取ることによって、それがわかります。したがって、次のように定式化できます。${\displaystyle \gamma }$として $${\displaystyle \gamma ={\frac {Mt+1}{MN}}\approx {\frac {t}{N}}.}$$

ブロックインターリーバの欠点 ：図から明らかなように、列は順次読み取られるため、受信側は完全なメッセージを受信した後でなければ、個々の行を解釈できません。また、受信側は受信したシンボルを格納するためにかなりの量のメモリを必要とし、完全なメッセージを格納しなければなりません。したがって、これらの要因により、レイテンシとストレージ（かなりの量のメモリ）という2つの欠点が生じます。これらの欠点は、後述する畳み込みインターリーバを使用することで回避できます。

クロスインターリーバは、マルチプレクサ・デマルチプレクサシステムの一種です。このシステムでは、遅延線を使用して徐々に長さを増やしていきます。遅延線は基本的に、信号を一定の時間だけ遅延させる電子回路です。${\displaystyle n}$遅延線の数と${\displaystyle d}$各遅延線によって導入されるシンボルの数をとする。したがって、連続する入力間の間隔は =${\displaystyle nd}$記号。符号語の長さを${\displaystyle \leqslant n.}$したがって、入力コードワード内の各シンボルは、それぞれ異なる遅延線上に配置されます。長さのバーストエラーを考えます。${\displaystyle \ell }$発生します。連続する記号間の間隔は${\displaystyle nd,}$デインターリーブされた出力に含まれる可能性のあるエラーの数は${\displaystyle {\tfrac {\ell }{nd+1}}.}$上記の定理により、誤り訂正容量は${\displaystyle t}$最大バースト長は${\displaystyle (nd+1)(t-1).}$バースト長の場合${\displaystyle (nd+1)(t-1)+1,}$デコーダーが故障する可能性があります。

クロスインターリーバの効率（${\displaystyle \gamma }$):デコーダが失敗する可能性のあるバースト長とインターリーバメモリの比率を取ることで求められます。この場合、インターリーバのメモリは次のように計算できます。 $${\displaystyle (0+1+2+3+\cdots +(n-1))d={\frac {n(n-1)}{2}}d.}$$

したがって、次のように定式化できます。${\displaystyle \gamma }$次のように： $${\displaystyle \gamma ={\frac {(nd+1)(t-1)+1}{{\frac {n(n-1)}{2}}d}}.}$$

クロスインターリーバの性能 ：上記のインターリーバ図に示すように、出力は各遅延線の終端で生成される対角線状のシンボルです。この場合、入力マルチプレクサのスイッチが約半分のスイッチングを完了すると、受信側で最初の行を読み取ることができます。したがって、最初の行を読み取るために、受信側には最大で約半分のメッセージを格納する必要があります。これにより、ストレージ要件が大幅に半分に削減されます。最初の行を読み取るのに必要なメッセージが半分だけになったため、遅延も半分に短縮され、ブロックインターリーバに比べて大幅に改善されます。このように、インターリーバ全体のメモリは送信側と受信側で分割されます。

エラー訂正符号がなければ、デジタルオーディオは技術的に実現不可能だったでしょう。^{[ 7 ]}リード・ソロモン符号は、 1ビットのエラーで破損したシンボルを、すべてのビットが間違っているシンボルを訂正するのと同じくらい簡単に訂正できます。このため、RS 符号はバーストエラーの訂正に特に適しています。^{[ 5 ]} RS 符号の最も一般的な用途は、コンパクトディスクです。RS 符号による基本的なエラー訂正に加えて、ディスクの傷によるバーストエラーに対する保護は、クロスインターリーバによって提供されます。^{[ 3 ]}

現在のコンパクトディスクデジタルオーディオシステムは、オランダのNVフィリップス社と日本のソニー株式会社によって開発された（1979年に契約締結）。

コンパクトディスクは、 透明なプラスチックコーティングが施された直径120 mmのアルミ蒸着ディスクで構成され、 長さ約5 kmのらせん状のトラックがあり、波長約0.8 μmのレーザーによって約1.25  m/sの一定速度で光学的にスキャンされます。この一定速度を実現するために、ディスクの回転速度は、トラックの内側部分をスキャンしているときは約8 rev/s、外側部分をスキャンしているときは約3.5 rev/sに変化します。ピットとランドは、トラックに沿ってバイナリデータを構成する凹み（深さ0.12 μm）と平坦な部分（幅0.6 μm）です。^{[ 8 ]}

CDプロセスは、以下のサブプロセスのシーケンスとして抽象化できます。

• 信号源のチャネル符号化
• マスターディスクの準備、ユーザーディスクの製造、再生中にユーザーディスクに埋め込まれた信号の検出といった機械的なサブプロセス – チャネル
• ユーザーディスクから感知した信号を解読する

このプロセスは、バーストエラーとランダムエラーの両方の影響を受けます。^{[ 7 ]}バーストエラーには、ディスク材料（アルミニウム反射フィルムの欠陥、透明ディスク材料の低い反射率）、ディスク製造（ディスク成形およびディスク切断中の欠陥など）、ディスクハンドリング（傷 - 一般的に薄く、放射状で、記録方向に対して直交）、再生メカニズムの変動によるものが含まれます。ランダムエラーには、再構成された信号波のジッターと信号の干渉によるものが含まれます。CIRC（クロスインターリーブリードソロモンコード）は、CD プロセスのエラー検出と訂正の基礎です。これは、連続する 3,500 ビット（ CD 表面で長さ 2.4 mm）までのエラーバーストを訂正し、小さな傷によって発生する可能性のある 12,000 ビット（8.5 mm）までのエラーバーストを補償します 。

エンコーディング:音波はサンプリングされ、A/Dコンバータによってデジタル形式に変換されます。音波は振幅についてサンプリングされます（44.1  kHz、つまりステレオ音の左右チャンネルそれぞれに1つずつ、44,100ペア）。ある時点での振幅には、長さ16のバイナリ文字列が割り当てられます。したがって、各サンプルは2つのバイナリベクトルを生成します。${\displaystyle \mathbb {F} _{2}^{16}}$または4${\displaystyle \mathbb {F} _{2}^{8}}$1秒の音声が記録されると、44,100 × 32 = 1,411,200ビット（176,400バイト）のデータが生成されます。^{[ 5 ]} 1.41 Mbit/sのサンプリングされたデータストリームは、誤り訂正システムを通過し、最終的に1.88 Mbit/sのストリームに変換されます。   

エンコーダへの入力は、それぞれ24個の8ビットシンボル（A/Dコンバータからの12個の16ビットサンプル、左右のデータ（音声）ソースからの6個ずつ）からなる入力フレームで構成されます。フレームは次のように表すことができます。 ${\displaystyle L_{1}R_{1}L_{2}R_{2}\ldots L_{6}R_{6}}$どこ${\displaystyle L_{i}}$そして${\displaystyle R_{i}}$左チャンネルと右チャンネルからのバイト数です。${\displaystyle i^{th}}$フレームのサンプル。

最初は、バイトが並べ替えられて、次のような新しいフレームが形成されます。${\displaystyle L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}}$どこ${\displaystyle L_{i},R_{i}}$代表する${\displaystyle i}$2つのフレームを挟んだ後のフレームから、左と右のサンプルをそれぞれ取得します。

次に、これらの 24 個のメッセージシンボルは、短縮された RS コードである C2 (28,24,5) リード・ソロモンコードを使用してエンコードされます。${\displaystyle \mathbb {F} _{256}}$これは2つの誤り訂正が可能で、最小距離は5です。これにより4バイトの冗長性が追加されます。${\displaystyle P_{1}P_{2}}$新しいフレームを形成する：${\displaystyle 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}}$結果として得られる28シンボルの符号語は、（28.4）クロスインターリーバを通過し、28個のインターリーブされたシンボルになります。これらは次にC1（32,28,5）RSコードを通過し、32個の符号化された出力シンボルの符号語になります。上記の4フレーム遅延インターリーブ後に残っている可能性のある短いバーストを分割するために、符号語の奇数番目のシンボルと次の符号語の偶数番目のシンボルをさらに再グループ化します。したがって、24個の入力シンボルごとに32個の出力シンボルが得られ、${\displaystyle R=24/32}$最後に、制御および表示情報の 1 バイトが追加されます。^{[ 5 ]} 33 バイトのそれぞれは、EFM (8 ビットから 14 ビットへの変調) と 3 ビットのマージの追加により 17 ビットに変換されます。したがって、6 つのサンプルのフレームは 33 バイト×  17 ビット (561 ビット) となり、これに 24 ビットの同期ビットと 3 ビットのマージが追加され、合計 588 ビットになります。

デコード: CDプレーヤー（CIRCデコーダ）は32個の出力シンボルデータストリームを受信します。このストリームはまずデコーダD1を通過します。デコード方式を決定し、製品性能を最適化するのは、CDシステムの個々の設計者に委ねられています。最小距離5であるため、D1、D2デコーダはそれぞれ、${\displaystyle e}$エラーと${\displaystyle f}$消去によって${\displaystyle 2e+f<5}$[ ^{5 ]ほとんどの復号方式では、D1 は単一のエラーを}訂正するように設計されています。エラーが 1 つ以上ある場合、このデコーダは 28 個の消去を出力します。次の段階のデインターリーバは、これらの消去を 28 個の D2 コードワードに分散します。また、ほとんどの方式では、D2 は消去のみを処理するように設定されています (よりシンプルでコストのかからない方式)。4 つを超える消去が発生した場合、D2 は 24 個の消去を出力します。その後、エラー隠蔽システムは、訂正不可能なシンボルの場合に (隣接するシンボルから) 補間を試み、それが失敗した場合は、そのような誤ったシンボルに対応するサウンドがミュートされます。

CIRC の性能: ^{[ 7 ]} CIRC は、単純な線形補間によって長いバーストエラーを隠蔽します。 2.5  mm のトラック長 (4000 ビット) は、完全に訂正可能な最大バースト長です。 7.7 mm のトラック長 (12,300 ビット) は、補間可能な最大バースト長です。 サンプル補間レートは、ビット誤り率(BER) で 10 時間ごとに 1 回です。${\displaystyle =10^{-4}}$BER = 1000 サンプル/分${\displaystyle 10^{-3}}$検出不可能なエラーサンプル（クリック）：BER = 750 時間ごとに 1 回未満${\displaystyle 10^{-3}}$BER = では無視できる${\displaystyle 10^{-4}}$。