Design of BCH-Goppa Decoding Algorithms in Terms of the Tau-functions over Finite Fields

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

In 1997 the following results are given. To decrease the computational complexity of the algorithm based on moment problems introduced by the head of investigator of this project a new decoding algorithm is formulated by using the finite Toda molecule equation over finite fields, namely, the quotient difference algorithm over finite fields It is checked that the algorithm can be successfully applied to various examples including the Goppa code. Secondly, the dynamics of the finite Toda molecule equation over finite fields is considered. There exist conserved quantities and periodic orbits where each period is equal to the order of finite field or its divisor. The periods and the correspondence to the BCH-Goppa decoding are completely classified by the conserved quantities. Moreover, a relationship is discussed between the first component of the eigenvector of the Lax pair of the finite Toda molecule and the value of error appearing the BCH-Goppa code.In 1998, the results obtained in 19 … More 97 are published as a Phys. Lett. A paper entitled "Dynamics of the finite Toda molecule over finite fields and a decoding algorithm". It is shown that the modified KdV (mKdV) equation induces a continued fraction expansion which is different from that given by the Toda molecule. The mKdV equation describes a one-parameter deformation of the orthogonal polynomials named the symmetric Szego polynomials. An integrable discretization of the mKdV equation is found.In 1999, an integrable discretization of the Schur flow is given which is a generalization of the discrete mKdV equation and is corresponding to the general Szego polynomials. Hirota's bilinear form and the tau-function plays the central role. With the help of the discrete Schur flow a new O(N^2) algorithm for computing continued fraction expansions of given Herglotz class functions is designed Moreover, a new algorithm for solving algebraic equations is formulated by the discrete mKdV equation, which will be published in Inverse Problems. Less