BCH コード

符号理論において、ボーズ・ショードリー・オッケンゲム符号（BCH符号）は、有限体（ガロア体とも呼ばれる）上の多項式を使用して構築される巡回 誤り訂正符号の一種である。BCH符号は、1959年にフランスの数学者アレクシ・オッケンゲムによって発明され、1960年にラージ・チャンドラ・ボースとDKレイ・ショードリーによって独立に発明された。^{[1] [2] [3]}ボーズ・ショードリー・オッケンゲムという名前（および頭字語のBCH）は、発明者の姓の頭文字に由来している（レイ・ショードリーの場合は誤っている）。

BCH コードの主な特徴の 1 つは、コード設計時に、コードによって訂正可能なシンボル エラーの数を正確に制御できることです。特に、複数のビット エラーを訂正できるバイナリ BCH コードを設計できます。BCH コードのもう 1 つの利点は、シンドローム デコードと呼ばれる代数的手法によって簡単にデコードできることです。これにより、小型で低電力の電子ハードウェアを使用して、これらのコードのデコーダーの設計が簡素化されます。

^{BCHコードは、衛星通信、 [4]} コンパクトディスクプレーヤー、DVD、ディスクドライブ、USBフラッシュドライブ、ソリッドステートドライブ、^[5] 2次元バーコードなどのアプリケーションで使用されます。

素数 qと素数べき q ^m（正の整数mとdでd ≤ q ^m − 1 ）が与えられたとき、有限体（またはガロア体）GF( q )上の、コード長n = q ^m − 1で距離が少なくともdである原始狭義 BCH コードが次の方法で構築されます。

α をGF( q ^m )の原始元とする。任意の正の整数iに対して、m _i ( x ) をα ⁱのGF( q )に係数を持つ最小多項式とする。BCH符号の生成多項式は、最小公倍数g ( x ) = lcm( m ₁ ( x ),…, m _{d − 1} ( x ))として定義される。 g ( x )はGF( q )に係数を持つ多項式であり、 x ⁿ − 1を割り切ることがわかる。したがって、g ( x )によって定義される多項式符号は巡回符号である。

q = 2、m = 4（したがってn = 15 ）とする。原始元α（z）= zを用いて、約分多項式z ⁴ + z + 1に基づいて、 GF （16）= GF（2 ⁴）のdの異なる値を検討する 。GF（2）の係数を持つ最小多項式m _i ( x )は14個あり、

${\displaystyle m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+1\right)}}=0.}$

最小多項式は

${\displaystyle {\begin{aligned}m_{1}(x)&=m_{2}(x)=m_{4}(x)=m_{8}(x)=x^{4}+x+1,\\m_{3}(x)&=m_{6}(x)=m_{9}(x)=m_{12}(x)=x^{4}+x^{3}+x^{2}+x+1,\\m_{5}(x)&=m_{10}(x)=x^{2}+x+1,\\m_{7}(x)&=m_{11}(x)=m_{13}(x)=m_{14}(x)=x^{4}+x^{3}+1.\end{aligned}}}$

BCHコードの生成多項式は次のようになる。 ${\displaystyle d=2,3}$

${\displaystyle g(x)={\rm {lcm}}(m_{1}(x),m_{2}(x))=m_{1}(x)=x^{4}+x+1.\,}$

最小ハミング距離は少なくとも 3 で、最大 1 つのエラーを訂正します。生成多項式は 4 次なので、このコードには 11 のデータ ビットと 4 つのチェックサム ビットがあります。これは(15, 11) BCHコード とも呼ばれます。

BCHコードの生成多項式は次のようになる。 ${\displaystyle d=4,5}$

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x))=m_{1}(x)m_{3}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)=x^{8}+x^{7}+x^{6}+x^{4}+1.\end{aligned}}}$

最小ハミング距離は少なくとも 5 で、最大 2 つのエラーを訂正します。生成多項式は 8 次なので、このコードには 7 つのデータ ビットと 8 つのチェックサム ビットがあります。これは(15, 7) BCHコードとも呼ばれます。

BCHコードの生成多項式は次のようになる。 ${\displaystyle d=6,7}$

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x),m_{5}(x),m_{6}(x))=m_{1}(x)m_{3}(x)m_{5}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1.\end{aligned}}}$

最小ハミング距離は少なくとも 7 で、最大 3 つのエラーを訂正します。生成多項式は 10 次であるため、このコードには 5 つのデータ ビットと 10 のチェックサム ビットがあります。これは(15, 5) BCHコードとも表記されます。(この特定の生成多項式は、 QR コードの「フォーマット情報」で実際に使用されています。)

以上のBCHコードの生成多項式は次のようになる。 ${\displaystyle d=8}$

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),...,m_{14}(x))=m_{1}(x)m_{3}(x)m_{5}(x)m_{7}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)\left(x^{4}+x^{3}+1\right)=x^{14}+x^{13}+x^{12}+\cdots +x^{2}+x+1.\end{aligned}}}$

このコードは最小ハミング距離が 15 で、7 つのエラーを訂正します。データ ビットは 1 ビット、チェックサム ビットは 14 ビットです。これは(15, 1) BCHコードとも呼ばれます。実際、このコードには 000000000000000 と 111111111111111 (単純な繰り返しコード) の 2 つのコードワードしかありません。

