基于二次高斯和的增信码重量分布

衡子灵, 陈辅灵, 李德祥, 刘奋进

(长安大学理学院，西安 710064)

0 引言

令q为素数p的方幂，Fqm表示有qm个元素的有限域，α为Fqm的本原元。

0.1 线性码和循环码

对于集合C ⊆Fnq，如果C是Fq上的线性子空间，则称C为q元线性码。这里n称为线性码C的码长，子空间C的维数k称为该码的信息位数，k/n称为该码的传输效率。线性码C的另一个重要参数是最小汉明距离d，它可以用来刻画码的检错和纠错能力。对于线性码来说，最小距离恰好等于其中所有非零码字汉明重量的最小值[1]。定义线性码C的对偶码为

其中〈c⊥,c〉表示这两个向量的内积。如果线性码C的对偶码的最小距离d⊥≥3，则称C为射影码。编码理论中的一个基本数学问题是构作性能良好的线性码，即希望效率k/n大以及最小距离d大，但是n、k、d相互制约，它们之间满足一些界，比如球填充界、Singleton 界、Griesmer 界等[1–2]。如果参数为[n,k,d+1]的线性码不存在，则称参数为[n,k,d]的码为最优码，参数是[n,k,d −1]的码为几乎最优码。令Ai表示[n,k,d]码C中所有重量为i的码字个数，则序列(1,A1,A2,···,An)称为C的重量分布，1+A1z+A2z2+···+Anzn称为C的重量多项式。重量分布是编码理论中的重要研究课题之一，它不仅可以刻画码的检错能力和纠错能力，而且可以计算码检错和纠错的误码率[3]。一般来说，计算码的重量分布是一件困难的事情。近年来，大量文献研究了一些特殊线性码的重量分布[4–14]。

循环码是一类具有高效编码和译码算法的重要线性码，在通信和数据存储系统等领域被广泛应用。若对于任意的码字c = (c0,c1,···,cn−1)∈C，其循环移位总满足(cn−1,c0,···,cn−2)∈C，则称线性码C为循环码。如果把码字c=(c0,c1,···,cn−1)写成多项式

则C为q元循环码当且仅当C为主理想环Fq[x]/〈xn −1〉的一个理想。从而循环码C都可以表示成主理想C=〈g(x)〉，其中g(x)∈Fq[x]为首1 多项式，且g(x)|(xn −1)。多项式g(x)称为循环码C的生成多项式，h(x):=(xn −1)/g(x)称为C的校验多项式。校验多项式的次数等于循环码的维数，借助于代数学知识，大量文献研究了循环码[4–8,11–14]。

0.2 线性码的增信码

令C为Fq上参数是[n,k,d]的线性码且其生成矩阵为G，设长度为n的全1 向量1 =(1,1,···,1)不是C中的码字，定义～C为由矩阵

生成的线性码，线性码～C称为C的增信码[15]。显然增信码～C的参数为[n,k+1]，从而～C的信息位数大于C的信息位数。一般来说，确定增信码～C的最小距离和重量分布是一件困难的事情，这可能需要知道原始码C的完全重量分布信息[15]。当q= 2 时，容易得出～C的最小距离

其中wmax表示C中的最大汉明重量。显然～C和C具有不同的参数和重量分布，从而增信码是构造新码的重要方法之一。最近，文献[16]研究了一类不可约循环码的增信码，这类增信码是具有三个非零重量的射影码；文献[17]研究了一类循环码的增信码，这类增信码关于Griesmer 界最优且其对偶码是几乎MDS 码。

0.3 本文主要工作

令q为奇素数的方幂，令Trqm/q表示从Fqm到Fq的迹函数，其中

定义一类q元可约循环码

根据Delsarte 定理[3]知，这类循环码的校验多项式为mα−1(x)m(−α)−1(x)，其中mα−1(x)、m(−α)−1(x)分别表示α−1和(−α)−1的极小多项式。显然mα−1(x)和m(−α)−1(x)的次数均为m，从而C的参数为[qm −1,2m]。当m为奇数时，文献[13]中定理7 证明了C是一类具有两个非零重量的循环码，且C在q=3 时是射影码。

