「形式情報」と「型番情報」の計算の方法を解説します。
誰のニーズがあるのかはわかりませんが・・・。
このステップで重要なのは、3番目の「あらかじめ決められた多項式で「割り算」して「余り」の多項式を求める」です。
このページでは、具体的な説明は省きますが、「リード・ソロモン」のページで説明するように、多項式で割り算した余りを使うことによって、「エラー訂正」ができるようになるのです。
「エラー訂正」というのは、読み間違ったときでも元の情報を推測するチカラです。
(詳しい解説はこちらを見てくださいね。)
それでは、早速作り方を具体的にみてみましょう。
「エラー訂正レベル」は「L」「M」「Q」「H」の4種類がありますが、それぞれ「L(01)」「M(00)」「Q(11)」「H(10)」の2桁の1、0で表します。
次に、「マスク参照子」ですが、パターン1から8までの数字を3桁の2進数で表したものです。
例えば、「マスク参照子」が「2」の場合「010」とします。
この場合、例えば「エラー訂正レベル」が「Q」で、「マスク参照子」が「5」の場合、「11101」という5桁の1,0にします。
「型番情報」の場合、バージョン7～40のバージョンの数をそのまま、6桁の2進数にします。
例えば、バージョンが15だったら「001111」になります。
これは、次のステップで別の多項式で「割り算」するために必要な作業です。
「形式情報」の場合は、「\(a_{1}x^{14}+a_{2}x^{13}+a_{3}x^{12}+a_{4}x^{11}+a_{5}x^{10}\)」とします。
ここで、\(a_{1},a_{2},a_{3},a_{4},a_{5}\)は、先ほど表した5桁の1,0がそのまま入ります。
例えば、「11101」の場合「\(1x^{14}+1x^{13}+1x^{12}+0x^{11}+1x^{10}=x^{14}+x^{13}+x^{12}+x^{10}\)」となりますね。
一方、「型番情報」の場合は「\(b_{1}x^{17}+b_{2}x^{16}+b_{3}x^{15}+b_{4}x^{14}+b_{5}x^{13}+b_{6}x^{12}\)」とします。
ここで、\(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}\)は、先ほど表した6桁の1,0がそのまま入ります。
例えば、「001111」の場合「\(0x^{17}+0x^{16}+1x^{15}+1x^{14}+1x^{13}+1x^{12}=x^{15}+x^{14}+x^{13}+x^{12}\)」となりますね。
多項式の割り算についてはこちらで解説しているので、見てください。
「形式情報」であれば「\(x_{10}+x_{8}+x_{5}+x_{4}+x_{2}+x+1\)」で割り算します。
「型番情報」であれば「\(x_{12}+x_{11}+x_{10}+x_{9}+x_{8}+x_{5}+x_{2}+1\)」で割り算します。
そして、割り算した余りの多項式を計算します。
割り算した結果は、「形式情報」であれば「\(w_{1}x^{9}+w_{2}x^{8}+w_{3}x^{7}+w_{4}x^{6}+w_{5}x^{5}+w_{6}x^{4}+w_{7}x^{3}+w_{8}x^{2}+w_{9}x+w_{10}\)」になります。
\(w_{1}\)～\(w_{10}\)が求めたい10個の1,0になります。
割り算した結果は、「型番情報」であれば「\(v_{1}x^{11}+v_{2}x^{10}+v_{3}x^{9}+v_{4}x^{8}+v_{5}x^{7}+v_{6}x^{6}+v_{7}x^{5}+v_{8}x^{4}+v_{9}x^{3}+v_{10}x^{2}+v_{11}x+v_{12}\)」になります。
\(v_{1}\)～\(v_{12}\)が求めたい12個の1,0になります。
「形式情報」であれば、次の2つの変換をします。
「排他論理和(はいたろんりわ)」というと難しい言葉に聞こえますが、各桁を比較して「1と1ならば0」「0と0ならば0」「1と0ならば1」「0と1ならば1」とするだけです。
例えば、「10010」と「11100」の排他論理和は「01110」となります。
「型番情報」であれば次の変換をするだけです。
これで、「形式情報」と「型番情報」を計算することができます。
が、結局一覧表をつかって求めたほうが早い気もしますよね。
誰のニーズがあるのかはわかりませんが・・・。
基本的な考え方
「形式情報」も「型番情報」も次のステップを踏んで計算します。- 表したい情報を「1」と「0」を並べて表現する
- \(x^{n}\)を使って、表したい情報を多項式で表現する
- あらかじめ決められた多項式で「割り算」して「余り」の多項式を求める
- 最後にちょっぴり単純な変換をする
このステップで重要なのは、3番目の「あらかじめ決められた多項式で「割り算」して「余り」の多項式を求める」です。
このページでは、具体的な説明は省きますが、「リード・ソロモン」のページで説明するように、多項式で割り算した余りを使うことによって、「エラー訂正」ができるようになるのです。
「エラー訂正」というのは、読み間違ったときでも元の情報を推測するチカラです。
(詳しい解説はこちらを見てくださいね。)
それでは、早速作り方を具体的にみてみましょう。
表したい情報を「1」と「0」を並べて表現する
「形式情報」の場合は、「エラー訂正レベル」と「マスク参照子」を並べて作ります。「エラー訂正レベル」は「L」「M」「Q」「H」の4種類がありますが、それぞれ「L(01)」「M(00)」「Q(11)」「H(10)」の2桁の1、0で表します。
次に、「マスク参照子」ですが、パターン1から8までの数字を3桁の2進数で表したものです。
例えば、「マスク参照子」が「2」の場合「010」とします。
この場合、例えば「エラー訂正レベル」が「Q」で、「マスク参照子」が「5」の場合、「11101」という5桁の1,0にします。
「型番情報」の場合、バージョン7～40のバージョンの数をそのまま、6桁の2進数にします。
例えば、バージョンが15だったら「001111」になります。
\(x^{n}\)を使って、表したい情報を多項式で表現する
このステップでは、初めのステップで1,0に変換した情報を、多項式の表現にします。これは、次のステップで別の多項式で「割り算」するために必要な作業です。
「形式情報」の場合は、「\(a_{1}x^{14}+a_{2}x^{13}+a_{3}x^{12}+a_{4}x^{11}+a_{5}x^{10}\)」とします。
ここで、\(a_{1},a_{2},a_{3},a_{4},a_{5}\)は、先ほど表した5桁の1,0がそのまま入ります。
例えば、「11101」の場合「\(1x^{14}+1x^{13}+1x^{12}+0x^{11}+1x^{10}=x^{14}+x^{13}+x^{12}+x^{10}\)」となりますね。
一方、「型番情報」の場合は「\(b_{1}x^{17}+b_{2}x^{16}+b_{3}x^{15}+b_{4}x^{14}+b_{5}x^{13}+b_{6}x^{12}\)」とします。
ここで、\(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}\)は、先ほど表した6桁の1,0がそのまま入ります。
例えば、「001111」の場合「\(0x^{17}+0x^{16}+1x^{15}+1x^{14}+1x^{13}+1x^{12}=x^{15}+x^{14}+x^{13}+x^{12}\)」となりますね。
あらかじめ決められた多項式で「割り算」して「余り」の多項式を求める
先ほどのステップで作った多項式を、あらかじめ決められた別の多項式で割り算します。多項式の割り算についてはこちらで解説しているので、見てください。
「形式情報」であれば「\(x_{10}+x_{8}+x_{5}+x_{4}+x_{2}+x+1\)」で割り算します。
「型番情報」であれば「\(x_{12}+x_{11}+x_{10}+x_{9}+x_{8}+x_{5}+x_{2}+1\)」で割り算します。
そして、割り算した余りの多項式を計算します。
割り算した結果は、「形式情報」であれば「\(w_{1}x^{9}+w_{2}x^{8}+w_{3}x^{7}+w_{4}x^{6}+w_{5}x^{5}+w_{6}x^{4}+w_{7}x^{3}+w_{8}x^{2}+w_{9}x+w_{10}\)」になります。
\(w_{1}\)～\(w_{10}\)が求めたい10個の1,0になります。
割り算した結果は、「型番情報」であれば「\(v_{1}x^{11}+v_{2}x^{10}+v_{3}x^{9}+v_{4}x^{8}+v_{5}x^{7}+v_{6}x^{6}+v_{7}x^{5}+v_{8}x^{4}+v_{9}x^{3}+v_{10}x^{2}+v_{11}x+v_{12}\)」になります。
\(v_{1}\)～\(v_{12}\)が求めたい12個の1,0になります。
最後にちょっぴり単純な変換をする
先ほどの多項式の割り算の結果でてきた、\(w_{1}\)～\(w_{10}\)や\(v_{1}\)～\(v_{12}\)をちょっぴり変換します。「形式情報」であれば、次の2つの変換をします。
- \(w_{1}\)～\(w_{10}\)の先頭にステップ1で求めた\(a_{1}\)～\(a_{5}\)をくっつけて、「\(a_{1},a_{2},a_{3},a_{4},a_{5},w_{1},w_{2},w_{3},w_{4},w_{5},w_{6},w_{7},w_{8},w_{9},w_{10}\)」とします。
- 「\(a_{1},a_{2},a_{3},a_{4},a_{5},w_{1},w_{2},w_{3},w_{4},w_{5},w_{6},w_{7},w_{8},w_{9},w_{10}\)」と「101010000010010」の「排他論理和」を計算して出来上がりです。
「排他論理和(はいたろんりわ)」というと難しい言葉に聞こえますが、各桁を比較して「1と1ならば0」「0と0ならば0」「1と0ならば1」「0と1ならば1」とするだけです。
例えば、「10010」と「11100」の排他論理和は「01110」となります。
「型番情報」であれば次の変換をするだけです。
- \(v_{1}\)～\(v_{12}\)の先頭にステップ1で求めた\(b_{1}\)～\(b_{6}\)をくっつけて、「\(b_{1},b_{2},b_{3},b_{4},b_{5},b_{6},v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7},v_{8},v_{9},v_{10},v_{11},v_{12}\)」とします。
これで、「形式情報」と「型番情報」を計算することができます。
が、結局一覧表をつかって求めたほうが早い気もしますよね。