yamicha.com's Blog - Presented by yamicha.com
Blog yamicha.com's Blog - 2017/09 の記事
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30]

yamicha.com's Blog
 諸事情により、現在更新休止中。ご了承ください。もし今後ブログを再開することがあるとすれば、その際にはこのブログスクリプトではなく、新しく開発したものによるかもしれません。
 当ブログ管理者についてはこちらをご参照。
開発魔法(737)
社会問題(733)
お知らせ(11)
質問・バトン回答(15)
ゲスト出演(8)
経済・知的財産(150)
ゲーム開発(182)
[Ada] 勝手に補足
- Note
- 金配りの次の一手


- Endless Ultimate Diary
- 銃世界

漢字バトン
- うるる雑記帳
- 漢字接力棒

ツキアイゲノムバトン
- ブログ@うにうに画像倉庫
- あぶ内閣

縺イ縺セ縺、縺カ縺励ヰ繝医Φ
- 月夜のボヤキ
- 騎士サーラバトン
パスワードを使う
名無し (2012/02/27)


開発者解放裁判
yamicha.com (2010/03/14)
Winnyに関しては、私も「純白」とまでは考えておりませんし、使用し..

開発者解放裁判
通りすがり (2010/03/08)
winnyに関しては「ダウンロードソフト板」なんてところを拠点に開発..

新型インフルエンザの恐怖
いげ太 (2009/11/03)
> C#などの「int Some(int , int)」は、F#では「(int * int) ->..

時効に関する思考
yamicha.com (2009/08/31)
>いげ太さんコメントありがとうございます。手元にドキュメントが少..
Homepage
Blog Top
Normal View
List View
Search
Calendar
Comment List
Trackback List
Blog RSS
Send Trackback
Phone Mode
Administrator
yamicha.com
Blog
るううるる。
Source
法令データ提供システム
FindLaw
Development
Java2 Platform SE 6
Java EE 6 API
MySQL Developer Zone
PHP Reference
MSDN Library
Ada Reference Manual
Objective Caml
Python Documentation
Erlang
Prolog Documents
日本中の実装者の中で最も数学能力が低い人間によるQRコードRS符号実装(2)
2009/03/05(Thu)20:54:08
日本中の実装者の中で最も数学能力が低い人間によるQRコードRS符号実装(2)

 ガロア拡大体をビットで表現する方法が分かったところで、琉球大学のサイトに置かれた表を見てみます。この琉球大学のサイトにあるGF(24)の指数表のラベル、2008年3月現在では少し間違いがありまして、「a^3」「a^2」「a^2」「a^0」ではなく「a^3」「a^2」「a^1」「a^0」が正解です。
 例によって意味不明な方程式だか因数分解だかが書かれていますが、このようなものは読めないのですから存在しないのと同じです。ひとまず全部無視して、これを除いた表を以下に示します。
a^3 a^2 a^1 a^0 2進値 2進値を整数に直したもの
a^-無限大 0 0 0 0 0000 0
a^0 0 0 0 1 0001 1
a^1 0 0 1 0 0010 2
a^2 0 1 0 0 0100 4
a^3 1 0 0 0 1000 8
a^4 0 0 1 1 0011 3
a^5 0 1 1 0 0110 6
a^6 1 1 0 0 1100 12
a^7 1 0 1 1 1011 11
a^8 0 1 0 1 0101 5
a^9 1 0 1 0 1010 10
a^10 0 1 1 1 0111 7
a^11 1 1 1 0 1110 14
a^12 1 1 1 1 1111 15
a^13 1 1 0 1 1101 13
a^14 1 0 0 1 1001 9
a^15 0 0 0 1 0001 1

 非常に不思議な表です。
 表の見方ですが、これは「aを何乗したらその値になるか」の対応表です。仮に「a^2」の値を調べたければ、「値」の行の「a^2」の部分を見てください。
 最初の「aの-無限大乗」は特殊な例ですので、特に考えなくても構いません。ここは飛ばして、次からの行を見てください。

