5・2 2重誤り訂正 BCH符号[1] 誤り ロケータ巡回ハミング符号 を もとに 2重誤り訂正符号 を 作ろう。 例として (15, 11) 巡回ハミング符号 を 用いる。 生成多項式 G(x) は 4次 の 原始多項式 G(x) = x4 + x + 1 ――― (5・30) である。 巡回ハミング符号 で 1重誤り が 訂正できるのは、すべての 1重誤り の 誤りパターン多項式 に 対する シンドローム が 非 0 で 相異なっているからである (4章 4・8節[2]項) 。 符号長 15ビット中 i 番目 の ビット に 誤り が あるならば、誤りパターン多項式 E(x) は E(x) = x i ――― (5・31) であり、このとき シンドローム s は s = Y(α) = W(α) + E(α) = E(α) = α i ――― (5・32) であり、シンドローム s = α i が 計算されたならば、すぐに i 番目 の ビット が 誤っていることがわかる。 NOTE - α , α i は それぞれ 根 です。 α i が 得られたならば、i 番目のビット位置 というのは わずらわしいので、i 番目のビットの位置 を α i 番目 の 位置 と 呼ぶことにする。 (図5・1) 。 0 番目、1 番目、2 番目、… という代わりに、α 0 番目、α 1 番目、α 2 番目、… と呼ぶ。 ビットの位置 は 0 番目 から 14 番目 まで、α i も 4章 の 表 4・7 のように α 0 から α 14 まで あって、すべて異なっているから、一向に差支えない。 このように、α i で表した 誤り位置 を 誤り ロケータ (error locator) という。 2 元符号の場合、誤り訂正 は 誤り ロケータ が わかれば 行えるから、復号器の役割は、シンドローム から 未知の 誤り ロケータ α i を 推定することである。
[2] 2重誤り を 訂正するためにこの符号で α i 番目 と α j 番目 の 2重誤り が 起きたらどうなるだろうか？ (図 5・2) 誤りパターン多項式は E(x) = x i + x j ――― (5.33) である。 このとき得られる シンドローム は s = Y(α) = E(α) = α i + α j ――― (5.34) である。
このままでは、使用できる式が 1個 しかなく、未知数 α i と α j は 確定できない。 2個 の 未知数 を 決めるには、独立な方程式 が 2つ必要である。 未知数 α i と α j を 含み、受信多項式 Y(x) から 計算される 別の シンドローム が 必要である。 巡回ハミング符号 は 根 α を もつようにして、その 根 を 受信多項式 に 代入した s' = Y(α) ――― (5.35) を シンドローム として、併せて使ってみよう。 GF(24) の 0 でない 元 は 0, 1, α, …, α 14 と 16種類ある。 α = 0 と 選ぶと 式(5・35) は 常に 0 となり、誤りの 訂正 ・ 検出 の 役には立たない。 α = 1 とすると s' = Y(1) = E(1) = 0 ――― (5.36) であって、未知数 α i, α j を 含んでいないので、やはり 2重誤りの場所 を 確定することができない。 α = α 2 としたらどうであろうか？ 受信多項式 Y(x) は GF(2) 上の 多項式 であるから、式(5・7) のように Y(x 2) = (Y(x)) 2 ――― (5.37) が成り立つので s' = Y(α 2) = (Y(α)) 2 = s 2 = (α i + α j) 2 = α 2i + α 2j ――― (5.38) となり、s が わかれば s' は 計算でき、誤り ロケータ に関して 新たな情報 を 与えるものではない。
の 関係 が あり、この 連立方程式 を 解くことで 誤り ロケータ が 求められる。 α i , α j が ガロア体 の 元 であり 自由に 加減剰余 を 行ってよいから、このような 連立方程式 が 解けるのである。 得られた 誤り ロケータ に対し、α i 番目 および α j 番目 の ビット を 誤り として 反転 すれば、誤りの 訂正 が 行える。 [3] 2重誤り訂正 BCH符号 の 生成多項式この符号は、α および α 3 を 根 とする 符号 である。 巡回ハミング符号 の 生成多項式 (5・30) は、例2a のように { α, α 2, α 4, α 8 } を 根 にもつ。 さらに、根 α 3 を もたせるために α 3 の 最小多項式 M3(x) を 追加し、M1(x) と M3(x) の 最小公倍多項式 G(x) = LCM ( M1(x), M3(x) ) = M1(x) M3(x) が、この 符号 の 生成多項式 となる。 符号長 は、G(x) で 割り切れる 多項式 x n - 1 における 最小 の n である。 表 5・1 から、ここの M1(x), M3(x) の 位数 は それぞれ 15, 5 である。 求める n は n = LCM (15, 5) = 15 ――― (5・41) であり、符号長 は 15 となる。 また、生成多項式 G(x) の 次数 m = 8 であるから、この 符号 の ここでは、(15, 11) ハミング符号 を もとに 考えてきたが、一般に GF(2m) 上の 原始元 α を 根 にもつ ハミング符号 を もとに、同様にして、α, α 3 を 根 にもつ 符号 として 2重誤り訂正符号 が 導かれ、その 生成多項式 は G(x) = M1(x) M3(x) ――― (5・42) ただし、M1(x), M3(x) は α, α 3 の 最小多項式 であり、符号長 は n = 2m - 1 ――― (5・43) となる。 この 生成多項式 を もつ 符号 が 2重誤り訂正BCH符号 (Boss-Chaudhuri-Hocquenghem code) である。
[4] シンドローム計算回路式(5・39) の シンドローム s1, s3 を 使って、この 符号 は 2重誤り を 訂正する。 シンドローム を 計算する回路 を 考えよう。 4章 の SEC-DED ハミング符号 は 2つの LFSR回路 で 式(5・25) の シンドローム を 計算している。 これと同じように、2つの LFSR回路 を 用意すれば s1 , s3 が 計算できる。 s1 は Y(α) であり、巡回ハミング符号 の シンドローム であるから、図 5・4 (a) の M1(x) = x 4 + x + 1 ――― (5・44) による 割り算回路 でも 計算できる。 別の観点 から 見てみよう。 受信多項式 を Y(x) = y14 x 14 + y13 x 13 + … + y0 ――― (5・45) とする。 Y(x) を M1(x) で 割り算し、余り を S(x) と すれば 次式(5・46) Y(x) = Q(x) M1(x) + S(x) ――― (5・46) M1(x) は 根 α を もつ ことに 注意して、式(5・46) に x = α を 代入しよう。 Y(α) = Q(α) M1(α) + S(α) = S(α) ――― (5・47)
これが シンドローム s1 である。 ところで、Y(x) は 係数 が 0 または 1 , すなわち GF(2) 上 の 多項式 である が、0, 1 は GF(24) の 元 でもある。 多項式 の 係数 の 計算 を GF(24) で 行って、Y(x) を GF(24) 上 の 1次式 ( x - α ) で 割り算し、余り を S1 とする。 Y(x) = Q'(x) ( x - α ) + S1 ――― (5・48) 1次式 で 割り算した から、余り S1 は GF(24) 上 の 定数 である。 この式に x = α を 代入すれば Y(α) = S1 ――― (5・49) となり、これも シンドローム s1 である。 したがって、多項式 Y(x) を ( x - α ) で 割り算し、余り を 求めても シンドローム s1 が 得られる。 多項式 x - α による 割り算回路 として シンドローム s1 の 計算回路を示せば 図 5・4 (b) である。 この回路に Y(x) の 係数 を 高次項 y14 から 順番に入れ、y0 まで 入力し終わった段階で レジスタ に残るのが s1 である。 この回路は、4章 4・2節[1]項 で述べた 割り算回路 と 基本的考え は 全く同一の シフトレジスタ回路 である。 割り算 されるのが GF(24) 上 の 多項式 であるから、以下の点 が 拡張されている。
GF(24) の 元 を 4 ビット の ベクトル で 表すならば、この レジスタ回路 は 4 ビット の 並列データ を 一つの単位 として 取り扱っている GF(24) の 上 の LFSR である。 誤解のないよう、図 の 信号線 は 太い ⇒ で 表してある。 なお、多項式 Y(x) の 係数 の yi は 1 または 0 であるが、この 回路 に入るときは 4 ビット の 並列データ であり、それぞれ α0 = ( 0 0 0 1 ) , 0 = ( 0 0 0 0 ) として 扱われる。 同様に考えれば、シンドローム s3 = Y(α3) は 式(5・47), 式(5・48) で α を α3 で 置き換えればよく、x - α3 による 割り算回路 で 計算 できる。 したがって、用意すべき二つ目の LFSR も GF(24) 上 の LFSR であり、 x - α3 による 割り算回路 として 図 5・5 となる。
NOTE - α3 は 根 です。 [5] 誤り位置 多項式NOTE - α i ： 誤りパターン の ある i 番目 の 根 α j ： 誤りパターン の ある j 番目 の 根 シンドローム s1 , s3 が 計算 されたならば、式(5・39) の 連立方程式 から 誤りロケータ α i, α j を 求める。 この手段として、GF(24) 上 の 次 の 多項式 δ(z) を 考える。 δ(z) = ( 1 - α iz ) ( 1 - α jz ) ――― (5・50) = 1 + δ1 z + δ2 z 2 ――― (5・51) この 多項式 は、誤りロケータ の 逆数 α-i , α-j を 根 にもつ。 この δ(z) のように、誤りロケータ が その 根 から 容易に計算できる 多項式 を 誤り位置多項式 (error locator polynomial) という。 シンドローム s1, s3 から この δ(z) (の 係数 δ1, δ2) が 定まれば、その 根 として 誤りロケータ の 逆数 が 求まり、誤りロケータ が わかる。 式(5・50) を 展開し δ(z) = 1 - ( α i + α j ) z + α i α j z 2 とすれば、式(5・39), (5・51) と 比較し、GF(24) 上 の 計算 であることに 注意して
となる。 このようにして、シンドローム s1 , s3 から 誤り位置多項式 δ(z) を 求めることができる。 この δ(z) は 2次方程式 であるが、実数体 の 方程式 のように 根 の 公式 で 解くわけにはいかない * 。 α-i ( i = 0, 1, 2, …, 14 ) を 順次 δ(z) に 代入し、δ(α-i) が 0 か どうか を 調べることで 誤りロケータ を 求めることになる。 しかし、この方法 は 時間が かかるので、2重誤り訂正符号 では、誤り位置多項式 の 係数 (または シンドローム) と 根 の 関係 を 表 で 用意しておき、この表 を 引くことで 誤りロケータ を 求めて 誤り訂正 を 行うことが多い。 * 根 の 公式 は GF(2m) 上 の 2次方程式 には 適用できない。 GF(2m) に おいては、 2 = 0 であり、2 で 割り算 することが できないからである。 [6] 2重誤り訂正BCH符号 の 復号法2重誤り以外 の 誤り が 生じたとき どうなるか を 考察して、この符号の 復号法 としてまとめよう。 α i 番目 のみの 単一誤り であった場合
であるから、式(5・51) から 誤り位置多項式 は δ(z) = 1 - s1 z + 0 z 2 = 1 - α i z の 1次式 となる。 その 根 は z = α -i の 一つ である。 この場合、誤り位置多項式 の 根 の 数 が 1つ となるだけで、正しい 誤りロケータ が 得られる。 式(5・39) の s1 は、巡回ハミング符号 の シンドローム である。 巡回ハミング符号 は、最小距離 が 3 であるから、3重以上の 誤り に対してのみ s1 = 0 となることがある。 このとき 式(5・52) において、0 で 割り算 することになり、δ2 が 求まらない。 また、誤り位置多項式 δ(z) が 求められても、α 0, …, α -n+1 までの 範囲 に 根 が ない場合もある。 しかし、2重以下 の 誤り に 対しては、このようなことは 起きないので、誤り位置多項式 の 係数 や、その 根 が 求められなかった場合は、3重以上 の 誤り と 考えればよい。 以上をまとめれば、復号法 として 次のようになる。 これを 図 5・6 に示す。
なお、この 復号法 は (15, 7) BCH符号 以外 であっても、根 として GF(2 m) 上 の α と α 3 をもつ 任意 の 符号 に 適用可能である。 例4ここで 考えている 2重誤り訂正BCH符号 で 誤り訂正 の 例 を見よう。 受信語 を y = ( 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 ) ――― (5・55) とする。 受信多項式は Y(x) = x 5 + 1 ――― (5・56) である。 シンドローム は、4章 の 表 4・7 を 見て計算すると
である。 誤り位置多項式 の 係数 は δ(z) = 1 + α 10 z + α 5 z 2 ――― (5・59) に z = α i ( i = 0, 1, …, 14 ) を 順次 代入して 根 を 求めれば、δ(α0) = 0 が まず 求められる。 このまま 代入 を 続けるか、または 求められた 根 α0 を使って δ(z) / ( 1 - α0 z ) = ( 1 - α5 z ) と 計算すれば、誤りロケータ α0 と α5 が 得られる。 y に対し、この 位置 を 訂正すれば、送信語 w は w = ( 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ) ――― (5・60) と推定される。 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
