yamicha.com's Blog - Presented by yamicha.com
Blog yamicha.com's Blog - 2017/05 の記事
[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] [31]

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符号実装(1)
2009/03/05(Thu)20:51:02
日本中の実装者の中で最も数学能力が低い人間によるQRコードRS符号実装(1)
 できるだけ分かりやすく書こうとしたところ、作文用紙にして実に200枚近い、軽めの文庫本ほどの長文となりましたので、記事を分割しています。本来は1つの文章として書いたものです。

 このところ、紙媒体などを中心に「QRコード」なるものを頻繁に見かけるようになりました。この言葉に聞き覚えのない方も、おそらく実物なら目にしたことがあるはずです。ご存じない方のために簡単に解説しておきますと、「QRコード」とはデンソーウェーブの登録商標で、「JIS X 0510」及び「ISO/IEC 18004」で規格化されています。マトリックス二次元型の2ビットパターンで、高速読み取り及び一定のデータ破損耐久性を前提として開発されたものです。
 余計に分からない、との声が聞こえてきそうですが、要するに二次元バーコードです。モザイク模様としてデータが格納されたもので、最近は携帯電話を使用して読み込む例が多いようです。広告・雑誌などの紙媒体の隅に印刷してある、人間には到底解読不可能な幾何学模様が描かれた、さりげないように見えて大変目障りなあれです。
 私は携帯電話なるものを使用していないため、基本的には携帯電話または専用機械で読み取られる場合が多いQRコードには全く縁がなく、したがってQRコードは障害物でしかありません。本来そのようなものは無視していれば済むのですが、さすがに目障りなだけはあり、どうにも目に付いて仕方ありません。結果、自作してみたくなるのはある意味で当然の結末です。
 自作とはいっても、私は別にQRコードに情報やURLを格納し、それをどこかに貼り付けたいわけではありません。皆様におかれましても、そのような用途がお望みなら、世には多くのフリーQR生成ソフトが出回っていますし、フォームから作成できるサイトもありますので、それを使用すれば足ります。ここでの「自作」とは、すなわちQRコード生成プログラムの開発を意味します。何らかの物事の中身を深く理解するには、それを自分で実装してみるのが最も良い方法です。
 QRコードを作成するには、まず仕様を入手しなければなりません。仕様はJISのサイトから入手できるのですが、何と有料(しかもかなりの高額)です。他人様の開発した技術の仕様書を売って金を取ろうなどとは、一体どのような了見なのでしょう。まさか、日本の技術の発展と流通を止めようとしているのでしょうか。じきに金配り政策の代償も払わされるはずですので、庶民はこのようなものを買ってはいけません。こちらのサイトからPDFをダウンロードできますので、これを利用しましょう。ただし、私はJISの仕様書を購入していませんので、ここにあるPDFに書かれた仕様がJISの仕様書と同等であるかは分かりません。
 何はともあれ、これで仕様も手に入りましたので、これでようやく実装にかかれる、などと考えてはいけません。このPDFがまたひたすら意味不明なのです。ちまたにはQRコードの作成方法について書かれたサイトが多くありますので、仕様書は技術仕様のリストとしてのみ使用し、具体的な作り方はGoogleなどでサイトを探して調べることを強く推奨します。
 ところで、実はQRコード自体はさほど難しいものではありません。サイズやエラー訂正の規格がやたら多くあって困りますが、ここでは全規格を網羅しようとしているわけではありませんので、比較的作りやすそうな規格に絞って考えれば十分でしょう。データのビット化も簡単ですし、ドットの配置の方法も単純で、面倒な処理は存在しますが、文字通り「難しい」処理はほとんど存在しません。
 しかし、これには1つだけ例外があります。この例外だけはどうしようもないほどに難しく、おそらくQRコードの鬼門といえるものです。QRコード生成プログラムの作成に挑戦して撃沈した人のうち、9割5分はこれに跳ね返されたと考えて間違いありません。前述の通り、QRコード自体は全く難しいものではありませんので、それなりに確かな開発手腕さえ持っていれば、誰にでも開発できるでしょう。したがって、ここではQRコード自体の実装は一切行わず、この「鬼門」に絞って詳説するものとします。

 QRコードは紙などの有形物に印刷し、それを読み取って使用するのが前提の技術ですから、汚損や破損に耐性がなければ話になりません。インクの汚れやにじみは日常茶飯事ですし、コードが湾曲あるいは斜めになっていたり、ビットが判別しづらかったりする状態で読み取りがなされる可能性もあります。そこで、誤りを検出・訂正する技術が重要になってきます。それこそがQRコード最大の鬼門なのです。
 QRコードの誤り訂正に用いられているのは、「リード・ソロモン符号」(RS符号)と呼ばれる技術です。ソロモンといえば何と言ってもソロモンの鍵でしょう。相当昔のはずなのですが、あのアラビア風の音楽は今でも記憶に残っています。それと符号とは何の関係もないのは言うまでもありませんが、そのような連想でもしないことには、とてもやっていられません。
 どうやら、この技術には数学が密接にかかわりあっているようです。確かに、例のPDFの仕様書に目を通してみても、訳の分からない数式がひたすら並べてあるのみで、何をどうすれば先に進めるのか全く分かりません。ここまで何の取っ掛かりもなく、まさに手も足も出ないとなると、むしろ気持ちよくあきらめがつきそうです。さすがに鬼門だけはあって、私とは次元が違いすぎます。
 検索でたどり着いた方のために、ここで簡単に自己紹介をしておきましょう。
  • 名前
     サイト内ではドメイン名をハンドルの代わりとして使用しています。外部では分野に応じて色々な名前を使用しています。
  • 好きなもの
     ブラックコーヒー、読書、会話、カラオケ(フォーク)。
  • 得意分野
     数学に比べれば、政治・経済・法・社会学の方が余程得意です。
  • 今までブログで取り扱った言語
     C , C++ , Java , Perl , PHP , JavaScript , Python , Ruby , Groovy , C# , VB.NET , COBOL , Ada , Haskell , Common Lisp , Scheme , OCaml , Prolog , SQLなど。今回はJavaを使用します。
  • 数学能力
     「算数」では100点の常連でした。ただし「数学」ではなく「算数」です。数学能力はゼロに等しく、方程式は正真正銘ほぼ完全に分かりません。因数分解はやり方どころか、それが何であるかさえ理解していません。虚数は定義だけ知っていますが、使い方は全く知りません。FORTRANなどには複素数型がありますが、何に使うのか分かりません。
     以前までは三角関数の意味を全く知りませんでしたが、3Dライブラリの実装によってベクトル・マトリックス・三角関数とその逆関数を習得しました。また、Haskellのおかげでモナドやモノイド、単位元などといった概念を習得しました。しかし、これらの知識は今回の問題には関係ありません。
 ある意味でとてつもない挑戦です。すなわち、この記事は

