通信符号理論 11

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

2 トレリスによる復号 • 符号をトレリスで表現した時、与えられた受信語に対して、最 も良い符号語を選ぶ→復号 • Viterbi アルゴリズム • 動的計画法によって最適な符号語を高速に計算する • ハミング距離最小・尤度最大・事後確率最大などがほぼ同じアルゴリ ズムで計算できる • まずハミング距離最小について説明する

3 トレリスとは何か • 循環のない有向グラフ (Directed Acyclic Graph, DAG) • 辺（エッジ）がs桁のシンボルを表現する • 始点と終点が定義される • 始点から終点までの長さはどの経路（パス）を通っても同じ(=N) • 始点から終点までの経路上のシンボルを連結すると符号語になってい る 𝑠 = 1, 𝑁 = 5 𝑠 = 2, 𝑁 = 3

4 ハミング距離最小基準 • 受信語 𝒚 = (𝑦1 , … , 𝑦𝑛 )に対する復号結果 ෝ = arg min 𝑑ℎ (𝒙, 𝒚) 𝒙 𝒙∈𝐶 • 重要な性質 • 𝒙(𝑖) = 𝑥1 , … , 𝑥𝑖 , 𝒚(𝑖) = (𝑦1 , … , 𝑦𝑖 ) とする • 𝑑ℎ 𝒙 𝑖 , 𝒚 𝑖 = 𝑑ℎ 𝒙 𝑖−1 , 𝒚 𝑖−1 • min 𝑑ℎ (𝒙 𝑖−1 , 𝑥𝑖 ), 𝒚 𝑖 + 𝑑ℎ 𝑥𝑖 , 𝑦𝑖 , 𝑑ℎ (𝒛 𝑖−1 , 𝑥𝑖 ), 𝒚 𝑖 = min 𝑑ℎ 𝒙 𝑖−1 , 𝒚 𝑖−1 , 𝑑ℎ 𝒛 𝑖−1 , 𝒚 𝑖−1 + 𝑑ℎ 𝑥𝑖 , 𝑦𝑖

5 Viterbiアルゴリズム 1 0 1 1 0 0 1 0

6 Viterbiアルゴリズム 1 0 1 1 0 2 1 0 0 1 1 0

7 Viterbiアルゴリズム 1 0 1 1 0 0 1 2 2 1 2 0 1 1 1 0

8 Viterbiアルゴリズム 1 1 0 0 1 3 0 1 2 2 1 0 1 2 0 1 1 1

9 Viterbiアルゴリズム 1 1 0 0 1 3 0 1 2 2 1 0 1 2 0 1 1 1 ノードに入る エッジのうち、 累積距離が最小 のものを選ぶ

10 Viterbiアルゴリズム 1 1 0 0 1 3 0 1 2 2 1 1 0 1 2 0 1 1 1 累積距離最小の エッジを記録し ておく

11 Viterbiアルゴリズム 1 0 1 1 0 0 1 2 2 1 2 1 3 0 0 1 1 1 1 1

12 Viterbiアルゴリズム 1 0 1 1 0 2 0 1 2 1 1 1 2 0 1 2 0 1 1 1 1

13 Viterbiアルゴリズム 1 0 1 1 0 0 0 1 2 2 1 2 0 1 1 1 1 1 1 選んだエッジを 逆方向にたどる (backtrace)

14 Viterbiアルゴリズム 1 0 1 1 0 0 1 2 2 1 2 1 1 エッジ上のラベ ルを読む 0 1 1 11110 0 1 1

15 Viterbiアルゴリズム • 記号の定義 • 𝒚 = (𝑦1 , . . . , 𝑦𝑛 ): 受信語 (𝑘) • 𝑣𝑏 : 時刻𝑘 (0 ≤ 𝑘 ≤ 𝑛)でシンドローム𝑏に対応するノード • 𝑙(𝑣, 𝑣’): ノード𝑣と𝑣’の間のエッジのラベル • 𝑀(𝑣): ノード𝑣に至る経路と受信語とのハミング距離の最小 値

