第3章 情報とその伝達
§1
§2
§3
§4
§5
情報の符号化
情報源の符号化
情報量とエントロピー
情報の伝達
符号理論と暗号
§1 情報の符号化
情報の符号化
• コンピュータ内部の情報処理は論理回路
で行われる
• 従って、コンピュータ内部では、すべての
情報はビット(0又は1)の組み合わせで表
現されている必要がある
• 情報をビット列に変換することを符号化と
いう
1ビット=2進数に符号化されたデータの一桁
PCの主要構造
ハードディスク
CPU
外部記
憶装置
DVD
ドライブ
FD
ドライブ
バス(BUS)
I/Oポート
主記憶装
置(メイン・
メモリ)
外部記憶装置
• FD(フロッピーディスク)
– 磁性体のディスク(円盤)
– N極・S極の向き⇔{0, 1}に対応
• HD(ハードディスク)
– 磁性体を蒸着したアルミ製ディスク
• ハード=硬い
– N極・S極の向き⇔{0, 1}に対応
• CD・DVD
– レーザー光の反射の量⇔{0, 1}に対応
なぜビット(2進数)なのか?
(1/2)
なぜ2進数か?3進数・4進数…ではないのか?
1. 記憶素子数の最適化
r進数⇒r種類の符号が必要
例:10進数
⇒ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}の10種類の数字が必要
従って、r進数のn桁の数字を表現するためには、
M=nr
(1)
の記憶素子数が必要
r進数のn桁の数字が表現できる数字の大きさ(種類)
Q=rn
(2)
(1)式(2)式からnを消去すると
M=r log Q / log r
Qを留めてMを最小化するrはr=e(自然対数)=2.718…
従って3進数(r=3)が一番最適。2進数(r=2)・4進数(r=4)がそ
れに続く
なぜビット(2進数)なのか?(2/2)
なぜ2進数か?
2.信頼性
電子回路では電圧がある・なしの2値状態の判別が
一番信頼できる
記憶装置の磁石の向き(右・左)も同じ
3. 四則演算が容易
2進数同士のかけ算=桁をずらす操作(シフト)
(1)数の符号化
数の符号化(1/6)
1. 10進数⇒2進数
• 10進数=10で桁上げ
• 2進数=2で桁上げ
2. 2進数で演算(論理回路を使う)
3. 2進数⇒10進数
(3)10
+ (5)10
(8)10
(0011)2
+ (0101)2
(1000)2
数の符号化(2/6)
2進数
2で割った
商と余り
2で割った
商と余り
10進数⇒2進数
(i)2で割った余りを下の桁の値に
(ii)商がゼロでなければ更に2で割る
(iii)以上を繰り返す
2進数⇒10進数
(111)2=(100)2+(010)2 +(001)2
=22+2+1=7
数の符号化(3/6)
問題:5本の指で数を表現することを考えよう。
各指の使い方は、伸ばした状態か、折り曲げた
状態かのどちらかしかないとする。表現できる
数はゼロから最大いくつまでか?
数の符号化(4/6)
小数の2進数表現
(0.1)10=1/10, (0.01)10=1/100, (0.001)10=1/103と同じく
(0.1)2=1/2, (0.01)2=1/22, (0.001)2=1/23等とする
(注)10進数で有限小数であっても2進数では循環
小数になることがある
例: (0.4)10=(0.01100110011…)2
従って、一端2進数にして計算するコンピュータの
計算には誤差を含んでいることになる
数の符号化(5/6)
補数表示(負の数の表現法)
十進数
補数表現
ビット反転
十進数
補数表現(ビット反転+1)
-8
1000
7
0111
1000
-7
1001
6
0110
1001
-6
1010
5
0101
1010
-5
1011
4
0100
1011
-4
1100
3
0011
1100
-3
1101
2
0010
1101
-2
1110
1
0001
1110
-1
1111
0
0000
数の符号化(6/6)
補数表示を使った減算
– 減算=負の数の和
(例)5-2 =5+(-2)
-2の補数
表現
0101 (510)
+)
1110 (-210)
10011 (310)
桁あふれ
は気にし
ない
(2)文字の符号化
文字の符号化(1/5)
下図のように、文字を符号化する(ビット列に
対応させる)のに何ビット必要か?
1ビット
2ビット
3ビット
4ビット
a
○
○○
○○○
○○○○
b
●
○●
○○●
○○○●
c
●○
○●○
○○●○
d
●●
○●●
○○●●
e
●○○
○●○○
f
●○●
○●○●
g
●●○
○●●○
h
●●●
○●●●
i
●○○○
j
●○○●
k
●○●○
文字の符号化(2/5)
アルファベット(大文字・小文字)
52文字
清音(ア、カ、サ、タ、ナなど)
47文字
カ 濁音(ガ、ザ、ダ、バなど)
タ
カ 半濁音(パ、ピ、プ、ぺ、ポ)
ナ
拗音(小さいァ、ィ、ャ、ョな
ど)
句読点(ピリオド、コンマ)
合計
20文字
5文字
9文字
2文字
135文字
2<22<23<24<25<26<27(=128)<135<28(=256)
文字の符号化(3/5)
1bit=2進数に符号化されたデータの一桁
ところが、1bitは文字データの単位としては小さ過ぎる
そこで、新しい単位が導入された
•1B(バイト)=符号化された英文1文字の長さ(=8ビット)
•2B(バイト)=符号化された日本語1文字の長さ(=16ビット)
(注)16ビットは、256×256(=65536)通りの場合が
表現可能
文字の符号化(4/5)
演習:以下の測定実験を行いファイルの大きさが正しく
評価できることを確認しなさい。
• 「メモ帳」(エディタ)
1行だけのファイルのデータ量(何バイト?)
2行あるファイルのデータ量(何バイト?)
3行あるファイルのデータ量(何バイト?)
• 「Word」(ワープロ)
上と同じ文字数のファイルを作成しデータの大きさを比
較せよ
英文1文字=1バイト、和文1文字=2バイト
文字の符号化(5/5)
大きな文字データを表す場合の単位
1024 バイト=1Kバイト (K:キロ)
1024Kバイト=1Mバイト (M:メガ)
1024Mバイト=1Gバイト (G:ギガ)
1024Gバイト=1Tバイト (T:テラ)
問い 1,000,000バイトは何Mバイトか?
答え 約0.954Mバイト
(3)音・画像の符号化
アナログ情報の符号化
• アナログとデジタル
– 指針のある時計 v.s デジタル時計
– レコード v.s CD(Compact Disk)
• 変化するアナログ量の符号化
– 音声・画像の符号化
– 標本化
↓
量子化
↓
符号化
15
10
5
標本化
8.5
13.5
4.7
7.9
量子化
9
14
5
8
符号化 1001 1110 0101 1000
「ペイント」の図形情報(1/3)
(作業)
(1)図形(例えば、円)を描く
(2)「表示」メニュー「拡大」「拡大する」
(3)「表示」メニュー「拡大」「グリッドを表示」
ペイントで描く図形の情報
=「方眼用紙に色を付ける」方法
(ビットマップ方式・ラスター方式)
他の例:テレビ・デジタルカメラ・スキャナー
用語:ピクセル(画素)=方眼用紙の升目
「ペイント」の図形情報(2/3)
(作業)
(1)「変形」メニュー「キャンバスの色とサイズ」を実行し、キャン
バスの縦幅と横幅をピクセル単位で指定する
(2)「ファイル」メニュー「保存」を実行し、 「ファイルの種類」をビッ
トマップ形式にして、適当なファイル名前で画像を保存する
(3)ファイルのプロパティを見ることにより、ファイルのデータ量を
確認する
(4)1ピクセル当たりのデータの大きさを確認する
(注)1ピクセル当たりのデータの大きさ
=ファイルの大きさ
÷(縦幅(ピクセル単位)×横幅(ピクセル単位))
「ペイント」の図形情報(3/3)
1ピクセル当たりの
=
データの大きさ
ファイルの種類
表現できる
色の種類
1ピクセル当りのデータの大きさ
24ビットビットマップ 1ピクセル=3バイト((1バイト=英語1文字))
(ビットマップはWindows専 224(3バイト=24ビット)種類
用のドットマップ形式の名
=28+8+8= 28 ×28×28=256×256×256
前)
(赤256階色×緑256階色×青256階色)
256色ビットマップ
=16,777,216色
1ピクセル=1バイト
28(1バイト=8ビット)種類=256色
符号化のまとめ
• 数字・文字・画像・音楽etcが符号化により
bitで表現される
• コンピュータは元々計算を自動化すること
を目的として考案・発明された
• ところが、10進数ではなく2進数を計算す
るようになったコンピュータは、数字以外の
情報も符号化してしまえばbitとして同じで
あるため、数字以外の情報を処理できる
道具に進化していたのである
§4 情報の伝達
さまざまなコミュニケーション
• 目的:
考え・認識・感情などの情報をある人から別の
人に伝え物事を運ぶ
• 方法:
情報を送る人と受ける人との間に通信チャンネ
ル(通信路)設け情報伝送を行う。
例:直接会話、手紙、電話による会話、
FAX、電子メールetc
コミュニケーションの危さ
通信チャンネル
OR
Alice
Bob
送り手(Alice)の頭の中にあるものがそのまま転送されるわけ
ではない。表現手段により一度別の形態に変換され通信
チャンネル(伝送路)を通して送られる。そして、その後受け
手(Bob)の中で再構築されなければならない。
"instruction"(=教育)の起源in+struct(=in+build)はまさしくこうい
う状況を表現している。
ダウンロード

第3章 情報とその伝達