通信符号理論 13

1 通信符号理論 第13回 伊藤彰則

2 シンボルMAP復号に向けて ෝ = arg max 𝑃 𝒚 𝒙 𝑃(𝒙) • ブロックMAP復号 𝒙 𝒙 • ブロックMAP復号は「全体として」確率最大のシンボル系列 ෝ = (𝑥ො1 , … , 𝑥ො𝑛 ) 𝒙 を計算する • それぞれの𝑥ො𝑖 が確率的な意味で最適であることを必ずしも意味しない • ある𝑖番目のシンボルについて、確率的な意味で最も良い復号結 果を得るためにはどうしたらいいのか？

3 特定のシンボルを復号する • 𝑖番目のシンボルについて最適な結果を得るには？ • 𝑥ො𝑖 = arg max𝑥𝑖 σ𝒙∖𝑥𝑖 𝑃𝑌|𝑋 (𝒚| … , 𝑥𝑖 , … ) 𝑃𝑋 ( … , 𝑥𝑖 , … ) • 𝒙 ∖ 𝑥𝑖 は「𝒙から𝑥𝑖 を除いたもの」つまり(𝑥1 , … , 𝑥𝑖−1 , 𝑥𝑖+1 , … , 𝑥𝑛 ) • 省略しているが、実際にはσ𝒙∖𝑥𝑖 𝑃(… )は、「変数𝒙 ∖ 𝑥𝑖 について、すべ ての可能な値に関する総和をとる」ことを意味する

4 シンボルMAP復号 • 𝑥ො𝑖 = arg max𝑥𝑖 σ𝒙∖𝑥𝑖 𝑃𝑌|𝑋 (𝒚| … , 𝑥𝑖 , … ) 𝑃𝑋 ( … , 𝑥𝑖 , … ) • 違う書き方をすると σ𝒙∈𝐶,𝑥 =0 𝑃𝑌|𝑋 𝒚 𝒙 𝑃𝑋 (𝒙) • 𝐿𝑖 = log σ 0 • 𝑥ො𝑖 = ቐ ? 1 𝑖 𝒙∈𝐶,𝑥𝑖 =1 𝑃𝑌|𝑋 𝐿𝑖 > 0 𝐿𝑖 = 0 𝐿𝑖 < 0 𝒚 𝒙 𝑃𝑋(𝒙)

5 Forward-Backwardアルゴリズム • トレリスを使って確率の周辺化をするアルゴリズム • Viterbiアルゴリズムに似た方法で確率を求める方法（Forward 確率）と、それを逆方向に適用する方法（Backward確率）の 組み合わせ • 鎖状のファクターグラフに対するSum-Productアルゴリズムと考える ことができる

6 トレリス、関数、変数 • 例えば次のトレリスを考える 入力𝑦𝑖 =0 1 0 0 1 • 受信語 𝒚 = (𝑦1 , … , 𝑦𝑛 ) : 定数 • 符号語 𝒙 = (𝑥1 , … , 𝑥𝑛 ) : 変数 • 状態系列𝒔 = (𝑠0 , 𝑠1 , … , 𝑠𝑛 ): 変数 • シンボル出力確率 • 𝑃𝑌|𝑋 (𝑦𝑖 |𝑥𝑖 ) • 状態遷移関数 • 𝑇(𝑠𝑖−1 , 𝑥𝑖 , 𝑠𝑖 ): 状態𝑠𝑖−1 でシンボル𝑥𝑖 を出力して状態𝑠𝑖+1 に遷移できる場 合は1、できない場合は0

