一類基于特征函數構造的極小線性碼

胡金霞，金文剛，王天心

(西北師范大學 數學與統計學院, 甘肅 蘭州 730070)

0 引言

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

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

(1)

其中〈r,x〉是r和x的內積.即若設

則有

(2)

1 預備知識

Fp上n維空間的一個k維子空間稱為碼長為n、維數為k的[n,k,d]線性碼C,其中最小漢明距離為d,C中的每一個向量稱為碼字.設Ai表示C中漢明重量為i的碼字的個數,1+A1z+A2z2+…+Anzn定義為碼C的重量計數器,序列(1,A1,…,An)稱為碼C的重量分布.若在A1,A2,…,An中,使得Ai≠0(1≤i≤n)的個數為t,則稱碼C為t重碼.C中碼字a=(a1,…,an)的支撐集定義為

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

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

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

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

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

那么碼C是極小碼.

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

(3)

(4)

2 極小線性碼的構造

在這一部分,利用特征函數來構造滿足式(1)的極小線性碼.對給定的集合S,|S|表示S中所含元素的個數.

(5)

(6)

其中t=wt(r).

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

(7)

(8)

所以

(9)

(10)

定理得證.

顯然,wt(cr)取決于wt(r).所以,當給定p和m時,可以確定碼CD的wmin和wmax的值.可以看出,對任意的奇素數p及正整數m≥4,所構造的碼CD至多為m重的.

接下來的引理可用于證明CD是極小線性碼.

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

定義

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

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

定理3符號定義如上,

(1)當p=2且m≥7時,有

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

(2)當p為奇素數且m≥3時,有

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

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

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

(2)首先證w1

因為p為奇素數,所以只需證

(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)的對稱軸為

所以,當x≥3時h1(x)關于素數p單調遞增且均為正值.因此,對所有奇素數p和整數m≥3有w1

不妨設

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

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

注記

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

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

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

3 結語

該文在文獻[15]的基礎上,基于特征函數構造極小線性碼的方法,通過選取適當的定義集,構造了一類不滿足Ashikhmin-Barg條件的低重極小線性碼.結果表明,得到的線性碼均為極小線性碼,且除個別參數下為窄極小碼外,其余所得的線性碼均為寬極小碼,可用作設計具有良好訪問結構的秘密共享方案.