两类具有两个零点的最优三元循环码-凯发国际一触即发

1. 引言

循环码作为线性码的一个重要子类，主要有两大特点：一是可以用许多优秀的数学工具(如多项式代数、有限域等)进行分析与研究码，这使得循环码在理论上拥有很强的可研究性，能够设计出高效的编码和译码算法；二是循环码的编译码操作能够通过移位寄存器来完成，这种方法在硬件上非常简单有效。因此，循环码在工程中广泛应用，特别是在数据传输和广播系统等对实时性和可靠性要求较高的场合。近些年来，最优循环码的构造是一个热门研究课题，尤其是对由两个或三个零点生成的循环码的最优性的研究。

设f p m 是含有p m 个元素的有限域，其特征为p。f p m * 表示f p m 中的非零元素集合。有限域f p 上参数为[ n,k,d ] 线性码c 是f p n 中的一个k维子空间，其最小汉明距离为d。若对任意码字( c 0 , c 1 ,⋯, c n−1 )∈c 循环移位后，仍有( c n−1 , c 0 ,⋯, c n−2 )∈c ，则称c 是参数为[ n,k,d ] 的循环码。一个参数为[ n,k ] 码的码字( c 0 , c 1 ,⋯, c n−1 ) 可以与一个次数小于n的多项式相对应。因此，长度为n且在有限域f p 上的任何循环码都对应于多项式剩余类环f p [ x ]/ ( x n −1 ) 的一个理想。对于gcd( n,p )=1 ，注意到f p [ x ]/ ( x n −1 ) 中的每个理想都是主理想，码长为n的循环码c 在有限域f p 上可以表示为c=〈 g( x ) 〉 ，其中g( x ) 是首项系数为1且次数最小的多项式，称之为循环码c 的生成多项式，将生成多项式的零点称为循环码的零点。设α 是有限域f p m 中的一个本原元，对于任意的一个整数1≤t≤ p m −1 ，记f p m 上α t 的极小多项式为m α t ( x ) 。记生成多项式为g( x )= m t 1 ( x ) m t 2 ( x )⋯ m t i ( x ) 生成的循环码为c ( t 1 , t 2 ,⋯, t t ) ，其中1≤ t 1 ,⋯, t i ≤ p m −1 。近些年，研究两个或三个零点生成的循环码的最小距离及其对偶码的重量分布是一个热门话题。2005年，carlet、ding和yuan [1]首次得到了参数为[ 3 m −1, 3 m −2m−1,4 ] 循环码c ( 1,e ) ，并达到了sphere-packing界。2013年，ding和helleseth [2]基于有限域f 3 m 上的一些单项式函数构造出了几类三元最优循环码c ( 1,e ) 及其相关刻画，并基于数学软件magma搜索提出了九个公开问题。2014年，n. li与c. li等人[3]利用有限域上低次多项式求根的方法解决了文献[2]中的第一个公开问题。2015年，n. li和z. zhou等人[4]通过解特定的方程解决了文献[2]中第二个公开问题。2019年，han和yan [5]解决了文献[2]中的三个公开问题。基于作者查阅文献，目前为止，就这三个问题完全得到了解决。除此之外，许多学者围绕剩余的6个公开问题进行探究，得到了特定条件下的结果与提出了新的三元最优循环码，具体情况，可以查阅文献[6]-[17]。

本文利用有限域上的多变元法、因式分解与低次不可约多项式的解等数学工具，得到了两类新的三元循环码，其参数为[ 3 m , 3 m −2m−1,4 ] 。我们的结论丰富了文献[7] [8]中三元最优循环码的结论。

2. 基础知识

下面，我们给出需要用到的引理与定理：

引理1 [3]设m是正整数，对于任意正整数e满足1≤e≤ 3 m −2 和gcd( e, 3 m −1 )≤2 。则3-次分圆陪集c e 的大小为| c e |=m 。

引理2 [18]设gcd( n,l )=1 ，则有限域f p ml 上n次多项式g( x ) 不可约的充要条件是f p m 上n次多项式g( x ) 不可约。

定理1 [3]设正整数e ∈ c e 且| c e |=m ，则三元循环码c ( 1,e ) 具有参数[ 3 m −1, 3 m −2m−1,4 ] 当且仅当如下条件成立：

1) 正整数e是偶数；

2) 方程( x 1 ) e − x e −1=0 在有限域f 3 m 中仅有一解x=0 ；

3) 方程( x 1 ) e x e 1=0 在有限域f 3 m 中仅有一解x=1 。

引理3 [19] (sphere-packing界)对于f p 上一个参数为[ n,k,d ] 的线性码，满足下列不等式