1.数学能力を一切持っていない、当ブログ執筆者たる私が
2.心もとない開発能力と開発者のカンのみを頼みに、QRコードのエラー訂正用リード・ソロモン符号を理解・実装する

 ものであるといえます。したがって、私は「QRコードのエラー訂正RS符号を実装した日本中の人間の中で、おそらく最も数学能力の低い人間」でしょう。
 ここまで徹底していると、私が謙遜あるいは大げさに書いていると考える方も出てくるかもしれませんが、できることなら「大げさ」であって欲しいと私もつくづく考えています。なまじ開発能力が使えると、勝手に理系であるとみなされてしまうのがつらいところです。

補足説明 : 方程式や累乗に関して
 以下、説明に中学1年生レベルの方程式を使用している場合があります。私が中学1年生前半レベルの方程式までしか理解していないため、それ以上に難しいものは出てきませんが、念のためにいくつか補足をしておきます。いずれも当然のことしか書いていませんので、理解している方は飛ばしてください。

・方程式では掛け算記号を省略する場合がある
 方程式では、「a * b」は「ab」、「a * 2」は「2a」などとも書けます。とはいえ、ただの掛け算ですから難しく考える必要はありません。RPGなどで、ダンジョンに出かけるので「ポーション」や「やくそう」を20個ほど買い込んだとして、ゲーム画面では「ポーション x 20」と書かれるところを、数学では「20ポーション」と表記するに過ぎません。

