Constructions of cyclic codes and extended primitive cyclic codes with their applications_2

2025-04-27 0 0 200.98KB 21 页 10玖币

侵权投诉

arXiv:2210.05170v1 [cs.IT] 11 Oct 2022

Constructions of cyclic codes and extended primitive cyclic codes

with their applications

Ziling Heng, Xinran Wang∗, Xiaoru Li

School of Science, Chang’an University, Xi’an 710064, China

Abstract

Linear codes with a few weights have many nice applications including combinatorial design, dis-

tributed storage system, secret sharing schemes and so on. In this paper, we construct two families

of linear codes with a few weights based on special polynomials over ﬁnite ﬁelds. The ﬁrst family

of linear codes are extended primitive cyclic codes which are afﬁne-invariant. The second family

of linear codes are reducible cyclic codes. The parameters of these codes and their duals are de-

termined. As the ﬁrst application, we prove that these two families of linear codes hold t-designs,

where t=2,3. As the second application, the minimum localities of the codes are also determined

and optimal locally recoverable codes are derived.

Keywords: Linear code, cyclic code, extended primitive cyclic code

2000 MSC: 94B05, 94A05

1. Introduction

Let Fqbe the ﬁnite ﬁeld with qelements, where qis a power of a prime. Let F∗

q:=Fq\ {0}.

Let Cbe a non-empty set such that C⊆Fn

q. If Cis a k-dimensional linear subspace over Fq, then

Cis called an [n,k,d]linear code over Fq, where ddenotes its minimum distance. In particular, if

any codeword (c0,c1,···,cn−1)∈Cimplies (cn−1,c0,···,cn−2)∈C, then Cis called a cyclic code.

The dual of an [n,k,d]linear code Cis deﬁned by

C⊥=u∈Fn

q:hu,ci=0∀c∈C,

where hu,cidenotes the standard inner product of uand c. It is obvious that C⊥is an [n,n−k]

linear code. Let Aidenote the number of codewords with weight iin a linear code of length n,

where 0 ≤i≤n. Then A(z) = 1+A1z+A2z2+···+Anznis referred to as the weight enumerator

of C. The sequence (1,A1,··· ,An)is called the weight distributions of C. The weight enumerator

can be used not only to characterize the error detection and correction capabilities of linear codes,

⋆This research was supported in part by the National Natural Science Foundation of China under Grant 12271059,

in part by the Young Talent Fund of University Association for Science and Technology in Shaanxi, China, under

Grant 20200505, and in part by the Fundamental Research Funds for the Central Universities, CHD, under Grant

300102122202.

∗Corresponding author

Email addresses:

zilingheng@chd.edu.cn

(Ziling Heng),

wangxr203@163.com

(Xinran Wang∗),

lixiaoru@163.com

(Xiaoru Li)

but also to calculate the error rate of error correction and detection. The weight enumerator of

linear codes including cyclic codes has been studied in a large number of literatures in recent years

[6, 11, 14, 15, 16, 17, 18, 19, 22, 29].

Let κ,tand nbe positive integers with 1 ≤t≤κ≤n. Let Pbe a set of nelements and Bbe a

set of κ-subsets of P. The pair D= (P,B)is called a t-(n,κ,λ)design, or simply t-design, if each

t-subset of Pis contained in precisely λelements of B. The elements of Pare called points and the

elements of Bare referred to as blocks. A t-design without repeated blocks is said to be simple. A

t-design is called a Steiner system if λ=1 and t≥2, which is denoted by S(t,κ,n). Some Steiner

systems have been constructed in [4, 9, 23, 25, 26, 30].

Linear codes can be used to constructed t-designs. The well-known coding-theoretic construc-

tion is described below. Let P={1,2,···,n}be a set of coordinate positions of the codewords

of linear code Cwith length n. The support of a codeword c={c1,c2,···,cn}in Cis deﬁned by

suppt(c) = {1≤i≤n:ci6=0}. Let Bκdenote the set of supports of all codewords with Hamming

weight κin C. The pair (P,Bκ)may be a t-(n,κ,λ)design for some positive integer λ, which is

referred to as a support design of C. In other words, we say that the codewords with weight κin

Csupport a t-(n,κ,λ)design. When the pair (P,Bκ)is a simple t-(n,κ,λ)design, we have the

following relation:

|Bκ|=1

q−1Aκ,n

tλ=κ

t1

q−1Aκ.(1)

The following theorem developed by Assmus and Mattson gives a sufﬁcient condition such that

the pair (P,Bκ)deﬁned in a linear code Cis a t-design.

Theorem 1. [1] (Assmus-Mattson Theorem) Let Cbe an [n,k,d]code over Fq, and let d⊥denote

the minimum distance of C⊥. Let w be the largest integer satisfying w ≤n and

w−w+q−1

q−2<d.

Deﬁne w⊥analogously with d⊥. Let (A0,A1,···,An)and (A⊥

0,A⊥

1,···,A⊥

n)be the weight distribu-

tions of Cand C⊥, respectively. Let t be a positive integer with t <d such that there are at most

d⊥−t weights of Cin the sequence (A0,A1,···,An−t). Then