∑ i=0 s ( n i ) ( p−1 ) i ≤ p n−k ,

其中s=⌊ d−1 2 ⌋ 。

当p=3 ，码长为n= 3 m −1 ，维数为k= 3 m −1−2m ，其中m>1 。则由上面的不等式，可得

∑ i=0 s ( 3 m −1 i ) 2 i − 3 2m ≤0 ，

若s=1 ，则有∑ i=0 1 ( 3 m −1 i ) 2 i − 3 2m =− 3 2m 2⋅ 3 m −1=− 3 m ⋅( 3 m −2 )−1≤0 。

若s=2 ，则有∑ i=0 2 ( 3 m −1 i ) 2 i − 3 2m = 3 m ⋅( 3 m −4 ) 3>0 。

又当s>2 时，∑ i=0 s ( 3 m −1 i ) 2 i > ∑ i=0 2 ( 3 m −1 i ) 2 i 。

综上分析，当s≤1 时，∑ i=0 s ( 3 m −1 i ) 2 i ≤ 3 2m 才成立，其中s=⌊ d−1 2 ⌋ 。当d≤4 时，才有s≤1 。从而可得，若循环码c ( 1,e ) 的码长为n= 3 m −1 与维数为k= 3 m −1−2m 时，则它的最小距离d≤4 。因此，参数为[ 3 m −1, 3 m −2m−1,4 ] 的循环码c ( 1,e ) 达到了sphere-packing界，则称该三元循环码c ( 1,e ) 是最优的。

3. 两类三元最优循环码

接下来，首先运用有限域上的多变元知识将求解的问题转化为低次多项式解的问题[7] [8]，再利用因式分解与低次不可约多项式的解的结构等方法，我们得到了两类最小距离为4的最优三元循环码。

定理3：设m是奇数，e是正整数且满足11e≡2⋅ 3 h ( mod 3 m −1 ) ，其中0≤h≤m−1 。若有m ≡ 0( mod5 ) 和m ≡ 0( mod9 ) ，则生成多项式为m 1 ( x ) m e ( x ) 的三元循环码c ( 1,e ) 的参数为[ 3 m −1, 3 m −2m−1,4 ] 且是最优的。

证：因gcd( 3 5 −1,11 )=11 ，易得当m ≡ 0( mod5 ) 时，gcd( 3 m −1,11 )=1 。由同余的性质可得，11e≡2⋅ 3 h ( mod 3 m −1 ) 有解e，并且e是偶数，e ∈ c 1 。又因为gcd( 11e, 3 m −1 )=gcd( 2⋅ 3 h , 3 m −1 )=2 ，所以( e, 3 m −1 )=2 。由引理1，可得| c e |=m 。因此，三元循环码c ( 1,e ) 的维数为3 m −2m−1 。

因m ≡ 0( mod5 ) ，可得gcd( 11, 3 m −1 )=1 。因此，对∀x∈ f 3 m ，存在θ,β∈ f 3 m 使x 1= λ 11 和x= β 11 ，则有

θ 11 − β 11 =1. (10)

下面讨论定理1中条件2)与条件3)：

由方程( x 1 ) e − x e −1=0 ，可得θ 11e − β 11e =1 。由11e≡2⋅ 3 h ( mod 3 m −1 ) ，则有θ 2⋅ 3 h − β 2⋅ 3 h =1 ，从而θ 2 − β 2 =1 。设y=θ β ，则由1=( θ β )( θ−β ) 可得y∈ f 3 m * 和θ−β= 1 y 。从而，可得θ=−y− 1 y 和β=−y 1 y ，并代入方程(10)，则有

( −y− 1 y ) 11 − ( −y 1 y ) 11 =1. (11)

展开整理可得y 20 y 11 − y 4 −1=0 。再因式分解：

( y−1 ) 2 ( y 9 y 8 y 7 y 6 y 5 y 4 y 3 y 2 −1 )( y 9 y 8 y 7 y 6 y 5 y 4 y 3 y 2 −y 1 )=0

其中y 9 y 8 y 7 y 6 y 5 y 4 y 3 y 2 −1 与y 9 y 8 y 7 y 6 y 5 y 4 y 3 y 2 −x 1 是f 3 上的不可约多项式。

由引理2可得，当m ≡ 0( mod9 ) 时，方程(11)只有解y=1 。从而，可得有唯一解x=0 。定理1中条件2)满足。

下面讨论方程( x 1 ) e x e 1=0 的解。

同理，方程( x 1 ) e x e 1=0 可变形为θ 2⋅ 3 h β 2⋅ 3 h =−1 ，从而θ 2 β 2 =−1 。设θ−β=u 和θβ=v ，则有

u 2 −v=−1 (12)