補足事項
 別に知らなくても全く問題はありませんが、知的欲求が満たされない方のために、なぜ「a^-無限大」が「0」になるかを解説しておきます。
 ここに0と1以外の任意の数である「x」があります。xを何乗すれば0になるでしょうか。仮にxを2として考えましょう。指数を増やしても2^2 = 4、2^3 = 8、2^4 = 16...と値が増えてしまいますので、指数を減らさなくてはなりません。2^1 = 2、2^0 = 1、2^-1 = 0.5、2^-2 = 0.25、2^-3 = 0.125...。このような具合に、指数のマイナスを増やすたびに値は小さくなるものの、指数のマイナスが有限の値である限り0にはなりません。したがって、xを累乗によって0にするには、マイナスの無限大乗を行う必要があるのです。
 これはaの累乗でも同じです。a^3もa^2もa^1もa^0も何もない、つまりは0の状態にするには、マイナス無限大を累乗するよりありません。

 まずa^0からa^3までは見たままでしょう。「a^1」は「a^1が1個あって、他のものがない」状態で、「a^3」は「a^3が1個あって、他のものがない」状態です。これだけなら何の問題もありません。
 問題はa^4以降です。常識的に考えて、「a^4」を「a^0 .. a^3」の組み合わせで表せるはずがありません。ところが、謎の変数「a」はまさに魔法のような変数です。何と「a^4」は「a^1 + a^0」に変化することができるのです。なぜそうなるのかは、まだ考えない方が無難です。今から正体を暴こうとしたところで、意味が分からなくなってしまうのがオチです。今までにRS符号の実装を投げた人のうち、9割はこの「a」の意味不明な変化についていけなかったためでは、とも推測できるほどです。
 ともかく、この表からは次のことが分かります。

1.aの累乗指数が1つ増えるたびに、その構成要素となるa^0 .. a^3の指数も1つずつ増加している。これは先に解説した通りだが、例えば「a^4 = a^1 + a^0」なのが、指数が増えると「a^5 = a^2 + a^1」である。
2.指数がa^4に達したところで、よく分からない「魔法の変化」が発生する。GF(2^4)の場合は「a^4」がなぜか「a^1 + a^0」に変化してしまう。
3.指数が0から14(2^4 - 2)まではすべて違うパターンが現れている。全部で15(2^4 - 1)パターン。
4.指数が15(2^4 - 1)になったところで、値はa^0の場合と等しくなる。

 まずは1番目の特徴について。
 これの理由は先ほど解説した通りです。しかし、これが実は重要な意味を持っています。例えば「a^4 = a^1 + a^0」をビットにすると、a^3とa^2が0個、a^1とa^0が1個ですので「0011」です。これがa^5になると、「a^5 = a^2 + a^1」で「0110」です。さらにa^6になると、「a^6 = a^3 + a^2」ですから、「1100」です。つまり、指数が増えるたびにビットが左にずれているのです(なお、a^7になると「a^7 = a^4 + a^3」となり、「a^4」が魔法の変化を起こしてしまいますので、単にビットを左にずらすだけでは計算できなくなります)。
 すなわち、足し算がXORで計算できるばかりか、指数増加が左シフト演算子で計算できるのです。ビットが左にシフトすると、10進数では値が倍になりますので(例えば0011は10進数にすると3、0110は6、1100は12)、上記の表でも10進表記の値が次々と倍になっています。

 2番目以降の特徴は、ガロア拡大体にとって非常に重要なところです。ここでGF(2^8)のリストも示しておきます。これを見て共通項を探してみてください。左側のリストが先のリストに相当します(右側はその逆引き用です)。
 GF(2^4)の特徴を踏まえて見てみると、次のことが分かるのではないでしょうか。

