ほろ酔いリードソロモン符号

リードソロモンという符号があります。CDや通信の基盤で使われています。
ここにたどり着くまでの話です。ここでの内容は、その導入の有限体の話の導入です。

情報科学の世界は、有限の世界です。ビルディングブロックは{0,1}です。
加減乗除の演算をするので、これを体として扱いたいです。
数学ではF_2ですが、情報科学ではGF(2)と記述することが一般的なようです。

F_2は、加減乗までは、整数環Zの和と積を使って、modulo(2)で0,1の２つの記号に落とし込めばよいです。
割り算は、0以外の数が１だけなので、1/1=1で問題ありません。

少し世界を大きくして2を素数pにしても同じことができます。modulo(p)でZからの計算をします。
この世界をF_pと書きます。ほぼF_2と同じですが、少し厄介なのが割り算（同じことですが逆元、すなわち積をとったら1になる元）です。
F_2では0以外の元は１つでしたが、F_pではp-1個あり、それらの逆元が１つあるか？を考えなくてはいけません。
具体的には、それほど難しいことではなくF_3であれば1の逆は2です。2の逆は2です。2*2=4=1(mod 3)ですので、2に2をかけたら1になります。

mを勝手な整数として有限体F_mはあるか？というのが自然と問題になります。
m=0はないです。m=1もないです。（ただ、先端のアグレッシブな世界ではF_1が考えられているようですが、、、）。
体には、少なくとも和と積の演算の単位元0,1がなければいけないからです。
m>=2ということです。
m=pq （p,q素数）はどうでしょうか？m=6=2*3とかです。これもNGです。2,3はF_6で０ではありませんが(modulo(6)で０でない）
、積は0になってしまいます。(1/2)*(1/3)=1/0でまずいですね。
この場合の2,3を0-divisorといいます。(すいません、書いている時点で日本語を度忘れしてしまいました)
（0-divisorがない世界を整域といいます。体より少し広い（条件が弱い）世界です。）
したがって、mは一つの素数で割れる、素数pの冪m=p^nしか可能性がありません。

m=4=2*2を考えると、F_4={(0,0),(0,1),(1,0),(1,1)}という集合が考えられます。
和は、成分ごとにF_2の演算をします。和の単位元は(0,0)です。
問題は、「積をどのように定めたらよいか？」です。
たとえば、単純に成分ごとの積をとると、(1,0)*(0,1)=(1*0,0*1)=(0,0)となり0-divisorとなってしまいます。

n>1の有限体（その、積構造）を考えるヒントとして、実数体Rと複素数体Cの関係があります。CはRの”２次拡大体”です。
”Rの拡大体”は、Rを含む体です。”２次”は、”CはR上のベクトル空間と考えたとき、２次である”ということです。
Cの元はRの元a,bと、i^2+1=0を満たす記号iを使って、a+biとなります。
すなわち、CはをR上の基底とするベクトル空間とみなせることを意味します。この意味で”２次”です。
２次の部分は、i^2+1=0 が２次であることに対応するであろうと想像できます。この想像に１つ条件を付け加えれば正しくなります。

次に、積構造はどうでしょうか？実際の計算を見てみます。
複素数の積は
(a+bi)*(c+di)=(ac-bd)+(ad+bc)i
ですが、a+biを上のF_4の時のように(a,b)と表すと、(a,b)*(c,d)=(ac-bd,ad+bc)という積を定義したことになります。
この、不思議な積はどこから来るのでしょうか？

複素数iは（√(-1)をあらわす）記号なので、xでもOKです。ただし、x^2+1=0という条件が必要ですね。
すると、R係数の多項式で、多項式のmodulo (x^2+1)でもいいと考えられます。
a+bi->a+bxと読み替えて、多項式とmoduloの計算をしても同じことが言えます。
a+bi->a+bxと読み替えて、多項式とmoduloの計算をしても同じことが言えます。
(a+bx)*(c+dx)=ac+(ad+bc)x+bdx^2=(ac-bd)+(ad+bc)x (modulo x^2+1)
です。
複素数と、R係数多項式modulo(x^2+1)を同一視してもよいでしょう。（細かい条件を調べる必要はありますが、）
この集合を、R[x]/(x^2+1)という記号で書きます。R[x]は、R係数多項式の集合（和・積も通常の多項式演算、moduloをとることもF_pと同じ）
数と多項式を一緒にしてしまうような違和感があるかもしれませんが、、、。
x^2+1が既約多項式、すなわち（定数でない）次数が小さい多項式の積に分解しない、であることが条件です。
R上の多項式は、３次以上はすべて可約（かならず２次以下の多項式の積になる）のでRは２次以上の拡大はありません。
これは、この方法で実数体Rを拡大複素数体Cが最大の拡大になっていることからきています。
（一般に体K上の多項式環K[x]の剰余環K[x]/(f(x))は、Kの拡大体になります。）

この仕組みを使ってF_pを拡大します。
たとえば、F_2の２次拡大F_4=F_2[x]/(x^2+x+1)です。
このとき、(1,1)と(1,1)の積は、(1,1)*(1,1)=(x+1)*(x+1)=x^2+1=-x=x=(1,0)
となります。
個の計算での”=”は、かなり拡大解釈的な”=”で、最初の=は、F_4の元の表し方の読み替え、２番目はxの係数２をF_2のmoduloで０に読み替え、
３番目は、多項式のmodulo(x^2+x+1)の読み替え、４番目はF_2のでmoduloで-を+に読み替え、最後は元の表し方の読み替え、
をしています。

先ほどのx^2+1が使えない理由は、「x^2+1=0は、R上既約ですがF_2上可約」であるからです。
1を代入するとx^2+1=(1)^2+1=2=0なので（等式は適宜moduloを使っています）、x^2+1=(x-1)^2となってしまいます。
x^2+x+1は、0,1,どちらを代入しても0にはならないので、（２次より小さい因子である１次因子に分解できないので）既約です。

この多項式の表し方を使えば、任意の素数pのF_pの拡大が得られます。
ここからは少々Deepになりますので、別の機会にすることにします。

リードソロモンに一言、実用上よく使われる有限体はF_8（2^8=256個の元を持つ体）です。既約多項式は何でしょうか？？？