杜小妮，王天心，金文剛

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,甘肅 蘭州 730070)

0 引言

線性碼具有良好的代數(shù)結(jié)構(gòu)和高效的譯碼算法,因此廣泛應(yīng)用于通信、信息安全和數(shù)據(jù)存儲(chǔ)系統(tǒng)等領(lǐng)域.一般情況下,確定線性碼的長(zhǎng)度、維數(shù)和最小距離是比較困難的,能確定重量分布的碼字只占很小的一部分，因此,線性碼的構(gòu)造及其重量分布一直是密碼學(xué)者關(guān)注的課題.具有較低重量的線性碼可被應(yīng)用于認(rèn)證碼[1]、結(jié)合方案[2]、強(qiáng)正則圖[3]和構(gòu)造具有良好訪問(wèn)結(jié)構(gòu)的秘密共享方案[4]等領(lǐng)域,極小線性碼在秘密共享方案[4]和兩方安全計(jì)算[5]中扮演著重要角色.一般地,具有較低重量的極小線性碼可以通過(guò)選擇不同的定義集[6]來(lái)構(gòu)造,且大多數(shù)滿足Ashikhmin-Barg條件.2018年,Chang等[7]提出了一類不滿足Ashikhmin-Barg條件的極小二元線性碼；Heng等[8]構(gòu)造了一類不滿足Ashikhmin-Barg條件的無(wú)限族的極小三元線性碼,并給出了判斷極小線性碼的充要條件；Ding等[9]給出了另一種判斷極小二元線性碼的充要條件,并構(gòu)造了三類不滿足Ashikhmin-Barg條件的極小二元線性碼,同時(shí)確定了這些碼的重量分布.2019 年,Xu 等[10]研究了奇數(shù)域上的極小線性碼；Bartoli等[11]將文獻(xiàn)[9]中的第三類極小線性碼從二元推廣到特征為奇數(shù)的情況.2020年,Bonini 等[12]利用文獻(xiàn)[7]的方法構(gòu)造了許多極小二元線性碼；受文獻(xiàn)[9,10]的啟發(fā),Mesnager 等[13]利用特征函數(shù)構(gòu)造了多類極小線性碼.

受上述工作的啟發(fā),文中基于特征函數(shù)構(gòu)造極小碼的方法,在文獻(xiàn)[13]的基礎(chǔ)上,選取適當(dāng)?shù)亩x集,構(gòu)造了一類具有較低重量且不滿足Ashikhmin-Barg條件的極小線性碼.

1 預(yù)備知識(shí)

文中總假定p是素?cái)?shù)且q=pm,其中m是正整數(shù)；Fq是含有q個(gè)元素的有限域,F*q表示Fq的乘法群.Fp上n維空間的一個(gè)k維子空間稱為碼長(zhǎng)為n、維數(shù)為k的[n,k,d]線性碼C,其中最小漢明距離為d,C中的每一個(gè)向量稱為碼字.設(shè)Ai表示C中漢明重量為i的碼字的個(gè)數(shù),則1+A1z+A2z2+…+Anzn定義為碼C的重量計(jì)數(shù)器,序列(1,A1,…,An)稱為碼C的重量分布.若在A1,A2,…,An中,使得Ai≠0(1≤i≤n)的個(gè)數(shù)為t,則稱碼C為t重碼.C中碼字a=(a1,a2,…,an)的支撐集定義為

supp(a)={1≤i≤n:ai≠0},

且碼字a的漢明重量w(a)滿足

w(a)=|supp(a)|.

引理1[14](Ashikhmin-Barg條件) 如果Fp上的線性碼C的最大漢明重量wmax和最小漢明重量wmin滿足wmin/wmax>(p-1)/p,那么線性碼C是極小碼.

(1)

(2)

(3)

2 極小線性碼的構(gòu)造

(6)

首先給出線性碼CD的一些性質(zhì).

其中t=w(r).

首先確定|D|,由D的定義可知

(7)

(8)

所以

顯然,w(cr)取決于w(r).所以,當(dāng)給定p和m時(shí)可以確定碼CD的wmin和wmax的值.可以看出,對(duì)任意的素?cái)?shù)p及正整數(shù)m≥4,構(gòu)造的碼CD至多為m重的.

下面的引理3用于證明CD是極小線性碼.

定理2設(shè)定義集D的選取如(6)式,則(1)式定義的線性碼CD是一個(gè)極小線性碼.

則(7)～(8)式結(jié)合引理3可知,

下證|{x∈D:r2,x≠0,r1,x=0}|>0.由線性無(wú)關(guān)可知，存在i,j使得(b1i,b2i)和(b1j,b2j)也線性無(wú)關(guān),其中1≤i≠j≤m.因此,存在c1,c2∈Fp使得

c1(b1i,b2i)+c2(b1j,b2j)=(0,1).

|{x∈D:r2,x≠0,r1,x=0}|>0,

即M≠(ζp-1)(p-1)|D|.因此,由引理2可知CD是極小線性碼.】

證明由引理3可知,碼字cr的重量取決于w(r)，從而

為了討論方便,設(shè)w(r)=1時(shí)w(cr)的值為w1,w(r)=m時(shí)w(cr)的值為wm.下證w1

因?yàn)閜為素?cái)?shù),所以只需(m-3)p2-3(m-2)p+3(m-1)>0.

下面對(duì)p和m的取值分類進(jìn)行結(jié)論.

因此

當(dāng)p=3且m≥6或p=5且m≥5時(shí)的證明與p=2且m≥6時(shí)的情形類似,此處省略.

令h1(x,m)=(m-3)x2-3(m-1)x+3m,則h1(x,m)的對(duì)稱軸為

因?yàn)閙為正整數(shù)，所以3/(m-3)在m=4時(shí)取得最大值4，所以x=9/2.因?yàn)閜=7時(shí)h1(m,7)=31m-126,所以m≥5時(shí)h1(x,m)單調(diào)遞增且均為正值.因此,當(dāng)p≥7且m≥5時(shí),結(jié)論成立.

由引理1可知,在給定參數(shù)(p,m)對(duì)的取值情形下,CD是不滿足Ashikhmin-Barg條件的極小線性碼,即為寬極小碼.】

注1當(dāng)p=2且m=3時(shí),CD是常重碼.

定理3中(p,m)特殊取值對(duì)應(yīng)極小碼的屬性如表1所示.

表1 極小線性碼的屬性

3 總結(jié)

在文獻(xiàn)[13]的基礎(chǔ)上,基于特征函數(shù)構(gòu)造極小線性碼的方法,通過(guò)選取適當(dāng)?shù)亩x集,構(gòu)造了一類不滿足Ashikhmin-Barg 條件的低重極小線性碼.結(jié)果表明,得到的線性碼均為極小線性碼,且除個(gè)別參數(shù)下的線性碼屬于窄極小碼外,其余所得的線性碼均為寬極小碼,可用作設(shè)計(jì)具有良好訪問(wèn)結(jié)構(gòu)的秘密共享方案.