1. (P,Bκ)is a simple t-design provided that Aκ6=0and d ≤κ≤w;

2. (P,B⊥

κ)is a simple t-design provided that A⊥

κ6=0and d⊥≤κ≤w⊥, where B⊥

κdenotes the

set of supports of all codewords of weight κin C⊥.

The Assmus-Mattson Theorem is a powerful tool for construction t-design from linear codes

[3, 4, 5, 6, 7, 8, 10, 20, 21, 26, 27, 28].

We can also use the automorphism group approach to obtain t-designs from linear codes. We

review the automorphism group of linear codes for introducing this approach. The set of coordinate

permutations that map a code Cto itself forms a group denoted by PAut(C). PAut(C) is called the

permutation automorphism group of C. If Cis a code with length n, then PAut(C) is a subgroup

of the symmetric group Sym(n). A monomial matrix over Fqis a square matrix which has exactly

one nonzero element of Fqin each row and column. A monomial matrix Mcan be written either in

the form PD or the form D′Pwith Pa permutation matrix and Dand D′being diagonal matrices.

The set of monomial matrices that map Cto itself forms a group denoted as MAut(C). MAut(C)

is called the monomial automorphism group of C. It is obvious that PAut(C)⊆MAut(C). The

automorphism group Aut(C) of Cis a set of maps with form Mσthat map Cto itself, where Mis

a monomial matrix and σis a ﬁeld automorphism. Then we have PAut(C)⊆MAut(C)⊆Aut(C).

Note that PAut(C), MAut(C) and Aut(C) are the same in the binary case.

Clearly, every element in Aut(C) has the form DPσ, where Dis a diagonal matrix, Pis a

permutation matrix and σis an automorphism of Fq. If for every pair of t-element ordered sets of

coordinates, there exists an element DPσin Aut(C) such that its permutation part Psends the ﬁrst

set to the second set, then Aut(C) is called t-transitive. The following gives a sufﬁcient condition

for a linear code to hold t-designs.

Theorem 2. [13] Let Cbe a linear code of length n over Fq. If Aut(C) is t-transitive, then the

codewords of any weight i ≥t of Chold a t-design.

The objective of this paper is to construct two families of linear codes with a few weights and

study their applications. We ﬁrst construct the linear codes based on special polynomials over

ﬁnite ﬁelds. The ﬁrst family of linear codes are extended primitive cyclic codes which are afﬁne-

invariant. The second family of linear codes are cyclic codes. The parameters of these codes and

their duals are determined. As the ﬁrst application, we prove that these two families of linear codes

hold t-designs, where t=2,3. As the second application, the minimum localities of the codes are

also determined and optimal locally recoverable codes are derived.

The remainder of this paper is organized as follows. In Section 2, we introduce some prelimi-

nary results on the number of zeros of some equations over ﬁnite ﬁelds and afﬁne-invariant codes,

which will be used in this paper. In Section 3, we construct a class of extended primitive cyclic

codes by a special function and determine their parameters. We then derive some inﬁnite families

of 2-designs and 3-designs from these linear codes. In Section 4, we give another construction of

linear codes, which are cyclic codes, and determine their parameters and weight distributions. It

turns out that they hold 3-designs. In Section 5, we drive some optimal locally recoverable codes

from these linear codes. In Section 6, we conclude the paper.

2. Preliminaries

In this section, we will present some preliminary results on the number of zeros of some equa-

tions over Fqand afﬁne-invariant codes.

2.1. The number of zeros of some equations over ﬁnite ﬁelds

Lemma 3. Let h and m be two integers with h <m and let q =pmwith p a prime. Deﬁne a nonzero

polynomial of the form

g(x) =

∑

i=0

aixpi,ai∈Fq.

Denote by Ngthe number of zeros of g(x)in Fq. Then Ng∈ {1,p,p2,p3,···,ph}.

Proof. It is obvious that Ng≤ph. Let Gbe the set of zeros of g(x)in Fq. Then G6=/

0as 0 ∈G. It

is easy to prove that (G,+) is a subgroup of Fq. By Lagrange’s Theorem, the order of Gdivides

the order of Fq. Then we have Ng∈ {1,p,p2,p3,···,ph}.

In the following, we let αbe a generator of F∗

qand give some examples to verify Lemma 3.

Example 4. Let p =2,m=5and q =pm. Let

g1(x) = α2x+αx2+α5x4.

Denote by Ng1the number of zeros of g1(x)in Fq. By Magma program, Ng1=2.

Example 5. Let p =2,m=4and q =pm. Let

g2(x) = α3x+α5x2+α8x4+α7x8.

Denote by Ng2the number of zeros of g2(x)in Fq. By Magma program, Ng2=4.

Example 6. Let p =3,m=4and q =pm. Let

g3(x) = α5x+α9x3+α12x9+α11x27.

Denote by Ng3the number of zeros of g3(x)in Fq. By Magma program, Ng3=9.

Example 7. Let p =2,m=4and q =pm. Let

g4(x) = α13x+α7x2+α10x4+αx8.

