通信符号理論 09

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

2 確率推論と復号 • これまでは「ある誤りシンボル数以下の場合には元に戻る」と いう議論で確率は関係なかった • 今回は確率を使った議論 送信者 X 受信者 Y 送信シンボル系列 𝑥 送信確率𝑃𝑋 (𝑥) 受信シンボル系列 𝑦 受信確率𝑃𝑌 (𝑦)

3 確率推論と復号 • 同時確率 𝑃𝑋𝑌 (𝑥, 𝑦) • 送信側で𝑥を送信し、かつ受信側で𝑦を受信する確率 • 条件付確率 𝑃𝑌|𝑋 (𝑦|𝑥) • 送信側で𝑥を送信した条件下で、受信側で𝑦を受信する確率 • 条件付確率 𝑃𝑋|𝑌 (𝑥|𝑦) • 受信側で𝑦が受信された条件下で、送信側で𝑥を送信していた確率

4 ベイズ則 • 条件付確率を入れ替える 𝑃𝑌|𝑋 𝑦 𝑥 𝑃𝑋 (𝑥) 𝑃𝑋|𝑌 𝑥 𝑦 = 𝑃𝑌 (𝑦) • 事前確率(prior probability) 𝑃𝑋 (𝑥) • 事後確率(posterior probability) 𝑃𝑋|𝑌 (𝑥|𝑦)

5 確率的推論 • 復号＝受信語𝑦を見て送信符号語𝑥を推定する＝ 「𝑦を受信したときに送信された確率が最も高い𝑥を求める」 𝑥ො = arg max 𝑃𝑋|𝑌 (𝑥|𝑦) 𝑥 𝑃𝑌|𝑋 𝑦 𝑥 𝑃𝑋 (𝑥) = arg max 𝑥 𝑃𝑌 (𝑦) = arg max 𝑃𝑌|𝑋 𝑦 𝑥 𝑃𝑋 (𝑥) 𝑥 ブロックMAP復号 (Maximum A Posteriori)

6 ブロックMAP復号と最尤復号 • 確率的推論の枠組み 𝑥ො = arg max 𝑃𝑋|𝑌 𝑥 𝑦 𝑥 • ブロックMAP復号 𝑥ො = arg max 𝑃𝑌|𝑋 𝑦 𝑥 𝑃𝑋 (𝑥) 𝑥 尤度関数 • 最尤(ML)復号：事前確率が一定の場合 𝑥ො = arg max 𝑃𝑌|𝑋 𝑦 𝑥 𝑥

7 通信路：記憶性、無記憶 • 無記憶通信路 • あるシンボルの条件付確率 𝑃(𝑦𝑖 |𝑥𝑖 )が過去の系列に依存しない場合、 このような通信路を「無記憶通信路」と呼ぶ • ２元対称通信路は無記憶通信路の一種 • 無記憶の場合、𝑃(𝒚|𝒙) = ς𝑖 𝑃(𝑦𝑖 |𝑥𝑖 ) • 記憶性通信路 • シンボルの生起確率が過去の系列に依存する • マルコフモデルによるモデル化

8 Gilbert-Elliott通信路 • 記憶性通信路のうち、比較的 単純なもの • 誤りが起きにくい状態 (Good) と起きやすい状態 (Bad) に分か れる • 𝑃(𝐵|𝐺) = 𝑏, 𝑃(𝐺|𝐵) = 𝑔 • Good状態の誤り確率は 𝑃𝐺 、 Bad状態では𝑃𝐵 • 𝑃𝐺 < 𝑃𝐵 M. Rezaeian, DOI: 10.1109/AUSCTW.2005.1624226

9 Gilbert-Elliott通信路 • Gilbert-Elliott通信路はバース ト誤りを表現できる • Bad状態が続けば誤りが連続し て起きやすくなる • 𝑃𝐺 = 0, 𝑃𝐵 = 1の場合が考えやす い M. Rezaeian, DOI: 10.1109/AUSCTW.2005.1624226

10 Gilbert-Elliott通信路 • 𝑃𝐺 = 0, 𝑃𝐵 = 1の場合 • Bad状態の停留確率を𝜆とすれば 1−𝑏 𝑔 1−𝜆 1−𝜆 = 𝑏 1−𝑔 𝜆 𝜆 𝑏 より𝜆 = 𝑔+𝑏 となる。 これが平均シンボル誤り率 • Bad状態で𝑛シンボル連続で誤る確率は 1 − 𝑔 𝑛−1 𝑔 𝑔 1 𝑛−1 平均はσ∞ 𝑛 1 − 𝑔 𝑔 = = 2 𝑛=1 𝑔 1− 1−𝑔 これが平均バースト長になる Average burst length 10.0 7.5 5.0 2.5 0.25 0.50 Good probability (g) 0.75

