2010年度 情報数理 ~ QRコードを作ろう!(1) ~.

Slides:



Advertisements
Similar presentations
2009/11/10 10 進数と r 進数を相互に変換できる コンピュータのための数を表現できる 2進数の補数を扱える コンピュータにおける負の数の表現を説明で きる コンピュータでの演算方法を説明できる 文字や記号の表現方法を示せる 第7回 今日の目標 § 2.2 数の表現と文字コード.
Advertisements

効率的に計算可能な 加法的誤りの訂正可能性 安永 憲司 九州先端科学技術研究所 SITA 2012 @ 別府湾ロイヤルホテル
7章 情報の表現と基礎理論. 数の表現(書き方) 「数」と「数の書き方」をわけて考える 「数の書き方」と,「数そのものの性質」は別のもの 例:13 は素数・・・”13”という書き方とは無関係 ここでは書き方(表現方法)について考える 567.
Outlook メール文字化けの原因と対策 Exchange Server 環境編. 目次はじめに文字化けのよくある原因と回避策 1. A:半角英数字、ヨーロッパ言語などが混在した 文字化け B : 送信済みメールの宛先や CC の文字化け 2. 返信、転送時の、ユーザー名や件名の文字化け 3. 日本語が半角英数字に文字化け.
基本編の用語説明 その2 エディタと日本語入力 エディタ  エディタ (editor) :文書を作成、編集する アプリケーションソフトウェア  教育用計算機システムのエディタは、 テキストエディット テキストエディット  基本的な編集方法はここここ  カーソル:文字が入力される位置を表している目印.
第6回 JavaScript ゼミ セクション3-6 発表者 直江 宗紀. 組み込み関数  JavaScript に予め用意された関数  特定のオブジェクトに依存していない  単に関数名で呼び出すことが可能.
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
復習 配列変数の要素 5は配列の要素数 これらの変数をそれぞれ配列の要素と呼ぶ この数字を配列の添え字,またはインデックスと呼ぶ
復習 配列変数の要素 5は配列の要素数 これらの変数をそれぞれ配列の要素と呼ぶ この数字を配列の添え字,またはインデックスと呼ぶ
第2章 第2節 情報通信の効率的な方法 1 情報の容量と伝送の特性 2 データの圧縮 3 エラー検出とエラー訂正
『基礎理論』 (C)Copyright, Toshiomi KOBAYASHI,
富山大学 公開講座 2008 「QRコードを作ろう!」 ~ QRコードを作ろう! ~.
数当てゲーム (「誤り訂正符号」に関連した話題)
LZ圧縮回路の設計とハード・ソフト 最適分割の検討 電子情報デザイン学科 高性能計算研究室 4回生 中山 和也 2009/2/27.
「情報」 (中村) オリジナル PPT (2010/05/07) 1 1.
情報処理の基礎 私たちとコンピュータの扱うデータの違い 明治学院大学 法学部消費情報環境法学科 鶴貝 達政
情 報 の 表 現(3) 情報社会とコンピュータ 第10回.
[復習]通信路符号化の限界 通信路符号化定理(Shannonの第2符号化定理)
コードの歴史 ASCII(American Standard Code for Information Interchange)  ANSI ISO 646 = 95文字のラテン文字 アルファベット+数字+特殊文字 制御コード: LF, CR などの表示制御と   ACK,DEL などの通信制御 、など.
地理情報システム論 第3回 コンピュータシステムおける データ表現(1)
第三章 ディジタル符号変換の基礎 3・1PCMパルス符号変換 3・2符号変換 3・3通信路符号形式 3・4スクランブル.
プログラミング論 II 2008年9月25日 誤り検出,訂正符号 ハミング符号
心理学情報処理法Ⅰ コンピュータにおけるデータ表現 マルチメディアとコンピュータ.
プログラミング言語論 プログラミング言語論 プログラミング言語論 演習1 解答と解説 演習1解答と解説 1 1.
アナログとディジタル 高校1年 社会と情報⑤.
2012年度 情報数理 ~ QRコードを作ろう!(1) ~.
2008年度 情報数理 ~ QRコードを作ろう!(1) ~.
日本大学 文理学部 情報システム解析学科 谷研究室 益田真太郎
システム開発実験No.7        解 説       “論理式の簡略化方法”.
Outlook メール文字化けの原因と対策
補数 n:桁数、b:基数 bの補数 bn-x 253(10進数)の10の補数は、 =747
10.通信路符号化手法2 (誤り検出と誤り訂正符号)
情 報 A ー ディジタル化のしくみ ー.
ネットワークでかわる社会 第2節 ネットワークのしくみ②
データベース設計 第2回 データベースモデル(1)
第3回: 今日の目標 平均情報量を説明し、計算できる シャノンの通信モデルを説明できる 情報源符号化の条件を示せる
情報基礎 講義番号:X61029 科目区分:教養教育科目 対象年次:1-4 必修 クラス指定 工(応化) 講義の内容
高速剰余算アルゴリズムとそのハードウェア実装についての研究
コンピュータを知る 1E16M009-1 梅津たくみ 1E16M017-8 小沢あきら 1E16M035-0 柴田かいと
文字コード 情報処理3 今井孝明.
文字の表現.
岩村雅一 知能情報工学演習I 第8回(C言語第2回) 岩村雅一
巡回冗長検査CRC32の ハード/ソフト最適分割の検討
QRコードを用いたウェーブレット変換による 電子透かし
2章 暗号技術 FM15002 友池 絲子.
第4回 コンピューティングの要素と構成 平成22年5月10日(月)
Ibaraki Univ. Dept of Electrical & Electronic Eng.
VIII. 空間情報表現.
文字エンコーディング 2010年7月.
QRコードを用いたIDカードに 適した電子透かし
2012年度 情報数理 ~ 様々なデジタル情報(1) ~.
暗号技術 ~暗号技術の基本原理~ (1週目) 情報工学科  04A1004 石川 真悟.
Fortranについて 高エネルギー加速器研究機構 平山 英夫.
岡村耕二 ビット誤りと訂正 岡村耕二 情報ネットワーク.
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
長さの制限付きギャップと 文字クラスを含むパタンに対する 照合アルゴリズムの改善
2010年度 情報数理 ~ 様々なデジタル情報(1) ~.
データの表現 2進数 0と1を使う。 基数(基準になる数)が2. 101(2) かっこで2進数と示すことがある。
地理情報システム論(総)/ 国民経済計算論(商)
富山大学 公開講座 2008 「QRコードを作ろう!」 ~ ハミング距離 ~.
エラー訂正符号を含むシステム CD, DAT, MD, DVD, ディジタルVTR等 ディジタル(衛星)TV放送 ディジタル・セルラ
線形符号(10章).
情報処理Ⅱ 第2回 2004年10月12日(火).
岡村耕二 ビット誤りと訂正演習 岡村耕二 情報ネットワーク.
2019年度 情報数理特論B ~ 様々なデジタル情報(1) ~.
復習 いろいろな変数型(2) char 1バイト → 英数字1文字を入れるのにぴったり アスキーコード → 付録 int
2008年度 情報数理 ~ 授業紹介 ~.
2012年度 情報数理 ~ 授業紹介 ~.
2012年度 情報数理 ~ ハミング距離 ~.
2010年度 情報数理 ~ ハミング距離 ~.
Presentation transcript:

2010年度 情報数理 ~ QRコードを作ろう!(1) ~

これは何でしょう? Quick Response 型番:7(45),誤り訂正レベル:L Code 答え:QRコード

QRコード最大の特徴 QRコード最大の特徴である3箇所に配置された位置検出パターン 型番:7(45),誤り訂正レベル:L

位置検出パターン(切り出しシンボル) 白黒の比が 1:1:3:1:1 になっている

QRコードの切り出し 型番:7(45),誤り訂正レベル:L 型番:7(29),誤り訂正レベル:L

クワイエットゾーン(マージン) 位置検出パターンを使ってQRコードを切り出すためには、QRコードの周りに4モジュール(セル)幅の領域が必要である。 型番:7(45),誤り訂正レベル:L

タイミングパターン 密度が決まる 型番が決まる モジュール(セル)の位置が決まる 型番:7(45),誤り訂正レベル:L

形式情報(フォーマット情報) 形式情報はデータおよびその誤り訂正コード語の復号化に必要な情報である。 誤り訂正レベル(2ビット),マスクパターン(3ビット)およびその誤り訂正コード語(10ビット)が矢印の順に配置されている。 冗長度を増すために2箇所に配置される。 型番:1(21),誤り訂正レベル:L

ちょっと実験 型番:1(21),誤り訂正レベル:L

