貪欲法に基づく順序付基底を構成するアルゴリズムと生成される線形符号について

概要

論文の詳細を見る
本稿では, 順序付基底の構成アルゴリズムを提案する. 本アルゴリズムは, 与えられた有限体F_q, 符号長n, 次元kに対して, 大きなFeng-Rao設計距離d_<FR>を与える線形符号の構成を目的とするものである. Feng-Rao設計距離の大きい符号を構成する問題は, 良好な順序付基底を構成する問題に帰着できる. ここで, 順序付基底とは, 番号付けされているF^n_qの基底である. 本稿では, 代数幾何に基づく手法とは異なる観点から順序付基底構成問題へのアプローチを試みる. 提案する基底構成アルゴリズムは, 初期基底を順次, 改良していく手法に基づいており, その時間計算量はO(n^4)である. 本アルゴリズムは, 任意の有限体, 符号長に対して適用可能である. そのため従来, 符号構成が困難であったパラメータにおいても符号を構成できる. また, このアルゴリズムにより得られる符号は, Feng-Rao復号法により, ⌊(d_<FR>-1)/2⌋までの限界距離復号がO(n^3)で可能である.
社団法人電子情報通信学会の論文
1999-03-11