コンピュータリテラシ 6. 情報の表現

文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
コンピュータリテラシ
6. 情報の表現
Chris Plaintail
2013
1 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
目次
1
文字コード
2
アナログからデジタルへ
3
画像データの表現
4
さまざまな画像データ
5
音声データの扱い
6
データの圧縮
2 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
情報の表現
コンピュータによる情報処理が基礎においているの
は，いうまでもなく デジタル技術 である．デジタル技術
においては諸量（情報）を 離散的に (0, 1, 2, 3, . . . ) 表す
点が大きな特徴である．たとえば文字の情報はひとつひ
とつが（離散的な）数に対応づけられて処理されるが，
連続データ（ アナログ ）として扱われてきた画像や音声
も離散的に扱われている．様々な情報を数に対応させる
ことを 符号化 とよぶ．ここでは符号化およびその応用と
して 圧縮技術 や 暗号 についても学ぶ．
3 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
A
B
C
D
E
F
G
H
0
8
>
>
>
>
>
>
>
<
>
>
>
>
>
>
:
0
1
8
>
>
<
>
>
:
8
>
>
<
>
:
0
1
0
1
0
1
0
1
0
1
0
1
0000
0001
0010
0011
0100
0101
0110
0111
0
1
2
3
4
5
6
7
4 / 73
文字コード
アナログからデジタルへ
A
B
C
D
E
F
G
H
a
b
d
e
f
g
h
0
1
画像データの表現
8
>
>
>
>
>
>
<
>
>
>
>
>
>
:
8
>
>
>
>
>
>
<
>
>
>
>
>
>
:
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
0
1
0
1
8
>
>
<
>
:
8
>
>
<
>
:
8
>
<
>
>
:
8
>
>
<
>
>
:
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
5 / 73
文字コード
アナログからデジタルへ
A
a
B
b
C
D
d
E
e
F
f
G
g
H
h
0
1
画像データの表現
8
>
>
>
>
>
>
<
>
>
>
>
>
>
:
8
>
>
>
>
>
>
<
>
>
>
>
>
>
:
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
0
1
0
1
8
>
>
<
>
:
8
>
>
<
>
:
8
>
<
>
>
:
8
>
>
<
>
>
:
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
6 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
文字の処理：文字集合・符号化
アルファベット・数字・記号 < 128 文字 ↔ 7 bit
⇒ 半角英数
+ 制御文字 (CR, LF, DEL,...): ASCII
:::::::::
⇒ ISO/IEC 646 : \, ˜
日本語（カナ） < 128 文字 ↔ 7 bit
⇒ 半角カナ
→×
:::::::::
ASCII + ドイツ語・アラビア語・ギリシア語 · · ·
⇒ ISO/IEC 8859
256 文字 ↔ (7 + 1) bit = 1 Byte
7 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
2 Byte = 16 bit ↔ 65, 536 文字
⇔ 康煕字典・諸橋漢和字典・今昔文字鏡 ⇒ 全角文字
:::::::::
文字集合
:::::::::
JIS X 0208 : 94(区) × 94(点) = 8, 836 字
非漢字 (1 - 8 区：524 字)
第 1 水準 (16 - 47 区：2.965 字)
第 2 水準 (48 - 84 区：3,390 字)
JIS X 0212 : 補助漢字（第 3 水準・第 4 水準）
JIS X 0213 : :::
面・区・点：11,233 字
8 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
国際符号化文字集合 JIS X 0221
= ISO/IEC 10646 (Universal Coded Character Set)
（群）
・面・区 (0-255) ・点 (0-255)
JIS X 0213 : 面区点
JIS X 0208 : 区点のみ
ASCII : 点のみ
符号化方式 : ISO/IEC 2022
2 バイトの文字集合を切り替える
エスケープシーケンス
:::::::::::::::::::::
9 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
文字集合と符号化方式
JIS X 0208 : ISO/IEC 2022-JP,
Shift-JIS, EUC-JP
JIS X 0213 : ISO/IEC 2022-JP-2004
Unicode : UTF-8, UTF-16
ISO/IEC 8859
Big5
EUC (EUC-JP, EUC-KR, GB2312)
10 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
unicode (21 bit)
文字集合
BMP (16 bit) = UCS-2
異体字セレクタ
符号化方式
UTF-8 (1 - 4 Bytes)
UTF-16 (BMP : 16 bits, ohter : 2×16 bits)
CID (Adobe)
IME パッド
11 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
ブラウザ：文字エンコーディング
文字化けサンプル
環境依存文字
Windows XP まで
Windows Vista 以降
Shift JIS
unicode
JIS X 0208-1990
JIS X 0213-2004
12 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
文字コード
字義・字体・異体字・包摂・字形・例示字形
「斎」(3A58) と「斉」(4046) は字義が異なる．
「齋」(6337) と「斎」(3A58) は
字義が同じで字体が異なる（異体字）．
「齊」(736E) と「斉」(4046) は
字義が同じで字体が異なる（異体字）．
「高」島屋・「葛」飾区と「葛」城市
「吉」野家
13 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
問題 I
1
使える文字がちょうど 16 種あるとき，そのうちの 1 文字だ
けを伝えるために何 bit 必要か？（たとえば A, B, C, D, ..., O, P
のうちどれか 1 文字）また，これらから 2 文字を取り出して
順に伝えるためには何 bit 必要になるか？
2
ASCII (ISO 646) のコード表をみて，どんな文字がどんな符号
に割り当てられているか確認しよう．たとえばアルファベッ
トの「A」や「a」が 10 進数のどんな数に対応しているか．
またそれらは 2 進数でどのように表現されているか？
3
字義・字体・字形・包摂・異体字，それぞれの言葉の意味を説
明せよ．
4
コンピュータで正しく表示されない文字にどんなものがある
か．それらは，なぜ正しく表示されないのか．
14 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
問題 II
5
異体字に別々のコードが割り当てられている例を探してみよ．
6
ブラウザで表示されているページのエンコードを変えてみて，
表示がどのように変化するか確かめよ（わざと文字化けさせ
てみよ）．
15 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
データの圧縮
非可逆圧縮（ロスのある圧縮）
画像圧縮：JPEG (.jpg), GIF (.gif). . .
⇒ GIMP でファイル保存
音声圧縮：MP3, AAC, WMA, . . .
⇒ audacity でファイル保存
可逆圧縮（ロスのない圧縮）
ZIP (.zip), LHA (.lzh), gzip (.gz), bzip2 (.bz2),...
⇒ 送る-圧縮フォルダ (zip)
16 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
データの圧縮
画像ファイル
JPEG : DCT + 視覚効果 + Huffman
GIF : LZW
BMP : RLE
音声ファイル
MP3 : DCT + 聴覚効果 + Huffman
可逆圧縮
ZIP : LZSS + Huffman
17 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
データの圧縮
画像・音声の情報処理
周波数特性
対数圧縮
差分予測・差分 PCM
符号化
連長圧縮 RLE
ハフマン符号化（エントロピー符号化）
辞書式 (LZW, LZ77, LZSS)
18 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
データの圧縮
連長圧縮
BBBBBBBBBWWBBBBBBBWWWWWWWBBB
⇓
B9W2B7W8B3
19 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
データの圧縮
ハフマン符号化
8
文字
A
B
C
D
出現回数
400
200
100
100
符号
0
10
110
111
A= 400
400
B= 200
200
C= 100 D= 100
1 × 400 + 2 × 200 + 3 × 100 + 3 × 100 = 1400 bits
2 × (400 + 200 + 100 + 100) = 1600 bits
20 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
データの圧縮
ハフマン符号化
1
文字 A, B, C, D のみを含む文書に対して前ページのような符号
化の規則を適用しているものとすると次の符号列はどんな文
字列を表しているか．
10111111111110100
2
文字列 ABCDABAA を前ページのような規則にしたがって符号
化するとどうなるか．また，各文字を A(00), B(01), C(10),
D(11) と符号化するとどうなるか．
21 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
データの圧縮
辞書式
The long and winding road
that leads to your door
will never disapear
⇒
2681/4 1514/11 96/44 2997/39 2238/62
2679/18 1455/8 2720/57 3039/17 749/50
2992/55 1726/18 716/33
22 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号
秘匿と認証
古典暗号
シーザー暗号, etc.,...
現代暗号
対象鍵暗号（共通鍵暗号）
：
AES, DES, etc.,...
非対称鍵暗号（公開鍵暗号）
：
RSA, ECC, ElGamal
23 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：シーザー暗号
IBM −→ HAL
DaitoBunkaUniversity
−→ FckvqDwpmcWpkxgtukva
A computer is a general device that can be programmed to
carry out a finete set of arithmetic or logical operations.
−→
D frpsxwhu lv d jhqhudo ghylfh ...
24 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号
アルゴリズム
暗号化：平文 −→ 暗号
⇑
鍵
⇓
復号化：暗号 −→ 平文
アルゴリズム
25 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：現代暗号
アルゴリズム：公開
鍵
対称鍵（共通鍵）暗号 DES, AES, RC4
同一の鍵（非公開）で暗号化・復号化
ストリーム暗号 (RC4)
ブロック暗号 (DES, AES)
非対称鍵（公開鍵）暗号 RSA, PGP
異なる鍵で暗号化・復号化，鍵の一方を公開
共通鍵を暗号化するために使われる
実装
SSL/TLS : RC2, RC4, triple DES, AES
WEP, WPA : RC4
26 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：現代暗号
ストリーム暗号：RC4
秘密鍵 p（初期値として） ⇒ 疑似乱数列 k
暗号化：平文と排他的論理和 : m = M ⊕ k
復号化：暗号と排他的論理和 : M = m ⊕ k
排他的論理和：コーヒーまたは紅茶
論理和：6 才未満または女性
論理積：体重 47 kg 以上かつ身長 160 cm 以上
排他的論理和 a ⊕ b
論理和 a + b
論理積 a · b
a\ b 0 1
a\ b 0 1
a\ b 0 1
0
0 1
0
0 1
0
0 0
1
1
1
1 0
1 1
0 1
27 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：現代暗号
ストリーム暗号：RC4 — GNU Octave による計算例
準備（秘密鍵） p を初期値として疑似乱数列をつくる．
p=13 : 適当な整数 p を設定
rand("seed", p) : 疑似乱数を p で初期化
rand(1, 8) : 1 行 8 列の疑似乱数（ 0 ∼ 1 の値）
int32(rand(1, 8)) :
各要素の小数点以下を四捨五入 (0 or 1)
num2str(int32(rand(1, 8)),"%d") :
0 and/or 1 からなる数値配列を文字列に変換
bin2dec(num2str(int32(rand(1, 8)),"%d")) :
0 and/or 1 からなる文字列を対応する十進数に変換
28 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：現代暗号
ストリーム暗号：RC4 — GNU Octave による計算例 1
平文：
M=65
:::::
2 進表現：dec2bin(M)
乱数の種：
p=13
:::::::::
疑似乱数の初期化：
rand("seed", p)
::::::::::::::::::
疑似乱数発生：
::::::::::::::
k=bin2dec(num2str(int32(rand(1,8)),"%d"))
2 進表現：dec2bin(k)
暗号化：
m=bitxor(M, k)
:::::::
2 進表現：dec2bin(m)
復号化：
bitxor(m, k)
:::::::
29 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：現代暗号
ストリーム暗号：RC4 — GNU Octave による計算例 2
平文：
M=toascii("A")
:::::
乱数の種：
p=13
:::::::::
疑似乱数の初期化：
rand("seed", p)
::::::::::::::::::
疑似乱数発生：
::::::::::::::
k=bin2dec(num2str(int32(rand(1,8)),"%d"))
暗号化：
m=bitxor(M, k)
:::::::
復号化：
char(bitxor(m, k))
:::::::
30 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：現代暗号
ストリーム暗号：RC4 — GNU Octave による計算例 3
平文：
M=bin2dec("10001110")
:::::
乱数の種：
p=13
:::::::::
疑似乱数の初期化：
rand("seed", p)
::::::::::::::::::
疑似乱数発生：
::::::::::::::
k=bin2dec(num2str(int32(rand(1,8)),"%d"))
暗号化：
m=bitxor(M, k)
:::::::
復号化：
dec2bin(bitxor(m, k))
:::::::
31 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
秘密鍵方式における「安全な鍵配送」の問題
公開鍵のアイディア (1976)
Whitfield Diffie, Martin Hellman,
”New Directions in Cryptography”
実装 (1977)
Ronald Rivest, Adi Shamir, Lenonard Adelman,
”A Method for Obtaining Digital Signatures and Public-Key
Cryptosystems”
暗号技術の禁輸（国家による情報管理）
特許 (RSA Data Security inc.)
普及と自由化 (PGP) Phillip Zimmermann
32 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
秘匿
n α ← p, q, β
#
౏㐿㎛
$
n, α
⒁ኒ㎛ p, q, β
m
M
ᓳภൻ
M
ᥧภൻ
33 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
認証
n α ← p, q, β
#
$
౏㐿㎛
⒁ኒ㎛
ᥧภൻ
ᓳภൻ
34 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
鍵の生成
p, q : 巨大な素数
n = pq
α : 適当な整数
1 以外に (p − 1)(q − 1) と共通の約数をもたない
β : 整数
αβ を (p − 1)(q − 1) で割ったあまりが 1 である
35 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
鍵の生成 — maxima による計算
r() := random(2ˆ8);
p : next_prime(r());
q : next_prime(r());
n : p*q;
factor(n);
a : next_prime((p-1)*(q-1));
gcd(a, (p-1)*(q-1));
b : inv_mod(a, (p-1)*(q-1));
36 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
秘匿通信
平文データ M
公開鍵で暗号化
m = ( M a を n で割ったあまり)
秘密鍵で復号化
M ′ =(mb を n で割ったあまり)
37 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
秘匿通信 — maxima による計算
平文データ（例） M : 65;
暗号化
復号化
m : mod(Mˆa, n);
mod(mˆb, n);
38 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
認証
平文データ M
秘密鍵で暗号化
m = ( M b を n で割ったあまり)
公開鍵で復号化
M ′ =(ma を n で割ったあまり)
39 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
認証 — maxima による計算
平文データ（例） M : 65;
暗号化
復号化
m : mod(Mˆb, n);
mod(mˆa, n);
40 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：RSA 暗号
安全性
公開鍵 n, α から秘密鍵 p, q, β を知るには...
素因数分解 n = pq → p, q が必要
r() := random(2ˆ8);
p : next_prime(r());
q : next_prime(r());
n : p*q;
factor(n);
41 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
暗号：GPG
原理はさておき...
GPG(GNU Privacy Guard) で暗号を利用しよう．
42 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
レンダリング
音楽 ⇐ MIDI データ (楽譜) / 音源
テキスト ⇐ 文字コード / フォント
3D 画像 ⇐ シーン記述言語
リッチテキスト ⇐ マークアップ言語
ウェブページ
Postscript
TEX
43 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
44 / 73
文字コード
アナログからデジタルへ
画像データの表現
さまざまな画像データ
音声データの扱い
データの圧縮
45 / 73