DVD のブックを確認していたら、もしかしたら誤り訂正技術の本丸か？というような「原始多項式の原始元」という言葉が出てきました。実は誤り訂正技術そのものの本質ではないようなんですが、これを理解しておかないと計算ができないのでは重要事項です。
原始多項式はこう書いてあります。
P(x) = x^8 + x^4 + x^3 + x^2 + 1
さてここでの x^n は例によって数値列の桁を表します。ところが x が小文字であることに注目して下さい。最初に DVD のデータはバイト単位で処理します、と云いました。そのバイト単位のデータ列 X^n を大文字で表しました。ところがここでは小文字なのでこれはビット列であることを表します。こういうようにバイト関連は大文字、ビット関連は小文字ということで DVD ブックは記載されています。
ところが符号理論、誤り訂正技術関連での扱いは１ビット単位だろうとバイトあるいは複数ビット単位だろうと数学的扱いは同じなので、大文字で統一されていることが多いと思います。一般的な書籍を読むときは注意して下さい。
で、ここでは P(x) は小文字で表現されていますのでビットで見ていきますと、この式は「多項式 P(x) は、ビット列 9 桁目、5 桁目、4 桁目、3 桁目、1 桁目の加算を表す」ということが分かります。これを前にやった「多項式はデータ列を表す」ということで書き直すと、「100011101」となるのですが、今これをやると次の話が進まなくなるのでやめます。
とにかくこういう多項式＝原始多項式ということで一旦打ち切って下さい。
次に「原始多項式の（原始）元」ということですから、P(x) = 0 とおいてこの多項式を解くわけです。ではやってみます。
・・・、？？？
で、できませ～ん！！！
そうです、できないのです。ところがこの（原始）元をαとしろ、と云っているのですからどうせよと？となってしまいます。実際にどうしようもないのです。早い話がαがなんであるか、誰も知りません。これを提唱した数学者も知らないでしょう。が、利用することはできます。つまり実体はなんであるか分からないがその性質は利用できる、ということになります。
どういうことかもっと身近な例で云うと、
x^2 + 1 = 0
の解は虚数表現 i を使って、i、-i ですね。でもよく考えて下さい。i は便宜上定義したもので実体は不明です。ですが何故かこれを利用すると電気の分野では交流信号の位相を含めた表現に適していますね。i などという実体が何であるかわからない記号の性質「２回掛けると符号が反転する」という性質を利用して色々な現象を表現しているだけです。電線の中に「i」が絶叫上げてかけずり回っているわけではありません。（昔私は本気でそうだと思っていました）
それと同じでαも実体は分からないが、何か特別な性質を持っていれば利用価値があるだろうということになります。
その性質とは、
x^8 + x^4 + x^3 + x^2 + 1 =0
の解ですから、α^8 + α^4 + α^3 + α^2 + 1 = 0 が成り立ちます。これが性質です。でよく見てみますと、これは 9 桁のビット列になっています。1 バイト＝ 8 ビットですから 1 桁多いですね。つまり桁上がりしてしまっているわけです。書き直すと、
α^8 = α^4 + α^3 + α^2 + 1
となります。桁上がりしたら、5 桁目、4 桁目、3 桁目、1 桁目に加算せよ、という意味になります。正直言ってこの辺りの説明は難しいです。x はビット単位だったのですが、それらを結合した原始多項式はバイトになっていてαはなんだか分からなくて、今ビット単位の説明をしているのか塊を説明しているのか自分でもわからなくなっています。ですが、ここはこういうもんだと思って下さい。より深く理解したい人は専門書を読んで下さい。
結局何がやりたいかというと、バイトデータをαで表したい、ということです。この辺りは華麗にスルーした方が混乱しないとおもいます。
さて、αでバイトデータを表す手始めとして、α^0 = 1 = 00000001 と置きます。8 ビット列なら何でも良いのですが、難しくなるだけなのでやめた方が良いです。で、このビット列ですが 2 進数表現と思ってはいけません。α進数表現とでも思って下さい。先に 2 進数表現だった場合の説明をすると、00000001 に 2 を掛けると云うことはビット列を左にシフトさせることになります。これを延々と繰り返すと 8 桁をオーバーして延々と桁が増え続けます。これでは役に立ちません。このビット列はα進数と考えるとどうなるかというと、α^0 にαを掛けるとα^1 になるのですが、とりあえず同様に左にシフトさせます。そして繰り返していきます。
α^0 = 0000 0001
α^1 = 0000 0010
α^2 = 0000 0100
α^3 = 0000 1000
α^4 = 0001 0000
α^5 = 0010 0000
α^6 = 0100 0000
α^7 = 1000 0000
ここまでは順調です。問題は次です。
α^8 = 1 0000 0000
オーバーフローしてしまいました。そこでαが持つ性質「α^8 = α^4 + α^3 + α^2 + 1」が登場します。
α^8 = α^4 + α^3 + α^2 + 1 = (0001 0000)+(0000 1000)+(0000 0100)+(0000 0001)
= 0001 1101
となります。以下、
α^9 = α･α^8 = 「α^8 のデータを左にシフト」= 0011 1010
あるいは、
α^9 = α･α^8 = α･（α^4 + α^3 + α^2 + 1）=α^5 + α^4 + α^3 + α
= (0010 0000)+(0001 0000)+(0000 1000)+(0000 0010)
= 0011 1010
という案配です。とにかく何か普通に指数表現の中で計算して、α^7, α^6, α^5, α^4, α^3, α^2, α, 1 の組み合わせとなれば、8 ビットすべてを表現できることになります。このまま繰り返していくと α^254 まで出来ます。その中には同じビット列はありません。そして α^255 は α^0 = 1 になって巡回します。
1 つ足りないだろう？ということですが、それは 0 = 0000 0000 です。これはαで表現することは出来ません。
で、00000000 と α^n (n=0 to 254) を合わせて一つの符号体（ガロア体）ということになります。
もうここまででお分かりのように、すべてのバイトデータは 0 またはα^n で表現できますから、掛け算はαに置き換えて計算することができます。
例として、(0000 1000) x (0100 0000) はα表現すると
α^3 x α^6 = α^(3 + 9) = α^9
となり、上の計算結果から (0011 1010) となります。
次回はαによる計算例を示していこうと思います。
原始多項式はこう書いてあります。
P(x) = x^8 + x^4 + x^3 + x^2 + 1
さてここでの x^n は例によって数値列の桁を表します。ところが x が小文字であることに注目して下さい。最初に DVD のデータはバイト単位で処理します、と云いました。そのバイト単位のデータ列 X^n を大文字で表しました。ところがここでは小文字なのでこれはビット列であることを表します。こういうようにバイト関連は大文字、ビット関連は小文字ということで DVD ブックは記載されています。
ところが符号理論、誤り訂正技術関連での扱いは１ビット単位だろうとバイトあるいは複数ビット単位だろうと数学的扱いは同じなので、大文字で統一されていることが多いと思います。一般的な書籍を読むときは注意して下さい。
で、ここでは P(x) は小文字で表現されていますのでビットで見ていきますと、この式は「多項式 P(x) は、ビット列 9 桁目、5 桁目、4 桁目、3 桁目、1 桁目の加算を表す」ということが分かります。これを前にやった「多項式はデータ列を表す」ということで書き直すと、「100011101」となるのですが、今これをやると次の話が進まなくなるのでやめます。
とにかくこういう多項式＝原始多項式ということで一旦打ち切って下さい。
次に「原始多項式の（原始）元」ということですから、P(x) = 0 とおいてこの多項式を解くわけです。ではやってみます。
・・・、？？？
で、できませ～ん！！！
そうです、できないのです。ところがこの（原始）元をαとしろ、と云っているのですからどうせよと？となってしまいます。実際にどうしようもないのです。早い話がαがなんであるか、誰も知りません。これを提唱した数学者も知らないでしょう。が、利用することはできます。つまり実体はなんであるか分からないがその性質は利用できる、ということになります。
どういうことかもっと身近な例で云うと、
x^2 + 1 = 0
の解は虚数表現 i を使って、i、-i ですね。でもよく考えて下さい。i は便宜上定義したもので実体は不明です。ですが何故かこれを利用すると電気の分野では交流信号の位相を含めた表現に適していますね。i などという実体が何であるかわからない記号の性質「２回掛けると符号が反転する」という性質を利用して色々な現象を表現しているだけです。電線の中に「i」が絶叫上げてかけずり回っているわけではありません。（昔私は本気でそうだと思っていました）
それと同じでαも実体は分からないが、何か特別な性質を持っていれば利用価値があるだろうということになります。
その性質とは、
x^8 + x^4 + x^3 + x^2 + 1 =0
の解ですから、α^8 + α^4 + α^3 + α^2 + 1 = 0 が成り立ちます。これが性質です。でよく見てみますと、これは 9 桁のビット列になっています。1 バイト＝ 8 ビットですから 1 桁多いですね。つまり桁上がりしてしまっているわけです。書き直すと、
α^8 = α^4 + α^3 + α^2 + 1
となります。桁上がりしたら、5 桁目、4 桁目、3 桁目、1 桁目に加算せよ、という意味になります。正直言ってこの辺りの説明は難しいです。x はビット単位だったのですが、それらを結合した原始多項式はバイトになっていてαはなんだか分からなくて、今ビット単位の説明をしているのか塊を説明しているのか自分でもわからなくなっています。ですが、ここはこういうもんだと思って下さい。より深く理解したい人は専門書を読んで下さい。
結局何がやりたいかというと、バイトデータをαで表したい、ということです。この辺りは華麗にスルーした方が混乱しないとおもいます。
さて、αでバイトデータを表す手始めとして、α^0 = 1 = 00000001 と置きます。8 ビット列なら何でも良いのですが、難しくなるだけなのでやめた方が良いです。で、このビット列ですが 2 進数表現と思ってはいけません。α進数表現とでも思って下さい。先に 2 進数表現だった場合の説明をすると、00000001 に 2 を掛けると云うことはビット列を左にシフトさせることになります。これを延々と繰り返すと 8 桁をオーバーして延々と桁が増え続けます。これでは役に立ちません。このビット列はα進数と考えるとどうなるかというと、α^0 にαを掛けるとα^1 になるのですが、とりあえず同様に左にシフトさせます。そして繰り返していきます。
α^0 = 0000 0001
α^1 = 0000 0010
α^2 = 0000 0100
α^3 = 0000 1000
α^4 = 0001 0000
α^5 = 0010 0000
α^6 = 0100 0000
α^7 = 1000 0000
ここまでは順調です。問題は次です。
α^8 = 1 0000 0000
オーバーフローしてしまいました。そこでαが持つ性質「α^8 = α^4 + α^3 + α^2 + 1」が登場します。
α^8 = α^4 + α^3 + α^2 + 1 = (0001 0000)+(0000 1000)+(0000 0100)+(0000 0001)
= 0001 1101
となります。以下、
α^9 = α･α^8 = 「α^8 のデータを左にシフト」= 0011 1010
あるいは、
α^9 = α･α^8 = α･（α^4 + α^3 + α^2 + 1）=α^5 + α^4 + α^3 + α
= (0010 0000)+(0001 0000)+(0000 1000)+(0000 0010)
= 0011 1010
という案配です。とにかく何か普通に指数表現の中で計算して、α^7, α^6, α^5, α^4, α^3, α^2, α, 1 の組み合わせとなれば、8 ビットすべてを表現できることになります。このまま繰り返していくと α^254 まで出来ます。その中には同じビット列はありません。そして α^255 は α^0 = 1 になって巡回します。
1 つ足りないだろう？ということですが、それは 0 = 0000 0000 です。これはαで表現することは出来ません。
で、00000000 と α^n (n=0 to 254) を合わせて一つの符号体（ガロア体）ということになります。
もうここまででお分かりのように、すべてのバイトデータは 0 またはα^n で表現できますから、掛け算はαに置き換えて計算することができます。
例として、(0000 1000) x (0100 0000) はα表現すると
α^3 x α^6 = α^(3 + 9) = α^9
となり、上の計算結果から (0011 1010) となります。
次回はαによる計算例を示していこうと思います。