線形ブロック符号のトレリスダイアグラムの並列構造に関する研究

軟判定最尤復号の複雑さは符号Cのトレリスダイアグラム(以下,トレリス)Tの“複雑さ"によりほぼきまる.本研究では,線形符号のセクショントレリスの並列構造の解析,及び,それを利用した軟判定最尤復号器の実現検討に関して以下のような結果を得た.(1)与えられた線形符号をC,その状態数最小のトレリスダイアグラムをTと書く.与えられたh_1,h_2について,Tの第h_1記号から第h_2記号までのセクションの並列構造を詳細に解析し,(i)ラベルを除いて互いに同型である並列部分グラフ(以下,並列成分と略称)の個数,(ii)並列成分の始状態数,及び終状態数などをCやその部分符号の次元を用いて表した(発表論文1).また,(iii)基準となる並列成分を表すTの部分トレリスダイアグラムの構成,(iv)基準並列成分のラベルから,他の並列成分のラベルを求めるための各成分毎の入力記号変換,(v)隣接する二つのセクションの並列成分間の接続関係(前のセクションの各並列成分の各終状態が次のセクションのどの並列成分のどの始状態に等しいか)についても,Cに関係する符号を用いて表した(発表論文1).さらに,1つの並列成分について枝ラベルに基づきその内部構造を明らかにした(発表論文2).そして,それらを求めるプログラム群を作成した.(2)符号長64の3次のRM符号等についてマクロセルレベルでVLSIでの実現を検討した.その結果,この例の実現のためには,復号器の複雑度を減らす必要があることがわかった.解析結果を利用して高速化の手法を開発したので(発表論文2の付録参照),それを用いて復号器の複雑度をどの程度減らせるか現在検討中である.

軟判定最尤復号の複雑さは符号Cのトレリスダイアグラム(以下,トレリス)Tの“複雑さ"によりほぼきまる.本研究では,線形符号のセクショントレリスの並列構造の解析,及び,それを利用した軟判定最尤復号器の実現検討に関して以下のような結果を得た.(1)与えられた線形符号をC,その状態数最小のトレリスダイアグラムをTと書く.与えられたh_1,h_2について,Tの第h_1記号から第h_2記号までのセクションの並列構造を詳細に解析し,(i)ラベルを除いて互いに同型である並列部分グラフ(以下,並列成分と略称)の個数,(ii)並列成分の始状態数,及び終状態数などをCやその部分符号の次元を用いて表した(発表論文1).また,(iii)基準となる並列成分を表すTの部分トレリスダイアグラムの構成,(iv)基準並列成分のラベルから,他の並列成分のラベルを求めるための各成分毎の入力記号変換,(v)隣接する二つのセクションの並列成分間の接続関係(前のセクションの各並列成分の各終状態が次のセクションのどの並列成分のどの始状態に等しいか)についても,Cに関係する符号を用いて表した(発表論文1).さらに,1つの並列成分について枝ラベルに基づきその内部構造を明らかにした(発表論文2).そして,それらを求めるプログラム群を作成した.(2)符号長64の3次のRM符号等についてマクロセルレベルでVLSIでの実現を検討した.その結果,この例の実現のためには,復号器の複雑度を減らす必要があることがわかった.解析結果を利用して高速化の手法を開発したので(発表論文2の付録参照),それを用いて復号器の複雑度をどの程度減らせるか現在検討中である.