抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2600000, indirect: -)
The objective of this research is to develop an efficient algorithm for solving the problem of synthesizing linear feedback shift register allowing given pairs of input and output arrays by expanding our research results on fast decoding of algebraic geometric (AG) codes. The problem is an extension of the problem of synthesizing linear feedback shit register capable of generating given output arrays, which is closely related to fast decoding methods of practical algebraic codes such as RS codes, BCH codes and next-generation error-correcting codes, i.e. AG codes. The present problem treats nonhomogeneous Toeplitz and block-Toeplitz equations and their multidimensional extensions, while the former problem treats homogeneous Toeplitz and block-Toeplitz equations and their multidimensional extensions. Our problem is known as Wiener-Hoph equations in the field of linear system theory. As an outcome of our research, we have given an efficient method of solving our problem in case of pairs of one-dimensional input and output arrays, and presented our result in the IEEE 2002 International Symposium on Information Theory, in Lausanne, Switzerland, Jun 30-July 5,2000. Next, we have made clear that our method can be applied to fast factorization of polynomials over rational function field in the second stage of list decoding of polynomials over algebraic function field in the second stage of list decoding of AG codes, and presented these results in the Third Asian-European Workshop on Information Theory, in Awakamogawa, Jun 25-28, 2003, and in the IEEE 2003 International Symposium on Information Theory, in Yokohama, Jun 29-July 4, 2003, respectively. In the beginning of this research we undertook to solve the problem from a standpoint of system theory so that we have succeeded to show that our method can be applied to fast list decoding of RS codes and AG codes, which was one of our aims for more efficient decoding method. Related to the research, we published papers on parallel decoding of AG codes and compound-error-correcting codes in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J85-A, 4, 460-470, 2002 (in Japanese), and E86-A, 7, 1813-1819, 2003 (in English).