二元廣義反碼與最優(yōu)LCD碼

李瑞虎, 付 強, 宋 昊, 劉 楊

(空軍工程大學基礎部,西安,710051)

二元反碼是由Farrell[1]首先提出的,反碼在小碼長最優(yōu)碼構造和局部修復碼研究方面得到廣泛應用[2-3]。近年來,人們證明線性補對偶(linear complementary dual,LCD)碼能夠用于經(jīng)典與量子信息保護、防止側信道攻擊[3-5],從而掀起研究LCD碼的熱潮[5-15]。研究一般碼長的LCD碼時,用組合構造、計算機輔助搜索和解方程等方法確定出一些小碼長(n≤40)最優(yōu)LCD碼以及維數(shù)k≤4的LCD碼,但是卻難以確定碼長超過40的最優(yōu)LCD碼以及維數(shù)更大的最優(yōu)LCD碼[6-14]。為突破現(xiàn)有方法的局限性,借鑒文獻[17～19]中線性碼的定義向量(defining vector)理論,本文引入廣義反碼及其定義向量、定義向量的重復度概念,確立廣義反碼、其參數(shù)與定義向量之間的聯(lián)系。利用廣義反碼描述任意碼長線性碼的參數(shù),將確定任意碼長線性碼的參數(shù)問題轉化為確定小碼長廣義反碼問題。

設Nm=2m-1, 關于二元最優(yōu)[sNm+Nm-a,m]的LCD性,可得到如下結果:

1)m=3,且a=2時,存在二元最優(yōu)[sNm+Nm-a,m]碼為LCD碼[8-10]。

2)m=4,5,6且a=5,9時,存在二元最優(yōu)[sNm+Nm-a,m]碼為LCD碼[10-13]。

本文將利用線性碼的定義向量和廣義反碼理論,研究二元最優(yōu)[sNm+Nm-a,m]的根維數(shù)以及LCD性,設法證明1≤a≤11,m適當大時, 二元最優(yōu)[sNm+Nm-a,m]線性碼不是LCD碼。

1 基本理論

本文中F2為二元域,線性碼C指二元線性碼,C的Euclid對偶表示為C⊥,定義為:

若C?C⊥,C叫做自正交 (self-orthogonal,SO) 碼。Hull(C)=C∩C⊥叫做C的根碼[3,15],又稱為C的包殼,Hull(C)的維數(shù)記為h(C)。

若Hull(C)={0}(或h(C)=0),C叫做線性補對偶碼[3]。

若[n,k,d]碼存在, 定義:

h([n,k,d])=min{h(C)∣C=[n,k,d]}。

如果存在置換將碼C變成C′,C和C′ 稱為等價碼,C?C′。若G1與G2生成等價碼, 則記為G1?G2。等價碼性能一樣,故可以不區(qū)分等價碼與置換等價的生成矩陣,將它們視作同一對象進行。

約定: 由二維Simplex 碼的生成矩陣S2結合遞歸構造方法,可構造k-維 Simplex的生成矩陣:

記αi為i(1≤i≤N=2k-1) 的二進制k-維向量表示, 即α1=(1,0,…,0)T,…,αN=(1,1,…,1)T, 則Sk=(α1,…,αN)。

記Sk的后2k-2m列(1≤m≤k-1)構成的矩陣為Mk,m,Mk,m生成Mk,m=[2k-2m,k,2k-1-2m-1] MacDonald碼[21]。

若G是C=[n,k] 的生成矩陣,G中有l(wèi)i,αi(1≤i≤N),稱L=(l1,…,lN)為G的定義向量,并記G為G=(l1α1,…,lNαN)。

設ljl(1≤l≤t)為L=(l1,l2,…,lN)的不同坐標且lj1

例如L1=(s+1,s-1,s,s,s+1,s-1,s+1) 具有類型]](s-1)2∣(s)2∣(s+1)3]],L2=(3,1,1,3,1,3,1) 具有類型]](1)4∣(3)3]]。

設Pk為Sk中全體非零向量為行的(2k-1)×(2k-1)矩陣,Jk為(2k-1)×(2k-1) 全一矩陣,Qk=Jk-Pk。線性碼C=[n,k]的距離和性質可由定義向量L=(l1,…,lN)得到。若C=[n,k]具有生成矩陣G=(l1α1,…,lNαN)和定義向量L=(l1,…,lN),WT=PkLT,則W=(w1,w2,…,wN) 對應C中2k-1個非零向量的重量,d=min1≤i≤2k-1{wi}為C最小距離[16-17]。記W=(w1,w2,…,wN)=d12k-1+Λ,其中Λ=(λ1,λ2,…,λN)且λi=wi-d≥0則至少有一個λi=0.設σ=λ1+λ2+…+λN, 則σ=2k-1n-d(2k-1) 。

可由WT=PkLT得到L=(l1,…,lN),由如下方程解出:

引理1.1設C=[n,k,d]的生成矩陣和定義向量分別為G與L,有:

1)若lmin

2) 若k≥3,則GGT=Ga(Ga)T;

3)C為LCD碼當且僅當Ga(Ga)T可逆。

證明1)從sSk中刪除G的列得到Ga,sSk生成等重碼[s(2k-1),k,s2k-1],而Ga中行的2k種線性組合向量的最大重量為δ,故d=s2k-1-δ。

GGT=Ga(Ga)T

3)C為LCD碼當且僅當GGT可逆,由(2)可得C為LCD碼當且僅當Ga(Ga)T可逆。

下文要用到C的約化碼和擴展碼的h(C)[15]。

引理1.2[15]若C1為C的約化碼,h(C1)=h≥2, 則h(C)≥h-1≥1,C不是LCD碼。

引理1.3[15]設d為奇數(shù),Ce為C=[n,k,d]的擴展碼,若h(Ce)=h≥2,則h(C)≥h-1≥1,C不是LCD碼。

本文的主要結論如下:

定理1.1設s≥0,Nk=2k-1,1≤a≤11.若(k,a)滿足條件 :①k≥4,a=1,3,4,7,8;②k≥5,a=2,6,10; ③k≥7,a=5,9,11。則相應條件下二元[sNk+Nk-a,k]最優(yōu)碼不是LCD碼。

2 定理1.1的證明

本節(jié)證明引理1.1, 分3步進行:①a=1,3,4,7,8;②a=2,6,10,11;③a=5,9。

引理2.1若s≥0,k≥4 ,Nk=2k-1且a=1,3,4,7,8,則[Nks+Nk-a,k]最優(yōu)碼不是LCD碼。

證明設a=1,3,7, 則相應有a=2r-1,其中r分別對應1,2,3。1≤r≤k-1時[18],有:

C=[sN+2k-2r,k,s2k-1+2k-1-2r-1]

唯一,C=Ms(k,r)=[sN+2k-2r,k,s2k-1+2k-1-2r-1]是s個Simplex碼與MacDonald碼的并置;故r對應為1,2,3時C的根維數(shù)h(C)分別為k-1,k-2,k。從而C不是LCD碼。

當a=4,8時,二元最優(yōu)[Nks+Nk-a,k]的距離分別為2k-1s+2k-1-3和2k-1s+2k-1-5,這時它們的擴展碼分別對應a=3,7的最優(yōu)碼。

由擴展碼的根維數(shù)可推出a=4,8, 最優(yōu)碼[Nks+Nk-a,k]的根維數(shù)分別為k-2≥2以及k,故二元最優(yōu)[Nks+Nk-a,k]是根維數(shù)不小于1的碼,不是LCD碼。

引理 2.2若k≥5,則二元最優(yōu)[Nks+Nk-2,k,2k-1s+2k-1-2]碼不是LCD碼。

證明若k≥5, 記Nk=N, 則C=[n,k,d]=[Nks+Nk-2,k,2k-1s+2k-1-2]為二元最優(yōu)碼。

對此碼有σ=2k-1n-d(2k-1)=2k-1+d,且L滿足s-1≤li≤s+2,1≤i≤N。

1)若lmax=s+2, 則C有約化碼:[Nks+Nk-4,k-1,2k-1s+2k-1-2]=[(2s+1)Nk-1+Nk-1-3,k-1,(2s+1)2k-2s+2k-2-2]

此約化碼的h≥(k-1)-2=k-3。故h(C)≥k-4。

2)若lmax=s+1且lmin=s, 則有廣義反碼(2,2k,{2}),此廣義反碼(2,2k,{2})的秩為2,因此h(C)≥k-2。

3)若lmax=s+1且lmin=s-1, 則C的定義向量L以及Lc分別具有以下形式:

L:]](s-1)1∣(s)0∣(s+1)N-1]],

從而此時C為自正交碼,h(C)≥k。

總結以上討論結果,可得到:

h([Nks+Nk-2,k,2k-1s+2k-1-2])≥k-4,引理成立。

引理2.3若k≥5,則二元最優(yōu)[Nks+Nk-6,k]碼不是LCD碼。

證明記C=[n,k,d]=[Nks+Nk-6,k,2k-1s+2k-1-4]為二元最優(yōu)碼,對此碼有σ=2k-1n-d(2k-1)=2k-1+d, 且L滿足s-1≤li≤s+2,1≤i≤N。

1)若lmax=s+2,則C有約化碼:

[Nks+Nk-8,k-1,2k-1s+2k-1-4]=

[(2s+1)Nk-1+Nk-1-7,k-1,(2s+1)2k-2s+2k-2-4]

其為自正交碼,因此h(C)≥k-2。

2)若lmax=s+1且lmin=s, 則有廣義反碼(6,2k,{4}),此廣義反碼(6,2k,{4})的秩至多為4,故h(C)≥k-4。

3)若lmax=s+1且lmin=s-1, 則C的定義向量L以及Lc分別具有形式:

①L1:]](s-1)1∣(s)4∣(s+1)N-5]],

②L2:]](s-1)2∣(s)2∣(s+1)N-4]],

③L3:]](s-1)3∣(s+1)N-3]];

以上3種定義向量L分別對應碼的h(C)值為h≥k-4,h≥k-2以及h=k。

總結以上各種情況,可得到h([Nks+Nk-6,k,2k-1s+2k-1-4])≥k-4,故引理成立。

引理2.4若k≥7,則二元最優(yōu)[Nks+Nk-5,k]碼不是LCD碼。

證明記C=[n,k,d]=[Nks+Nk-5,k,2k-1s+2k-1-4]為二元最優(yōu)碼,σ=2k-1n-d(2k-1)=2×2k-1+d, 且s-2≤li≤s+3,1≤i≤N。

1)若lmax=s+3, 則C有約化碼[Nks+Nk-8,k-1,2k-1s+2k-1-4]=[(2s+1)Nk-1+Nk-1-7,k-1,(2s+1)2k-2s+2k-2-4]為自正交碼。 因此h(C)≥k-2。

2)若lmax=s+2, 則C有約化碼[Nks+Nk-7,k-1,2k-1s+2k-1-4]=[(2s+1)Nk-1+Nk-1-6,k-1,(2s+1)2k-2s+2k-2-4],此約化碼的h值為h≥k-1-4=k-5.因此h(C)≥k-6。

3)若lmax=s+1 且lmin=s, 則有廣義反碼(5,2k,{4}),此廣義反碼(5,2k,{4})的秩至多為4,故h(C)≥k-4。

4)若lmax=s+1 且lmin=s-1, 則C的定義向量L以及Lc分別具有以下形式:

①L1:]](s-1)1∣(s)3∣(s+1)N-4]],

②L2:]](s-1)2∣(s)1∣(s+1)N-3]],

以上2種定義向量L分別對應碼的h(C)值為h≥k-3,h≥k-1。

5)若lmax=s+1 且lmin=s-2,則C的定義向量L以及Lc分別具有形式:

②L2:]](s-2)1∣(s-1)1∣(s)0∣(s+1)N-2]],

以上2種定義向量L分別對應碼的h(C)值為h≥k-3,h≥k-1。

總結以上各種情況,可得到h([Nks+Nk-5,k,2k-1s+2k-1-4])≥k-6,故引理成立。

引理2.5若k≥5,則二元最優(yōu)[Nks+Nk-10,k]碼不是LCD碼。

證明記[n,k,d]=[Nks+Nk-10,k,2k-1s+2k-1-6], 則C=[n,k,d]為二元最優(yōu)碼,并有σ=2k-1n-d(2k-1)=2k-1+d,且L滿足s-1≤li≤s+2,1≤i≤N。

首先, 我們可斷言lmax=s+2不會出現(xiàn),否則C有約化碼[Nks+Nk-12,k-1,2k-1s+2k-1-6]=[(2s+1)Nk-1+Nk-1-11,k-1,(2s+1)2k-2+2k-2-6]違背Griesmer界,矛盾。從而可得lmax=s+1。

1)若lmax=s+1,lmin=s,則C對應的反碼為(10,2k,{6}),此廣義反碼生成矩陣Ga的秩至多為6,下面證明Ga的秩至多為5。 否則,可設Ga?(I6∣u1,u2,u3,u4),ui(1≤i≤4)是互不相同的向量且重量都大于2。 若ui中有一個具有奇重量, 則反碼具有碼字 的重量δ≥7,矛盾。若ui都具有偶重量,則由4×2/6=2可知(u1,u2,u3,u4)具有一行的重量不小于2,于是Ga中存在5行的線性組合得到的碼字重量δ≥7,矛盾。故可得出Ga的秩至多為5。

根據(jù)文獻[20], 秩不超過5的(10,2k,{6})反碼僅有2個,分別滿足rank(Ga(Ga)T)=4,2故此種情況下h(C)≥k-4。

2)若lmax=s+1,lmin=s-1,則C的定義向量L以及Lc分別具有形式:

①L1:]](s-1)1∣(s)8∣(s+1)N-9]],

②L2:]](s-1)2∣(s)6∣(s+1)N-8]],

③L3:]](s-1)3∣(s)4∣(s+1)N-7]],

④L4:]](s-1)4∣(s)2∣(s+1)N-6]],

⑤L5:]](s-1)5∣(s)0∣(s+1)N-5]],

若L(Lc)具有形式Li,(3≤i≤5),則有rank(Ga(Ga)T)≤4。

總結上面2種情形,即證明引理成立。

推論2.6若k≥6,則二元最優(yōu)[Nks+Nk-11,k]碼不是LCD碼。

證明參數(shù)[Nks+Nk-11,k,2k-1s+2k-1-7]的碼是二元最優(yōu)碼,它的擴展碼是[Nks+Nk-10,k,2k-1s+2k-1-6]二元最優(yōu)碼,此擴展碼的根維數(shù)h≥k-4。

當k≥6, 擴展碼的根維數(shù)h≥k-4≥2,故二元最優(yōu)[Nks+Nk-11,k]碼的根維數(shù)h≥k-5,不是LCD碼。

引理2.7若k≥7,則二元最優(yōu)[Nks+Nk-9,k]碼不是LCD碼。

證明記C=[n,k,d]=[Nks+Nk-9,k,2k-1s+2k-1-6]為二元最優(yōu)碼,對此最優(yōu)碼有σ=2k-1n-d(2k-1)=2×2k-1+d,且s-2≤li≤s+3(1≤i≤N)。

仿照引理2.4可證明lmax=s+3不會出現(xiàn),于是lmax≤s+2。

1)lmax=s+2, 則C有約化碼[Nks+Nk-11,k-1,2k-1s+2k-1-6]=[(2s+1)Nk-1+Nk-1-10,k-1,(2s+1)2k-2s+2k-2-6],

此約化碼的h值為h≥=k-5,因此h(C)≥k-6。

2)若lmax=s+1,lmin=s,則C的則有廣義反碼(9,2k,{6}),此廣義反碼(9,2k,{6})的秩至多為6,故h(C)≥k-6。

3)若lmax=s+1,lmin=s-1,則C的定義向量L以及Lc分別具有形式:

①L1:]](s-1)1∣(s)7∣(s+1)N-8]],

②L2:]](s-1)2∣(s)5∣(s+1)N-7]],

③L3:]](s-1)3∣(s)3∣(s+1)N-6]],

④L4:]](s-1)4∣(s)5∣(s+1)N-5]],

若L(Lc)具有形式Li,(2≤i≤4),則有rank(Ga(Ga)T)≤5。

于是, 我們僅需要確定情形1)下廣義反碼(9,2k,{6})的秩,仿照情形1)可證明廣義反碼生成矩陣Ga的秩至多為5。這表明lmax=s+1且lmin=s-1時h(C)≥k-5。

4)若lmax=s+1,lmin=s-2, 則C的定義向量L以及Lcs分別具有形式:

①L1:]](s-2)1∣(s-1)0∣(s)6∣(s+1)N-7]],

②L2:]](s-2)1∣(s-1)1∣(s)4∣(s+1)N-6]],

③L3:]](s-2)1∣(s-1)2∣(s)2∣(s+1)N-5]],

④L4:]](s-2)2∣(s-1)0∣(s)3∣(s+1)N-5]],

⑤L5:]](s-2)2∣(s-1)1∣(s)1∣(s+1)N-4]],

⑥L6:]](s-2)1∣(s-1)3∣(s)0∣(s+1)N-4]],

⑦L7:]](s-2)3∣(s-1)0∣(s)0∣(s+1)N-3]],

總結以上4類情形,即證明引理成立。

3 結語

本文利用廣義反碼理論與方法研究形如[sNk+Nk-a,k]的二元性質,證明1≤a≤11,k≥7時,二元最優(yōu)碼不是LCD碼。這為確定對應碼長最優(yōu)LCD碼的距離以及研究如何構造最優(yōu)LCD碼奠定了基礎, 為研究高維二元LCD提供了可借鑒的新理論和新方法。