基于六阶分圆序列的循环码的构造 A Construction of Cyclic Code from Cyclotomic Sequence of Order Six

doi:10.12677/CSA.2014.41003

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Computer Science and Application 计算机科学与应用, 2014, 4, 12-18

http://dx.doi.org/10.12677/csa.2014.41003 Published Online January 2014 (http://www.hanspub.org/journal/csa.html)

A Construction of Cyclic Code from Cyclotomic Sequence of

Order Six

Sihao Niu1*, Guangkui Xu1,2, Xiwang Cao1

1Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing

2Department of Mathematics and Computational Science, Huainan Normal University, Huainan

Email: *niusihao@126.com, xuguangkuiy@163.com, xwcao@nuaa.edu.cn

Received: Dec. 3rd, 2013; revised: Dec. 28th, 2013; accepted: Jan. 7th, 2014

stricted use, distribution, and reproduction in any medium, provided the origin al work is properly cited. In accordance of th e Creative Commons At-

guarded by law and by Hans as a guardian.

Abstract: Cyclic code is a subclass of linear codes and has a lot o f applications in consumer electr onics, data transmis-

sion technologies, broadcast systems, and computer applications as it has efficient encoding and decoding algorithms. In

this paper, the cyclotomic sequence of order six is employed to construct a class of cyclic codes over

( )

GF q

with

prime length, and in add ition its linear complexity an d minima polynomial are determined. The minimal po lynomial is

served as the generator polynomial of cyclic code and constructs the cyclic codes over

( )

GF q

with the length of n.

Keywords: Cyclic Codes; Cyclotomic Sequences ; Min imal Polynomial; Generator Polynomial

基于六阶分圆序列的循环码的构造

牛思皓 1*，许广魁 1,2，曹喜望 1

1南京航空航天大学，理学院数学系，南京

2淮南师范学院，数学与计算科学系，淮南

Email: *niusihao@126.com, xuguangkuiy@163.com, xwcao@nuaa.edu.cn

收稿日期：2013 年12 月3日；修回日期：2013 年12 月28 日；录用日期：2014 年1月7日

摘要：循环码是线性码中的一类，在电子产品、数据传输技术、广播系统有着广泛的应用。由于他们有着高

效的编码和解码算法，在计算机中也有着广泛的应用。本文中，首先构造了在

( )

GF q

上周期为素数 n的六阶分

圆序列，并且给出了序列的线性复杂度和极小多项式。利用此序列的极小多项式作为循环码的生成多项式，构

造了

( )

GF q

上长度为 n的循环码。

关键词：循环码；分圆序列；极小多项式；生成多项式

1. 引言

循环码是线性分组码的一个重要子集，是目前研

究的比较成熟的一类线性码。它有许多特殊的代数性

质，这些性质有助于按所要求的纠错能力系统的构造

这类码。在相同长度和维数下，循环码的汉明重量比

其他线性码有更小的下界，具有较强的检错和纠错能

通讯作者。

OPEN ACCESS

基于六阶分圆序列的循环码的构造

力。

循环码也有着良好的编码和解码算法，因此，循

环码在有线通讯中有着重要的应用。例如，RS 码广

泛应用与数据通信和数据存储系统的差错控制中。RS

码在数字存储设备、数字电视、卫星通信等发挥着重

要的作用。文献[1-5]给出了循环码的高效的编码和解

码算法。

文献[6-9]给出了循环码的一些构造方法和重要

性质。丁存生在文献[6]中用两个素数的 Whiteman 广

义分圆序列构造了几类具有良好参数的循环码，并且

给出了这些循环码的极小重量的下界。闫统江在文献

[7]中利用四阶 Whiteman 广义分圆序列构造了另外几

类循环码。在文献[9]中，丁存生利用四阶分圆序列构

造了

( )

GF q

上长度为奇素数的几类最优的循环码。本

文中给出了基于六阶分圆序列的循环码的构造方法。

2. 预备知识

2.1. 周期序列的线性复杂度和极小多项式

设

()

λλ

∞

为定义在有限域

( )

GF q

上周期为

的序列。它的线性复杂度定义为该序列的线性移位

寄存器的最短长度，即最小正整数

满足

0112 2

iiil il

cc cc

λλ λλ

−− −