1) 借助于二次高斯和精确刻画出了增信码～C在偶数m和奇数m两种情形下的重量分布；

2) 证明了～C的对偶码关于球填充界最优或几乎最优，且～C在偶数m和奇数m两种情形下都是射影码；

3) 给出了循环码C的完全重量分布。

1 有限域上特征与特征和

令p为素数，e为正整数且q=pe，令ζp表示本原p次复单位根，定义有限域Fq的加法特征为加法群Fq到复乘法群C∗的同态映射ϕ，即ϕ满足

对任意的a ∈Fq，函数

即为Fq的一个加法特征[1]。此外，集合{ϕa:a ∈Fq}给出了Fq的全部q个不同的加法特征且构成一个群。如果a= 0，则称ϕ0为Fq的平凡加法特征；如果a= 1，则称ϕ1为Fq的典范加法特征。显然ϕa(x)=ϕ1(ax),a ∈Fq。加法特征的正交关系如下[18]

令F∗q= Fq{0}且β为Fq的本原元，有限域Fq的乘法特征为乘法群F∗q到复乘法群C∗的同态映射

Fq的所有乘法特征可如下给出

其中0≤j ≤q −2。特别地，ψ0称为平凡乘法特征，η:=ψ(q−1)/2称为二次乘法特征。乘法特征的正交关系如下[18]

令ψ为Fq的乘法特征，ϕ为Fq的加法特征。定义有限域Fq上的高斯和如下

对于非平凡特征ϕ，称G(η,ϕ)为Fq上的二次高斯和。高斯和G(ψ,ϕ)的精确值仅仅在一些特殊情形下是清楚的，下面给出二次高斯和的精确值。

引理1[18]令q=pe，e为正整数且p为奇素数，令ϕ1为Fq的典范加法特征，那么

引理2[18]令ϕ为Fq的非平凡加法特征，其中q为奇素数的方幂。令f(x) =a2x2+a1x+a0∈Fq[x]且a2/=0，则

2 增信码～C 的参数和重量分布

规定一些符号如下：令χ1、ϕ1分别表示有限域Fqm和Fq的典范加法特征，q=pe，p为奇素数。令η、η′分别表示有限域Fqm和Fq的二次乘法特征。

下面研究式(1)中定义的增信码～C的重量分布。

对任意码字

根据加法特征的正交关系以及迹函数的传递性，可知其汉明重量

定义一类特征和如下

则

其中

从而计算～C的重量分布只需研究特征和S(a,b,c)和S(aα,−bα,c)的分布即可。下面分两种情形进行讨论。

2.1 当m 为偶数时

在本部分中，令m为正偶数。由于q为奇数且m为偶数，故任意的y ∈F∗q都满足η(y)=1。根据引理2，可知

类似可以得到

根据引理1，可知

对于固定的元素c ∈Fq，下面给出S(a,b,c)+S(aα,−bα,c)当(a,b)取遍Fqm×Fqm时值的分布。

下面的引理很容易证明，这里证明略去。

引理3 令q为奇素数p的方幂，则如下的等式成立

根据式(3)、式(4)和引理3 可直接得出下面的结论。

引理4 令c ∈Fq为任意固定元素，m为偶数。如果(a,b)取遍Fqm×Fqm中元素，则S(a,b,c)+S(aα,−bα,c)值的分布见表1，其中

表1 引理4 中S(a,b,c)+S(aα,−bα,c)的值的分布(c ∈Fq 为固定元素)

本部分的主要结论如下。

定理1 令m为偶数且q=pe，其中p为奇素数，则循环码～C是

射影循环码且其重量分布见表2，其中

表2 定理1 中～C 的重量分布

此外，若q ＞3，则～C的对偶码的参数为[qm −1,qm −2m −2,3≤˜d⊥≤4]，且对偶码关于球填充界最优或几乎最优。

证明 根据加法特征的正交关系