𝑦𝑖 Viterbiアルゴリズム (𝑖−1) 𝑀(𝑣1 ) (𝑖−1) 𝑣1 16 (𝑖−1) 𝑙(𝑣1 (𝑖) , 𝑣𝑏 ) (𝑖) (0) 𝑀(𝑣0 ) ← 0 𝑣𝑏 (𝑖−1) 𝑀(𝑣2 For 𝑖 ← 1, . . . , 𝑛 do ) (𝑖−1) 𝑣2’ (𝑖) For all 𝑏 such that 𝑣𝑏 exists do (𝑖) (𝑖−1) (𝑖−1) (𝑖) 𝑀(𝑣𝑏 ) ← min𝑏’ 𝑀(𝑣𝑏’ ) + 𝑑ℎ (𝑦𝑖 , 𝑙(𝑣𝑏’ , 𝑣𝑏 )) Mark the edge with the lowest distance End For End For (𝑖−1) 𝑙(𝑣2 (𝑖) , 𝑣𝑏 )

17 MAP復号とトレリス • MAP復号の式 𝑥ො = arg max𝑥 𝑃(𝒚|𝒙)𝑃(𝒙) • 無記憶の場合を考えると 𝑃(𝒚|𝒙)𝑃(𝒙) = ς𝑖 𝑃(𝑦𝑖 |𝑥𝑖 )𝑃(𝑥𝑖 ) • 対数をとっても大小関係は変わらないので 𝑥ො = arg max𝑥 𝑃(𝒚|𝒙)𝑃(𝒙) = arg max𝑥 log(𝑃(𝒚|𝒙)𝑃(𝒙)) = arg max𝑥 log ෑ 𝑃(𝑦𝑖 |𝑥𝑖 )𝑃(𝑥𝑖 ) 𝑖 = arg max𝑥 ෍ log 𝑃(𝑦𝑖 |𝑥𝑖 ) + log 𝑃(𝑥𝑖 ) 𝑖

18 MAP復号のViterbiアルゴリズム (0) 𝑀(𝑣0 ) ← 0 For 𝑖 ← 1, . . . , 𝑛 do (𝑖) For all 𝑏 such that 𝑣𝑏 exists do (𝑖) (𝑖−1) 𝑀(𝑣𝑏 ) ← max𝑏’ 𝑀(𝑣𝑏’ ) + log𝑃(𝑦𝑖 |𝑥𝑖 ) + log𝑃(𝑥𝑖 ) (𝑖−1) (𝑖) where 𝑥𝑖 = 𝑙(𝑣𝑏’ , 𝑣𝑏 ) Mark the edge with the highest probability End For End For

19 畳み込み符号 • これまで見てきた符号は「ブロック符号」 • メッセージ長と符号長が決まっている • 固定長のメッセージに対して一対一に符号語が割り当てられる • 畳み込み符号 (Convolutional Code) • 入力に対して逐次的に出力を決定する • 長さが決まっていない（入力した分だけ出力する） • 入力1シンボルに対して出力Nシンボル（符号化率 1/N） • 過去と現在の入力から現在の出力が決定する • 過去Sシンボルのメッセージを利用（拘束長 S+1）

畳み込み符号の例 （フィードフォワード型、非再帰型） • 入力 𝑚1 , 𝑚2 , … (𝑚𝑖 = 0 for 𝑖 ≤ 0) (1) (2) • 出力 𝑥𝑖 = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 = 𝑚𝑖 + 𝑚𝑖−2 𝑆 … , 𝑚3 , 𝑚2 , 𝑚1 𝑚𝑖 (𝑛) (𝑛) 𝑥𝑖 = ෍ 𝑎𝑘 𝑚𝑖−𝑘 𝑘=0 𝑚𝑖−1 𝑚𝑖−2 畳み込み演算 + + (2) 𝑥𝑖 (1) 𝑥𝑖 20

