誤り訂正符号化とは、データを扱うとき一部に欠損があっても、正しい情報を復元できるようなものです。 ネットワークを通してデータを送信するとき、例えば通信経路上で電圧の変動があったりすると 0と1が正しく送られなかったりします。また、CD-ROMに傷が付いてしまったり、バーコードが折れ曲がっていたり… と、世の中にデータが欠損してしまう例はいくらでもあります。
これを防ぐため、一般に符号化が行われます。たとえば、[0,1,0]というデータを送るのに、各データを三回繰り返して送ることにします。([0,0,0,1,1,1,0,0,0]となります) すると、この中の信号の一つが0から1に誤ってしまっても、正しくデータを復元できます。しかし、元々のデータに比べて伝えるデータは長くなってしまいます。このように、送るべきデータを変換することを符号化といいます。特にデータサイズを減らす符号化は圧縮と呼ばれ、符号化というとエラー訂正用のものを指すことが多いようです。

ここではエラー訂正についての符号化を説明します。 エラー訂正は「虫食い算を解く」のと同じようなものです。例えばxとyが与えられていたとき、

z=(x+y)

を計算しておきます。そうすると、xが失われたら

z=(?+y)

の?を解いて、残ったzとyから(z-y)によってxが求められるし、yが失われたら(z-x)によってxが求められます。
もう少し一般化すると、エラー訂正の対象となるるデータは、有限の長さのビット列です。 エラー訂正の理論では、元のデータ{d0, d1, ... }を関数f(d0, d1, ...)に代入して、エラー訂正データ{c0, c1, ...}を計算します。関数fはとりあえず一次式を考えることにすると、

c0 = a00 * d0 + a01 * d1 + a02 * d2 +...
c1 = a10 * d0 + a11 * d1 + a12 * d2 +...

みたいな計算でc0,c1...を計算します。(a00, a01, a10とかは定数)
もしもいずれかのデータが失われたら、分からないデータを?とおいて「虫食い算」を解けばいいわけです。 (あ、普通は方程式と言いますね)　 元々のc0, c1,...を上のような「定数倍の和」で計算している場合は、連立一次方程式を解くという問題に帰着されます。
例をあげます。d0, d1, d2, d3というデータがあるとき、c0, c1を以下のように計算します。 (d0, d1, d2, d3は普通の整数だと思ってください)

c0 = 1 * d0 + 1 * d1 + 1 * d2 + 1 * d3
c1 = 1 * d0 + 2 * d1 + 3 * d2 + 4 * d3

ここで、

• c0かc1(またはその両方)が失われたら、上の式から再計算
• d0, d1, d2, d3の中で最大二つが失われたら、上式を変数二つの一次方程式と見て解く
• (c0かc1の片方)と(d0,d1,d2,d3のどれか)が同時に失われたら、まず失われたdを上の式から求め、さらにcを再計算

として、データ6個中2個の欠損に対応することができます。
注意しないといけないのはもa00とかの定数をある程度工夫しないと、連立一次方程式が解けなくなってしまう場合が あることです。例えばa00 = a10, a01 = a11 ,...だとc0は常にc1となり、データ二つの欠損に対応できなくなります。 このため、用いる行列としてはある程度制限がかかってきます。 線形台数の理論の方で、a_ijとしては、"Vandermonde行列"を用いると常に方程式が解け、また後の連立一次方程式も 解きやすいことが知られています。 Vandermond行列は以下のようなものです。

1   1   1   1
1   2   3   4
1   4   9  16
1   8  27  32

a_ij = i^jです。なかなか覚えやすい形ですね。

さて、普通に数学的な四則演算で上のコードを作ると、エラー訂正コードの長さが演算によって無駄に長くなってしまう、という問題点があります。
例えば、8ビットのデータa,bを符号化する場合を考えます。例えば次のような演算があったとします。

c = a + b;
d = a * b;

