情報理論

練習問題
以下の検査行列を持つ線形符号 C を考える
C の重み分布を求めよ
C の誤り特性評価を行い,式とグラフで各確率を示せ
1

1
H 
1

0
1 1 0 1 0 0 0

1 0 1 0 1 0 0
.

0 1 1 0 0 1 0

1 1 1 0 0 0 1
回答例は http://narayama.naist.jp/~kaji/lecture/ に掲載
1
前回の復習,本日の講義
前回の講義:符号の性能評価
最小ハミング距離に基づく評価
重み分布に基づく評価
今回の講義:やや実用・研究的な話題
巡回符号:線形符号の特殊なクラス
シャノンの通信路符号化定理
新しいタイプの誤り訂正符号
2
「実用的な」線形符号の模索
これまでの議論...一般の線形符号を対象
符号化,誤りの検出,訂正とも,行列演算により実行可能
行列演算 ⇒ 単純な組合せ回路だけで実現可能
⇒ 高速に動作させるのに有利
性能向上のためには,符号長などを大きくすることが有利
規模の大きな線形符号
生成行列,検査行列とも巨大(符号長の2乗オーダ)
組合せ回路の面積増大 ⇒ 遅延,消費電力,設計困難
もっと扱いやすい線形符号は?
畳込み符号
巡回符号
3
巡回符号
巡回符号(cyclic code):線形符号の一種
符号化器や復号器のハードウェア実現が容易
組合せ回路ではなく,シフトレジスタを利用して,
符号化器や復号器を構成可能
シフトレジスタの利用は,速度的には若干不利
回路面積や消費電力,コストの削減に貢献.
符号
線形符号
巡回符号
4
巡回符号:準備(1)
係数が 0 か 1 であるような,1変数多項式を考える
x4 + x3 + x2
+1
+)
x3
+x+1
x4
+ x2 + x
11101
+) 01011
10110
x4 + x3 + x2
+1
x3
+x+1
×)
x4 + x3 + x2
+1
x5 + x4 + x3
+x
x7 + x6 + x5
+ x3
x7 + x6
+ x3 + x2+ x + 1
11101
×) 01011
多項式の加算:
(減算)
多項式の乗算:
• 係数の足し算は2進で行う
• 繰り上がりなし
11101
11101
11101
11001111
xm を掛ける: 左 m ビットシフト
5
巡回符号:準備(2)
多項式の除算:
x4
+
x3
+
x2
x2 + x + 1
+ 1 ) x6
+ x4
x6 + x5 + x4
+ x2
x5
+ x2
x5 + x4 + x3
+x
x4 + x3 + x2 + x
x4 + x3 + x2
+1
x+1
111
11101 ) 1010000
11101
10010
11101
11110
11101
11
• 足し算と引き算は同じ
• シフトレジスタを利用すれば,除算回路の実現は容易
6
参考:除算回路について(1)
x6 + x4 を x4 + x3 + x2 + 1 で割る場合
除数 1
(a  b の b)
1
1
0
1
被除数 (a  b の a)
1010000
商
剰余
1.
2.
3.
被除数をシフトレジスタに投入
最上位ビットが1のとき,
除数と加算(排他的論理和)
左にシフト(step 1へ)
7
参考:除算回路について(2)
1
1
1
0
1
1
0
1
0
0
1
1
1
0
1
0
1
0
0
1
00
00
111
11101 ) 1010000
11101
10010
11101
11110
11101
11
1サイクルの操作
= 筆算の1ステップ
被除数を全部投入後の
レジスタ内の値 = 剰余
8
巡回符号:生成多項式
符号長 n, 情報記号数 k の巡回符号を構成する.
(検査記号数 p = n-k)
準備:xn + 1を割り切る p 次の多項式 G(x) を求める
n = 7 の場合,x7 + 1 = (x3 + x2 + 1) (x4 + x3 + x2 + 1).
p = 4, G(x) = x4 + x3 + x2 + 1 として (7,3) 巡回符号を構成可能
1101
11101 ) 10000001
G(x)
11101
1101001
11101
11101
11101
0
• G(x) を利用して巡回符号を生成する.
• G(x) を生成多項式と呼ぶ.
(generator polynomial)
9
巡回符号の定義
G(x) を生成多項式とする巡回符号:
n 次未満である G(x) の倍多項式(に対応する2進系列)の集合
倍多項式:数字の「倍数」の多項式版
0, G(x), xG(x), (x + 1)G(x), x2G(x), (x2+1)G(x), (x2+x)G(x), ...
n = 4, G(x) = x2 + 1 のとき (n = 4, k = p = 2),
倍多項式は
0, x2 + 1, x(x2 + 1) = x3 + x, (x + 1)(x2 + 1) = x3 + x2 + x + 1
符号語は 0000, 0101, 1010, 1111
10
巡回符号の性質(1)
定理: 巡回符号は線形符号である
証明:
任意の2つの符号語の和が,符号語になることを示せばよい.
巡回符号の符号語は,G(x) の倍多項式になっている
符号語 c1...倍多項式 f1(x)G(x) の係数と対応
符号語 c2...倍多項式 f2(x)G(x) の係数と対応
c1 + c2... 倍多項式 (f1(x) + f2(x))G(x) の係数と対応
⇒ c1 + c2も,正しい符号語である
11
巡回符号の性質(2)
定理:
(an-1, an-2, ..., a0) が符号語なら,(an-2, ..., a0, an-1) も符号語
証明:
W(x) = an-1xn-1 + ... + a0 とすると,W(x) は G(x) の倍多項式.
一方,W ’(x) =
an-2xn-1 + ... + a0x + an-1
= an-1xn + an-2xn-1 + ... + a0x + an-1+ an-1xn
= xW(x)
+ an-1(xn + 1)
W(x),(xn +1)はG(x)の倍多項式⇒W ’(x) も G(x) の倍多項式
よって (an-2, ..., a0, an-1) も符号語
符号語を巡回シフトしても,やはり符号語
12
巡回符号の符号化
情報記号列と符号語を,どのように対応付けるか
生成行列を使う
通常の線形符号と同じで,巡回符号のメリットなし
掛け算アプローチ
符号語 = 情報記号列 × 生成多項式
理屈はわかりやすいが,組織符号にはならないかも
(符号語から,情報記号列に戻すのが面倒)
割り算アプローチ
情報記号列をシフトし,生成多項式で割る
剰余部分をキャンセルして,倍多項式に丸める
理屈はわかりにくいが,常に組織符号となる
13
巡回符号:符号化
符号化の手順
1. 情報記号列を多項式表現する (以下では A(x) とする)
2. A(x)xp を G(x) で割り,剰余を B(x) とする
3. A(x)xp + B(x) を符号語(の多項式表現)と考える
n = 7, k = 3, p = 7-3 = 4, G(x) = x4 + x3 + x2 + 1 のとき,011 を符号化する
1. A(x) = x + 1
2. A(x)x4 = x5 + x4 = x(x4 + x3 + x2 + 1) + (x3 + x) より,B(x) = x3 + x
3. A(x)x4 + B(x) = x5 + x4 + x3 + x,すなわち 0111010 が符号語
A(x)
x4
W(x) = A(x) x4 + B(x)
被除数
G(x)
除数
除算器
剰余
B(x)
商
D(x)
14
前スライドの符号化手順について
A(x)xp + B(x) は,本当に符号語になっているか?
⇔ A(x)xp + B(x) は,生成多項式 G(x) で割り切れるか?
Yes
B(x) は,A(x)xp を G(x) で割った余りになっている
二進の世界では,足し算=引き算...「B(x) を足す=B(x) を引く」
A(x)xp + B(x) = A(x)xp – B(x)
⇒ A(x)xp を G(x) で割った剰余を,「あらかじめ引いた」式
A(x)xp + B(x) が G(x) で割り切れるのは,当然のこと
15
巡回符号の例
G(x)=x4 + x3 + x2 + 1
C:
0000000,
0011101,
0111010,
0100111,
1110100,
1101001,
1001110,
1010011.
x4
被除数
x4+x3+x2+1
除数
除算器
剰余
商
2進多項式の除算器は,シフトレジスタを使って簡単に実現可能
除算回路の複雑さ O(n) < 行列乗算回路の複雑さ O(n2)
⇒ 一般の線形符号より,装置化が容易で経済的
16
巡回符号における誤り検出
誤りを訂正せず,検出するだけならば,簡単な回路で実現可能
ベクトルが符号語 ⇔ 対応する多項式が G(x) で割り切れる
受信系列を多項式表現し,
• G(x) で割り切れれば誤りは発生していない
• G(x) で割り切れないならば,誤りが発生
受信系列
生成多項式
被除数
除数
除算器
剰余
商
剰余が0: 誤り無し
1: 誤り発生
誤り検出回路は簡単に装置化できる
⇒ CRC (Cyclic Redunduncy Check) 方式
17
巡回符号における誤り訂正
誤りの訂正手段について,いくつかの方式が知られている
代表的なものとして,誤りトラップ復号法[嵩61,他]
特殊な巡回符号については,さらに効率よい方法もある
BCH (Bose-Chaudhuri-Hocquenghem) 符号
Reed-Solomon 符号
に対する Berlekamp 法など
多元符号…記号は 0 と 1 だけでない
パラメータ次第では,バイト単位での符号化も可能
バースト誤りに強い
CD, DVD, 無線通信などで広く利用されている
18
シャノンの通信路符号化定理と通信路容量
シャノンの情報源符号化定理(既出):
情報源符号化の限界と可能性を示唆した定理
シャノンの通信路符号化定理:
通信路符号化の限界と可能性を示唆した定理
(第二回講義内容)
通信路
入力記号 X
記号 A={a0, ..., ar–1}が,
確率 p = {p0, ..., pr–1} で発生
出力記号 Y
Y を知ることで,X に関する
あいまいさが減少する
⇒ 相互情報量 I(X; Y)
I(X; Y) は,この通信路を介して伝達される情報量
通信路容量 C= I(X; Y) の最大値 = maxp{I(X; Y)}
19
通信路符号化定理
符号化率 R = (log2(符号語の個数)) / 符号語の長さ
(n, k) 組織符号の場合,R = k / n
シャノンの通信路符号化定理:
通信路容量(通信路の信頼度)が C のとき,
R < C で,復号誤り率が限りなく 0 に近い符号が存在する
R > C ならば,そのような符号は存在しない
(“A Mathematical Theory of Communications,” 1948.)
理想的な符号が「存在する」ことだけを示している
具体的な符号の構成法は,示されていない
20
通信路符号化定理の残した課題
いかにして,シャノンの示した性能限界に近づくか?
符号の性能を改善する(誤り訂正能力を上げる)には…
規模の大きい符号を利用することが不可欠
符号化率 R = k/n を一定にして,符号長 n だけを変化させる
長さ n の系列の総数は 2n
符号語の数は 2k
符号語の「密度」は 2k–n = (1/2(1–R))n
密度は,n に関し指数的に減少
原理的には,符号語間の距離を大きく取れるはず
具体的に,どうすれば良いかは明確でない
21
解決法の模索(1)
90年代中ごろまでのアプローチ:
単一技術ではなく,複数の技術の組合せにより問題に対処
連接符号化
誤り訂正符号を連接して使用
「Reed-Solomon符号 + 畳込み符号」の組合せが一般的
符号化1
外部符号
(RS)
符号化2
内部符号
(畳込み)
復号1
復号2
通信路
22
解決法の模索(2)
積符号
データビットを,符号1により符号化
データビットと符号1のパリティ記号を,符号2により符号化
符号2の復号結果を,符号1の復号処理での受信語とする
データビット
0 1 0 1 1 符号1の
0 1 0 1 0
0 0 0
1 1 0 0 1 パリティ記号
0 1 0 0 1
1 1 0
1 0 0 1 0
1 0 1 1 0
1 0 1
符号2
符号1
1 0 1 1 0
の復号
の復号
0 1 0 0 1
符号2のパリティ記号
23
新時代への扉:積符号方式の問題
0 1 0 1 1
0 1 0 1 0
0 0 0
1 1 0 0 1
0 1 0 0 1
1 1 0
1 0 0 1 0 符号2 1 0 1 1 0 符号1 1 0 1
1 0 1 1 0 の復号
の復号
0 1 0 0 1
問題点:符号1の復号の際,受信情報そのものは使われない
「受信情報」と「符号2の復号結果」の双方を比較活用すれば,
より精度の高い誤り訂正ができるのではないか?
符号1の復号結果を符号2の復号器にフィードバックし,再度復
号させれば,さらに精度を向上できるのでは?
符号1と符号2が,互いに情報を出し合って助け合う仕組を作る
24
想定している復号の仕組
符号1と符号2が,互いに情報を出し合って助け合う仕組を作る
符号1の復号器
受信情報
符号2の復号器
復号結果
各復号器での処理を繰り返し,精度を向上させていく
精度確保のため,復号器の入出力とも,実数値(確率値)に
MAP (maximum a posteriori) 復号
ある種の隠れマルコフモデルの推定問題
⇒ ターボ符号
25
ターボ符号
1993年,Berrouらにより提案された符号化方式
1セットの情報記号に対し,2セットのパリティ記号を付与
情報記号
符号1・符号化
符号系列
インタリーブ
符号2・符号化
(記号の並べ替え)
符号系列
情報記号
パリティ記号1
パリティ記号2
26
ターボ符号の復号
受信情報
復号結果
符号1・MAP復号
I–1
I
I
符号2・MAP復号
I インタリーバ
I–1 逆インタリーバ
2つの復号器のあいだで,信頼度情報をやり取りする
情報のやり取りを繰り返し,精度を向上させてゆく
繰り返し回数は,比較的少なくても十分(10~20回程度)
27
ターボ符号の性能
符号長を十分長く設定すると,シ
ャノン限界に近づく性能を発揮
(右図の場合,65536ビット長で
1.0dB以下の損失)
右図で示された領域より下では,
エラーフロア現象が発生する
C. Berrou et al.: Near Shannon Limit ErrorCorrecting Coding and Decoding: Turbo Codes,
ICC 93, pp. 1064-1070, 1993.
28
ターボ符号と標準化
第3世代携帯電話で本格的採用
W-CDMA, CDMA-2000
衛星通信
インマルサット
NASA, Mars Reconnaissance Orbiter (05年8月打ち上げ)
NASA/JPL
http://www.jpl.nasa.gov/images/mro/mro-image-browse.jpg
29
LDPC符号の再発見
ターボ符号の教訓:
従来の性能指標(最小ハミング距離)に拘る必要は無い
とくにS/N比が小さい場合,パラメータを大きくとることが有効
大規模でも扱いやすい符号があれば,有効性は高い
LDPC符号 (Low Density Parity Check 符号)
検査行列が非常に疎な行列
ほとんどの要素が0で,ごく少数の要素だけ1である行列
1962年にGallagerが提案,長く忘れられていた
1999年,MacKayらによる再発見
30
LDPC符号とその復号
ごく普通の線形ブロック符号,ただし検査行列が非常に疎
信念伝播(belief propagation)アルゴリズムを用いることにより,
ほぼ線形時間で復号を行うことが可能
⇒符号長を長く設定しても,復号計算量が爆発することはない
1110100
H= 1011010
0111001
p1
q1
p3
q3
p4
q4
Tanner Graph
p6
q6
0 の確率
1 の確率 (= 1 – pi)
p3 = p1 p4 p6 + q1 q4 p6 + q1 p4 q6 + p1 q4 q6
31
LDPC符号の特長
LDPC符号…検査行列が疎 ⇒ Tanner Graphが疎
比較的少ない繰り返し回数で,「最適に近い」推定が可能
⇒ 効率的に,符号の性能を最大限発揮できる
符号長を十分長く取れば,シャノン限界に迫る性能
ターボ符号で発生する,エラーフロア現象が起こりにくい
32
LDPC符号の問題点
符号化アルゴリズムの計算量が「小さくない」
符号長に対して2乗オーダ(従来の線形符号と同じ)
良い符号の構成方法に関する研究が,まだ発展途上
当初は,ランダムな行列構成が良いと考えられてきた
研究の進展に伴い,数学的構成法の利点が明らかに
符号化等を容易にする構造の確保
エラーフロアの影響低減
33
LDPC符号と標準化
ターボ符号に比べると,まだこれから
10GBASE-T (IEEE802.3an)
無線LAN (IEEE 802.11n)
モバイル WiMAX (IEEE 802.16e)
デジタル衛星放送規格 DVB-S2
34
本日のまとめ
巡回符号
線形符号の特殊なクラス
割り算回路(シフトレジスタ)を使った実装が可能
シャノンの通信路符号化定理
次世代型の誤り訂正符号
ターボ符号
LDPC符号
35
練習問題
n = 7, k = 4, p = 7 – 4 = 3 とし,巡回符号を構成する.
G(x) = x3 + x2 + 1 が生成多項式に使えることを確かめよ
0110 を符号化せよ
0001100 は正しい符号語か,判定せよ
36