一類基于特征函數(shù)構(gòu)造的極小線性碼

胡金霞，金文剛，王天心

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

0 引言

線性碼因其具有良好的代數(shù)結(jié)構(gòu)和高效的譯碼算法等特性,被廣泛地應(yīng)用于通信、信息安全和數(shù)據(jù)存儲(chǔ)系統(tǒng)等領(lǐng)域.線性碼的重量分布不僅表明了碼的糾錯(cuò)能力,還可用來(lái)計(jì)算信息在傳輸過(guò)程中產(chǎn)生的錯(cuò)誤概率.一般情況下,確定線性碼的長(zhǎng)度、維數(shù)和最小距離都是比較困難的,能確定重量分布的碼字占很小的一部分.因此,線性碼的構(gòu)造及其重量分布一直是線性碼研究中的重要課題.特別地,具有較低重量的線性碼可被應(yīng)用于認(rèn)證碼[1]、結(jié)合方案[2]、強(qiáng)正則圖[3]和構(gòu)造具有良好訪問(wèn)結(jié)構(gòu)的秘密共享方案等領(lǐng)域[4].此外,極小線性碼在秘密共享方案和兩方安全計(jì)算中扮演著必不可少的角色.

1972年,Baumert等[5]首次提出了基于定義集設(shè)計(jì)具有較低重量的線性碼的方法.2007年,丁存生等[6-7]提出選擇恰當(dāng)?shù)亩x集可以構(gòu)造出一些較低重量的線性碼.2016年,丁存生[8]通過(guò)選取合適的定義集,提出了利用布爾函數(shù)的Walsh譜值分布構(gòu)造多類二元線性碼的方法.2018年,Chang等[9]提出了一類不滿足Ashikhmin-Barg條件的極小二元線性碼.同年,衡子靈等[10]構(gòu)造了一類不滿足Ashikhmin-Barg條件的無(wú)限族極小三元線性碼,并給出了判斷極小線性碼的充要條件.隨后,丁存生等[11]給出了另一種判斷極小二元線性碼的充要條件,并構(gòu)造了三類不滿足Ashikhmin-Barg條件的極小二元線性碼,同時(shí)確定了這些碼的重量分布.2019年,許廣魁等[12]研究了奇數(shù)域上的極小線性碼.之后,Bartoli等[13]將文獻(xiàn)[11]中的第三類極小線性碼從二元推廣到特征為奇數(shù)的情況.2020年,Bonini等[14]利用文獻(xiàn)[9]中的方法構(gòu)造了許多極小二元線性碼.同年,受文獻(xiàn)[11]和[12]的啟發(fā),Mesnager在文獻(xiàn)[15]中利用特征函數(shù)構(gòu)造了多類極小線性碼.

(1)

其中〈r,x〉是r和x的內(nèi)積.即若設(shè)

則有

(2)

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

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,…,an)的支撐集定義為

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

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

wt(a)=|Suppt(a)|.

下面的引理中給出了利用重量分布判定線性碼是極小線性碼的一個(gè)充分條件.

引理1[16](Ashikhmin-Barg條件)如果Fp上的線性碼C的最大漢明重量wmax和最小漢明重量wmin滿足

那么碼C是極小碼.

一般地,稱滿足Ashikhmin-Barg條件的極小碼為窄極小碼,而其他的極小碼稱為寬極小碼.自2018年以來(lái),有關(guān)寬極小碼的研究受到學(xué)者們的廣泛關(guān)注.

(3)

(4)

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

在這一部分,利用特征函數(shù)來(lái)構(gòu)造滿足式(1)的極小線性碼.對(duì)給定的集合S,|S|表示S中所含元素的個(gè)數(shù).

(5)

(6)

其中t=wt(r).

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

(7)

(8)

所以

(9)

(10)

定理得證.

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

接下來(lái)的引理可用于證明CD是極小線性碼.

定理2式(1)中定義的線性碼CD是一個(gè)極小線性碼.

定義

由定理1證明中的式(7)和(8)可知,

下證|{x∈D:〈r2,x〉≠0,〈r1,x〉=0}|>0.

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是極小線性碼.

進(jìn)一步,由定理2以及對(duì)p和m的范圍進(jìn)行討論,可得如下定理.

定理3符號(hào)定義如上,

(1)當(dāng)p=2且m≥7時(shí),有

則式(1)中定義的線性碼CD是寬極小碼.

(2)當(dāng)p為奇素?cái)?shù)且m≥3時(shí),有

則式(1)中定義的線性碼CD是寬極小碼.

證明由引理3可知,cr的重量取決于wt(r).從而由式(10)可知,

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

(2)首先證w1

因?yàn)閜為奇素?cái)?shù),所以只需證

(p-2)m2-(3p-4)m+2(p-1)>0.

令

h1(x)=(p-2)x2-(3p-4)x+2(p-1),

顯然h1(4)≥0,h1(x)的對(duì)稱軸為

所以,當(dāng)x≥3時(shí)h1(x)關(guān)于素?cái)?shù)p單調(diào)遞增且均為正值.因此,對(duì)所有奇素?cái)?shù)p和整數(shù)m≥3有w1

不妨設(shè)

h2(x,m)=(m-1)(m-2)x2- (m-1)(3m-2)x+2m(m-1),

又由引理1可知,在給定參數(shù)(p,m)對(duì)的取值情形下,CD是寬極小碼.

注記

①若p=2且m=3時(shí),CD是常重碼.

②若p=2且m=4,5,6時(shí),CD是滿足Ashikhmin-Barg條件的窄極小碼.

③若p≥3且m=3時(shí),CD是不滿足Ashikhmin-Barg條件的寬極小碼.

3 結(jié)語(yǔ)

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