A*アルゴリズムを用いた線形ブロック符号の軟判定最尤/準最尤復号に関する研究

向井 友弘 (9651109)


誤り訂正符号において、符号化率を固定して、符号長当たりの相対的な最小 距離(誤り訂正能力)を高めるためには、符号長を大きくする必要がある。 しかし、符号長が大きくなると、一般に、復号のための計算量は指数的に 増加してしまうため、空間的・時間的に、より効率の良い復号アルゴリズム が求められている。

本発表では、従来、主に人工知能の分野で用いられて来た、A*アルゴリズム と呼ばれるアルゴリズムを、線形ブロック符号の復号に適用し、その特性の 検討、および、その復号複雑さについて他の復号法との比較を行なう。この アルゴリズムを用いて最尤復号を行なう場合には、通信路のSN比が高い所では 計算量を低く抑えることができるが、通信路のSN比の悪化に伴い、計算量が 指数的に増大するという問題点があった。 そこで本発表では、計算量の上限を設定することにより準最尤復号を行ない、 SN比の低い所においては、復号誤り率をさほど大きくすること無く計算量を 大幅に減少させ得ることを示す。 さらに、復号の過程で得られた候補符号語に対し、それが、符号の最小距離 を利用した最尤符号語になるための十分条件を満たしているかを確かめる ことにより計算量の減少を図り、特に符号化率の低い符号に対しては、その 方法が有効となることも示す。