− =+++

( )

0, ,,

cccGF q≠∈

对所有的

il≥

都成立。

多项式

()

01 l

c xccxcx=+ ++

称为序列

∞

的特

征多项式。因为序列

∞

的周期为

，不妨设

{}

01 1

,,,

λλ λ

−



是序列

∞

的第一个周期，则其生成多

项式定义为

()

01 1

xxx

λλ λ

−

Λ= +++

。因此该序

列的极小多项式定义为

( )( )

( )

gcd 1,

mx xx

−

=−Λ

(1)

序列

∞

的线性复杂度定义为

( )

deg gcd1,.

Lnx x=− −Λ

(2)

2.2. q元循环码定义及其构造方法

设

是一个素数的方幂。若

( )

GF q

为

( )

GF q

上

的

维线性空间，则称

( )

GF q

上的参数为

[ ]

,,nkd

的

线性码是

( )

GF q

的一个

维子空间。

元线性码

叫做循环码，是指

(

,,cc

)

−

∈

，则循环移位得到

( )

101 2

,,, ,

c cccC

−−

∈

。

对于任意的

( )

011

,, ,

cccGF q

−

∈

满足

( )

[ ]

( )

01 21

ccxcxcxGFqxx

−

+ +++∈−

这时

( )

GF q

上长度为

的线性码对应于

()

[]

( )

GF qxx−

的一个子集。

()

[]

()

GF qxx−

是

主理想环当且仅当环

( )

[ ]

( )

GF qxx−

的理想都是

主理想。

设

()

C gx

是循环码且

( )

hx xgx= −

，

则称

( )

是循环码的生成多项式，

( )

是循环码的

校验多项式。文献[9]给出了几类基于四阶分圆序列的

循环码的构造方法，本文中将利用多项式(1)作为循环

码的生成多项式给出一类基于六阶分圆序列的循环

码的构造方法。由多项式(1)作为生成多项式的循环码

，称为是由序列

∞

定义的参数为

( )

,nk

的循环码。

2.3. 分圆理论

设

是奇素数，则

( )

GF r

∗

是循环群，令其生成元

为

且

( )

d ord

表示

模

的阶。则

( )

d ord

= =

1r−

。对于正整数

1, 1

，令其满足

1r ef−=

。

阶分圆类有如下定义：

( )

,0,1, ,1

er ie

C ie

αα

== −

则

( )

() ()()

,, ,

01 1

er erer

GF rCCC

∗

−

= 

( )(){}

0GF rGF r

∗

=

阶分圆数定义为

( )

(

)

er er

ij CC

=+ 

，对所有

的

01, 01ie je≤≤− ≤≤−

。根据

( )

的定义，由文献

[7]可得到下面的结论。

引理 2.1.

1) 对每个

( )

,er

aC∈

，则有

( )()

( )

mod

jij e

aCC +

；

2) 若

为偶数，则

()

C−∈

。

2.4. 高斯周期

高斯周期定义为

( )

,0,1, ,1

xi e

ηχ

∈

== −

∑



其中

称为有限域

( )

GF r

上的典范加法特征。

根据引理 2.1，可以给出高斯周期的一些性质。

OPEN ACCESS 13

基于六阶分圆序列的循环码的构造

引理 2.2.[10] 设

是奇素数，则

()

GFr∗

是循环群，

( )

,er

是同上所定义的

()

GF r

∗

上的

阶分圆类，则高

斯周期有以下性质：

( )

eer

−

= −

∑

；

( )()

1,,

eer er

i ikk

ηη θ

−

= −

∑

{ }

0,1, ,1ke∈−

，其中，





= =







，当是偶数，时

，当是奇数，时

，其它

即

当且仅当

( )

C−∈

。

2.5. 循环码的极小距离

高斯周期与高斯和有着紧密的联系。通过离散傅

立叶变换，可以得到

( )

( )( )

Nr ij jij j

iN N

η ζψζψ

−−

= =



== −+





∑∑

(3)

其中

2π1

−

，

是

( )

GF r

∗

上阶数为

的乘法特

征。一般情况下，高斯周期的值很难通过计算得到。

为了计算循环码的汉明重量的下界，首先给出下面的

引理。

引理 2.3. 对于任意的整数

，满足

iN≤≤ −

