FSH2007ST6/QR(2) の変更点 - PukiWiki

&color(red){★ 工事中 ★};
* QRコードについて (その2) [#ye52eee4]
** 形式情報について [#p680f370]

形式情報は2ビットの誤り訂正レベルの指示子と3ビットのマスクパターン参照子の計5ビットです.
その5ビットのあとに誤り訂正のための10ビットを続けます.
- 誤り訂正レベル ~
,2進指示子,誤り訂正レベル,復元能力%(概数),型番IのRSブロック
,00,M,15%,RS(26 16 4)
,01,L,7%,RS(26 19 2)
,10,H,30%,RS(26 9 8)
,11,Q,25%,RS(26 13 6)
- マスクパターン ~
,マスクパターン参照子,条件
,000,i+j mod 2=0
,001,i mod 2=0
,010,j mod 3=0
,011,i+j mod 3=0
,100,(i div 2)+(j div 3) mod 2=0
,101,((ij) mod 2+(ij) mod 3)=0
,110,((ij) mod 2+(ij) mod 3) mod 2=0
,111,((ij) mod 3+(i+j) mod 2) mod 2=0

** 誤り訂正部分の計算 [#led64b1b]

誤り訂正部分を作る際には生成多項式と呼ばれる特別な多項式
&mimetex(g(x)=x^{10}+x^8+x^5+x^4+x^2+x+1); を使います.
多項式の乗算や剰余の計算は全て &mimetex(F_2); 係数の多項式として計算を行います.

+ 形式情報5ビット&mimetex(b_4 b_3 b_2 b_1 b_0);を多項式で表わし, 
さらに&mimetex(x^{10});を掛けた式を&mimetex(q(x));とします.
すなわち, ~
&mimetex(q(x)=(b_4 x^4+b_3 x^3+b_2 x^2+b_1 x+b_0)x^{10}=b_4 x^{14} b_3 x^{13}+b_2 x^{12}+b_1 x^{11} +b_0 x^{10}); ~
&mimetex(q(x)=(b_4 x^4+b_3 x^3+b_2 x^2+b_1 x+b_0)x^{10}=b_4 x^{14}+ b_3 x^{13}+b_2 x^{12}+b_1 x^{11} +b_0 x^{10}); ~
を計算します.
+ &mimetex(q(x)); を生成多項式 &mimetex(g(x)=x^{10}+x^8+x^5+x^4+x^2+x+1); で割った余り&mimetex(r(x));を計算します.
+ 多項式 &mimetex(q(x)+r(x)); を14次の多項式と見て係数のビット列15ビットが求める誤り訂正部分を含む形式情報になります.
- (注意) &mimetex(q(x)+r(x)); は &mimetex(F_2);係数の多項式として, 生成多項式
&mimetex(g(x));で必ず割り切れます. ~
数の場合のたとえ話を交えて簡単に説明します.
-- &mimetex(F_2);の世界では加算(+)と減算(-)は同じです. x+y=x-y (x,yに0または1を入れて確認してみて下さい)
-- 数Qを数Gで割った余りを数Rとするとき, (Q-R)はGで割り切れます. (例.Q=13, G=5のとき, R=3であり, Q-R=10は, G=5で割り切れます.)
-- 多項式q(x)を多項式g(x)で割った余りをr(x)とするとき, (q(x)-r(x))はg(x)で割り切れます.
-- &mimetex(F_2); 係数の多項式の演算でも加算(+)と減算(-)は同じです. すなわち, q(x)+r(x)=q(x)-r(x) です.
-- 従って, q(x)+r(x)はg(x)で割り切れます.
-- 実は, 生成多項式 g(x) は原始既約多項式&mimetex(x^4+x+1);で割り切れるように作られています. ~
実際, &mimetex(g(x)=(x^4+x+1)(x^6 + x^4 + x^3 + x^2 + 1)); です.
-- 従って, q(x)+r(x)は&mimetex(x^4+x+1);でも割り切れることになります.
-- この性質を誤り訂正や検査に用いています.

** (例) 実際のQRコードの形式情報データを作ってみる [#d6c73d67]

誤り訂正レベルM, マスク条件((ij)mod3+(i+j)mod2)mod2=0の形式情報は00111です.
この5ビットのデータに誤り訂正部分10ビットを加えて15ビットのデータ列を作ります.
+ &mimetex(q(x)=0 x^{14} + 0 x^{13} + 1x^{12} + 1x^{11} + 1x^{10} = x^{12}+x^{11}+x^{10});になります.
+ &mimetex(q(x)); を &mimetex(g(x)=x^{10}+x^8+x^5+x^4+x^2+x+1); で割ると,
&mimetex(r(x)= x^9+x^7+x^5+x^4+x);となります.
+ 求める多項式 q(x)+r(x)は, &mimetex(x^{12}+x^{11}+x^{10}+x^9+x^7+x^5+x^4+x); となり誤り訂正部分を含む15ビットの列は001111010110010になります.


** [[ハイレベル合宿に戻る>FSH2007ST6]] [#jf38418c]

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSSPDF