一類三重或四重線性碼的構(gòu)造*

薛文芳，王維瓊，李亞偉

(長安大學(xué)理學(xué)院，陜西 西安 710064)

1 引言

設(shè)p為素數(shù)，m為正整數(shù)，q=pm，F(xiàn)q表示具有q個元素的有限域。Fp上的一個[n,k,d]線性碼C為Fp上n維向量空間的一個k維子空間，其中d為碼C的極小漢明距離，它刻畫了線性碼C的檢錯與糾錯能力。線性碼C的重量計數(shù)器可表示為：

1+A1z+A2z2+…+Anzn

(1)

其中，Ai為線性碼C中漢明重量為i的碼字的個數(shù)。若|{Ai|Ai≠0,1≤i≤n}|=t，則稱線性碼C為t重線性碼。對于一個參數(shù)為[n,k,d]的線性碼C，若參數(shù)為[n,k,d+1]的線性碼不存在，則稱線性碼C為最優(yōu)碼。若參數(shù)為[n,k,d+1]的線性碼C最優(yōu)，則稱參數(shù)為[n,k,d]的線性碼C為幾乎最優(yōu)碼。較少重量的線性碼可用于構(gòu)造秘密共享方案、認(rèn)證碼、結(jié)合方案及強正則圖等。

2007年，Ding等[1]利用有限域上的跡函數(shù)提出了一種構(gòu)造線性碼的一般方法。有限域Fp上長度為n的線性碼C可由式(2)給出:

?x∈Fq}

(2)

受文獻(xiàn)[14]的啟發(fā)，本文基于布爾函數(shù)構(gòu)造出了一類二元三重或四重線性碼，給出了碼的參數(shù)和重量分布，所構(gòu)造出的線性碼的對偶碼均為關(guān)于Sphere-packing界的最優(yōu)碼或幾乎最優(yōu)碼。

2 預(yù)備知識

本節(jié)給出第3節(jié)中需要用到的一些定義和引理。

設(shè)p為素數(shù)，m為正整數(shù)，q=pm，F(xiàn)q表示具有q個元素的有限域。

定義1[15]有限域Fpm到Fps的跡函數(shù)定義為：

(3)

其中，s為m的正因子。

定義2[15]對?a∈Fq，有限域Fq上的加法特征定義為：

(4)

其中，x∈Fq，ζp為有限域Fp上的m階本原單位根。

若a=1，稱χ1為有限域Fq上的典范加法特征。顯然χa(x)=χ1(ax)。有限域Fq上加法特征具有如下正交關(guān)系：

(5)

(6)

特別地，當(dāng)p=2時，對?a,b∈F2m，令f(x)=ax2h+1+bx，其中正整數(shù)h滿足1≤h

(7)

引理2[16]若m/l為奇數(shù)，則:

Sh(a,b)=Sh(1,bc-1)

(8)

特別地，當(dāng)a=1時，有:

(9)

引理3[16]設(shè)e為正整數(shù)，若偶數(shù)m=2e，且m/l為偶數(shù)，則:

(10)

①若a?〈α2l+1〉，則f(x)為Fq上的置換多項式。設(shè)x0為f(x)=b2h在F2m上的唯一解，則:

(11)

②若a∈〈α2l+1〉，且f(x)=b2h在F2m上無解，則Sh(a,b)=0。若a∈〈α2l+1〉，且f(x)=b2h在F2m上有解，記x0為其中一個解，則:

(12)

定義3布爾函數(shù)f:F2m→F2的Walsh變換定義為：

(13)

定義4[17]設(shè)K為有限域Fp上(n,K,d)碼C中碼字的個數(shù)，若：

(14)

稱碼C滿足Sphere-packing界。

3 主要結(jié)果及證明

證明由Walsh變換的定義，有：

n=|{x∈F2m|g(x)=1,g(x+α)=0}|=

(15)

證畢。

□

(16)

中零碼元的個數(shù)，則：

(17)

(18)

其中，

證畢。

□

本節(jié)后面內(nèi)容考慮以D為定義集的線性碼CD。

首先給出g(x)和F(x)的Walsh變換。

引理6g(x)的Walsh變換滿足:

(19)

(20)

引理6的結(jié)論的證明可由Walsh變換的定義、引理2和引理3的結(jié)論得出。

(21)

證明由Walsh變換的定義和引理1得：

(22)

(23)

證畢。

□

Table 1 Weight distribution of code CDin theorem 1表1 定理1中碼CD的重量分布

證明由引理4和引理7知線性碼CD的碼長n=2m-2。

(24)

w1=2m-3,

(25)

由于零碼字出現(xiàn)了2次，故線性碼的維數(shù)k=m-1。

若記線性碼CD的非零重量wi對應(yīng)的頻數(shù)為Ai(1≤i≤3)，則根據(jù)MacWilliams方程[18]可得：

(26)

解此方程組有：

(27)

證畢。

□

類似定理1中的方法，可得如下結(jié)論。

Table 2 Weight distribution of code CDin theorem 2表2 定理2中碼CD的重量分布

Table 3 Weight distribution of code CDin theorem 3表3 定理3中碼CD的重量分布

Table 4 Weight distribution of code CDin theorem 4表4 定理4中碼CD的重量分布

4 結(jié)束語

本文利用定義集的方法構(gòu)造出了一類三重或四重線性碼，確定了這些碼的參數(shù)、重量分布和對偶距離，并編寫Magma程序驗證了所得結(jié)論。

根據(jù)文獻(xiàn)[3]中的引理13和定理12，若線性碼中非零碼字的最小重量wmin和最大重量wmax滿足關(guān)系式：

wmin/wmax>(p-1)/p

(28)