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);
}

?>

実際に使う場合は毎度計算する必要もないので、一度書き出してしまえば楽でしょう。

FuelPHPでURLからindex.phpを消したい

FuelPHPをドキュメント等を参考にして環境を整えると、URLの構成が

http://localhost/PROJECT_NAME/public/index.php/welcome/hello

な感じで、どのページに行くにしてもindex.phpが入っててちょっち邪魔。
これを

http://localhost/PROJECT_NAME/welcome/hello

にしたい。

FuelPHPの導入解説をされてるサイトや本を見ると.htaccessによる方法が
よく書かれているけど、見てみるとURLにpublicディレクトリが入っている。

http://localhost/PROJECT_NAME/public/index.php/welcome/hellohttp://localhost/PROJECT_NAME/public/welcome/hello

こんな感じ。確かにindex.phpは無くなったけれども・・・
できればpublicも取っちゃいたいよね。
恐らくこの場合ってDocumentRootが/var/www/htmlになってるとすると、

/var/www/html
      └PROJECT_NAME
       ├docs
       ├fuel
       └public

こんな感じの配置になっていると思う。(デフォルトのhttpd.confで行けば)

今回やりたいのは

http://localhost/PROJECT_NAME/welcome/hello

でアクセス出来るようにする事なので、自分が配置した構成は

/var/www/html
      └PROJECT_NAME
       ├develop(開発環境)
       │├docs
       │├fuel
       │└public
       └release(本番環境)
        ├docs
        ├fuel
        └public

こんな感じ。FuelPHPの設定で本番環境と開発環境を切り替える事も出来るけど、
他の都合で使い分けたい事もあるので別ディレクトリとして切る事にした。
http://localhost/PROJECT_NAME
で /var/www/html/PROJECT_NAME/release/public を見に行くにはhttpd.confに

Alias /PROJECT_NAME /var/www/html/PROJECT_NAME/release/public

を追加(場所はDocumentRootの設定下ぐらいが把握しやすくていいと思う)して、
/var/www/html/PROJECT_NAME/release/public のディレクティブも追加してあげる。
その際、後述する.htaccessの設定を有効にする為にAllowOverrideはAllにする事。

次に release/public/.htaccess を編集する。
.htaccessはoil create時に自動で作成されているはずなので無かった場合は
oil create のどこかでエラーが起きていた可能性がある。
追加するのは次の一行で、場所は既にあるRewriteCondの下あたりでOK。

RewriteRule ^(.*)$ /PROJECT_NAME/index.php?/$1 [L]

本などに載っている内容だと /PROJECT_NAME/ に相当する箇所が無いと思うけど
これは今回publicを省略する構成で行ったからなので、最初に紹介したデフォルトの
DocumentRoot構成の場合は

RewriteRule ^(.*)$ index.php?/$1 [L]

で同様にindex.phpが省略出来ます。

FuelPHPのoil createでエラーが出る件

さくらのVPSでFuelPHPを動かそうと思って

oil create PROJECT_NAME

とコマンドを打つと

Submodule path 'fuel/packages/parser': checked out '634204f87047fdb2d5957b74a7c24a4faea33cc2' 
PHP Fatal error: Exception thrown without a stack frame in Unknown on line 0 

Fatal error: Exception thrown without a stack frame in Unknown on line 0

とエラーが出てしまう。
同じ事をAmazonのEC2でやると

Submodule path 'fuel/packages/parser': checked out '634204f87047fdb2d5957b74a7c24a4faea33cc2' 
Made writable: /APP_PATH/fuel/app/cache 
Made writable: /APP_PATH/fuel/app/logs 
Made writable: /APP_PATH/fuel/app/tmp 
Made writable: /APP_PATH/fuel/app/config 

こんな感じで成功する。どうも最後の権限変更で落ちてるっぽい。
/usr/bin/oil
の中身を見てどんな処理が行われていて、どこで落ちているかを追いかけて行くと
fuel/core/classes/fuel.php

static::$timezone = \Config::get('default_timezone') ?: date_default_timezone_get();

で落ちているみたい。
Config::get('default_timezone') は fuel/app/config/config.php
default_timezone の値を見るのだけど、確認してみたら空だった。
なのでphpのdate_default_timezone_get()を実行するのだけれど、ここで落ちている。
date_default_timezone_get() は php.ini の date.timezone を見るので
/etc/php.ini を見てみたら、見事に空だった。そこで /etc/php.ini に

date.timezone = "Asia/Tokyo"

を追加してあげるとエラーが起きずに oil create が完了した。
EC2はパッケージのインストール時に気を利かせて色々設定してくれるので、
php.iniのtimezoneも設定してくれててエラーが起きなかったみたい。
最初に config.php を見てるので fuel/app/config/config.php

'default_timezone'   => 'Asia/Tokyo'

を記述してもエラーは起きなくなるけれど、fuel/app/config/config.php
oil create をして作成されるファイルなので、新しいプロジェクトを作る度に
config.php の編集とchmodしないといけないのでちょっち面倒。

phpインストールしたらtimezoneの設定ぐらいするよねー
と言ってしまえばおしまいだけどね!