注意到，

θ 5 − β 5 =( θ 3 − β 3 )( θ 2 β 2 )− θ 2 β 2 ( θ−β )=− u 3 −u⋅ v 2 ,

θ 7 − β 7 =( θ 5 − β 5 )( θ 2 β 2 )− θ 2 β 2 ( θ 3 − β 3 )= u 3 u v 2 − u 3 v 2 ,

θ 9 − β 9 =( θ 7 − β 7 )( θ 2 β 2 )− θ 2 β 2 ( θ 5 − β 5 )=− u 3 −u v 2 − u 3 v 2 u v 4 ,

θ 11 − β 11 =( θ 9 − β 9 )( θ 2 β 2 )− θ 2 β 2 ( θ 7 − β 7 )= u 3 u v 2 u v 4 u 3 v 4 .

从而，可得u 3 u v 2 u v 4 u 3 v 4 =1 。联立方程(12)，则有

u 11 − u 9 u 7 − u 5 − u 3 −u 1=0 (13)

在f 3 上因式分解可得，

( u−1 ) 5 ( u 2 u−1 )( u 4 u 3 − u 2 −u−1 )=0,

其中u 2 −u−1 与u 4 − u 3 − u 2 u−1 是f 3 上的不可约多项式。

由引理2可得，当m是奇数时，方程(13)只有解u=1 ，并代入方程(12)有v=−1 。因此，θ−β=1 ，θβ=−1 ，则有( β 1 )β=−1 。从而，β=1 ，可得x=1 。因此，定理1中的条件3)满足。

综上可得，三元循环码c ( 1,e ) 的参数为[ 3 m −1, 3 m −2m−1,4 ] 且是最优的。

例1 设m=3,h=0 ，α 是f 3 m * 上的生成元，且满足条件α 3 2α 1=0 。则由11e≡2⋅ 3 h ( mod 3 m −1 ) 可得e=12 。利用magma可得，c ( 1,e ) 是参数为[ 26,20,4 ] 的三元循环码，其生成多项式为x 6 x 5 2 x 4 2 x 3 x 2 x 2.

例2 设m=7,h=0 ，α 是f 3 m * 上的生成元，且满足条件α 7 − α 2 1=0 ，则由11e≡2⋅ 3 h ( mod 3 m −1 ) 可得e=1590 。利用magma可得，c ( 1,e ) 是参数为[ 2186,2172,4 ] 的三元循环码，其生成多项式为x 14 2 x 13 x 12 2 x 11 2 x 9 x 8 2 x 7 x 5 2 x 4 x 2 2 。

例3 设m=7,h=1 ，α 是f 3 m * 上的生成元，且满足条件α 7 − α 2 1=0 ，则由11e≡2⋅ 3 h ( mod 3 m −1 ) 可得e=1590 。利用magma可得，c ( 1,e ) 是参数为[ 2186,2172,4 ] 的三元循环码，其生成多项式为x 14 2 x 13 x 12 2 x 11 2 x 9 x 8 2 x 7 x 5 2 x 4 x 2 2 。

定理4：设m是奇数，e是正整数且满足13e≡2⋅ 3 h ( mod 3 m −1 ) ，其中0≤h≤m−1 。若有m ≡ 0( mod3 ) ，则则生成多项式为m 1 ( x ) m e ( x ) 的三元循环码c ( 1,e ) 的参数为[ 3 m −1, 3 m −2m−1,4 ] 且是最优的。

证：因gcd( 3 3 −1,13 )=13 ，易得当m ≡ 0( mod3 ) 时，gcd( 3 m −1,13 )=1 。由同余的性质可得，13e≡2⋅ 3 h ( mod 3 m −1 ) 有解e，并且e是偶数，e ∈ c 1 。因为gcd( 13e, 3 m −1 )=gcd( 2⋅ 3 h , 3 m −1 )=2 ，所以( e, 3 m −1 )=2 。由引理1，可得| c e |=m 。因此，三元循环码c ( 1,e ) 的维数为3 m −2m−1 。

因m ≡ 0( mod3 ) ，可得gcd( 13, 3 m −1 )=1 。因此，对∀x∈ f 3 m ，存在θ,β∈ f 3 m 使x 1= θ 13 和x= β 13 ，则有

θ 13 − β 13 =1. (14)

下面讨论定理1中条件2)与条件3)：

由方程( x 1 ) e − x e −1=0 ，可得θ 13e − β 13e =1 。由13e≡2( mod 3 m −1 ) ，则有θ 2⋅ 3 h − β 2⋅ 3 h =1 ，从而θ 2 − β 2 =1 。设y=θ β ，则由1=( θ β )( θ−β ) 可得y∈ f 3 m * 和θ−β= 1 y 。从而，可得θ=−y− 1 y 和β=−y 1 y ，并代入方程(14)，则有

( −y− 1 y ) 13 − ( −y 1 y ) 13 =1. (15)

展开整理可得y 24 y 20 − y 13 y 8 1=0 。再因式分解：

( y−1 ) 2 ( y 3 −y 1 )( y 3 y 2 y−1 )( y 4 y 3 −1 )( y 12 − y 10 y 9 y 8 y 6 − y 5 − y 4 − y 3 − y 2 y 1 )=0

其中y 12 − y 10 y 9 y 8 y 6 − y 5 − y 4 − y 3 − y 2 y 1 ，y 3 −y 1 ，y 3 y 2 y−1 ，与y 4 y 3 −1 是f 3 上的不可约多项式。

由引理2可得，当m是奇数与m ≡ 0( mod3 ) 时，方程(15)只有解y=1 。从而，可得有唯一解x=0 。定理1中条件2)满足。

下面讨论方程( x 1 ) e x e 1=0 的解。

同理，方程( x 1 ) e x e 1=0 可变形为α 2 β 2 =−1 。设θ−β=u 和θβ=v ，则有

u 2 −v=−1. (16)

注意到，

θ 5 − β 5 =( θ 3 − β 3 )( θ 2 β 2 )− θ 2 β 2 ( θ−β )=− u 3 −u⋅ v 2 ,

θ 7 − β 7 =( θ 5 − β 5 )( θ 2 β 2 )− θ 2 β 2 ( θ 3 − β 3 )= u 3 u v 2 − u 3 v 2 ,

θ 9 − β 9 =( θ 7 − β 7 )( θ 2 β 2 )− θ 2 β 2 ( θ 5 − β 5 )=− u 3 −u v 2 − u 3 v 2 u v 4 ,

θ 11 − β 11 =( θ 9 − β 9 )( θ 2 β 2 )− θ 2 β 2 ( θ 7 − β 7 )= u 3 u v 2 u v 4 u 3 v 4 .

θ 13 − β 13 =( θ 11 − β 11 )( θ 2 β 2 )− θ 2 β 2 ( θ 9 − β 9 )=− u 3 −u v 2 u 3 v 2 −u v 6 .

从而，可得− u 3 −u v 2 u 3 v 2 −u v 6 =1 。联立方程(16)，则有

u 13 u 7 − u 5 − u 3 −u 1=0 (17)

在f 3 上因式分解可得，

( u−1 )( u 3 − u 2 1 )( u 9 − u 8 − u 5 − u 3 − u 2 −1 )=0,

其中u 3 − u 2 1 与u 9 − u 8 − u 5 − u 3 − u 2 −1 是f 3 上的不可约多项式。

由引理2可得，当m ≡ 0( mod3 ) 时，方程(17)只有解u=1 ，并代入方程(16)有v=−1 。因此，θ−β=1 ，θβ=−1 ，则有( β 1 )β=−1 。从而，β=1 ，可得x=1 。因此，定理1中的条件3)满足。

综上可得，三元循环码c ( 1,e ) 的参数为[ 3 m −1, 3 m −2m−1,4 ] 且是最优的。

例3 设m=5,h=0 ，α 是 f 3 m * 上的生成元，且满足条件α 5 2α 1=0 ，则由13e≡2⋅ 3 h ( mod 3 m −1 ) 可得e=56 。利用magma可得，c ( 1,e ) 是参数为[ 242,232,4 ] 的三元循环码，其生成多项式为x 10 2 x 8 x 7 x 4 x 3 2x 2 。

例4设m=7,h=0 ，α 是 f 3 m * 上的生成元，且满足条件α 7 2 α 2 1=0 ，则由13e≡2⋅ 3 h ( mod 3 m −1 ) 可得e=2018 。利用magma可得，c ( 1,e ) 是参数为[ 2186,2172,4 ] 的三元循环码，其生成多项式为x 14 x 13 2 x 11 x 10 x 9 2 x 6 2 x 5 x 2 。

4. 总结

本文通过对单项式函数构造的三元循环码进行研究，得到了两类参数为[ 3 m −1, 3 m −2m−1,4 ] 的最优的三元循环码c ( 1,e ) 。这些最优的三元循环码丰富了已有最优三元循环码的种类。我们注意到，具有e( 3 h 2 )≡2( mod 3 m −1 ) 或e( 3 h 4 )≡2( mod 3 m −1 ) 等的循环码c ( 1,e ) ，h取较小值时，也可以以类似的方式建立得到三元最优循环码。更一般性的结论，更加复杂，可能需要其他方法。

参考文献