，

可以得到

( )

()



−

+≤





(4)

证明：当

0j=

时，

( )

ψχ

∈

== −

∑

。

所以，

( )

11 1

Nr ij j

Nij j

NN N

η ζψ

ψ ζψ

ζψ

−−

−

+= +

=++



−

≤≤





∑

。

令

( )

gcd ,1

nq =

，且

( )

kord q=

是

模

的阶数。

设

rq=

，

是整除

1r−

的正整数，

是满足

( )

1nr N= −

的正整数。设

是

( )

GFr∗

上的本原元，

θα

。则集合

( )()()

(

{

( )

)

( )

}

,Tr,Tr, ,

Tr ,

rq rq

CrNabab

aba bGFr

−

=++

+∈



(5)

是

( )

GF q

上参数为

[ ]

,1nk+

的循环码，

是

( )

GF r

到

( )

GF q

上的迹函数。

由文献[11]的定理可以得到，

( )

CrN

是

( )

GF q

上以

()( )

1xmx

−

为校验多项式的循环码，其中

( )

−

是

( )

GF q

上以

−

为极小多项式的不可约多

项式。

引理 2.4.[9]

是整除

1r−

的正整数，

()

kord q

是

模

的阶数。设

() ()

( )

gcd11 ,NrqN= −−

，则(3)

中

( )

,CrN

是

( )

GF q

上参数为

[]

, 1,

nk d+

的循环码，

循环码的极小距离

满足

( )( )

()( )()

min 1,

1 111

rr r

dq qN

qrN r

qNq N





−−





≥−









− −−−

−

−









定理 2.5. 令

k−

且

qn−<

，

( )

qC∈

，则

( )

GF q

上以

( )()

1xmx

−

为校验多项式的循环码的

参数为

( )

,2 3,nn d+





，

()( )( )

1 111

qrN r

dqNq N



− −−−

−

≥−





其中

( )

−

= −

。

证明：因为

( )()

kord qn== −

且

1qn−<

，

所以多项式

()

( )

6,n

Ω

是

( )

GF q

上的不可约多项式。因

为(3)中循环码的校验多项式为

()( )

1xmx

−

，所以循

环码的维数等于

( )

23n+

。

由

1qn−<

，

是素数可以得到

( )

gcd ,1

NN Nq

−



−

== −



−



则极小距离

由引理 2.4 可以得到。

3. 基于六阶分圆序列的循环码的构造

设

是一个素数，

()

1 mod3n≡

，则

可以表示成

3nu v

= +

，

( )

1 mod3u≡

，

的符号是不确定的。对

OPEN ACCESS

基于六阶分圆序列的循环码的构造

于素数

，令

3q=

，且

( )

gcd ,31n=

。设

是

( )

3GF

扩

域上的

阶本原单位根，

( )

ord q

是

模

的乘法阶。

定义

( )

∈

Ω= −

∏

，

( )

6,n

称为

( )

GF n

上的 6阶分圆类，则

( )

56,

xx x

−= −Ω

∏

，显然

( )

()()

[ ]

x GFxΩ∈

。

下面我们将给出基于六阶分圆序列的循环码的

构造，为此先给出

( )

3GF

上的序列

∞

。定义

( )()

6, 6,

mod

1 mod

i nCC

∈





=−∈









，

，其它

0i≥

此序列即是

( )

3GF

上的序列。

为了计算序列的极小多项式和线性复杂度，我们需

要计算

( )

gcd 1,

xx−Λ

，并且需要给出下面的多项式

( )

( )() ()( )

6, 6,6,6,

03 14

nn nn

iC CiC C

x xx

∈∈

Λ= −

∑∑



(5)

( )

( )()( )()

6, 6,6, 6,

14 2

nn nn

iC CiC C

x xx

∈∈

Γ= −

∑∑



(6)

由引理 2.2 可得到

()()( )( )

( )()

6, 6, 6,6,

01 23

6, 6,

nnnn

iiii

iC iC iC iC

iC iC

ηηηη

ηη

∈∈∈∈

∈∈

+++

++ =−

∑∑∑∑

∑∑

由(5)式和(6)式，以及引理2.1 可得到下面的引理。

引理 3.1

( )

( )( )

( )

( )( )

( )

