Call-by-Need型最尤復号法における探索戦略について

斉宮 誠 (9951008)


最尤復号法とは, 通信路を介して受信した信号系列から最も尤度の高い符号系列 を見つけるような復号法であり, 誤り訂正符号の復号法としては最も基本的 で重要なものである. 近年, 線形ブロック符号のための最尤復号アルゴリズムが いくつか提案されている. これらのアルゴリズムは演算数, 操作数の観点からは効率的で あるが, 復号器自身が符号の部分的なトレリス構造に関する情報を記憶する必要 があり, 空間計算量的にはまだ改善の余地があった. これに対し我々の研究グループは, 線形ブロック符号に対し効率良く最尤復号 を行うCall-by-Need型最尤復号法を提案している. この手法を用いて最尤復号を行う際には, 符号系列のある区間において, 局 所的最尤ベクトルの候補をすべて列挙し, その中で最も尤度が高いものを選択す るという操作が必要になる. 本研究では, 局所的最尤ベクトルの探索において尤 度の小さな候補ベクトルの計算をうまく「枝刈り」して省略する戦略を提案した. また, 計算機シミュレーションによって提案戦略の復号複雑さの評価を行っ た. その結果, 従来法より大幅に復号複雑さが改善された.