スライド 1

応用数学
情報・通信に関する理論
情報通信工学科 3年
C507098
宮崎 公貴
1
目次
• 1.回帰分析
• 2.情報理論
• 3.符号理論
2
1.回帰分析(1)P46,47
• 回帰分析とは相関関係にある2つの変数の
関係を数式で表現し、データを分析、予測す
る統計的手段である。
• 回帰分析は回帰直線と相関係数を用いて求
める。
3
1.回帰分析(2)P46,47
• 相関係数
2つの変数の関連性の強さを表すものは相関係数という。
強い
弱い
弱い
負の相関
-1
負の相関
強い
正の相関
0
無相関
無相関
1
正の相関
完全相関(r=1)
4
1.回帰分析(3)P46,47
• 回帰直線
• 2つの変数の数値を分布にし、その分布の中心を通る直線。
5
2.情報理論(1)P48,49
• 情報源は無記憶情報源と記憶情報源に分けられる
• 無記憶情報源
情報源はある時点で発生した事象の生起確率がそれ以前に発生した事象の生
起確率に依存しない
情報源がA,B,Cの文字をランダムに生成するのであれば、ある時点でAが生成さ
れる確率はそれ以前にどの文字が生成されたかには依存しない。
6
2.情報理論(2)P48,49
• 記憶情報源
情報源はある時点で発生した事象の生起確率がそれ以前に発生した事象の生
起確率に依存する
・マルコフ情報源
0.4
発生文字\次の文字
A
A
0.4 0.2
0.4
B
0.3 0.2
0.5
0.3 0.3
0.4
C
確立行列P
0.4 0.2 0.4
P=
0.3 0.2 0.5
0.3 0.3 0.4
B
C
A
0.2
0.3
0.3
B
0.2
0.4
0.3
0.5
C
0.4
7
2.情報理論(2) 課題
• Cから複数STEP後にAに移動している確率の数式について
次の段階をPで表わせるとすると、1STEP後はP×P=P 2 となり,2STEP後は
P×P×P= P 3 となる。よって100STEP後は P101となる。
P2 
P101
 0.4 0.2 0.4   0.4 0.2 0.4   0.34 0.24 0.42

 
 

 0.3 0.2 0.5    0.3 0.2 0.5    0.33 0.25 0.42
 0.3 0.3 0.4   0.3 0.3 0.4   0.33 0.34 0.43

 
 

 0.333333 0.242424 0.424242


  0.333333 0.242424 0.424242
 0.333333 0.243424 0.424242


P101 よりCから100STEP後にAになる確率は0.333333になる
8
2.情報理論(3)P48,49
• エルゴード情報源
事象の生起確率を長期に観測すると、出発がどのような事象であっても
、それぞれの事象が一定の出現確率に収束する
マルコフ情報源を長期に統計を取ると全ての確率は一定になる。
情報源はA,B,Cの文字であるならば、全ての文字の確率は一定の値
に収束する
9
2.情報理論(3) 課題
• 無記憶情報源 具体例
コインを投げ、表または裏がでても次回投げる時に、表または
裏がでる確率は1/2で変動しない。
• 記憶情報源 具体例
天気が「晴れ」と「雨」の2種類と考える。
・「晴れ」の次の日は「晴れ」の確率が高い
・「雨」の次の日は「雨」の確率が高い
10
3.符号理論(1) P50,51
・情報通信モデル
情報源
送信機
ノイズ
通信路
符号化
受信機
受信者
復号
・通信路符号化
情報ビットに冗長ビットを加える事により誤りの検出や訂正ができるようになる。
・情報源符号化
元の情報データを小さくすることができる。
11
3.符号理論(2) P50,51
• ハミング符号方式
情報ビット4ビットに対して冗長ビット3ビットを付加することにより誤り検知と自己
訂正を受け取り側で行うことができる。
2ビットの誤り検出、1ビットの誤り訂正を行うことができる。
•
情報ビットをX1,X2,X3,X4、冗長ビットをP1,P2,P3とする。
X1+X3+X4+P1=0
+は排他的論理和
X1+X2+X4+P2=0
X1+X2+X3+P3=0
X1,X2,X3,X4を0110であるときP1,P2,P3は次のようになる
0+1+0+P1=0 P1は1
0+1+0+P2=0 P2は1
0+1+1+P3=0 P3は0
12
3.符号理論(3) P50,51
・誤り訂正
送信ビット 0110011
受信ビット 0010011
ハミング符号
X1,X2,X3,P3,X4,P2,P1
X1+X3+X4+P1=0
X1+X2+X4+P2=0
X1+X2+X3+P3=0
①0+1+0+1=0 X1、X3、X4、P1は正しい
②0+0+0+1=1 X1orX2orX4orP2が間違っている
③0+0+1+0=1 X1orX2orX3orP3が間違っている
①に当てはまらず、②、③に入っているX2が間違っている
13
3.符号理論(3) P50,51
• CRC方式
情報ビット列を生成多項式で割った余りを検査用として用いる。
誤り検出のみで、誤り訂正はできない。
情報ビットを110101の6ビットであるとき5乗(6-1次)の多項式F(X)で表わす。
F(X)=1・ X 5  1・ X 4  0・ X 3  1・ X 2  0・ X 1  1・ X 0
=X 5  X 4  X 2  1
生成多項式をG(X)= X 3  X 2  1 とするとF(X)にG(X)の最高次のX 3 を掛けG(X)
を割った余りを求める。
X・3 F ( X ) / G( X )  X 3 ( X 5  X 4  X 2  1) /( X 3  X 2  1)
余りはX 2  1 となり、CRC符号は101となる。
送信するビット列は情報ビット-CRC符号なので110101101となる。
受信側は受信したデータをG(X)で割りきれなければ誤りとわかる。
14
3.符号理論(4) P50,51
• パリティチェック
奇偶検査とも呼ばれ、送信するビット数に対して2進数の合計が偶数か奇数かを
比較することにより、ビットの誤りを検出する。
2bit以上の誤りを検出できないため、CRC方式と再送を併用するか、ハミング符号
など誤り訂正できる方式を用いる。
列と行で1の数が偶数になるように
パリティビットを追加する。
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
1
1
1
1
1
0
0
水
平
パ
リ
テ
ィ
垂直パリティ
15
3.符号理論(5) P50,51
• 情報源符号化(ハフマン符号化)
情報源から発生した情報をその確率的性質を利用して、より効率的に圧縮できる
圧縮対象の記号とその出現確立
記号
A1
A2
A3
A4
A5
A6
出現
確立
0.13
0.3
0.15
0.07
0.25
0.1
(1.0)
0
1
符号化を行った結果の符号語
記号
A2
A5
A3
A1
A6
A4
符号
語
00
10
010
011
110
111
(0.58)
0
(0.42)
1
0
1
(0.28)
A2(0.3)
0
A3(0.15)
1
A4(0.17)
A5(0.25)
A1(0.13)
0
A6(0.1)
1
A4(0.07)
16