あるエンジニアの回想録

ブログ始めました!ネタとしては自分がもともと専門であった電気工学系が中心です。時々時事ネタもいれます。

全体表示

[ リスト ]

前々回は 1 個のエラーを訂正する方法を解説し、前回は複数個のエラーがある場合のシンドロームが表すものを解説しました。で、複数個ある場合は連立方程式を解けば良いということなのですが、非線形連立方程式なので簡単に解くことはできない、まずは誤り位置を求めてそれから誤り量を計算するということでした。
誤り位置を求めるには誤り位置多項式という線型連立方程式らしきものを作って解きます。とはいっても誤り数が多くなると大変なことになります。その辺りを例を見ながらつかんでいこうと思います。

ピーターソン方式では誤り位置多項式をこんな風に定義します。

イメージ 1

これの意味は、X = 1 / P1, X = 1 / P2 ・・・ X = 1 / Pn のいずれでも L(X) = 0 となります。以下、かなり面倒な計算になりますが、

イメージ 2

という形に帰着します。でも添え字の関係が今一つわかりにくいですね。ピーターソン方式はあらかじめ受信データ多項式の中のいくつが誤っているかを想定して、行列を作って連立方程式にして解くという方法ですが、いくつ誤っているかなど分かるわけがありません。その辺りは色々方法があるようですが、ここでは仮に 1 個だったら、2 個だったらと増やしながらやってみます。

これを想定したエラー数における組み合わせ可能な n, j について展開します。

1個のエラーを想定した場合、
イメージ 3

2個のエラーを想定した場合、
イメージ 4

行列での表現はこうです。
イメージ 5
ここで、
イメージ 6
ならば(=0の時はエラーが1個)、この連立方程式は解くことが 出来て、
イメージ 7

となります。
ちなみにパリティデータが6個以上ある場合は、シンドロームもその数だけあるので誤り位置多項式で3個のエラーまで位置を探すことが出来て、
イメージ 8

となります。
一般式は省略します。

こうして得た誤り位置多項式ですが、多項式形式になっているのでこのままではすぐには解けません。で、この多項式は最初に挙げた因数分解された表現に戻さなくてはいけないのですが、代数的に解くことは無理ゲーです。そこでガロア体の取り得る値は有限という性質を利用して、片っ端から数値を入れていって当たればラッキーという方法を使います。あ、いやいやもう少しましな方法です。
早い話が多項式の X に数値を入れていって成立するかどうかを確かめていけば良いのですが、実はこの値自体がすでにさらに制限された値になっています。つまし誤り位置というのは受信データの桁の数しかありません。前の例では 10 桁のしかありませんから 10 の値について調べれば良いのです。DVD フォーマットでは横方向(PI)は 192、縦方向(PO)は 208 なのでかなり増えてしまいますが順番に入れていけばその内当たります。
最初は 1 として次はいくつなんだ?ということですが素直に X = α^(-1) です。なぜ逆数かというと最初の因数分解された式を見て下さい。X と P1 の積が 1 になればカッコ内はゼロになって多項式の解と云うことになるからです。

実際にやる場合は今回のケースでは誤り位置多項式は、このような形になりますから、
イメージ 17

最初は X と X^2 と X^3 に 1 を入れます。それがゼロならば最後の項に誤りがあります。続いて X と X^2 と X^3 について、α^(-1)、α^(-2)、α^(-3) をそれぞれ代入しゼロになるか計算し、ならなければ α^(-2)、α^(-4)、α^(-6) を代入それもダメなら α^(-3)、α^(-6)、α^(-9) という要領で α^(-9)、α^(-18)、α^(-27) まで計算します。2 個誤りを想定していますから、どこか 2 カ所がゼロになったはずです。
ちなみに α^(-1) というのは α^254 のことです。


では、前に使ったデータ列を元に計算してみます。


元データはこれでした。(カッコ内はα表示、ゼロは - とします)

T(X) = 3Ch, 15h, 74h, BCh, 1Fh, 2Dh, 30h, 5Fh, BFh, 03h
(77,141,10,71,113,18,29,64,162,25)


こでに二つのエラーが発生したとします。エラーデータ列はこれです。

E(X) = 00h, 00h, 00h, 8Ch, 00h, 00h, 00h, 00h, 34h, 00h
(-,-,-,49,-,-,-,-,106,-)


受信データはこれです。

R(X) = 3Ch, 15h, 74h, 30h, 1Fh, 2Dh, 30h, 5Fh, 8Bh, 03h
(77,141,10,29,113,18,29,64,237,25)


シンドロームを計算します。(以下αべき乗表現)


S(X) = 132, 196, 162, 87(左から、S0、S1、S2、S3)


2 個エラーとして判定式(行列固有値)を計算します。

イメージ 9
ゼロではないので少なくとも 2 個以上です。
ここでは 2 個と決め打ちですのでそれ以上はやりませんが、本来なら 3 x 3 の行列式を計算してゼロになることを確かめなくてはいけません。それを計算するためには実はシンドロームがもう一つ必要で、つまりパリティデータももう一つ必要なのです。今回の例はそういう意味でちょっとまずかったようです。4 個のパリティを付ければ 2 個まで位置を検出して訂正できる、としましたが検証が出来ません。5 個パリティを付けておけば検証まで出来ました。今更なのでこのまま進めます。

L1, L2 はこのようになります。

イメージ 10
イメージ 11
これで誤り位置多項式が出来ました。

これを因数分解するために、X にまず 1 を入れて見てゼロになるかどうか、次に α^(-1) だめなら α^(-2) 続いて α^(-3) と α^(-9) までやるのですが、ここでは 0 番目と 1 番目の計算だけやっておきます。あとは表を見て下さい。イメージ 13

イメージ 14
表はαべき乗表現で書きました。多項式の定数部分は計算せずにそれ以外の項の和が 1 = α^0 になるかどうかで判断します。

ということで、右から見て 2 番目(n = 1)と 7 番目(n = 6)に誤りがあるということが分かりました。

誤り位置多項式は次のように因数分解できたことになります。イメージ 15

で、この場合は多項式の解は α^1 と α^6 です、という表現になります。この表現自体はこういうものだというだけで先には出てきません。

誤り量は次の連立方程式を
解くことになります。
イメージ 12

二元一次なので普通に解くことが出来て、

イメージ 16
というエラー量を得ます。

で、当該受信データを 8Bh + 34h = BFh、30h + 8Ch = BCh と訂正することが出来ます。

今回はエラーが 2 個だけだったので連立方程式でサクッと解いてしまいましたが、一般的にはもう少し工夫が必要です。  

この記事に

閉じる コメント(0)

コメント投稿

顔アイコン

顔アイコン・表示画像の選択

名前パスワードブログ
絵文字
×
  • オリジナル
  • SoftBank1
  • SoftBank2
  • SoftBank3
  • SoftBank4
  • docomo1
  • docomo2
  • au1
  • au2
  • au3
  • au4
投稿

.


みんなの更新記事