Modern algebraic decoding of error-correcting codes

1. 降低了仿射变码译码中误差估计的计算复杂度。传统的用Berlekamp-Massey-Sakata算法解码仿射变码的误差估计方法采用高斯消去法求解线性方程组。为了降低误差估计的计算复杂度，建立了一个关于证候值和离散傅里叶变换扩展的引理，即主引理，并将其应用于误差估计中。因此，将码长三次幂的计算复杂度降低到码长近二次幂。提出了高性能广义拟循环码的高效搜索算法。此外，作为有理整数环上码的类比，本文还定义了广义整数码，并研究了它们的对偶码、搜索算法和通过Hecke环的枚举方法。

1. The computational complexity of the error-value estimation in the decoding of affine variety codes has been reduced. The conventional method of the error-value estimation in the decoding of affine variety codes by Berlekamp-Massey-Sakata algorithm employs solving systems of linear equations by Gaussian elimination. In order to reduce its computational complexity, a lemma for the extension of syndrome values and discrete Fourier transforms, called Main Lemma, is established and applied to the error-value estimation. Thereby, the computational complexity third power of the code length has been reduced to the nearly second power of the code length.2. Efficient search algorithms of high-performance generalized quasi-cyclic codes are proposed. Moreover, as an analogy of these results to the codes over rational integer rings, generalized integer codes have been newly defined, and their dual codes, search algorithms, and an enumeration method via Hecke rings have been investigated.