ηη

Λ∈



Γ∈

− Λ+Γ∈



Λ=

Λ∈



Γ∈



− Λ+Γ∈



，

并且

( )

()

Λ =Λ=

。

证明：由引理 2.1知，如果

( )

6,n

aC∈

，则有

( )()

()

mod6

jij

aCC +

。

当

( )

∈

时，则

( )()

6, 6,nn

aC C=

，所以

( )

( )()()()

( )()( )()

( )

6, 6,6, 6,

03 14

6, 6,6, 6,

03 14

nn nn

aai ai

iC CiCC

iC CiC C

η ηη

∈∈

Λ= −

=−=Λ

∑∑



当

( )

aC∈

时，则

( )()

( )

1 mod6

aC C

，所以

()

()()()()

( )()()()

( )

6, 6,6, 6,

03 14

6, 6,6, 6,

14 2

nn nn

aai ai

iC CiCC

iC CiC C

x xx

η ηη

∈∈

Λ= −

=−=Γ

∑∑



当

()

∈

时，则

()()

()

2 mod6

aC C

，所以

()

( )( )()()

( )()

( )

6, 6,6, 6,

03 14

nn nn

aaiai

iC CiCC

η ηη

ηη

∈∈

Λ= −

=− Λ+Γ

∑∑



同理，当

()

∈

时，

( )

3 mod6

∈

，所以

( )

( )( )( )( )

( )( )()( )

( )

6, 6,6, 6,

03 14

6, 6,6, 6,

03 14

nn nn

aai ai

iC CiCC

iC CiC C

η ηη

∈∈

Λ= −

=−=Λ

∑∑



当

( )

aC∈

时，则

()( )

()

4 mod6

aC C

，所以

( )

()( )( )()

()( )()( )

( )

6, 6,6, 6,

03 14

6, 6,6, 6,

14 2

nn nn

aai ai

iC CiCC

iC CiC C

x xx

η ηη

∈∈

Λ= −

=−=Γ

∑∑



当

( )

aC∈

时，则

( )

5 mod6

∈

，所以

()

()()()( )

() ()

( )

6, 6,6, 6,

03 14

nn nn

aaiai

iC CiCC

η ηη

ηη

∈∈

Λ= −

=− Λ+Γ

∑∑



引理 3.2.[10] 如果

( )

−∈

，

( )

C∈

，则

( )

( )()()()

() ()

012 3

,1, 12,23,3

4,45, 56

llllllll

ll ll

ηη

ηη η η

ηη

∈





=



=+− −+−−+−−

−

+−−+− −+

∑

( )( )

()()( )

() ()()

6, 6,

012

34 5

3,2, 11,2

,3 1,42,5

iC jC

lll lll

ηη η

ηηη

ηη η

−

∈∈

=+++−++ −

+−+− −+−−

∑∑

引理 3.3.[12] 假设

61nf= +

为奇素数，并且

4 27nL M= +

，其中

( )

1 mod3L≡

，

为偶数

OPEN ACCESS 15

基于六阶分圆序列的循环码的构造

时，则

1 ,3CC−∈ ∈

，

( )

0,1,2,3,4,5

的值在[12]

的表 3中已给出。如下：

1) 当

( )

20mod3

ind

≡

时，

当

( )

1 mod36n≡

时，

01234 5

0, 1

ηηηηη η

== ====−

;

当

( )

13 mod36n≡

时，

12345 0

1, 0

ηηηηηη

= =====

;

当

( )

25 mod36n≡

时，

12345 0

1, 1

ηηηηηη

=====−=

2) 当

( )

21 mod3ind

≡

时

当

( )

1 mod36n≡

时，

14025 3

0,1, 1

ηηηηη η

= == ===−

;

当

( )

13 mod36n≡

时，

03425 1

1,1,0

ηηηηη η

===−===

;

当

( )

25 mod36n≡

时，

013 254

0,1, 1

ηηηηηη

=== ==−=

;

3) 当

( )

22mod3ind

≡

时

当

( )

1 mod36n≡

时，

03125 4

0,1, 1

ηηηηη η

====== −

;

当

( )

13 mod36n≡

时，

03514 2

1,1, 0

ηηηηη η

===−== =

;

当

( )

25 mod36n≡

时，

