Error correction code
符号理論 において 、 ボーズ・ショードゥリ・オッケンゲム符号 （ BCH符号）は、 有限体 （ ガロア体 とも呼ばれる）上の 多項式 を用いて構成される 巡回 誤り訂正符号 の一種である。BCH符号は1959年にフランスの数学者 アレクシ・オッケンゲム によって発明され 、1960年には ラージ・チャンドラ・ボース と DK・レイ＝ショードゥリ によって独立に発明された。 [1] [2] [3] ボーズ・ショードゥリ・オッケンゲム という名称 （および頭字語の BCH ）は、発明者の姓の頭文字（レイ＝ショードゥリの場合は誤り）に由来する。
BCH符号の重要な特徴の一つは、符号設計時に、符号によって訂正可能なシンボルエラーの数を正確に制御できることです。特に、複数ビットのエラーを訂正できるバイナリBCH符号を設計することが可能です。BCH符号のもう一つの利点は、 シンドローム復号法 と呼ばれる 代数的 手法を用いて容易に復号できることです。これにより、小型で低消費電力の電子ハードウェアを用いて、これらの符号のデコーダの設計を簡素化できます。
BCHコードは、衛星通信、 [4] コンパクトディスク プレーヤー、 DVD 、 ディスクドライブ 、 USBフラッシュドライブ 、 ソリッドステートドライブ 、 [5] 2 次元バーコード などのアプリケーションで使用されます 。
定義と説明
原始狭義BCH符号 素数 q と 素べき q m （正の整数 m と d で d ≤ q m − 1 ） が与えられたとき、 有限体 （またはガロア体） GF( q ) 上の、コード長 n = q m − 1 で 距離 が少なくとも d である原始狭義 BCH コードが 次の方法で構築されます。
α を GF( q m ) の 原始元 とする 。任意の正の整数 i について 、 m i ( x )を α i の GF( q ) に係数を持つ 最小多項式 とする 。BCH 符号の 生成多項式は、 最小公倍数 g ( x ) = lcm( m 1 ( x ),…, m d − 1 ( x ))として定義される。 g ( x )は GF( q ) に係数を持つ多項式であり、 x n − 1 を割り切ること がわかる 。したがって、 g ( x ) によって定義される 多項式符号 は巡回符号である。
例 q = 2 、 m = 4 （したがって n = 15 ） とする。GF (16) = GF(2 4 ) の d の値を、原始元 α ( z ) = z を用いて、約分多項式 z 4 + z + 1 に基づいて検討する
。GF (2) に係数を持つ最小多項式 m i ( x ) は14個あり、
m i ( α i ) mod ( z 4 + z + 1 ) = 0. {\displaystyle m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+1\right)}}=0.} 最小多項式は
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. {\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コードの 生成多項式は次のようになる。 d = 2 , 3 {\displaystyle d=2,3}
g ( x ) = l c m ( m 1 ( x ) , m 2 ( x ) ) = m 1 ( x ) = x 4 + x + 1. {\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コードの 生成多項式は次のようになる。 d = 4 , 5 {\displaystyle d=4,5}
g ( x ) = l c m ( m 1 ( x ) , m 2 ( x ) , m 3 ( x ) , m 4 ( x ) ) = m 1 ( x ) m 3 ( x ) = ( x 4 + x + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) = x 8 + x 7 + x 6 + x 4 + 1. {\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コードの 生成多項式は次のようになる。 d = 6 , 7 {\displaystyle d=6,7}
g ( x ) = l c m ( 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 ) = ( x 4 + x + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) ( x 2 + x + 1 ) = x 10 + x 8 + x 5 + x 4 + x 2 + x + 1. {\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コードの 生成多項式は d = 8 {\displaystyle d=8}
g ( x ) = l c m ( m 1 ( x ) , m 2 ( x ) , . . . , m 14 ( x ) ) = m 1 ( x ) m 3 ( x ) m 5 ( x ) m 7 ( x ) = ( x 4 + x + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) ( x 2 + x + 1 ) ( x 4 + x 3 + 1 ) = x 14 + x 13 + x 12 + ⋯ + x 2 + x + 1. {\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と11111111111111（単純な 繰り返しコード ）の2つのコードワードしかありません。
一般的なBCHコード 一般的な BCH コードは、2 つの点で原始的な狭義の BCH コードと異なります。
まず、の原始元である という要件を 緩和することができます。この要件を緩和すると、コードの長さは から の 元 の 大き さに変わります。 α {\displaystyle \alpha } G F ( q m ) {\displaystyle \mathrm {GF} (q^{m})} q m − 1 {\displaystyle q^{m}-1} o r d ( α ) , {\displaystyle \mathrm {ord} (\alpha ),} α . {\displaystyle \alpha .}
第二に、生成多項式の連続根は 、 α c , … , α c + d − 2 {\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}} α , … , α d − 1 . {\displaystyle \alpha ,\ldots ,\alpha ^{d-1}.}
定義。 が素数冪 である 有限体を考える。 が を法 と する 乗法位数 と なるような正の整数を選ぶ。 G F ( q ) , {\displaystyle GF(q),} q {\displaystyle q} m , n , d , c {\displaystyle m,n,d,c} 2 ≤ d ≤ n , {\displaystyle 2\leq d\leq n,} g c d ( n , q ) = 1 , {\displaystyle {\rm {gcd}}(n,q)=1,} m {\displaystyle m} q {\displaystyle q} n . {\displaystyle n.}
前と同様に、 をの 原始 平方根 とし 、 を の 最小多項式 と する。BCH コードの生成多項式は、 最小公倍数として定義される。 α {\displaystyle \alpha } n {\displaystyle n} G F ( q m ) , {\displaystyle GF(q^{m}),} m i ( x ) {\displaystyle m_{i}(x)} G F ( q ) {\displaystyle GF(q)} α i {\displaystyle \alpha ^{i}} i . {\displaystyle i.} g ( x ) = l c m ( m c ( x ) , … , m c + d − 2 ( x ) ) . {\displaystyle g(x)={\rm {lcm}}(m_{c}(x),\ldots ,m_{c+d-2}(x)).}
注: 簡略化された定義のように、 は 1 であり、 を法とする の順序 は したがって、簡略化された定義は、実際には一般的な定義の特殊なケースです。 n = q m − 1 {\displaystyle n=q^{m}-1} g c d ( n , q ) {\displaystyle {\rm {gcd}}(n,q)} q {\displaystyle q} n {\displaystyle n} m . {\displaystyle m.}
特殊なケース を持つ BCH コードは、 狭義の BCH コード と呼ばれます 。 c = 1 {\displaystyle c=1} を持つ BCH コードは プリミティブ と呼ばれます 。 n = q m − 1 {\displaystyle n=q^{m}-1} BCH 符号の 生成多項式は、 の係数を持つ 。一般に、 上の巡回符号で生成多項式が である ものは、 上の BCH 符号と呼ばれる。 上の BCH 符号 と、 の連続するべきを根とする生成多項式は、 リード・ソロモン符号 の一種であり、 デコーダ（シンドローム）アルファベットがチャネル（データと生成多項式）アルファベットと同じで、 のすべての要素が である 。 [6] もう一方のタイプのリード・ソロモン符号は、 BCH 符号ではない、 オリジナル ビューのリード・ソロモン符号である。 g ( x ) {\displaystyle g(x)} G F ( q ) . {\displaystyle \mathrm {GF} (q).} G F ( q p ) {\displaystyle \mathrm {GF} (q^{p})} g ( x ) {\displaystyle g(x)} G F ( q p ) . {\displaystyle \mathrm {GF} (q^{p}).} G F ( q m ) {\displaystyle \mathrm {GF} (q^{m})} g ( x ) {\displaystyle g(x)} α {\displaystyle \alpha } G F ( q m ) {\displaystyle \mathrm {GF} (q^{m})}
プロパティ BCH符号の生成多項式の次数は最大 である 。さらに、 かつ ならば 、 生成多項式の次数は最大 である 。 ( d − 1 ) m {\displaystyle (d-1)m} q = 2 {\displaystyle q=2} c = 1 {\displaystyle c=1} d m / 2 {\displaystyle dm/2}
BCH コードの最小ハミング距離は少なくとも です 。 d {\displaystyle d}
証拠
が非ゼロ項の数 よりも少ない符号語である と仮定する。すると p ( x ) {\displaystyle p(x)} d {\displaystyle d}
p ( x ) = b 1 x k 1 + ⋯ + b d − 1 x k d − 1 , where k 1 < k 2 < ⋯ < k d − 1 . {\displaystyle p(x)=b_{1}x^{k_{1}}+\cdots +b_{d-1}x^{k_{d-1}},{\text{ where }}k_{1}<k_{2}<\cdots <k_{d-1}.} はの根である ことを思い出し、 したがって の根であることを覚えておいてください 。これは 、 が各 に対して以下の式を満たすことを意味します 。 α c , … , α c + d − 2 {\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}} g ( x ) , {\displaystyle g(x),} p ( x ) {\displaystyle p(x)} b 1 , … , b d − 1 {\displaystyle b_{1},\ldots ,b_{d-1}} i ∈ { c , … , c + d − 2 } {\displaystyle i\in \{c,\dotsc ,c+d-2\}}
p ( α i ) = b 1 α i k 1 + b 2 α i k 2 + ⋯ + b d − 1 α i k d − 1 = 0. {\displaystyle p(\alpha ^{i})=b_{1}\alpha ^{ik_{1}}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0.} 行列形式では、
[ α c k 1 α c k 2 ⋯ α c k d − 1 α ( c + 1 ) k 1 α ( c + 1 ) k 2 ⋯ α ( c + 1 ) k d − 1 ⋮ ⋮ ⋮ α ( c + d − 2 ) k 1 α ( c + d − 2 ) k 2 ⋯ α ( c + d − 2 ) k d − 1 ] [ b 1 b 2 ⋮ b d − 1 ] = [ 0 0 ⋮ 0 ] . {\displaystyle {\begin{bmatrix}\alpha ^{ck_{1}}&\alpha ^{ck_{2}}&\cdots &\alpha ^{ck_{d-1}}\\\alpha ^{(c+1)k_{1}}&\alpha ^{(c+1)k_{2}}&\cdots &\alpha ^{(c+1)k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(c+d-2)k_{1}}&\alpha ^{(c+d-2)k_{2}}&\cdots &\alpha ^{(c+d-2)k_{d-1}}\\\end{bmatrix}}{\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{d-1}\end{bmatrix}}={\begin{bmatrix}0\\0\\\vdots \\0\end{bmatrix}}.} この行列の行列式は
( ∏ i = 1 d − 1 α c k i ) det ( 1 1 ⋯ 1 α k 1 α k 2 ⋯ α k d − 1 ⋮ ⋮ ⋮ α ( d − 2 ) k 1 α ( d − 2 ) k 2 ⋯ α ( d − 2 ) k d − 1 ) = ( ∏ i = 1 d − 1 α c k i ) det ( V ) . {\displaystyle \left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det {\begin{pmatrix}1&1&\cdots &1\\\alpha ^{k_{1}}&\alpha ^{k_{2}}&\cdots &\alpha ^{k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(d-2)k_{1}}&\alpha ^{(d-2)k_{2}}&\cdots &\alpha ^{(d-2)k_{d-1}}\\\end{pmatrix}}=\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det(V).} この行列は ヴァンデルモンド行列 であり 、その行列式は V {\displaystyle V}
det ( V ) = ∏ 1 ≤ i < j ≤ d − 1 ( α k j − α k i ) , {\displaystyle \det(V)=\prod _{1\leq i<j\leq d-1}\left(\alpha ^{k_{j}}-\alpha ^{k_{i}}\right),} これはゼロではない。したがって 、 b 1 , … , b d − 1 = 0 , {\displaystyle b_{1},\ldots ,b_{d-1}=0,} p ( x ) = 0. {\displaystyle p(x)=0.}
BCH コードは巡回的です。
証拠
長さ の多項式コードは 、その生成多項式が を割り切る場合のみ巡回的です。 は 根を持つ最小多項式なので、 の それぞれが の根であることを確認すれば十分です。 これは 、 が定義により の 乗根である という事実から直ちにわかります 。 n {\displaystyle n} x n − 1. {\displaystyle x^{n}-1.} g ( x ) {\displaystyle g(x)} α c , … , α c + d − 2 , {\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2},} α c , … , α c + d − 2 {\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}} x n − 1. {\displaystyle x^{n}-1.} α {\displaystyle \alpha } n {\displaystyle n}
エンコーディング 生成多項式の倍数である任意の多項式は有効な BCH 符号語であるため、BCH エンコーディングは単に生成多項式を因数として持つ多項式を見つけるプロセスになります。
BCH符号自体は、多項式の係数の意味について規定していません。概念的には、BCH復号アルゴリズムの唯一の関心事は、受信した符号語とのハミング距離が最小となる有効な符号語を見つけることです。したがって、BCH符号は、実装者が符号化された多項式にメッセージを埋め込む方法に応じて、 組織符号 として実装することも、そうでない場合もあります。
非体系的符号化：要素としてのメッセージ 生成元の倍数となる多項式を見つける最も簡単な方法は、任意の多項式と生成元の積を計算することです。この場合、メッセージのシンボルを係数として任意の多項式を選択できます。
s ( x ) = p ( x ) g ( x ) {\displaystyle s(x)=p(x)g(x)} 例として、 POCSAG などで用いられる(31, 21)二進BCH符号で用いられる生成多項式 を考えてみましょう 。21ビットのメッセージ{1011011101111111101}を符号化するには、まず を 上の多項式として表します 。 g ( x ) = x 10 + x 9 + x 8 + x 6 + x 5 + x 3 + 1 {\displaystyle g(x)=x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1} G F ( 2 ) {\displaystyle GF(2)}
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 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} 次に、（ についても ）計算します。 G F ( 2 ) {\displaystyle GF(2)}
s ( x ) = p ( x ) g ( 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 ) ( x 10 + x 9 + x 8 + x 6 + x 5 + x 3 + 1 ) = 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 {\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}}} したがって、送信されるコードワードは {110011101001111011101110101} です。
受信機はこれらのビットを係数として利用し 、有効なコードワードを保証するために誤り訂正を行った後、再計算することができる。 s ( x ) {\displaystyle s(x)} p ( x ) = s ( x ) / g ( x ) {\displaystyle p(x)=s(x)/g(x)}
体系的な符号化：メッセージを接頭辞として 体系的符号とは、メッセージが符号語内のどこかにそのまま現れる符号です。したがって、体系的BCH符号化では、まずメッセージ多項式を符号語多項式に埋め込み、次に残りの（メッセージ以外の）項の係数を調整して、 が で割り切れるようにします 。 s ( x ) {\displaystyle s(x)} g ( x ) {\displaystyle g(x)}
この符号化方法は、被除数から剰余を引くと除数の倍数になるという事実を利用しています。したがって、前と同じようにメッセージ多項式を取り、それを （メッセージを剰余から「シフト」させるため） 乗算すると、多項式の ユークリッド除算を 用いて次の式が得られます。 p ( x ) {\displaystyle p(x)} x n − k {\displaystyle x^{n-k}}
p ( x ) x n − k = q ( x ) g ( x ) + r ( x ) {\displaystyle p(x)x^{n-k}=q(x)g(x)+r(x)} ここで、は有効な符号語である ことがわかります。 は常に の次数より小さい次数 （ の次数 ）なので、 から を引いて もメッセージ係数は変化しません。したがって、 は となります 。 q ( x ) g ( x ) {\displaystyle q(x)g(x)} r ( x ) {\displaystyle r(x)} n − k {\displaystyle n-k} g ( x ) {\displaystyle g(x)} p ( x ) x n − k {\displaystyle p(x)x^{n-k}} s ( x ) {\displaystyle s(x)}
s ( x ) = q ( x ) g ( x ) = p ( x ) x n − k − r ( x ) {\displaystyle s(x)=q(x)g(x)=p(x)x^{n-k}-r(x)} にわたって（つまり、バイナリ BCH コードの場合）、このプロセスは 巡回冗長検査 を追加することと区別がつかず、体系的なバイナリ BCH コードがエラー検出の目的でのみ使用される場合、BCH コードは 巡回冗長検査の数学 の一般化にすぎないことがわかります 。 G F ( 2 ) {\displaystyle GF(2)}
体系的符号化の利点は、受信側が 誤り訂正を実行した後、最初の係数の後のすべてを破棄することで元のメッセージを復元できることです。 k {\displaystyle k}
デコード BCH符号の復号アルゴリズムは数多く存在します。最も一般的なアルゴリズムは以下の概要に従います。
受信ベクトルの シンドローム s jを計算する シンドロームから エラー数 t とエラー位置多項式 Λ(x)を決定する エラー位置多項式の根を計算してエラー位置 X iを見つける これらのエラー位置における エラー値 Y iを計算する エラーを修正する これらのステップのいくつかにおいて、デコードアルゴリズムは受信ベクトルにエラーが多すぎて訂正できないと判断することがあります。例えば、適切な t 値が見つからない場合、訂正は失敗します。切り捨てられた（プリミティブではない）コードでは、エラー位置が範囲外になることがあります。受信ベクトルにコードが訂正できる以上のエラーがある場合、デコーダーは送信されたメッセージとは異なる、一見有効なメッセージを無意識のうちに生成する可能性があります。
症候群を計算する 受信ベクトルは正しいコードワード と未知のエラーベクトル の和である。 シンドローム値は 多項式として考え、それを次のように評価することによって形成される。 したがって、シンドロームは [7]である。 R {\displaystyle R} C {\displaystyle C} E . {\displaystyle E.} R {\displaystyle R} α c , … , α c + d − 2 . {\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}.}
s j = R ( α j ) = C ( α j ) + E ( α j ) {\displaystyle s_{j}=R\left(\alpha ^{j}\right)=C\left(\alpha ^{j}\right)+E\left(\alpha ^{j}\right)} 〜の ために j = c {\displaystyle j=c} c + d − 2. {\displaystyle c+d-2.}
は のゼロであり、その 倍数である ため、 シンドローム値を調べるとエラー ベクトルが分離され、それを解き始めることができます。 α j {\displaystyle \alpha ^{j}} g ( x ) , {\displaystyle g(x),} C ( x ) {\displaystyle C(x)} C ( α j ) = 0. {\displaystyle C\left(\alpha ^{j}\right)=0.}
エラーがない場合、 すべての シンドロームがゼロであれば、デコードは完了です。 s j = 0 {\displaystyle s_{j}=0} j . {\displaystyle j.}
エラー位置多項式を計算する 非ゼロのシンドロームが存在する場合、エラーが発生します。デコーダーは、エラーの数とそれらのエラーの位置を特定する必要があります。
単一のエラーがある場合、これを と書きます。 は エラーの位置、 は エラーの大きさです。最初の2つのシンドロームは E ( x ) = e x i , {\displaystyle E(x)=e\,x^{i},} i {\displaystyle i} e {\displaystyle e}
s c = e α c i s c + 1 = e α ( c + 1 ) i = α i s c {\displaystyle {\begin{aligned}s_{c}&=e\,\alpha ^{c\,i}\\s_{c+1}&=e\,\alpha ^{(c+1)\,i}=\alpha ^{i}s_{c}\end{aligned}}} これらを組み合わせることで、（リード・ソロモン符号の場合は完全に決定する）
についての 計算 と情報の提供が可能になります。 e {\displaystyle e} i {\displaystyle i}
2つ以上のエラーがある場合、
E ( x ) = e 1 x i 1 + e 2 x i 2 + ⋯ {\displaystyle E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,} 未知のもの に対する結果として生じるシンドロームをどうやって解決し始めるかはすぐには明らかではない。 e k {\displaystyle e_{k}} i k . {\displaystyle i_{k}.}
最初のステップは、計算されたシンドロームと互換性があり、最小限の ロケータ多項式と互換性のあるものを見つけることです。 t , {\displaystyle t,}
Λ ( x ) = ∏ j = 1 t ( x α i j − 1 ) {\displaystyle \Lambda (x)=\prod _{j=1}^{t}\left(x\alpha ^{i_{j}}-1\right)} このタスクでよく使われる 3 つのアルゴリズムは次のとおりです。
Peterson-Gorenstein-Zierler アルゴリズム ベルレカンプ・マッシーアルゴリズム 杉山ユークリッド互除法
Peterson-Gorenstein-Zierler アルゴリズム ピーターソンのアルゴリズム は、一般化BCH復号手順のステップ2です。ピーターソンのアルゴリズムは、 多項式の
誤り位置多項式係数を計算するために使用されます。 λ 1 , λ 2 , … , λ v {\displaystyle \lambda _{1},\lambda _{2},\dots ,\lambda _{v}}
Λ ( x ) = 1 + λ 1 x + λ 2 x 2 + ⋯ + λ v x 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 と します。
まず、 シンドローム値を要素とする行列
を生成する。 S v × v {\displaystyle S_{v\times v}} S v × v = [ s c s c + 1 … s c + v − 1 s c + 1 s c + 2 … s c + v ⋮ ⋮ ⋱ ⋮ s c + v − 1 s c + v … s c + 2 v − 2 ] . {\displaystyle S_{v\times v}={\begin{bmatrix}s_{c}&s_{c+1}&\dots &s_{c+v-1}\\s_{c+1}&s_{c+2}&\dots &s_{c+v}\\\vdots &\vdots &\ddots &\vdots \\s_{c+v-1}&s_{c+v}&\dots &s_{c+2v-2}\end{bmatrix}}.} 要素を持つベクトル を生成する c v × 1 {\displaystyle c_{v\times 1}} C v × 1 = [ s c + v s c + v + 1 ⋮ s c + 2 v − 1 ] . {\displaystyle C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.} 未知の多項式係数を次のように表す 。 Λ {\displaystyle \Lambda } Λ v × 1 = [ λ v λ v − 1 ⋮ λ 1 ] . {\displaystyle \Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.} 行列方程式を形成する S v × v Λ v × 1 = − C v × 1 . {\displaystyle S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}.} 行列の行列式 がゼロでない場合、実際にこの行列の逆行列を見つけて、未知の値の値を解くことができます 。 S v × v {\displaystyle S_{v\times v}} Λ {\displaystyle \Lambda } もし そうなら、 det ( S v × v ) = 0 , {\displaystyle \det \left(S_{v\times v}\right)=0,} もし v = 0 {\displaystyle v=0} それから 空のエラーロケータ多項式を宣言する ピーターソン手順を停止します。 終わり セット v ← v − 1 {\displaystyle v\leftarrow v-1} ピーターソンの解読の始まりから、より小さな S v × v {\displaystyle S_{v\times v}} の値が得られたら 、エラーロケータ多項式が得られます。 Λ {\displaystyle \Lambda } ピーターソン手順を停止します。
因数分解誤差位置多項式 多項式が得られたので、その根は、 例えば Chien探索 アルゴリズムを用いて、力ずくで見つけることができます 。原始元の指数乗は、 受信語におけるエラーの発生位置を示します。そのため、この多項式は「エラーロケータ」多項式と呼ばれます。 Λ ( x ) {\displaystyle \Lambda (x)} Λ ( x ) = ( α i 1 x − 1 ) ( α i 2 x − 1 ) ⋯ ( α i v x − 1 ) {\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（すべての文字が読み取り可能な場合）の場合、これは簡単です。受信ワードのビットをこれらの位置で反転するだけで、訂正されたコードワードが得られます。より一般的なケースでは、誤りの重みは 線形連立方程式を解くことで決定できます。 e j {\displaystyle e_{j}}
s c = e 1 α c i 1 + e 2 α c i 2 + ⋯ s c + 1 = e 1 α ( c + 1 ) i 1 + e 2 α ( c + 1 ) i 2 + ⋯ ⋮ {\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}}}
フォーニーアルゴリズム ただし、 Forney アルゴリズム と呼ばれるより効率的な方法があります 。
させて
S ( x ) = s c + s c + 1 x + s c + 2 x 2 + ⋯ + s c + d − 2 x d − 2 . {\displaystyle S(x)=s_{c}+s_{c+1}x+s_{c+2}x^{2}+\cdots +s_{c+d-2}x^{d-2}.} v ⩽ d − 1 , λ 0 ≠ 0 Λ ( x ) = ∑ i = 0 v λ i x i = λ 0 ∏ k = 0 v ( α − i k x − 1 ) . {\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]
Ω ( x ) ≡ S ( x ) Λ ( x ) mod x d − 1 {\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}} ついに：
Λ ′ ( x ) = ∑ i = 1 v i ⋅ λ i x i − 1 , {\displaystyle \Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},} どこ
i ⋅ x := ∑ k = 1 i x . {\displaystyle i\cdot x:=\sum _{k=1}^{i}x.} シンドロームがエラーワードによって説明できる場合、エラーワードは位置 でのみ非ゼロになる可能性があり 、エラー値は i k {\displaystyle i_{k}}
e k = − α i k Ω ( α − i k ) α c ⋅ i k Λ ′ ( α − 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なので、式は次のように簡略化されます。
e k = − Ω ( α − i k ) Λ ′ ( α − i k ) . {\displaystyle e_{k}=-{\Omega \left(\alpha ^{-i_{k}}\right) \over \Lambda '\left(\alpha ^{-i_{k}}\right)}.}
フォーニーアルゴリズムの計算の説明 これは、 ラグランジュ補間 と 関数生成 の手法に基づいています。
簡単に するために、 と を 仮定する と、 S ( x ) Λ ( x ) , {\displaystyle S(x)\Lambda (x),} λ k = 0 {\displaystyle \lambda _{k}=0} k > v , {\displaystyle k>v,} s k = 0 {\displaystyle s_{k}=0} k > c + d − 2. {\displaystyle k>c+d-2.}
S ( x ) Λ ( x ) = ∑ j = 0 ∞ ∑ i = 0 j s j − i + 1 λ i x j . {\displaystyle S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+1}\lambda _{i}x^{j}.} S ( x ) Λ ( x ) = S ( x ) { λ 0 ∏ ℓ = 1 v ( α i ℓ x − 1 ) } = { ∑ i = 0 d − 2 ∑ j = 1 v e j α ( c + i ) ⋅ i j x i } { λ 0 ∏ ℓ = 1 v ( α i ℓ x − 1 ) } = { ∑ j = 1 v e j α c i j ∑ i = 0 d − 2 ( α i j ) i x i } { λ 0 ∏ ℓ = 1 v ( α i ℓ x − 1 ) } = { ∑ j = 1 v e j α c i j ( x α i j ) d − 1 − 1 x α i j − 1 } { λ 0 ∏ ℓ = 1 v ( α i ℓ x − 1 ) } = λ 0 ∑ j = 1 v e j α c i j ( x α i j ) d − 1 − 1 x α i j − 1 ∏ ℓ = 1 v ( α i ℓ x − 1 ) = λ 0 ∑ j = 1 v e j α c i j ( ( x α i j ) d − 1 − 1 ) ∏ ℓ ∈ { 1 , ⋯ , v } ∖ { j } ( α i ℓ x − 1 ) {\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}}} 未知数を計算したい ので、項を削除することで文脈を簡略化できます 。これにより、誤差評価多項式が得られます。 e j , {\displaystyle e_{j},} ( x α i j ) d − 1 {\displaystyle \left(x\alpha ^{i_{j}}\right)^{d-1}}
Ω ( x ) ≡ S ( x ) Λ ( x ) mod x d − 1 . {\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}.} おかげで 私たちは v ⩽ d − 1 {\displaystyle v\leqslant d-1}
Ω ( x ) = − λ 0 ∑ j = 1 v e j α c i j ∏ ℓ ∈ { 1 , ⋯ , v } ∖ { j } ( α i ℓ x − 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 } x = α − i k {\displaystyle x=\alpha ^{-i_{k}}}
Ω ( α − i k ) = − λ 0 e k α c ⋅ i k ∏ ℓ ∈ { 1 , ⋯ , v } ∖ { k } ( α i ℓ α − i k − 1 ) . {\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).} を得るには 、積を取り除けばいいだけです。既に計算済みの根から直接積を計算することもできます が 、より単純な形式を使うこともできます。 e k {\displaystyle e_{k}} α − i j {\displaystyle \alpha ^{-i_{j}}} Λ , {\displaystyle \Lambda ,}
形式的な派生語 として
Λ ′ ( x ) = λ 0 ∑ j = 1 v α i j ∏ ℓ ∈ { 1 , ⋯ , v } ∖ { j } ( α i ℓ x − 1 ) , {\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つだけとなる
Λ ′ ( α − i k ) = λ 0 α i k ∏ ℓ ∈ { 1 , ⋯ , v } ∖ { k } ( α i ℓ α − i k − 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).} それで最後に
e k = − α i k Ω ( α − i k ) α c ⋅ i k Λ ′ ( α − i k ) . {\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 }
Λ ( x ) = ∑ i = 1 v λ i x i {\displaystyle \Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}} 得られる：
Λ ′ ( x ) = ∑ i = 1 v i ⋅ λ i x i − 1 , {\displaystyle \Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},} どこ
i ⋅ x := ∑ k = 1 i x . {\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}
拡張ユークリッドアルゴリズムに基づく復号法 多項式Λと誤り位置多項式の両方を見つける代替プロセスは、杉山康夫による 拡張ユークリッド互除法 の適応に基づいています。 [10] 判読できない文字の修正も簡単にアルゴリズムに組み込むことができます。
判読不能な文字の位置を とします。これらの位置を局所化する多項式を作成します 。判読不能な位置の値を 0 に設定し、シンドロームを計算します。 k 1 , . . . , k k {\displaystyle k_{1},...,k_{k}} Γ ( x ) = ∏ i = 1 k ( x α k i − 1 ) . {\displaystyle \Gamma (x)=\prod _{i=1}^{k}\left(x\alpha ^{k_{i}}-1\right).}
フォーニーの公式で既に定義したように、 S ( x ) = ∑ i = 0 d − 2 s c + i x i . {\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.}
多項式と の最小公約数を求める拡張ユークリッドの互除法を実行してみましょう。 目標は最小公約数を見つけることではなく、 最大次数の 多項式と の多項式を見つけることです。 の 低次 保証は、 拡張された（ によって ）定義条件を満たすでしょう。 S ( x ) Γ ( x ) {\displaystyle S(x)\Gamma (x)} x d − 1 . {\displaystyle x^{d-1}.} r ( x ) {\displaystyle r(x)} ⌊ ( d + k − 3 ) / 2 ⌋ {\displaystyle \lfloor (d+k-3)/2\rfloor } a ( x ) , b ( x ) {\displaystyle a(x),b(x)} r ( x ) = a ( x ) S ( x ) Γ ( x ) + b ( x ) x d − 1 . {\displaystyle r(x)=a(x)S(x)\Gamma (x)+b(x)x^{d-1}.} r ( x ) {\displaystyle r(x)} a ( x ) {\displaystyle a(x)} Γ {\displaystyle \Gamma } Λ . {\displaystyle \Lambda .}
Fourney の式の の位置に を定義し て使用すると、エラー値が得られます。 Ξ ( x ) = a ( x ) Γ ( x ) {\displaystyle \Xi (x)=a(x)\Gamma (x)} Ξ {\displaystyle \Xi } Λ ( x ) {\displaystyle \Lambda (x)}
このアルゴリズムの主な利点は、 Forney 式に必要な計算を同時に実行できることです。 Ω ( x ) = S ( x ) Ξ ( x ) mod x d − 1 = r ( x ) {\displaystyle \Omega (x)=S(x)\Xi (x){\bmod {x}}^{d-1}=r(x)}
デコードプロセスの説明 目標は、読み取り可能な位置において受信語との差異が可能な限り小さい符号語を見つけることです。受信語を最も近い符号語とエラー語の和として表す場合、読み取り可能な位置における非ゼロの数が最小となるエラー語を見つけようとします。シンドロームは、 エラー語を条件によって制限します
。 s i {\displaystyle s_{i}}
s i = ∑ j = 0 n − 1 e j α i j . {\displaystyle s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.} これらの条件を別々に書くこともできるし、多項式を作成することもできる。
S ( x ) = ∑ i = 0 d − 2 s c + i x i {\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}} べき乗に 近い係数を比較すると 0 {\displaystyle 0} d − 2. {\displaystyle d-2.}
S ( x ) = { 0 , ⋯ , d − 2 } E ( x ) = ∑ i = 0 d − 2 ∑ j = 0 n − 1 e j α i j α c j x i . {\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}.} 位置に判読不能な文字があると仮定し、シンドロームの集合を 次の式で定義される シンドロームの集合に 置き換えることができる。 エラーワードに対して、元の シンドロームの集合によるすべての制約が満たされると仮定すると、 k 1 , {\displaystyle k_{1},} { s c , ⋯ , s c + d − 2 } {\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}} { t c , ⋯ , t c + d − 3 } {\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}} t i = α k 1 s i − s i + 1 . {\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}.} { s c , ⋯ , s c + d − 2 } {\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}
t i = α k 1 s i − s i + 1 = α k 1 ∑ j = 0 n − 1 e j α i j − ∑ j = 0 n − 1 e j α j α i j = ∑ j = 0 n − 1 e j ( α k 1 − α j ) α i j . {\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}.} 新しい症候群のセットはエラーベクトルを制限する
f j = e j ( α k 1 − α j ) {\displaystyle f_{j}=e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)} 元のシンドロームの集合がエラーベクトルを制限したのと同じ方法で。 ただし、エラー 位置 を特定するという目的のために 、 シンドロームの集合を同様の方法で変更し、判読できない文字をすべて反映させることができます。これにより、シンドロームの集合は次のように短縮されます。 e j . {\displaystyle e_{j}.} k 1 , {\displaystyle k_{1},} f k 1 = 0 , {\displaystyle f_{k_{1}}=0,} f j {\displaystyle f_{j}} e j = 0. {\displaystyle e_{j}=0.} k . {\displaystyle k.}
多項式定式化において、シンドローム集合を シンドローム集合 に置き換えると、 { s c , ⋯ , s c + d − 2 } {\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}} { t c , ⋯ , t c + d − 3 } {\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}
T ( x ) = ∑ i = 0 d − 3 t c + i x i = α k 1 ∑ i = 0 d − 3 s c + i x i − ∑ i = 1 d − 2 s c + i x i − 1 . {\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}.} したがって、
x T ( x ) = { 1 , ⋯ , d − 2 } ( x α k 1 − 1 ) S ( x ) . {\displaystyle xT(x){\stackrel {\{1,\cdots ,\,d-2\}}{=}}\left(x\alpha ^{k_{1}}-1\right)S(x).} を で置き換えた後 、べき乗付近の係数についての式が必要となる。 S ( x ) {\displaystyle S(x)} S ( x ) Γ ( x ) {\displaystyle S(x)\Gamma (x)} k , ⋯ , d − 2. {\displaystyle k,\cdots ,d-2.}
判読不能文字の場合と同様に、与えられた位置の影響を排除するという観点からエラー位置を探すことも考えられます。もし、 その影響を排除するとすべてゼロからなるシンドロームの集合が得られるような位置が見つかった場合、それらの座標にのみエラーを持つエラーベクトルが存在することになります。 これらの座標の影響を排除する多項式を とすると、次の式が得られます
。 v {\displaystyle v} Λ ( x ) {\displaystyle \Lambda (x)}
S ( x ) Γ ( x ) Λ ( x ) = { k + v , ⋯ , d − 2 } 0. {\displaystyle S(x)\Gamma (x)\Lambda (x){\stackrel {\{k+v,\cdots ,d-2\}}{=}}0.} ユークリッド互除法では、（読み取り可能な位置において）最大で 個の誤りを訂正しようとします 。これは、誤り数が大きいほど、受信語から同じ距離内により多くの符号語が存在する可能性があるためです。したがって、 我々が求めている に対して、式は から始まるべき乗に近い係数に対して成立する必要があります。 1 2 ( d − 1 − k ) {\displaystyle {\tfrac {1}{2}}(d-1-k)} Λ ( x ) {\displaystyle \Lambda (x)}
k + ⌊ 1 2 ( d − 1 − k ) ⌋ . {\displaystyle k+\left\lfloor {\frac {1}{2}}(d-1-k)\right\rfloor .} Forney の式では、 スカラーを掛けても同じ結果が得られます。 Λ ( x ) {\displaystyle \Lambda (x)}
ユークリッドの互除法では、次数と同じ数の異なる根を持つ よりも高い次数を求める場合があります 。この場合、フォーニーの公式はすべての根の誤りを訂正できますが、そのような多くの誤りを訂正することはリスクを伴う可能性があります（特に受信語に他の制約がない場合）。通常、 より高い次数を得た後、誤りを訂正しないことにします。 根の多重度が高い場合、または根の数が次数より少ない場合、訂正は失敗する可能性があります。フォーニーの公式が送信されたアルファベットの外側に誤りを返すことで、誤りが検出される場合があります。 Λ ( x ) {\displaystyle \Lambda (x)} 1 2 ( d − 1 − k ) {\displaystyle {\tfrac {1}{2}}(d-1-k)} Λ ( x ) {\displaystyle \Lambda (x)} Λ ( x ) {\displaystyle \Lambda (x)}
エラーを修正する エラー値とエラー位置を使用してエラーを修正し、エラー位置のエラー値を減算して修正されたコード ベクトルを形成します。
デコード例
判読不能文字のないバイナリコードのデコード GF(2 4 ) 上の BCH 符号を考えます 。 （これは QR コード で使用されます 。）送信するメッセージを [1 1 0 1 1]、または多項式表記で表すとします。「チェックサム」シンボルは、 を で割って 余りを求める ことで計算され、結果として [ 1 0 0 0 0 1 0 1 0 0 ] または [ 1 0 0 0 0 1 0 1 0 0 ] となります。これらがメッセージに付加されるため、送信されるコードワードは [ 1 1 0 1 1 0 0 0 0 1 0 1 0 0 ] となります。 d = 7 {\displaystyle d=7} g ( x ) = x 10 + x 8 + x 5 + x 4 + x 2 + x + 1 {\displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1} M ( x ) = x 4 + x 3 + x + 1. {\displaystyle M(x)=x^{4}+x^{3}+x+1.} x 10 M ( x ) {\displaystyle x^{10}M(x)} g ( x ) {\displaystyle g(x)} x 9 + x 4 + x 2 {\displaystyle x^{9}+x^{4}+x^{2}}
ここで、伝送中に2つのビットエラーがあったと仮定すると、受信コードワードは[1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]となります。多項式表記では以下のようになります。
R ( x ) = C ( x ) + x 13 + x 5 = x 14 + x 11 + x 10 + x 9 + x 5 + x 4 + x 2 {\displaystyle R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x^{5}+x^{4}+x^{2}} 誤りを修正するには、まずシンドロームを計算します。 とすると 、 となります。次に、次の 拡張行列 を行縮約してピーターソン手順を適用します 。 α = 0010 , {\displaystyle \alpha =0010,} s 1 = R ( α 1 ) = 1011 , {\displaystyle s_{1}=R(\alpha ^{1})=1011,} s 2 = 1001 , {\displaystyle s_{2}=1001,} s 3 = 1011 , {\displaystyle s_{3}=1011,} s 4 = 1101 , {\displaystyle s_{4}=1101,} s 5 = 0001 , {\displaystyle s_{5}=0001,} s 6 = 1001. {\displaystyle s_{6}=1001.}
[ S 3 × 3 | C 3 × 1 ] = [ s 1 s 2 s 3 s 4 s 2 s 3 s 4 s 5 s 3 s 4 s 5 s 6 ] = [ 1011 1001 1011 1101 1001 1011 1101 0001 1011 1101 0001 1001 ] ⇒ [ 0001 0000 1000 0111 0000 0001 1011 0001 0000 0000 0000 0000 ] {\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のみであるため、誤り値を計算する必要はありません。 λ 2 = 1000 , {\displaystyle \lambda _{2}=1000,} λ 1 = 1011. {\displaystyle \lambda _{1}=1011.} Λ ( x ) = 1000 x 2 + 1011 x + 0001 , {\displaystyle \Lambda (x)=1000x^{2}+1011x+0001,} 0100 = α − 13 {\displaystyle 0100=\alpha ^{-13}} 0111 = α − 5 . {\displaystyle 0111=\alpha ^{-5}.} α {\displaystyle \alpha }
判読できない文字でデコードする 同じシナリオを想定しますが、受信したワードに2つの判読不能な文字 [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ] が含まれているとします。判読不能な文字をゼロに置き換え、それらの位置を反映する多項式を作成します。 シンドローム とを計算します（GF(2 4 )同型に依存しない対数表記を使用します 。計算結果の確認には、前の例で使用したのと同じ加算表現を使用できます。 のべき乗の 16 進数表記は、1、2、4、8、3、6、C、B、5、A、7、E、F、D、9 の順で、ビット単位の排他的論理和に基づいて加算されます）。 Γ ( x ) = ( α 8 x − 1 ) ( α 11 x − 1 ) . {\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).} s 1 = α − 7 , s 2 = α 1 , s 3 = α 4 , s 4 = α 2 , s 5 = α 5 , {\displaystyle s_{1}=\alpha ^{-7},s_{2}=\alpha ^{1},s_{3}=\alpha ^{4},s_{4}=\alpha ^{2},s_{5}=\alpha ^{5},} s 6 = α − 7 . {\displaystyle s_{6}=\alpha ^{-7}.} α {\displaystyle \alpha }
シンドローム多項式を作ってみましょう
S ( x ) = α − 7 + α 1 x + α 4 x 2 + α 2 x 3 + α 5 x 4 + α − 7 x 5 , {\displaystyle S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{5}x^{4}+\alpha ^{-7}x^{5},} 計算する
S ( x ) Γ ( x ) = α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 + α 7 x 6 + α − 3 x 7 . {\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}.} 拡張ユークリッドの互除法を実行します。
( S ( x ) Γ ( x ) x 6 ) = ( α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 + α 7 x 6 + α − 3 x 7 x 6 ) = ( α 7 + α − 3 x 1 1 0 ) ( x 6 α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 + 2 α 7 x 6 + 2 α − 3 x 7 ) = ( α 7 + α − 3 x 1 1 0 ) ( α 4 + α − 5 x 1 1 0 ) ( α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 α − 3 + ( α − 7 + α 3 ) x + ( α 3 + α − 1 ) x 2 + ( α − 5 + α − 6 ) x 3 + ( α 3 + α 1 ) x 4 + 2 α − 6 x 5 + 2 x 6 ) = ( ( 1 + α − 4 ) + ( α 1 + α 2 ) x + α 7 x 2 α 7 + α − 3 x α 4 + α − 5 x 1 ) ( α − 7 + α 4 x + α − 1 x 2 + α 6 x 3 + α − 1 x 4 + α 5 x 5 α − 3 + α − 2 x + α 0 x 2 + α − 2 x 3 + α − 6 x 4 ) = ( α − 3 + α 5 x + α 7 x 2 α 7 + α − 3 x α 4 + α − 5 x 1 ) ( α − 5 + α − 4 x 1 1 0 ) ( α − 3 + α − 2 x + α 0 x 2 + α − 2 x 3 + α − 6 x 4 ( α 7 + α − 7 ) + ( 2 α − 7 + α 4 ) x + ( α − 5 + α − 6 + α − 1 ) x 2 + ( α − 7 + α − 4 + α 6 ) x 3 + ( α 4 + α − 6 + α − 1 ) x 4 + 2 α 5 x 5 ) = ( α 7 x + α 5 x 2 + α 3 x 3 α − 3 + α 5 x + α 7 x 2 α 3 + α − 5 x + α 6 x 2 α 4 + α − 5 x ) ( α − 3 + α − 2 x + α 0 x 2 + α − 2 x 3 + α − 6 x 4 α − 4 + α 4 x + α 2 x 2 + α − 5 x 3 ) . {\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次の多項式に到達しており、
( − ( α 4 + α − 5 x ) α − 3 + α 5 x + α 7 x 2 α 3 + α − 5 x + α 6 x 2 − ( α 7 x + α 5 x 2 + α 3 x 3 ) ) ( α 7 x + α 5 x 2 + α 3 x 3 α − 3 + α 5 x + α 7 x 2 α 3 + α − 5 x + α 6 x 2 α 4 + α − 5 x ) = ( 1 0 0 1 ) , {\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}},} 私たちは得る
( − ( α 4 + α − 5 x ) α − 3 + α 5 x + α 7 x 2 α 3 + α − 5 x + α 6 x 2 − ( α 7 x + α 5 x 2 + α 3 x 3 ) ) ( S ( x ) Γ ( x ) x 6 ) = ( α − 3 + α − 2 x + α 0 x 2 + α − 2 x 3 + α − 6 x 4 α − 4 + α 4 x + α 2 x 2 + α − 5 x 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}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}}.} したがって、
S ( x ) Γ ( x ) ( α 3 + α − 5 x + α 6 x 2 ) − ( α 7 x + α 5 x 2 + α 3 x 3 ) x 6 = α − 4 + α 4 x + α 2 x 2 + α − 5 x 3 . {\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 の根は簡単に見つけることができます)。 Λ ( x ) = α 3 + α − 5 x + α 6 x 2 . {\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}.} λ 0 ≠ 1. {\displaystyle \lambda _{0}\neq 1.} Λ . {\displaystyle \Lambda .} α 2 , {\displaystyle \alpha ^{2},} α 10 {\displaystyle \alpha ^{10}} α 2 {\displaystyle \alpha ^{2}} Λ {\displaystyle \Lambda } ( x − α 2 ) {\displaystyle \left(x-\alpha ^{2}\right)}
させて
Ξ ( x ) = Γ ( x ) Λ ( x ) = α 3 + α 4 x 2 + α 2 x 3 + α − 5 x 4 Ω ( x ) = S ( x ) Ξ ( x ) ≡ α − 4 + α 4 x + α 2 x 2 + α − 5 x 3 mod x 6 {\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}}} 式を使ってエラー値を調べてみましょう
e j = − Ω ( α − i j ) Ξ ′ ( α − i j ) , {\displaystyle e_{j}=-{\frac {\Omega \left(\alpha ^{-i_{j}}\right)}{\Xi '\left(\alpha ^{-i_{j}}\right)}},} 私たち のルーツは どこにあるのでしょうか α − i j {\displaystyle \alpha ^{-i_{j}}} Ξ ( x ) . {\displaystyle \Xi (x).} Ξ ′ ( x ) = α 2 x 2 . {\displaystyle \Xi '(x)=\alpha ^{2}x^{2}.}
e 1 = − Ω ( α 4 ) Ξ ′ ( α 4 ) = α − 4 + α − 7 + α − 5 + α 7 α − 5 = α − 5 α − 5 = 1 e 2 = − Ω ( α 7 ) Ξ ′ ( α 7 ) = α − 4 + α − 4 + α 1 + α 1 α 1 = 0 e 3 = − Ω ( α 10 ) Ξ ′ ( α 10 ) = α − 4 + α − 1 + α 7 + α − 5 α 7 = α 7 α 7 = 1 e 4 = − Ω ( α 2 ) Ξ ′ ( α 2 ) = α − 4 + α 6 + α 6 + α 1 α 6 = α 6 α 6 = 1 {\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}}} 事実、それは 驚くべきことではありません。 e 3 = e 4 = 1 , {\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]であるとします。
再び、判読できない文字をゼロに置き換え、それらの位置を反映する多項式を作成します。 シンドロームを計算し 、 シンドローム多項式を作成します。 Γ ( x ) = ( α 8 x − 1 ) ( α 11 x − 1 ) . {\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).} s 1 = α 4 , s 2 = α − 7 , s 3 = α 1 , s 4 = α 1 , s 5 = α 0 , {\displaystyle s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1},s_{5}=\alpha ^{0},} s 6 = α 2 . {\displaystyle s_{6}=\alpha ^{2}.}
S ( x ) = α 4 + α − 7 x + α 1 x 2 + α 1 x 3 + α 0 x 4 + α 2 x 5 , S ( x ) Γ ( x ) = α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 + α − 1 x 6 + α 6 x 7 . {\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}}} 拡張ユークリッドの互除法を実行してみましょう。
( S ( x ) Γ ( x ) x 6 ) = ( α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 + α − 1 x 6 + α 6 x 7 x 6 ) = ( α − 1 + α 6 x 1 1 0 ) ( x 6 α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 + 2 α − 1 x 6 + 2 α 6 x 7 ) = ( α − 1 + α 6 x 1 1 0 ) ( α 3 + α 1 x 1 1 0 ) ( α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 α 7 + ( α − 5 + α 5 ) x + 2 α − 7 x 2 + 2 α 6 x 3 + 2 α 4 x 4 + 2 α 2 x 5 + 2 x 6 ) = ( ( 1 + α 2 ) + ( α 0 + α − 6 ) x + α 7 x 2 α − 1 + α 6 x α 3 + α 1 x 1 ) ( α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 α 7 + α 0 x ) {\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次の多項式に到達しており、
( − 1 α − 1 + α 6 x α 3 + α 1 x − ( α − 7 + α 7 x + α 7 x 2 ) ) ( α − 7 + α 7 x + α 7 x 2 α − 1 + α 6 x α 3 + α 1 x 1 ) = ( 1 0 0 1 ) , {\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}},} 私たちは得る
( − 1 α − 1 + α 6 x α 3 + α 1 x − ( α − 7 + α 7 x + α 7 x 2 ) ) ( S ( x ) Γ ( x ) x 6 ) = ( α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α − 1 x 5 α 7 + α 0 x ) . {\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}}.} したがって、
S ( x ) Γ ( x ) ( α 3 + α 1 x ) − ( α − 7 + α 7 x + α 7 x 2 ) x 6 = α 7 + α 0 x . {\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.} 心配 しないで ください 。 Λ ( x ) = α 3 + α 1 x . {\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{1}x.} λ 0 ≠ 1. {\displaystyle \lambda _{0}\neq 1.} Λ ( x ) {\displaystyle \Lambda (x)} α 3 − 1 . {\displaystyle \alpha ^{3-1}.}
させて
Ξ ( x ) = Γ ( x ) Λ ( x ) = α 3 + α − 7 x + α − 4 x 2 + α 5 x 3 , Ω ( x ) = S ( x ) Ξ ( x ) ≡ α 7 + α 0 x mod x 6 {\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}}} 多項式の根である 式 を使って誤差値を調べてみましょう e j = − Ω ( α − i j ) / Ξ ′ ( α − i j ) , {\displaystyle e_{j}=-\Omega \left(\alpha ^{-i_{j}}\right)/\Xi '\left(\alpha ^{-i_{j}}\right),} α − i j {\displaystyle \alpha ^{-i_{j}}} Ξ ( x ) . {\displaystyle \Xi (x).}
Ξ ′ ( x ) = α − 7 + α 5 x 2 . {\displaystyle \Xi '(x)=\alpha ^{-7}+\alpha ^{5}x^{2}.} 私たちは
e 1 = − Ω ( α 4 ) Ξ ′ ( α 4 ) = α 7 + α 4 α − 7 + α − 2 = α 3 α 3 = 1 e 2 = − Ω ( α 7 ) Ξ ′ ( α 7 ) = α 7 + α 7 α − 7 + α 4 = 0 e 3 = − Ω ( α 2 ) Ξ ′ ( α 2 ) = α 7 + α 2 α − 7 + α − 6 = α − 3 α − 3 = 1 {\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}}} 驚くべきことではない 事実。 e 3 = 1 {\displaystyle e_{3}=1}
したがって修正されたコードは[1 1 0 1 1 1 0 0 0 0 1 0 1 0 0]です。
引用 ^ リード＆チェン 1999、189ページ ^ ホッケンゲム 1959 ^ ボーズ＆レイ・チャウドゥリ 1960 ^ 「フォボス着陸船コーディングシステム：ソフトウェアと分析」 （PDF） 。 2022年10月9日時点のオリジナルより アーカイブ （PDF） 。 2012年 2月25日 閲覧 。 ^ Marelli, Alessia; Micheloni, Rino (2018). 「ソリッドステートドライブ向けBCHコード」. ソリッドステートドライブ（SSDS）の内側 . Springer Series in Advanced Microelectronics. 第37巻. pp. 369– 406. doi :10.1007/978-981-13-0599-3_11. ISBN 978-981-13-0598-6 . 2023年 9月23日 閲覧 。 ^ Gill nd、3ページ ^ リドル＆ピルツ 1999年、229ページ ^ ゴレンスタイン、ピーターソン、ツィールラー 1960 ^ Gill nd、47ページ ^ 杉山康夫、笠原将夫、平沢重一、滑川俊彦。ゴッパ符号を解読するための鍵方程式を解く方法。情報と制御、27:87–99、1975。
参考文献
一次資料
二次資料 Gill, John (nd), EE387 Notes #7, Handout #28 (PDF) , Stanford University, pp. 42– 45, archived (PDF) from the original on 2022-10-09 , retrieved April 21, 2010 [ リンク切れ ] 2012年度のコースノートが書き直されているようです: http://www.stanford.edu/class/ee387/ 2013年6月5日アーカイブ、 Wayback Machineより ゴレンスタイン、ダニエル ； ピーターソン、W. ウェスリー ；ツィーラー、ニール（1960）「2誤り訂正ボーズ・チャウドゥリ符号は準完全である」『 情報 制御』 3 (3): 291– 294, doi : 10.1016/s0019-9958(60)90877-9 リドル、ルドルフ；ピルツ、ギュンター（1999年）、 応用抽象代数 （第2版）、ジョン・ワイリー Reed, Irving S. ; Chen, Xuemin (1999)、 Error-Control Coding for Data Networks 、ボストン、マサチューセッツ州： Kluwer Academic Publishers 、 ISBN 0-7923-8528-4
さらに読む Blahut, Richard E. (2003)、 「データ伝送のための代数的コード （第2版）」、 ケンブリッジ大学出版局 、 ISBN 0-521-55374-1 ギルバート、WJ; ニコルソン、WK (2004)、 『現代代数学の応用』 （第2版）、ジョン・ワイリー Lin, S.; Costello, D. (2004), Error Control Coding: Fundamentals and Applications , Englewood Cliffs, NJ: Prentice-Hall MacWilliams, FJ; Sloane, NJA (1977), The Theory of Error-Correcting Codes , New York, NY: North-Holland Publishing Company Rudra, Atri, CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications, University at Buffalo, 2012-12-18にアーカイブされたオリジナルからの転載 
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01ae26421a97007762e7db564652697943f6c6dd)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34d562bd03e10536d5a5c4f55c8b831b7dfec00f)
