A-15 新問 類似 FA507 A-15、FA401 A-12
トレリス線図を用いたビタビ復号法の動作についての問題です。過去問ではシンプルなトレリス線図が出されていましたが、今回は見ただけでやる気をなくすような複雑な線図です。でも地道にやるしかないんです。さあ、頑張ろう（笑）。
(2)で与えられた受信符号系列「00 10 00 10 00 11 11」を出力するであろう経路をトレリス線図に書き込んでみましょう（ここでは連続しなくても、対応する経路が2つあっても構いません）。
この経路（青点線）と経路①および経路②で異なる部分をすべて抽出し、その部分の符号の異なるビット数の総和を計算します。（ちなみにこのふたつの符号で異なるビット数（0と1が食い違っている数）をハミング距離といいます。
【経路①】
3箇所の経路が異なり、符号誤りの総和は3ビットです。すなわちハミング距離=3になります。
【経路②】
4箇所の経路が異なり、符号誤りの総和は5ビットです。すなわちハミング距離=5になります。
これらより経路①のPM=3で最小となり生き残りとなります。最後に経路①に対応する入力系列を考えればおしまいです。
まず状態遷移図を理解します。
題意にある通り、シフトレジスタT1T2の初期状態は”00”ですから左端の円（下図赤丸）からスタートします。ここから①入力uに’0’が入ると②出力Ｃ1Ｃ2は”00”となり③シフトレジスタは”00”のままです。
次に①入力uに’1’が入ると②出力Ｃ1Ｃ2は”11”となり③シフトレジスタは下端の円（青丸）”10”の状態に変わります。
他の状態も同様に考えればOKです。
さて経路①に対応する入力系列を考えましょう。シフトレジスタT1T2の初期状態は”00”であることを考えると、経路①は最初の出力Ｃ1Ｃ2が’00’なので、入力u=0であり、シフトレジスタT1T2は’00’のままです。次に出力Ｃ1Ｃ2が’11’になるので入力u=1になります。従って入力系列は’0 1･･･から始まることがわかるので「0-1-1-0-1-0-0」が正しい答えになります。
一応これで解答が得られますが、解答枝にある入力系列が正しく経路①または②を表すかどうかを調べておきましょう。
①入力系列「0-1-1-0-1-0-0」の場合
この場合は経路①を通りますね。
②入力系列「0-0-0-1-0-0-0」の場合
これは経路②ですね。
大変お疲れ様でした・・・