New infinite families of near MDS codes holding t-designs

2025-05-02 0 0 311.97KB 34 页 10玖币

侵权投诉

arXiv:2210.05194v2 [cs.IT] 17 Mar 2023

New inﬁnite families of near MDS codes holding t-designs

Ziling Heng, Xinran Wang

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

Abstract

In “Inﬁnite families of near MDS codes holding t-designs, IEEE Trans. Inform. Theory, 2020,

66(9), pp. 5419-5428”, Ding and Tang made a breakthrough in constructing the ﬁrst two inﬁnite

families of NMDS codes holding 2-designs or 3-designs. Up to now, there are only a few known

inﬁnite families of NMDS codes holding t-designs in the literature. The objective of this paper

is to construct new inﬁnite families of NMDS codes holding t-designs. We determine the weight

enumerators of the NMDS codes and prove that the NMDS codes hold 2-designs or 3-designs.

Compared with known t-designs from NMDS codes, ours have different parameters. Besides,

several inﬁnite families of optimal locally recoverable codes are also derived via the NMDS codes.

Keywords: Linear code, weight enumerator, t-design

2000 MSC: 94B05, 94A05

1. Introduction

Let qbe a power of a prime p. Denote by Fqthe ﬁnite ﬁeld with qelements and F∗

q=Fq\ {0}.

1.1. Linear codes

For a positive integer n, a non-empty subset Cof Fn

qis called an [n,κ,d]linear code over Fq

provided that it is a κ-dimensional linear subspace of Fn

q, where dis its minimum distance. Deﬁne

the dual of an [n,κ]linear code Cover Fqby

C⊥=u∈Fn

q:hu,ci=0 for all c∈C,

where h·,·i denotes the standard inner product. By deﬁnition, C⊥is an [n,n−κ]linear code over

Fq. For an [n,κ]linear code Cover Fq, let Airepresent the number of codewords with weight iin

C, where 0 ≤i≤n. Deﬁne the weight enumerator of Cas the following polynomial:

A(z) = 1+A1z+A2z2+···+Anzn.

The weight distribution of Cis deﬁned by the sequence (A0,A1,...,An). In recent years, the weight

distribution of linear codes has been widely investigated in the literature [4, 5, 6, 7, 9, 10, 11,

⋆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)

15, 16, 19, 20, 21, 32, 37]. The weight distribution of a linear code contains crucial information

including the error detection and correction capabilities of the code and allows to compute the error

probability of its error detection and correction [17].

In coding theory, modifying existing codes may yield interesting new codes. A longer code can

be constructed by adding a coordinate. Let Cbe an [n,κ,d]linear code over Fq. The extended code

Cof Cis deﬁned by

C=((c1,c2,...,cn,cn+1)∈Fn+1

q:(c1,c2,...,cn)∈Cwith

n+1

∑

i=1

ci=0).

This construction is said to be adding an overall parity check [23]. Note that Chas only even-like

vectors. Then Cis also a linear code over Fqwith parameters [n+1,κ,d], where d=dor d+1.

For instance, the extended code of the binary [7,4,3]Hamming code has parameters [8,4,4]. The

extension technique was used in [3, 33] to obtain desirable codes.

An [n,κ,d]linear code is said to be good if it has both large rate κ/nand large minimum

distance d. However, there is a tradeoff among the parameters n,κand d. If an [n,κ,d]linear code

over Fqexists, then the following Singleton bound holds:

d≤n−κ+1.

Linear codes achieving the Singleton bound with parameters [n,κ,n−κ+1]are called maximum

distance separable (MDS for short) codes. Linear codes nearly achieving the Singleton bound are

also interesting and have attracted the attention of many researchers. An [n,κ,n−κ]linear code

is said to be almost maximum distance separable (AMDS for short). It is known that the dual of

an AMDS code may not be AMDS. AMDS codes whose duals are also AMDS are said to be near

maximum distance separable (NMDS for short). NMDS codes are of interest because they have

many nice applications in ﬁnite geometry, combinatorial designs, locally recoverable codes and

many other ﬁelds [5, 20, 21, 28, 29]. In general, constructing inﬁnite families of NMDS codes with

desirable weight distribution is challenging. In recent years, a few families of NMDS codes were

constructed in [5, 20, 21, 29, 33, 34] and their weight distributions were determined.

1.2. Combinatorial designs from linear codes

Let k,t,nbe positive integers such that 1 ≤t≤k≤n. Let Pbe a set with |P|=n≥1. Denote

by Ba collection of k-subsets of P. For each t-subset of P, if there exist exactly λelements of B

such that they contain this t-subset, then the pair D:= (P,B)is referred to as a t-(n,k,λ)design

(t-design for short). The elements in Pand Bare called points and blocks, respectively. A t-design

