有限环、群环上的编码和相关算法研究

有限环、群环上的编码及相关算法近二十年来一直是研究热点；有限环上的线性系统相应于有限环上的一类约束满足问题（简称CSP）；CSP的相变理论为算法提供分析测试平台。本项目利用有限环、有限群的表示理论思想技术及算法渐进分析研究有限环、群环上的编码、算法的几个问题。一是有限环、群环上线性码的检验元问题及其编码译码算法，以及相关的生成矩阵、检验矩阵刻画；重点之一是具有一个检验元的码的数学结构、码论性质、编码译码算法。二是有限环上的自对偶码的存在性和构造；特别是有限环上type II的自对偶码的存在条件和构造，群环上的自对偶置换码存在条件和码的结构。三是CSP模型、有限环上线性CSP模型的相变与算法意义；特别是有限环上线性方程组的相变现象及其算法意义、k-CSP模型的推广和变形。上述几个研究问题相互启发、相互联系。

本项目利用有限环、有限群的表示理论思想技术及算法渐近分析研究有限环、有限域、群环上的编码和算法的几个问题。经过四年的研究，我们在相关研究内容上取得了重要进展，完成了项目预期的研究目标。. 一、关于有限环、群环上线性码的检验元问题及其编码译码算法，以及相关的生成矩阵、检验矩阵刻画的研究。. 我们给出了任意群代数上的阿贝尔码(Abelian Codes)及其对偶码代数结构的一般性刻画。我们证明了主理想群代数上任意一个阿贝尔码都有一个生成元和检验元，并给出了这类群环码的对偶码的精确表达形式。我们研究了主理想群代数上的自对偶、自正交的群环码的计数问题，给出了相应的计数公式。我们给出了群环上的自对偶置换码存在性条件和码的结构。. 我们获得了几类循环码的本原幂等元，极小Hamming距离及其重量分布。给出了有限域上常循环码保距同构的充要条件；获得了一批特定长度的自对偶循环码和负循环码的生成多项式及其个数的计数公式。我们刻画了自正交的循环码和负循环码存在性的充要条件；特别地，利用满足特定条件的常循环码构造出一批MDS量子码。. 我们给出了一类MDS Alternant常循环码的修正的Berlekamp-Welch译码算法。. 二、关于有限环上的自对偶码的存在性和构造的研究。. 我们研究了有限域、有限环上的几类自对偶码、循环码和负循环码的代数结构以及码的性能。我们研究了有限交换Frobenius环上的矩阵积码的结构，刻画了矩阵积码是自（正交）对偶码的条件，给出了基于不同度量下的极小距离的下界和上界。我们决定了一类有限交换链环上的常循环码及其对偶码的代数结构，距离结构和码的个数，并决定了这类环上的自对偶码的结构。. 三、关于CSP模型、有限环上线性CSP模型的相变与算法意义的研究。. 我们构造了一个新的约束满足问题模型，d-k-CSP模型，证明了此模型具有精确的可满足相变现象，由此确定了有限域上随机线性方程组的可满足相变点，给出了高斯消去法与相变现象的联系。. 基于项目四年的研究， 项目组成员共发表研究论文35篇，其中SCI论文31篇，EI检索论文2篇。