一類非二元循環(huán)碼的重量分布

李 夢, 劉 麗, 謝賢紅

(1.合肥工業(yè)大學 數(shù)學學院,安徽 合肥 230601; 2.中國科學技術(shù)大學 網(wǎng)絡(luò)空間安全學院,安徽 合肥 230026)

循環(huán)碼是線性碼的子類,具有有效的編碼和解碼算法特性,可以應用到消費電子產(chǎn)品,數(shù)據(jù)存儲系統(tǒng)和通信系統(tǒng)中;同時,少重量的線性碼在密鑰共享方案[1]和認證碼[2]中應用廣泛。因此,研究線性碼的重量分布理論具有重要的基礎(chǔ)理論意義。

(1) 碼的重量分布是計算錯誤檢測和糾正概率的主要依據(jù)。

(2) 重量分布是研究碼結(jié)構(gòu)的主要工具,可以通過改進碼字的內(nèi)在關(guān)系尋找新的好碼。

近年來,由于計算循環(huán)碼的重量分布的困難性,只能得到少數(shù)滿足特殊情況的循環(huán)碼的重量分布。

文獻[3]得到了2類循環(huán)碼,可用于密鑰共享方案,本文將進一步進行這方面的研究。

此時,p-分圓陪集Ct={t,tp,tp2,…,tpm-1}模q-1的階等于m、π-1和π-t在Fp上的極小多項式的次數(shù)相同。定義循環(huán)碼為:

由Delsarte定理[4]可知,碼C的維數(shù)為2m。碼字c(α,β)=(c0,c1,…,cn-1)的Hamming重量為:

WH(c(α,β))=|{i|0≤i≤n-1,ci≠0}|=

(1)

顯然,可以通過計算指數(shù)和S(α,β)的值分布來確定循環(huán)碼C的重量分布。當p≡3(mod 4)時,文獻[5]計算出S(α,β)的值分布,從而確定了這類循環(huán)碼的重量分布。本文將解決p≡1(mod 4)的情形,為此，以下總是假設(shè)p≡1(mod 4)。

本文確定了碼C在e為奇數(shù)和偶數(shù)2種情況下的重量分布，并通過對碼C的碼字進行截斷得到了另一類循環(huán)碼。

1 預備知識

當e、m都為偶數(shù)時,任取Fp中的元素a,有at=a;當e,m都為奇數(shù)時,無法得出at=a。故對于Fp中的平方元a,可得at=a。

引理1 令F表示域Fq,則F2=Fpe+1,且F=Fpe+1∪λFpe+1。

設(shè)x∈F,由xpm=x可得:

根據(jù)λ的性質(zhì),可得F=Fpe+1∪λFpe+1。

(2)

為了計算S(α,β)的值分布,需要確定指數(shù)和T(α,β),以下簡要介紹有限域上的二次型的相關(guān)知識。

引理2[3]定義一個Fq到Fq0的函數(shù):

則Q(α,β)(x)是Fq0上的二次型,且

其中,rα,β為Q(α,β)(x)的秩;ζp為p次本原單位根;η0為Fq0的二次乘法特征,即

(1)rα,β=s,s-1或s-2;

m1=(pm-1)pm-e,

m0=p2m-1-m1-m2。

結(jié)合引理2和引理3,定義以下2個常量:

對ν=±1,i∈{0,1,2},假設(shè)

mν,i=|Vν,i|,則Vi=V-1,i+V1,i且mi=m1,i+m-1,i。

表1 m/e為奇數(shù),ν=±1時T(α,β)的值分布

最后介紹分圓域Q(ζp)的伽羅瓦群的性質(zhì)。

2 循環(huán)碼C的重量分布

2.1 e為奇數(shù)時C的重量分布

表2 e、m/e為奇數(shù)時循環(huán)碼C的重量分布

證明由引理6及(1)式、(2)式可知:

結(jié)合引理4和引理5得循環(huán)碼C的重量分布。

以下推論僅給出e是奇數(shù)時碼C的性質(zhì)。

推論1 設(shè)wmax和wmin分別表示碼C的極大重量和極小重量,則有:

故碼C可用于構(gòu)造密鑰共享方案和認證碼[1]。