is said to be simple if it contains no repeated blocks. A t-design with k=tor k=nis said to be

trivial. In this paper, we are interested in only simple and nontrivial t-designs with n>k>t. A

t-(n,k,λ)design satisfying t≥2 and λ=1 is called a Steiner system denoted by S(t,k,n). For a

t-(n,k,λ)design, the following equality holds [23]:

n

tλ=k

tb,

where bis the number of blocks in B. Let Bcrepresent the set of the complements of the blocks in

B. Then (P,Bc)is a t-(n,n−k,λ0,t)design if (P,B)is a t-(n,k,λ)design, where

λ0,t=λn−t

k

n−t

k−t.(1)

The pair (P,Bc)is referred to as the complementary design of (P,B).

In past decades, the interplay between linear codes and t-designs has been a very interesting

research topic. For one thing, the incidence matrix of a t-design yields a linear code. See [2] for

progress in this direction. For another thing, linear codes may hold t-designs. The well-known

coding-theoretic construction of t-designs is described as follows. Let Cbe an [n,κ]linear code

over Fqand the coordinates of a codeword in it be indexed by (1,2,...,n). Denote by P(C) =

{1,2,...,n}. For a codeword c={c1,c2,...,cn} ∈ C, deﬁne its support by

suppt(c) = {1≤i≤n:ci6=0}.

Denote by

Bw(C) = 1

q−1{{suppt(c):wt(c) = wand c∈C}},

where {{}} denotes the multiset notation, wt(c)is the Hamming weight of cand 1

q−1Sdenotes the

multiset obtained by dividing the multiplicity of each element in the multiset Sby q−1 [30]. If

the pair (P(C),Bw(C)) is a t-(n,w,λ)design with bblocks for 0 ≤w≤n, we say that the code C

supports t-designs, where

b=1

q−1Aw,λ=w

t

(q−1)n

tAw.(2)

The following Assmus-Mattson Theorem provides a sufﬁcient condition for a linear code to

hold t-designs.

Theorem 1. [3, Assmus-Mattson Theorem] Let Cbe an [n,κ,d]linear code over Fqwhose weight

distribution is denoted by (1,A1,A2,...,An). Let d⊥be the minimum weight of C⊥whose weight

distribution is denoted by (1,A⊥

1,A⊥

2,...,A⊥

n). Let t be an integer satisfying 1≤t<min{d,d⊥}.

Assume that there are at most d⊥−t nonzero weights of Cin the range {1,2,...,n−t}. Then the

followings hold:

1. (P(C),Bi(C)) is a simple t-design if Ai6=0with d ≤i≤w, where w is the largest integer

satisfying w ≤n and

w−w+q−2

q−1<d.

2. (P(C⊥),Bi(C⊥)) is a simple t-design if A⊥

i6=0with d⊥≤i≤w⊥, where w⊥is the largest

integer satsifying w⊥≤n and

w⊥−w⊥+q−2

q−1<d⊥.

The Assmus-Mattson Theorem is a powerful tool for constructing t-designs from linear codes

and has been widely used in [3, 6, 7, 8]. Another method to prove that a linear code holds t-designs

is via the automorphism group of the code. Several inﬁnite families of t-designs were constructed

via this method in the literature [3, 8, 9, 10, 11, 31, 35, 36]. The third method is directly character-

izing the supports of the codewords of ﬁxed weight. See [5, 29, 35] for known t-designs obtained

by this method. Recently, Tang, Ding and Xiong generalized the Assmus-Mattson Theorem and

derived t-designs from codes which don’t satisfy the conditions in the Assmus-Mattson Theorem

and don’t admit t-homogeneous group as a subgroup of their automorphisms [30].

1.3. Motivations and objectives of this work

Constructing t-designs from special NMDS codes has been an interesting research topic for a

long time. The ﬁrst NMDS code dates back to 1949. Golay discovered the [11,6,5]ternary NMDS

code which is called the ternary Golay code. This NMDS code holds 4-designs. In the past 70

years after this discovery, only sporadic NMDS codes holding t-designs were found. The question

as to whether there exists an inﬁnite family of NMDS codes holding an inﬁnite family of t-designs

for t≥2 remained open during this long period. In 2020, Ding and Tang made a breakthrough in

constructing the ﬁrst two inﬁnite families of NMDS codes holding 2-designs or 3-designs [5]. Up

to now, there are only a few known inﬁnite families of NMDS codes holding t-designs for t=2,3,4

in the literature [5, 29, 34, 38]. It is challenging to construct new inﬁnite families of NMDS codes

holding t-designs with t>1.

The objective of this paper is to construct several new inﬁnite families of NMDS codes holding

t-designs. To this end, some special matrices over ﬁnite ﬁelds are used as the generator matrices of