・方程式では0個になったものが消えてしまう場合がある
 「a * 2」を「2a」と書くなら、「a * 0 + b」は何でしょう。aが0個ですから「0a + b」でしょうか。しかし、「aがない」のですから、特にaを書く必要はないはずです。したがって、これは単に「b」とも書けます。
 先のRPGの例で考えれば、「ポーション20個」とイベントアイテム「キャメル本」を持ってダンジョンにもぐったとしましょう。しかし、度重なる戦闘でポーションを消耗し、結局全部使い切ってしまいました。魔法などがなければ、ほぼ「詰み」の状態です。
 ところで、ここでステータス画面を開いたとして、アイテム欄に「ポーション x 0」「キャメル本」と表記されるでしょうか。普通は「ポーション」が一覧から消えてなくなるのではないでしょうか。つまり、アイテムは「キャメル本」だけとなります。

・方程式では「1個」を明示しない場合がある
 ここに「2a」があるとしましょう。もしここからaを1つ取り去ったら、残りは何になるでしょうか。「2a」とは「aが2つ」なのですから、aが1つなくなったら「1a」です。しかし、1個のものをわざわざ「1a」などと断る必要はないでしょう。したがって、「1a」は単に「a」とも書きます。

・累乗の指数表記について
 本来は小さな文字で「22」のように表記するものとされていますが、HTMLや特殊書式をサポートする文書にしか反映できません。プレーンテキストでは使用できず、コピーして別の文章に貼り付けると「22」になってしまうなど、PC上では不便です。したがって、「2^2」などと表記するのが慣習となっています。以下ではこれらが混在していますが、同じものです。文章を引用する際に「22」の表記が使用されていた場合、引用元文章の内容を損なわないために、できるだけ同様の表記を用いたのが混在の理由です。
 ただし、ここでもう1つ注意が必要なのが、CやJavaなどプログラム上の演算子としての「^」です。CやJavaにおいての「^」は累乗ではなく、ビットごとの排他論理和の演算子です。言語によっては「^」に累乗を割り当て、排他論理和として「XOR」などの命令を用意している場合もあります。この2つを混同しないように注意してください。
 以下では分かりやすいよう、排他論理和としての「^」演算子の使用はプログラムにかかわる部分に限定し、普段はできるだけ「XOR」と表記するようにしました。また、累乗は原則として「2^2」のようにくっつけて記述し、XORは「2 ^ 2」と離して記述しています。

・「x^0」について
 xの1乗が「x」、xの2乗が「x * x」、xの3乗が「x * x * x」であるのは、おそらく常識でしょう。それでは、「x^0」はいくつになるのでしょうか。これは「数の悪魔」でも述べられている有名な話ですが、「x^0 = 1」です。2でも100でも0でも、0乗すると1になります。
 今後「a^0」などといった表記が出てきますが、これは「1」と同じものと考えてください。「a^1 + a^0」と「a^1 + 1」は同じものです。また「a^1 = a」ですので、「a + 1」も同じものです。状況に応じて「a^0」と「1」の両方の表記を用いていますが、両者は全く同じと考えてください。

