著者
阪田 省二郎 栗原 正純
出版者
電気通信大学
雑誌
基盤研究(C)
巻号頁・発行日
2002

本研究は、本研究代表者が以前から行ってきた代数幾何符号の高速復号法の研究を発展させつつ、「与えられた入出力系列対を許容する線形帰還シフトレジスタの合成問題」を高速に解くアルゴリズムを確立することが最大の目的である。従来よく研究されてきた「与えられた系列を出力する線形帰還シフトレジスタの合成問題」は、代数的符号、特にReed-Solomon符号やBCH符号のような実用上も重要な誤り訂正符号、さらには、次世代誤り訂正符号として有望視されている代数幾何符号等の高速復号法と関係が深く、情報通信工学において重要な意味を有しているのに対し、本研究課題は、テプリッツ、および、ブロック・テプリッツ型の非同次連立1次方程式の高速解法に対応しており、拡張した問題を扱っている。これは、代数的符号の高速復号法と離れても、線形システムに対するWiener-Hoph方程式の高速解法として、それ自身、重要な意義を有する。本研究では、まず1次元入出力系列対の場合について、本問題を解く高速アルゴリズムを与え、実際に、その高速性を計算機シミュレーションにより確認した。このアルゴリズムの理論面については、2002年6月、スイスのLausanneにおいて開催されたISIT-2002(2002年IEEE国際情報理論Symposium)で発表した。次に、この結果を、Reed-Solomon符号やBCH符号のリスト復号の第2段階における有理関数体上での因数分解の高速解法に応用できることを明らかにした。さらに、多次元(2次元以上)の入出力系列対の場合にアルゴリズムを拡張し、それを代数幾何符号のリスト復号の第2段階における代数関数体上での因数分解の高速解法に応用可能であることを理論的に示した。これらの成果を、2002年6月末から7月初めに、安房鴨川と横浜において引き続き開催されたAEWIT-2003(2003年アジア・ヨーロッパ情報理論研究ワークショップ)、および、ISIT-2003(2003年IEEE国際情報理論Symposium)において発表した。当初、代数的誤り訂正符号のより高精度の復号という最終的な研究目標への前段階として、システム理論的な問題の形で本研究課題を設定したが、その目標にほぼ沿った形で、Reed-Solomon符号や代数幾何符号のリスト復号への応用が可能であることを明らかにした。また、関連する研究として、代数曲線符号の並列複号、複合誤り訂正符号についての成果を、電子情報通信学会論文誌に共著論文として出版した。