023 145

0,1, 1

ηηη ηηη

=== ==−=

下面我们将给出序列

∞

的极小多项式和线性复

杂度，即给出循环码的生成多项式结果如下面的定理

所示：

定理 3.4. 设

是一个素数，且

( )

1 mod3n≡

，

3nuv= +

，

( )

1 mod3u≡

，

的符号是不确定的。

∞

是定义在

( )

GF q

上的序列。由序列

∞

定义的

( )

GF q

上的循环码

的参数为

[ ]

,,nkd

，并且循环码

的生

成多项式即为序列

∞

的极小多项式，维数

( )

degn mx

−

，则循环码

的生成多项式为：

1) 当

( )

20mod3ind

≡

时，极小多项式，即循环

码

生成多项式为

( )()

( )

( )()

( )

()

( )( )

()

( )

()

( )()

6, 6,

1,1 mod36

1,13 mod36

1,25mod36 .

gxm x

x xx

−≡

−Ω Ω



−



= ≡

−Ω Ω



−

≡

−Ω Ω



线性复杂度为

( )

()

22 2

deg gcd1,33

Lnxxn +−

=−−Λ=− =

。

即由序列

∞

定义循环码

的生成多项式为

( )

，

它的参数为

()

,2 3,

nn d+





。循环码的极小距离

满

足定理 2.5 所给定的下界。

2) 当

( )

21 mod3ind

≡

时，极小多项式，即循环

码

生成多项式为

()( )

( )

()

( )

( )()

( )

()

( )

()( )

()

( )

()( )

6, 6,

1,1mod36

1,13mod36

1,25 mod36

gxm x

x xx

−≡

−Ω Ω



−



= ≡

−Ω Ω



−

≡

−Ω Ω



线性复杂度为

( )

22 2

deg gcd1,33

Lnxxn +−

=−−Λ=− =

。

即由序列

∞

定义循环码

的生成多项式为

( )

，它的参数为

( )

,2 3,nn d+





。循环码的极小

距离

满足定理 2.5 所给定的下界。

3) 当

( )

22mod3ind

≡

时，极小多项式，即循环

码

生成多项式为

() ()

( )

()( )

( )

( )()

( )

()( )

6, 6,

1,1mod36

1,13mod36

1,25 mod36

gxm x

x xx

−≡

−Ω Ω



−



= ≡

−Ω Ω



−

≡

−Ω Ω



线性复杂度为

OPEN ACCESS

基于六阶分圆序列的循环码的构造

( )

22 2

deg gcd1,33

Lnxxn +−

=−−Λ=− =

即由序列

∞

定义循环码

的生成多项式为

( )

，它的参数为

( )

,2 3,

nn d+





。循环码的极小

距离

满足定理 2.5 所给定的下界。

证明：1. 1) 当

()

1 mod36n≡

时，

01234 5

0, 1

ηηηηη η

== ====−

当

( )

∈

时，

()

ηη

Λ =Λ=

；

当

()

∈

时，

( )

()

ηη

Λ =Γ=≠

；

当

( )

aC∈

时，

( )

( )( )

( )

η ηη

Λ=− Λ+Γ=−≠

；

当

( )

aC∈

时，

( )

ηη

Λ =Λ=

；

当

( )

aC∈

时，

( )

ηη

Λ =Γ=≠

；

当

( )

aC∈

时，

( )

( )( )

( )

η ηη

Λ=− Λ+Γ=−≠

；

所以，它的极小多项式，即生成多项式为

()( )( )

()

( )

6, 6,

gcd 1,

gxm xxx

x xx

−

= =−Λ

−

=−ΩΩ

线性复杂度

( )

12 1

deg gcd1,33

Lnxxn −+

=−−Λ=− =

2) 当

( )

13 mod36n≡

时，

12345 0

1, 0

ηηηηηη

= =====

当

( )

aC∈

时，

( )

ηη

Λ=Λ=−≠

；

当

( )

∈

时，

( )

ηη

Λ =Γ=

；

当

( )

aC∈

时，

( )

( )( )

()

η ηη

Λ=− Λ+Γ=≠

；

当

( )

aC∈

时，

( )

ηη

Λ=Λ=−≠

；

当

( )

aC∈

时，

( )

ηη

Λ =Γ=