・「アルファ」の表記について
 アルファ記号はShift_JISの0x83BF、Unicodeの0x03B1のコードで、日本語を使えるPCならおそらくほぼ確実に表示可能なはずですが、表示されない可能性がゼロとまではいえず、またソースコードなどにコピーして使用するにも使いづらい、本来ならasciiのみで表せる数式に2バイト文字が入る、などの理由により、本文中では「a」と表示してあります。引用部分のアルファはそのままにしてありますので、表記の混在が発生していますが、同じものです。

 本題に戻ります。
 上記でリンクしたWikipediaの記事によれば、「符号理論の基本概念として以下に登場する加算記号(+)は全て加算ではなく各ビットごとの排他的論理和を表す」とのことですが(ちなみに「排他論理和」とは、片方が1でもう片方が0の場合のみ1となるビット演算です。記号では「^」、英単語では「XOR」と表現されることがあります。1 XOR 0 = 1、0 XOR 1 = 1、0 XOR 0 = 0、1 XOR 1 = 0です)、なぜ加算記号がXORになってしまうのでしょうか。さっぱり意味が分かりません。また、リード・ソロモン符号は「拡大ガロア体」を使用しているのだそうです。ところで、ガロア体とは一体何なのでしょう。全く耳慣れない言葉です。地中海地方の一部でしょうか。それとも、船の種類の一種でしょうか。私のボキャブラリーにあるのはこの辺りが限界で、「ガロア体」などといった言葉は全く不明です。
 まずはWikipediaに頼ってみるとしましょう。有限体の項がそれです(「有限体」はガロア体の別名)。ところが、何が書いてあるのか全く分かりません。ただ、仕様書PDF中に「GF(x)」といった記述が出ていましたが、この記事中にも「GF」なるものがいくつか出てきており、これがガロア体に関係あるらしいことが分かりました。
 こうなれば、頼りになるのが検索エンジンです。「QRコード」や「リード・ソロモン」、「ガロア体」などのワードで片っ端から探してみたところ、様々なサイトが見つかりました。最初の時点で発見し、役に立ったサイトを列挙しておきます。また、これらのサイトの作成者の方々には、この場を借りてお礼申し上げます。

QRコード作成関連(RS符号化以外の部分の実装時にも参考になります) リード・ソロモン符号やガロア体の解説
  • 琉球大学教授の和田氏のガロア体補足
  • hesperus.netガロア体 GF(28)(何とガロア体 GF(2^8) 算出ソースがあります。後述の理由で私は参考にしていませんが、そのような縛りを設けない方には有用でしょう)
 これらのサイトの中には、処理のソースを記載したり、あるいはQRコード変換プログラムのソースを公開しているものもありますが、私は今回他人のソースは一切見ないことを条件としました。ただし、明らかな虚偽の事実の発信を避けるため、最終確認と最終調整のみにいくつかのソースを閲覧しています。早い話がソースを丸写しすれば動きますし、そうでなくても参考にすれば難易度は大きく下がりますが、それでは技術の習得ができませんし、何よりソースの権利関係がややこしくなります。このブログ上のソースは基本的に流用自由ですが、もし他人のソースを写してしまっては、そのような主張ができなくなりますので、この条件を導入した次第です。
 上記の資料にはQRコードの作り方が書かれているわけですから、読めばRS符号など簡単に作れそうなものではあります。しかし、仕様書より何倍もマシであるとはいえ、上記のいずれのサイトも大変難しいため、はっきり言って到底理解できるものではありません。Googleで相当色々なサイトを調べましたが、分かりやすいものは1つたりともありませんでした。RS符号を作るとなると、やはりそれなりの知識が前提となるのでしょうか。
 それでは、まず仕様書を読むなり、Googleなどで探すなり、swetake.comや渋谷氏のPDFといった資料を読むなりして、エラー訂正について調べてみましょう。異口同音に次のようなことが書いてあります。

QRコードの多項式は2を法とする算術および100011101を法とする算術(体の原始多項式 x^8+x^4+x^3+x^2+1 の係数を示す100011101を持つ 2^8のガロア体)を使用して求める(仕様書PDF)

 いくつかの記述を読み比べてみると、これが「GF(2^8)」なるものであるらしいと分かります。しかし、このGFなるものが何であるのかが分かりません。ガロア体とやらに関するもののようですが、一体何なのでしょうか。数学ができない人間には相当な苦痛なのですが、どうやらガロア体について学ばなければならないようです。
 そこで先の琉球大学の資料を読んでみます。まず「ガロア体」についてですが、次のように解説されています。

