一种求解线性码最小距离的方法

（天津职业技术师范大学 理学院，天津 300222）

1 引言及预备知识

线性码的最小距离与编码的检错和纠错能力息息相关，最小距离越大，检错和纠错能力越强.线性码的最小距离有多种求法，如利用权重分布多项式、穷举、生成矩阵、校验矩阵相关列、几何学等方法求线性码最小距离[1]237.多项式理论可以用来描述一部分具有良好性质的线性码（如循环码），且也可以通过编码的方式将线性码转化为多项式，即用原数字信息与线性码的生成矩阵做乘法，得到由多项式表示的线性码一般表达式.在此基础上，可以考虑由线性码生成的理想It，其由线性码的一般表达式中t个不同的多项式乘积生成，对于理想It，Gröbner 基理论是用来解决理想生成元的一种手段.近年来，Gröbner基在线性码理论的研究中是一个活跃的研究领域，1992 年，Cooper 在文献[2]中用多项式表示循环码，进而用Gröbner 基理论进行解码，其是首位把Gröbner 基应用到线性码理论中的学者；文献[3-6]应用Gröbner基理论研究了线性码的各种性质；文献[7-9]对Gröbner 基理论的应用做了详细的介绍.

本文由文献[1]中的一种求线性码最小距离的方法展开，该方法主要运用代数方法求由线性码生成的理想It何时有非零解，来确定线性码的最小距离.但该方法的适用范围有限，码字较长时计算过程比较复杂，基于这种情形，提出一种新的方法——利用线性码所生成理想的Gröbner 基确定线性码的最小距离.改进后的方法能够处理原方法不能处理的一些问题，且会给出较好的结果.基于Maple 平台对2种方法进行了对比，证明改进后的方法比原方法速度更快.

线性码的本质是有限域上有限维向量空间的线性子空间，因此可以用线性代数中的一些工具对线性码进行研究.记为有限域Fq上的n维线性空间.

自1965 年Buchberger 提出Gröbner 基方法后，Gröbner 基已经在各个研究领域得到了很好的应用，包括代数方程组的求解、多项式的因子分解、纠错编码中循环码和代数几何码的译码、密码学等研究领域.Gröbner 基与单项式的序关系密切相关，常见的序关系有字典序、分次字典序、分次逆字典序等.

2 基于Gröbner 基的最小距离算法

由命题1 可知，可以通过计算It的零点集来判定码C的最小距离，但是当n和t较大时，利用此方法无法在有限时间内得到结果，实例验证可以说明利用命题1 计算最小距离耗时更长.

直接计算理想It的零点集较为困难，但可以利用理想的Gröbner 基求出其零点集，这是计算理想零点集的一个有效方法.

命题2 是对命题1 的改进，它给出一种求码C最小距离的新方法，即利用多项式理想的Gröbner 基算法求码C的最小距离.

根据命题2 求码C最小距离时的基本思路为：首先确定码C的一般表达式和多项式运算规则，通过一个循环构造理想It，接下来调用Maple 中用于计算Gröbner 基的函数包，计算理想It在字典序下的Gröbner基，输出It的Gröbner 基G，由此可确定所给线性码的最小距离.

求码C最小距离的Maple 程序：

3 实例验证

给出3个实例，用命题2 求解其最小距离，并在每个例题后给出用Gröbner 基算法计算由码C生成的理想所需要的时间.

解由生成矩阵G可以得到码字的一般表达式c=(x1,x2,x3,x1+x2+x3,x1+αx2+α2x3,x1+α2x2+αx3),由α2+α+1=0可知，α3=1，α2=α+1.经过计算可得到I1，I2，I3，I4的Gröbner基分别为

用Gröbner 基算法计算由二元线性码生成的理想I1，I2，I3，I4所需要的时间分别为0.031 200 2，0.093 600 6，0.249 601 6，0.249 601 6，0.109 200 7 s.

例2 设五元线性码C的生成矩阵为，求该线性码的最小距离.

用Gröbner 基算法计算由五元线性码生成的理想I1，I2，I3所需要的时间分别为0.015 600 1，0.046 800 3，0.031 200 2 s.

用Gröbner 基算法计算由码C生成的理想I1，I2，I3，I4，I5，I6所需要的时间分别为0.062 400 4，0.483 603 1，5.990 438 4，42.276 271，137.421 280 9，195.999 656 4 s.

注在例3 中，若用命题1 来求解码字的最小距离，首先要根据定义5 给出It（t=1,2,3,4,5,6），再计算It在F2中何时有非零解，从而得出二元码C的最小距离.利用命题1 计算I1，I2，I3，I4，I5，I6零点集所需要的时间分别为0.24，0.82，9.85，70.42，200.82，285.67 s，所需时间明显多于本文所给方法.因此，当码长较长的情况下，用Gröbner 基算法计算码C的最小距离速度更快.

4 结语

最小距离反映了线性码的检错和纠错能力，因此研究线性码最小距离的求解方法对线性码的测评具有重要意义[11].本文介绍了基本的代数编码知识，利用线性码所生成理想的Gröbner 基对原有线性码最小距离求法进行改进，提出了一种求解线性码最小距离的新方法，并用实例验证在码字较长的情况下，新方法比原有方法的计算速度更快.