重み分布の反復計算による最良畳込み符号の効率的探索法

小上 祐輝  笹野 博  曽根 直人  毛利 公美  西村 卓也  森井 昌克  

誌名
電子情報通信学会論文誌 A   Vol.J88-A   No.6   pp.730-738
発行日: 2005/06/01
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: 符号理論
キーワード: 
畳込み符号,  重み分布,  列距離関数,  反復計算,  

本文: PDF(1.1MB)
>>論文を購入


あらまし: 
本論文では,多数の符号の中から最良畳込み符号を効率的に探索する方法を提案する.一般に,最良畳込み符号は対象となる符号すべての重み分布を求めることにより探索される.また,重み分布は符号の木に対する走査により計算でき,この際の効率的なアルゴリズムとして列距離関数をしきい値として用いるFASTが知られている.対象となる符号が比較的多く,すべての符号の重み分布を計算するために膨大な計算が必要となる場合,重み分布の計算の過程で符号の棄却判断を行い非最良符号を棄却すれば,最良符号の重み分布のみを計算することができ,効率的に最良符号を探索できる.この棄却判断をより効果的に行うために,符号語のハミング重みに一定の制限を設け重み分布を反復計算する方法を提案する.提案手法はFASTを用いる方法に比べて,走査が行われるノードの数を少なく非最良符号を棄却でき,同時に不必要な列距離関数計算を省略できることを示し,実際に2種類の符号の集合に対して最良符号の探索を行い,探索時間が著しく短縮されることを確認する.