整数の集合は{..., -1, 0, 1, 2, ...}と無限の要素から成り立っているのに対して、 ガロア体とは整数を素数(たとえば5)で除算した余りの集合{0, 1, 2, 3, 4}のように 要素が有限で四則演算が閉じている集合である。

 その下には具体例も書いてあるため、記述が理解しやすくなっています。「閉じている」などと言われてもさっぱりですが、今回の目的は「ガロア体の理解」ではなくRS符号の実装ですから、そこは考える必要がありません。簡単に理解してしまいましょう。
 ガロア体といいますのは、「ある数字X以上のものが存在しない世界」といえそうです。この「X」が5であれば、0〜4しかない世界です。足し算や掛け算で値が5以上になった際には、mod 5(5で割った余り)を求めて0〜4の範囲にします。例えば「3 + 4」であれば7ですが、5以上の数は存在できないため、7を5で割った余りを求め、2が得られます。「4 * 4」は16ですが、これも5で割った余りを求めて1にします。このような世界が「5のガロア体」となるようです。

補足事項
(これはただの補足であって、知らなくても実装には全く関係ありません。意味が分からない方、あるいはお急ぎの方は飛ばしてください。今後出てくる「補足事項」についても同様です)
 5のガロア体なるものは分かりました。一方、このページによりますと、4はガロア体ではないのだそうです。理由は「四則演算が閉じている」わけではないからとのこと。さっぱり意味が分かりませんが、一体何を言わんとしているのでしょうか。
 私はこれを簡単に「逆算の可否」と考えています。小学校であった「X + 3 = 5」などという、あの逆算です。ガロア体は四則演算の逆算ができますが、そうでないものではできないらしいのです(ただし「0 * X = 0」のような問題は、ガロア体であってもなくても逆算のしようがありませんので、除外します)。
 まずは5のガロア体の場合を考えてみます。「X * 2 = 3」であれば、Xには何が入るのでしょうか。「0 * 2 = 0」「1 * 2 = 2」「2 * 2 = 4」「3 * 2 = 1」(計算自体の答えは6だが、5のガロア体には5以上の値が存在しないため、それを5で割った余りを求め、結果は1)「4 * 2 = 3」ですから、Xは4であると分かります。
 他の掛け算でも、仮に「X * 3 = 4」であれば、Xを0から4に置き換えて計算してみると、それぞれ「0 * 3 = 0」「1 * 3 = 3」「2 * 3 = 1」「3 * 3 = 4」「4 * 3 = 2」ですから、Xは3であると分かります。5のガロア体では、この逆算がいかなる場合にも成り立ちます。
 それでは4の場合はどうでしょうか。「X * 2 = 2」の問題を考えてみましょう。「1 * 2 = 2」「2 * 2 = 0」(しつこいようですが、2 * 2 = 4ではあるものの、4以上の値は存在しないため、4で割った余りを求めて0)「3 * 2 = 2」と、どちらが正しいXなのかが分かりません。したがって、「逆算ができない場合がある」ので、これはガロア体ではありません。

 次に、先の琉球大学のページを読み進め、GF(2)の場合を見てみましょう。ここで「GF」が出現しましたが、本文によればこれは「ガロア拡大体」というものらしいことが分かります。とはいえ、この段階では「拡大」ゆえの違いなどありませんので、まだ無視して構いません。これはゆくゆく説明しますので、今は単純に「2のガロア体」と考えてください。
 GF(2)はつまり0と1しかない世界です。計算方法は5のガロア体などと基本的に変わりません。0と1しかない分、5よりも余程簡単です。
 ところで、このサイトには次のような文章が出てきます。

