QRコードを作る時に使う生成多項式g(x)の求め方
趣味でQRコードを作るプログラムを書いてみたいと思い色々調べてみた所、
こちらのサイトがとても親切に解説をされていて、解説に沿って
ひとまずQRコードを作ってみようと思い、ぺちぺちとコードを書いてたの
ですが、3ページ目に出てくるg(x)が何の事かサッパリで心が折れそうに
なりました。
なぜこのg(x)が必要なのか、といった話は数学の偉い方々の努力の結晶
なので疑問を持たない事にするとして、サイトに掲載されている表3が
28語の所までしかありません。
このままでは型番2までのQRコードしか作れないので、エラー訂正コード
を指定してg(x)を求めるプログラムを作りたいと思います。
まず、基本的なg(x)の成り立ちから調べて行きたいと思います。
こちらのpdfによると、
g1(x) = (x + 1)(x + a) g2(x) = (x + 1)(x + a)(x + a^2)
という事がわかりました。(数式の中で出てくる ^ は累乗を表しています)
※pdfではαと記述されている箇所を、文字幅の都合上aとさせて頂きます。
では、それぞれの式を展開してみましょう。まずはg1(x)からやってみます。
g1(x) = x^2 + (1 + a)x + a
となりました。先程のpdfを見ると、この次にg1(x)は
g1(x) = x^2 + a^25x + a
になるようです。・・・1 + a = a^25 !?
なんでしょうか、この式。この式を理解する為に、表現を少し変えます。
1 = a^0, a = a^1 として式を書き換えると以下のようになります。
a^0 + a^1 = a^25
すべてaで表現出来ました。
(なぜ 1 = a^0 となるかはこちらのサイトで分かりやすく解説されています)
そしてwikipediaのリード・ソロモン符号の項を見るとこうあります。
なお符号理論の基本概念として以下に登場する加算記号(+)は全て加算ではなく各ビットごとの排他的論理和を表す。
つまり、a^0 と a^1 を何かしらで xor すれば a^25 が導けるらしいです。
この計算を理解するにはこちらの表が大変参考になります。
a^0 と a^1、そして a^25 のベクトル表現を並べてみます。
a^0 : 00000001 a^1 : 00000010 a^25 : 00000011
見事にxorになっていますね!ちなみにこちらのベクトル表現は
そのままこちらの表の整数部分に対応していますので、
プログラムで扱う際は、指数部をキーにした配列として定義しておくと楽そうです。
計算ロジックとしては、それぞれの指数から整数表現を導き、xorを行います。
xorを行った結果から指数表現を逆引した結果が、欲しかった指数となります。
先の例でいくと、指数表現の0から整数表現の1を求め、指数表現の1から整数表現の2を
求めます。1 xor 2 の結果は 3 ですので、整数表現の3を探します。結果は25です。
この調子でドンドン式を展開していってみましょう。
g2(x) = (x + 1)(x + a)(x + a^2)
前半部分は既に展開済みですので
g2(x) = (x^2 + a^25x + a)(x + a^2) = x^3 + (a^25 + a^2)x^2 + (a^27 + a^1)x + a^3
a^25 + a^2 の部分を先程と同様に xor をします。
a^25 : 00000011 a^2 : 00000100
結果は 00000111 つまり、7になるので整数の7を指数に戻します。
整数の7は指数でいう198です。
a^27 + a^1 も同様に計算すると199が求まり、展開した結果は
g2(x) = x^3 + a^198x^2 + a^199x + a^3
となりました。
計算の過程を省きますが、同様にg3(x)を計算すると以下のようになります。
g3x(x) = x^4 + a^75x^3 + a^249x^2 + a^78x + a^6
理解度を深める為にも、紙に書いて計算してみる事をお勧めします!
展開方法が分かればこっちのものですので、後はロジックをプログラムに
落とし込むだけです。
ロジックに落とすには扱う数字や概念を極力シンプルにした方が楽なので、
これまでの展開結果をジーッと見つめて、楽出来そうな所を探します。
分かりやすくする為に、g3(x)を1 = a^0 = x^0 を使って表現してみます。
g3(x) = a^0x^4 + a^75x^3 + a^249x^2 + a^78x^1 + a^6x^0
そしてもう一度ジーッと見てみます。何かに気付きませんか?
xの係数に着目してみてください。左から4,3,2,1,0と下がっていっています。
g2(x)もよく見ると、3,2,1,0と下がっていっています。
なんとなく、配列に出来そうな気がしませんか?
そしてxを配列のインデックス代わりに出来ると式に登場するのはaだけに
なりますので、いっそのことaも取っ払っちゃいましょう。そうすると
g3(x) = (0, 75, 249, 78, 6)
という表現になります。配列のインデックスとxの係数が逆になってますが、
全く使う事はないので問題ありません。見た時の分かりやすさ優先です。
そして展開ロジックですが、こちらもイメージしやすくする為に展開式を
別の表現で書き直してみます。手始めに一番単純なg1(x)からやってみます。
分かりやすくする為に、g1(x)も 1 = a^0 = x^0 を使った表現にします。
g1(x) = (a^0x^1 + a^0x^0)(a^0x^1 + a^1x^0) = a^0x^2 + (a^0 + a^1)x^1 + a^1x^0
さらに、前述の配列表現で式を表現してみます。
x + 1 = a^0x^1 + a^0x^0 = (0, 0) x + a = a^0x^1 + a^1x^0 = (0, 1) と書けるので g1(x) = (0, 0)(0, 1)
となります。各配列の数字はaの乗数となります。
展開式を図で表現すると以下のようになります。
0 | 0 | |
---|---|---|
0 | 0 | 0 |
1 | 1 | 1 |
各マスの計算結果は単なる足し算です。(累乗のかけ算なので)
結果に下ろす時は下の段を一つずらして
0 | 0 | |
---|---|---|
1 | 1 | |
0 | 0 + 1 | 1 |
このようになります。
(0 + 1)は前述の整数に戻して排他的論理和を行ってまた指数に戻して25にします。
まとめると
g1(x) = (0, 0)(0, 1) = (0, 25, 1)
となります。同様にg2(x)を計算してみます。
g2(x) = (x + 1)(x + a^1)(x + a^2) (配列表現) = (0, 0)(0, 1)(0, 2) = (0, 25, 1)(0, 2)
となるので、展開図を表で表すと
0 | 25 | 1 | |
---|---|---|---|
0 | 0 | 25 | 1 |
2 | 2 | 27 | 3 |
となります。一段ずらして結果を求めます。
0 | 25 | 1 | |
---|---|---|---|
2 | 27 | 3 | |
0 | 25 + 2 | 1 + 27 | 3 |
25 +2と1 + 27を計算した結果
g2(x) = (0, 0)(0, 1)(0, 2) = (0, 198, 199, 3)
となります。
最後に、上記のロジックをphpのコードにしたのがこちらです。
<?php $words = 2; // 求めたいエラー訂正コード語数 $gx_array = array(0, 0); for($i = 1;$i < $words;$i++) { $n_array = array(0, $i); $gx_array = calc_gx($gx_array, $n_array); } print_r($gx_array); function calc_gx($base_array, $n_array) { $ret = array(); for($i = 0;$i < count($n_array);$i++) { for($j = 0;$j < count($base_array);$j++) { // 係数部分のかけ算は足し算になる $val = $n_array[$i] + $base_array[$j]; if ($val > 255) { $val -= 255; } if (array_key_exists($i + $j, $ret)) { $ret[$i + $j] = calc_sum($ret[$i + $j], $val); } else { $ret[$i + $j] = $val; } } } return $ret; } function calc_sum($i, $j) { $alpha_table = array( 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142, 1, ); $sum = $alpha_table[$i] ^ $alpha_table[$j]; if ($sum > 255) { $sum -= 255; } return array_search($sum, $alpha_table); } ?>
実際に使う場合は毎度計算する必要もないので、一度書き出してしまえば楽でしょう。