情報科学概論
通信と符号化の話
Lecture 8
田中美栄子
ディジタル通信と情報の符号化
• ディジタル方式による情報の記録
→「すべての情報を数字に置き換えて記録する」
という考えを実行する.
例：音楽 CD の場合, 記録すべき音の強さを 65536(＝216) 段階に分ける.
• 文字で文章を送る（英語のアルファベットは大文字,
小文字を区別すると 52 文字ある）
→「52 個の異なる記号の組み合わせで文章を作る」
という考えになる.
必要な文字数 (52 個)の2 進数を用意し,
文章を｛0,1｝ からなる数列に置き換える
ディジタル情報とは何か
• 1 桁の 2 進数は「0, 1」の 2 つ
• 2 桁の 2 進数は「00, 01, 10, 11」の 4 つ
• 3 桁だと 000, 001, 010, 011, 100, 101, 110, 111
となり, これら 8 つにそれぞれ異なる文字を対応させ、
8 文字まで使って文が作れる
4 桁の 2 進数.
• 一般に k 桁の 2 進数は 2のk乗 個ある
•
•
•
•
•
•
•
•
符号
文字
NL (改行)
a
b
c
d
e
２進
0001010
1100001
1100010
1100011
1100100
1100101
１０進
10
97
98
99
100
101
誤り率1万分の１は小さいか？
誤りの正体と符号化
• ディジタル信号にもエラーが起こる
• 0と1という数字を送ると言っても、実際には電
気信号なので、雑音が入ったり、クロックが
ずれたりするだけで 0が1に、1が0に変わっ
てしまう
• 英数半角文字は8ビットで一文字を表すので、
実際には8個の２進数列のうち１個が変化し
ただけで違った文字に化けてしまう
• 誤りの正体は、信号の中で0 と 1 が
入れ替わること
３倍にして送ると安全
• 0→000
• 1→111
と3倍にして送ると、無駄な情報を送らなければ
ならない代わりに、間違いを修正できる
000の一つの0が1に化けても、多数決で元に
戻せる．二つ以上同時に間違うとどうしようも
ないが、そのような確率は非常に低い．
誤り確率が１億分の１だと
• ３つのゼロのうち一つ間違っても元に戻せる
• ２つ以上同時に間違う確率は１億分の１、つ
まり１憶の文字中１個しか間違わない．１頁に
1000文字、200頁分ある本が持つ情報量は
20万文字である．2バイト文字が20万で320
万ビットである．このような本が３冊で1000万
ビット．30冊で１億ビット．つまり誤り率１億分
の１とは、本30冊のうち１文字以下しか間違
わない、非常に正確な情報伝達ができること
誤り検出だけならもっと簡単
• いくら正確でも情報量を3倍使うのでは無駄
• 間違っていることを知るだけなら、
パリティ・ビットを付け加えるだけで済む
• 送ろうとする情報単位ごとに１の個数を奇数
と決めておく．つまりもともと1が奇数個の
情報には0を、１が偶数個含まれる情報には、
1をパリティ・ビットに書き込んでおく
• 送られてきた情報の1の数が偶数ならどこか
に間違いがあるので送りなおして貰えば良い
parity check code 「パリティ検査符号」
• つまり, もともと 2 桁だったものの右に, 余分に 1 桁増やして
3 桁にしているのですが, その規則は
もとの情報に 1 が偶数個なら 0 を付け加え,
もとの情報に 1 が奇数個なら 1 を付け加える
というものです. このように, 誤りの検出や訂正のために
余分な情報を付け加えることを符号化といいます.
この符号化によると「たけやぶやけた」は
• 011 000 110 101 110 000 011
となります. 送り手はこれを送るわけです.
• なお, 上のような規則で符号化を行う符号を
「パリティ検査符号」(parity check code) といいます
符号化の話
いろいろな符号化
• アルファベットが (ほんとうは２６文字あるが）
Ａ，Ｂ, Ｃ, Ｄ の４文字だと仮定しよう
• これを０と１で符号化（２元符号化）するとき
下の表のようにいろいろ考えられる
Ｃ１
Ｃ２
Ｃ３
Ｃ４
Ｃ５
Ｃ６
出現比
Ａ
00
0
0
0
0
0
0.6
Ｂ
01
10
10
01
10
10
0.25
Ｃ
10
110
110
011
11
11
0.1
Ｄ
11
1110
111
111
01
0
0.05
特異符号
• Ｃ６は、ＡとＤの両方に0が対応しており、0を
Ａと読むのかＤなのか不明．このような符号を
特異符号という．（文脈次第で、これでも読め
ることもある）
Ｃ１
Ｃ２
Ｃ３
Ｃ４
Ｃ５
Ｃ６
出現比
Ａ
00
0
0
0
0
0
0.6
Ｂ
01
10
10
01
10
10
0.25
Ｃ
10
110
110
011
11
11
0.1
Ｄ
11
1110
111
111
01
0
0.05
一意復号可能かどうか
• Ｃ5は、特異符号ではないものの、一意復号
できない．
• 0110という信号はＤＢとも読めるし、ACAとも
読めるので紛らわしい
Ｃ１
Ｃ２
Ｃ３
Ｃ４
Ｃ５
Ｃ６
出現比
Ａ
00
0
0
0
0
0
0.6
Ｂ
01
10
10
01
10
10
0.25
Ｃ
10
110
110
011
11
11
0.1
Ｄ
11
1110
111
111
01
0
0.05
瞬時復号可能かどうか
• C1～Ｃ4は、すべて、一意復号できるが、C4
は瞬時複合できない．C４で0110を送ると、
• 0110という信号を復号するときAやBから始
めると途中で困って引き返し、CAと読むまで
に時間がかかる．瞬時性がない．
Ｃ１
Ｃ２
Ｃ３
Ｃ４
Ｃ５
Ｃ６
出現比
Ａ
00
0
0
0
0
0
0.6
Ｂ
01
10
10
01
10
10
0.25
Ｃ
10
110
110
011
11
11
0.1
Ｄ
11
1110
111
111
01
0
0.05
コンパクトかどうか
• C1～Ｃ3は、瞬時符号だが、C2はコンパクト
でない．無駄がある．
• 平均符号長を計算するとC1は２,C2は1.6で
C3は1.55．C2はC3より長くコンパクトでない
Ｃ１
Ｃ２
Ｃ３
Ｃ４
Ｃ５
Ｃ６
出現比
Ａ
00
0
0
0
0
0
0.6
Ｂ
01
10
10
01
10
10
0.25
Ｃ
10
110
110
011
11
11
0.1
Ｄ
11
1110
111
111
01
0
0.05
コンパクト符号の作り方（ハフマン符号の例）
• ハフマン符号はコンパクト
• ハフマン符号の作り方：
1)文字の出現比の順にソートし、
2)出現比の一番小さい文字と2番目に小さい文
字を合流させる．この二つの枝に0と１を割り
つける
3)合流したものを含めて、出現比の小さい二つ
を合流させこの二つの枝に0と１を割りつける
4)これを繰り返して確率が1になったらやめる
ハフマン符号の作り方：2元符号の場合
• 符号語｛A,B,C,D}の出現確率Pが
{PA=0.6,PB=0.25,PC=0.1,PD=0.05}
0.1
0
0.15
0.05
1
1)符号語を出現確率順にソートする
2)確率最小の二つを選び（PCと,PD）,これらを葉とした2分木を
作り節点に二つの確率の和(0.15)を割り当て,一方の枝を0,
他方の枝を1とする
確率の低いものを生成木の一番遠くへもって行くための操作
3)新節点を新しい葉とみなし,これと残りの節点を加えた全部に
対して2)を繰り返す
根から数えて
Aは0
4)確率１の節点一つになれば，これを根として終了
PA=0.6
PB=0.25
PC=0.1
PD=0.05
0
0
0
0.15
1
1
0.4
1
1
(根)
Bは10
Cは110
Dは111
で符号化
できる
ハフマン符号の作り方：3元符号の場合
• 符号語｛A,B,C,D}の出現確率Pが
{PA=0.6,PB=0.25,PC=0.1,PD=0.05}
0.25
0.1
0.05
0
1
0.4
2
1) ソートする
2) 生成確率最小の3つを選び（PCと,PD）,これらを葉とし3分木
を作り節点に3つの確率の和(0.15)を割り当て,3本の枝に
0,1,2を各々与える
確率の低いものを生成木の一番遠くへもって行くための操作
3)新節点を新しい葉とみなし,これと他の節点を加えた全部に
対して2)を繰り返す→しかしあと一点しかないので3分木は作れない
4)確率１の節点一つが残るまで続けて終了（適用不可）
PA=0.6
PB=0.25
PC=0.1
PD=0.05
0
1
0.4
2
失敗 ！
ハフマン符号の作り方：3元符号の場合
• 符号語｛A,B,C,D,E}の出現確率Pが
0.1
0
{PA=0.6,PB=0.25,PC=0.1,PD=0.05, PE=0} 0.05 1
0.4
2
0
1) ソートする
2) 生成確率最小の3つを選び（PC,PD,PE）,これらを葉として
3分木を作り,節点に3つの確率の和(0.15)を割り当て,3本
の枝に0,1,2を各々与える
確率の低いものを生成木の一番遠くへもって行くための操作
3)新節点を新しい葉とみなし,これと他の節点を加えた全部に
対して2)を繰り返す
根から数えて
Aは0
4)確率１の節点一つが残るまで続けて終了
PA=0.6
PB=0.25
0
PC=0.1
PD=0.05
PE=0
1
0
1
2
0.15
1
2
Bは1
Cは20
Dは21
で符号化
できる
では問題
• 4元符号ならどうでしょう？
ハフマン符号の作り方：4元符号の場合
• 符号語｛A,B,C,D,E}の出現確率Pが
{PA=0.6,PB=0.25,PC=0.1,PD=0.05}
1) ソートする
2) 生成確率最小の4つを選び（PA,PBPC,PD）,これらを葉とし
て 4分木を作り,節点に4つの確率の和(1)を割り当て,4本
の枝に0,1,2,3を各々与える
3)新節点を新しい葉とみなし,これと他の節点を加えた全部に
対して2)を繰り返す
根から数えて
4)確率１の節点一つが残るまで続けて終了
PA=0.6
PB=0.25
PC=0.1
PD=0.05
0
1
2
1
3
Aは0
Bは1
Cは2
Dは3
で符号化
できる??
結果は？
• そう、無駄骨でした（4符号のままでも同じ）
2元と3元のどちらが効率的?
• 2元符号の時,A=0,B=10,C=110,D=111
長さ1の符号が60%,長さ2が25%,長さ3が15%
出るのでABCDで書かれた文の長さの期待値
は, 1×0.6+2×0.25+３×0.15=1.45
• 3元符号の時,A=0, B=1,C=20,D=21
長さ1の符号が85%,長さ2が15%出るので
ABCDで書かれた文の長さの期待値は,
1×0.85+2×0.15=1.15
→3元符号の方が効率的（文が短い）
追加
誤り訂正の考え方（１）
• バースト欠損
ランダム欠損
誤 り 検出訂正 （ ま た
誤 り 検出
はエ ラ ー 検 出 訂 正 ）
はエ ラ ー 検 出 訂 正 ）
と は 、 デー タ に符号
と は 、 デ
に符号
誤 り が発生
誤
た場合
場合
に それ を
いは
あ る 。
が発生
に それ
こ と で
正 （ ま た
検出 ・ あ る
は訂正す
あ る 。
こ
で
バースト欠損を
ランダム欠損にする方法
～アミダくじのアイデア～
追加
０
１
２
３
４
５
６
７
８
９
３
５
１
２
６
０
８
９
４
７
© Copyright 2024 ExpyDoc