11 トレリスによる符号の表現 • 復号とは、符号𝐶の中から、何らかの意味で受信語𝑦に最も「合 う」符号語を選ぶ過程 • ハミング距離最小、事後確率最大、尤度最大など • ２元対称通信路で尤度最大＝ハミング距離最小 • これまでの符号（Hamming符号、Reed-Solomon符号など）で は、探索を効率的に行う方法があった • 全探索なら計算量は 𝑂(2𝑛 ) だが、上記の方法では多項式オーダー • 事後確率最大や尤度最大の基準で復号することはできない

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

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

14 トレリスを使うと何がいいのか • 受信語と符号語の比較のしかた • 通常は受信語と符号語を「語ごとに」比較する • トレリスを使うと、受信語と複数の符号語を「桁ごとに」比較しなが ら最良の符号語（＝トレリス上の経路）を選ぶことができる ＝Viterbi Algorithm 11010 ハミング距離最小解だけでな く、事後確率最大や尤度最大 の解もほぼ同じアルゴリズム で求めることができる

15 トレリスを使うと何がいいのか • トレリスでしか表現できない符号がある • これまで扱ってきた符号は符号長が決まっている＝「ブロック符号」 • ブロックの長さが決まっておらず、「入力されたメッセージの分だけ 符号化された系列を出力する」というタイプの符号がある（畳み込み 符号） →このような符号ではトレリスを使った復号しかできない 010011… Encoder 001110111110…

16 トレリスに関する内容 • ブロック符号で、どうやってトレリスを作るのか • シンドロームトレリス • トレリスを使って、どうやって復号するのか • Viterbiアルゴリズム • 最尤復号、事後確率最大復号 • 畳み込み符号

17 シンドロームトレリス • 検査行列 𝐻 = (𝒉1 ⋯ 𝒉𝑛 ) の行数を 𝑚 とする • 𝑚ビットの２進数を0 ≤ 𝑏 < 2𝑚 とするとき、トレリスのノード (0) (1) (𝑛) 𝑣𝑏 , 𝑣𝑏 , . . . , 𝑣𝑏 を用意する i=0 b=00 b=01 b=10 b=11 1 2 3 𝑛 = 3, 𝑚 = 2 の場合 たとえば下の検査行列など 1 0 1 𝐻= 0 1 1

18 シンドロームトレリス (𝑖) (𝑖+1) • すべての𝑣𝑏 から𝑣𝑏 へのエッジを作り、ラベルを0とする i=0 b=00 b=01 b=10 b=11 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 𝐻= 1 0 0 1 1 1

19 シンドロームトレリス (𝑖) (𝑖+1) • すべての𝑣𝑏 から𝑣𝑏+ℎ𝑖+1 へのエッジを作り、ラベルを1とする ℎ𝑖 = 10 i=0 01 1 11 2 1 0 1 0 1 1 ℎ1 = (1 0) ℎ2 = (0 1) ℎ3 = (1 1) 𝐻= 3 b=00 b=01 b=10 b=11 1 (0) (1) (1) 𝑣00 から𝑣00+10 = 𝑣10 に1のエッジを 追加

20 シンドロームトレリス (𝑖) (𝑖+1) • すべての𝑣𝑏 から𝑣𝑏+ℎ𝑖+1 へのエッジを作り、ラベルを1とする ℎ𝑖 = 10 i=0 01 1 11 2 1 0 1 0 1 1 ℎ1 = (1 0) ℎ2 = (0 1) ℎ3 = (1 1) 𝐻= 3 b=00 b=01 b=10 b=11 1 1 (0) (1) (1) 𝑣01 から𝑣01+10 = 𝑣11 に1のエッジを 追加

21 シンドロームトレリス (𝑖) (𝑖+1) • すべての𝑣𝑏 から𝑣𝑏+ℎ𝑖+1 へのエッジを作り、ラベルを1とする ℎ𝑖 = 10 i=0 01 1 11 2 1 0 1 0 1 1 ℎ1 = (1 0) ℎ2 = (0 1) ℎ3 = (1 1) 𝐻= 3 b=00 b=01 b=10 b=11 1 1 (0) (1) (1) 𝑣10 から𝑣10+10 = 𝑣00 に1のエッジを 追加