一般的な BCH コードは、2 つの点で原始的な狭義の BCH コードと異なります。

まず、の原始要素であるという要件を緩和することができます。この要件を緩和すると、コードの長さは から の要素の順序に変わります。${\displaystyle \alpha}$${\displaystyle \mathrm {GF} (q^{m})}$${\displaystyle q^{m}-1}$${\displaystyle \mathrm {ord} (\alpha ),}$${\displaystyle \alpha .}$

第二に、生成多項式の連続根は、${\displaystyle \alpha^{c},\ldots,\alpha^{c+d-2}}$${\displaystyle \alpha ,\ldots ,\alpha ^{d-1}.}$

定義。が素数べき乗である有限体を決めます。 が を法 とする乗法順序であるような正の整数を選びます。${\displaystyle GF(q),}$${\displaystyle q}$${\displaystyle m,n,d,c}$${\displaystyle 2\leq d\leq n,}$ ${\displaystyle {\rm {gcd}}(n,q)=1,}$${\displaystyle m}$${\displaystyle q}$${\displaystyle n.}$

以前と同様に、を の原始の 乗根とし、を のすべての に対するの最小多項式とします。BCH コードの生成多項式は、最小公倍数として定義されます。${\displaystyle \alpha}$${\displaystyle n}$${\displaystyle GF(q^{m}),}$${\displaystyle m_{i}(x)}$${\displaystyle GF(q)}$${\displaystyle \alpha^{i}}$${\displaystyle i.}$ ${\displaystyle g(x)={\rm {lcm}}(m_{c}(x),\ldots ,m_{c+d-2}(x)).}$

注:簡略化された定義のように、 は1であり、を法とするの順序は したがって、 簡略化された定義は、実際には一般的な定義の特殊なケースです。 ${\displaystyle n=q^{m}-1}$${\displaystyle {\rm {gcd}}(n,q)}$${\displaystyle q}$${\displaystyle n}$${\displaystyle m.}$

• を持つ BCH コードは、狭義の BCH コードと呼ばれます。${\displaystyle c=1}$
• を持つ BCH コードはプリミティブと呼ばれます。${\displaystyle n=q^{m}-1}$

BCH 符号の生成多項式は、の係数を持ちます。一般に、を生成多項式として 上の巡回符号は、 上の BCH 符号と呼ばれます。 の連続 するべきを根として持つ、 上の BCH符号は、デコーダ（シンドローム）アルファベットがチャネル（データと生成多項式）アルファベットと同じで、 のすべての要素が であるリード・ソロモン符号の一種です。^[6]リード・ソロモン符号のもう 1 つのタイプは、 BCH 符号ではない オリジナル ビューのリード・ソロモン符号です。${\displaystyle g(x)}$${\displaystyle \mathrm {GF} (q).}$${\displaystyle \mathrm {GF} (q^{p})}$${\displaystyle g(x)}$${\displaystyle \mathrm {GF} (q^{p})。}$${\displaystyle \mathrm {GF} (q^{m})}$${\displaystyle g(x)}$${\displaystyle \alpha}$${\displaystyle \mathrm {GF} (q^{m})}$

BCH 符号の生成多項式の次数は最大 です。さらに、および の場合、生成多項式の次数は最大 です。 ${\displaystyle (d-1)m}$${\displaystyle q=2}$${\displaystyle c=1}$${\displaystyle dm/2}$

BCH コードの最小ハミング距離は少なくとも です。 ${\displaystyle d}$

BCH コードは巡回的です。

生成多項式の倍数である多項式はすべて有効な BCH 符号語であるため、BCH エンコーディングは生成多項式を因数として持つ多項式を見つけるプロセスにすぎません。

BCH コード自体は、多項式の係数の意味について規定していません。概念的には、BCH デコード アルゴリズムの唯一の関心事は、受信したコードワードとのハミング距離が最小である有効なコードワードを見つけることです。したがって、BCH コードは、実装者がエンコードされた多項式にメッセージを埋め込む方法に応じて、体系的なコードとして実装することも、そうでない場合も あります。

生成子の倍数である多項式を見つける最も簡単な方法は、任意の多項式と生成子の積を計算することです。この場合、メッセージのシンボルを係数として使用して、任意の多項式を選択できます。

${\displaystyle s(x)=p(x)g(x)}$

例として、POCSAGなどが使用する (31, 21) バイナリ BCH コードで使用するために選択された生成多項式 を考えます。21 ビットのメッセージ {101101110111111101} をエンコードするには、まず 上の多項式として表現します。 ${\displaystyle g(x)=x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1}$${\displaystyle GF(2)}$

${\displaystyle p(x)=x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1}$

次に、（ についても）計算します。 ${\displaystyle GF(2)}$

${\displaystyle {\begin{aligned}s(x)&=p(x)g(x)\\&=\left(x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1\right)\left(x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1\right)\\&=x^{30}+x^{29}+x^{26}+x^{25}+x^{24}+x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{2}+1\end{aligned}}}$

したがって、送信されるコードワードは {1100111010011110111101110101} です。

受信機はこれらのビットを係数として使用し、有効なコードワードを保証するためにエラー訂正を行った後、再計算することができる。${\displaystyle s(x)}$${\displaystyle p(x)=s(x)/g(x)}$

体系的なコードとは、メッセージがコードワード内のどこかにそのまま現れるコードです。したがって、体系的な BCH エンコーディングでは、まずメッセージ多項式をコードワード多項式内に埋め込み、次に残りの（メッセージ以外の）項の係数を調整して がで割り切れるようにします。 ${\displaystyle s(x)}$${\displaystyle g(x)}$

このエンコード方法は、被除数から剰余を引くと除数の倍数になるという事実を活用します。したがって、前と同じようにメッセージ多項式を取り、それを乗算すると(メッセージを剰余から「シフト」するため)、多項式の ユークリッド除算を使用して次の式が得られます。${\displaystyle p(x)}$${\displaystyle x^{n-k}}$

${\displaystyle p(x)x^{n-k}=q(x)g(x)+r(x)}$

ここで、 は有効なコードワードであることがわかります。 は常に より小さい次数（ の次数）であるため、メッセージ係数を変更することなく から を安全に減算できます。したがって、 は次のように 表されます。${\displaystyle q(x)g(x)}$${\displaystyle r(x)}$${\displaystyle n-k}$${\displaystyle g(x)}$${\displaystyle p(x)x^{n-k}}$${\displaystyle s(x)}$

${\displaystyle s(x)=q(x)g(x)=p(x)x^{n-k}-r(x)}$

上(つまり、バイナリ BCH コードの場合)、このプロセスは巡回冗長検査を追加することと区別がつかず、体系的なバイナリ BCH コードがエラー検出の目的でのみ使用される場合、BCH コードは巡回冗長検査の数学の一般化にすぎないことがわかります。 ${\displaystyle GF(2)}$

体系的コーディングの利点は、受信側がエラー訂正を実行した後、最初の係数の後のすべてを破棄することで元のメッセージを復元できることです。 ${\displaystyle k}$

BCH コードをデコードするためのアルゴリズムは多数あります。最も一般的なアルゴリズムは次の概要に従います。

1. 受信したベクトルのシンドロームs _{jを計算する}
2. シンドロームからエラー数tとエラー位置多項式Λ(x)を決定する
3. エラー位置多項式の根を計算してエラー位置X _{iを見つけます。}
4. これらのエラー位置でのエラー値Y _{iを計算する}
5. エラーを修正する

これらのステップのいくつかでは、デコード アルゴリズムが、受信したベクトルにエラーが多すぎて修正できないと判断する場合があります。たとえば、適切なtの値が見つからない場合、修正は失敗します。切り捨てられた (プリミティブではない) コードでは、エラーの位置が範囲外になることがあります。受信したベクトルにコードが修正できる以上のエラーがある場合、デコーダーは、送信されたメッセージではない、一見有効なメッセージを知らないうちに生成することがあります。

受信ベクトルは正しいコードワードと未知のエラーベクトルの和である。シンドローム値は多項式として考え、それを次のように評価することによって形成される。したがって、シンドロームは^{[7]である。}${\displaystyle R}$${\displaystyle C}$${\displaystyle E.}$${\displaystyle R}$${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}.}$

${\displaystyle s_{j}=R\left(\alpha ^{j}\right)=C\left(\alpha ^{j}\right)+E\left(\alpha ^{j}\right)}$

〜のために${\displaystyle j=c}$${\displaystyle c+d-2.}$

は の倍数であるのゼロなので、シンドローム値を調べるとエラー ベクトルが分離され、それを解き始めることができます。 ${\displaystyle \alpha ^{j}}$${\displaystyle g(x),}$${\displaystyle C(x)}$${\displaystyle C\left(\alpha ^{j}\right)=0.}$

エラーがない場合、すべてのシンドロームがゼロであれば、デコードは完了です。 ${\displaystyle s_{j}=0}$${\displaystyle j.}$

非ゼロのシンドロームがある場合は、エラーがあります。デコーダーは、エラーの数とそれらのエラーの位置を把握する必要があります。

単一のエラーがある場合、これを と書きます。はエラーの位置、 はその大きさです。最初の2つのシンドロームは次のようになります。 ${\displaystyle E(x)=e\,x^{i},}$${\displaystyle i}$${\displaystyle e}$

${\displaystyle {\begin{aligned}s_{c}&=e\,\alpha ^{c\,i}\\s_{c+1}&=e\,\alpha ^{(c+1)\,i}=\alpha ^{i}s_{c}\end{aligned}}}$

これらを組み合わせることで、（リード・ソロモン符号の場合は完全に決定する） についての計算と情報の提供が可能になります。${\displaystyle e}$${\displaystyle i}$

2つ以上のエラーがある場合、

${\displaystyle E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,}$

未知のものに対する結果として生じるシンドロームをどうやって解決し始めるかはすぐには明らかではない。${\displaystyle e_{k}}$${\displaystyle i_{k}.}$

最初のステップは、計算されたシンドロームと互換性があり、最小限のロケータ多項式と互換性のあるものを見つけることです。 ${\displaystyle t,}$

${\displaystyle \Lambda (x)=\prod _{j=1}^{t}\left(x\alpha ^{i_{j}}-1\right)}$

このタスクによく使用される 3 つのアルゴリズムは次のとおりです。

