兩個奇質數乘積長度的二元二次剩余碼的冪等生成元

劉淵博, 廖群英

(四川師范大學 數學科學學院, 四川 成都 610066)

1 準備知識

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

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

2 相關引理

d=

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

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

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

degg(x)≤n-1,

引理 2.1[6]設f(x)∈Fl[x]且循環碼C=〈g(x)〉,則f(x)是C的生成元當且僅當

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

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

取l=2,設n=pq,其中p,q為兩個不同的奇質數,θ是Ω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},

則

最后,對j,m∈{1,2},設

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]設p,q≡±1 (mod8).對0,1,2∈{1,-1}以及m=1,2,稱循環碼

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

或

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

為二元二次剩余碼.

注 2.1當m=1,2時,分別為文獻[12]的第二、三種構造,且這樣的二元二次剩余碼共有32個.

對j,m∈{1,2},設

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中的二元二次剩余碼.

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

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

表1 冪等元

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

2) 當s∈A1時

3) 當s∈A2時

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

引理 2.3設p、q為不同的奇質數,θ為Ω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}.

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

由引理2.1得

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

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

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

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

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

C的生成多項式與冪等生成元的對應關系如表2所示.

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

其次,由定理3.1得到

的冪等生成元,即結論如下.

定理 3.2對設

4 定理的證明

定理 3.1的證明因為

q≡p≡±1 (mod8),

所以

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

由引理2.2可得

同時

又由引理2.2得結果如表3所示.

表3 冪等元的值

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

gcd

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

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

當且僅當

又

故

gcd

同理

gcd

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

5 實例

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

首先,設

其中

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}.

其次,設

{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,