加算はEXORで、1+1=0ですので1=−1となることに注意してください。
乗算はANDということになります。

 なぜでしょうか。そういえば、先ほどのWikipediaの「リード・ソロモン符号」でも「+は加算ではなく排他論理和だ」と書かれていました。つまり、2のガロア体における加算は加算ではないのでしょうか。ますます意味が分からなくなってきました。以下、GF(2)の計算を考えてみます。

・足し算
0 + 0 = 0 であるため、結果は0。
1 + 0 = 1 であるため、結果は1。
0 + 1 = 1 であるため、結果は1。
1 + 1 = 2 だが、GF(2)では0と1しか存在できないので、2で割った余りを求める。結果は0。

・掛け算
0 * 0 = 0 , 1 * 0 = 0 , 0 * 1 = 0 であるため、どれも結果は0。
1 * 1 = 1 であるため、結果は1。

 これで謎が解けました。上記のような計算となるため、結果的に足し算はXOR、掛け算はANDと等しいのです。足し算をした上でmod 2で値を0か1にしても構いませんが、XORを使用する方が断然楽ですから、今後はここでもこれを使用します。
 ここまでの理解はさほど難しくありませんが、ここから一気に混迷が深まります。GF(2^w)について。先のサイトにはこのように書いてあります。

2w(2のw乗)の要素(元)をもつ体は2wのガロア拡大体と呼び、GF(2w)と表します。

i. GF(2)上の元{0, 1}を係数にもつw次の既約多項式p(x)を考える。
ii. 新しくaという元を考え、p(α)=0と仮定します。
iii. 既約多項式p(x)をうまく選べば、

α0123,...,α2w-2

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

a2w-1 = 1

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

iv. これに零元を加えてると、GF(2w)の元の集合となる。

 ここまでは噛み砕いて書いてあったはずが、ここで完全に意味不明となりました。何が書かれているのか全く分かりません。取り付く島もないとはこのことで、私にとってGFなるものがいかに無謀な挑戦であったかが分かります。何やら謎の変数「a」がカギになりそうですが、この時点ではそれが何であるかすら想像もつきません。
 現段階ではとても私の手に負えませんので、ここは無視して先に進むとして、ひとまず新出の用語の解読だけでも行っておきます。
  • 既約多項式の「既約」とは何か
     これは「これ以上簡略化できない状態まで簡略化されたもの」といえます。分数で「5/15」を「1/3」に直したりしましたが、「1/3」はこれ以上簡略化できないので既約です。
  • それでは、多項式とは何か
     いくつか式が連なっているものです。1 + 2 + 3など。
  • 既約多項式とは何か
     これ以上簡略化できない多項式です。なお、幸いなことに多項式の因数分解などはする必要がありません。もしあったら確実に撃沈していました。「因数分解に当たる処理」はあるようですが、すべて実装に畳み込めます。この「既約多項式」の言葉自体、忘れていても何の問題もないものですので、意味が分からない方も安心してこの先をご覧ください。
  • 要素(元)とは何か
     調べてみたところ、いわゆる「配列の要素」のようなものだそうです。例えば5のガロア体は、0から4までの5つの要素を持っていました。GF(2^w)は2^w個の要素を持っているというわけです。
  • 「新しくaという元を考え、p(a)=0と仮定します」とはいかなる意味か
     それが分かれば苦労はしません
 次にGF(24)の項を見てみましょう。GFは「拡大ガロア体」なるものであることを先に述べましたが、これは通常の「ガロア体」とは少々違うものです。GF(2)では表立った違いはありませんでしたが、それを超えた値となると違いが生じてきます。
 さて、このGF(2^4)ですが、ここで次のような疑問を持たれた方もいるかもしれません。

「GF(2^4)はGF(16)ではないのか。また、そう表記してはいけないのか」

 正解です。GF(2^4)はGF(16)と同じもので、実際にGF(16)と表記しているサイトもあります。これは好みの問題ともいえるでしょう。しかし、「2^w」のガロア拡大体といいますものは、2のガロア体をw個用意したものと考えることができ、リード・ソロモン符号はそれを応用した技術となっています。2のガロア体が4つあるものと考えるのでGF(2^4)です。ですからあえて「16」ではなく「2^4」と書かれるのです。きっと
 具体的には、GF(2^4)は次のようなものであるといえます。謎の変数「a」のが登場していますが、これが何であるかは現時点では良く分かりませんので、とにかく「何らかの代数」と考えてください。少しばかり方程式らしき記述が出ていて申し訳ないのですが、