Denote by Ng4the number of zeros of g4(x)in Fq. By Magma program, Ng4=8.

Example 8. Let p =3,m=3and q =pm. Let

g5(x) = α14x+α10x3+α24x9.

Denote by Ng5the number of zeros of g5(x)in Fq. By Magma program, Ng5=9.

Let hand mbe positive integers with h<mand let q=pmwith pa prime. Now we consider

the zeros of the nonzero polynomial

f(x) = c+

∑

i=0

aixpi,ai,c∈Fq,(2)

in Fq. Let g(x)be the polynomial deﬁned in Lemma 3. It is obvious that f(x) = g(x) + c,c∈Fq.

Lemma 9. Let h and m be positive integers with h <m and let q =pmwith p a prime. Denote by

Nfthe number of zeros of f (x)in Fq. Then Nf∈ {0,1,p,p2,p3,···,ph}.

Proof. If ai=0 for all 0 ≤i≤hand c6=0, then Nf=0. Now we assume that (a0,a1,···,ah)6=

(0,0,···,0). If f(x)has a zero uin Fq, then f(u) = g(u) + c=0 which implies c=−g(u). Thus

f(x) = g(x) + c=g(x)−g(u) = g(x−u). This implies that Nf=Ng. By Lemma 3, we have

Nf∈ {1,p,p2,p3,···,ph}. The desired conclusion follows.

Lemma 10. [25] Let q =pm, where p is an odd prime, m ≥2. Let 1≤s≤m−1, l =gcd(m,s). Let

Uq+1:={x∈Fq2:xq+1=1}and f (x) = ax+bxps+cxps+1+u, where (a,b,c,u)∈F4

q2\{0,0,0,0}.

Then f (x)has 0,1,2or pl+1zeros in Uq+1.

2.2. Afﬁne-invariant codes

In this subsection, we introduce afﬁne-invariant codes.

We give the deﬁnition of primitive cyclic codes at ﬁrst. A primitive cyclic code is a cyclic

code of length n=qm−1 over Fq, where mis a positive integer. Let Rnrepresent the quotient ring

Fq[x]/(xn−1). Any primitive cyclic code Cover Fqis an ideal of Rnwhich is generated by a monic

polynomial g(x)of the least degree over Fq. We call this polynomial the generator polynomial of

C. It can be represented as

g(x) = ∏

t∈T

(x−αt),

where αis a generator of F∗

qmand T⊂ {0,1,···,n−1}is a union of some q-cyclotomic cosets

modulo n.

We then introduce the extended primitive cyclic codes. Let Gdenote the generator matrix of

a primitive cyclic code C. Deﬁne a matrix Gby adding a column to Gsuch that the sum of the

elements of each row of Gis 0. The matrix Gis the generator matrix of the extended code of C. The

extended code of a primite cyclic code Cis called an extended primitive cyclic code and denoted

by C.

Deﬁne the afﬁne group GA1(Fq)by the set of all permutations σu,v:x7−→ ux +vof Fq, where

u∈F∗

q,v∈Fq. An afﬁne-invariant code is an extended primitive cyclic code Csuch that GA1(Fq)⊆

PAut(C). It is easy to prove that the group action of GA1(Fq)on Fqis doubly transitive, i.e. 2-

transitive. Then by the Theorem 2, we have the following theorem.

Theorem 11. [13] For each i with Ai6=0in an afﬁne-invariant code C, the supports of the code-

words of weight i form a 2-design.

Theorem 11 is a very useful tool in constructing t-designs from extended primitive cyclic codes.

3. A family of extended primitive cyclic codes

In this section, let hand mbe positive integers with h<mand q=pmwith pa prime. For

convenience, let dim(C)and d(C)respectively denote the dimension and minimum distance of a

linear code C. Let αbe a generator of F∗

qand αi:=αifor 1 ≤i≤q−1.

Deﬁne

Dh=







1 1 ··· 1 1

α1α2··· αq−10

αp

1αp

2··· αp

q−10

αp2

1αp2

2··· αp2

q−10

αph

1αph

2··· αph

q−10







,(3)

Dhis an h+2 by qmatrix over Fq. Let CDhbe the linear code over Fqgenerated by Dh. Let D′

hbe

the h+2 by q−1 submatrix of Dhobtained by deleting the last column of Dh. Then the linear code

CD′

hgenerated by D′

his obvious a primitive cyclic code. It is easy to verify that CDhis the extended

code of CD′

h. Hence CDhis an extended primitive cyclic code.

In the following, we study the parameters of CDhand its dual C⊥

Dhand obtain t-designs from

them.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.05170v1[cs.IT]11Oct2022ConstructionsofcycliccodesandextendedprimitivecycliccodeswiththeirapplicationsZilingHeng,XinranWang∗,XiaoruLiSchoolofScience,Chang’anUniversity,Xi’an710064,ChinaAbstractLinearcodeswithafewweightshavemanyniceapplicationsincludingcombinatorialdesign,dis-tributedstorag...

展开>> 收起<<

Constructions of cyclic codes and extended primitive cyclic codes with their applications_2.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Constructions of cyclic codes and extended primitive cyclic codes with their applications_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: