利用有限域GF(2m)上的三项式构造二元循环码

张爱仙，冯克勤

（1.西安理工大学数学系，陕西 西安　710048；2.清华大学数学系，北京　100084）

利用有限域GF(2m)上的三项式构造二元循环码

张爱仙1，冯克勤2

（1.西安理工大学数学系，陕西 西安710048；2.清华大学数学系，北京100084）

循环码是一类特殊的线性码，由于循环码快速的编码和译码算法，它被广泛应用于消费电子，数据存储以及通信系统当中.在本文中，利用特征是偶数的有限域上的三项式构造出了两类二元循环码，我们不仅可以确定出这两类循环码最小距离的下界，而且这两类循环码在参数的选取上非常的灵活.关键词：循环码；三项式；序列；有限域

1　引言

设 q是素数 p的幂.向量空间 GF(q)n的一个线性子空间叫作 q元线性码.若此子空间是GF(q)n的k-维子空间且极小汉明重量是d，则称此空间为参数［n，k，d］的q元线性码.码长为 n的 q元线性码 C叫作循环码，是指若 (c0，c1，...，cn-1)∈C，则它的循环移位(cn-1，c0，c1，...，cn-2)∈C.

把向量(c0，c1，...，cn-1)∈GF(q)n等同于多项式

则 GF(q)上码长为 n的循环码 C对应于 GF(q)［x］/(xn-1)中的子集.如果C是循环码当且仅当C在GF(q)［x］/(xn-1)中对应的子集是商环 GF(q)［x］/(xn-1)的一个理想.熟知GF(q)［x］/(xn-1)中每个理想都是主理想.设C=(g(x))，则称g(x)是循环码C的生成多项式，h(x)=(xn-1)/g(x)是循环码C的校验多项式.关于有限域与纠错码的基础知识读者可参见［1-3］.

设s∞=(si)∞i=0是GF(q)上周期为n的序列，

设Cs是以如下多项式

为生成多项式的循环码.

那么一个自然的问题是：用此方法能否构造出性能最优的循环码？事实表明，只要选取合适的序列s∞，用此方法可以构造出最优或几乎最优的循环码，见文献［4-5］.

设m是正整数，n=2m-1，α是GF(2m)∗的生成元.f(x)是GF(2m)上的多项式，定义由f(x)得到的序列s∞，其中

Tr(x)表示由GF(2m)到GF(2)的绝对迹映射.在本文中，通过选取GF(2m)上恰当的三项式f(x)，以(1)式定义的多项式为生成多项式构造出了两类二元循环码，我们不仅可以确定出这两类循环码最小距离的下界，而且这两类循环码在参数的选取上非常的灵活.

2　若干引理

设n=2m-1.包含j模n的2-分圆陪集定义为Cj={j，2j，22j，...，2ℓj-1j}，

其中ℓj是使得等式2ℓjj≡j(mod n)成立的最小正整数.

引理2.1设h是整数，且

则对任意j∈Γ1，

•j是Cj的首元；

•ℓj=m，若m是奇数；ℓ2m/2+1=m/2，若m是偶数.

证明先证明第一个结论.由于陪集首元一定是奇数，对任意j∈Γ1，假设

其中

则Cj中所有的奇数为由于当1≤t≤k-1时，it≤m/2，可知j是Cj的首元.

现在证明第二个结论.当j∈Γ1时，ℓj|m并且j可被(2m-1)/(2ℓj-1)整除.当m是奇数时，如果ℓj＜m，则ℓj≤m/3，从而(2m-1)/(2ℓj-1)＞22m/3，即证明了j＞22m/3.这是不可能的，因为j＜2(m+1)/2.于是证明了，当m是奇数时，ℓj=m.类似地，当m是偶数时，如果ℓj＜m，则ℓj≤m/2，(2m-1)/(2ℓj-1)＞2m-ℓj.很容易可以证明，当j∈Γ1时，j可被(2m-1)/(2ℓj-1)整除当且仅当j=2m/2+1并且ℓj=m/2.

对于周期序列，一般来说很难确定出它的线性复杂度以及极小多项式，下面给出文献［6］中的一个结果.

引理 2.2[6]GF(q)上周期为qn-1的序列s∞可以展开成如下唯一的表达式

其中α是GF(qn)∗的生成元，ci∈GF(qn).设I={i|ci/=0}，则s∞的极小多项式为

s∞的线性复杂度是|I|.

其中

证明对任意奇数j，1≤j≤2h-1.设Bj={1≤i≤2h-1：i∈Cj}.由分圆陪集可知，

并且

从而

其中

又因为对任意i∈B2j+1，Tr(xi)=Tr(x2j+1)可知第二个等式成立.

设LC是序列s∞的线性复杂度，则LC(s∞)=m2h-1+N2(m)，其中

序列s∞的极小多项式为

其中mαj(x)是αj的极小多项式.

证明由f(x)的定义及引理2.3可知，

由(4)可知，当

当

于是，上式中最后一个等式成立.

注意到，对任意t≥0，st=Tr(f(1+αt)).由引理2.1，引理2.2以及公式(6)可知序列s∞的线性复杂度和极小多项式.从而引理得证.

3　循环码的两类构造

本节用引言中介绍的方法给出循环码的两类构造，由定理3.1和3.2可以看出这两类码在参数的选取上非常的灵活，对循环码的编码和译码算法感兴趣的读者可参考文献［7-10］.

3.1第一类构造

是以

为生成多项式的循环码.