ここでa,bは8ビット、つまり{0 <= a,b < 256}ですが、cはこの範囲に収まらない可能性があります。 例えばa=200, b=100だとc=300、d=20000になりるので、cには9ビット、dには16ビットの符号長が必要になります。もっと複雑な演算を繰り返すと、cやdに割り当てなければいけないビット数はどんどん長くなります。
しかし、このようなビットの使い方は本質的に無駄があります。例えばdは{0 < d < 65535}の範囲になりますが、aもbも255以下の整数なので、d=263 (素数)となることは決してありません。実際、エラー訂正における演算は「後で元のデータをちゃんと回復できる」ことが大事なので、正確に+や*の計算結果を用いる必要はありません。ちゃんと一次方程式が解ければ、+の代わりに(+')みたいなのを用いてもOKです。 この一次方程式が解ける、という条件ですが、これは演算の一意性に関係しています。 例えば、

1 (+') 2 = 3, 1 (+') 5 = 3, 2 ≠ 5

という世界では、

1 (+') ? = 2

という方程式が一意には解けません。(?が2か5か分からない)
つまり、必要なのは

c = a (+') b 

のとき、

c = ? (+') b 

の?を埋める値がただ一つ、確実に定まる(そしてそれは当然aに等しい)というものです。 これは、(-')という演算が成立して

a = c (-') b

となる、というのと同義です。ここで、a(+')bが{0 <= a,b < 256}に収まるようにできれば、先ほどのように無駄に符号長が長くなる問題を回避できます。
積の場合もほぼ同じですが、少し異なるのは0の存在です。

c = a * b 

のとき、

c = ? * b 

を満たす?は、(b!=0)のときは一通りですが、b=0の時は?はなんでもよくて、むしろc==0が必要になります。
また、適当に(+')や(*')の意味を決めてしまうと交換則(a+b=b+a)や結合則((a+b)+c)=(a+(b+c))・分配則( (a+b)*c = a*c+b*c )が成立しなくなってしまうので、普通の一次方程式の解き方が出来なくなってしまいます。このため、最低限この3つの法則は成り立ってほしいと思われます。
では、このような都合が良い(+')や(*')なんて演算はあるのでしょうか。これを与えてくれるのがガロア体上での演算です。

先ほど、a(+')bが{0 <= a,b < 256}に収まってくれればいい、と書きましたが、これは数学の世界では(+')という演算が「閉じている」と表現されます。これは、a, bが属する{0 <= a,b < 256}という集合に対し、a(+')bの結果もこの集合の中に収まっていることを示します。 つまり、求める体系は

• 対象とするのは{0 <= a,b < 256}などの、閉じた整数集合
• この集合に閉じた演算(+')、(*')が定義されている
• (+')と(*')によって構成された一次方程式が解ける

となります。最後のが少し曖昧ですが、このあたり(演算子に求められる条件)を長々書いてもあまり面白くないので、とりあえず進みます。で、とにかくどんな方法でもいいから、これに相当する(+')と(*')の演算を定義すればいいわけです。
このように集合とその中での演算を考えるのを「代数」と言います。演算は適当に決めれば作れるのですが、「方程式が解ける」みたいな条件を課すにはどんな演算でもいいというわけではありません。数学の世界では、ある特定の性質を満たす集合と演算の組に「環」や「体」などの名前を付けています。ここでは「体」について説明します。
「体」とは、以下の性質を満たす集合Fと演算(+,*)のことをいいます。
まずFの任意の元a,b,cと+についての性質です。

• a + b = d のとき、dは必ずFに含まれる
• (a + b) + c = a + (b + c)
• 0(零元)が存在し、0 + a = a + 0 = a　ここで0はFに含まれる
• -a(逆元)が存在し、a + (-a) = (-a) + a = 0　ここで(-a)はFに必ず含まれる

これらの性質をまとめて、F, +が加法群であると言います。 これに加えて、演算の順番を変えてもいい、という

• a + b = b + a

も加えられています。これを加えると「加法可換群」と呼ばれます。

次にFのなかで0を除く任意の元a,b,cと*についての性質です。

• a * b = d のとき、dは必ずFに含まれる
• (a * b) * c = a * (b * c)
• 1(単位元)が存在し、1 * a = a * 1 = a　ここで1はFに含まれる
• a^-1(逆元)が存在し、a * a^-1 = a^-1 * a = 1　ここでa^-1はFに必ず含まれる

これらの性質をまとめて、F, *が乗法群であると言います。 これに加えて、演算の順番を変えてもいい、という

• a * b = b * a

も加えられています。これを加えると「乗法可換群」と呼ばれます。

これに、分配法則

• (a + b) * c = a * c + b * c

を加えて、「体」の定義が完了です。(意外と長かった…)
このようにかなり厳しい定義なので、演算は普通の+や*と同じようにできます。それに加えてうれしいのは、

• a + b = cのとき、cはF(元の集合)に含まれる
• a * b = dのとき、dはF(元の集合)に含まれる

という条件です。Fを(0-255)の整数、という集合として定義しておけば、Fの中の元をどのように四則演算しても、その値は0-255の範囲を超えることはありません。しかも、交換法則・結合法則などが確保されているので、一次方程式は普通の四則演算とまったく同じように解けます。あとはこんなうまい演算+や*が見つかるか、という話になるわけですが…
あ、「体」と「ガロア体」の違いですが、体の集合Fが有限集合(元の数が有限)のとき、これを「有限体」とか「ガロア体」と呼びます。符号理論で扱うのは有限長のデータなので、ガロア体上での演算が役立つわけです。

ガロア体は有限個の元で構成される演算です。この要素に対して上に述べたような条件を満たした演算が定義できればいいわけです。 計算機で扱うときに重要になるのはビット列で表せる要素なので、2^n個(2,4,8,...,256,..)の要素です。

まずはn=2, {0, 1}で構成される演算を考えてみます。 とりあえず空の+の表を書いてみます。

+	0	1
0	?	?
1	?	?

ここで0は+の単位元なので、以下の演算は自動的に埋まります。

+	0	1
0	0	1
1	1	?

1+1はまだ分かりません。ただ、ここでの元は0,1の二つしかないので、 1+1=0又は1+1=1です。
1+1=1とすると、1の加法に関する逆元(-1)を両辺に足して、1+0となってしまいます。そこで、正解の候補になるのは1+1=0の場合のみになります。

+	0	1
0	0	1
1	1	0

この世界では、0,1のいずれにも逆元が存在し、対角線を挟んで折り返し対称なので交換則が成立し、分配則も成立しています。(分配則についてなんですが、一つ一つ確認する以外思いつきません。もっといい方法あるのかなぁ)
同様に積も考えてみます。任意の元aについて0*a=0,1*a=a*a=aより、以下の表が書けます。
(0*a=0は、結合則を用いた0 * a + a * b = (0 + a) * b = a * bより導かれます)

*	0	1
0	0	0
1	0	?

さて、1*1が埋まりません。これもまた1*1=0または1*1=1について考えてみます。1*1=0とすると、1の積に関する逆元が存在しないためまずいので、1*1=1となります。改めて積の表を書くと

*	0	1
0	0	0
1	0	1

となります。
このように、「逆元の一意性」がけっこう効いてきます。

次に、GF(4)を構成してみます。まずは地道に。
決まっているのは元が4つ、ということです。とりあえず{0, 1, p, q}とおきます。 それぞれの元は異なっています。ここでガロア体の性質を満たす+, *を考えます。
とりあえず空の+の表を書いてみます。

+	0	1	p	q
0	0	1	p	q
1	1	?	?	?
p	p	?	?	?
q	q	?	?	?

ここでp+1について考えてみます。この世界で元は四つしかないので、p+1の値も四つのうちどれかです。

• p+1=0
• p+1=1
• p+1=p
• p+1=q

それぞれケチをつけてみます。

• p+1=1とすると、1の逆元(-1)を両辺に足すことでp=0となり不適
• p+1=pとすると、pの逆元(-p)を両辺に足すことで1=0となり不適
• p+1=0とすると、p=-1となる。ここで(1+1)を考えると、この値は0, 1, p, qのどれか。
  • 1+1=0とすると、1の逆元-1が1とpの二つ存在し不適
  • 1+1=1とすると、1=0となり不適
  • 1+1=pとすると、1+1+1=0, p+p=1。ここで1+qを考える。
    • 1+q=0とすると、1の逆元がp,qの二つ存在し、不適
    • 1+q=1とするとq=0となり不適
    • 1+q=pとすると、両辺に1を足しp+q=p+1、q=1となり不適
    • 1+q=qとすると、1=qとなり不適
    よって1+1≠p
  • 1+1=qとすると、両辺にpを足し1=q+p、さらにpを足し(p+p)+q=0。つまりqの逆元はp+p。
    ところで、この世界では全ての元は0, 1, p, qのいずれかである。p+pについて考えると
    • p+p=0とすると、-q=0, q=0となり不適
    • p+p=1とするとqの逆元は1。ここで1はpを逆元に持つから、逆元の一意性に反し不適
    • p+p=pとすると、p=0となり不適
    • p+p=qとすると、-q=q。1+1=qの両辺にqを足し、1+1+q=0, 1+p=0よりp=1+q, p+q=1。 このとき+の表は以下のようになる

      +	0	1	p	q
      0	0	1	p	q
      1	1	q	0	p
      p	p	0	q	1
      q	q	p	1	0

      これは可換加法群の性質を満たしている。
      p=3, q=2と書くと、これは整数の加算を4で割ったあまりになっています。

      +	0	1	2	3
      0	0	1	2	3
      1	1	2	3	0
      2	2	3	0	1
      3	3	0	1	2

• p+1=qとする。ここで1+1=0, 1, p, qのそれぞれについて考えると

  +	0	1	p	q
  0	0	1	p	q
  1	1	?	q	?
  p	p	q	?	?
  q	q	?	?	?

  1の逆元(-1)を両辺に足すことでp=0となり不適

:::以下書きかけ:::

ここで少し面白いアプローチを取ってみます。「有限の整数の集合」ではなく、「多項式の集合」を考え、そこでまず演算子を求めてみるのです。
数学の世界では「同じ性質を持つものは同一視できる」という面白い考え方があります。 例えば、「線形空間」を定義して、その空間上で色んな定理の体系を作ると、ベクトルと関数・行列と(線形一次)微分方程式が同一視できます。そうすると、微分方程式を解くのが対応する行列の演算に帰着できます。
今回の問題で対象としているのはビット列(=決まった範囲の整数)の集合で、これに対して適当な(+')と(*')という演算を定義して、上にあげたような性質を満たすようにしたいと考えていますが、これと同じ性質を満たす集合・演算が見つかれば、それと整数集合の体系を対応付けられるかもしれません。
というわけで、整数の話をちょっと抜きにして演算だけを考えてみます。
{0, 1, 1+1, 1+1+1, 1+1+1+1, ... }
{0, 1, x, x*x, x*x*x,  ... }
、かなり天下り的ですが、以下のような多項式集合を考えてみます。
{0, 1, x, x2, x3, ...}
さて、ここで演算子(+)を定義します。
0 (+) 0   = 0
0 (+) 1   = 1
0 (+) x   = x
0 (+) x+1 = x+1

1 (+) 1   = 1
1 (+) x   = x+1
1 (+) x+1 = x

x (+) x   = 0
x (+) x+1 = 1

x+1 (+) x+1 = 0
、「これらの多項式を普通に掛けて、(x²で」

---

Top -> 数学 -> リード・ソロモン符号化とガロア体

'2007/06/14 / Kei Takahashi / [BBS]