前回の練習問題
ハフマン符号を構成するプログラムを作成せよ
さらに，拡大情報源に対して利用できるよう改良せよ
優先度付きキューと呼ばれるデータ構造の典型的な用法
「データの登録」「優先度最大データの取り出し」の２種の操作
符号木を「データ」，確率を「優先度」とし，
「木を二つ取出し，一つに併合して再度登録」を繰返す
1
chapter 3:
エラーから情報を守る
2
chapter 3の目的
通信路で発生する誤りを検出し，訂正する技術について学ぶ
現実の通信環境...
“送信情報 = 受信情報” の保証はない
“送信情報 ≠ 受信情報” ... 誤りが発生するかも
誤りを「減らす」ことはできても，完全に「なくす」ことは難しい
無線通信 ... 送信電力の増加 ⇒ 消費電力の増加
CD, DVD ... 記録密度の抑制 ⇒ データ容量の低下
3
通信路符号化
誤りの発生... 送信情報の一部が，途中で失われることに相当
途中で一部が失われても，必要十分な量の情報が届くよう，
余分な情報を事前に上乗せして送信すればよい
＝
な情報を付加する
やみくもに冗長な情報を付加すればよいというわけではない
誤りの訂正に効果的な，適切な符号化方式が必要
⇒ 通信路符号化
4
2つの符号化
chapter 2 ... 情報源符号化
情報源からの出力に対する符号化
コンパクトな情報表現を与える
chapter 3 ... 通信路符号化
通信路への入力に対する符号化
誤りに強い情報表現を与える
どちらも「符号化」だが，目的とする方向性が異なる
5
「符号化」の複層構造
アプリケーション
送信者
受信者
情報源符号化
符号化
復号
情報保護
暗号化
復号
通信路符号化
符号化
復号
通信路
6
通信路のモデル
以下の議論では，デジタル通信路を仮定
入出力には，記号が用いられる
1記号の入力に 対し，必ず1記号の出力が得られる
遅延や消失は，モデルとしては考えない
入力記号と出力記号の関係は，確率的に与えられる
入力
(送信側）
変調器
デジタル
通信路
アナログ
通信路
出力
（受信側）
復調器
7
2元対称通信路
2元対称通信路 (binary symmetric channel, BSC)
入力記号 = 出力記号 = {0, 1}
確率 𝑝で，記号の 0 と 1が反転するような通信路
p ＝ビット誤り率（通常は p < 0.5）
0
0
出力
入力
1
1–p
p
p
1–p
1
00000 を送信したとき...
00000が受信される確率 = 1 − 𝑝 5
00001が受信される確率 = 1 − 𝑝 4 𝑝
00011が受信される確率 = 1 − 𝑝 3 𝑝2
...
8
通信路符号化：準備
本講義では，以下のような通信路符号化方式を考える
符号化器への入力： 𝑘 ビットのバイナリデータ
符号化器の出力（符号語）： 𝑛 ビットのバイナリデータ
𝑘<𝑛
データ = 系列 = ベクトル
𝑏1 𝑏2 ⋯ 𝑏𝑚 = (𝑏1 , 𝑏2 , … , 𝑏𝑚 )
加減算はビット単位の2進演算
001 + 101 = 100
XORと考えてもOK
𝑉𝑘
𝑉𝑛
9
符号化と復号
符号化： 任意の 𝑘 ビットから，𝑛 ビットの符号語を計算する
𝑉𝑘
𝑉𝑛
符号化
復号
符号 𝐶＝ 符号語の集合
復号： （誤りを含む可能性のある）任意の 𝑛 ビットから，
【誤り検出】 誤りの有無を判定する
【誤り訂正】 送信されたであろう符号語を推定する
復号が，符号化の逆操作になっていないことに注意
10
良い符号とは？
𝑉𝑛
符号 𝐶 は
の部分集合
𝑉 𝑛 には 2𝑛 個の系列
𝐶 には 2𝑘 個の系列（符号語）
2𝑛
全部で 𝑘 通りの符号が存在
2
𝑉𝑛
𝑉𝑘
00
01
10
11
000
011
101
110
𝐶
どの符号を選ぶのが良いか？
誤り訂正能力が高いこと
符号化，復号操作が容易に行えること
線形符号 (linear code) と呼ばれる符号が有利
11
この後の筋書き
線形符号
定義と基本的な性質
線形符号の符号化
線形符号の復号
ハミング符号
線形符号の性能評価
今回
次回
定義の前に，簡単な例を２つ紹介...
12
偶パリティ符号
偶パリティ符号（even parity code）の符号化操作：
情報 𝑎1 , 𝑎2 , … , 𝑎𝑘 ∈ 𝑉 𝑘 に対し...
𝑝 = 𝑎1 + 𝑎2 + ⋯ + 𝑎𝑘 mod 2 を計算する
(𝑎1 , 𝑎2 , … , 𝑎𝑘 , 𝑝) を (𝑎1 , 𝑎2 , … , 𝑎𝑘 )の符号語とする
𝑘 = 3の場合 000
001
010
011
100
101
110
111
p=0+1+1=0
0000
0011
0101
0110
1001
1010
1100
1111 符号 C
13
偶パリティ符号の特徴
0000
0011
0101
0110
1001
1010
1100
1111
符号 C
符号長は 𝑛 = 𝑘 + 1
符号化操作は，
もともと送りたかった情報記号の後に，
検査記号（冗長記号）を付け足す
情報記号
1010
検査記号
符号語に含まれる１の個数は，かならず偶数
情報記号中に１が偶数個 ⇒ 𝑝 = 0
情報記号中に１が奇数個 ⇒ 𝑝 = 1
（符号語の中に発生する奇数ビットの誤り検出が可能）
14
水平垂直パリティ検査符号
水平垂直パリティ検査符号の符号化：
情報記号を長方形状に並べる
水平方向および垂直方向に偶パリティ符号化を行う
冗長記号を一次元に配列し，情報記号に付加する
k = 9 の場合： (a1, a2, ..., a9) の符号化
a1
a2
a3
p
1
a4
a5
a6
p2
a7
a8
a9
p3
q1
q2
q3
p1 = a1 + a2 + a3
p2 = a4 + a5 + a6
p3 = a7 + a8 + a9
q1 = a1 + a4 + a7
q2 = a2 + a5 + a8
q3 = a3 + a6 + a9
r = a1 + a2 + ... + a9
r 符号語は
(a1, a2, ..., a9, p1, p2, p3, q1, q2, q3, r)
15
符号化の例
011100101 を符号化すると，符号語は 0111001010100101
0
1
1
0
1
0
0
1
1
0
1
0
0
1
0
1
0111001010100101
情報記号
検査記号
特徴
水平垂直パリティ検査符号は，組織符号
𝑘 = 𝑎𝑏 のとき，符号長は 𝑛 = 𝑎𝑏 + 𝑎 + 𝑏 + 1
（符号語の中に発生する１ビットの誤り訂正が可能）
16
誤り訂正の原理
受信した系列を，符号化のときと同じ順番で並べ直す：
誤りナシ ⇒ 全ての行，列は偶数個の１を含む
１ビット誤りが発生
⇒ 1が奇数個の行，列が，1個ずつ発生
⇒ その行と列の交差するところが誤り
010110101
受信語
011110101
誤りを訂正
0
1
1 偶
0
1
0 奇
1
0
1 偶
奇
偶
偶
17
線形符号について
線形符号
定義と基本的な性質
線形符号の符号化
線形符号の復号
ハミング符号
線形符号の性能評価
18
線形符号の定義
以下のように構成される符号を線形符号と呼ぶ：
符号語＝（𝑘ビットの情報記号）＋（𝑚ビットの検査記号）
(𝑥1 , 𝑥2 , … , 𝑥𝑘 , 𝑝1 , 𝑝2 , … , 𝑝𝑚 )
情報記号 検査記号（冗長記号）
検査記号は，情報記号の線形式により求められる
𝑝1 = 𝑎1,1 𝑥1 + 𝑎1,2 𝑥2 + ⋯ +𝑎1,𝑘 𝑥𝑘
𝑝2 = 𝑎2,1 𝑥1 + 𝑎2,2 𝑥2 + ⋯ +𝑎2,𝑘 𝑥𝑘
⋮
𝑝𝑚 = 𝑎𝑚,1 𝑥1 + 𝑎𝑚,2 𝑥2 + ⋯ +𝑎𝑚,𝑘 𝑥𝑘
(𝑎𝑖,𝑗 ∈ 0,1 )
19
線形符号の例
偶パリティ符号：(𝑥1 , 𝑥2 , 𝑥3 , 𝑝1 )
𝑝1 = 𝑥1 + 𝑥2 + 𝑥3
水平垂直パリティ検査符号：(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑝1 , 𝑝2 , 𝑝3 , 𝑝4 , 𝑝5 )
𝑥1
𝑥2 𝑝1
𝑝1 = 𝑥1 +𝑥2
𝑝2 =
𝑥3 𝑥4 𝑝2
𝑝3 = 𝑥1
𝑝3
𝑝4 =
𝑝4 𝑝5
𝑥3 +𝑥4
+𝑥3
𝑥2
+𝑥4
𝑝5 = 𝑥1 +𝑥2 +𝑥3 +𝑥4
20
線形符号の性質
符号 𝐶 が線形符号であれば...
定理１： 0, … , 0 ∈ 𝐶
証明：
検査記号は情報記号の線形式で定まるため，
𝑥1 , … , 𝑥𝑘 = (0, … , 0)なら 𝑝1 , … , 𝑝𝑚 = (0, … , 0)，
よって 𝑥1 , … , 𝑥𝑘 , 𝑝1 , … , 𝑝𝑚 = 0, … , 0 ∈ 𝐶
定理２：任意の符号語𝒖, 𝒗 ∈ 𝐶に対し，𝒖 + 𝒗 ∈ 𝐶
証明：
次ページで...
21
定理２の証明（その１）
まずは補題を示す
補題：任意の線形関数 𝑓(𝑥1, … , 𝑥𝑘 )について，
𝑓 𝑢1 , … , 𝑢𝑘 + 𝑓 𝑣1 , … , 𝑣𝑘 = 𝑓 𝑢1 + 𝑣1 , … , 𝑢𝑘 + 𝑣𝑘
証明：
𝑓 𝑥1, 𝑥2, … , 𝑥𝑘 = 𝑎1 𝑥1 + ⋯ + 𝑎𝑘 𝑥𝑘 とすると
左辺＝𝑎1 𝑢1 + ⋯ + 𝑎𝑘 𝑢𝑘 + 𝑎1 𝑣1 + ⋯ + 𝑎𝑘 𝑣𝑘
＝𝑎1 𝑢1 + 𝑣1 + ⋯ + 𝑎𝑘 (𝑢𝑘 + 𝑣𝑘 )＝右辺
22
定理２の証明（その２）
定理２：任意の符号語𝒖, 𝒗 ∈ 𝐶に対し，𝒖 + 𝒗 ∈ 𝐶
証明：
𝑖番目の検査記号を与える線形式を 𝑓𝑖 (𝑥1 , … , 𝑥𝑘 )とすると
𝒖 = ( 𝑢1
+𝒗=(
, … , 𝑢𝑘
𝑣1 , … ,
, … , 𝑓𝑖 𝑢1 , … , 𝑢𝑘
𝑣𝑘 , … ,
𝑓𝑖 𝑣1 , … , 𝑣𝑘
,…)
,…)
𝒖 + 𝒗 = ( 𝑢1 + 𝑣1 , … , 𝑢𝑘 + 𝑣𝑘, … , 𝑓𝑖 𝑢1 , … , 𝑢𝑘 + 𝑓𝑖 𝑣1 , … , 𝑣𝑘 , … )
= ( 𝑢1 + 𝑣1 , … , 𝑢𝑘 + 𝑣𝑘, … ,
𝑓𝑖 𝑢1 + 𝑣1 , … , 𝑢𝑘 + 𝑣𝑘 ,
∈𝐶
前ページの補題を使用
…)
23
線形符号の性質（一部再掲）
符号 𝐶 が線形符号であれば...
定理１： 0, … , 0 ∈ 𝐶
定理２：任意の符号語𝒖, 𝒗 ∈ 𝐶に対し，𝒖 + 𝒗 ∈ 𝐶
定理２は，「必要十分条件」のカタチで証明できる...
定理2+：
𝐶が線形符号 iff 任意の符号語𝒖, 𝒗 ∈ 𝐶に対し𝒖 + 𝒗 ∈ 𝐶
24
線形符号の構成例
𝑘 = 3の場合：情報記号列は (𝑥1, 𝑥2, 𝑥3)
検査記号を適当に定義する．
𝑝1 = 𝑥1 + 𝑥2
⇒ 符号語は (𝑥1, 𝑥2, 𝑥3, 𝑝1, 𝑝2)
𝑝2 =
𝑥2 + 𝑥3
00000
00101
01011
01110
10010
10111
11001
11100
00000
00000
00101
01011
01110
10010
10111
11001
11100
00101
00101
00000
01110
01011
10111
10010
11100
11001
01011
01011
01110
00000
00101
11001
11100
10010
10111
01110
01110
01011
00101
00000
11100
11001
10111
10010
10010
10010
10111
11001
11100
00000
00101
01011
01110
10111
10111
10010
11100
11001
00101
00000
01110
01011
11001
11001
11100
10010
10111
01011
01110
00000
00101
11100
11100
11001
10111
10010
01110
01011
00101
00000
25
このあとのストーリー
線形符号の符号化
生成行列の導入
生成行列の性質
線形空間との関係
26
符号語の「中の仕組み」
符号語 ＝(𝑥1 , … , 𝑥𝑘 , 𝑝1 , … , 𝑝𝑚 )
𝑝1 = 𝑎1,1 𝑥1 + ⋯ +𝑎1,𝑘 𝑥𝑘
⋮
𝑝𝑚 = 𝑎𝑚,1 𝑥1 + ⋯ +𝑎𝑚,𝑘 𝑥𝑘
𝑥1 , … , 𝑥𝑘
= 𝑥1 , … , 𝑥𝑘
1 ⋯ 0
⋮ ⋱ ⋮
0 ⋯ 1
𝑝1 , … , 𝑝𝑚
𝑎1,1
⋮
𝑎1,𝑘
⋯ 𝑎𝑚,1
⋱
⋮
⋯ 𝑎𝑚,𝑘
1 ⋯ 0 𝑎1,1
⋮ ⋱ ⋮
⋮
0 ⋯ 1 𝑎1,𝑘
⋯ 𝑎𝑚,1
⋱
⋮
⋯ 𝑎𝑚,𝑘
= 𝑥1 , … , 𝑥𝑘
𝑥1 , … 𝑥𝑘 , 𝑝1 , … , 𝑝𝑚 = 𝑥1 , … , 𝑥𝑘
27
生成行列
𝑥1 , … 𝑥𝑘 , 𝑝1 , … , 𝑝𝑚
= 𝑥1 , … , 𝑥𝑘
1 ⋯ 0 𝑎1,1
⋮ ⋱ ⋮
⋮
0 ⋯ 1 𝑎1,𝑘
𝑘 × 𝑘単位行列
⋯ 𝑎𝑚,1
⋱
⋮
⋯ 𝑎𝑚,𝑘
生成行列
検査記号定義式の
係数行列の転置
28
生成行列の例
偶パリティ符号：(𝑥1 , 𝑥2 , 𝑥3 , 𝑝1 )
𝑝1 = 𝑥1 + 𝑥2 + 𝑥3
1 0 0 1
𝐺= 0 1 0 1
0 0 1 1
水平垂直パリティ検査符号：(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑝1 , 𝑝2 , 𝑝3 , 𝑝4 , 𝑝5 )
𝑝1 = 𝑥1 +𝑥2
𝑝2 =
𝑥3 +𝑥4
𝑝3 = 𝑥1
+𝑥3
𝑝4 =
𝑥2
+𝑥4
𝑝5 = 𝑥1 +𝑥2 +𝑥3 +𝑥4
1 0 0 0 1 0 1 0 1
0 1 0 0 1 0 0 1 1
𝐺=
0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 0 1 1
29
生成行列を用いた符号化
𝑘ビットデータ 𝒙 を符号化したいときは...
𝒙 を，左側から生成行列 𝐺に乗じた結果 𝒙𝐺 が符号語
水平垂直パリティ検査符号で 𝒙 = (0,1,1,1)を符号化...
0 1 1
1 1 0
1 0 1
1
0
(0,1,1,1)
0
0
⇒ 符号語は 011110101
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
= (0,1,1,1,1,0,1,0,1)
30
論理回路による符号化器の実現
x
情 x1
報 x2
記 x3
号 4
x 1 x 2 x 3 x 4 p1
符
1
0
(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 )
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
p2
号
1
1
1
1
p3
p4
p5
語
排他的論理和
31
このあとのストーリー
線形符号の符号化
生成行列の導入
生成行列の性質
線形空間との関係
32
生成行列の行ベクトル
1 ⋯
𝐺= ⋮ ⋱
0 ⋯
0 𝑎1,1
⋮
⋮
1 𝑎1,𝑘
⋯ 𝑎𝑚,1
⋱
⋮
⋯ 𝑎𝑚,𝑘
𝑝1 = 𝑎1,1 𝑥1 + ⋯ + 𝑎1,𝑖 𝑥𝑖 + ⋯ +𝑎1,𝑘 𝑥𝑘
⋮
𝑝𝑚 = 𝑎𝑚,1 𝑥1 + ⋯ + 𝑎𝑚,𝑖 𝑥𝑖 + ⋯ +𝑎1,𝑘 𝑥𝑘
𝐺の第 𝑖 行ベクトルは
>
(0, … , 0,1,0, … , 0, 𝑎1,𝑖 , … , 𝑎𝑚,𝑖 )
𝑖ビット目だけが1
𝑥1 , … , 𝑥𝑘 = (0, … , 0,1,0, … 0)と
したときの 𝑝1 , … , 𝑝𝑚 となっている
𝐺の第 𝑖行ベクトルは， 0, … , 0,1,0, … , 0 に対応する符号語
33
線形空間としての線形符号
定理3：
𝐶が線形符号ならば，𝐶は線形空間（ベクトル空間）を構成する
定理4：
生成行列の行ベクトルは，線形空間の基底をなす
𝐺=
𝒈1
𝒈2
⋮ とすると，任意の符号語 𝒖 ∈ 𝐶 は以下のように書ける
𝒈𝑘
𝒖 = 𝑢1𝒈1 + 𝑢2𝒈2 + … + 𝑢𝑘𝒈𝑘
(𝑢𝑖 ∈ {0, 1})
34
25ページの例では...
情報記号 (𝑥1, 𝑥2, 𝑥3) に対し，
𝑝1 = 𝑥1 + 𝑥2
𝑝2 =
𝑥2 + 𝑥3
1 0 0 1 0
𝐺= 0 1 0 1 1
0 0 1 0 1
符号語
00000 = 0・10010 + 0・01011 + 0・00101
00101 = 0・10010 + 0・01011 + 1・00101
01011 = 0・10010 + 1・01011 + 0・00101
01110 = 0・10010 + 1・01011 + 1・00101
10010 = 1・10010 + 0・01011 + 0・00101
10111 = 1・10010 + 0・01011 + 1・00101
11001 = 1・10010 + 1・01011 + 0・00101
11100 = 1・10010 + 1・01011 + 1・00101
G の行ベクトルが，基底となっていることがわかる
35
ここまでのまとめ：符号化と生成行列
線形符号は...
検査記号が，情報記号の線形式で定義される符号
符号語集合がベクトル空間をなすような符号
生成行列
符号化操作を効率的に行うための道具
組み合わせ回路の実現等にも有用
行ベクトルが，符号の基底となっている
36
練習問題
情報記号(𝑥1 , 𝑥2 , 𝑥3 )に対し，
𝑝1 = 𝑥1 +𝑥2 +𝑥3
𝑝2 = 𝑥1 +𝑥2
𝑝3 = 𝑥1
+𝑥3
とし，(𝑥1 , 𝑥2 , 𝑥3 , 𝑝1 , 𝑝2 , 𝑝3 )を符号語と定義する．
この符号の生成行列を求めよ
この符号の符号語をすべて列挙せよ
p.31 のような符号化器を示せ
37
© Copyright 2024 ExpyDoc