例1 令p=5,m=3,e=1,C是F5上[124,6,90]循環(huán)碼,經(jīng)計算得其重量計數(shù)器為:

1+3 270x90+9 424x100+2 480x110。

C′={c′(α,β)|α,β∈Fq}。

表3 e、m/e均為奇數(shù)時線性碼C′的重量分布

例2令p=5,m=3,e=1,則C′是F5上[62,6,45]線性碼,經(jīng)計算得其重量計數(shù)器為:

1+3 270x45+9 424x50+2 480x55。

2.2 e為偶數(shù)時C的重量分布

下面利用文獻[9]中的方法給出S(α,β)滿足的恒等式。觀察可得:

其中

由t是奇數(shù)可得(-1)t=-1,因此Ω1=pm。同時,

其中,Ω2表示下列方程組

(3)

引理7 令e為偶數(shù),則下列等式成立:

(4)

(5)

且

(1) 若b1為平方元,則

T2(a1,b1)=

(2) 若b1為非平方元,則

T2(a1,b1)=

證明證明分成以下幾種情況:

(1)a1=b1=0時,T2(0,0)=Ω1。

(2)a1≠0,b1=0時，由(6)式中的第2個等式可得x=-z,從而有a1=0,產(chǎn)生矛盾,因此T2(a1,0)=0。

(3)a1≠0,b1≠0時，實際上,這種情況很難直接計算,但可以根據(jù)(5)式中x與z的平方性分為以下4種情況來討論:

情況1x與z皆為平方元;

情況2x和z皆為非平方元或0;

情況3x為平方元,z為非平方元;

情況4x為非平方元,z為平方元。

現(xiàn)依次討論每個情況對應T2(a1,b1)的值。

情況1x與z皆為平方元。

(6)

(1) 若b1是一個平方元,則

T2′=

(2) 若b1是一個非平方元,則

T2′=

證明設(shè)(x1,z1)為(6)式中第2個方程的解,顯然x1≠z1,不妨假設(shè):

(7)

(8)

w2-2vw+1=0

(9)

(10)

則(6)式可整理為:

(11)

即T2′為(11)式的解。

接下來，討論T2′的值。

(12)

(13)

(14)

(15)

令Γ1和Γ2分別表示(14)式和(15)式關(guān)于θ在Fq2中的解集；顯然Γ1∩Γ2=?，且(11)式的解集等于Γ1∪Γ2。易見θ是(14)式的解當且僅當θ-1是(15)的解,故|Γ1|=|Γ2|,且(9)式的非零解成對出現(xiàn)。

當(11)式有解時,求|Γ1|。設(shè)θ1、θ2為(14)式的2個非零解,則

因為gcd(pe-1,q-1)=pe-1,|Γ1|=pe-1,所以(11)式關(guān)于θ在Fq2中有2(pe-1)個非零解。

若T2′=2(pe-1),則可得:

(pe-1)+2(pe-1)T=q-1。

類似可得b1是非平方元的結(jié)論。

(1) 若b1是一個平方元,則

T2″=

(2) 若b1是一個非平方元,則

T2″=

證明以下考慮(6)式解的情況。若(x1,z1)是(6)式的解,則(-x1,z1)、(-x1,-z1)及(x1,-z1)也是(6)式的解。

若x1z1≠0,則(6)式恰有4個不同的解,但只作為(5)式的1個解存在。

T2″=T2′=

情況2x和z皆為非平方元或0。

(1) 若b1是一個平方元,則

T3″=

(2) 若b1是一個非平方元,則

T3″=

證明該證明與情況1的證明類似,此處省略。

情況3x為平方元,z為非平方元。

(16)

引理12 令T4′表示(16)式解的個數(shù),則

T4′=

證明設(shè)(x1,z1)為(16)式中第2個方程的解,顯然x1≠z1,不妨假設(shè)

(17)

以下證明步驟與引理9類似,此處省略。

T4″=

證明考慮(16)式解的情況。若(x1,z1)是(16)式的解,則(-x1,z1),(-x1,-z1)及(x1,-z1)也是(16)式的解。

若x1z1≠0,則(15)式恰有4個不同的解,但只作為(5)式的1個解存在。

T4″=T4′=

情況4x為非平方元,z為平方元。

引理14 令T5″表示(5)式關(guān)于(x,z)的解的個數(shù)(其中,z是一個平方元、x是一個非平方元或x=0),則

T5″=

證明情況4與情況3對稱,證明略。

由引理10、引理11、引理13和引理14可得引理8。

表5 e為偶數(shù)、m/e為奇數(shù),ν=±1時循環(huán)碼C的重量分布

證明首先計算指數(shù)和S(α,β)的重量分布。

對ν,μ=±1,0≤i,j≤2,定義以下常量:

Vν,μ,i,j={(α,β)|(α,β)∈Vν,i,

(-λα,λβ)∈Vμ,j},

mν,μ,i,j=|Vν,μ,i,j|。

由引理5的證明可知,當i、j非零時,mν,μ,i,j=0。由T(α,β)和T(-λα,λβ)的對稱性可知mν,μ,i,j=mμ,ν,j,i,因此只需計算mν,μ,i,:=mν,μ,i,0即可。

由引理3和引理4,有

m1,1,0+m-1,1,0+m1,1,1+m-1,1,1+

m1,1,2+m-1,1,2=m1,0

(18)

m1,-1,0+m-1,-1,0+m1,-1,1+m-1,-1,1+

m1,-1,2+m-1,-1,2=m-1,0

(19)

結(jié)合(2)式和引理3,有

m1,1,1+m1,-1,1=m1,1

(20)

m-1,1,1+m-1,-1,1=m-1,1

(21)

m1,1,2+m1,-1,2=m1,2

(22)

m-1,1,2+m-1,-1,2=m-1,2

(23)

T(λα,λβ)=η0(λ)rα,βT(α,β)。

對奇數(shù)s,當rα,β=s或s-2,η0(λ)=-1時,

T(λα,λβ)=-T(α,β)

(24)

由(24)式知,存在一個一一映射，即

V-1,1,1,0→V-1,-1,1,0,

由此可得m-1,1,1=m-1,-1,1。

類似可得下列等式成立,

m1,1,1=m1,-1,1,m1,1,2=m-1,-1,2,

m-1,1,2=m1,-1,2,m1,1,0=m-1,-1,0,

m1,-1,0=m-1,1,0。

結(jié)合引理7、(10)～(15)式、(20)式及(21)式,易得:

(2m1,-1,2+2m-1,1,2)+p4m=

求解由(10)～(17)式、(18)式及(20)～(23)式構(gòu)成的方程組,可得到S(α,β)的值分布。

WH(c(α,β))=pm-1(p-1)-

其中,ν,μ∈{±1};0≤i,j≤2。由此可得e為偶數(shù)時循環(huán)碼C的重量分布。

例3 令p=5,m=6,e=2,C是F5上[15 624,12,11 300]循環(huán)碼,得其重量計數(shù)器為:

1+5 077 800x12 200+5 077 800x12 300+

4 687 200x12 700+4 687 200x12 800+

15 624x11 300+15 624x13 700+

56 340 144x12 400+56 340 144x12 600+

111 899 088x12 500。

在偶數(shù)的情況下,表5中碼C中的所有非零碼字都有公因子p-1,可以推導出πn′t=πn′=π1,這意味著碼C的任何碼字c(α,β)都可以用c′(α,β)表示:

WH(c′(α,β))=WH(c(α,β))/(p-1)。

表6 e為偶數(shù)、m/e為奇數(shù),ν=±1時線性碼C′的重量分布

表6中w為C′中碼字的重量；Aw為C′中重量為w的碼字個數(shù)。

例4令p=5,m=6,e=2,C′是F5上[3 906,122 825]線性碼,計算得重量計數(shù)器為:

1+5 077 800x3 050+5 077 800x3 076+

4 687 200x3 175+4 687 200x3 200+15 624x2 825。

3 結(jié) 論

本文給出了一類對偶碼含2個重點的非二元循環(huán)碼的重量分布，并利用magma程序驗證了結(jié)果的正確性?？梢钥闯觯玫降木€性碼為少重量的，可應用于密鑰共享方案。進一步的研究將會尋找更一般的函數(shù)，從而構(gòu)造出性能更好的線性碼，并給出一般表達式。