7 状態遷移関数の例 • 右の例では • 𝑇 𝑠10 , 0, 𝑠20 = 1 • 𝑇 𝑠10 , 0, 𝑠21 = 𝑇 𝑠10 , 0, 𝑠22 = 𝑇 𝑠10 , 0, 𝑠23 • 𝑇 𝑠10 , 1, 𝑠21 = 1 • 𝑇 𝑠10 , 1, 𝑠20 = 𝑇 𝑠10 , 1, 𝑠22 = 𝑇 𝑠10 , 1, 𝑠23 • 𝑇 𝑠13 , 0, 𝑠23 = 1 • 𝑇 𝑠13 , 0, 𝑠20 = 𝑇 𝑠13 , 0, 𝑠21 = 𝑇 𝑠13 , 0, 𝑠23 • 𝑇 𝑠13 , 1, 𝑠22 = 1 • 𝑇 𝑠13 , 1, 𝑠20 = 𝑇 𝑠13 , 1, 𝑠21 = 𝑇 𝑠10 , 1, 𝑠23 • 𝑇 𝑠11 , 𝑥, 𝑠2𝑘 = 0, 𝑇 𝑠12 , 𝑥, 𝑠2𝑘 = 0 =0 𝑠10 0 𝑠20 1 𝑠11 𝑠21 =0 𝑠12 𝑠22 =0 𝑠13 =0 1 0 𝑠23

8 ファクターグラフ 𝑇(𝑠0 , 𝑥, 𝑠1 ) 𝑠0 𝑇(𝑠1 , 𝑥, 𝑠2 ) 𝑠1 𝑇(𝑠2 , 𝑥, 𝑠3 ) 𝑠2 𝑥1 𝑥2 𝑃 𝑦1 𝑥1 𝑃(𝑥1 ) 𝑃 𝑦2 𝑥2 𝑃(𝑥2 ) 𝑇(𝑠3 , 𝑥, 𝑠4 ) 𝑠3 𝑇(𝑠4 , 𝑥, 𝑠5 ) 𝑠4 𝑠5 𝑥3 𝑥4 𝑥5 𝑃 𝑦3 𝑥3 𝑃(𝑥3 ) 𝑃 𝑦4 𝑥4 𝑃(𝑥4 ) 𝑃 𝑦5 𝑥5 𝑃(𝑥5 ) 5 𝑃 𝒙 𝒚, 𝒔 = ෑ 𝑇 𝑠𝑖−1 , 𝑥𝑖 , 𝑠𝑖 𝑃𝑌|𝑋 𝑦𝑖 𝑥𝑖 𝑃𝑋 (𝑥𝑖 ) 𝑃 𝒙 𝒚 = ෍ 𝑃(𝒙|𝒚, 𝒔) 𝑖=1 𝒔

9 例 • 長いので3状態で考える • 𝑃 𝒙 𝒚, 𝒔 = 𝑇 𝑠0 , 𝑥1 , 𝑠1 𝑓1 𝑥1 × 𝑇 𝑠1 , 𝑥2 , 𝑠2 𝑓2 (𝑥2 ) 0 𝑠00 𝑠0 𝑇(𝑠1 , 𝑥, 𝑠2 ) 𝑠1 𝑥1 𝑠2 𝑥2 0 𝑠20 𝑠10 1 𝑠01 𝑇(𝑠0 , 𝑥, 𝑠1 ) 1 𝑠11 𝑠21 𝑃𝑌|𝑋 𝑦1 𝑥1 𝑃𝑋 𝑥1 𝑃𝑌|𝑋 𝑦2 𝑥2 𝑃𝑋 𝑥2 = 𝑓1 (𝑥1 , 𝑦1 ) = 𝑓2 (𝑥2 , 𝑦2 )

10 例 0 • 長いので3状態で考える • 𝑃 𝒙 𝒚, 𝒔 = 𝑇 𝑠0 , 𝑥1 , 𝑠1 𝑓1 𝑥1 × 𝑇 𝑠1 , 𝑥2 , 𝑠2 𝑓2 (𝑥2 ) • より具体的に • 𝑃 00 00, 𝑠00 , 𝑠10 , 𝑠20 = 1 ⋅ 𝑓1 0,0 ⋅ 1 ⋅ 𝑓2 0,0 = 𝑃𝑌|𝑋 0 0 𝑃𝑋 0 𝑃𝑌|𝑋 0 0 𝑃𝑋 (0) • 𝑃 00 00, 𝑠00 , 𝑠11 , 𝑠20 = 0 ⋅ 𝑓1 0,0 ⋅ 0 ⋅ 𝑓2 0,0 = 0 • 𝑃 11 01, 𝑠00 , 𝑠11 , 𝑠20 = 1 ⋅ 𝑓1 1,0 ⋅ 1 ⋅ 𝑓2 1,1 = 𝑃𝑌|𝑋 0 1 𝑃𝑋 1 𝑃𝑌|𝑋 1 1 𝑃𝑋 (1) 𝑠00 0 1 𝑠01 𝑠20 𝑠10 1 𝑠11 𝑠21