白と黒のモジュールがまばらになるように! マスク処理 型番:7(45),誤り訂正レベル:L 白と黒のモジュールがまばらになるように!

マスクパターンの種類 000: (i+j) mod 2=0 001: i mod 2=0 010: j mod 3=0 100: ((i div 2)+(j div 3)) mod 2=0 101: (i*j) mod 2+(i*j) mod 3=0 110: ((i*j) mod 2+(i*j) mod 3) mod 2=0 111: ((i*j) mod 3+(i+j) mod 2) mod 2=0 “X mod 2”はXを2で割った剰余 “X div 3”はXを3で割った商 条件式が真であれば黒(1)で、偽であれば白(0)でマスクを施す

マスク処理 j マスク処理はデータおよび誤り訂正コード語の領域に排他的論理和の演算を施すことで行なわれる(形式情報を含む) マスクは8種類あり、評価基準にしたがって減点法で採点され、一番得点の高いマスク処理が施される ・黒と白の比が1:1 ・特殊なパターンの出現を抑える ・黒(白)の連続配置を抑える i 型番:1(21) マスクパターン:000(市松模様)

*モデル1とモデル2では位置合せパターンが異なる モデル1とモデル2の違い 型番:7(45),誤り訂正レベル:L モデル1 モデル2 *モデル1とモデル2では位置合せパターンが異なる

モデル2の歪み補正 型番:7(45),誤り訂正レベル:L 位置合せパターンにより一定間隔で歪み補正が可能となる

モデル2が優れている点 位置検出パターンが全体に散らばっているため、全体の歪みに強い(モデル1は中心部分の歪みを補正することができない)。 *モデル1より大きな型番のQRコードが作成可能 データおよび誤り訂正コード語が全体に散らばるように配置されるためバースト誤りに強い(モデル1ではデータと誤り訂正コード語が塊として配置される) モデル2の使用が推奨されている

復元能力は全体の長さ(データ+誤り訂正コード語)に対する復元能力である QRコードの誤り訂正レベル 誤り訂正レベル 復元能力(%) L 7 M 15 Q 25 H 30 復元能力は全体の長さ(データ+誤り訂正コード語)に対する復元能力である

型番(バージョン)の比較 型番1(21×21)*最小 型番7(45×45) 型番29(133×133) 型番40(177×177)*最大 型番が1つ増すたびに4モジュール(セル)増える(型番×4+17)。 型番29(133×133) 型番40(177×177)*最大

QRコードの情報量 型番 数字 英数字 8ビット 漢字 1 (21×21) L 41 25 17 10 M 34 20 14 8 Q 27 誤り訂正レベル 数字 英数字 8ビット 漢字 1 (21×21) L 41 25 17 10 M 34 20 14 8 Q 27 16 11 7 H 4 : 40 (177×177) 7089 4296 2953 1817 5596 3391 2331 1435 3993 2420 1663 1024 3057 1852 1273 784

補足:型番情報 型番7以降は型番情報が付加され、タイミングパターンの情報を補足する。 型番(6ビット)およびその誤り訂正コード語(12ビット)が3×6(6×3)モジュールの領域に配置される。 冗長度を増すために2箇所に配置される。 型番:7(45),誤り訂正レベル:L

