<- 第参版 -> NAIST-IS-MT9751066: Daisuke Tanaka

MAP復号法に対する再帰的アルゴリズム

田中大介 (9751066)


符号のトレリスダイアグラムを利用した復号アルゴリズムとして, 最尤復号法 を実現するビタビアルゴリズムや, 事後確率最大化復号(MAP復号)を実現する BCJRアルゴリズムが広く知られている. これらのアルゴリズムでは, トレリスダイアグラムを単なる有向グラフとしてのみ利用する為に, トレリスダイアグラムが巨大になるブロック符号や符号長の長い符号に対しては, 非常に計算量が大きくなる. この問題に対し, 近年, 線形ブロック符号の構造を 有効に利用することで効率的に最尤復号を行うことが可能な再帰的最尤復号法 が提案されている. 本論文では 再帰的最尤復号法のアイディアを$\MAP$復号法に適用することにより, 二元線形符号に対する効率のよい$\MAP$アルゴリズムを提案する. $\MAP$復号はTurbo符号などの繰り返し復号アルゴリズムでの重要性が 指摘されており, MAP復号の効率がTurbo符号全体の効率に大きく影響する. 提案するアルゴリズムはBCJRアルゴリズムよりも効率的であるだけでなく, 並列処理やパイプライン処理に適しているため, スループットの高い復号器 の実現にも有利である. 計算機シミュレーションによりいくつかの代表的なブロック 符号の復号に要する計算量を評価したところ, 特に符号化率の低い符号に対しては, 復号複雑さが大きく軽減されることが判明した.