根据公式(2)和引理4，即可得到表2 中～C的重量分布。由于

根据表2，可知

从而，容易得出～C的最小距离

现在证明～C是射影码。显然，对偶码～C⊥的最小距离˜d⊥不可能为1。根据对偶码的定义，～C⊥中存在重量为2 的码字，当且仅当存在u1,u2∈F∗q以及两个整数t1和t2(0≤t1＜t2≤qm −2)，使得

根据上述方程组第一个和第三个式子可得出t1=t2，这与t1＜t2矛盾。从而˜d⊥≥3，故～C是射影码。若q ＞3，根据球填充界[1]，可知

容易得出˜d⊥≤4，从而～C⊥的参数为[qm −1,qm −2m −2,3≤d⊥≤4]，且～C⊥关于球填充界最优或几乎最优。

推论1 令m为偶数且q=pe，其中p为奇素数，则C为

循环码且其重量分布见表3，其中

表3 推论1 中C 的重量分布

此外，C⊥为[qm −1,qm −1−2m,2]循环码。

证明 对任意码字

根据公式(2)，可知其汉明重量

显然T(0) =q −1。根据引理4 容易得出S(a,b,0)+S(aα,−bα,0)的值的分布，从而容易得出C的重量分布和最小距离。根据C的重量分布和文献[19]中的Pless Power Moments 可以得出其对偶码的最小距离为2。

下面给出由Magma 生成的一些例子，它们与上述定理的结果一致。

例1 令p= 3,e= 1 且m= 2，则～C为参数是[8,5,2]的三元循环码且其重量多项式为1+8z2+56z4+64z5+80z6+16z7+18z8，其对偶码～C⊥为[8,3,4]三元循环码。根据http://codetables.de/中的Code Tables 可知，～C和～C⊥均为几乎最优码。此外，C为[8,4,2]三元循环码且其重量多项式为1+8z2+24z4+32z6+16z8，其对偶码的参数为[8,4,2]。

例2 令p= 5,e= 1 且m= 2，则～C为参数是[24,5,8]的五元循环码且其重量多项式为

其对偶码的参数为[24,20,2]。

2.2 当m 为奇数时

在本部分中，令m为奇数。由于q为奇数且m为奇数，则任意y ∈F∗q都满足η(y) =η′(y)。根据引理2 以及乘法特征的正交关系

类似可以得到

根据引理1 可知

以及

取任意固定元素c ∈Fq，下面给出S(a,b,c)+S(aα,−bα,c)的值的分布。

引理5 令m为奇数，如果(a,b)取遍Fqm×Fqm中元素，则S(a,b,0)+S(aα,−bα,0)值的分布为

证明 令c=0，则根据公式(5)和公式(6)，可知

则容易得出S(a,b,0)+S(aα,−bα,0)的值的分布。

引理6 令m为奇数，若(a,b,c)取遍Fqm×Fqm×F∗q中元素，则S(a,b,c)+S(aα,−bα,c)值的分布见表4，其中

表4 引理6 中S(a,b,c)+S(aα,−bα,c)值的分布

证明 对任意c ∈F∗q, 根据公式(5)和(6)可得

若(a,b)跑遍Fqm×Fqm且c为固定元素，则S(a,b,c)+S(aα,−bα,c)的值的分布为

其中每一个非零重量的频数可由引理3 得出。注意到如果c是F∗q中的平方元，则η′(c) =1；如果c是F∗q中的非平方元，则η′(c)=−1。从而当(a,b,c)取遍Fqm×Fqm×F∗q中的元素时，S(a,b,c)+S(aα,−bα,c)值的分布即可得出。

定理2 令m ≥3 为奇数且q=pe，其中p为奇素数，则～C为

射影循环码且其重量分布见表5，其中

表5 定理2 中～C 的重量分布

此外，如果q ＞3，则～C的对偶码是[qm −1,qm −2m −2,3≤˜d⊥≤4]循环码且关于球填充界最优或几乎最优。

证明 根据公式(2)和引理5、引理6，可直接得出表5 中～C重量分布。由于m ≥3，则有

根据表5 可知

从而～C的最小距离˜d=(qm−1(q −1))/2。类似于定理1 的证明，容易得出～C为射影码且其对偶码的参数为[qm −1,qm −2m −2,3≤˜d⊥≤4]。根据球填充界可知，对偶码最优或几乎最优。

根据定理2 容易得出下面的推论。

推论2 令m ≥3 为奇数且q=pe，其中p为奇素数，则C为

循环码且其重量分布见表6。如果q=3，其对偶码的参数为[3m −1,3m −2m −1,3]；如果q ＞3，其对偶码的参数为[qm −1,qm −2m −1,2]。

表6 推论2 中C 的重量分布

证明 对任意码字

根据公式(2)可知其汉明重量

显然T(0)=q −1。根据引理5 即可得到S(a,b,0)+S(aα,−bα,0)值的分布，从而容易得出C的重量分布。根据文献[13]即可得到其对偶码的参数。

下面给出由Magma 生成的一些例子，它们与上述定理的结果一致。

例3 令p= 3,e= 1 且m= 3，则～C为参数是[26,7,9]的三元循环码且其重量多项式为

其对偶码～C⊥为[26,19,3]三元循环码。此外，C为[26,6,9]三元循环码且其重量多项式为1+52z9+676z18，其对偶码的参数为[26,20,3]。

例4 令p= 5,e= 1 且m= 3，则～C为参数是[124,7,50]的五元循环码且其重量多项式为

其对偶码～C⊥为[124,117,3]五元循环码。根据http://codetables.de/中的Code Tables 可知，～C⊥为最优码。此外，C为[24,4,8]五元循环码且其重量多项式为1 + 248z50+15 376z100，其对偶码的参数为[124,118,2]。

2.3 循环码C 和～C 的比较

定理1、定理2 和推论1、推论2 分别给出了循环码C和～C在两种情形下的参数和重量分布。容易看出，无论m是奇数还是偶数，循环码C和其增信码～C具有相同的最小汉明距离。现在比较C的码率R和～C的码率～R，显然

从而增信码～C的传输效率优于C。

此外，根据推论1、推论2，只有当q=3 且m为奇数时，C才为射影码，其他情形下都是非射影码。而根据定理1、定理2，增信码～C总是射影码。

综上，本文所研究的增信码在上述两方面优于原码C。

3 C 的完全重量分布

二元码的完全重量分布即为其重量分布，但非二元码的完全重量分布与重量分布不同。完全重量分布是编码理论中的重要研究课题之一，国内外很多文献研究了一些循环码或线性码的完全重量分布[21–24]。

下面给出循环码

的完全重量分布。对任意c ∈Fq，记

类似于公式(2)的推导过程，可得

根据公式(7)和引理4 可直接得出m为偶数时，C的完全重量分布。

定理3 令m为偶数，如果(a,b)取遍Fqm×Fqm中元素，则码C的完全重量分布见表7，其中

表7 定理3 中循环码C 的完全重量分布

令β为Fq的本原元，下面给出m为奇数时，C的完全重量分布。

定理4 令m为奇数，如果(a,b)取遍Fqm×Fqm中元素，则码C的完全重量分布见表8，其中

表8 定理4 中循环码C 的完全重量分布

证明 若(a,b)取遍Fqm×Fqm中元素且c为非零固定元素，则由引理6 的证明过程可得S(a,b,−c)+S(aα,−bα,−c)的值的分布为

从而，根据公式(7)即可得到C的完全重量分布。

4 总结

本文主要利用有限域上特征的性质、二次高斯和等数论工具研究了循环码C的增信码～C，不仅给出了～C的参数和重量分布，而且给出了C的完全重量分布，增信码～C的对偶码关于球填充界最优或几乎最优。特别地，增信码～C和原码C具有相同的最小距离，但～C的传输效率更高。原码C仅仅当q= 3 且m为奇数时为射影码，而增信码～C在所有情形下总是射影码。