第３章 情報の伝達と通信
• プロトコル (3.2.2) (a)
– 通信の際の決めごと
• 通信の秘密と相手の認証 (3.2.3) (a)
– 暗号 盗聴を防ぐ
– (認証 通信参加者の身元の保証)
– (署名 通信内容の改竄の防止、否認の防止)
1
Shannonの情報理論
通信の最適な符号化の理論
• C.E. Shannon, A mathematical theory of
communications, Bell Syst. Tech. J. 27 (1948),
pp.10-21.
• C. E. Shannon, A mathematical theory of
communications, Bell Syst. Tech. J. 27 (1948),
pp.379-423.
• C. E. Shannon, Communications in the presence
of noise, Proc. IRE 37 (1949), pp.10-21.
• C. E. Shannon and W. Weaver, The Mathematical
Theory of Communication, Univ. Illinois Press,
1949.
2
通話路
符号化
Coding
Ｒ ビット/秒
情報源
復号化
Decoding
A1’
A2’
・・・
Ｈ
事象{A1,A2,…An} が確率
的に生起する
Ｈ 情報源の出す１事象あ
たりの平均情報量（情報源
のエントロピー） ビット
Ｒ 通話路容量
最適な符号化を取
れれば、平均 Ｒ/Ｈ
文字（事象）伝送で
きる
3
3.1.2 情報量の定義
情報量 (ビット bit (binary digit))
（１）確率事象の生起に伴う情報量
確率 p で生起する事象が起こったことを伝達されたとき得る
情報量
H log2 p
ビット
（２）記号列としての情報量 (場合の数の対数)
H log2（記号列のとりうる場合の総数）
ビット
= 0, 1 の記号列の長さ
[注] ８ビット (bit) を１バイト (byte) と呼ぶ。
4
・ 前提：情報量は確率によって決まる。
・ 前提： 情報量の加法則が成立する。つまり
確率事象ＡとＢが独立で、それぞれの生起確率
がp 、 qとするとき 以下が成立する。
f ( p) f (q) f ( pq)
確率p の事象の生起を知って得られる情報量は
f ( p) C log p (C 0は定数)
• 特に f ( p) log2 ( p) をビットという単位で呼ぶ
5
対数関数、指数関数の定義
1
d
1
dt log(x) 1 t
dx
x
d
1
exp(x) log1 ( x) exp(x)
y exp(x)
dx
dx
dy
log(x)
x
log(xy) log(x) log( y )
d
1
1
// log(xy)
y log(xy) log(x) C
dx
xy
x
x 1 log( y ) C //
exp(xy) exp(x) exp(y )
// a exp(x), b exp(y )
x y log(a) log(b) log(ab)
exp(x y ) ab exp(x) exp(y ) //
exp(1) e 2.718...
exp(n) e n n : 整数
6
加法則
f ( pq) f ( p) f (q)
f ( p) f ( p) f (1)
ゆえに
f (1) 0
f ( x ) f ( x)
f (1 / x)
f ' ( x) lim
lim
0
0
1
f (1 / x) f (1)
1
1
lim
f ' (1) C '
x 0
/x
x
x
ゆえに
f ( x) C log(x) (C 0)
• ここでＣの値を決めると、それぞれの単位の
取り方に対応する
1
のとき
C
log 2
C 1
のとき
1
C
log 10
log( p)
f ( p)
log2 ( p) ビット
log 2
f ( p) log p
ニット
log( p)
f ( p)
log10 ( p)
log 10
ディット
情報量の加法性の要請
3
1
1
f ( ) f ( ) f ( )
4
3
4
3
1
1
f ( ) f ( ) f ( )
4
3
4
3
1
1
f ( p) C log p C log( ) C log( ) C log( )
4
3
4
情報量の加法性の再検討
3
2
3
1
f ( ) f ( ) f ( ) f ( ) なぜ成り立たないのか？
4
4
8
4
日本史
日本史
日本史
東洋史
東洋史
東洋史
世界史
です
西欧史
アメリカ史
場合の数 ３
P(東洋史 or 西欧史 or
アメリカ史)= 3/4
東洋史でも
西欧史
西欧史でも
アメリカ史 ありません
アメリカ史です
日本史
西欧史
アメリカ史
場合の数 ２
P(日本史 or アメリカ史)
= 2/4 = 1/2
東洋史
西欧史
場合の数 １
31 3
アメリカ史 P(アメリカ史)=1/4 4 2 8
• 事象ＡとＢが独立でないときは、必ずしも加法則はな
りたたない。
• P(世界史）P（東洋史、西洋史でない）
＝3/4・2/4=3/8
＝1/4＝P(世界史で、かつ東洋史、西洋史でない)
確率事象の独立性
P(A) : 事象Aが起こる確率
P(B) : 事象Bが起こる確率
P(A,B) : A,B がともに（同時に）起こる確率
定義： P(A,B)=P(A)P(B) のとき確率事象A,B は独立であるという。
例 20 面体さいころを振る。
事象A : 4 の倍数の目がでる。 P(A)=5/20=1/4
{4,8,12,16,20}
事象B : 6 の倍数の目がでる。 P(B)=3/20
{6,12,18}
A,B がともに起こる:
P(A,B) ＝ P(A)P(B)
P(A,B)=1/20
{12}
なので A,B は独立な事象ではない。
例
サイコロの目
－log2(1/6) 2.59 ビット
ルーレットの目
－log2(1/100) 6.64 ビット
コイン投げの裏表 －log2(1/2) = 1 ビット
記号列の長さとしての情報量ビットと確率事象の生起の情報
量ビットの同値性
０，１ の２値がどちらも確率 １／２ で生起するとすると、そのひ
とつの値の情報量は 1 ビットになる。このとき ０，１ の特定の
長さ ｎ の記号列が発生する確率は 1 / 2 n で、ゆえにその生起
確率から計算される情報量は log2 (1/ 2n ) n ビットである。
ゆえに、長さ n の 0,1 列の情報量を n ビットとした記号列の長
さで定義した情報量と、整合的である。
13
ほかの記号種類の記号列のメモリ容量(情報量)
・ {a,b,c,…,x,y,z,w}長さ 3 の列 26＊26＊26=17576 通り
・ {0,1,2,3,…,9} 長さ 3 の列 1000 通り
これらを 0, 1 の記号列として表すのに必要な長さは
17576 2n , n log2 17576 14.101... ビット
1000 2n , n log2 1000 9.96578... ビット
14
3.1.3 平均情報量
事象 A1,A2,…,An が独立に確率 (p1,…,pn) で発生する
情報源があったとする。この情報源の１文字あたりの平
均情報量（情報源のエントロピー）を H とすると、それは
n
H pi log 2 pi
(ビット)
i 1
情報源の生起事象を復元可能な符号化によって 0,1
に符号化した列で通知しようとすると、その長さの平均
値を L ビットとすると、常に以下の不等式が成立する。
n
L pi l ( Ai ) H
i 1
15
情報源符号化定理 (Shcannon の第一定理)
H が平均情報量の時任意の 0 に対して平
均符号長 L が以下を満たすような符号化が存
在する。
H L H
つまり、良い符号化を使えば平均符号長が、情報
源のエントロピー（平均情報量） H にいくらでも近く
できるということが保証されている。
16
良い符号化を見つけよう
[ハフマン 符号化]
データに出現する記号の個数を求める。 それが木構造
の葉に相当すると見なし、木を構成する。
(1)まず、葉を含むすべての節点のうち、親を持たないも
のを集める。
(2)その中から、最小の値をもつものと2番目に小さい値
をもつものを取り出す。 それらを子供にもつ新しい節
点を作る。 このとき、新しい節点の値は、両方の子供
の値の和とする。
17
以上を繰り返して根節点まで到達して木が完成される。
(3) 次に、根から順に左右に0と1の値を割り振っていく
（左右のどちらに0と1を与えるかは任意）。
(4) すると、それぞれの葉（記号）に対して、一意にビット
列が与えられる。 この記号とビット列の関係をもとに、も
とのデータの記号をビット列に変換していくことで符号化
が行われる。
ハフマン符号は一意復元可能である。
18
Sample データ ：
DAEBCBACBBBC
出現頻度と割り当てられた符号
記号
Ｂ
Ｃ
A
D
Ｅ
５
３
２
１
１
個数
推定確率 5/12 3/12 2/12 1/12 1/12
符号
0
10
110 1110 1111
19
12桁 を0,1のビット列に符号化
[例]
A:000, B:001, C:010, D:011, E:100
平均符号長 3.0 ビット
と符号化すると
A:1110, B:0, C:10, D:110, E:1111 と符号化すると
均符号長 2.1666… ビット
情報源の情報量
n
H pi log2 pi
i 1
5
5
3
3
2
2
1
1
1
1
( log2 ( ) log2 ( ) log2 ( ) log2 ( ) log2 ( ))
12
12 12
12 12
12 12
12 12
12
2.0545....(ビット )
ハフマン符号化で達成された 2.1666… ビットは、良い値である。
20
同じ例で違う木による符号化
左の木による符号化
12
00
5
B
B ０
1
C １０
7
0
3
C
Ａ １１１
Ｄ １１００
1
Ｅ １１０１
4
0
2
0
1
1
D
1
E
1
2
A
前の例での符号化
B ０
C １０
Ａ １１０
Ｄ １１１０
Ｅ １１１１
21
Huffman Code の例
A
B
確率
Code
0.5
0
0.2
C 0.1
10
1100
D 0.08
1101
E
0.05
1110
F
0.04
11110
G 0.02
111110
H 0.01
111111
0
0.5
A
1.0
0
0.2
B
1
0.5
1
0
0.18
0 1
0.1 0.08
C
D
0.3
1
0
0.12
0.05
0
E
0.04
F
1
0.07
1
0.03
0
0.02
G
1
0.01
H
22
Shannon 最適に近づける －－－反復を用いる
生起確率
ハフマン符号化
A
2/3
1
B
1/3
0
平均符号長
l1 1.0
ハフマン符号化しても、少しも良くなっていない。
情報源のエントロピーの値
2
2 1
1
2
H { log 2 ( ) log 2 ( )} log 2 3 0.918295 .....
3
3 3
3
3
23
生起確率
ハフマン符号
単純符号
AA
4/9
0
00
AB
2/9
10
01
BA
2/9
111
10
BB
1/9
110
11
ハフマン符号化の平均符号長
4
2
2
1 17
l 2' 2 3 3
1.88888 .....
9
9
9
9 9
もとの１文字あたりの平均符号長
1
17
l 2 l2 '
0.944444 .....
2
18
ゆえに以下のように情報源のエントロピーの値により近づく
l1 1.0 l2 0.944444..... H 0.91829....
24
3.5.3条件付きエントロピー
Ｈ（Ｘ｜Ｙ）：Ｙを受信したときのＸのエントロピー
（エントロピーはあいまい度のこと）
H ( X | Y ) p ( y j ) H ( X | y y j )
j
p ( y j )
i
j
p ( xi , y j )
p( y j )
log(
p ( xi , y j )
p( y j )
)
p ( xi , y j ) log( p ( xi , y j )) p ( xi , y j ) log( y j )
i
j
i
j
H ( X , Y ) p ( y j ) log( y j ) H ( X , Y ) H (Y )
j
25
例 情報伝送速度
0.9
1
1
入力側で０，１を1/2 ずつの確
0.
0.
率で毎秒 1000個発生するとし、
0 1
0
1
通信路の誤り確率を 0.1 とす
0.9
る。すると、
1
1 1
1
H ( X ) 1000 ( (log ) log( )) 1000 ビット/ 秒
2
2
2
2
が発信されるので、900 ビット/秒 の情報が受け取れ
るかというとそうではない。出力が 0でもとの信号が正
しく０であった確率は0.9, 出力が０でもとの信号が1で
あった確率は0.1, 信号１についても同様なので, あい
まい度は H ( X | Y ) 1000 (0.9 log 0.9 0.1log 0.1)
469 ビット/ 秒
26
だから伝送速度は R=1000-469=531 ビット/秒であ
る。わずか１割の雑音で情報量はほぼ半分に減っ
てしまうのである。
３．５．４ 相互情報量
Ｉ（Ｘ；Ｙ）： 受信Ｙを観測して得られるＸに関する情
報量
I ( X ;Y ) H ( X ) H ( X | Y )
H ( X , Y ) H ( X ) (Y )
H (Y ) H (Y | X ) I (Y ; X )
27
情報伝達速度 Ｒ：１秒当たり受信によって得られる
情報量 Ｒ を情報伝送速度と呼ぶ。このとき、
R H ( X ) H ( X | Y ) I ( X ;Y )
通信路容量 C： 情報伝送速度 Ｒ は、入力 x i の
確率 pi によって決まる。このＲの最大値を通信路
容量と呼ぶ。
C max{I ( X ;Y ) | p( xi )i 1,...,n }
28
通信路容量
• Xの確率分布を変更したときの相互情報量
I(X;Y)の最大値
• 符号化の方法によって相互情報量を通信路
容量に近づけることが出来る
29
通信路容量Ｃの計算例
情報の構造の一様性を仮定する。すると、
m
H (Y | xi ) p j log p j ,
i 1
m
H (Y | X ) p j log p j
i 1
ゆえに
m
C max{H (Y ) H (Y | X )} max{H (Y )} p j log p j
i 1
Ｈ（Ｙ）が最大の値を取るのは
p( xi ) 1
m
のときだから
m
C log(m) p j log p j
j 1
30
例
１-ｐ
１
ｐ
ｐ
０
１
１－ｐ
０
m＝２，
誤り率： p
この通信路の容量は
C log2 2 (1 p) log2 (1 p) p log2 p
1 (1 p) log2 (1 p) p log2 p
（注：ｐ＝１／２ ならば Ｃ＝０）
31
定理（誤りを持つ通信路の基本定理）
容量 Ｃ の通信路と１秒当たりＫのエントロピーを持
つ情報源があるとき、Ｋ＜Ｃ ならば、情報源の情報
をこの通信路を通して任意に小さい誤り確率で送れ
るような符号化が存在する。
このことは、雑音の混入が避けられない通信路で、誤
りのない通信ができる。しかも、そのときの情報伝送速
度を最大 C まで高められるという、一見常識に反する
ことを意味するので、通信理論にたずさわる人たちを
驚かせた。
32
熱力学的観点から：熱力学のエントロピーと情報エント
ロピーの関係
・ 1 ビット
0.7 k erg （エルグ）
k 1.381023 J / K ボルツマン定数
・ 1 erg は 1 dyn の力で 1cm 物を動かしたときの仕
事・エネルギー のＣＧＳ単位
・ 1 dyn は 1 g の質量に 1cm / s 2 の加速度を与える
力の大きさ （約９８グラムの重さ）
33
3.2 情報通信
クライアント サーバ の例
• WWW
WebブラウザWebサーバ
HTTPプロトコル
• 電子メイル
メイルソフトメイルサーバ
imap, pop, 受信のプロトコル
smtp
送信のプロトコル
34
メイル受信プロトコル(POP と IMAP)
メイルが受信され
POP方式 る
受信サーバ
メイル
IMAP方式
メイル
端末
A
B
A
B
端末Aで読む 端末Bで読む 端末Aで読 端末Bで読
35
む 再びAで む
[参照] HWB 10.4.2 POPとIMAP
3.3.3 通信の秘密と相手の認証
・ 共通鍵暗号（対称鍵暗号）
–送信する暗号化での鍵と受信での復
号化の鍵が同じもの。(シーザー暗号
など)
• 公開鍵暗号（非対称鍵暗号）
–暗号化と復号での鍵が違うもの(RSA
方式など)
36
共通鍵暗号（対称鍵暗号）
• ヴァーナム使い捨て鍵暗号 (Vernam‘s one-time
pad)
全ての受動的攻撃に耐えられる完全秘匿
(perfectly secure)な暗号系
• 欠点
– 文書と同一の長さの真正ランダム鍵が必要
– その鍵が、安全に届けられなければならない（ワ
シントンモスクワ間での信頼できる特使により運
搬されていたそうである）
37
共通鍵暗号
• 一つの鍵で暗号化と復号化が両方できるモデ
ル
鍵を秘密に保つ必要がある
38
38
公開鍵暗号
P Aさんの公開鍵
E Aさんだけが知っている秘密鍵
P で暗号化
平文
E で復号化
暗号文
平文
Aさんだけが復号化できる
平文
E で暗号化
暗号文
P で復号化
平文
発信者が A さんであると分かる
39
P Aさんの公開鍵
E Aさんだけが知っている秘密鍵
K 共通鍵
K で暗号化
平文
K で復号化
暗号文
P で暗号化
共通鍵K
平文
E で復号化
暗号
K
Aさんだけが復号化できる
40
公開鍵暗号（ハッシュ関数）
別掲ＰＤＦファイルへ
41
署名と検証
これによりメッセージの発信者が特定でき、かつメッセージが
改ざんされていないことが分かる。別掲ＰＤＦファイルへ
42
3.3 交換の方式
• 通信の交換の方式
(1) 回線交換
(2) パケット交換
--パケットごとに送られて受信側に到達すると、
受信側でもとに組み立て直す。
– ネット内でのパケットの大きさは、数十から
数千バイト程度の大きさ。
– イーサネット内では 1500 Byte
43
交換方式の特性
交換方式
回線 (電話)
パケット (インター
ネット)
流れる情報の種類
音声のように途切れ
ては困るもの
WWWのように時間
がかかっても構わな
いもの
料金体系
回線を占有している
時間に対して課す
全体の設備を使う権
利に対して課す
端末の能力
単純でよい
データをためる・送り
直す等の能力が必要
交換機の能力
高くないといけない
比較的低い
44
3.4 インターネット
• ネットワークの集合体と通信 (3.4.1)
• 階層プロトコル (3.4.2)
• IPアドレスとポート番号 (3.4.3)
各機器はホスト番号を持つ
ルーターのネット
ワーク番号
ルーター
各機器は同じネットワーク番号
インターネットの世界
46
IPアドレス
• IPアドレス: インターネット内の住所
８ビット. ８ビット．８ビット．８ビットの３２ビット
これらの８ビットは通常０～２５５の整数で表す
（ゆえに 172.16.11.13 のように表示する）
– インターネットに接続するホストは、すべて一意
のアドレスを必ず持つ
– 連続する番号が意味を持つ
• 組織毎にIPアドレスのまとまりで使用を許可される
• ネットワークの住所を表す
47
IPアドレスは、ネットワーク番号と機器のホスト番号をつ
なげたもの。
最初の何ビットがネットワーク番号となるかは、ネットワー
クごとに異なる
IPアドレス
ネットワーク番号
ホスト番号
左から何桁がネットワーク番号になるかは、ネットマスク
で表される。
48
IPアドレスとネットマスクの例
・ 172.16.30.6 / 255.255.255.0
ネットマスクの値が 111....1100000000 で左
から24 個1が並んでいるので２４ビットまでが
ネットワーク番号、その後がホスト番号。
・ 上を 172.16.30.6 /24 と表記しても、同じ意味
である。
49
Web
サーバ
ブラウザ
データ
HTTP
TCP
TCP
IP
IP
ヘッダ データ
50
ＴＣＰ によるデータの分割とパケットの送信、受信
データ
送信側:データの分割
1
3
2
4
インターネット
2
1
4
3
受信側で並べ直してデータを復元する
1
2
3
4
51
パケットを作る
1. TCP がデータの前に TCP ヘッダをつける。
2. IP が TCP ヘッダの前に IP ヘッダをつける
3. IP がさらに IP ヘッダの前に MAC ヘッダを
つける。
4. これでパケットが完成する
MAC
IPヘッダ TCPヘッダ データ
MACアドレスとはイーサ－ネットで使われる機器固有の48ビット論理アド レス。
52
MACアドレス（マック・アドレス、Media Access Control
address）
ネットワーク上で、ネットワーク機器のハードウェアに（原則と
して）一意に割り当てられる物理アドレスである。
MACアドレスの表現には、04-A3-43-5F-43-23 や
32:61:3C:4E:B6:05 といったオクテット表現を用いる。
1オクテットは8ビットに相当する。オクテットに似た情報量の
単位にバイトがある。多くの場合、バイトとオクテットは同じだ
が、1バイトが何ビットに相当するかは文脈によるため、必ず
しも1バイトが8ビットとは限らない。オクテットは必ず8ビットで
ある。オクテットは通信分野でよく出てくる。
A. IP ヘッダ（その中身）
ーネットワーク間通信に使う
1.
2.
3.
4.
5.
生存期間(TTL)
プロトコル番号
送信元 IP アドレス
発信元 IP アドレス
など
54
B. TCPヘッダ（その中身）
アプリケーション間の通信に使う
1. 送信元ポート番号
2. 宛先ポート番号
3. シーケンス番号－このパケットデータ
の先頭位置が、このパケットの何バイ
ト目かを受信側に知らせる
4. ACK 番号
5. など
55
• ポート番号 計算機では、ネットワーク通信
を行うアプリケーションが複数同時に働いて
いる。アプリケーションごとの通信で、相手の
計算機の中のどのアプリケーションと通信す
るのかを特定する必要がある。そのために、
開いているアプリケーションごとにポート番号
（16ビット）を付与して、区別できるようにして
ある。
56
ドメイン名
mail. ecc. u-tokyo. ac. jp
情報基
盤センタ
東京大学
学術
機関
日
本
• 32ビットの IPアドレスは人間には扱いづらい。
• ドメイン名:
IP アドレスのかわりに人間が使うためのもの・
階層化されている
– 各ドメインには、ドメイン名サーバ(DNS)とい
うコンピュータが用意されている
– DNSとインターネットを使って通信して IP ア
ドレスを調べる
（WWW シミュレータを実演してみせる）
57
DNSによるIPアドレスの解決
root
jp
co
de
1
ac
2
3
u-tokyo
klee
uk
4
tu-berlin
WWW
58
© Copyright 2024 ExpyDoc
