表題番号:2000A-156 日付:2002/02/25
研究課題誤り訂正符号における最ゆう復号法の効率化に関する研究
研究者所属(当時) 資格 氏名
(代表者) 理工学部 助手 小林 学
研究成果概要
 本研究は携帯電話や衛星通信等の情報通信において、雑音の影響を取り除く誤り訂正符号に対する復号法を対象としている。中でも最ゆう復号法は復号誤り確率を最小とするが、最もゆう度の高い符号語を探索する必要があるため、多くの計算量を要するという欠点をあわせ持つ。本研究はこの最ゆう復号法の計算量を従来手法よりさらに低減することを目的としている。従来効率的な最ゆう復号法として、誤り訂正符号の符号化を利用する復号法が知られている。これは通信路から受信した系列の信頼度の高い位置を情報シンボルとみなし、この情報シンボルを緩やかに変化させながら複数回符号化を行うことにより候補符号語を出力し、ゆう度が最大となる最ゆう符号語を探索する復号法である。これにより復号に必要となる平均計算量の大幅な低減が実現されている。
 本研究では、従来独立に複数回繰り返していた符号化に対し、以前候補符号語として出力された符号語を利用することにより、次に出力すべき候補符号語を非常に効率良く求める手法を提案した。また従来符号化を行い、候補符号語を生成してからその符号語のゆう度(事後確率に比例する)を独立に求めていたのに対し、複数符号語のゆう度を同時に計算することによりさらなる計算量低減を実現した。これらの技術をAIの探索手法であるA*アルゴリズムを用いる最ゆう復号法に応用し、結果的に符号化する回数が低減され、かつ符号化1回に必要となる計算量も減少することにより、復号全体に必要となる計算量を大幅に低減した。
 またゆう度を求めるためには候補符号語に対し実数上の演算が必要となるが、0、1のシンボル情報のみから、得られた符号語が最ゆうとはなりえないことを判定する十分条件を導き、これを符号語が得られるたびに判定することにより、数多くの不必要なゆう度計算のための実数演算量を低減した。
 本研究により、従来計算量が問題となっている最ゆう復号法に対し、その効率化を実現することができた。これらの提案は、復号誤り確率の多少の劣化を許しても、更なる大幅な計算量の提言を実現する準最ゆう復号法へ応用することも容易に可能である。計算量低減の度合いの理論的保証が重要な今後の課題である。