1.aの指数が1つ増えるたびに、その構成要素となるa^0 .. a^7の指数も1つずつ増加している。
2.指数がa^8に達したところで、よく分からない変化が発生する。
3.指数が0から254(2^8 - 2)まではすべて違う値が現れている。全部で255(2^8 - 1)パターン。
4.指数が255(2^8 - 1)になったところで、得られる値は指数が0の場合と等しくなる。

 何と、全く同じ特徴を持っています。これこそが「ガロア拡大体」の特徴なのです。
 しかし、分からないのがその先です。GF(2^4)ではa^4が魔法の変化を起こしていましたが、こちらではa^8が不思議な変化をしているのです。この特徴もGF(2^4)の場合と同じです。この変化は一体何なのでしょうか。
 GF(2^4)にせよ、GF(2^8)にせよ、まずは魔法の変化について知る必要がありそうです。この魔法の変化については、先の琉球大学のサイトにもそれらしい記述がありました。
 早速、琉球大学サイトのGF(2^4)の記述を読んでみると、

p(a) = a^4 + a + 1 = 0

 このような意味不明な式が書いてあります。また、指数「4」の部分の式を見てみると、

a^4 = 1 + a

 こう書いてあります。何が何だか分かりませんが、要するに「a^4 は 1 + a に等しい」と書いてあるようです。なお、「1 + a」は「a^0 + a^1」と全く同じです。つまりは「a^4 = a^1 + a^0」と書いてあるのです。
 それでは、なぜ「a^4 = a^1 + a^0」なのでしょうか。ここまでは「魔法の変化」で済ませてきましたが、さすがにそろそろ魔法の理屈を解き明かしておきたいものです。
 ここで、先ほどGF(2^4)リストを見た際に分かったことを再掲しておきます。

1.aの累乗指数が1つ増えるたびに、その構成要素となるa^0 .. a^3の指数も1つずつ増加している。
2.指数がa^4に達したところで、よく分からない「魔法の変化」が発生する。GF(2^4)の場合は「a^4」がなぜか「a^1 + a^0」に変化してしまう。
3.指数が0から14(2^4 - 2)まではすべて違うパターンが現れている。全部で15(2^4 - 1)パターン。
4.指数が15(2^4 - 1)になったところで、値はa^0の場合と等しくなる。

 実はこの3と4こそが「ガロア拡大体」が満たさなくてはならない要件なのです。つまり、ガロア拡大体は「この2つの条件を満たす」ために「一見すると意味不明で不思議な変化をする、aという魔法の変数を導入している」のです。「a」の不思議な変化によって帳尻を合わせているともいえるでしょう。
 その変化こそが、先ほど引用した以下の式なのです。

a^4 = 1 + a

 あるいは、このように言い換える方が分かりやすいかもしれません。

a^4 = a^1 + a^0

 なぜこのような式になるのかは、ここでは考える必要はありません。円周率として3.14159...、eとして2.71828...が求められているように、先人たちが苦労してこの式を導出してくださっているのですから、我々後進の人間はそれをありがたく利用させていただきましょう。
 これによって、「a^4」は「a^1 + a^0」に変化できます。「a^5」は指数を増やして「a^2 + a^1」になりますし、「a^6」は同じく指数が増えて「a^3 + a^2」です。
 「a^7」は「a^4 + a^3」ですが、a^4は変化が必要なので「a^1 + a^0」に変えて「a^3 + a^1 + a^0」になります。
 したがって、以下のようなリストが作成できます。
式	a^3	a^2	a^1	a^0	2進数	10進数
a^3	1	0	0	0	1000	8
a^4	0	0	1	1	0011	3
a^5	0	1	1	0	0110	6
a^6	1	1	0	0	1100	12
a^7	1	0	1	1	1011	11
 かなり難易度が上がってしまいましたが、つまりはこれが「ガロア拡大体」なのです。
 次にGF(2^8)の場合を考えてみます。GF(2^8)といえばQRコードのエラー訂正で使用されているものですので、こちらが本番です。まずはリストを見てみましょう。