QRコードの作成条件 ・モデル:2(推奨されている) ・型番:1(最小サイズ) ・誤り訂正レベル:L(復元率7%) ・マスクパターン:000(市松模様) ・モード指示子:1000(漢字モード) ■:位置検出パターン ■:タイミングパターン ■:形式情報 ■:データおよび誤り訂正コード語 □と■:固定 型番:1(21) QRコードの構造 *型番1なので位置合せパターンはない

データの種類(モード指示子) 数字(モード指示子:0001) 0~9(数字) QRコードで扱える主なデータの種類は以下のとおりである。 数字(モード指示子:0001)  0~9(数字) 英数字(モード指示子: 0010)  0~9(数字),A~Z(アルファベット大文字)  スペース $ % * + - . / : 8ビットバイト(モード指示子: 0100)  0016~FF16   *ASCIIコード(制御キャラクタ,アルファベット,半角カタカナなど) 漢字(モード指示子: 1000)  814016(“ ”)~9FFC16(“條”)  E04616(“澁”)~EAA416(“熙”)  *シフトJISコード

QRコードのデータ構造 モード指示子 文字数 データ(情報) モード指示子 文字数 データ(情報) モード指示子 文字数 データ(情報) 終端パターン(0000) *次に解説するデータ圧縮と合わせて、全体のデータ列の長さが最小となるように基本データ列(モード指示子+文字数+データ)に最適化(分割)するのが望ましい

データの節約術(数字) 0(00002)~9(10012)を表すには4ビット必要である(無駄が多い) → 1文字あたり4ビット 0(00002)~9(10012)を表すには4ビット必要である(無駄が多い)  → 1文字あたり4ビット 210=1024 (000~999の数字列を表せる) 3文字を10ビットで表せる(無駄が少ない)  → 1文字あたり3.3ビット 27=128 (00~99の数字列を表せる) 2文字を7ビットで表せる(無駄が少ない)  → 1文字あたり3.5ビット

データの節約術(数字)の例 32ビット ⇒ 27ビット (5ビットお得) 28ビット ⇒ 24ビット (4ビットお得) 例1: 12345678 残りが2文字の場合は7ビットの2進数に変換 123 456 78 (3桁ごとに分割) 0001111011 0111001000 1001110 (各ブロックを10ビットの2進数に変換) 32ビット ⇒ 27ビット (5ビットお得) 例2: 1234567 残りが1文字の場合は4ビットの2進数に変換 123 456 7 (3桁ごとに分割) 0001111011 0111001000 0111 (各ブロックを10ビットの2進数に変換) 28ビット ⇒ 24ビット (4ビットお得)

データの節約術(漢字) 例: 幸 ⇒ 8D4B16 ⇒ 8D4B16 - 814016 ⇒ 0C 0B16 コンピュータは8ビットを1語として処理する 漢字は種類が多く、8ビット1語を基準にすれば、2バイト(16ビット)必要である  → 実際には13ビット(8192文字以下)で十分 例: 幸 ⇒ 8D4B16 ⇒ 8D4B16 - 814016 ⇒ 0C 0B16 ⇒ 0C16×C016 + 0B16 ⇒ 090B16 ⇒ 01001000010112 (13ビットで表す)

作成するデータ列 13ビットに圧縮された漢字コード列 漢字モード:10002 3文字なら:000000112 00002 モード指示子 文字数 データ(情報) 終端パターン 3文字なら:000000112 4文字なら:000001002 5文字なら:000001012 00002 *誤り訂正レベル L かつ 型番 1 の全体のデータ列は19バイトである。従って、上図のデータ列が19バイトに満たない場合は、埋め草コードを補って全体のコード列を19バイトにする

補足:復号誤りの低減(1) 正しい符号語 別の符号語

*符号語と符号語のハミング距離が十分でないとき、誤って別の符号語に誤り訂正されることを防ぐ 補足:復号誤りの低減(2) 誤りであることはわかるが、訂正しない ハミング距離が 近すぎる場合 正しい符号語 別の符号語 *符号語と符号語のハミング距離が十分でないとき、誤って別の符号語に誤り訂正されることを防ぐ