11 例 𝑥2 • 𝑃 𝑥2 𝒚, 𝒔 を求める 𝑇(𝑠0 , 𝑥, 𝑠1 ) 𝑠0 𝑇(𝑠1 , 𝑥, 𝑠2 ) 𝑠1 𝑥1 𝑓2 (𝑥2 , 𝑦2 ) 𝑠2 𝑇(𝑠0 , 𝑥, 𝑠1 ) 𝑇(𝑠1 , 𝑥, 𝑠2 ) 𝑠2 𝑥2 𝑠0 𝑃 𝑦1 𝑥1 𝑃 𝑥1 = 𝑓1 (𝑥1 , 𝑦1 ) 𝑠1 𝑃 𝑦2 𝑥2 𝑃 𝑥2 = 𝑓2 (𝑥2 , 𝑦2 ) 𝑥1 𝑓1 (𝑥1 , 𝑦1 )

12 例 𝑥2 • 𝑃 𝑥2 = 1 𝒚, 𝒔 を求める ෍ 𝑇 𝑠0 , 𝑥1 , 𝑠1 𝑓1 (𝑥1 , 𝑦1 ) 𝑠0 ,𝑥1 𝑓2 (𝑥2 , 𝑦2 ) 𝑇(𝑠0 , 𝑥, 𝑠1 ) 𝑠1 𝑇(𝑠1 , 𝑥, 𝑠2 ) 𝑠2 1 𝑓1 (𝑥1 , 𝑦1 ) 𝑠0 𝑥1 𝑓1 (𝑥1 , 𝑦1 )

13 例 ෍ 𝑇(𝑠1 , 𝑥2 , 𝑠2 ) ෍ 𝑇 𝑠0 , 𝑥1 , 𝑠1 𝑓1 (𝑥1 , 𝑦1 ) 𝑠1 ,𝑠2 𝑠0 ,𝑥1 𝑥2 • 𝑃 𝑥2 = 1 𝒚, 𝒔 を求める • 𝑃 𝑥2 𝒚, 𝒔 = 𝑓2 (𝑥2 , 𝑦2 ) ෍ 𝑇 𝑠0 , 𝑥1 , 𝑠1 𝑓1 (𝑥1 , 𝑦1 ) 𝑠0 ,𝑥1 𝑓(𝑥2 , 𝑦2 ) ෍ 𝑇(𝑠1 , 𝑥2 , 𝑠2 ) × 𝑇(𝑠0 , 𝑥, 𝑠1 ) 𝑠1 ,𝑠2 𝑠1 𝑇(𝑠1 , 𝑥, 𝑠2 ) 1 𝑓2 (𝑥2 , 𝑦2 ) 𝑠2 ෍ 𝑇 𝑠0 , 𝑥1 , 𝑠1 𝑓1 (𝑥1 , 𝑦1 ) 𝑠0 ,𝑥1 𝑠0 𝑥1 𝑓1 (𝑥1 , 𝑦1 )

14 Forward確率とBackward確率 • トレリスの先頭から始まり、時刻𝑡において状態𝑠𝑡 にいる確率 𝛼 𝑡, 𝑠𝑡 （Forward確率） • 時刻𝑡において状態𝑠𝑡 にいて、そこから最後まで遷移する確率 𝛽 𝑡, 𝑠𝑡 （Backward確率） • 受信語が受信される確率はσ𝑠𝑡 𝛼 𝑡, 𝑠𝑡 𝛽(𝑡, 𝑠𝑡 ) 𝑠𝑡0 𝛼(𝑡, 𝑠𝑡 ) 𝑇(𝑠𝑡−1 , 𝑥𝑡 , 𝑠𝑡 ) 𝑠𝑡1 𝑠𝑡 𝛽(𝑡, 𝑠𝑡 ) 𝑇(𝑠𝑡 , 𝑥𝑡+1 , 𝑠𝑡+1 ) 𝑠𝑡+1 𝑠𝑡−1 𝑥𝑡 𝑥𝑡+1

15 Forward確率 𝛼 𝑡, 𝑠𝑡 = ෍ 𝑇 𝑠𝑡−1 , 𝑥𝑡 , 𝑠𝑡 𝑓𝑡 𝑥𝑡 , 𝑦𝑡 𝛼(𝑡 − 1, 𝑠𝑡−1 ) 𝑠𝑡−1 ,𝑥𝑡 𝑠𝑡 𝛼(𝑡, 𝑠𝑡 ) 𝑇(𝑠𝑡−1 , 𝑥𝑡 , 𝑠𝑡 ) 𝑇(𝑠𝑡 , 𝑥𝑡+1 , 𝑠𝑡+1 ) 0 0 𝑠𝑡−1 𝑠𝑡0 1 1 𝛼(𝑡 − 1, 𝑠𝑡−1 ) 𝑠𝑡+1 𝑠𝑡−1 𝑥𝑡 𝑥𝑡+1 𝑓𝑡 (𝑥𝑡 , 𝑦𝑡 ) 1 𝑠𝑡−1 0 𝑠𝑡1 0 𝛼 𝑡, 𝑠𝑡0 = 𝑓𝑡 0, 𝑦𝑡 𝛼 𝑡 − 1, 𝑠𝑡−1 + 1 𝑓𝑡 1, 𝑦𝑡 𝛼(𝑡 − 1, 𝑠𝑡−1 )

16 Backward確率 𝛽 𝑡, 𝑠𝑡 = ෍ 𝑇 𝑠𝑡 , 𝑥𝑡+1 , 𝑠𝑡+1 𝑓𝑡+1 𝑥𝑡+1 , 𝑦𝑡+1 𝛽(𝑡 + 1, 𝑠𝑡+1 ) 𝑠𝑡+1,𝑥𝑡+1 𝑠𝑡 𝑇(𝑠𝑡−1 , 𝑥𝑡 , 𝑠𝑡 ) 𝛽(𝑡, 𝑠𝑡 ) 𝑇(𝑠𝑡 , 𝑥𝑡+1 , 𝑠𝑡+1 ) 𝑠𝑡0 0 1 0 𝑠𝑡+1 1 𝑠𝑡+1 𝑠𝑡−1 𝑥𝑡 𝑥𝑡+1 𝛽(𝑡 + 1, 𝑠𝑡+1 ) 𝑓𝑡+1 (𝑥𝑡+1 , 𝑦𝑡+1 ) 𝑠𝑡1 0 1 𝑠𝑡+1 0 𝛽 𝑡, 𝑠𝑡0 = 𝑓𝑡+1 0, 𝑦𝑡+1 𝛽 𝑡 + 1, 𝑠𝑡+1 + 1 𝑓𝑡+1 1, 𝑦𝑡+1 𝛽(𝑡 + 1, 𝑠𝑡+1 )

17 シンボル生成確率 𝑓𝑡 (𝑥𝑡 , 𝑦𝑡 ) ෍ 𝑇 𝑠𝑡−1 , 𝑥𝑡 , 𝑠𝑡 𝛼 𝑡 − 1, 𝑠𝑡−1 𝛽(𝑡, 𝑠𝑡 ) 𝑠𝑡−1 ,𝑠𝑡 ෍ 𝑇 𝑠𝑡−1 , 𝑥𝑡 , 𝑠𝑡 𝛼 𝑡 − 1, 𝑠𝑡−1 𝛽(𝑡, 𝑠𝑡 ) 𝑥𝑡 𝑓𝑡 (𝑥𝑡 , 𝑦𝑡 ) 𝑠𝑡−1 ,𝑠𝑡 𝑓𝑡 (𝑥𝑡 , 𝑦𝑡 ) 𝑇(𝑠𝑡−1 , 𝑥𝑡 , 𝑠𝑡 ) 0 0 𝑠𝑡−1 𝑠𝑡−1 𝛼(𝑡 − 1, 𝑠𝑡−1 ) 𝑠𝑡0 1 𝑠𝑡 1 𝛽(𝑡, 𝑠𝑡 ) 1 𝑠𝑡−1 0 𝑠𝑡1

18 Forward-Backwardアルゴリズム 1. Forward確率𝛼(𝑡, 𝑠𝑡 )を求める。 • 初期条件 𝛼 0, 𝑠00 = 1 • 漸化式を使って𝛼(𝑡, 𝑠𝑡 )を小さいtから順番に計算する 2. Backward確率𝛽(𝑡, 𝑠𝑡 )を求める。 • 初期条件𝛽 𝑛, 𝑠𝑛0 = 1 • 漸化式を使って𝛽(𝑡, 𝑠𝑡 )を大きいtから順番に計算する 3. ある特定の𝑥𝑡 について • 𝑔𝑡 𝑥𝑡 = 𝑓𝑡 (𝑥𝑡 , 𝑦𝑡 ) σ𝑠𝑡−1 ,𝑠𝑡 𝑇 𝑠𝑡−1 , 𝑥𝑡 , 𝑠𝑡 𝛼 𝑡 − 1, 𝑠𝑡−1 𝛽(𝑡, 𝑠𝑡 )

19 ターボ符号に向けて • 現代でよく使われている符号 • Reed-Solomon符号 • ターボ符号 • Low Density Parity Check (LDPC)符号 • ターボ符号は畳み込み符号を組み合わせて作られている • 「インターリーバ」による符号ビットの並べ替え • 複数の畳み込み符号化器による符号化 • 繰り返し復号（ターボ復号）アルゴリズム • シャノン限界に近い符号化性能を達成

20 インターリーバ (Interleaver) • 符号を並べ替える(interleaving)操作をするしくみ • 12345678 → 13572468 など • さまざまなインターリーバ • ブロックインターリーバ • ランダムインターリーバ • 巡回シフトインターリーバ

21 インターリーバの意義 • 誤り訂正では、ビット誤りが局所的に固まる（バースト誤り） と性能が低下することが多い • 誤りが多くても分散していればなんとかなる

22 インターリーバの意義 • ビットをあらかじめ入れ替え、後で元に戻す • 誤りが集中しても、元に戻すことで誤りが分散する 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 0 1 2 3 4 5 0 4 8 1 1 1 1 1 1 1 5 9 2 6 3 7 2 3 0 4 1 5 0 4 8 1 1 1 1 1 1 1 5 9 2 6 3 7 2 3 0 4 1 5 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 0 1 2 3 4 5

23 ブロックインターリーバ • 固定長のブロックに対して簡単な方法で順序を入れ替える • 原理が単純、ハードウェア化も容易 • 同じインターリーバを2回通すと元に戻る 0 1 2 3 4 5 6 7 8 縦方向に上→下、左→右の 順に行列にビットを詰める 0 3 6 1 4 7 2 5 8 0 3 6 1 4 7 2 5 8 横方向に左→右、上→下の順に 行列からビットを取り出す 前のページで使ったのは4×4のブロックインターリーバ

24 その他のインターリーバ • ランダムインターリーバ • ブロックの長さを決め、ビットの入れ替えをランダムに決める （決めるときには疑似乱数で決め、一度入れ替え方を決めたら固定す る） • 巡回シフトインターリーバ • ブロック長𝐿に対し、𝐿と互いに素な数 𝑎 < 𝐿を使い、 𝑝 𝑖 = 𝑎𝑖 + 𝑠 mod 𝐿 (𝑖 = 0, . . . , 𝐿 − 1) によってインターリーブする • ブロックインターリーバは典型的に𝐿 = 𝑛2 であったが、巡回シフトイ ンターリーバではそうでなくてもよい

25 巡回シフトインターリーバ • 𝑝 𝑖 = 𝑎𝑖 + 𝑠 mod 𝐿, 𝐿 = 8, 𝑎 = 3, 𝑠 = 1 の例 𝒊 𝒑(𝒊) 𝒑−𝟏 (𝒊) 0 1 5 1 4 0 2 7 3 3 2 6 4 5 1 5 0 4 6 3 7 7 6 2 0 1 2 3 4 5 6 7 5 0 3 6 1 4 7 2

26 巡回シフトは全単射 0 < 𝑎 < 𝐿かつ𝑎と𝐿は互いに素であると する。 𝑖 < 𝑗より、𝑛2 > 𝑛1 となる。両辺を𝑎で 割り、 整数𝑖, 𝑗 (0 ≤ 𝑖 < 𝑗 < 𝐿)について、𝑝 𝑖 = 𝑝(𝑗)であると仮定する。 𝑛2 − 𝑛1 𝐿 𝑗−𝑖 = 𝑎 𝑎と𝐿は互いに素であるから、𝑛2 − 𝑛1 は 正かつ𝑎の倍数でなければならない。こ れは最小でも𝑎であり、 𝑛2 − 𝑛1 = 𝑎と 仮定すれば𝑗 − 𝑖 = 𝐿より 𝑗 =𝑖+𝐿 >𝐿 仮定より、整数0 ≤ 𝑟 < 𝐿, 0 ≤ 𝑛1 ≤ 𝑛2 に ついて 𝑎𝑖 + 𝑠 = 𝑛1 𝐿 + 𝑟 𝑎𝑗 + 𝑠 = 𝑛2 𝐿 + 𝑟 と表せる。辺々引けば 𝑎 𝑗 − 𝑖 = 𝑛2 − 𝑛1 𝐿 これは𝑗 < 𝐿の仮定に反する。したがっ て𝑝 𝑖 ≠ 𝑝(𝑗)である。

27 演習 • 図のようなトレリスに対して、次の条件のとき、ForwardBackwardアルゴリズムを使って σ𝒙,𝑥2 =0 𝑃𝑌|𝑋 𝒚 𝒙 𝑃𝑋 (𝒙) 𝑃(𝑥2 = 0|𝒚) 𝐿2 = log = log σ𝒙,𝑥2 =1 𝑃𝑌|𝑋 𝒚 𝒙 𝑃𝑋 (𝒙) 𝑃(𝑥2 = 1|𝒚) を求めよ。ただし受信語と各種の確率は以下の通りとする。 • 𝒚 = (0,1) • 𝑃𝑋 0 = 𝑝0 , 𝑃𝑋 1 = 𝑝1 , 𝑝0 + 𝑝1 = 1 • 𝑃𝑌|𝑋 0 1 = 𝑃𝑌|𝑋 1 0 = 𝑝 y=(0, 1) 0 0 • 𝑃𝑌|𝑋 0 0 = 𝑃𝑌|𝑋 1 1 = 1 − 𝑝 1 1

28 演習 • 求め方 • Forward確率 𝛼 0, 𝑠00 , 𝛼 1, 𝑠10 , 𝛼 1, 𝑠11 を求める • Backward確率 𝛽(2, 𝑠20 )を求める • 𝑔2 0 = 𝑃𝑌|𝑋 1 0 𝑃𝑋 0 𝛼 1, 𝑠10 𝛽(2, 𝑠20 ) • 𝑔2 1 = 𝑃𝑌|𝑋 1 1 𝑃𝑋 1 𝛼 1, 𝑠11 𝛽 2, 𝑠20 • 𝐿2 = log 𝑔2 (0) 𝑔2 (1)