一類三重或四重線性碼的構造*

薛文芳，王維瓊，李亞偉

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

1 引言

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

1+A1z+A2z2+…+Anzn

(1)

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

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

?x∈Fq}

(2)

受文獻[14]的啟發，本文基于布爾函數構造出了一類二元三重或四重線性碼，給出了碼的參數和重量分布，所構造出的線性碼的對偶碼均為關于Sphere-packing界的最優碼或幾乎最優碼。

2 預備知識

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

設p為素數，m為正整數，q=pm，Fq表示具有q個元素的有限域。

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

(3)

其中，s為m的正因子。

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

(4)

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

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

(5)

(6)

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

(7)

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

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

(8)

特別地，當a=1時，有:

(9)

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

(10)

①若a?〈α2l+1〉，則f(x)為Fq上的置換多項式。設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布爾函數f:F2m→F2的Walsh變換定義為：

(13)

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

(14)

稱碼C滿足Sphere-packing界。

3 主要結果及證明

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

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

(15)

證畢。

□

(16)

中零碼元的個數，則：

(17)

(18)

其中，

證畢。

□

本節后面內容考慮以D為定義集的線性碼CD。

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

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

(19)

(20)

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

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

由于零碼字出現了2次，故線性碼的維數k=m-1。

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

(26)

解此方程組有：

(27)

證畢。

□

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

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 結束語

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

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

wmin/wmax>(p-1)/p

(28)