QRコードをつくってみる3

最初のページへ  前のページへ  次のページへ




2.3 誤り訂正コード語の作成

 前述した通り、QRコードではリード・ソロモン(以下RS)誤り訂正方式という方法で 冗長コードを付加し誤り訂正機能を持たせています。

 まず前項で得たコード列を各バージョン・誤り訂正レベルで規定されるRSブロックに分割します。
 いま表5より1-H型はRSブロック数1なので分割は不要です。

 次に計算方法ですがJISの規定では以下のように記されています...

「QRコードの多項式は2を法とする算術および100011101を法とする 算術(体の原始多項式 x8+x4+x3+x2+1 の係数を示す100011101を持つ 28のガロア体)を使用して求める。データコード語は多項式の項の係数で 最高次項を最初のデータコード語とする。誤り訂正コード語はRS誤り訂正で 使用される多項式g(x)によってデータコード語を除算して得られた剰余とする。」

....学校でもう少し数学をまともに学んでおけばよかったと思いました...
一見ちんぷんかんぷんですが一つずつ解釈していきます。

まずわかりやすいところから...g(x)ですがこれは表3を参照します。
いま1-H型は誤り訂正コード語数が17ですので表3より

g(x)=x1743x16139x15206x1478x1343x12
    +α239x11123x10206x9214x8147x724x6
    +α99x5150x439x3243x2163x +α136

となります。

 ここで出てくるαとは「GF(28)上の原始要素2の根」と規定にはありますがこれも数学に 疎い者には難解です。まずGF(28)を理解しなくてはいけません。

 私は下記のページを読んでイメージをつかみました。一読してみてください。

http://bw-www.ie.u-ryukyu.ac.jp/~wada/vhdl/GaloisField.html

ここで使用するGF(28)の特徴として
 1、四則演算ができる。
 2、α255=1である。
 3、αのべき乗と整数とをテーブル(表4)を用いて互いに変換できる。
があげられます。

ここでデータコードを係数とした多項式f(x)をg(x)で除算します。
すなわち

f(x)=32x25 +65x24 +205x23 +69x22 +41x21 +220x20 +46x19 +128x18 +236x17 <---(1)

これをg(x)でわります。

ここでf(x)の最初の項の係数が32なので商の最初の項の係数は32となりますが、 g(x)の係数がαのべき乗表示なので 表4より 32をαのべき乗すなわち α5 となります。

 g(x)*(α5)*x8

5*x25543*x245139*x235206*x22578*x21・・・

5*x2548*x24144*x23211*x2283*x21・・・

=32x25 +70x24 +168x23 +178x22 +187x21 ・・・ <---(2)

(1)と(2)の項の係数の排他論理和を計算して

f(x)'=7x24 +101x23 +247x22+146x21・・・

を得ます。

あとはこれの繰り返しで次は7に対応するα198を商の次の項の係数とし、g(x)*α198*x7を 計算し係数部を整数化して排他論理和をとります。なおαのべき乗の指数が255を超えた ときは α255=1 を利用して255未満にします。

この結果、

剰余R(x)=42x16 +159x15 +74x14 +221x13 +244x12 +169x11+239x10
    +150x9 +138x8 +70x7 +237x6 +85x5 +224x4 +96x3 +74x2 +219x +61


がえられます。(途中の計算は表6参照)

よって最終的なデータは

32 65 205 69 41 220 46 128 236 42 159 74 221 244 169 239 150 138 70 237 85 224 96 74 219 61

となります。


次ページ:データの配置

前のページ  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]  次のページ