22 シンドロームトレリス (𝑖) (𝑖+1) • すべての𝑣𝑏 から𝑣𝑏+ℎ𝑖+1 へのエッジを作り、ラベルを1とする ℎ𝑖 = 10 i=0 01 1 11 2 1 0 1 0 1 1 ℎ1 = (1 0) ℎ2 = (0 1) ℎ3 = (1 1) 𝐻= 3 b=00 b=01 b=10 b=11 1 1 (0) (1) (1) 𝑣11 から𝑣11+10 = 𝑣01 に1のエッジを 追加

23 シンドロームトレリス (𝑖) (𝑖+1) • すべての𝑣𝑏 から𝑣𝑏+ℎ𝑖+1 へのエッジを作り、ラベルを1とする ℎ𝑖 = i=0 10 01 1 11 2 1 0 1 0 1 1 ℎ1 = (1 0) ℎ2 = (0 1) ℎ3 = (1 1) 𝐻= 3 b=00 b=01 b=10 b=11 以下同じ

24 シンドロームトレリス (0) (𝑛) • 𝑣0 を始点に、𝑣0 を終点に設定する ℎ𝑖 = i=0 b=00 b=01 b=10 b=11 10 01 1 11 2 3 1 0 1 0 1 1 ℎ1 = (1 0) ℎ2 = (0 1) ℎ3 = (1 1) 𝐻=

25 シンドロームトレリス • 始点から終点までつながった経路だけを残し、残りを削除 ℎ𝑖 = i=0 b=00 b=01 b=10 b=11 10 01 1 11 2 3 1 0 1 0 1 1 ℎ1 = (1 0) ℎ2 = (0 1) ℎ3 = (1 1) 𝐻=

26 シンドロームトレリス • 始点から終点までつながった経路だけを残し、残りを削除 ℎ𝑖 = i=0 b=00 b=01 b=10 b=11 10 01 1 11 2 3 1 0 1 0 1 1 ℎ1 = (1 0) ℎ2 = (0 1) ℎ3 = (1 1) 𝐻=

27 シンドロームトレリスは何をしているのか • 符号語𝒙 = (𝑥1 , . . . , 𝑥𝑛 )に対して、𝐻𝒙𝑇 = 0より 𝑥1 𝒉1 + 𝑥2 𝒉𝟐 + ⋯ + 𝑥𝑛 𝒉𝑛 = 0 である。 • 𝑥1 𝒉1 + 𝑥2 𝒉𝟐 + ⋯ + 𝑥𝑘 𝒉𝑘 = 𝒛𝑘 とおく(1 ≤ 𝑘 ≤ 𝑛)。 • 𝒛𝑛 = 0 • 𝒛𝑘+1 = 𝒛𝑘 + 𝑥𝑘+1 𝒉𝑘+1

28 シンドロームトレリスは何をしているのか • 𝒛𝑘 は𝑚ビットのベクトルなので、0~2𝑚 − 1に対応付けることができ る。 • 𝑥𝑘+1 = 0ならば、 𝒛𝑘+1 = 𝒛𝑘 + 𝑥𝑘+1 𝒉𝑘+1 =𝒛𝑘 • 𝒛𝑘 と𝒛𝑘+1 が同じなので、横方向の矢印に対応する 𝑘 0 𝒛𝑘 1 • 𝑥𝑘+1 = 1ならば、 𝒛𝑘+1 = 𝒛𝑘 + 𝑥𝑘+1 𝒉𝑘+1 =𝒛𝑘 + 𝒉𝑘+1 • ななめ方向の矢印に対応する 𝑘+1 𝒛𝑘 + 𝒉𝑘+1

29 シンドロームトレリスは何をしているのか • 最後に右上のノード（つまり𝒛𝑛 = 0）に到達する経路だけが 𝐻𝒙𝑇 = 0を満たすベクトルに対応する経路となる ℎ𝑖 = i=0 10 01 1 11 2 3 b=00 𝒛𝑛 = 00 b=01 𝒛𝑛 = 01 b=10 𝒛𝑛 = 10 b=11 𝒛𝑛 = 11

30 演習 • 次の検査行列で定義される符号のトレリスを作れ。 1 1 1 0 𝐻= 0 1 1 1