r0 ... r3 を2のガロア体とし、それぞれが0または1の任意の値を取るものとして、
GF(2^4) = r3a^3 + r2a^2 + r1a^1 + r0a^0

「r3a^3」のような表記が苦手な方は、以下のように掛け算記号を入れて理解してください。
GF(2^4) = r3 * a^3 + r2 * a^2 + r1 * a^1 + r0 * a^0

 要するに、r0 ... r3は「a^xがあるかないか」を表しています。仮にr3が1であれば、「r3a^3」は「1a^3」となりますので、そのまま「a^3」が得られます。一方、r3が0であれば「0a^3」ですから、「a^3」は存在しないとみなせます。
 少し練習してみましょう。もしr3とr1が1、r2とr0が0なら、a^3とa^1が1個、a^2とa^0が0個ですから、

1a^3 + 0a^2 + 1a^1 + 0a^0 = a^3 + a^1

 ということで、答えは「a^3 + a^1」です。同様に、r3とr2が0、r1とr0が1なら、

a^1 + a^0

 といえます。

 それからもう1つ、指数に関する演算の例も出しておきます。謎の変数「a」の奇妙な性質にかかわる部分ですので、ここは非常に混乱するところですが、現段階ではまだ解説のしようがありません。詳細は後述していますので、原理を解き明かそうなどとは考えず、ひとまず「そういうもの」とだけ覚えておいてください。
 まずは以下の式をご覧ください。

a = a

 これが真であるなら(真に決まっていますが)、以下の記述も真となります。

a^2 = a^2

 ここまでは当然です。
 それでは、仮に「a^4 = a^1 + a^0」が成り立つとしましょう。なぜこれが成り立つのか全く理解不能ですが、ゆくゆく解説していきますので、今はaを「魔法の変数」であると考えてください。この場合、a^4は

a^4 = a^1 + a^0

 となりますが、それではa^5やa^6の場合は一体どうなるのでしょうか。これは意外に簡単で、左辺値の指数が増えただけ、右辺値の指数を増やせば良いのです。つまり、

a^4 = a^1 + a^0
a^5 = a^2 + a^1
a^6 = a^3 + a^2

 こうなります。
 「なぜ」との声が聞こえてきそうですが(分かる方は読み飛ばしてください)、冷静に考えればご理解いただけることでしょう。これは中学校1年生の教科書に出ていた覚えがあるのですが、「a = b」が真なら「2a = 2b」や「3a = 3b」も真になります。では、もし「a = b + c」の場合、aを2倍にしたら、左辺値はどうなるのでしょう。要は右辺値を倍にすれば良いのですから、「2a = 2b + 2c」です。3倍なら「3a = 3b + 3c」、5倍なら「5a = 5b + 5c」です。記号がややこしくて理解できないという方は、記号を数字に置き換えてみてください。もし「a = b + c」が「5 = 2 + 3」なら、それぞれを倍にした「10 = 4 + 6」や、5倍にした「25 = 10 + 15」が成り立つのがお分かりいただけるでしょう。
 次に指数について。仮にここに「2^2」なる値があるとしましょう。それでは、「2^3」は「2^2」の何倍でしょうか。言うまでもなく「2^2 * 2」です。もし「3^4」を「3^5」にするなら、こちらは「3^4 * 3」です。「7^2」を「7^3」にしたければ、もうお分かりの通り「7^2 * 7」です。ここまでは算数よりほんの少し上のレベルですから、私でも分かります。
 この2つを踏まえて、先の式を考えてみましょう。「a^4 = a^1 + a^0」と仮定して、「a^4」を「a^5」にするには、「a^4」を何倍する必要があるのでしょうか。先ほどの「2^3 = 2^2 * 2」の例をそのまま使って、「a^5 = a^4 * a」です。左辺値をa倍したのですから、右辺値もa倍すれば良いので、「a^4 * a = a^1 * a + a^0 * a」ということで、「a^5 = a^2 + a^1」となるのです。お分かりいただけましたでしょうか。

 ガロア拡大体には他にもいくつか厄介な条件が存在しますが、基本的にはこのような構造となっています。つまり、「a^3」「a^2」「a^1」「a^0」がそれぞれ「1個」か「0個」か、言い換えれば「ある」か「ない」かです。
 ところで、「あるなし」を管理するのは2のガロア体ですから、「1 + 1 = 0」であることに注意が必要です。例えば「a^3 + a^3」を演算すると、これはa^3が「ある + ある」、つまり「1 + 1」となりますので、a^3が消えてなくなってしまいます。これが「a^3 + a^2」であれば、a^3は「1 + 0 = 1」、a^2は「0 + 1 = 1」ですので、「a^3 + a^2」が得られます。また、「a^3 + a^2」と「a^2」を足すと、a^3は「1 + 0 = 1」、a^2は「1 + 1 = 0」となりますので、「a^2」が消えてしまって「a^3」が答えとなります。
 これで理解できた聡明な方は次に進んでください。意味が分からない方は、先ほど出てきたr0 .. r3を思い出してみましょう。