指数	2進	10進
a^0	00000001	1
a^1	00000010	2
a^2	00000100	4
a^3	00001000	8
a^4	00010000	16
a^5	00100000	32
a^6	01000000	64
a^7	10000000	128
 8ビットになっている以外は、基本的にGF(2^4)と変わりません。
 問題は「a^8が何に変化するか」です。これもまた先人たちが導出してくださっているので、我々はその成果の恩恵にあずかることができます。
 久留米工業大学のPDFによれば、それは次のような式なのだそうです。

a^8 = a^4 + a^3 + a^2 + 1

 また、QRコードの仕様書にはこうあります。

 QRコードの多項式は、2を法とする算術及び100011101を法とする算術(体の原始多項式x8+x4+x3+x2+1の係数を示す100011101をもつ28のガロア体)を用いて計算する。

 異口同音に同じことが述べられています。1は「a^0」ですから、これは「a^4 + a^3 + a^2 + a^0」に置き換えられます。2進法にすれば「00011101」です。つまり、a^8はこれに変化させれば良いのです。なぜそうなるのかは、これもまた特に考える必要はありません。円周率のようなものです。

補足事項
 GF(2^4)におけるa^4が0011に、GF(2^8)におけるa^8が00011101に変化するのは「円周率のようなもの」と述べましたが、なぜそうなるのでしょうか。そのような疑問が出てくるのは当然ともいえます。
 しかし、私はこれをあえて省略するものとしました。なぜなら、世にある多くのサイトでは、突然

p(a) = 0
ただし、p(x)はGF(2)上の元{0, 1}を係数にもつw次の既約多項式

 なる何が言いたいのか分からない定義によって変数aが定められ、しかも直後には

a^4 = a^1 + 1(GF(2^4)の場合)
a^8 = a^4 + a^3 + a^2 + 1(GF(2^8)の場合)

 などといった意味不明な式が何の脈略もなく登場し、なぜそうなるのかも示されないままにこの式に基づく因数分解なるものが行われているのです。このような意味不明な記述が理解できる人間は、新人類になれるのではないでしょうか。
 aとは何か、pとは何か、なぜa^4はa^1 + 1なのか、といった問題は、別に理解しなくてもプログラムは書けますが、このままでは非常に気持ちが悪いので、補足として触れておきます。なお、私もこれらの問題に確固とした答えを見つけたわけではなく、開発中になんとなく浮かんだものを文章化しているだけですので、正しいかどうかの保証はしません。

1.aとは何か
 今まで散々「魔法の変数」として扱ってきたaですが、琉球大学のサイトではaについて次のように定義されています。

新しくaという元を考え、p(a) = 0と仮定します。
既約多項式p(x)をうまく選べば、

a0,a1,a2,a3,...,a2w-2

なる要素はすべて異なり、

a2w-1 = 1

を成立させることができる。

 上記の文章を要約すると、以下のようになります。例えばGF(2^4)の場合であれば、

1.a^0、a^1...a^14までの15パターンの値がすべて異なっていること(GF(2^4)はa^3とa^2とa^1とa^0がそれぞれ「ある」か「ない」かの組み合わせであるので、組み合わせ自体が16パターンしかない。そのうち「a^-無限大 = 0000」を除く15パターンが1つずつ全部登場しなければならない)。
2.しかも「a^15 = a^0 = 1」となること。
3.a^4が、(1)と(2)の条件を両方満たすような値(この場合はa^1 + 1)に変化すること。(1)と(2)の条件はガロア拡大体が満たさなければならない条件です。逆に言えば、ガロア拡大体にはこの「a」が絶対に必要です。

 これが「a」の正体です。そのような数字は実在しそうにありませんが、久留米工業大学のPDFによると「虚数のようなもの」だそうです。つまり、この「a」とやらは想像上の産物であるといえます。すなわち、aとは「a^4になったらa^1 + 1に変化する」という空想上の変数なのです。
 何のことはない、aは本当に「魔法の変数」でした、という単純なオチです。

