独極・QRコード担当の「あじな」です。
ガロアさんって人は、20才前後で「体」の概念を考えたそうです。
僕は20才前後だと、大学に通いながら毎日遊びほうけておりました・・
できる人はちがいますね・・・やっぱり。
ただし、ここで「\(x\)」は何でもよい数字(だから「\(x\)」としているのです・・・)なので、「\(\alpha\)」を使うことにします。
そして、この「\(\alpha\)」は「\(x^8+x^4+x^3+x^2+1=0\)の解の1つ」とします。
つまり、「\(\alpha^8+\alpha^4+\alpha^3+\alpha^2+1=0\)」です。これは、「\(\alpha^8=\alpha^4+\alpha^3+\alpha^2+1\)」と書くこともできます。
えっ？マイナスを忘れてるって？
いえいえ。今考えている体の世界では、係数は「2で割った余り」にするのでした。「-1」を2で割った余りは「1」になります。そのため、この世界では「\(-1=1\)」なのです。
さて、\(\alpha\)を使うと、この体の要素は次のような式でかけることとなります。
$$ a_7\alpha^7+a_6\alpha^6+a_5\alpha^5+a_4\alpha^4+a_3\alpha^3+a_2\alpha^2+a_1\alpha^1+a_0\alpha^0 $$ このとき、上記の係数だけ抜き出した表現をすると、\((a_7,a_6,a_5,a_4,a_3,a_2,a_1,a_0)\)となります(このことを「2進数表現」と呼びましょう)。
ちなみに、この2進数を10進数に変換したものを「10進数表現」とここでは呼びましょう。
このとき、\(\alpha^0,\alpha^1,\alpha^2, \cdots ,alpha^254,\alpha^256\)がどう表現されるか見てみましょう。
・・・疲れました。これが、永遠と残り242行続いていきます。全量はこちらを見てください。
\(\alpha\)の列は、単純に\(0,\alpha^0,\alpha^1,\alpha^2,\cdots,\alpha^253,\alpha^254\)となるだけです。
2進数表現の列は、多項式表現の部分の係数を抜き出しているだけです。そして、10進数表現の列は、2進数表現を10進数の数字に置き換えただけです。ここでは0〜255までの数字がでてきます。
(実は、0〜255までの数字がでてくるかどうかは、別途証明しないとわからないのですが、雰囲気的にでてくるものだと思ってください)
多項式表現の列はちょっと難しいです。ポイントは、次の3つです。
01.\(\alpha\)を一つ前の行の多項式表現の部分に単純に掛け算する
02.もし、\(\alpha^8\)がでてきたら、\(\alpha^4+\alpha^3+\alpha^2+1\)で置き換える(\(\alpha^8=\alpha^4+\alpha^3+\alpha^2+1\)でしたね)
03.各係数を「2」で割り算した余りに置き換えます(今回の体で導入している特殊な足し算のルールですね。係数が「2」になっている項は係数が「0」に置き換わるので、なくなります)
こうやって、各行を計算することができます。そして、この数式のすごいところは\(\alpha^{254}=\alpha^7+\alpha^3+\alpha^2+\alpha^1\)となるところです。
えっ？何がすごいかって？\(\alpha^{254}\)に、\(\alpha\)を掛け算して、\(\alpha^{255}\)を計算してみてください。
$$ \alpha^{255}=\alpha^{254} \times \alpha=\alpha^8+\alpha^4+\alpha^3+\alpha^2 $$ となりますが、\(\alpha^8=\alpha^4+\alpha^3+\alpha^2+1\)なので、上の式は次のようになります。
$$ \alpha^{255}=(\alpha^4+\alpha^3+\alpha^2+1)+\alpha^4+\alpha^3+\alpha^2=2\alpha^4+2\alpha^3+2\alpha^2+1 $$ そして、各係数を2で割った余りに置き換えるので、最終的には次のようになります。
$$ \alpha^{255}=1 $$ そうなんです。この\(\alpha\)は255乗すると1に戻るんです。
だから、例えば\(\alpha^{300}\)なんてでてきても、「\(\alpha^{300}=\alpha^{255} \times \alpha^{45}=1 \times \alpha^{45}=\alpha^{45}\)」と、小さい\(\alpha\)に置き換えることができます。
そのため、大きな数字がでてこなくなるので計算がとっても簡単なんです。
QRコードで使うリード・ソロモン符号では0〜255までの数字を先ほどの表で\(\alpha\)に変換して計算します。
(しつこいですが、\(\alpha\)で計算するときの足し算と掛け算は普通のやつではなく、今回導入した特殊な足し算・掛け算をします)
この、\(\alpha\)に変換した数字や、特殊な足し算・掛け算のことを「\(2^8\)のガロア拡大体、\(GF(2^8)\)」と呼びます。
GFは「Galois Field」の略です。「Galois(ガロア)」はこういう特殊な計算について研究した研究者の名前で、「Field(フィールド)」は「体」という意味です。
$$ \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 & 1 & 1 \\ 1 & \alpha & \alpha^2 & \cdots & \alpha^(2t-3) & \alpha^(2t-2) & \alpha^(2t-1) \\ 1 & \alpha^2 & \alpha^4 & \cdots & \alpha^{2(2t-3)} & \alpha^{2(2t-2)} & \alpha^{2(2t-1)} \\ \vdots & \vdots & \vdots & \cdots & \vdots & \vdots & \vdots \\ 1 & \alpha^{(n-3)} & \alpha^{2(n-3)} & \cdots & \alpha^{(n-3)(2t-3)} & \alpha^{(n-3)(2t-2)} & \alpha^{(n-3)(2t-1)} \\ 1 & \alpha^{(n-2)} & \alpha^{2(n-2)} & \cdots & \alpha^{(n-2)(2t-3)} & \alpha^{(n-2)(2t-2)} & \alpha^{(n-2)(2t-1)} \\ 1 & \alpha^{(n-1)} & \alpha^{2(n-1)} & \cdots & \alpha^{(n-1)(2t-3)} & \alpha^{(n-1)(2t-2)} & \alpha^{(n-1)(2t-1)} \\ \end{pmatrix} $$ リード・ソロモン符号を計算するときは全て先ほどの「\(GF(2^8)\)」を使って計算するので、ここででてくる\(\alpha\)は「\(GF(2^8)\)」の要素として扱います。
もし、\(n=50,t=20\)となったら、上の行列の右下の要素\(\alpha^{(n-1)(2t-1)}\)は\(\alpha^{49 \times 39}=\alpha^{1911}\)となります。
これは、普通だったらとっても大きな数になりそうですね・・・。でも\(alpha^{255}=1\)という性質をつかうと、これを簡単にできます。
\(\alpha^{1911}=(\alpha^{255})^7 \times \alpha^{126}=1^7 \times \alpha^{126}=\alpha^{126}\)となりますよね。
このガロア拡大体、\(GF(2^8\)を使っていると、どんなに大きな数字でも\(alpha^{255}\)より小さくすることができるという便利な特徴を持っているんです。(だから、リード・ソロモン符号に使われることになったのですが・・・)
さて、元のメッセージからリード・ソロモン符号を計算するときに、\((z-\alpha^0)(z-\alpha^1)(z-\alpha^2) \cdots (z-\alpha^{(2t-3)})(z-\alpha^{(2t-2)})(z-\alpha^{(2t-1)})\)で割り算しなければいけませんでした。
ここででてくる\(\alpha\)も「\(GF(2^8)\)」のメンバーとして扱います。
例として「\(t=5\)」のときの場合をみてみましょう。「\(t=5\)」とすると、割り算をする多項式は次のようになります。
$$ (z-\alpha^0)(z-\alpha^1)(z-\alpha^2)(z-\alpha^3)(z-\alpha^4)(z-\alpha^5)(z-\alpha^6)(z-\alpha^7)(z-\alpha^8)(z-\alpha^9) $$ これを普通の計算のように展開すると次のようになります。
$$ \begin{align} z^{10} & +\\ & (-\alpha^9-\alpha^8-\alpha^7-\alpha^6-\alpha^5-\alpha^4-\alpha^3-\alpha^2-\alpha^1-1)z^9+\\ & (\alpha^{17}+\alpha^{16}+2\alpha^{15}+2\alpha^{14}+3\alpha^{13}+3\alpha^{12}+4\alpha^{11}+4\alpha^{10}+5\alpha^{9}+4\alpha^{8}+4\alpha^{7}+3\alpha^{6}+3\alpha^{5}+2\alpha^{4}+2\alpha^3+\alpha^{2}+\alpha)z^8+\\ & (-\alpha^{24}-\alpha^{23}-2\alpha^{22}-3\alpha^{21}-4\alpha^{20}-5\alpha^{19}-7\alpha^{18}-8\alpha^{17}-9\alpha^{16}-10\alpha^{15}-10\alpha^{14}-10\alpha^{13}-10\alpha^{12}-9\alpha^{11}-8\alpha^{10}-7\alpha^{9}-5\alpha^{8}-4\alpha^{7}-3\alpha^{6}-2\alpha^{5}-\alpha^{4}-\alpha^{3})z^7+\\ & (\alpha^{30}+\alpha^{29}+2\alpha^{28}+3\alpha^{27}+5 \alpha^{26}+6\alpha^{25}+9\alpha^{24}+10\alpha^{23}+13\alpha^{22}+14\alpha^{21}+16\alpha^{20}+16\alpha^{19}+18\alpha^{18}+16\alpha^{17}+16\alpha^{16}+14\alpha^{15}+13\alpha^{14}+10\alpha^{13}+9\alpha^{12}+6\alpha^{11}+5\alpha^{10}+3\alpha^{9}+2\alpha^{8}+\alpha^{7}+\alpha^{6})z^6+\\ & (-\alpha^{35}-\alpha^{34}-2\alpha^{33}-3\alpha^{32}-5\alpha^{31}-7\alpha^{30}-9\alpha^{29}-11\alpha^{28}-14\alpha^{27}-16\alpha^{26}-18\alpha^{25}-19\alpha^{24}-20\alpha^{23}-20\alpha^{22}-19\alpha^{21}-18\alpha^{20}-16\alpha^{19}-14\alpha^{18}-11\alpha^{17}-9\alpha^{16}-7\alpha^{15}-5\alpha^{14}-3\alpha^{13}-2\alpha^{12}-\alpha^{11}-\alpha^{10})z^5+\\ & (\alpha^{39}+\alpha^{38}+2\alpha^{37}+3\alpha^{36}+5\alpha^{35}+6\alpha^{34}+9\alpha^{33}+10\alpha^{32}+13\alpha^{31}+14\alpha^{30}+16\alpha^{29}+16\alpha^{28}+18\alpha^{27}+16\alpha^{26}+16\alpha^{25}+14\alpha^{24}+13\alpha^{23}+10\alpha^{22}+9\alpha^{21}+6\alpha^{20}+5\alpha^{19}+3\alpha^{18}+2\alpha^{17}+\alpha^{16}+\alpha^{15})z^4+\\ & (-\alpha^{42}-\alpha^{41}-2\alpha^{40}-3\alpha^{39}-4\alpha^{38}-5\alpha^{37}-7\alpha^{36}-8\alpha^{35}-9\alpha^{34}-10\alpha^{33}-10\alpha^{32}-10\alpha^{31}-10\alpha^{30}-9\alpha^{29}-8\alpha^{28}-7\alpha^{27}-5\alpha^{26}-4\alpha^{25}-3\alpha^{24}-2\alpha^{23}-\alpha^{22}-\alpha^{21})z^3+\\ & (\alpha^{44}+\alpha^{43}+2\alpha^{42}+2\alpha^{41}+3\alpha^{40}+3\alpha^{39}+4\alpha^{38}+4\alpha^{37}+5\alpha^{36}+4\alpha^{35}+4\alpha^{34}+3\alpha^{33}+3\alpha^{32}+2\alpha^{31}+2\alpha^{30}+\alpha^{29}+\alpha^{28})z^2+\\ & (-\alpha^{45}-\alpha^{44}-\alpha^{43}-\alpha^{42}-\alpha^{41}-\alpha^{40}-\alpha^{39}-\alpha^{38}-\alpha^{37}-\alpha^{36})z+\\ & \alpha^{45} \end{align} $$ 予想通りですが、びっくりする式になりましたね。。
もうここまでくるとどうにでもなれ！って感じですが、この式の\(\alpha\)の部分を先ほどの表に従って、多項式表現に直してみます。
例えば、\(-\alpha^9-\alpha^8-\alpha^7-\alpha^6-\alpha^5-\alpha^4-\alpha^3-\alpha^2-\alpha^1-1\)であれば、\(-1((\alpha^5+\alpha^4+\alpha^3+\alpha)+(\alpha^4+\alpha^3+\alpha^2+1)+\alpha^7+\alpha^6+\alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha^1+1\)となります。(-1を括りだしています)
これを整理すると次のようになります。
$$ \alpha^7+\alpha^6+2\alpha^5+3\alpha^4+3\alpha^3+2\alpha^2+2\alpha^1+2\alpha^0 $$ ちなみに、\(\alpha^0=1,\alpha^1=\alpha\)であることに注意してくださいね。次に、各項の係数を2で割った余りに置き換えます。
$$ -1*(\alpha^7+\alpha^6+\alpha^4+\alpha^3) $$ 最後に多項式表現を先ほどの表に従って\(\alpha\)に置き換えると、\(\alpha^{251}\)になります。
つまり、\(-\alpha^9-\alpha^8-\alpha^7-\alpha^6-\alpha^5-\alpha^4-\alpha^3-\alpha^2-\alpha^1-1=-\alpha^{251}\)となるのです。
(さらに言えば、\(-alpha^{251}\)の係数「-1」は、2で割ると余りが1になるので、\(alpha^{251}\)とかけてしまいます)
超シンプルになりましたね。こんな感じですべての係数の計算をしていくと、上の式は次のようになります。
$$ z^{10}+\alpha^{251}z^9+\alpha^{67}z^8+\alpha^{46}z^7+\alpha^{61}z^6+\alpha^{118}z^5+\alpha^{70}z^4+\alpha^{64}z^3+\alpha^{94}z^2+\alpha^{32}z^1+\alpha^{45}z^0 $$ あんなに複雑だった式が・・・とってもすっきりしました。ガロア拡大体の威力はすさまじいですね。
メッセージ多項式を上の式で割り算すれば、その余りがリード・ソロモン符号になるのでしたね。
ちなみに、割り算するときにはメッセージ多項式も\(\alpha\)に置き換えて、多項式同志の割り算しなければいけません。
「ガロア拡大体、\(GF(2^8\)」を使うと大きな数字でも簡単に計算できることがわかりました。
これで、QRコードを理解するための道具はそろいました。
ここまで、わかればQRコードを99.9%理解したことになります。
次回からは、これまで解説した内容をつかって、具体的なQRコードの作り方を解説していきます！ようやくこの連載の終わりが見えてきました・・・
ガロアさんって人は、20才前後で「体」の概念を考えたそうです。
僕は20才前後だと、大学に通いながら毎日遊びほうけておりました・・
できる人はちがいますね・・・やっぱり。
これまでの復習 [表示する]
- QRコードは株式会社デンソーが作ったもので、スマホや携帯で読み取れる
- QRコードは「小さな白と黒の四角でできている」「多少汚れても大丈夫」という特徴がある
- 白黒の四角を使うのは、コンピュータにわかりやすくさせるため
- QRコードは「機能パターン」と「符号化領域」で出来上がっている
- 「機能パターン」は、「クワイエットゾーン」「位置検出パターン」「位置検出パターンの分離パターン」「タイミングパターン」「位置合わせパターン」の5種類
- 「符号化領域」は「形式情報」「型番情報」「データ領域」の3種類
- 「形式情報」は「エラー訂正レベル」と「マスクパターン参照子」で決まり、「\(4 \times 8=32\)」種類のパターンがある
- 「型番情報」は「QRコードのバージョンによって決まり、40種類ある
- 「データ領域」は「データ」と「エラー訂正情報」で出来上がる
- QRコードはバージョンが1〜40まである。一辺の大きさは、「QRコードのバージョン(1〜40)\( \times \)4\( + \)17」
- 「エラー訂正レベル」は「L(7%の汚れまで)」「M(15%の汚れまで)」「Q(25%の汚れまで)」「H(30%の汚れまで)」の4種類ある。
- 「エラー訂正レベル」が「L」だと「QRコード」で表現できるデータの量は最大で、「H」のときに最小になる。
- 「1bit」とは白・黒、1・0のような2種類の情報を表すことができる能力のことで、文字を増やすと「2bit(4種類)」「3bit(8種類)」と表現できる種類が増える
- 日常の言葉を「エンコード」して「コード(符号)」に置き換え、「コード(符号)」を「デコード」して日常の言葉に戻す
- QRコードの「エンコード」方式は「数字モード」「英数字モード」「漢字モード」「8bitモード」の4種類
- どの「エンコード」方式でも、データは「モード指示子」＋「文字数指示子」＋「データ」＋「終端パターン」＋「埋め草ビット」＋「埋め草ワード」となる
- QRコードには「白」と「黒」を読み間違えても、元の情報を復元する「エラー訂正」能力が備わっている
- 「エラー訂正」は読み取れた(聞き取れた)言葉から最も近い「ありえそうな単語」を推測すること
- 「エラー訂正力が強い」ということは、「あえて使っていない単語が多い」ということと同じで、効率性は悪い
- 1,0でできている符号では「ハミング距離(2つの符号間で1と0が異なる箇所の個数)」があり、符号間で最も「ハミング距離」が小さいものを「最小距離」と呼ぶ
- 使える「単語」を制限すると「最小距離」は大きくなる
- 「最小距離」の半分までのエラーであれば訂正することができる
- 「単語」を「符号化」したものに、適当な「1」や「0」を後ろにつけると「最小距離」が大きい「エラー訂正機能付符号」になる
- 「エラー訂正機能付符号」を作る際は「符号」に「行列(生成行列)」を掛け算する。
- 「QRコード」は「リード・ソロモン符号」と呼ばれる方法で「エラー訂正機能付符号」を作る
- 「行列」は数字を並べただけのもので、もともとは「連立方程式」の係数だけ抜き取ってならべたもの
- 「行列」の「足し算」「引き算」は各「行列」の要素同士を「足し算」「引き算」したもの
- 「行列」の「掛け算」は、左の「行列」から「行」を取り出し、右の「行列」から「列」を取り出して、それぞれの要素を掛け算して足し合わせる
- 左の「行列」の大きさが「a行b列」で、右の「行列」の大きさが「b行c列」だった時、「掛け算」結果の行列は「a行c列」になる
- 「行列」の「掛け算」は順番を変えると結果も変わる
- 「掛け算」しても結果を変えない行列を「単位行列」と呼び、「掛け算」すると結果が「単位行列」になる行列を「逆行列」と呼ぶ
- 「行列」の特徴を表している「数字」を「行列式」と呼ぶ。「行列式」は「正方行列」だけが持っている
- 「並び替え」は「置換」によってい表すことができ、偶数回の「置換」でできる「並び替え」を「遇置換」、奇数回の「置換」でできる「並び替え」を「奇置換」という
- 「行列式」は各列から数字を選択し「掛け算」し、符号をつけた(「遇置換→(+)」「奇置換→(-)」たものを全ての選択パターンで足し合わせる。
- 「列」で計算しても、「行」で計算しても結果は同じ
- 「全てが0の列」、もしくは、「すべてが0の行」があれば「行列式」は「0」
- 「列」を入れ替えたら「行列式」の符号が変わる。「行」を入れ替えても「行列式」の符号が変わる。
- 全く同じ「行」が2個以上あれば「行列式」は「0」。全く同じ「列」が2個以上あっても「行列式」は「0」
- ある「行列」の「行列式」は、その「行列」の1つの「列」(もしくは「行」)を2つに分割して、2つの「行列」の「行列式」の「足し算」にすることができる
- ある「行」に違う「行」を「足し引き」しても、「行列式」の結果は変わらない。ある「列」に違う「列」を「足し引き」しても、「行列式」の結果は変わらない。
- ある「行(もしくは列)」を「定数倍」した「行列」の「行列式」は、「定数倍」する前の「行列」の「行列式」に定数をかけたものと同じ
- 2つの「行列」を「掛け算」した結果の「行列」の「行列式」と、それぞれの「行列」の「行列式」を「掛け算」した結果は同じ((\ \left| \mathb{A} \times \mathb{B} \right| = \left| \mathb{A} \right| \times \left| \mathb{B} \right| \))
- 「連立方程式」の係数を抜き出した「行列」の「行列式」の値が「0」になるということは、元の「連立方程式」が「不良設定問題」である
- 「逆行列」は「正方行列」かつ「行列式」の値が「0」でない「行列」だけに存在する
- 「\((-1)^{(i+j)} \times (元の行列からi行目とj列目を取り去った行列) \)」を「余因子行列」と呼ぶ
- 「行列式」は「余因子展開」を使うと、1サイズ小さい「行列」の「行列式」の「足し算」に展開することができる
- 「逆行列」は「(元の「行列」の「行列式」の逆数)\(\times\)(x行・y列目の要素が＜元の行列のy行・x列目を取り除いた「余因子行列」の「行列式」＞となる「行列」)」
- 「階段行列」は上の行から、左側(0の部分を除きます)を1にして、その行より下の行の左側が0になるように適当な数字をかけて足し算・引き算するというのを繰り返して作る
- 「ランク」はその「行列」の中の独立した行(または列)の数で、「連立方程式」の係数を「行列」にした場合、未知数の数より「ランク」が低ければ「不良設定問題」となる
- 「符号」のサイズが1行n列、「エラー訂正付符号」のサイズが1行m列のとき、「生成行列」はn行m列になる
- 「QRコード」で利用される「エラー訂正機能付符号」は「リード・ソロモン符号」と呼ばれるもの
- 「検査行列」を「エラー訂正機能付符号」に「掛け算」すると結果は「ゼロ行列」になる。逆に「ゼロ行列」にならないと、読み取った「エラー訂正機能付符号」が間違っている
- エラー訂正機能のスペックは「n(「エラー訂正機能付符号」の「長さ」)」、「k(実質的に単語を表現する桁数)」、「d(「エラー訂正機能付符号」の間の「最小距離」)」の3つ
- エラー訂正機能のスペックの「n(「エラー訂正機能付符号」の「長さ」)」は「検査行列」の行数と同じ
- エラー訂正機能のスペックの「k(「実質的に単語を表現する桁数)」は「検査行列」をn行m列だとすると、「n-(検査行列のランク)」となる
- 同じ仲間の「エラー訂正機能付符号」を2つ用意すると、それらを「引き算」した結果も同じ仲間の「エラー訂正機能付符号」の1つになる
- 「エラー訂正機能付符号」軍団の中の「最小距離」は、その「エラー訂正機能付符号」軍団の中で最も小さい「ハミング重み」と同じになる
- エラー訂正機能のスペックの「d(「エラー訂正機能付符号」の間の「最小距離」)」は「(「検査行列」の「ランク」)+1」以上となる
- 「シングルトン限界式」は「d(「エラー訂正機能付符号」の間の「最小距離」)」が「n(「エラー訂正機能付符号」の「長さ」)-k(実質的に単語を表現する桁数)+1」以下になること
- リード・ソロモンの「検査行列」は、x行y列の要素が\(\alpha^{(x-1)(y-1)}\)で、xはn行まで、yは2t列までの「行列」
- リード・ソロモンの「検査行列」のランクは2t
- リード・ソロモンの「検査行列」の特徴は、「エラー訂正機能付符号」の「長さ」はn、実質的に単語を表現する桁数)はn-2t、「エラー訂正機能付符号」の間の「最小距離」は2t+1
- 「ヴァンデルモンド行列」の行列式は、行列の要素に同じ値のものがなければ「0」にはならない。
- 受信符号に検査行列を掛け算した結果は、発生したエラーに検査行列を掛けたものと同じになる、「\(\boldsymbol{Y} \times \boldsymbol{H} = \boldsymbol{E} \times \boldsymbol{H}\)」
- 「\(\boldsymbol{Y} \times \boldsymbol{H} = \boldsymbol{E} \times \boldsymbol{H}\)」を展開すると、方程式の数がn個、未知数が2t個の連立方程式になる
- リード・ソロモン符号の解き方は、「01.エラーの発生個数」「02.エラーの発生位置」「03.エラーの内容」の3ステップ
- \(\begin{vmatrix} S_0 & S_1 & \ldots & S_{j-1} \\ S_1 & S_2 & \ldots & S_{j} \\ \vdots & \vdots & \ddots & \vdots \\ S_{j-1} & S_{j} & \ldots & S_{ 2j-2 } \\ \end{vmatrix}\)という行列式の\(j\)の値を\(t\)から1つずつ減らしていき、初めて行列式の値が「0」以外になった時の\(j\)がエラーの発生個数になる。
- エラーが発生している位置に対応する\(\alpha\)の「逆数」(つまり、\(\alpha^{-p_0},\alpha^{-p_1},\cdots ,\alpha^{-p_{j-2}},\alpha^{-p_{j-1}}\)を入力したときだけ「0]を出力する関数を、\(\boldsymbol{Y} \)と\(\boldsymbol{H}\)の情報から作ることができ、エラーの位置を求めることができる
- エラーの位置が分かった状態であれば、元の「\(\boldsymbol{Y} \times \boldsymbol{H} = \boldsymbol{E} \times \boldsymbol{H}\)」を普通の連立方程式のように解くことができ、「エラーの内容」を求めることができる
- 多項式を多項式で割り算することができ、割り算した商を\(Q(x)\)、余りを\(R(x)\)とすると、「\(f(x) = g(x)Q(x) + R(x)\)」と書ける
- 次数が\(f\)の多項式を次数が\(g\)の多項式で割り算すると余りの多項式の次数は\(g\)未満になる
- 多項式\(f(x)\)の解(\(f(a)=0\)となる\(a\)の値）を使うと、\(f(x)=(x-a)R(x)\)と因数分解できる（剰余の定理）
- 多項式\(f(x)\)は\(f(x) = (x-a_1)(x-a_2)(x-a_3) \cdots (x-a_{(n-2)})(x-a_{(n-1)})(x-a_{n})\)と因数分解できる（ただし、\(a\)は複素数になることもある）
- \(x_0\)〜\(x_{(n-1)}\)を係数にもつ\(n-1\)次の多項式\(f(z)\)(\(f(z)=z^0 x_0 + z^1 x_1 + z^2 x_2 + \cdots + z^{(n-3)} x_{(n-3)} + z^{(n-2)} x_{n-2} + z^{(n-1)}x_{(n-1)})を\((z-\alpha^0)(z-\alpha^1)(z-\alpha^2) \cdots (z-\alpha^{(2t-3)})(z-\alpha^{(2t-2)})(z-\alpha^{(2t-1)})\)で割り切ることができれば、\(x_0\)〜\(x_{(n-1)}\)はリード・ソロモン符号
- メッセージ多項式\((m(z)=z^0 m_0 + z^1 m_1 + z^2 m_2 + \cdots + z^{(k-3)} m_{(k-3)} + z^{(k-2)} m_{(k-2)} + z^{(k-1)}m_{(k-1)})\)に\(z^{2t}\)を掛けて、\((z-\alpha^0)(z-\alpha^1)(z-\alpha^2) \cdots (z-\alpha^{(2t-3)})(z-\alpha^{(2t-2)})(z-\alpha^{(2t-1)})\)で割り算した余り\(R(z)\)の多項式の係数を、元のメッセージ符号に付け加えると、リード・ソロモン符号になる
- 「01.加法と乗法が定義されている」「02.演算が閉じている」「03.結合法則が成り立つ」「04.単位元がある」「05.逆元がある」「06.可換である」の6個のルールを満たす集合を「体」と呼ぶ
- 「体」であれば、その集合はここで解説している符号化やエラー訂正の理論がそのまま適用できる
- QRコードは8桁の多項式(\(ax^7+bx^6+cx^5+dx^4+ex^3+fx^2+gx+h\)を要素とする「体」を使ってリード・ソロモン符号の計算をする
リード・ソロモンの計算に多項式の「体」をどうやって使うの？
では、リード・ソロモンの計算に具体的にどのように使うかをみてみましょう。まず、数字をすべて\(a_7x^7+a_6x^6+a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x^1+a_0x^0\)という形式で表すことにします。ただし、ここで「\(x\)」は何でもよい数字(だから「\(x\)」としているのです・・・)なので、「\(\alpha\)」を使うことにします。
そして、この「\(\alpha\)」は「\(x^8+x^4+x^3+x^2+1=0\)の解の1つ」とします。
つまり、「\(\alpha^8+\alpha^4+\alpha^3+\alpha^2+1=0\)」です。これは、「\(\alpha^8=\alpha^4+\alpha^3+\alpha^2+1\)」と書くこともできます。
えっ？マイナスを忘れてるって？
いえいえ。今考えている体の世界では、係数は「2で割った余り」にするのでした。「-1」を2で割った余りは「1」になります。そのため、この世界では「\(-1=1\)」なのです。
さて、\(\alpha\)を使うと、この体の要素は次のような式でかけることとなります。
$$ a_7\alpha^7+a_6\alpha^6+a_5\alpha^5+a_4\alpha^4+a_3\alpha^3+a_2\alpha^2+a_1\alpha^1+a_0\alpha^0 $$ このとき、上記の係数だけ抜き出した表現をすると、\((a_7,a_6,a_5,a_4,a_3,a_2,a_1,a_0)\)となります(このことを「2進数表現」と呼びましょう)。
ちなみに、この2進数を10進数に変換したものを「10進数表現」とここでは呼びましょう。
このとき、\(\alpha^0,\alpha^1,\alpha^2, \cdots ,alpha^254,\alpha^256\)がどう表現されるか見てみましょう。
| \(\alpha\) | 2進数表現 | 多項式表現 | 10進数表現 |
|---|---|---|---|
| \(0\) | \((0,0,0,0,0,0,0,0)\) | 0 | 0 |
| \(\alpha^0\) | \((0,0,0,0,0,0,0,1)\) | \(\alpha^0\) | 1 |
| \(\alpha^1\) | \((0,0,0,0,0,0,1,0)\) | \(\alpha^1\) | 2 |
| \(\alpha^2\) | \((0,0,0,0,0,1,0,0)\) | \(\alpha^2\) | 4 |
| \(\alpha^3\) | \((0,0,0,0,1,0,0,0)\) | \(\alpha^3\) | 8 |
| \(\alpha^4\) | \((0,0,0,1,0,0,0,0)\) | \(\alpha^4\) | 16 |
| \(\alpha^5\) | \((0,0,1,0,0,0,0,0)\) | \(\alpha^5\) | 32 |
| \(\alpha^6\) | \((0,1,0,0,0,0,0,0)\) | \(\alpha^6\) | 64 |
| \(\alpha^7\) | \((1,0,0,0,0,0,0,0)\) | \(\alpha^7\) | 128 |
| \(\alpha^8\) | \((0,0,0,1,1,1,0,1)\) | \(\alpha^4+\alpha^3+\alpha^2+1\) | 29 |
| \(\alpha^9\) | \((0,0,1,1,1,0,1,0)\) | \(\alpha^5+\alpha^4+\alpha^3+\alpha\) | 58 |
| \(\alpha^{10}\) | \((0,1,1,1,0,1,0,0)\) | \(\alpha^6+\alpha^5+\alpha^4+\alpha^2\) | 116 |
| \(\alpha^{11}\) | \((1,1,1,0,1,0,0,0)\) | \(\alpha^7+\alpha^6+\alpha^5+\alpha^3\) | 232 |
| \(\alpha^{12}\) | \((1,1,0,0,1,1,0,1)\) | \(\alpha^7+\alpha^6+\alpha^3+\alpha^2+1\) | 205 |
\(\alpha\)の列は、単純に\(0,\alpha^0,\alpha^1,\alpha^2,\cdots,\alpha^253,\alpha^254\)となるだけです。
2進数表現の列は、多項式表現の部分の係数を抜き出しているだけです。そして、10進数表現の列は、2進数表現を10進数の数字に置き換えただけです。ここでは0〜255までの数字がでてきます。
(実は、0〜255までの数字がでてくるかどうかは、別途証明しないとわからないのですが、雰囲気的にでてくるものだと思ってください)
多項式表現の列はちょっと難しいです。ポイントは、次の3つです。
01.\(\alpha\)を一つ前の行の多項式表現の部分に単純に掛け算する
02.もし、\(\alpha^8\)がでてきたら、\(\alpha^4+\alpha^3+\alpha^2+1\)で置き換える(\(\alpha^8=\alpha^4+\alpha^3+\alpha^2+1\)でしたね)
03.各係数を「2」で割り算した余りに置き換えます(今回の体で導入している特殊な足し算のルールですね。係数が「2」になっている項は係数が「0」に置き換わるので、なくなります)
こうやって、各行を計算することができます。そして、この数式のすごいところは\(\alpha^{254}=\alpha^7+\alpha^3+\alpha^2+\alpha^1\)となるところです。
えっ？何がすごいかって？\(\alpha^{254}\)に、\(\alpha\)を掛け算して、\(\alpha^{255}\)を計算してみてください。
$$ \alpha^{255}=\alpha^{254} \times \alpha=\alpha^8+\alpha^4+\alpha^3+\alpha^2 $$ となりますが、\(\alpha^8=\alpha^4+\alpha^3+\alpha^2+1\)なので、上の式は次のようになります。
$$ \alpha^{255}=(\alpha^4+\alpha^3+\alpha^2+1)+\alpha^4+\alpha^3+\alpha^2=2\alpha^4+2\alpha^3+2\alpha^2+1 $$ そして、各係数を2で割った余りに置き換えるので、最終的には次のようになります。
$$ \alpha^{255}=1 $$ そうなんです。この\(\alpha\)は255乗すると1に戻るんです。
だから、例えば\(\alpha^{300}\)なんてでてきても、「\(\alpha^{300}=\alpha^{255} \times \alpha^{45}=1 \times \alpha^{45}=\alpha^{45}\)」と、小さい\(\alpha\)に置き換えることができます。
そのため、大きな数字がでてこなくなるので計算がとっても簡単なんです。
QRコードで使うリード・ソロモン符号では0〜255までの数字を先ほどの表で\(\alpha\)に変換して計算します。
(しつこいですが、\(\alpha\)で計算するときの足し算と掛け算は普通のやつではなく、今回導入した特殊な足し算・掛け算をします)
この、\(\alpha\)に変換した数字や、特殊な足し算・掛け算のことを「\(2^8\)のガロア拡大体、\(GF(2^8)\)」と呼びます。
GFは「Galois Field」の略です。「Galois(ガロア)」はこういう特殊な計算について研究した研究者の名前で、「Field(フィールド)」は「体」という意味です。
リード・ソロモン符号で\(2^8\)のガロア拡大体を使おう
えっ？リード・ソロモン符号の検査行列にでてくる\(\alpha\)と関係があるのか？勘が鋭いですね。リード・ソロモン符号の検査行列は次のようなものでしたね。$$ \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 & 1 & 1 \\ 1 & \alpha & \alpha^2 & \cdots & \alpha^(2t-3) & \alpha^(2t-2) & \alpha^(2t-1) \\ 1 & \alpha^2 & \alpha^4 & \cdots & \alpha^{2(2t-3)} & \alpha^{2(2t-2)} & \alpha^{2(2t-1)} \\ \vdots & \vdots & \vdots & \cdots & \vdots & \vdots & \vdots \\ 1 & \alpha^{(n-3)} & \alpha^{2(n-3)} & \cdots & \alpha^{(n-3)(2t-3)} & \alpha^{(n-3)(2t-2)} & \alpha^{(n-3)(2t-1)} \\ 1 & \alpha^{(n-2)} & \alpha^{2(n-2)} & \cdots & \alpha^{(n-2)(2t-3)} & \alpha^{(n-2)(2t-2)} & \alpha^{(n-2)(2t-1)} \\ 1 & \alpha^{(n-1)} & \alpha^{2(n-1)} & \cdots & \alpha^{(n-1)(2t-3)} & \alpha^{(n-1)(2t-2)} & \alpha^{(n-1)(2t-1)} \\ \end{pmatrix} $$ リード・ソロモン符号を計算するときは全て先ほどの「\(GF(2^8)\)」を使って計算するので、ここででてくる\(\alpha\)は「\(GF(2^8)\)」の要素として扱います。
もし、\(n=50,t=20\)となったら、上の行列の右下の要素\(\alpha^{(n-1)(2t-1)}\)は\(\alpha^{49 \times 39}=\alpha^{1911}\)となります。
これは、普通だったらとっても大きな数になりそうですね・・・。でも\(alpha^{255}=1\)という性質をつかうと、これを簡単にできます。
\(\alpha^{1911}=(\alpha^{255})^7 \times \alpha^{126}=1^7 \times \alpha^{126}=\alpha^{126}\)となりますよね。
このガロア拡大体、\(GF(2^8\)を使っていると、どんなに大きな数字でも\(alpha^{255}\)より小さくすることができるという便利な特徴を持っているんです。(だから、リード・ソロモン符号に使われることになったのですが・・・)
さて、元のメッセージからリード・ソロモン符号を計算するときに、\((z-\alpha^0)(z-\alpha^1)(z-\alpha^2) \cdots (z-\alpha^{(2t-3)})(z-\alpha^{(2t-2)})(z-\alpha^{(2t-1)})\)で割り算しなければいけませんでした。
ここででてくる\(\alpha\)も「\(GF(2^8)\)」のメンバーとして扱います。
例として「\(t=5\)」のときの場合をみてみましょう。「\(t=5\)」とすると、割り算をする多項式は次のようになります。
$$ (z-\alpha^0)(z-\alpha^1)(z-\alpha^2)(z-\alpha^3)(z-\alpha^4)(z-\alpha^5)(z-\alpha^6)(z-\alpha^7)(z-\alpha^8)(z-\alpha^9) $$ これを普通の計算のように展開すると次のようになります。
$$ \begin{align} z^{10} & +\\ & (-\alpha^9-\alpha^8-\alpha^7-\alpha^6-\alpha^5-\alpha^4-\alpha^3-\alpha^2-\alpha^1-1)z^9+\\ & (\alpha^{17}+\alpha^{16}+2\alpha^{15}+2\alpha^{14}+3\alpha^{13}+3\alpha^{12}+4\alpha^{11}+4\alpha^{10}+5\alpha^{9}+4\alpha^{8}+4\alpha^{7}+3\alpha^{6}+3\alpha^{5}+2\alpha^{4}+2\alpha^3+\alpha^{2}+\alpha)z^8+\\ & (-\alpha^{24}-\alpha^{23}-2\alpha^{22}-3\alpha^{21}-4\alpha^{20}-5\alpha^{19}-7\alpha^{18}-8\alpha^{17}-9\alpha^{16}-10\alpha^{15}-10\alpha^{14}-10\alpha^{13}-10\alpha^{12}-9\alpha^{11}-8\alpha^{10}-7\alpha^{9}-5\alpha^{8}-4\alpha^{7}-3\alpha^{6}-2\alpha^{5}-\alpha^{4}-\alpha^{3})z^7+\\ & (\alpha^{30}+\alpha^{29}+2\alpha^{28}+3\alpha^{27}+5 \alpha^{26}+6\alpha^{25}+9\alpha^{24}+10\alpha^{23}+13\alpha^{22}+14\alpha^{21}+16\alpha^{20}+16\alpha^{19}+18\alpha^{18}+16\alpha^{17}+16\alpha^{16}+14\alpha^{15}+13\alpha^{14}+10\alpha^{13}+9\alpha^{12}+6\alpha^{11}+5\alpha^{10}+3\alpha^{9}+2\alpha^{8}+\alpha^{7}+\alpha^{6})z^6+\\ & (-\alpha^{35}-\alpha^{34}-2\alpha^{33}-3\alpha^{32}-5\alpha^{31}-7\alpha^{30}-9\alpha^{29}-11\alpha^{28}-14\alpha^{27}-16\alpha^{26}-18\alpha^{25}-19\alpha^{24}-20\alpha^{23}-20\alpha^{22}-19\alpha^{21}-18\alpha^{20}-16\alpha^{19}-14\alpha^{18}-11\alpha^{17}-9\alpha^{16}-7\alpha^{15}-5\alpha^{14}-3\alpha^{13}-2\alpha^{12}-\alpha^{11}-\alpha^{10})z^5+\\ & (\alpha^{39}+\alpha^{38}+2\alpha^{37}+3\alpha^{36}+5\alpha^{35}+6\alpha^{34}+9\alpha^{33}+10\alpha^{32}+13\alpha^{31}+14\alpha^{30}+16\alpha^{29}+16\alpha^{28}+18\alpha^{27}+16\alpha^{26}+16\alpha^{25}+14\alpha^{24}+13\alpha^{23}+10\alpha^{22}+9\alpha^{21}+6\alpha^{20}+5\alpha^{19}+3\alpha^{18}+2\alpha^{17}+\alpha^{16}+\alpha^{15})z^4+\\ & (-\alpha^{42}-\alpha^{41}-2\alpha^{40}-3\alpha^{39}-4\alpha^{38}-5\alpha^{37}-7\alpha^{36}-8\alpha^{35}-9\alpha^{34}-10\alpha^{33}-10\alpha^{32}-10\alpha^{31}-10\alpha^{30}-9\alpha^{29}-8\alpha^{28}-7\alpha^{27}-5\alpha^{26}-4\alpha^{25}-3\alpha^{24}-2\alpha^{23}-\alpha^{22}-\alpha^{21})z^3+\\ & (\alpha^{44}+\alpha^{43}+2\alpha^{42}+2\alpha^{41}+3\alpha^{40}+3\alpha^{39}+4\alpha^{38}+4\alpha^{37}+5\alpha^{36}+4\alpha^{35}+4\alpha^{34}+3\alpha^{33}+3\alpha^{32}+2\alpha^{31}+2\alpha^{30}+\alpha^{29}+\alpha^{28})z^2+\\ & (-\alpha^{45}-\alpha^{44}-\alpha^{43}-\alpha^{42}-\alpha^{41}-\alpha^{40}-\alpha^{39}-\alpha^{38}-\alpha^{37}-\alpha^{36})z+\\ & \alpha^{45} \end{align} $$ 予想通りですが、びっくりする式になりましたね。。
もうここまでくるとどうにでもなれ！って感じですが、この式の\(\alpha\)の部分を先ほどの表に従って、多項式表現に直してみます。
例えば、\(-\alpha^9-\alpha^8-\alpha^7-\alpha^6-\alpha^5-\alpha^4-\alpha^3-\alpha^2-\alpha^1-1\)であれば、\(-1((\alpha^5+\alpha^4+\alpha^3+\alpha)+(\alpha^4+\alpha^3+\alpha^2+1)+\alpha^7+\alpha^6+\alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha^1+1\)となります。(-1を括りだしています)
これを整理すると次のようになります。
$$ \alpha^7+\alpha^6+2\alpha^5+3\alpha^4+3\alpha^3+2\alpha^2+2\alpha^1+2\alpha^0 $$ ちなみに、\(\alpha^0=1,\alpha^1=\alpha\)であることに注意してくださいね。次に、各項の係数を2で割った余りに置き換えます。
$$ -1*(\alpha^7+\alpha^6+\alpha^4+\alpha^3) $$ 最後に多項式表現を先ほどの表に従って\(\alpha\)に置き換えると、\(\alpha^{251}\)になります。
つまり、\(-\alpha^9-\alpha^8-\alpha^7-\alpha^6-\alpha^5-\alpha^4-\alpha^3-\alpha^2-\alpha^1-1=-\alpha^{251}\)となるのです。
(さらに言えば、\(-alpha^{251}\)の係数「-1」は、2で割ると余りが1になるので、\(alpha^{251}\)とかけてしまいます)
超シンプルになりましたね。こんな感じですべての係数の計算をしていくと、上の式は次のようになります。
$$ z^{10}+\alpha^{251}z^9+\alpha^{67}z^8+\alpha^{46}z^7+\alpha^{61}z^6+\alpha^{118}z^5+\alpha^{70}z^4+\alpha^{64}z^3+\alpha^{94}z^2+\alpha^{32}z^1+\alpha^{45}z^0 $$ あんなに複雑だった式が・・・とってもすっきりしました。ガロア拡大体の威力はすさまじいですね。
メッセージ多項式を上の式で割り算すれば、その余りがリード・ソロモン符号になるのでしたね。
ちなみに、割り算するときにはメッセージ多項式も\(\alpha\)に置き換えて、多項式同志の割り算しなければいけません。
「ガロア拡大体、\(GF(2^8\)」を使うと大きな数字でも簡単に計算できることがわかりました。
これで、QRコードを理解するための道具はそろいました。
ここまで、わかればQRコードを99.9%理解したことになります。
次回からは、これまで解説した内容をつかって、具体的なQRコードの作り方を解説していきます！ようやくこの連載の終わりが見えてきました・・・