双対多点代数曲線符号の高速リスト復号に関する研究

点击翻译按钮获取中文摘要

本研究では、大きな符号において優れた性能を持つことが知られている多点代数曲線符号の双対符号に対して、１点代数曲線符号に対する効率的な限界距離復号法として知られているBerlekamp-Massey-Sakata(BMS)アルゴリズムを拡張することによって、訂正限界を超えた復号を可能にするリスト復号の効率的な復号法を与える。リスト復号は可能性のある符号を列挙する復号法であり、復号には時間がかかる。BMSアルゴリズムを利用したリスト復号では、未知シンドロームを求める段階で出現する極小多項式によって発生する分岐をすべて求めていくことによって実現できる。この無駄な分岐を少なくしてリスト復号を効率的に行うために、すべての分岐を探索するのではなく確率的に可能性の高い極小多項式を選択して計算を進める高速復号法を検討することが目的である。本年度は、前年度までに１点代数的符号対するリスト復号において調査してきた、（１）多数決の際の票数に関係する各シンドロームと極小多項式の関係と（２）極小多項式の次数とスパンから算出される多数決の票数が不足する場合のシンドローム値の関係から得られる知見を利用して、確率的にシンドローム値を定めることにより無駄な分岐を減少させる方法について検討した。結果としては、無駄な分岐を減少させる効率的なリスト復号法には至っておらず、より十分な検討を行い、より良いシンドローム値を選択するための情報について調べる必要がある。