；

当

( )

aC∈

时，

( )

( )( )

( )

η ηη

Λ=− Λ+Γ=≠

；

所以，它的极小多项式，即生成多项式为

( )( )()

( )

6, 6,

gxm xxxx

−

==−Ω Ω

线性复杂度

( )

12 1

deg gcd1,33

nn nn

Lnxxn −+

=−−Λ=− =

3) 当

( )

25 mod36n≡

时，

12345 0

1, 1

ηηηηηη

=====−=

。

当

()

aC∈

时，

( )

ηη

Λ =Λ=≠

；

当

( )

∈

时，

()

ηη

Λ =Γ=

；

当

( )

aC∈

时，

( )

( )( )

( )

η ηη

Λ=− Λ+Γ=≠

；

当

( )

aC∈

时，

( )

ηη

Λ =Λ=≠

；

当

( )

aC∈

时，

( )

ηη

Λ =Γ=

；

当

( )

aC∈

时，

( )

( )( )

( )

η ηη

Λ=− Λ+Γ=≠

；

所以，它的极小多项式，即生成多项式为

( )( )( )

( )

6, 6,

gxm xx xx

−

== −Ω Ω

线性复杂度

( )

22 2

deg gcd1,33

Lnxxn +−

=−−Λ=− =

同理，当

( )

21 mod3ind

≡

和

( )

22mod3ind

≡

时，

序列

∞

的极小多项式

( )

，即循环码的生成多项

式和维数可由引理 3得到。

例取

3q=

，

61n=

，则

是

( )

3GF

上参数为

[ ]

61,21,41

的循环码。

取

3q=

，

127n=

，则

是

( )

3GF

上参数为

[]

127,43,85

的循环码。

4. 结论

本篇文章，我们给出了基于六阶分圆序列构造了

循环码的构造方法。计算了在

( )

GF q

上周期为素数

的序列的极小多项式和线性复杂度。利用极小多项式

( )

作为循环码

的生成多项式

( )

，构造并计

算了在

( )

GF q

上参数为

[ ]

,,nkd

的循环码

。

基金项目

安徽省淮南师范学院自然科学研究项目(No.

2013XJ67)。

参考文献 (References)

[1] Cheng, Q. and Wan, D. (2007) On the list an d bounded distance

decodability of Reed-Solomon codes. SIAM Journal on Compu-

ting, 37, 195-209.

[2] Cheng, Q. and Wan, D . (2010) Complexity of decoding positive

rate Reed-Solomon codes. IEEE Transactions on Information

OPEN ACCESS 17

基于六阶分圆序列的循环码的构造

Theory, 56, 5217-5222.

[3] Chien, R.T. (1964) Cyclic decoding procedure for the Bose-

Chaudhuri-Hocquenghem codes. IEEE Transactions on Infor-

mation Theory, 10, 357-363.

[4] Forney, G.D. (1965) On decoding BCH codes. IEEE Transac-

tions on Information Theory, 11, 549-557.

[5] Prange, E. (1958) Some cyclic error-correcting codes with sim-

ple decoding algorithms. Air Force Cambridge Research Cen-

ter-TN-58-156, Cambridge.

[6] Ding, C. (2012) C yclic codes from the two-prime sequences. IEEE

Transactions on Information Theor y, 58, 3881-3891.

[7] Sun, Y., Yan, T. and Li, H. (2013) Cyclic codes from the two-

prime Whiteman’s generalized cyclotomic sequences w ith order

4. http://arxiv.org/abs/1303.6378

[8] Ding, C. (2013) A q-polynomial approach to cyclic co des . Finite

Fields and Their Applications, 20, 1-14.

[9] Ding, C. (2013) Cyclic codes from cyclotomic sequences of

order four. Finite Fields and Their Applications, 23, 8-34.

[10] Storer, T. (1967) Cyclotomy and difference sets. Markham, Chi-

cago.

[11] Delsarte, P. (1975) On subfield subcodes of modified Reed-

SoloMon codes. IEEE Transactions on Information Theory, 21,

575-576.

[12] Yin, Y. and Cao, X. (2012) The autorrelation values and linear

complexity of a class of g eneralized ternary sequ ence. Computer

Science and Application, 2, 165-171.

OPEN ACCESS