设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投搞
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
Computer Science and
Application
计算机科学与应用
, 201
4, 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 N
iu
1*
, Guangkui X
u
1,2
, Xiwang Cao
1
1
Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing
2
Department of Mathematics and Computational Science
,
Huainan Normal University, Huainan
Email:
*
niusihao@126.com,
xuguangkuiy@163.com
,
xwcao@nuaa.edu.cn
Received: Dec. 3
rd
, 2013; revised: Dec. 28
th
, 2013; accepted: Jan. 7
th
, 2014
Copyright © 201
4
Sihao Niu
et al. This is an open access article distribu ted under the Creative Commons Attribution License, which permits unre-
stricted use, distribution, and reproduction in any medium, provided the origin al work is properly cited. In accordance of th e Creative Commons A
t-
tribution License all Cop yrights © 201
4
are reserved for Hans and the o wner of the intellectual property Sih ao Niu
et al. All Copyright © 201
4 are
guarded by law and by Hans as a guardian.
Abstract:
Cyclic code
is
a subclass of linear codes and ha
s
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
.
Key
words:
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
12
基于六阶分圆序列的循环码的构造
力。
循环码也有着良好的编码和解码算法,因此,循
环码在有线通讯中有着重要的应用。例如,
RS
码广
泛应用与数据通信和数据存储系统的差错控制中。
RS
码在数字存储设备、数字电视、卫星通信等发挥着重
要的作用。文献
[1-5]
给出了循环码的高效的编码和解
码算法。
文献
[6-9]
给出了循环码的一些构造方法和重要
性质。丁存生在文献
[6]
中用两个素数的
Whiteman
广
义分圆序列构造了几类具有良好参数的循环码,并且
给出了这些循环码的极小重量的下界。闫统江在文献
[7]
中利用四阶
Whiteman
广义分圆序列构造了另外几
类循环码。在文献
[9]
中,丁存生利用四阶分圆序列构
造了
( )
GF q
上长度为奇素数的几类最优的循环码。本
文中给出了基于六阶分圆序列的循环码的构造方法。
2.
预备知识
2.1.
周期序列的线性复杂度和极小多项式
设
(
)
0
i
i
λλ
∞
∞
=
=
为定义在有限域
( )
GF q
上周期为
n
的序列。它的线性复杂度定义为该序列的线性移位
寄存器的最短长度,即最小正整数
l
满足
0112 2
,
iiil il
cc cc
λλ λλ
−− −
− =+++
( )
01
0, ,,
l
cccGF q
≠∈
,
对所有的
il
≥
都成立。
多项式
(
)
01
l
l
c xccxcx
=+ ++
称为序列
λ
∞
的特
征多项式。因为序列
λ
∞
的周期为
n
,不妨设
{
}
01 1
,,,
n
λλ λ
−
是序列
λ
∞
的第一个周期,则其生成多
项式定义为
(
)
1
01 1
nn
n
xxx
λλ λ
−
−
Λ= +++
。因此该序
列的极小多项式定义为
( )
( )
( )
1
,
gcd 1,
n
nn
x
mx
xx
λ
−
=
−Λ
(1)
序列
λ
∞
的线性复杂度定义为
( )
( )
( )
deg gcd1,.
nn
Lnx x
=− −Λ
(2)
2.2.
q
元循环码定义及其构造方法
设
q
是一个素数的方幂。若
( )
n
GF q
为
( )
GF q
上
的
n
维线性空间,则称
( )
GF q
上的参数为
[ ]
,,
nkd
的
线性码是
( )
n
GF q
的一个
k
维子空间。
q
元线性码
C
叫做循环码,是指
(
01
,,
cc
)
1
,
n
cC
−
∈
,则循环移位得到
( )
101 2
,,, ,
nn
c cccC
−−
∈
。
对于任意的
( )
( )
011
,, ,
n
n
cccGF q
−
∈
满足
( )
[ ]
( )
21
01 21
1
nn
n
ccxcxcxGFqxx
−
−
+ +++∈−
,
这时
( )
GF q
上长度为
n
的线性码对应于
(
)
[
]
( )
1
n
GF qxx
−
的一个子集。
(
)
[
]
(
)
1
n
GF qxx
−
是
主理想环当且仅当环
( )
[ ]
( )
1
n
GF qxx
−
的理想都是
主理想。
设
(
)
C gx
=
是循环码
且
( )
( )
( )
1
n
hx xgx
= −
,
则称
( )
gx
是循环码的生成多项式,
( )
hx
是循环码的
校验多项式。文献
[9]
给出了几类基于四阶分圆序列的
循环码的构造方法,本文中将利用多项式
(1)
作为循环
码的生成多项式给出一类基于六阶分圆序列的循环
码的构造方法。由多项式
(1)
作为生成多项式的循环码
C
λ
,称为是由序列
λ
∞
定义的参数为
( )
,
nk
的循环码。
2.3.
分圆理论
设
r
是奇素数,则
( )
GF r
∗
是循环群,令其生成元
为
α
且
( )
r
d ord
α
=
表示
α
模
r
的阶。则
( )
r
d ord
α
= =
1
r
−
。对于正整数
1, 1
ne
>>
,令其满足
1
r ef
−=
。
e
阶分圆类有如下定义:
( )
,
,0,1, ,1
er
ie
i
C ie
αα
== −
.
则
( )
() ()(
)
,, ,
01 1
er erer
e
GF rCCC
∗
−
=
,
( )(){}
0
GF rGF r
∗
=
.
e
阶分圆数定义为
( )
( )
( )
(
)
,,
,1
er er
ij
e
ij CC
=+
,对所有
的
01, 01
ie je
≤≤− ≤≤−
。根 据
( )
,
er
i
C
的定义,由文献
[7]
可得到下面的结论。
引理
2.1
.
1)
对每个
( )
,
er
i
aC
∈
,则有
( )
()
( )
,
,
mod
er
er
j
ij e
aCC
+
=
;
2)
若
f
为偶数,则
(
)
6,
0
1
r
C
−∈
。
2.4.
高斯周期
高斯周期定义为
( )
( )
( )
,
,
,0,1, ,1
er
i
er
i
C
xi e
χ
ηχ
∈
== −
∑
,
其中
χ
称为有限域
( )
GF r
上的典范加法特征。
根据引理
2.1
,可以给出高斯周期的一些性质。
OPEN ACCESS
13
基于六阶分圆序列的循环码的构造
引理
2.2
.
[10]
设
r
是奇素数,则
(
)
GFr
∗
是循环群,
( )
,
er
i
C
是同上所定义的
(
)
GF r
∗
上的
N
阶分圆类,则高
斯周期有以下性质:
1)
( )
1
,
0
1
e
er
i
i
η
−
=
= −
∑
;
2)
( )()
1
,,
0
e
er er
i ikk
i
rf
ηη θ
−
+
=
= −
∑
,
{ }
0,1, ,1
ke
∈−
,
其中,
10
1
2
0
k
fk
e
fk
θ
=
= =
, 当是偶数,时
, 当是奇数,时
, 其它
即
1
k
θ
=
当且仅当
( )
,
1
er
k
C
−∈
。
2.5.
循环码的极小距离
高斯周期与高斯和有着紧密的联系。通过离散傅
立叶变换,可以得到
( )
( )( )
11
,
00
11
1,
NN
Nr
ij jij j
iN N
jj
GG
NN
η ζψζψ
−−
−−
= =
== −+
∑∑
(3)
其中
2
π
1
e
N
N
ζ
−
=
,
ψ
是
( )
GF r
∗
上阶数为
N
的乘法特
征。一般情况下,高斯周期的值很难通过计算得到。
为了计算循环码的汉明重量的下界,首先给出下面的
引理。
引理
2.3
.
对于任意的整数
i
,满足
01
iN
≤≤ −
,
可以得到
( )
(
)
,
1
1
Nr
i
Nr
NN
η
−
+≤
(4)
证明:当
0
j
=
时,
( )
( )
*
0
1
r
xF
Gx
ψχ
∈
== −
∑
。
所以,
( )
( )
( )
( )
( )
( )
( )
11
,
0
11
0
1
11
1
1
1
11 1
11 1
1
1
1
N
Nr
ij j
iN
j
N
ij j
N
j
N
ij j
N
j
N
j
j
G
NN N
GG
NN N
G
N
Nr
G
NN
η ζψ
ψ ζψ
ζψ
ψ
−
−
=
−
−
=
−
−
=
−
=
+= +
=++
=
−
≤≤
∑
∑
∑
∑
。
令
( )
gcd ,1
nq
=
,且
( )
n
kord q
=
是
q
模
n
的阶数。
设
k
rq
=
,
N
是整除
1
r
−
的正整数,
n
是满足
( )
1
nr N
= −
的正整数。设
α
是
( )
GFr
∗
上的本原元,
N
θα
=
。则集合
( )()()
(
{
( )
)
( )
}
1
,Tr,Tr, ,
Tr ,
rq rq
n
rq
CrNabab
aba bGFr
θ
θ
−
=++
+∈
(5)
是
( )
GF q
上参数为
[ ]
,1
nk
+
的循环码,
Tr
rq
是
( )
GF r
到
( )
GF q
上的迹函数。
由文献
[11]
的定理可以得到,
( )
,
CrN
是
( )
GF q
上以
()( )
1
1
xmx
θ
−
−
为校验多项式的循环码,其中
( )
1
mx
θ
−
是
( )
GF q
上以
1
θ
−
为极小多项式的不可约多
项式。
引理
2.4
.
[9]
N
是整除
1
r
−
的正整数,
(
)
n
kord q
=
是
q
模
n
的阶数。设
() ()
( )
1
gcd11 ,
NrqN
= −−
,则
(3)
中
( )
,
CrN
是
( )
GF q
上参数为
[
]
, 1,
nk d
+
的循环码,
循环码的极小距离
d
满足
( )
( )
()( )()
1
min 1,
1 111
1
rr r
dq
qN
qrN r
q
qNq N
−−
≥−
− −−−
−
−
定理
2.5
.
令
1
3
n
k
−
=
且
1
qn
−<
,
( )
6,
0
n
qC
∈
,则
( )
GF q
上以
( )
(
)
1
1
xmx
θ
−
−
为校验多项式的循环码的
参数为
( )
,2 3,
nn d
+
,
()( )
( )
1 111
1
qrN r
q
d
qNq N
− −−−
−
≥−
其中
( )
( )
13
13
n
Nq
−
= −
。
证明:因为
( )()
13
n
kord qn
== −
且
1
qn
−<
,
所以多项式
(
)
( )
6,
n
i
x
Ω
是
( )
GF q
上的不可约多项式。因
为
(3)
中循环码的校验多项式为
(
)( )
1
1
xmx
θ
−
−
,所以循
环码的维数等于
( )
23
n
+
。
由
1
qn
−<
,
n
是素数可以得到
( )
( )
13
1
1
gcd ,1
1
n
q
NN Nq
q
−
−
== −
−
.
则极小距离
d
由引理
2.4
可以得到。
3.
基于六阶分圆序列的循环码的构造
设
n
是一个素数,
(
)
1 mod3
n
≡
,则
n
可以表示成
22
3
nu v
= +
,
( )
1 mod3
u
≡
,
v
的符号是不确定的。对
OPEN ACCESS
14
基于六阶分圆序列的循环码的构造
于素数
q
,令
3
q
=
,且
( )
gcd ,31
n
=
。设
η
是
( )
3
GF
扩
域上的
n
阶本原单位根,
( )
n
ord q
是
q
模
n
的乘法阶。
定义
( )
( )
( )
( )
6,
6,
n
i
n
i
i
iC
xx
η
∈
Ω= −
∏
,
( )
6,
n
i
C
称为
( )
GF n
上的
6
阶分圆类,则
( )
( )
( )
5
6,
0
11
n
n
i
i
xx x
=
−= −Ω
∏
,显然
( )
()()
[ ]
6,
3
n
i
x GFx
Ω∈
。
下面我们将给出基于六阶分圆序列的循环码的
构造,为此先给出
( )
3
GF
上的序列
λ
∞
。定义
( )()
( )()
6, 6,
03
6, 6,
14
mod
1
1 mod
0
nn
nn
i
i nCC
i nCC
λ
∈
=−∈
,
,
, 其它
,
0
i
≥
.
此序列即是
( )
3
GF
上的序列。
为了计算序列的极小多项式和线性复杂度,我们
需
要计算
( )
( )
gcd 1,
n
xx
−Λ
,并且需要给出下面的多项式
( )
( )
() (
)( )
6, 6,6,6,
03 14
nn nn
ii
iC CiC C
x xx
∈∈
Λ= −
∑∑
(5)
( )
( )()( )(
)
6, 6,6, 6,
5
14 2
nn nn
ii
iC CiC C
x xx
∈∈
Γ= −
∑∑
(6)
由引理
2.2
可得到
(
)()
( )
( )
( )
(
)
6, 6, 6,6,
01 23
6, 6,
5
4
1
nnnn
nn
iiii
iC iC iC iC
ii
iC iC
ηηηη
ηη
∈∈∈∈
∈∈
+++
++ =−
∑∑∑∑
∑∑
由
(5)
式和
(6)
式,以及引理
2.1
可得到下面的引理。
引理
3.1
( )
( )
( )
( )
( )
( )( )
( )
( )
( )
( )
( )
( )
( )( )
( )
( )
6,
0
6,
1
6,
2
6,
3
6,
4
6,
5
,
,
,
,
,
,
n
n
n
a
n
n
n
aC
aC
aC
aC
aC
aC
η
η
ηη
η
η
η
ηη
Λ∈
Γ∈
− Λ+Γ∈
Λ=
Λ∈
Γ∈
− Λ+Γ∈
,
并且
( )
(
)
0
10
η
Λ =Λ=
。
证明:
由引理
2.1
知,如果
( )
6,
n
i
aC
∈
,则有
( )
()
(
)
6,
6,
mod6
n
n
j
ij
aCC
+
=
。
当
( )
6,
0
n
aC
∈
时,则
( )()
6, 6,
nn
ii
aC C
=
,所以
( )
( )()()()
( )()( )()
( )
6, 6,6, 6,
03 14
6, 6,6, 6,
03 14
nn nn
nn nn
aai ai
iC CiCC
ii
iC CiC C
xx
η ηη
η
∈∈
∈∈
Λ= −
=−=Λ
∑∑
∑∑
.
当
( )
6,
1
n
aC
∈
时,则
( )
()
( )
6,
6,
1 mod6
n
n
i
i
aC C
+
=
,所以
(
)
(
)(
)
()
()
( )
()
(
)(
)
( )
6, 6,6, 6,
03 14
6, 6,6, 6,
5
14 2
nn nn
nn nn
aai ai
iC CiCC
ii
iC CiC C
x xx
η ηη
∈∈
∈∈
Λ= −
=−=Γ
∑∑
∑∑
.
当
(
)
6,
2
n
aC
∈
时,则
(
)
(
)
(
)
6,
6,
2 mod6
n
n
i
i
aC C
+
=
,所以
(
)
( )( )()
(
)
( )
(
)
( )
6, 6,6, 6,
03 14
nn nn
aaiai
iC CiCC
η ηη
ηη
∈∈
Λ= −
=− Λ+Γ
∑∑
.
同理,当
(
)
6,
3
n
aC
∈
时,
( )
( )
6,
3 mod6
n
i
aC
+
∈
,所以
( )
( )( )( )( )
( )( )()( )
( )
6, 6,6, 6,
03 14
6, 6,6, 6,
03 14
nn nn
nn nn
aai ai
iC CiCC
ii
iC CiC C
xx
η ηη
η
∈∈
∈∈
Λ= −
=−=Λ
∑∑
∑∑
.
当
( )
6,
4
n
aC
∈
时,则
(
)
( )
(
)
6,
6,
4 mod6
n
n
i
i
aC C
+
=
,所以
( )
(
)
( )
( )
(
)
(
)( )(
)(
)
( )
6, 6,6, 6,
03 14
6, 6,6, 6,
5
14 2
nn nn
nn nn
aai ai
iC CiCC
ii
iC CiC C
x xx
η ηη
∈∈
∈∈
Λ= −
=−=Γ
∑∑
∑∑
.
当
( )
6,
5
n
aC
∈
时,则
( )
( )
6,
5 mod6
n
i
aC
+
∈
,所以
(
)
()(
)()( )
() (
)
( )
6, 6,6, 6,
03 14
nn nn
aaiai
iC CiCC
η ηη
ηη
∈∈
Λ= −
=− Λ+Γ
∑∑
.
引理
3.2
.
[10]
如果
( )
6,
0
1
n
C
−∈
,
( )
6,
0
3
n
C
∈
,则
1)
( )
( )()()()
() ()
6,
2
2
012 3
45
,1, 12,23,3
1
4,45, 5
6
n
l
i
l
iC
llllllll
n
ll ll
ηη
ηη η η
ηη
∈
=
=+− −+−−+−−
−
+−−+− −+
∑
2)
( )( )
()()( )
() ()()
6, 6,
3
3
012
34 5
3,2, 11,2
,3 1,42,5
nn
ll
ij
ll
iC jC
lll lll
lll lll
ηη η
ηηη
ηη η
+
−
+
∈∈
=
=+++−++ −
+−+− −+−−
∑∑
引理
3.3
.
[12]
假设
61
nf
= +
为奇素数,并且
22
4 27
nL M
= +
,其中
( )
1 mod3
L
≡
,
3
M
f
为偶数
OPEN ACCESS
15
基于六阶分圆序列的循环码的构造
时,则
00
1 ,3
CC
−∈ ∈
,
( )
0,1,2,3,4,5
i
i
η
=
的值在
[
12]
的表
3
中已给出。如下:
1)
当
( )
20mod3
ind
η
≡
时,
当
( )
1 mod36
n
≡
时,
01234 5
0, 1
ηηηηη η
== ====−
;
当
( )
13 mod36
n
≡
时,
12345 0
1, 0
ηηηηηη
= =====
;
当
( )
25 mod36
n
≡
时,
12345 0
1, 1
ηηηηηη
=====−=
.
2)
当
( )
21 mod3
ind
η
≡
时
当
( )
1 mod36
n
≡
时,
14025 3
0,1, 1
ηηηηη η
= == ===−
;
当
( )
13 mod36
n
≡
时,
03425 1
1,1,0
ηηηηη η
===−===
;
当
( )
25 mod36
n
≡
时,
013 254
0,1, 1
ηηηηηη
=== ==−=
;
3)
当
( )
22mod3
ind
η
≡
时
当
( )
1 mod36
n
≡
时,
03125 4
0,1, 1
ηηηηη η
====== −
;
当
( )
13 mod36
n
≡
时,
03514 2
1,1, 0
ηηηηη η
===−== =
;
当
( )
25 mod36
n
≡
时,
023 145
0,1, 1
ηηη ηηη
=== ==−=
.
下面我们将给出序列
λ
∞
的极小多项式和线性复
杂度,即给出循环码的生成多项式结果如下面的定理
所示:
定理
3.4
.
设
n
是一个素数,且
( )
1 mod3
n
≡
,
22
3
nuv
= +
,
( )
1 mod3
u
≡
,
v
的符号是不确定的。
λ
∞
是定义在
( )
GF q
上的序列。由序列
λ
∞
定义的
( )
GF q
上的循环码
C
λ
的参数为
[ ]
,,
nkd
,并且循环码
C
λ
的生
成多项式即为序列
λ
∞
的极小多项式,维数
k
=
( )
( )
deg
n mx
λ
−
,则循环码
C
λ
的生成多项式为:
1)
当
( )
20mod3
ind
η
≡
时,极小多项式,即循环
码
C
λ
生成多项式为
( )
(
)
( )
( )
( )
( )
( )
(
)
( )
( )
( )
(
)
( )
( )
(
)
( )
(
)
(
)
( )
(
)
6, 6,
03
6, 6,
14
6, 6,
14
1
,1 mod36
1
1
,13 mod36
1
1
,25mod36 .
1
n
nn
n
nn
n
nn
gxm x
x
n
x xx
x
n
x xx
x
n
x xx
λ
=
−
≡
−Ω Ω
−
= ≡
−Ω Ω
−
≡
−Ω Ω
线性复杂度为
( )
(
)
(
)
22 2
deg gcd1,
33
nn
nn
Lnxxn
+−
=−−Λ=− =
。
即由序列
λ
∞
定义循环码
C
λ
的生成多项式为
( )
mx
λ
,
它的参数为
(
)
,2 3,
nn d
+
。循环码的极小距离
d
满
足定理
2.5
所给定的下界。
2)
当
( )
21 mod3
ind
η
≡
时,极小多项式,即循环
码
C
λ
生成多项式为
(
)(
)
( )
( )
(
)
( )
( )
()
( )
(
)
( )
( )
(
)
( )
(
)
( )
( )
( )
(
)
( )
6, 6,
03
6, 6,
14
6, 6,
14
1
,1mod36
1
1
,13mod36
1
1
,25 mod36
1
n
nn
n
nn
n
nn
gxm x
x
n
x xx
x
n
x xx
x
n
x xx
λ
=
−
≡
−Ω Ω
−
= ≡
−Ω Ω
−
≡
−Ω Ω
线性复杂度为
( )
( )
( )
22 2
deg gcd1,
33
nn
nn
Lnxxn
+−
=−−Λ=− =
。
即由序列
λ
∞
定义循环码
C
λ
的生成多项式为
( )
mx
λ
,它的参数为
( )
,2 3,
nn d
+
。循环码的极小
距离
d
满足定理
2.5
所给定的下界。
3)
当
( )
22mod3
ind
η
≡
时,极小多项式,即循环
码
C
λ
生成多项式为
() (
)
( )
( )
( )
( )
(
)
( )
( )
( )
( )
( )
( )
(
)
( )
( )
( )
( )
(
)
( )
6, 6,
03
6, 6,
14
6, 6,
14
1
,1mod36
1
1
,13mod36
1
1
,25 mod36
1
n
nn
n
nn
n
nn
gxm x
x
n
x xx
x
n
x xx
x
n
x xx
λ
=
−
≡
−Ω Ω
−
= ≡
−Ω Ω
−
≡
−Ω Ω
线性复杂度为
OPEN ACCESS
16
基于六阶分圆序列的循环码的构造
( )
( )
( )
22 2
deg gcd1,
33
nn
nn
Lnxxn
+−
=−−Λ=− =
.
即由序列
λ
∞
定义循环码
C
λ
的生成多项式为
( )
mx
λ
,它的参数为
( )
,2 3,
nn d
+
。循环码的极小
距离
d
满足定理
2.5
所给定的下界。
证明:
1. 1)
当
(
)
1 mod36
n
≡
时,
01234 5
0, 1
ηηηηη η
== ====−
.
当
( )
6,
0
n
aC
∈
时,
(
)
(
)
0
a
ηη
Λ =Λ=
;
当
(
)
6,
1
n
aC
∈
时,
( )
(
)
10
a
ηη
Λ =Γ=≠
;
当
( )
6,
2
n
aC
∈
时,
( )
( )( )
( )
10
a
η ηη
Λ=− Λ+Γ=−≠
;
当
( )
6,
3
n
aC
∈
时,
( )
( )
0
a
ηη
Λ =Λ=
;
当
( )
6,
4
n
aC
∈
时,
( )
( )
10
a
ηη
Λ =Γ=≠
;
当
( )
6,
5
n
aC
∈
时,
( )
( )( )
( )
10
a
η ηη
Λ=− Λ+Γ=−≠
;
所以,它的极小多项式,即生成多项式为
(
)( )
( )
(
)
( )
( )
( )
( )
( )
6, 6,
03
1
gcd 1,
1
1
n
nn
n
nn
x
gxm x
xx
x
x xx
λ
−
= =
−Λ
−
=
−ΩΩ
,
线性复杂度
( )
( )
( )
12 1
deg gcd1,
33
nn
nn
Lnxxn
−+
=−−Λ=− =
.
2)
当
( )
13 mod36
n
≡
时,
12345 0
1, 0
ηηηηηη
= =====
.
当
( )
6,
0
n
aC
∈
时,
( )
( )
10
a
ηη
Λ=Λ=−≠
;
当
( )
6,
1
n
aC
∈
时,
( )
( )
0
a
ηη
Λ =Γ=
;
当
( )
6,
2
n
aC
∈
时,
( )
( )( )
(
)
10
a
η ηη
Λ=− Λ+Γ=≠
;
当
( )
6,
3
n
aC
∈
时,
( )
( )
10
a
ηη
Λ=Λ=−≠
;
当
( )
6,
4
n
aC
∈
时,
( )
( )
0
a
ηη
Λ =Γ=
;
当
( )
6,
5
n
aC
∈
时,
( )
( )( )
( )
10
a
η ηη
Λ=− Λ+Γ=≠
;
所以,它的极小多项式,即生成多项式为
( )( )
(
)
( )
( )
( )
( )
6, 6,
14
1
1
n
nn
x
gxm x
xxx
λ
−
==
−Ω Ω
,
线性复杂度
( )
( )
( )
12 1
deg gcd1,
33
nn
nn
Lnxxn
−+
=−−Λ=− =
.
3)
当
( )
25 mod36
n
≡
时,
12345 0
1, 1
ηηηηηη
=====−=
。
当
(
)
6,
0
n
aC
∈
时,
( )
( )
20
a
ηη
Λ =Λ=≠
;
当
( )
6,
1
n
aC
∈
时,
(
)
(
)
0
a
ηη
Λ =Γ=
;
当
( )
6,
2
n
aC
∈
时,
( )
( )( )
( )
10
a
η ηη
Λ=− Λ+Γ=≠
;
当
( )
6,
3
n
aC
∈
时,
( )
( )
20
a
ηη
Λ =Λ=≠
;
当
( )
6,
4
n
aC
∈
时,
( )
( )
0
a
ηη
Λ =Γ=
;
当
( )
6,
5
n
aC
∈
时,
( )
( )( )
( )
10
a
η ηη
Λ=− Λ+Γ=≠
;
所以,它的极小多项式,即生成多项式为
( )( )
( )
( )
( )
( )
( )
6, 6,
14
1
1
n
nn
x
gxm x
x xx
λ
−
==
−Ω Ω
,
线性复杂度
( )
( )
( )
22 2
deg gcd1,
33
nn
nn
Lnxxn
+−
=−−Λ=− =
.
同理,当
( )
21 mod3
ind
η
≡
和
( )
22mod3
ind
η
≡
时,
序列
λ
∞
的极小多项式
( )
mx
λ
,即循环码的生成多项
式和维数可由引理
3
得到。
例
取
3
q
=
,
61
n
=
,则
C
λ
是
( )
3
GF
上参数为
[ ]
61,21,41
的循环码。
取
3
q
=
,
127
n
=
,则
C
λ
是
( )
3
GF
上参数为
[
]
127,43,85
的循环码。
4.
结论
本篇文章,我们给出了基于六阶分圆序列构造了
循环码的构造方法。计算了在
( )
GF q
上周期为素数
n
的序列的极小多项式和线性复杂度。利用极小多项式
( )
mx
λ
作为循环码
C
λ
的生成多项式
( )
gx
,构造并计
算了在
( )
GF q
上参数为
[ ]
,,
nkd
的循环码
C
λ
。
基金项目
安徽省淮南师范学院自然科学研究项目
(
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
18