第 8 章 たたみ込み符号 65
8.3 たたみ込み符号の復号
8.3.4 Viterbi 復号 (Viterbi アルゴリズム )
硬判定後の系列と, 全ての符号語のHamming距離を計算し,その中でHamming距離が最小となる符号語 を選べば,復号は可能である. が,この方法には膨大な計算が必要であり,現実的な方法とは言い難い. そこで, たたみ込み符号の復号には, 主にViterbi 復号(Viterbi decoding)という方法が使われる.
Viterbi復号とは, Viterbiアルゴリズムを用いてたたみ込み符号を復号することを表し,このViterbiアル
ゴリズムは,トレリス線図を用いて説明することができる.
Viterbiアルゴリズムは例を通して見るとうまく理解することができる. ということで, 次のような符号器を
考え,そのトレリス線図を用いて, Viterbiアルゴリズムを理解することを目標としよう.
m D1 D0
L
c1
c0
74 第8章 たたみ込み符号
この符号器の初期状態(s1, s0) = (0, 0)とする. このとき, 時点t=0から時点t=4までのトリレス線図を 完成させてみよう. 入力が1つだけなので,それほど複雑なトレリス線図が出来上がることはない.
時点 0 1 2 3 4
(11) (10) (01) (00)
初期状態（スタート）
初期状態(00)がスタートとなることに注意すると,次のようなトレリス線図を得ることができる.
時点 0 1 2 3 4
(00) (00)
(01)
(10)
(11)
0/00 0/00 0/00 0/00
1/01 1/01 1/01 1/01
0/00 1/01
0/00 0/00
0/11 0/11
1/10 1/10
1/01 1/01
0/11 0/11
1/10 1/10
このように,符号器に対応する,時点t=0からt=4までのトレリス線図を求めることができた. さて,ここで,受信者が受信信号を硬判定復号して得られた離散信号を01001010としよう.
|{z}01 |{z}00 |{z}10 |{z}10
このように,硬判定により得られた離散信号は, 2シンボルずつ,トレリス線図の , , , の部分と対応し ている. このことを念頭に置いて,硬判定後の系列を2ビットずつ区切った各部分と:::::: ,対応するトレリス線図 の各枝*7の
::::出力のHamming距離を計算し, トレリス線図に書き込んでみよう(ただし, 入出力の記述は省 略することにする).
*7トレリス線図の矢印を枝(brunch)と呼ぶ
8.3 たたみ込み符号の復号 75
時点 0 1 2 3 4
(00) (00)
(01)
(10)
(11)
1 0 1 1
0
1
2 2
0 1
1 1
1 1
0 0
2 2
1 1
0 0
00 10 10
01
Def : ブランチメトリック
¶ ³
トレリス線図の各枝に対応する出力と,硬判定後の離散系列の対応する各部分のHamming距離の値を, ブランチメトリック(brunch metric), または枝尤度(brunch likelihood)という. ブランチメト リックは,トレリス線図の各枝に対して定まる.
µ ´
さらに今度は, 時点0から順番に時点4まで, 各状態を表す°の中に, その°にたどり着くまでにかかるブ ランチメトリックの総和のうち最小のものを記入しよう. この値を, パスメトリック(pass metric)という. そして,::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::その時点,その状態までのブランチメトリックの総和を最小にするような経路を太線で強調しよう, それ以外の経路は今後使うことはない. この太線で強調することができた経路を生き残りパス(survivor pass)*8という. 全ての°にパスメトリックを記入し,生き残りパスが全て判明する流れを以下に示そう.
1.
時点 0 1 2 3 4
(00) (00)
(01)
(10)
(11)
1 0 1 1
0
1 2 2
0 1
1 1
1 1
0 0
2 2
1 1
0 0
00 10 10
01 0
*8残存経路,生存者経路とも呼ばれることがある.
76 第8章 たたみ込み符号
2.
時点 0 1 2 3 4
(00) (00)
(01)
(10)
(11)
1 0 1 1
0
1 2 2
0 1
1 1
1 1
0 0
2 2
1 1
0 0
00 10 10
01
0 1
0
3.
時点 0 1 2 3 4
(00) (00)
(01)
(10)
(11)
1 0 1 1
0
1 2 2
0 1
1 1
1 1
0 0
2 2
1 1
0 0
00 10 10
01
0 1
0
1
0
2
1
4.
時点 0 1 2 3 4
(00) (00)
(01)
(10)
(11)
1 0 1 1
0
1 2 2
0 1
1 1
1 1
0 0
2 2
1 1
0 0
00 10 10
01
0 1
0
1
0
2
1
1
1 2
0