1. Peterson-Gorenstein-Zierler アルゴリズム
2. ベルレカンプ・マッシーアルゴリズム
3. 杉山ユークリッド互除法

ピーターソンのアルゴリズムは、一般化されたBCH復号化手順のステップ2です。ピーターソンのアルゴリズムは、 多項式の エラーロケータ多項式係数を計算するために使用されます。${\displaystyle \lambda _{1},\lambda _{2},\dots ,\lambda _{v}}$

${\displaystyle \Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.}$

次にPeterson-Gorenstein-Zierlerアルゴリズムの手順を説明します。^[8]少なくとも2 t個のシンドロームs _c , …, s _{c +2 t −1}があるとします。v  =  tとします。

これで多項式が得られたので、 Chien 検索アルゴリズムなどを使用して、その根を形式内で総当たり方式で見つけることができます。基本要素の指数乗により、受信したワード内でエラーが発生する位置がわかります。そのため、この多項式は「エラー ロケータ」多項式と呼ばれます。 ${\displaystyle \Lambda (x)}$${\displaystyle \Lambda (x)=\left(\alpha ^{i_{1}}x-1\right)\left(\alpha ^{i_{2}}x-1\right)\cdots \left(\alpha ^{i_{v}}x-1\right)}$${\displaystyle \alpha }$

Λ( x )の零点は^_α − ^{i1 ,} …, α ^{− iv_で}ある。

エラー位置がわかったら、次のステップはそれらの位置のエラー値を決定することです。次に、エラー値を使用してそれらの位置で受信した値を修正し、元のコードワードを復元します。

バイナリBCHの場合（すべての文字が読み取り可能）は、これは簡単です。これらの位置で受信ワードのビットを反転するだけで、修正されたコードワードが得られます。より一般的なケースでは、エラーの重みは線形システムを解くことで決定できます。 ${\displaystyle e_{j}}$

${\displaystyle {\begin{aligned}s_{c}&=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\cdots \\s_{c+1}&=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \\&{}\ \vdots \end{aligned}}}$

しかし、フォーニーアルゴリズムと呼ばれるより効率的な方法があります。

させて

${\displaystyle S(x)=s_{c}+s_{c+1}x+s_{c+2}x^{2}+\cdots +s_{c+d-2}x^{d-2}.}$

${\displaystyle v\leqslant d-1,\lambda _{0}\neq 0\qquad \Lambda (x)=\sum _{i=0}^{v}\lambda _{i}x^{i}=\lambda _{0}\prod _{k=0}^{v}\left(\alpha ^{-i_{k}}x-1\right).}$

そして誤差評価多項式^[9]

${\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}}$

ついに：

${\displaystyle \Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},}$

どこ

${\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}$

シンドロームがエラーワードによって説明できる場合、エラーワードは位置 でのみ非ゼロになる可能性があり、エラー値は ${\displaystyle i_{k}}$

${\displaystyle e_{k}=-{\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right) \over \alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}.}$

狭義の BCH コードの場合、c = 1 なので、式は次のように簡略化されます。

${\displaystyle e_{k}=-{\Omega \left(\alpha ^{-i_{k}}\right) \over \Lambda '\left(\alpha ^{-i_{k}}\right)}.}$

これは、ラグランジュ補間と関数生成の手法に基づいています。

簡単にするために、 およびを仮定すると、 ${\displaystyle S(x)\Lambda (x),}$${\displaystyle \lambda _{k}=0}$${\displaystyle k>v,}$${\displaystyle s_{k}=0}$${\displaystyle k>c+d-2.}$

${\displaystyle S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+1}\lambda _{i}x^{j}.}$

${\displaystyle {\begin{aligned}S(x)\Lambda (x)&=S(x)\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{i=0}^{d-2}\sum _{j=1}^{v}e_{j}\alpha ^{(c+i)\cdot i_{j}}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\sum _{i=0}^{d-2}\left(\alpha ^{i_{j}}\right)^{i}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\left(\left(x\alpha ^{i_{j}}\right)^{d-1}-1\right)\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right)\end{aligned}}}$

未知数を計算したいので、項を削除することで文脈を単純化することができます。これにより、誤差評価多項式が得られます。 ${\displaystyle e_{j},}$${\displaystyle \left(x\alpha ^{i_{j}}\right)^{d-1}}$

${\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}.}$

おかげで私たちは ${\displaystyle v\leqslant d-1}$

${\displaystyle \Omega (x)=-\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right).}$

ラグランジュ補間法のおかげで、和は1つの被加数に縮退する。${\displaystyle \Lambda }$${\displaystyle x=\alpha ^{-i_{k}}}$

${\displaystyle \Omega \left(\alpha ^{-i_{k}}\right)=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).}$

を得るには、積を取り除く必要があります。の計算済みの根から直接積を計算することもできますが、より単純な形式を使用することもできます。 ${\displaystyle e_{k}}$${\displaystyle \alpha ^{-i_{j}}}$${\displaystyle \Lambda ,}$

正式な派生語として

${\displaystyle \Lambda '(x)=\lambda _{0}\sum _{j=1}^{v}\alpha ^{i_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right),}$

再び、被加数は1つだけになります

${\displaystyle \Lambda '\left(\alpha ^{-i_{k}}\right)=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).}$

それで最後に

${\displaystyle e_{k}=-{\frac {\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right)}{\alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}}.}$

この式は、形式 の形式微分を計算するときに便利です。${\displaystyle \Lambda }$

${\displaystyle \Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}}$

得られるもの:

${\displaystyle \Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},}$

どこ

${\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}$

多項式Λとエラーロケータ多項式の両方を見つける代替プロセスは、杉山康夫による拡張ユークリッド互除法の適応に基づいています。^[10]判読できない文字の修正も簡単にアルゴリズムに組み込むことができます。

読み取り不可能な文字の位置をとします。これらの位置を局所化する多項式を作成します。 読み取り不可能な位置の値を 0 に設定し、シンドロームを計算します。 ${\displaystyle k_{1},...,k_{k}}$${\displaystyle \Gamma (x)=\prod _{i=1}^{k}\left(x\alpha ^{k_{i}}-1\right).}$

フォーニーの公式で既に定義したように、${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.}$

多項式との最小公約数を求める拡張ユークリッドの互除法を実行してみましょう。 目標は最小公約数を見つけることではなく、最大次数の多項式と となる多項式を見つけることです。 の低次保証は、拡張された（ による）定義条件を満たすでしょう。${\displaystyle S(x)\Gamma (x)}$${\displaystyle x^{d-1}.}$${\displaystyle r(x)}$${\displaystyle \lfloor (d+k-3)/2\rfloor }$${\displaystyle a(x),b(x)}$${\displaystyle r(x)=a(x)S(x)\Gamma (x)+b(x)x^{d-1}.}$${\displaystyle r(x)}$${\displaystyle a(x)}$${\displaystyle \Gamma }$${\displaystyle \Lambda .}$

Fourney の公式の の代わりにを定義して使用すると、誤差値が得られます。${\displaystyle \Xi (x)=a(x)\Gamma (x)}$${\displaystyle \Xi }$${\displaystyle \Lambda (x)}$

このアルゴリズムの主な利点は、 Forney の式に必要な 計算を同時に実行できることです。${\displaystyle \Omega (x)=S(x)\Xi (x){\bmod {x}}^{d-1}=r(x)}$

目標は、読み取り可能な位置で受信ワードとできるだけ異なるコードワードを見つけることです。受信ワードを最も近いコードワードとエラーワードの合計として表現する場合、読み取り可能な位置でゼロ以外の数が最小のエラーワードを見つけようとします。シンドロームは条件によってエラーワードを制限します 。${\displaystyle s_{i}}$

${\displaystyle s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.}$

これらの条件を別々に記述することも、多項式を作成することもできます。

${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}}$

指数付近の係数を比較すると${\displaystyle 0}$${\displaystyle d-2.}$

${\displaystyle S(x){\stackrel {\{0,\cdots ,\,d-2\}}{=}}E(x)=\sum _{i=0}^{d-2}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}\alpha ^{cj}x^{i}.}$

位置に判読不能な文字があると仮定すると、シンドロームの集合を次の式で定義されるシンドロームの集合に置き換えることができる。エラーワードに対して、元のシンドロームの集合によるすべての制約が成り立つと仮定すると、 ${\displaystyle k_{1},}$${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}.}$${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$

${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}=\alpha ^{k_{1}}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}-\sum _{j=0}^{n-1}e_{j}\alpha ^{j}\alpha ^{ij}=\sum _{j=0}^{n-1}e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)\alpha ^{ij}.}$

新しい症候群のセットはエラーベクトルを制限する

${\displaystyle f_{j}=e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)}$

元のシンドロームのセットがエラーベクトルを制限したのと同じ方法で、がゼロである座標を除いて、エラー位置を見つけるという目的のために、シンドロームのセットを同様に変更して、判読できない文字をすべて反映させることができます。これにより、シンドロームのセットが短くなります。${\displaystyle e_{j}.}$${\displaystyle k_{1},}$${\displaystyle f_{k_{1}}=0,}$${\displaystyle f_{j}}$${\displaystyle e_{j}=0.}$${\displaystyle k.}$

多項式定式化では、シンドローム集合をシンドローム集合に置き換えると、 ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$

${\displaystyle T(x)=\sum _{i=0}^{d-3}t_{c+i}x^{i}=\alpha ^{k_{1}}\sum _{i=0}^{d-3}s_{c+i}x^{i}-\sum _{i=1}^{d-2}s_{c+i}x^{i-1}.}$

したがって、

${\displaystyle xT(x){\stackrel {\{1,\cdots ,\,d-2\}}{=}}\left(x\alpha ^{k_{1}}-1\right)S(x).}$

をに置き換えた後、べき乗付近の係数に対する式が必要となる。${\displaystyle S(x)}$${\displaystyle S(x)\Gamma (x)}$${\displaystyle k,\cdots ,d-2.}$

判読不能な文字の場合と同様に、与えられた位置の影響を排除するという観点からエラー位置を探すことも考えられます。影響を排除するとすべてゼロからなるシンドロームの集合が得られるような位置を見つけた場合、これらの座標にのみエラーを持つエラーベクトルが存在します。これらの座標の影響を排除する多項式を とすると、次の式が得られます。 ${\displaystyle v}$${\displaystyle \Lambda (x)}$

${\displaystyle S(x)\Gamma (x)\Lambda (x){\stackrel {\{k+v,\cdots ,d-2\}}{=}}0.}$

ユークリッドアルゴリズムでは、最大で（読み取り可能な位置で）エラーを訂正しようとします。エラー数が大きいほど、受信語から同じ距離内にコードワードが多く存在する可能性があるためです。したがって、私たちが探している に対して、方程式は、から始まるべき乗近くの係数に対して成立する必要があります 。${\displaystyle {\tfrac {1}{2}}(d-1-k)}$${\displaystyle \Lambda (x)}$

${\displaystyle k+\left\lfloor {\frac {1}{2}}(d-1-k)\right\rfloor .}$

Forney の式では、スカラーを掛けても同じ結果が得られます。 ${\displaystyle \Lambda (x)}$

ユークリッドのアルゴリズムでは、次数と同じ数の異なる根を持つよりも高い次数を見つけることが起こり得ます。この場合、フォーニーの公式はすべての根のエラーを訂正できますが、とにかくそのような多くのエラーを訂正することは危険です (特に受信語に他の制限がない場合)。通常、より高い次数を取得した後、エラーを訂正しないことに決めます。根の多重度が高い場合、または根の数が次数より少ない場合、訂正は失敗する可能性があります。フォーニーの公式が送信されたアルファベットの外側でエラーを返すことでも失敗が検出されます。 ${\displaystyle \Lambda (x)}$${\displaystyle {\tfrac {1}{2}}(d-1-k)}$${\displaystyle \Lambda (x)}$${\displaystyle \Lambda (x)}$

エラー値とエラー位置を使用してエラーを修正し、エラー位置のエラー値を減算して修正されたコード ベクトルを形成します。

およびを伴う GF(2 ⁴ )の BCH コードを考えます。(これはQR コードで使用されます。) 送信されるメッセージを [1 1 0 1 1]、または多項式表記法でとします。 「チェックサム」シンボルはで割って剰余をとることで計算され、結果はまたは [ 1 0 0 0 0 1 0 1 0 0 ] になります。これらはメッセージに追加されるため、送信されるコードワードは [ 1 1 0 1 1 0 0 0 0 1 0 1 0 0 ] になります。 ${\displaystyle d=7}$${\displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$${\displaystyle M(x)=x^{4}+x^{3}+x+1.}$${\displaystyle x^{10}M(x)}$${\displaystyle g(x)}$${\displaystyle x^{9}+x^{4}+x^{2}}$

ここで、送信時に2つのビットエラーがあったと仮定すると、受信コードワードは[1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]となります。多項式表記では次のようになります。

${\displaystyle R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x^{5}+x^{4}+x^{2}}$

エラーを修正するには、まずシンドロームを計算します。次の式をとれば、 次の拡張行列の行を削減して、Peterson 手順を適用します。 ${\displaystyle \alpha =0010,}$${\displaystyle s_{1}=R(\alpha ^{1})=1011,}$ ${\displaystyle s_{2}=1001,}$ ${\displaystyle s_{3}=1011,}$ ${\displaystyle s_{4}=1101,}$ ${\displaystyle s_{5}=0001,}$${\displaystyle s_{6}=1001.}$

${\displaystyle \left[S_{3\times 3}|C_{3\times 1}\right]={\begin{bmatrix}s_{1}&s_{2}&s_{3}&s_{4}\\s_{2}&s_{3}&s_{4}&s_{5}\\s_{3}&s_{4}&s_{5}&s_{6}\end{bmatrix}}={\begin{bmatrix}1011&1001&1011&1101\\1001&1011&1101&0001\\1011&1101&0001&1001\end{bmatrix}}\Rightarrow {\begin{bmatrix}0001&0000&1000&0111\\0000&0001&1011&0001\\0000&0000&0000&0000\end{bmatrix}}}$

ゼロ行があるため、S _3×3は特異ですが、コードワードに 2 つのエラーしか導入されていないため、これは驚くことではありません。ただし、行列の左上隅は[ S _2×2 | C _2×1 ]と同じであり、解が生成されます。 結果として得られるエラー位置多項式は、およびにゼロを持つ次のようになります。 の指数は、エラーの位置に対応します。この例では、可能な値は 1 のみであるため、エラー値を計算する必要はありません。 ${\displaystyle \lambda _{2}=1000,}$ ${\displaystyle \lambda _{1}=1011.}$${\displaystyle \Lambda (x)=1000x^{2}+1011x+0001,}$${\displaystyle 0100=\alpha ^{-13}}$${\displaystyle 0111=\alpha ^{-5}.}$${\displaystyle \alpha }$

同じシナリオですが、受信したワードに 2 つの判読できない文字 [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ] があるとします。判読できない文字をゼロに置き換え、それらの位置を反映する多項式を作成します。シンドロームとを計算します(GF(2 ⁴ ) 同型に依存しない log 表記を使用します。計算チェックには、前の例で使用したのと同じ加算表現を使用できます。の累乗の 16 進数表記は、1、2、4、8、3、6、C、B、5、A、7、E、F、D、9 の順で、加算はビット単位の XOR に基づきます。) ${\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).}$${\displaystyle s_{1}=\alpha ^{-7},s_{2}=\alpha ^{1},s_{3}=\alpha ^{4},s_{4}=\alpha ^{2},s_{5}=\alpha ^{5},}$${\displaystyle s_{6}=\alpha ^{-7}.}$${\displaystyle \alpha }$

シンドローム多項式を作ってみましょう

${\displaystyle S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{5}x^{4}+\alpha ^{-7}x^{5},}$

計算する

${\displaystyle S(x)\Gamma (x)=\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}.}$

拡張ユークリッドの互除法を実行します。

${\displaystyle {\begin{aligned}&{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+2\alpha ^{7}x^{6}+2\alpha ^{-3}x^{7}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{-5}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\left(\alpha ^{-7}+\alpha ^{3}\right)x+\left(\alpha ^{3}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-5}+\alpha ^{-6}\right)x^{3}+\left(\alpha ^{3}+\alpha ^{1}\right)x^{4}+2\alpha ^{-6}x^{5}+2x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\left(1+\alpha ^{-4}\right)+\left(\alpha ^{1}+\alpha ^{2}\right)x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-5}+\alpha ^{-4}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\left(\alpha ^{7}+\alpha ^{-7}\right)+\left(2\alpha ^{-7}+\alpha ^{4}\right)x+\left(\alpha ^{-5}+\alpha ^{-6}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-7}+\alpha ^{-4}+\alpha ^{6}\right)x^{3}+\left(\alpha ^{4}+\alpha ^{-6}+\alpha ^{-1}\right)x^{4}+2\alpha ^{5}x^{5}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}{\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.\end{aligned}}}$

我々は最大3次の多項式に到達しており、

${\displaystyle {\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},}$

私たちは得る

${\displaystyle {\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.}$

したがって、

${\displaystyle S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}\right)-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)x^{6}=\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}.}$

心配しないでください。の根を力ずくで見つけます。根は であり、 です(たとえば、見つけた後、対応する monom で割ることができ、結果として得られる monom の根は簡単に見つけることができます)。 ${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}.}$${\displaystyle \lambda _{0}\neq 1.}$${\displaystyle \Lambda .}$${\displaystyle \alpha ^{2},}$${\displaystyle \alpha ^{10}}$${\displaystyle \alpha ^{2}}$${\displaystyle \Lambda }$${\displaystyle \left(x-\alpha ^{2}\right)}$

させて

${\displaystyle {\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{-5}x^{4}\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}{\bmod {x^{6}}}\end{aligned}}}$

式を使ってエラー値を調べてみましょう

${\displaystyle e_{j}=-{\frac {\Omega \left(\alpha ^{-i_{j}}\right)}{\Xi '\left(\alpha ^{-i_{j}}\right)}},}$

私たち のルーツはどこにあるのか${\displaystyle \alpha ^{-i_{j}}}$${\displaystyle \Xi (x).}$ ${\displaystyle \Xi '(x)=\alpha ^{2}x^{2}.}$

${\displaystyle {\begin{aligned}e_{1}&=-{\frac {\Omega (\alpha ^{4})}{\Xi '(\alpha ^{4})}}={\frac {\alpha ^{-4}+\alpha ^{-7}+\alpha ^{-5}+\alpha ^{7}}{\alpha ^{-5}}}={\frac {\alpha ^{-5}}{\alpha ^{-5}}}=1\\e_{2}&=-{\frac {\Omega (\alpha ^{7})}{\Xi '(\alpha ^{7})}}={\frac {\alpha ^{-4}+\alpha ^{-4}+\alpha ^{1}+\alpha ^{1}}{\alpha ^{1}}}=0\\e_{3}&=-{\frac {\Omega (\alpha ^{10})}{\Xi '(\alpha ^{10})}}={\frac {\alpha ^{-4}+\alpha ^{-1}+\alpha ^{7}+\alpha ^{-5}}{\alpha ^{7}}}={\frac {\alpha ^{7}}{\alpha ^{7}}}=1\\e_{4}&=-{\frac {\Omega (\alpha ^{2})}{\Xi '(\alpha ^{2})}}={\frac {\alpha ^{-4}+\alpha ^{6}+\alpha ^{6}+\alpha ^{1}}{\alpha ^{6}}}={\frac {\alpha ^{6}}{\alpha ^{6}}}=1\end{aligned}}}$

事実、それは驚くべきことではありません。 ${\displaystyle e_{3}=e_{4}=1,}$

したがって、修正されたコードは [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0] になります。

エラー数が少ない場合のアルゴリズムの動作を示しましょう。受信した単語が [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ] であるとします。

再び、判読できない文字をゼロに置き換え、それらの位置を反映する多項式を作成します。 シンドロームを計算し、 シンドローム多項式を作成します。 ${\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).}$${\displaystyle s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1},s_{5}=\alpha ^{0},}$${\displaystyle s_{6}=\alpha ^{2}.}$

${\displaystyle {\begin{aligned}S(x)&=\alpha ^{4}+\alpha ^{-7}x+\alpha ^{1}x^{2}+\alpha ^{1}x^{3}+\alpha ^{0}x^{4}+\alpha ^{2}x^{5},\\S(x)\Gamma (x)&=\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}.\end{aligned}}}$

拡張ユークリッドの互除法を実行してみましょう。

${\displaystyle {\begin{aligned}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}&={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}\\x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+2\alpha ^{-1}x^{6}+2\alpha ^{6}x^{7}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{3}+\alpha ^{1}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\left(\alpha ^{-5}+\alpha ^{5}\right)x+2\alpha ^{-7}x^{2}+2\alpha ^{6}x^{3}+2\alpha ^{4}x^{4}+2\alpha ^{2}x^{5}+2x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\left(1+\alpha ^{2}\right)+\left(\alpha ^{0}+\alpha ^{-6}\right)x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}\end{aligned}}}$

我々は最大3次の多項式に到達しており、

${\displaystyle {\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},}$

私たちは得る

${\displaystyle {\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}.}$

したがって、

${\displaystyle S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{1}x\right)-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)x^{6}=\alpha ^{7}+\alpha ^{0}x.}$

心配しないでください。${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{1}x.}$${\displaystyle \lambda _{0}\neq 1.}$${\displaystyle \Lambda (x)}$${\displaystyle \alpha ^{3-1}.}$

させて

${\displaystyle {\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{-7}x+\alpha ^{-4}x^{2}+\alpha ^{5}x^{3},\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{7}+\alpha ^{0}x{\bmod {x^{6}}}\end{aligned}}}$

多項式の根である式を使用してエラー値を調べてみましょう${\displaystyle e_{j}=-\Omega \left(\alpha ^{-i_{j}}\right)/\Xi '\left(\alpha ^{-i_{j}}\right),}$${\displaystyle \alpha ^{-i_{j}}}$${\displaystyle \Xi (x).}$

${\displaystyle \Xi '(x)=\alpha ^{-7}+\alpha ^{5}x^{2}.}$

私たちは

${\displaystyle {\begin{aligned}e_{1}&=-{\frac {\Omega \left(\alpha ^{4}\right)}{\Xi '\left(\alpha ^{4}\right)}}={\frac {\alpha ^{7}+\alpha ^{4}}{\alpha ^{-7}+\alpha ^{-2}}}={\frac {\alpha ^{3}}{\alpha ^{3}}}=1\\e_{2}&=-{\frac {\Omega \left(\alpha ^{7}\right)}{\Xi '\left(\alpha ^{7}\right)}}={\frac {\alpha ^{7}+\alpha ^{7}}{\alpha ^{-7}+\alpha ^{4}}}=0\\e_{3}&=-{\frac {\Omega \left(\alpha ^{2}\right)}{\Xi '\left(\alpha ^{2}\right)}}={\frac {\alpha ^{7}+\alpha ^{2}}{\alpha ^{-7}+\alpha ^{-6}}}={\frac {\alpha ^{-3}}{\alpha ^{-3}}}=1\end{aligned}}}$

驚くべきことではない 事実。${\displaystyle e_{3}=1}$

したがって、修正されたコードは [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0] になります。

• Hocquenghem, A. (1959 年 9 月)、「CodesCorrecteurs d'erreurs」、Ciffres (フランス語)、2、パリ: 147–156
• Bose, RC ; Ray-Chaudhuri, DK (1960 年 3 月)、「誤り訂正バイナリ グループ コードの一クラスについて」(PDF)、Information and Control、3 (1): 68–79、doi :10.1016/s0019-9958(60)90287-4、ISSN  0890-5401、2022年 10 月 9 日にオリジナルからアーカイブ(PDF)

• Gill, John (nd)、EE387 ノート #7、配布資料 #28 (PDF)、スタンフォード大学、pp. 42–45、2022-10-09のオリジナルからアーカイブ(PDF) 、2010 年4 月 21 日取得^{[リンク切れ‍ ]}コースノートは2012年に作り直されているようです: http://www.stanford.edu/class/ee387/ 2013-06-05にWayback Machineでアーカイブされました
• ゴレンスタイン、ダニエル;ピーターソン、W. ウェスリー; ツィラー、ニール (1960)、「2 つのエラーを訂正するボーズ-チャウドゥリ コードは準完全である」、情報制御、3 (3): 291–294、doi : 10.1016/s0019-9958(60)90877-9
• リドル、ルドルフ、ピルツ、ギュンター（1999）、応用抽象代数（第2版）、ジョン・ワイリー
• リード、アーヴィング S. ; チェン、シュエミン (1999)、データネットワークのエラー制御コーディング、ボストン、マサチューセッツ州:クルーワー アカデミック パブリッシャー、ISBN 0-7923-8528-4

• Blahut, Richard E. (2003)、「データ伝送のための代数コード（第2版）」、ケンブリッジ大学出版局、ISBN 0-521-55374-1
• ギルバート、WJ; ニコルソン、WK (2004)、現代代数学の応用(第 2 版)、ジョン ワイリー
• Lin, S.; Costello, D. (2004)、エラー制御コーディング：基礎と応用、Englewood Cliffs、NJ：Prentice-Hall
• MacWilliams, FJ; Sloane, NJA (1977)、The Theory of Error-Correcting Codes、ニューヨーク、NY: North-Holland Publishing Company
• Rudra、Atri、CSE 545、誤り訂正コード：組合せ論、アルゴリズムとアプリケーション、バッファロー大学、2012-12-18 にオリジナルからアーカイブ