2.p(x)とは何か
 こちらも琉球大学からの引用ですが、

2^w(2のw乗)の要素(元)をもつ体は2^2のガロア拡大体と呼び、GF(2^w)と表します。
1.GF(2)上の元{0, 1}を係数にもつw次の既約多項式p(x)を考える。
2.新しくaという元を考え、p(a)=0と仮定します。

 これはいかなる意味でしょうか。
 まず(1)、このように説明されると非常にややこしいのですが、つまり「p(x)」とは以下のような式であると考えてください。ただし、r0 .. rwは2のガロア体で、それぞれ0または1の値を取ります。「x」は何らかの引数です。

p(x) = x^0r0 + x^1r1 + x^2r2 + ... + x^wrw

 仮にGF(2^4)であれば、以下のような式となります。

p(x) = x^0r0 + x^1r1 + x^2r2 + x^3r3 + x^4r4

 次に(2)です。「p(a) = 0」が成り立つと「仮定」するのだそうです。あくまで仮定ですから、何をどう考えても構いません。「もしもピアノが弾けたなら」と演奏できる場面を想像してみたり、「自分が家を建てたなら」と暖炉を作ったりするところを妄想したり、「ガンダーラに行ってみたら実はディストピアであった」と空想してみたりするのと、考え方は全く同じです。
 さて、r0 .. r4は2のガロア体なのですから、0か1のいずれかの数字のみが格納でき、「1 + 1 = 0」が成り立ちます。したがって、例えば「a + a = 1a + 1a = 0a = 0」(数字部分が2のガロア体であるので、「1 + 1 = 0」。つまり「ある + ある = なし」)が成り立ちますし、「a^2 + a^2 = 0」もまた真です。「a^0 + a^1 + a^2 + a^3 + a^0 + a^1 + a^2 + a^3 = 0」のような長い式も成り立ちます。
 これを踏まえて、r0 .. r4にそれぞれ0か1の好きな値を格納し、それで以下の式を成り立たせることを考えてみてください。ただし「r0 .. r4をすべて0にする」のは、「0a^0 + 0a^1 + 0a^2 + 0a^3 + 0a^4」となってしまい、式が消えてなくなってしまいますので、反則です。

p(a) = a^0r0 + a^1r1 + a^2r2 + a^3r3 + a^4r4 = 0

 現実の値にこれが成り立つものはなさそうです。ただし、「a」は空想上の魔法の変数ですので、そのようなものがあると「仮定」することができます。誰しも1度は「私が寝ている間に、この難問を小人さんたちが勝手にやってくれていたら」などといった想像をした経験があるはずですが、これと同じく想像上の話です。
 ひとまず、これを単に成立させるだけなら簡単です。例えば「a^2 = a」(「a^2」は「a」と等しい)と仮定すれば、「a + a^2 = a + a = 0」が成り立ちます。「a^4 = a^2 + a^3」と仮定すれば、「a^4 + a^2 + a^3 = a^2 + a^3 + a^2 + a^3 = 0」が成り立ちます。GF(2^4)における「正解」の式である「a^4 = a^0 + a^1」にしても、これらの仮定と何ら変わる点はありません。こちらも「a^4 + a^0 + a^1 = a^0 + a^1 + a^0 + a^1 = 0」が成り立ちます。
 ただし、ガロア拡大体の条件を満たせるのはこの式だけです。他の式を使っても、どこかで条件に反してしまいます。すなわち、a^0からa^14の間に同じものが複数出てきてしまったり、a^15 = a^0にならなかったりします。

3.なぜa^4はa^1 + 1なのか
 これは非常に気になるところです。いかなるサイトであっても、いきなり「a^4 = a^1 + 1なので」と何の脈略もなく定義され、それを次から次へと使用されるのですから、たまったものではありません。
 それでは、なぜa^4はa^1 + 1なのでしょうか。琉球大学の先ほどの引用を再び確かめてみましょう。