定理3.1设Cs是由上述序列s∞定义的循环码，则

(1)Cs的生成多项式为

其中mαj(x)是αj的极小多项式.

(2)Cs是参数为［n，n-m2h-1-N2(m)，d］的循环码，其中，

当m是奇数时，d≥2h+2；当m是偶数时，d≥2h+1.

证明(1)由引理2.4可得到Cs的生成多项式.

(2)由Cs的定义以及引理2.3可知它的维数为n-m2h-1-N2(m).下面证明极小距离d的下界，熟知以Ms(x)为生成多项式生成的循环码与以Ms(x)的互反多项式为生成多项式生成的循环码有相同的重量分布，由引理2.4可知，当j∈{1，...，2h}时，αj是Ms(x)的互反多项式的零点.由BCH码的下界得d≥2h+1.若m是奇数，则Cs是偶重码，从而可知d≥2h+2.

例3.1设(m，h)=(5，3)，α是GF(2m)∗的生成元，α5+α2+1=0.则Cs是以Ms(x)=x21+x20+x19+x18+x17+x16+x15+x13+x12+x10+x8+x7+x4+x2+x+1，为生成多项式，参数为［31，10，12］的最优二元循环码.

例3.2设(m，h)=(7，3)，α是GF(2m)∗的生成元，α7+α+1=0.则Cs是以Ms(x)=x29+x23+x21+x20+x18+x14+x13+x12+x11+x10+x8+x7+x6+x5+x2+1，为生成多项式，参数为［127，98，10］的最优二元循环码.

3.2第二类构造

设m是大于等于5的奇数，

α是GF(2m)∗的生成元，

设

是以

为生成多项式的循环码.

定理3.2设Cs是由上述序列s∞定义的循环码，则

(1)Cs的生成多项式为

其中mαj(x)是αj的极小多项式.

(2)Cs是参数为［n，n-3m-1，d］的循环码，其中

证明(1)由st的定义可知，

又由引理2.1可知，2-分圆陪集C1，C3，C2(m-1)/2+1所含元素个数均为m个，且它们两两不相交.综合引理2.2的结论以及st的表达式可知，s∞的线性复杂度为3m+1，Cs的极小多项式是

(2)下面只需要证明Cs最小距离d的下界.熟知以Ms(x)为生成多项式生成的循环码与以Ms(x)的互反多项式为生成多项式生成的循环码有相同的重量分布.当m=5时，对任意的t，t∈{0，1，2，3，4，5，6}，αt都是Ms(x)的互反多项式的零点，从而由BCH界可知d≥8.当m＞5时，对任意的t，t∈{0，1，2，3，4}，αt都是Ms(x)的互反多项式的零点，由BCH界可知d≥6.定理得证.

例3.3设m=5，α是GF(2m)∗的生成元，α5+α2+1=0.则Cs是以

为生成多项式，参数为［31，15，8］的最优二元循环码.

例3.4设m=7，α是GF(2m)∗的生成元，α7+α+1=0.则Cs是以为生成多项式，参数为［127，105，8］的最优二元循环码.

[1］冯克勤.纠错码的代数理论[M］.北京：清华大学出版社，2005.

[2］Lidl L，Niederreiter H.Finite Fields[M］.Cambridge：Cambridge University Press，1997.

[3］Huffman W.C，Pless V.Fundamentals of Error-Correcting Codes[M］.Cambridge：Cambridge University Press，2003.

[4］Ding C.Cyclic codes from the two-prime sequences[J］.IEEE Trans.Inform.Theory，2012，58（6）：3881-3891.

[5］Ding C.Cyclic codes from APN and planar functions[J］.arXiv：1206.4687，2012.

[6］Antweiler M，Bomer L.Complex sequences over GF（pM）with a two-level autocorrelation function and a large linear span[J］.IEEE Trans.Inform.Theory，1992，38：120-130.

[7］Chien R T.Cyclic decoding procedure for the Bose-Chaudhuri-Hocquenghem codes[J］.IEEE Trans.Inform. Theory，1964，10：357-363.

[8］Dobbertin H.Almost perfect nonlinear power functions on GF（2n）：the Welch case[J］.IEEE Trans.Inform. Theory，1999，45：1271-1275.

[9］Forney G D.On decoding BCH codes[J］.IEEE Trans.Inform.Theory，1995，11（4）：549-557.

[10］Van Lint J H，Wilson R M.On the minimum distance of cyclic codes[J］.IEEE Trans.Inform.Theory，1986，32（1）：23-40.

2010 MSC:94B15

Binary cyclic codes from trinomials over GF(2m)

Zhang Aixian1，Feng Keqin2
（1.Department of Mathematics，Xi′an University of Technology，Xi′an710048，China；2.Department of Mathematics，Tsinghua University，Beijing100084，China）

Cyclic codes are a subclass of linear codes and have wide applications in consumer electronics，data storage systems，and communication systems since they have efficient encoding and decoding algorithms.In this paper，some trinomials over finite fields with even characteristic are employed to construct two classws of binary cyclic codes.Lower bounds on the minimum weight of some cyclic codes are developed.The dimensions of the codes obtained in this paper are flexible.

cyclic codes，trinomial，sequences，finite fields

O236.2

A

1008-5513(2016)04-0380-07

10.3969/j.issn.1008-5513.2016.04.006

2016-07-06.

国家自然科学基金(11401468；11471178).

张爱仙(1984-)，博士，讲师，研究方向：代数数论及其应用.