GF(2^4) = r3a^3 + r2a^2 + r1a^1 + r0a^0

 ここでr0 .. r3は2のガロア体でした。2のガロア体には0と1しかありませんので、当然「1 + 1 = 0」です。
 先ほどの「a^3 + a^2」と「a^2」の足し算を例にとって考えてみましょう。これらは次のように変形できます。

a^3 + a^2 = 1a^3 + 1a^2 + 0a^1 + 0a^0
a^2 = 0a^3 + 1a^2 + 0a^1 + 0a^0

 この「1」や「0」の部分が2のガロア体で、「1 + 1 = 0」となるのですから、結果はもう明らかでしょう。これらを足し合わせてみると、以下のようになります。

r3 r2 r1 r0
a^3 + a^2 1 1 0 0
a^2 0 1 0 0
答え 1 + 0 = 1 1 + 1 = 0 0 + 0 = 0 0 + 0 = 0

 これにより、以上の計算の答えは「a^3」となります。

 面白いのはここからです。世の中には頭の良い人がいるもので、一体誰が最初に考えたのかは知りませんが、このa^0 .. a^3の「あるなし」をそれぞれのビットに対応させてしまおうというアイデアが生まれました。実際にはアイデアが先にあって、都合の良い計算方法が後で考えられたのかもしれませんが、順番はこの際どうでも構いません。重要なのは、これをビットにしてしまうというアイデアの部分です。
 もしa^2であれば、次のようにビットを作ります。
a^3	a^2	a^1	a^0
0	1	0	0
 したがって、「0100」です。同様にa^3なら
a^3	a^2	a^1	a^0
1	0	0	0
 ですから、「1000」でしょう。
 もしa^3 + a^2であれば、
a^3	a^2	a^1	a^0
1	1	0	0
 ですから、「1100」のビット列となります。
 これなら演算も簡単です。仮に「a^3 + a^2」と「a^3」を足し合わせたら、どのような結果になるでしょうか。a^3が「1 + 1 = 0」、a^2が「0 + 1 = 1」ですから、a^3が消えてなくなって「a^2」となるのですが、これもXORで簡単に計算できるようになります。「1100 XOR 1000 = 0100」ですから、あっという間に「a^2」が得られるのです。
 ここまでの内容がある程度つかめたら、次に進みましょう。
カテゴリ [開発魔法] [トラックバック 0][コメント 0]
<- 前の記事を参照 次の記事を参照 ->

- Blog by yamicha.com -