兩個(gè)奇質(zhì)數(shù)乘積長(zhǎng)度的二元二次剩余碼的冪等生成元

劉淵博, 廖群英

(四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 四川 成都 610066)

1 準(zhǔn)備知識(shí)

二次剩余碼是碼率接近1/2的循環(huán)碼,因其良好的性質(zhì)被廣泛地研究和應(yīng)用.早在1958年,Prange[1]基于循環(huán)碼的代數(shù)性質(zhì)提出了有限域上碼長(zhǎng)為奇質(zhì)數(shù)的二次剩余碼的概念.二次剩余具有較大的最小距離,所以它有非常好的糾錯(cuò)能力[2-3],從而廣泛應(yīng)用于網(wǎng)絡(luò)傳輸、衛(wèi)星通信、信息儲(chǔ)存以及圖像的信息隱藏等技術(shù)[4-5].二次剩余碼在理論方面有豐富的研究結(jié)果.特別地,其冪等生成元可用于研究最小距離下界和譯碼算法,所以成為最重要的研究問題之一[3,6-7].Macwilliams等[3,8]給出了有限域上碼長(zhǎng)為奇質(zhì)數(shù)的二次剩余碼的冪等生成元,進(jìn)而在1978年又進(jìn)一步研究了擴(kuò)充二次剩余碼的冪等生成元.2005年,Semyonovykh[9]將碼長(zhǎng)為奇質(zhì)數(shù)的二元二次剩余碼的概念推廣到高次剩余碼,考慮了三次和四次剩余碼的冪等生成元.

近年來(lái),有限域上碼長(zhǎng)為奇質(zhì)數(shù)的二次剩余碼有了進(jìn)一步的推廣,相應(yīng)的冪等生成元也有豐富的結(jié)果.首先,在構(gòu)造方法上,Charters[10]于2009年將經(jīng)典的碼長(zhǎng)為奇質(zhì)數(shù)的二元二次剩余碼推廣到p元域上的p次剩余碼,并利用構(gòu)造出的冪等生成元給出其中一些碼的最小距離的下界,其中p為奇素?cái)?shù).另外,Zanten等[11]在2015年構(gòu)造了有限域上碼長(zhǎng)為n的t次剩余碼,并給出了這些碼的冪等生成元,其中t為大于1的正整數(shù),n∈{2,4,pλ,2pλ|λ≥1}.其次,在碼長(zhǎng)方面,Ding[12]在2012年構(gòu)造了有限域Fl上碼長(zhǎng)為n=pq的二次剩余碼.特別地,得到二元二次剩余碼、三元二次剩余碼以及四元二次剩余碼的具體構(gòu)造,而且進(jìn)一步得到這些碼的最小odd-like權(quán)重的下界,其中p、q為奇質(zhì)數(shù)且勒讓德符號(hào)[5]

2 相關(guān)引理

d=

故可記C=[n,k,d]l.特別地,若線性碼C滿足:對(duì)任意c=(c0,c1,…,cn-1)∈C,C的循環(huán)移位(cn-1,c0,c1,…,cn-2)∈C,則稱C為循環(huán)碼.循環(huán)碼作為一類特殊的線性碼,有非常好的代數(shù)結(jié)構(gòu),因任意碼字c=(c0,c1,…,cn-1)可寫成多項(xiàng)式

c(x)=c0+c1x+…+cn-1xn-1∈

R=Fl[x]/(xn-1).

degg(x)≤n-1,

引理 2.1[6]設(shè)f(x)∈Fl[x]且循環(huán)碼C=〈g(x)〉,則f(x)是C的生成元當(dāng)且僅當(dāng)

gcd(f(x),xn-1)=g(x).

特別地,若C=〈e(x)〉且在R中e2(x)=e(x),則稱e(x)為C的冪等生成元.

取l=2,設(shè)n=pq,其中p,q為兩個(gè)不同的奇質(zhì)數(shù),θ是Ω2中的n次本原單位根.

A0={i|gcd(i,n)=1,i∈A},

A1={i|gcd(i,n)=p,i∈A},

A2={i|gcd(i,n)=q,i∈A},

則

x

A},

A},

則

最后,對(duì)j,m∈{1,2},設(shè)

Fj=±1,

(1)

以及

Fm0=±1,

(2)

則以下有兩種分解

x

F1,-1(x)F2,1(x)F2,-1(x)

或

x

F1,-1(x)F2,1(x)F2,-1(x).

定義 2.1[12]設(shè)p,q≡±1 (mod8).對(duì)0,1,2∈{1,-1}以及m=1,2,稱循環(huán)碼

C=〈Fm0,0(x)F1,1(x)F2,2(x)〉

或

C=〈(x-1)Fm0,0(x)F1,1(x)F2,2(x)〉

為二元二次剩余碼.

注 2.1當(dāng)m=1,2時(shí),分別為文獻(xiàn)[12]的第二、三種構(gòu)造,且這樣的二元二次剩余碼共有32個(gè).

對(duì)j,m∈{1,2},設(shè)

Ej=±1,

以及

E0=±1.

記

Em0,1,2(x)=Em0,0(x)+E1,1(x)+E2,2(x),

以及

gm0,1,2(x)=Fm0,0(x)F1,1(x)F2,2(x),

則

C=〈gm0,1,2(x)〉

或者

C=〈(x-1)gm0,1,2(x)〉,

即為定義2.1中的二元二次剩余碼.

在討論冪等生成元之前,先引入兩個(gè)引理.

引理 2.2設(shè)p,q為不同的奇質(zhì)數(shù),θ為Ω2中的pq次本原單位根.對(duì)s∈{1,2,…,pq-1}及和E(θs)有如表1的結(jié)果.

表1 冪等元

證明要證明引理2.2,只需證明表1中第二列的情形其中s∈{1,2,…,pq-1},其他情形的證明類似.

2) 當(dāng)s∈A1時(shí)

3) 當(dāng)s∈A2時(shí)

這就完成了引理2.2的證明.

引理 2.3設(shè)p、q為不同的奇質(zhì)數(shù),θ為Ω2中的pq次本原單位根.若

E1,1(θ)=E2,1(θ)=0,

則

證明

這就完成了引理2.3的證明.

注 2.2在引理2.3中,滿足

E1,1(θ)=E2,1(θ)=0

(E1,1(θ))2=E1,1(θ)

且

(E2,1(θ))2=E2,1(θ).

E1,1(θ)=a,E2,1(θ)=b,a,b∈{0,1}.

由中國(guó)剩余定理得,存在s∈A0滿足

由引理2.1得

E1,1(θs)=E2,1(θs)=0.

3 二元二次剩余碼的冪等生成元

下面給出定義2.1中相應(yīng)的二元二次剩余碼的冪等生成元.

定理 3.1對(duì)0,1,2∈{1,-1}以及m=1,2,則為冪等元且碼

C=〈Em0,1,2(x)〉，

C的生成多項(xiàng)式與冪等生成元的對(duì)應(yīng)關(guān)系如表2所示.

表2 二次剩余碼的冪等生成元

其次,由定理3.1得到

的冪等生成元,即結(jié)論如下.

定理 3.2對(duì)設(shè)

4 定理的證明

定理 3.1的證明因?yàn)?/p>

q≡p≡±1 (mod8),

所以

E1,1(θ)=E2,1(θ)=0.

由引理2.2可得

同時(shí)

又由引理2.2得結(jié)果如表3所示.

表3 冪等元的值

要證明表3,只需證明第一項(xiàng),其他項(xiàng)類似.當(dāng)q≡1 (mod8)且p≡-1 (mod8)時(shí),θs為的根當(dāng)且僅當(dāng)因此

gcd

這就完成了定理3.1的證明.

定理 3.2的證明對(duì)任意的首先,s任取s∈{0,1,…,n-1},則

當(dāng)且僅當(dāng)

又

故

gcd

同理

gcd

這就完成了定理3.2的證明.

5 實(shí)例

對(duì)文獻(xiàn)[12]例4和例7中的二元二次剩余碼[119,60],下面給出它們的冪等生成元.

首先,設(shè)

其中

A0={i|gcd(i,119)=1,1≤i≤118},

A1={i|gcd(i,119)=7,1≤i≤118}=

{7,14,21,…,112},

A2={i|gcd(i,119)=17,1≤i≤118}=

{17,34,51,68,85,102}.

其次,設(shè)

{1,2,4,8,9,11,15,16,18,22,23,25,29,30,

32,36,37,39,43,44,46,50,53,57,58,60,64,

65,67,71,72,74,78,79,81,86,88,92,93,95,

99,100,106,107,109,113,114,116},

{3,5,6,10,12,13,19,20,24,26,27,31,33,

34,38,40,41,45,47,48,52,54,55,59,61,62,

66,69,73,75,76,80,82,83,87,89,90,94,96,

97,101,103,104,108,110,111,115,117,118},

{1,2,4,8,9,13,15,16,18,19,25,26,30,

32,33,38,43,47,50,52,53,55,59,60,64,

66,67,69,72,76,81,83,86,87,89,93,94,

100,101,103,104,106,110,111,115,117,118},

{3,5,6,10,11,12,20,22,23,24,27,29,31,

36,37,39,40,41,44,45,46,48,54,57,58,61,

62,65,71,73,74,75,78,79,80,82,88,90,92,

95,96,97,99,107,108,109,113,114,116},

A1,1={7,14,28,56,63,91,105,112},

A1,-1={21,35,42,49,70,77,84,98},

A2,1={51,85,102},

A2,-1={17,34,68}.

其中

F2,1(x)=x3+x+1,

F2,-1(x)=x3+x2+1,

F1,1(x)=x8+x7+x6+x4+x2+x+1,

F1,-1(x)=x8+x5+x4+x3+1,

x31+x30+x28+x27+x26+x25+

x24+x23+x22+x21+x20+x18+

x17+x9+x8+x6+x3+x+1,

x39+x38+x337+x36+x35+x34+

x32+x30+x29+x27+x26+x24+

x22+x21+x19+x18+x16+x14+

x13+x12+x11+x10+x9+x7+

x6+x5+x4+x3+1.

表4 二次剩余碼[119,60]的冪等生成元

Em

和

Em0,1,2(x)+1,