前回は 2 個エラーがあるとした場合の誤り位置の検出方法と訂正方法を解説しましたが、最初の方でエラー訂正能力の話をしたときに n 個パリティデータを付けた場合、位置が分かっていれば n 個の訂正ができるといいました。今回はその方法を簡単に紹介したいと思います。
取り上げている例では、4 個のパリティを付けているので 4 個までは訂正できるはずです。
桁 h, i, j, k に e1、e2、e3、e4 が発生していたとすると、
S0 = e1 + e2 + e3 + e4
S1 = e1･α^h + e2･α^i + e3･α^j + e4･α^k
S2 = e1･α^(2h) + e2･α^(2i) + e3･α^(2j) + e4･α^(2k)
S3 = e1･α^(3h) + e2･α^(3i) + e3･α^(3j) + e4･α^(3k)
となっていますので、h, i, j, k が別の手段で分かっていれば求める数値の数だけ独立の連立方程式があるわけですから、これを解けば解決です。え、2 つや 3 つならともかくこれ以上のものだってあるのだから無理ぽ？そう実際には無理ですね。強力な計算機があれば出来るかも知れません。
ここでは Forney アルゴリズムによって得られた計算式を紹介することにします。Forney アルゴリズム自体を解説しようとするともはや本の写しになってしまいますので、私が参考にしている書籍を紹介するにとどめておきます。何か分かりやすい解釈が出来たら解説したいと思います。
参考書はこれです。
ディジタル・エラー訂正技術入門―無線データ通信における (ディジタル信号処理シリーズ)
で、工学者にとっては使えることが大事ですので、どういう公式で解を求めれば良いかが分かれば良いのです。それは以下の式になります。
※ 12/31 式が間違っていましたので差し替えました。
一般式はこれになります。m は誤りデータのグループのそれぞれの要素を表す添え字です。最大でパリティ桁数 n です。
一つ一つ解説していきます。
まず、分子の E(X) ですがこれは今まで出てきたエラー多項式とは違って、エラー評価多項式です。書籍を参照して解説する場合、どの本に合わせるのが良いのか迷ってしまい、混乱させてしまうのですが、これ以降は E(X) はエラー評価多項式とします。
これはこの式で表します。
E(X) = mod(S(X)･L(X), X^(n))
ここで、S(X) はシンドローム多項式、L(X) は誤り位置多項式です。これらは今までと同じです。なお以下の解説は誤り数が n 以下ならいくつでも成立するので、今回の例では 4 ではなくても 2, 3 でも使えます。ただ 2 の場合は前回の方法の方が簡単です。
この計算は一旦 S(X)･L(X) を計算した後、シンドロームの桁数だけ使うという意味です。
今回の例では、誤り位置がすでに分かっているので、S(X) も L(X) も既知と云うことになります。と、前の記事を確認していたら S(X) をちゃんと解説していなかったようです。おまけに「特に多項式表現はしません」などとも書いてあります。これは訂正です。
受信したデータ多項式を生成多項式 G(X) のそれぞれの因数で割って得られたそれぞれの剰余を多項式化したものが、シンドローム多項式になります。
前の例で示すと、
S(X) = S3･X^3 + S2･X^2 + S1･X + S0
という要領です。
一般式はこうです。
L(X) は今回はすでに誤り位置が分かっているのでこのような形式になります。
L(X) = (1 + X･P1) (1 + X･P2) (1 + X･P3) (1 + X･P4)
= 1 + L1･X + L2･X^2 + L3･X^3 + L4･X^4
これで E(X) を計算することが出来ます。
分母の積ですが、添え字 k を 1 から順番に代入していく際に求めるエラーの位置順の値だけ除いて積を作る、という意味です。
今まで使ってきたデータ列を使って計算してみます。カッコ内はα表現でのべき乗を表します。
送信データ列
T(X) = 3Ch, 15h, 74h, BCh, 1Fh, 2Dh, 30h, 5Fh, BFh, 03h（77,141,10,71,113,18,29,64,162,25)
エラーデータ列（以前は E(X) でしたが、今回はエラー評価多項式と区別するため D(X) とします）
D(X) = 00h, 00h, 4Ah, 8Ch, 00h, 00h, 13h, 00h, 34h, 00h（-,-,37,49,-,-,14,-,106,-）
受信データ列
R(X) = 3Ch, 15h, 5Eh, 30h, 1Fh, 2Dh, 23h, 5Fh, 8Bh, 03h（77,141,114,29,113,18,47,64,237,25）
シンドロームを計算します。計算過程は省略します。
S(X) = 9Fh, 01h, BEh, E1h (90,0,65,89)
ここで何かの手段によって、エラー位置がレポートされたとします。
D(X) を見ると分かるように、右から見て 2 番目（n = 1）、4 番目（n = 3）、7 番目（n = 6）、8 番目（n = 7）と云うことが分かっています。
この場合は、次のようになります。（α＾n をαn と表記します）
P0 = α1
P1 = α3
P2 = α6
P3 = α7
よって L(X) は以下のようになります。
L(X) = (1 + X･P0)(1 + X･P1)(1 + X･P2)(1 + X･P3)
= (1 + X･α1)(1 + X･α3)(1 + X･α6)(1 + X･α7)
= 1 + X･α73 + X^2･α102 + X^3･α216 + X^4･α17
S(X) = α89 + X･α65 + X^2･α0 + X^3･α90
ですから、E(X) = L(X) x S(X) より
E(X) = mod(α89 + X･α0 + X^2･α66 + X^3･α186 + X^4･α141 + X^5･α153 + X^6･α153 + X^4･α107, X^4)
= α89 + X･α0 + X^2･α66 + X^3･α186
手計算でやるとかなり大変です。私はエクセルで適当なマクロを組んでいますので後ほど紹介したいと思います。また、C 言語などの方が直接 Xor を計算したり出来るので良いのではないかと思います。
続いて分子から計算します。
X = 1/α1 とおいて
E(1 / P0) = α89 + α0/α1 + α66/α1^2 + α186/α1^3 = α230
X = 1/α3 とおいて
E(1 / P1) = α89 + α0/α3 + α66/α3^2 + α186/α3^3 = α130
X = 1/α6 とおいて
E(1 / P2) = α89 + α0/α6 + α66/α6^2 + α186/α6^3 = α172
X = 1/α7 とおいて
E(1 / P3) = α89 + α0/α7 + α66/α7^2 + α186/α7^3 = α87
分母はそれぞれについてこういう計算になります。
X = 1/α1 とおいて
分母 = (1 + P1 / P0) (1 + P2 / P0) (1 + P3 / P0)
= (1 + α3 /α1) (1 + α6 / α1) (1 + α7 / α1)
= α124
X = 1/α3 とおいて
分母 = (1 + P0 / P1) (1 + P2 / P1) (1 + P3 / P1)
= (1 + α1 /α3) (1 + α6 / α3) (1 + α7 / α3)
= α116
X = 1/α6 とおいて
分母 = (1 + P0 / P2) (1 + P1 / P2) (1 + P3 / P2)
= (1 + α1 /α6) (1 + α3 / α6) (1 + α7 / α6)
= α123
X = 1/α7 とおいて
分母 = (1 + P0 / P3) (1 + P1 / P3) (1 + P2 / P3)
= (1 + α1 /α7) (1 + α3 / α7) (1 + α6 / α7)
= α50
よって、エラー補正値は、
D0 = α230 / α124 = α106 = 34h エラー桁：右から 2 番目
D1 = α130 / α116 = α14 = 13h エラー桁：右から 4 番目
D2 = α172 / α123 = α49 = 8Ch エラー桁：右から 7 番目
D3 = α87 / α50 = α37 = 4Ah エラー桁：右から 8 番目
添え字の前後がひっくり返ってしまいましたが、エラー発生桁に対する補正値が求まりこれを使ってエラー訂正をすることができます。
とにかく計算が大変です。といってもプログラムで組んだりハードウェアで組んでおけばさほどでもないと思います。
次回以降はその辺りに触れてみようと思います。
取り上げている例では、4 個のパリティを付けているので 4 個までは訂正できるはずです。
桁 h, i, j, k に e1、e2、e3、e4 が発生していたとすると、
S0 = e1 + e2 + e3 + e4
S1 = e1･α^h + e2･α^i + e3･α^j + e4･α^k
S2 = e1･α^(2h) + e2･α^(2i) + e3･α^(2j) + e4･α^(2k)
S3 = e1･α^(3h) + e2･α^(3i) + e3･α^(3j) + e4･α^(3k)
となっていますので、h, i, j, k が別の手段で分かっていれば求める数値の数だけ独立の連立方程式があるわけですから、これを解けば解決です。え、2 つや 3 つならともかくこれ以上のものだってあるのだから無理ぽ？そう実際には無理ですね。強力な計算機があれば出来るかも知れません。
ここでは Forney アルゴリズムによって得られた計算式を紹介することにします。Forney アルゴリズム自体を解説しようとするともはや本の写しになってしまいますので、私が参考にしている書籍を紹介するにとどめておきます。何か分かりやすい解釈が出来たら解説したいと思います。
参考書はこれです。
ディジタル・エラー訂正技術入門―無線データ通信における (ディジタル信号処理シリーズ)
で、工学者にとっては使えることが大事ですので、どういう公式で解を求めれば良いかが分かれば良いのです。それは以下の式になります。
※ 12/31 式が間違っていましたので差し替えました。
一般式はこれになります。m は誤りデータのグループのそれぞれの要素を表す添え字です。最大でパリティ桁数 n です。
一つ一つ解説していきます。
まず、分子の E(X) ですがこれは今まで出てきたエラー多項式とは違って、エラー評価多項式です。書籍を参照して解説する場合、どの本に合わせるのが良いのか迷ってしまい、混乱させてしまうのですが、これ以降は E(X) はエラー評価多項式とします。
これはこの式で表します。
E(X) = mod(S(X)･L(X), X^(n))
ここで、S(X) はシンドローム多項式、L(X) は誤り位置多項式です。これらは今までと同じです。なお以下の解説は誤り数が n 以下ならいくつでも成立するので、今回の例では 4 ではなくても 2, 3 でも使えます。ただ 2 の場合は前回の方法の方が簡単です。
この計算は一旦 S(X)･L(X) を計算した後、シンドロームの桁数だけ使うという意味です。
今回の例では、誤り位置がすでに分かっているので、S(X) も L(X) も既知と云うことになります。と、前の記事を確認していたら S(X) をちゃんと解説していなかったようです。おまけに「特に多項式表現はしません」などとも書いてあります。これは訂正です。
受信したデータ多項式を生成多項式 G(X) のそれぞれの因数で割って得られたそれぞれの剰余を多項式化したものが、シンドローム多項式になります。
前の例で示すと、
S(X) = S3･X^3 + S2･X^2 + S1･X + S0
という要領です。
一般式はこうです。
L(X) は今回はすでに誤り位置が分かっているのでこのような形式になります。
L(X) = (1 + X･P1) (1 + X･P2) (1 + X･P3) (1 + X･P4)
= 1 + L1･X + L2･X^2 + L3･X^3 + L4･X^4
これで E(X) を計算することが出来ます。
分母の積ですが、添え字 k を 1 から順番に代入していく際に求めるエラーの位置順の値だけ除いて積を作る、という意味です。
今まで使ってきたデータ列を使って計算してみます。カッコ内はα表現でのべき乗を表します。
送信データ列
T(X) = 3Ch, 15h, 74h, BCh, 1Fh, 2Dh, 30h, 5Fh, BFh, 03h（77,141,10,71,113,18,29,64,162,25)
エラーデータ列（以前は E(X) でしたが、今回はエラー評価多項式と区別するため D(X) とします）
D(X) = 00h, 00h, 4Ah, 8Ch, 00h, 00h, 13h, 00h, 34h, 00h（-,-,37,49,-,-,14,-,106,-）
受信データ列
R(X) = 3Ch, 15h, 5Eh, 30h, 1Fh, 2Dh, 23h, 5Fh, 8Bh, 03h（77,141,114,29,113,18,47,64,237,25）
シンドロームを計算します。計算過程は省略します。
S(X) = 9Fh, 01h, BEh, E1h (90,0,65,89)
ここで何かの手段によって、エラー位置がレポートされたとします。
D(X) を見ると分かるように、右から見て 2 番目（n = 1）、4 番目（n = 3）、7 番目（n = 6）、8 番目（n = 7）と云うことが分かっています。
この場合は、次のようになります。（α＾n をαn と表記します）
P0 = α1
P1 = α3
P2 = α6
P3 = α7
よって L(X) は以下のようになります。
L(X) = (1 + X･P0)(1 + X･P1)(1 + X･P2)(1 + X･P3)
= (1 + X･α1)(1 + X･α3)(1 + X･α6)(1 + X･α7)
= 1 + X･α73 + X^2･α102 + X^3･α216 + X^4･α17
S(X) = α89 + X･α65 + X^2･α0 + X^3･α90
ですから、E(X) = L(X) x S(X) より
E(X) = mod(α89 + X･α0 + X^2･α66 + X^3･α186 + X^4･α141 + X^5･α153 + X^6･α153 + X^4･α107, X^4)
= α89 + X･α0 + X^2･α66 + X^3･α186
手計算でやるとかなり大変です。私はエクセルで適当なマクロを組んでいますので後ほど紹介したいと思います。また、C 言語などの方が直接 Xor を計算したり出来るので良いのではないかと思います。
続いて分子から計算します。
X = 1/α1 とおいて
E(1 / P0) = α89 + α0/α1 + α66/α1^2 + α186/α1^3 = α230
X = 1/α3 とおいて
E(1 / P1) = α89 + α0/α3 + α66/α3^2 + α186/α3^3 = α130
X = 1/α6 とおいて
E(1 / P2) = α89 + α0/α6 + α66/α6^2 + α186/α6^3 = α172
X = 1/α7 とおいて
E(1 / P3) = α89 + α0/α7 + α66/α7^2 + α186/α7^3 = α87
分母はそれぞれについてこういう計算になります。
X = 1/α1 とおいて
分母 = (1 + P1 / P0) (1 + P2 / P0) (1 + P3 / P0)
= (1 + α3 /α1) (1 + α6 / α1) (1 + α7 / α1)
= α124
X = 1/α3 とおいて
分母 = (1 + P0 / P1) (1 + P2 / P1) (1 + P3 / P1)
= (1 + α1 /α3) (1 + α6 / α3) (1 + α7 / α3)
= α116
X = 1/α6 とおいて
分母 = (1 + P0 / P2) (1 + P1 / P2) (1 + P3 / P2)
= (1 + α1 /α6) (1 + α3 / α6) (1 + α7 / α6)
= α123
X = 1/α7 とおいて
分母 = (1 + P0 / P3) (1 + P1 / P3) (1 + P2 / P3)
= (1 + α1 /α7) (1 + α3 / α7) (1 + α6 / α7)
= α50
よって、エラー補正値は、
D0 = α230 / α124 = α106 = 34h エラー桁：右から 2 番目
D1 = α130 / α116 = α14 = 13h エラー桁：右から 4 番目
D2 = α172 / α123 = α49 = 8Ch エラー桁：右から 7 番目
D3 = α87 / α50 = α37 = 4Ah エラー桁：右から 8 番目
添え字の前後がひっくり返ってしまいましたが、エラー発生桁に対する補正値が求まりこれを使ってエラー訂正をすることができます。
とにかく計算が大変です。といってもプログラムで組んだりハードウェアで組んでおけばさほどでもないと思います。
次回以降はその辺りに触れてみようと思います。