21 畳み込み符号 (𝑛) • 𝑥𝑖 (𝑛) = σ𝑆𝑘=0 𝑎𝑘 𝑚𝑖−𝑘 • 行列形式による表示 (1) 𝑚𝑖 𝑥𝑖 ⋮ • 𝒙𝑇𝑖 = =𝐴 ⋮ (𝑁) 𝑚𝑖−𝑆 𝑥𝑖 先ほどの例では 𝐴 = 1 1 1 0 1 1 • 例：𝑚 = 1 0 1 0 1 0 0 1 0 0 1 1 0 1 1 • 𝑥1𝑇 = 𝐴 0 = 𝑥2𝑇 = 𝐴 1 = 𝑥3𝑇 = 𝐴 0 = 𝑥4𝑇 = 𝐴 1 = 0 0 0 1 0 0 0 1 • 出力 11100010…

22 畳み込み符号とトレリス • 畳み込み符号は長さが不定なので、ブロック符号のような復号 法が使えない→トレリスによる復号 • 畳み込み符号のトレリスの特徴 • 各時刻で2𝑆 の状態がある。状態は直前のSシンボルに対応 • 例えばS=2の場合 s (2) s (1) 𝑚𝑖 が与えられたとき、 1 2 𝑠 , 𝑠 , 𝑚𝑖 から出力を計算 … , 𝑚3 , 𝑚2 , 𝑚1 𝑚𝑖 𝑚𝑖−1 𝑚𝑖−2 𝑠 (1) ← 𝑠 (2) 𝑠 (2) ← 𝑚𝑖 + +

23 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 10 01 11 入力1 (1) 𝑥𝑖 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 = 𝑚𝑖 + 𝑚𝑖−2

24 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 10 01 11 00 入力1 (1) 𝑥1 (1) 𝑥𝑖 (2) = 0 + 0 + 0, 𝑥1 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 =0+0 = 𝑚𝑖 + 𝑚𝑖−2

25 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 入力1 (1) 𝑥𝑖 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 00 11 10 01 11 (1) 𝑥1 (2) = 1 + 0 + 0, 𝑥1 =1+0 = 𝑚𝑖 + 𝑚𝑖−2

26 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 10 01 11 入力1 00 00 11 11 (1) 𝑥𝑖 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 = 𝑚𝑖 + 𝑚𝑖−2

27 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 入力1 00 00 11 11 (1) 𝑥𝑖 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 10 10 01 11 (1) 𝑥1 (2) = 0 + 1 + 0, 𝑥1 =0+0 = 𝑚𝑖 + 𝑚𝑖−2

28 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 入力1 00 00 11 11 (1) 𝑥𝑖 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 10 10 01 01 11 (1) 𝑥1 (2) = 1 + 1 + 0, 𝑥1 =1+0 = 𝑚𝑖 + 𝑚𝑖−2

29 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 𝑥𝑖 00 00 00 11 11 11 10 10 01 01 11 (1) 入力1 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 = 𝑚𝑖 + 𝑚𝑖−2

30 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 00 11 (1) 入力1 00 11 𝑥𝑖 11 10 10 01 01 01 11 = 𝑚𝑖 + 𝑚𝑖−2 00 11 10 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 (1) 𝑥1 (2) = 0 + 0 + 1, 𝑥1 =0+1

31 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 (1) 入力1 𝑥𝑖 00 00 00 11 11 11 = 𝑚𝑖 + 𝑚𝑖−2 11 10 10 10 01 01 01 11 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 (1) 00 𝑥1 (2) = 1 + 0 + 1, 𝑥1 =1+1

32 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 (1) 入力1 𝑥𝑖 00 00 00 11 11 11 = 𝑚𝑖 + 𝑚𝑖−2 11 10 10 10 01 00 (1) 01 01 01 11 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 𝑥1 (2) = 0 + 1 + 1, 𝑥1 =0+1

33 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 (1) 入力1 𝑥𝑖 00 00 00 11 11 11 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 = 𝑚𝑖 + 𝑚𝑖−2 11 10 10 10 01 01 00 01 01 11 10 (1) 𝑥1 (2) = 1 + 1 + 1, 𝑥1 =1+1

34 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 (1) 入力1 𝑥𝑖 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 00 00 00 00 11 11 11 11 11 11 10 10 10 01 01 00 10 01 01 11 10 01 01 10 00 = 𝑚𝑖 + 𝑚𝑖−2

35 畳み込み符号とトレリス 入力0 𝑠 (2) 𝑠 (1) 00 (1) 入力1 𝑥𝑖 (2) = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 00 00 00 00 00 11 11 11 11 11 11 11 11 10 10 10 01 01 00 10 00 10 01 01 11 10 01 01 10 01 01 10 = 𝑚𝑖 + 𝑚𝑖−2 00

36 畳み込み符号とViterbiアルゴリズム • 畳み込み符号を入力してトレリスをたどると、符号の終端でト レリスの上端に到達しない • 過去の入力𝑠 (2) 𝑠 (1) = 00の場合が上端 • →最後にS個の0を入力→「終端した畳み込み符号」 • 終端した畳み込み符号にはViterbiアルゴリズムが適用できる •例 • さきほどの畳み込み符号 • メッセージ 010 →符号語 001110 • 最後に00を追加→メッセージ 01000 →符号語 0011101100

37 終端した畳み込み符号 入力0 𝑠 (2) 𝑠 (1) 00 入力1 メッセージ 010 + 終端 00 00 00 00 00 00 11 11 11 11 11 11 11 11 10 10 10 01 01 00 10 00 10 01 01 11 10 01 01 10 01 01 10 00

38 Viterbiアルゴリズムの適用 𝑠 (2) 𝑠 (1) 00 0 00 11 11 11 00 00 00 00 00 00 11 11 11 11 11 11 11 11 10 10 10 01 01 00 10 00 10 01 01 11 10 01 01 10 01 01 10 00

39 Viterbiアルゴリズムの適用 00 𝑠 (2) 𝑠 (1) 00 0 00 0 11 10 11 11 11 00 00 00 00 00 11 11 11 11 11 11 11 2 10 10 01 01 00 10 00 10 01 01 11 10 01 01 10 01 01 10 00

40 Viterbiアルゴリズムの適用 00 𝑠 (2) 𝑠 (1) 00 0 00 11 0 2 11 11 10 00 0 2 11 00 00 00 00 11 11 11 11 11 11 10 10 01 11 10 00 10 3 01 01 01 11 00 3 10 01 01 10 01 01 10 00

41 Viterbiアルゴリズムの適用 00 𝑠 (2) 𝑠 (1) 00 0 00 11 0 2 11 11 10 00 11 0 2 00 00 00 11 11 11 11 11 11 00 10 10 01 11 3 2 10 00 01 01 01 11 3 10 1 3 01 00 10 01 1 10 01 01 10 00

42 Viterbiアルゴリズムの適用 00 𝑠 (2) 𝑠 (1) 00 0 00 11 0 2 11 11 10 00 11 0 2 01 00 3 00 11 11 11 2 10 00 1 01 3 1 11 10 3 10 00 2 01 01 01 11 00 11 3 01 00 11 10 10 11 01 01 1 10 2 10 00

43 Viterbiアルゴリズムの適用 00 𝑠 (2) 𝑠 (1) 00 0 00 11 0 2 11 11 10 00 11 0 2 01 00 3 00 11 11 11 2 10 00 1 01 3 1 11 10 3 10 00 10 2 00 01 01 01 1 1 3 2 01 01 11 00 11 3 01 00 11 10 10 11 2 10 3

44 Viterbiアルゴリズムの適用 00 𝑠 (2) 𝑠 (1) 00 0 00 11 0 2 11 11 10 00 11 0 2 01 00 3 00 11 11 11 2 10 00 1 01 3 1 11 10 3 10 00 10 2 00 01 01 01 1 1 3 2 01 01 11 00 11 3 01 00 11 10 10 11 2 10 3

45 演習 次の畳み込み符号を考える。 (1) (2) • 𝑥𝑖 = 𝑚𝑖 + 𝑚𝑖−1 + 𝑚𝑖−2 , 𝑥𝑖 = 𝑚𝑖 + 𝑚𝑖−1 1. メッセージ1011を符号化した時の符号語を示せ。 2. 受信語を10シンボルまで受理するトレリスを示せ。 3. 受信語が1100100010であった場合、符号語とメッセージを復 号せよ。