新しくaという元を考え、p(a) = 0と仮定します。
既約多項式p(x)をうまく選べば、(ガロア体の条件)を成立させることができます。

 「うまく選べば」とのことです。何のことはない、言い換えれば「そういう既約多項式が存在するから探してみろ」というわけです。身もふたもありません。
 この「そういう既約多項式」として、GF(2^4)では「a^4 + a^1 + 1」、GF(2^8)では「a^8 + a^4 + a^3 + a^2 + 1」が当てはまることが数学の大先輩たちによって計算されていますので、ありがたく使わせていただきましょう。

 「a^8 = a^4 + a^3 + a^2 + 1」を踏まえて、a^8以降のリストを考えてみましょう。「a^8」は「a^4 + a^3 + a^2 + 1」に変換できると分かっていますので、そのまま「a^8 = a^4 + a^3 + a^2 + 1」です。「a^9」では指数が1ずつ増えて「a^9 = a^5 + a^4 + a^3 + a^1」、同様に「a^10 = a^6 + a^5 + a^4 + a^2」「a^11 = a^7 + a^6 + a^5 + a^3」です。「a^12」は「a^12 = a^8 + a^7 + a^6 + a^4」ですが、a^8は変換しなくてはならないので「a^7 + a^6 + a^4 + a^4 + a^3 + a^2 + 1」です。GF(2)の足し算はXORですから、「a^4 + a^4」は消滅し、「a^7 + a^6 + a^3 + a^2 + 1」が答えとなります。2進数にすると「11001101」です。
指数	2進	10進
a^7	10000000	128
a^8	00011101 	29
a^9	00111010 	58
a^10	01110100 	116
a^11	11101000 	232
a^12	11001101 	205
 ここまで分かれば、プログラムを書いてGF(2^8)のリストを自作することもできるはずです。
 以下に示すのは、以上の処理を「全く定義通りに」書き、それによって表を生成するJSPプログラムです。なお、プログラムのソース中で使用されている「^」は累乗ではなくXORです。混同しないように気をつけてください。また、「全く定義通りに」書くために、やや遠回りな記述をしている箇所があります。
<%@page contentType="text/html;charset=Shift_JIS" %>

<%!
// 2進法の文字列を生成するプログラム
// dec : 2進法に変換する値
// bit : 何ビットの2進値に変換するか
private String decToBin(int dec , int bit){
	StringBuffer buf = new StringBuffer(bit);
	for(int i = bit - 1; i >= 0; i--)
		buf.append((dec >> i) & 1);

	return buf.toString();
}
%>

<html>
<head>
<title>GF List</title>
</head>

<body>
 ガロア拡大体 GF(2<sup>8</sup>) のリスト

<table border="1">

<tr>
<td bgcolor="#CCDDFF">指数</td>
<td bgcolor="#CCDDFF">根</td>
<td bgcolor="#CCDDFF">2進法</td>
</tr>

<%
int alpha = 1;
for(int i = 0; i < 256; i++){
%>
<tr>
<td align="right"><%=i%></td>
<td align="right"><%=alpha%></td>
<td align="right"><%=decToBin(alpha , 8)%></td>
</tr>
<%

	alpha = alpha << 1;	// 指数を増やす

	// もし a^8 が生じたら
	if((alpha & (1 << 8)) != 0){
		// a^8 を a^4 + a^3 + a^2 + 1 に変化
		alpha -= 1 << 8;
		alpha ^= (1 << 4) ^ (1 << 3) ^ (1 << 2) ^ 1;
	}
}
%>

</table>

</body>
</html>
 これで255までの全リストが得られます。
カテゴリ [開発魔法] [トラックバック 0][コメント 0]
<- 前の記事を参照 次の記事を参照 ->

- Blog by yamicha.com -