the NMDS codes. We then determine the weight enumerators of the NMDS codes and prove that

the NMDS codes hold 2-deigns or 3-designs. Most of the NMDS codes in this paper don’t satisfy

the conditions in the Assmus-Mattson Theorem but still hold t-designs. Compared with known

t-designs from NMDS codes, ours have different parameters. Besides, several inﬁnite families of

optimal locally recoverable codes are also derived via the NMDS codes.

2. Preliminaries

In this section, we present some preliminaries on the properties of NMDS codes and oval poly-

nomials, and the number of zeros of some equations over ﬁnite ﬁelds.

2.1. Properties of NMDS codes

Let Cbe an [n,κ]linear code and C⊥be its dual. Denote by (1,A1,...,An)and (1,A⊥

1,...,A⊥

the weight distributions of Cand C⊥, respectively. If Cis an NMDS code, then the weight distri-

butions of Cand C⊥are given in the following lemma.

Lemma 2. [3] Let Cbe an [n,κ,n−κ]NMDS code over Fq. If s ∈ {1,2,...,n−κ}, then

A⊥

κ+s=n

κ+ss−1

∑

j=0

(−1)jκ+s

j(qs−j−1) + (−1)sn−κ

sA⊥

κ.

If s ∈ {1,2,...,κ}, then

An−κ+s=n

κ−ss−1

∑

j=0

(−1)jn−κ+s

j(qs−j−1) + (−1)sκ

sAn−κ.

Though Lemma 2 and the relation 1 +∑κ

s=0An−κ+s=qκhold, the weight distribution of an

[n,κ]NMDS code still can not be totally determined. In [20], some inﬁnite families of NMDS

codes with the same parameters but different weight distributions were constructed.

The following lemma establishes an interesting relationship between the minimum weight code-

words in Cand those in C⊥.

Lemma 3. [12] Let Cbe an NMDS code. For any c= (c1,...,cn)∈C, its support is deﬁned by

suppt(c) = {1≤i≤n:ci6=0}. Then for any minimum weight codeword cin C, there exists, up

to a multiple, a unique minimum weight codeword c⊥in C⊥satisfying suppt(c)∩suppt(c⊥) = /

Besides, the number of minimum weight codewords in Cand the number of those in C⊥are the

same.

By Lemma 3, if the minimum weight codewords of an NMDS code hold a t-design, then the

minimum weight codes of its dual hold a complementary t-design.

2.2. Oval polynomials and their properties

The deﬁnition of oval polynomial is presented as follows.

Deﬁnition 4. [25] Let q =2mwith m ≥2. If f ∈Fq[x]is a polynomial such that f is a permutation

polynomial of Fqwith deg(f)<q and f (0) = 0, f (1) = 1, and ga(x):= ( f(x+a) + f(a))xq−2is

also a permutation polynomial of Fqfor each a ∈Fq, then f is called an oval polynomial.

The following gives some known oval polynomials.

Lemma 5. [26] Let m ≥2be an integer. Then the followings are oval polynomials of Fq, where

q=2m.

1. The translation polynomial f (x) = x2h, where gcd(h,m) = 1.

2. The Segre polynomial f (x) = x6, where m is odd.

By Lemma 5, it is obvious that f(x) = x4is an oval polynomial of Fq, where q=2mfor odd m.

By Deﬁnition 4, the following also holds for oval polynomials.

Lemma 6. Let q =2mwith m ≥2. Then f is an oval polynomial of Fqif and only if the followings

simultaneously hold:

1. f is a permutation polynomial of Fqwith deg(f)<q and f (0) = 0, f (1) = 1; and

2. f(x) + f(y)

x+y6=f(x) + f(z)

x+z

for all pairwise distinct elements x,y,z in Fq.

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

Let q=pmwith pa prime. The following lemma is very useful for determining the greatest

common divisor of some special integers.

Lemma 7. Let h and m be two integers with gcd(h,m) = ℓ. Then

gcd(ph+1,q−1) = 





1,for odd m

ℓand p =2,

2,for odd m

ℓand odd p,

pℓ+1,for even m

ℓ.

The following lemmas present some results on the number of solutions of some equations over

Fq.

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

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

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.05194v2[cs.IT]17Mar2023NewinﬁnitefamiliesofnearMDScodesholdingt-designsZilingHeng,XinranWangSchoolofScience,Chang’anUniversity,Xi’an710064,ChinaAbstractIn“InﬁnitefamiliesofnearMDScodesholdingt-designs,IEEETrans.Inform.Theory,2020,66(9),pp.5419-5428”,DingandTangmadeabreakthroughinconstruct...

展开>> 收起<<

New infinite families of near MDS codes holding t-designs.pdf

共34页,预览5页

还剩页未读，继续阅读

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

New infinite families of near MDS codes holding t-designs

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: