日記帳だ! with Tux on Libserver

例えば、振込の時口座番号を間違えて打ち込んだと。
照会できる場合は、打ち間違えても大概そんな口座ないよと言ってくれる。
チェックディジットのおかげですね。1文字なら間違えてもそんな口座ないから大丈夫ということ。
とはいえ、照会できなければ気付かないまま振り込んでしまうことになる。
すると振込手数料は無駄になるし、組戻手数料を取られることもある。
しかし多少の間違えなら自動で訂正してくれたら便利ですよね。

---

そんな銀行は聞いたことないが、不可能ってことはないですよ。
数学の力を借りればなんとでも。
こういうのを実現する方法はたくさんあるのですが、
まぁ有名なのはハミング符号ですよね。
調べると4ビットのデータに3ビット加えて7ビットにすれば、
1ビットの誤りを訂正できると。
ただその程度ということです。そんなにすごい能力が高いわけでもない。
メモリのデータの検査に使われていますよ。
64ビットを単位にして、8ビット加えて、1ビットの誤りを訂正できる。
こういうのをECC対応メモリ言うんだけどね。まぁPCでは使われないですね。サーバー向けね。
ただこれがさっきの目的を達成するのに向いてるわけはないわな。
人間が間違えるんだから1ビット単位で間違えるわけじゃないよね。
文字単位で間違えますからねー、これはダメです。
じゃあと発見したのが、リード・ソロモン符号というやつ。RS符号と略するらしい。
これは2^rのシンボルを単位としてやるのだが、
シンボルの中でどう間違えようと1つの間違えとしかカウントされない。
なので何文字か打ち間違えても補正がきくという仕組みにはもってこい。
けど難しすぎる…リード・ソロモン符号 (Wikipedia)見ても難しすぎ。

---

まぁしかしいろいろ調べてるとわかることもある。
RS符号は8桁のデータに、2桁の符号を加えるとかいう風にして作ると。
これで加えるのが2桁なら1文字、4桁なら2文字の補正がきく。
それを超えると補正失敗するか間違いを増やす補正をやるかどっちか。
それで桁数制限がありまして、2^r個のシンボルを使うなら、合計2^r桁までしか無理。
初め、10進数の範囲で入力できるように0～7の2³個のシンボルを使おうと思ったのだが、
すると7桁までしか無理だと。2^r桁未満ということ。
1桁補正するためには2桁は訂正用に使うから、データは5桁までしかいけない。
しかも8進数の5桁だから、たった32768個にしか対応できない。
これでも実用的かもしれないけど、なんというか。
というわけで今回は0～9、A～XのうちIとOを除いた32文字を使って、
6桁のデータに2桁付加することにしよう。
これならおよそ10.7億個分も用意できる。
無尽蔵とは言えないけど、31桁までは増やせるんだからね。

---

さて、その前にRS符号では有限体とかいうやつを使うらしい。
フェルマーの最終定理の証明にも使われた代物だとか。
0～31の範囲で加減乗除しても0～31の範囲に戻ってくるものということらしい。
この有限体の世界でいろいろやるらしい。意味不明ですね。
足し算は排他的論理和を使えばいいらしい。引き算も排他的論理和だと。
だからこの世界では31+7は24だということ。
CとかPerlでは排他的論理和は^の演算子を使うから、31^7=24と書けばよいか。
しかし^という記号はべき乗を思い浮かべるからどうも…
かけ算だが、αⁿで1～31までの値を表せるようにして、指数法則で計算しろと。
αというのはなんかわからんけどこの世界のべき乗で1～31の数字を用意できるものということ。
それで、どうもこれを作れるのが素数個のときと、素数のべき乗個のときらしい。
なので10進数でRS符号は作れないと。11進数とか9進数ならできるみたいだけど。
これなんだが、さっき書いたWikipediaの記事にいろいろ書いてあるが、
まずα⁰=1、α¹=2、α²=4、α³=8、α⁴=16と。
ここまではそういうものらしい。ここからが問題。
ここで原始多項式という魔法のような式を使ってやる。
それ以下の次数の式では割り切れない式というやつで、その性質があればいいらしい。
擬似ランダムパターン発生回路のページの下の方に載ってますね。
まぁこれの5次の式を持ってくる。x⁵+x²+1って式ですね。
これを変形して、+をこの世界の足し算である^に置き換えて、xにαを代入して…
α⁵=α² ^ 1 = 5
これ以上だが、これを両辺α倍して…とやっていくので…
α⁵⁺ⁿ=α²⁺ⁿ ^ αⁿ
の式のnを増やしながら計算すればいいんじゃないかな。これでα⁰からα³⁰の値をGET!
ちなみにα³¹=α⁰=0です。まぁ一周回ってくるということ。
しかし手作業でやるのもめんどくさいので、$a[$n]がα^$nの値になる@aをPerlで作ってみた。

@a=(1,2,4,8,16);
$a[5+$_]=$a[2+$_]^$a[$_] for(0..30-5);

結果なんだが、
@a=(1,2,4,8,16 , 5,10,20,13,26 , 17,7,14,28,29 , 31,27,19,3,6 , 12,24,21,15,30 , 25,23,11,22,9 , 18)
となる。これを使えばこの世界のかけ算・わり算ができる。
10×7は、10がα⁶、7がα¹¹なので、指数法則で答えはα¹⁷=19と。
わり算も10÷7=α^-5=α²⁶=23となるわけ。
実はここまでたどり着くのが一番大変だった。

---

Perlで符号化と復号化するから使う計算を用意するね。
$xを@aの中の何番目か探すのは実はlog_α($x)なのでloga関数として用意。

sub loga{
  for(0..$#a){
    return $_ if($a[$_]==$_[0]);
  }
  return undef;
}

当てはまらなければundefを返す。0はないからundefが返ってくる。
α^$nを$a[$n]と書くのはかっこわるい気がしたからapow関数として用意。

sub apow{
  return $a[ $_[0] % 31 ];
}

31で割ったあまりを取るのがポイントです。apow(-5)とすれば$a[26]を取ってくれるんですね。
これを使えばかけ算・わり算・べき乗も簡単ですね。

sub mul{
  my $p=0;
  for(@_){
    my $c=loga($_);
    return 0 if(!defined $c);
    $p+=$c;
  }
  return apow($p);
}

かけ算のポイントだが、0だとloga(0)はundefが返ってくる。undefが返ってきたらその瞬間0が答えになると言うこと。
0に何をかけても0なのはこの世界でも変わりません。
mul(2,3,4)とすれば2×3×4ということね。まぁあんまり意味はないけど。

sub div{
  my $p=loga($_[0]);
  return 0 if(!defined $p);
  my $c=loga($_[1]);
  return undef if(!defined $c);
  $p-=$c;
  return apow($p);
}

分子に0が来たらundefを返すようにしてる。分母が0なら0なのは当然ですね。

sub pow{
  return apow(loga($_[0])*$_[1]);
}

これはそのままですね。こんな風にlogを使って計算する世界だということです。
この世界での計算はこれと排他的論理和だけあれば十分です。

---

これでやっと符号化に入れる。@aを作って、計算を定義して、やっとですね。
@i=(1,2,3,4,5,6)を符号化します。
で符号化の理屈ですが、2桁加えるときは、
G(x)=(x ^ α⁰)(x ^ α¹)
というxの式を用意します。2桁だから2つの項ね。4つならαの指数を増やして用意するだけ。
Perlでスクリプト書いて展開させてもよいが…めんどくさいから手でやろう。
G(x)=x² ^ (α⁰ ^ α¹)x ^ α¹
分配法則使って展開すればいいのね。
で、整理すると x² ^ 3x ^ 2となる。@g=(1,3,2)として格納しておこう。
参考までにスクリプト@gを自動生成するスクリプト。

@g=(1);
for my $i(0..2-1){
  my $a=$a[$i];
  unshift @g,0;
  $g[$_]=($g[$_+1]//0)^mul($g[$_],$a) for(0..$#g);
}

筆算してるみたいなもんですよ。4桁とかなるとこれないと大変ですので。
この式を生成多項式というらしい。これは32個のシンボルを使って、2桁付加するときは共通。
さっきの@iに付加する2桁を加えて、こんな多項式を作る。
C(x)=1x⁶ ^ 2x⁷ ^ 3x⁵ ^ 4x⁴ ^ 5x³ ^ 6x² ^ Px ^ Qというxの式で表したもの。
これをG(x)で割り切れるようにすればよいと。結局の所、
1x⁶ ^ 2x⁷ ^ 3x⁵ ^ 4x⁴ ^ 5x³ ^ 6x²をG(x)で割ったあまりがPx ^ Qになると。
めんどくさいですねー。一体誰がこんなのを考えたんだ。
とりあえずさっきの式を@p=(1,2,3,4,5,6,0,0)と表して、@gで表してG(x)で割りましょうか。

while(@p>=@g){
  my $r=div(@p[$#p] , $g[0]);
  $p[$_] ^= mul($g[$_],$r) for(1..$#g);
  shift @p;
}

多項式のわり算ってのは、わる式よりも次数が余りの次数が低くなるまでやるもんだ。
例えば、(2x+2)÷(x+2)は商が2で、余りが-4、これは2x+2=2(x+2)-2で式が表されると言うこと。
それでこの処理で残った@pが余りと。(13,10)が残る。
というわけでさっきの式のPには13が、Qには10が当てはまる。
これで完成。
あとは初めに書いた32進数の文字に当てはめると。
1,2,3,4,5,6は数字そのまま、10はA、13はDですね。
文字リストを@cに入れて、$c[$n]とやって取り出すと便利ですよね。
というわけで結果は123456DAとなると。これで1文字間違えても訂正できるデータできあがり。

---

作るだけでこんなにめんどくさいのに、訂正なんてもっとめんどくさい。
受け取った方は、これを多項式にする。
C(x)=1x⁶ ^ 2x⁷ ^ 3x⁵ ^ 4x⁴ ^ 5x³ ^ 6x² ^ 10x ^ 13
それでシンドロームというものを求める。
2個文字を加えたなら2個のシンドロームができて、
それはS₁=C(α⁰)、S₁=C(α¹)、なんと代入するんですね。
まぁめんどくさいわ。さっきの多項式は@rに(1,2,3,4,5,6,10,13)と格納することにしよう。

@s=();
for my $n(0..2-1){
  my $s=0;
  for(0..$#r){
    $s^=mul($r[$_],pow($a[$n] , $#r-$_ ));
  }
  push @s,$s;
}

これでシンドロームの配列@sが作れた。結果だが(0,0)となる。
実は成功していれば全部の値が0になる。なぜならばC(x)はG(x)で割り切れて、
G(x)は式の形をみてもわかるように、xにα⁰ と α¹を入れたら0になる。
だからC(x)にそれを入れても0となると。ならなければ間違えです。
それで訂正方法だが、Wikipediaの記事を見るとけったいな行列式が書いてある。
けど1文字しか訂正しないならいろんな式が簡単になって、
1 ^ (S₁S₂)αⁿ=0を満たすnを発見すればよいと。
変形して、αⁿ=S₁/S₂、
対数を取って、n=log_α(S₁)-log_α(S₂)、
$n=loga($s[0])-loga($a[2]) となるわけですね。
そして、x^31-$nの項を修正する。(-$n)%31を取るといいと思います。
修正方法はS₁の値を足す、だから排他的論理和を取るだけ。
例、@r=(1,2,3,4,5,6,10,13)を@r=(1,2,3,0,5,6,10,13)と入力されてしまった。
すると@s=(4,10)となる。これより$nを計算すると-4となる。
だからx⁴の項、だから$r[$#r-4]の項ですね。
現在の値は0だけど、これを$r[$#r-4] ^= $s[0]と修正する。
すれば@r=(1,2,3,4,5,6,10,13)に訂正できた。めでたしめでたし。

---

と、わけのわからない計算ばっかりしてきましたが、
これをPerlで作っていろいろやってみるとなかなか楽しいです。
ちょっと打ち間違えてみても、直ってしまうんですね。
これで2個訂正可能にしたいんですが、訂正の式が難しすぎるので…
まぁいろいろ試してみようかなと思います。
うっかりミスを修復できれば何かと便利だよなーとは思いますけどね。
しかしえらいものがあるもんだ。こんなにすごいものが世の中にあったとは。
難解だし、計算しにくいけど、すごい強力だな。

---

Author : Hidemaro
Date : 2009/01/11(Sun) 22:31
電気・数学・物理 | Comment | trackback (0)

blog comments powered by Disqus

トラックバック

トラックバックURL取得