一種三元線性補對偶碼的構造方法

黃 山 朱士信 李 錦

①(安徽警官職業(yè)學院 合肥 230031)

②(合肥工業(yè)大學數(shù)學學院 合肥 230601)

1 引言

線性補對偶(Linear Complementary Dual,LCD)碼是一類具有特殊結構的線性碼，它由Massey[1]引入并用于解決數(shù)據(jù)的有效存儲。1992年，Massey[2]證明LCD碼為雙用戶加法器信道提供了一種最佳的線性編碼方案。2014年，Bringer等人[3]將2元LCD碼用于抵抗側信道攻擊和錯誤注入攻擊。2016年，Carlet和Guilley[4]將q元LCD碼用于抵抗側信道攻擊和錯誤注入攻擊，并給出了幾種LCD碼的構造方法。鑒于LCD碼在抵御側信道攻擊和錯誤注入攻擊方面的重要應用，LCD碼的研究是一項重要的工作。2017年，Li等人[5,6]構造了循環(huán)LCD碼，并確定了它們的參數(shù)。2018年，Sok等人[7]利用正交群、碼的擴展和矩陣積碼構造了大域上LCD碼。2019年，Liu等人[8]利用有限域上典型群構造了LCD碼。2021年，Shi等人[9]利用有限域上托普利茲矩陣構造了LCD碼。最近，唐春明等人[10]總結了有限域上LCD碼的一些主要成果和進展，并提出了此研究領域的一些未解決的重要問題。與此同時，有限域上LCD極大距離可分(Linear Complementary Dual Maximum Distance Separable, LCD MDS)碼的構造也得到了深入的研究。最近，金玲飛等人[11]總結了有限域上LCD MDS碼的一些主要成果和進展。除此之外，有限環(huán)上LCD碼的構造也得到了深入的研究[12-15]。

2018年，Carlet等人[16]證明：給定參數(shù)為[n,k,d]的q元線性碼，當q＞3時，存在一個與其等價的具有相同參數(shù)的q元LCD碼。此后，2元和3元LCD碼的構造受到重點關注。2017年，Rao等人[17]利用循環(huán)碼構造了一些參數(shù)好的2元LCD碼。2018年，Seneviratne和Melcher[18]利用幾何的方法分別構造了一類2元和3元LCD碼。2019年，Zhou等人[19]利用定義集方法構造了參數(shù)優(yōu)的2元LCD碼。Carlet等人[20]利用正交或辛基刻畫了2元LCD碼并研究了2元LCD碼的最小距離。Galindo等人[21]利用J-仿射變種碼的子域子碼，構造了參數(shù)好的2元和3元LCD碼。Li等人[22]利用定義集方法構造了參數(shù)優(yōu)的3元LCD碼。Liu等人[23]確定了幾類長度為2m+1的2元線性補BCH(Linear Complementary Dual Bose Chaudhuri Hocquenghem, LCD BCH)碼的參數(shù)。2020年，Wu等人[24]利用單純復形構造了參數(shù)優(yōu)的2元LCD碼。Huang等人[25]構造了一類長度為2m-1的LCD BCH碼并研究了這類碼的參數(shù)。Lu等人[26]利用拓展、截斷和組合等方法，構造了參數(shù)好的3元LCD碼。2021年，Bouyuklieva[27]研究了2元LCD碼的性質(zhì)及其最大極小重量的界。Araya等人[28]給出了2元和3元LCD碼的最大極小重量的一個刻畫，并分類了小維數(shù)的最優(yōu)2元和3元LCD碼。Harada[29]給出了2元和3元LCD碼的兩種構造方法，并改進了這兩類LCD碼的最大極小重量的界。Araya等人[30]分別確定了維數(shù)為5的2元LCD碼和維數(shù)為4的3元LCD碼的最大極小重量。2022年，Liu等人[31]利用矩陣積碼，構造了漸近好的2元和3元LCD碼。Huang等人[32]確定了一些3元長度為 3m-1的LCD BCH碼的重量分布。最近，李平等人[33]利用定義集方法構造了一些參數(shù)優(yōu)的3元LCD碼。從研究現(xiàn)狀分析，構造參數(shù)好的3元LCD碼是一個有趣的問題。

本文利用環(huán) F3+uF3(u2=0)上循環(huán)碼的Gray象構造3元LCD碼。環(huán) F3+uF3是一類有限鏈環(huán)。Dinh等人[34]確定了有限鏈環(huán)上循環(huán)碼的代數(shù)結構。Norton等人[35]證明有限鏈環(huán)上線性碼的Hamming距離等于其最高階撓碼的Hamming距離。張付麗等人[36]確定了環(huán)Fq+uFq上循環(huán)碼的剩余碼和撓碼的結構，并將其應用于構造量子碼，其中u2=0且q是一個素數(shù)冪。本文通過引入( F3+uF3)n到F23n的等距Gray映射，利用環(huán)F3+uF3上長度為n的循環(huán)碼的Gray象，構造了幾類長度為 2n的參數(shù)好的3元LCD碼。

2 預備知識

引理2[34]設n是一個正整數(shù)且g cd(n,3)=1。設C是環(huán)F3+uF3上長度為n的循環(huán)碼，則存在唯一的首一多項式f(x)和h(x)使 得C=(f(x)h(x),uf(x))，其中f(x)h(x)|(xn-1)。

文獻[36]研究了環(huán) Fq+uFq上循環(huán)碼的撓碼，其中u2=0 且q是一個素數(shù)冪。將相關結果應用到F3+uF3上循環(huán)碼，有如下結論。

引理3[36]設n是一個正整數(shù)且g cd(n,3)=1。設C=(f(x)h(x),uf(x))是 環(huán)F3+uF3上長度為n的循環(huán)碼，其中f(x)和h(x) 是F3上首一多項式且f(x)h(x)|(xn- 1) 。 則 R es(C) = (f(x)h(x))且Tor(C)=(f(x))。

3 3元LCD碼的構造

證明 由引理3， Res(C)=(f(x)h(x))。因為f(x)h(x)∈C，所以R es(C)?C。一方面，由引理1，R es(C)∩Res(C)⊥={0}當 且僅當(f(x)h(x))*=f(x)h(x) 。容 易 驗 證，(f(x)h(x))*=f*(x)h*(x)。因此， (f(x)h(x))*=f(x)h(x) 等價于f*(x)h*(x)=f(x)h(x)。 另一方面，由引理3，T or(C)=(f(x))。由引理1，T or(C)∩Tor(C)⊥={0}當 且僅當f*(x)=f(x)。綜合兩方面，結論成立。 證畢

引理5 設C=(f(x)h(x),uf(x))是 環(huán)R上長度為n的循環(huán)碼，其中f(x)和h(x) 是F3上首一多項式且f(x)h(x)|(xn-1) 。則C的G r a y 距離dG滿足：min{d1,2d2}≤dG≤2d2， 其中d1和d2分 別是Res(C)和T or(C)的Hamming距離。

證明 設c(x)=a(x)+ub(x)∈C且c(x)?=0。由引理4，R es(C)?C，所以a(x)∈Res(C)且b(x)∈Tor(C)。由Gray重量的定義

其中， (-|-) 表示向量的級聯(lián)。當a(x)=0時，b(x)?=0 且wtG(c(x))=2·wtH(b(x)) 。 由 于b(x)∈Tor(C) ，所以w tG(c(x))≥2d2。當a(x)?=0時，注意到

因此，w tG(c(x))≥min{d1,2d2}， 即dG≥min{d1,2d2}。特別地，因為T or(C)的 Hamming距離為d2，所以存在λ(x)∈Tor(C)使 得w tH(λ(x))=d2。 注意到uλ(x)∈C且 wtG(uλ(x))=2d2， 因此，dG≤2d2。 證畢

由引理4和引理5，利用環(huán)R上循環(huán)碼可以構造如下參數(shù)的3元LCD碼。

定理2 設f(x)和h(x)是 F3上首一多項式且使得f(x)h(x)|(xn-1),f*(x)=f(x)且h*(x)=h(x)。 設d1和d2分 別 是 長 度 為n的3 元 循 環(huán) 碼(f(x)h(x))和(f(x))的 Hamming距離。設C=(f(x)h(x),uf(x))是環(huán)R上長度為n的循環(huán)碼，則?(C) 是3元[2n,2n-2 deg(f(x))-deg(h(x)),d]L CD碼，其中min{d1,2d2}≤d ≤2d2。

證明 由引理3，R es(C)=(f(x)h(x))且 Tor(C)=(f(x))。 當f*(x)=f(x)且h*(x)=h(x)時，由引理4，Res(C)?C且Res(C)∩Res(C)⊥=Tor(C)∩Tor(C)⊥={0}。由定理1，?(C) 是長度為2n的LCD碼。碼?(C)的維數(shù)由引理5，碼C的Gray距離dG滿足min{d1,2d2}≤dG≤2d2。由 定 理1，碼?(C)的H a m m i n g 距 離d=dG。綜上所述，結論成立。 證畢

定理3 設n是一個正整數(shù)且存在j使得3j ≡-1(modn) 。設m是 使 得3m ≡-1(modn)的 最小正整數(shù)。設β是一個n次 本原單位根且M(x)是β在F3上 的極小多項式。設C=((x-1)M(x),u(x-1))是環(huán)R上長度為n的循環(huán)碼，則?(C) 是 3元[2n,2n-2m-2,4] L C D 碼，且R es(C) 是3 元[n,n-2m-1,d ≥4]LCD碼。

證明 顯然， (x-1)*=x-1 。因為存在j使得3j ≡-1(modn) ，所以M*(x)=M(x)。又因為m是使得3m ≡-1(modn)的最小正整數(shù)，所以ordn(3)=2m， 即d eg(M(x))=2m。 由定理2，?(C)是一個3 元 [2n,2n-2m-2]L C D 碼。由 引 理3，Res(C)=((x-1)M(x)) ， 則R es(C) 是3 元[n,n-2m-1] LCD碼。下面討論?(C) 和R es(C)的Hamming距離。

顯 然， Tor(C)=(x-1)的H a m m i n g 距 離d2=2 。設d1是R es(C)的Hamming距離。注意到3m ≡-1(modn)， 即β-1是M(x)的 零點。進而，β-1,β0,β是(x-1)M(x)的 零點。由BCH界[37]，d1≥4。綜合兩方面，由定理2，?(C)的Hamming距離d=4。 證畢

由定理3，可以得到如下兩類具體的LCD碼。

推論1設n=3m+1 ，其中m為整數(shù)。設β是一個n次本原單位根且M(x)是β在F3上的極小多項式。設C=((x-1)M(x),u(x-1)) 是 環(huán)R上長度為n的循環(huán)碼，則?(C) 是 3元[2·3m+2,2·3m-2m,4]LCD碼，且剩余碼 Res(C)=((x-1)M(x))是3元[3m+1,3m-2m,d ≥4]LCD碼。

下面分析定理3構造的LCD碼的性能。當[n,k,d]LCD碼用于抵御側信道攻擊時，零偏移遮蔽對策是d-1階 安全的。當[n,k,d]LCD碼用于抵御錯誤注入攻擊時，任何一個Hamming重量嚴格小于d的錯誤都可以被檢測出來。因此，對固定的長度n和 維數(shù)k，構造Hamming距離盡可能大的LCD碼

是環(huán)R上長度為 10 的 循環(huán)碼。由推論1，?(C)是3元[20,14,4]LCD碼，且R es(C)是3元[10,5,4] LCD碼。因為不存在3元[ 20,14,d ≥5]線 性碼，?(C)的Hamming距離達到了最大值，所以?(C)是最優(yōu)的3元LCD碼。由碼表[39]，長度為 10 維數(shù)為5 的3元線性碼的Hamming距離的最大值為5 。 因此，R es(C)是幾乎最優(yōu)的3元LCD碼。

例3 設β ∈F36是x6+2x5+2x3+2x+1的一個零點，則β是一個2 8次本原單位根。設

是環(huán)R上長度為 28 的 循環(huán)碼。由推論1，?(C)是3元[56,48,4] L C D 碼，且R es(C)是3 元[2 8,2 1,4]LCD碼。根據(jù)理論界，長度為 56 維數(shù)為4 8的3元線性碼的Hamming距離d ≤5。由碼表[39]，長度為56 維 數(shù)為4 8的3元線性碼的Hamming距離的已知最大值為 4。因此，?(C)是已知參數(shù)最好的3 元LCD碼。同理，由碼表[39]，長度為 28 維數(shù)為 21的3元線性碼的Hamming距離的已知最大值為4。因此，R es(C)也是已知參數(shù)最好的3元LCD碼。

定理4 設n是3m-1的 正因子且n＞3m/2+1，其中m≥2 為 正整數(shù)。設β是一個n次本原單位根且M(x)是β在F3上 的極小多項式。設C=((x-1)M(x)M*(x),u(x-1)) 是環(huán)R上長度為n的循環(huán)碼，則?(C)是 3元[ 2n,2n-2m-2,4] L CD碼，且R es(C)是3元[n,n-2m-1,d ≥4]LCD碼。

證明 設 ordn(3)=e。因為n整除3m-1，所以e整除m。當e＜m時

這 與n整 除3e-1 矛 盾。 因 此，deg(M(x))=deg(M*(x))=m。下面證明M(x)?=M*(x)。假設M(x)=M*(x)， 則β-1是M(x)的零點，其等價于存在0≤j ≤m-1 使 得- 1≡3j(modn) 。 當0≤j≤m/2時 ，0＜3j+1≤3m/2+1＜n， 矛盾。當m/2+1≤j ≤m-1 時 ，- 1≡3j(modn) 與-3m-j ≡3m ≡1(modn)等 價。同理，0＜3m-j+1≤3m/2-1+1＜n， 矛盾。因此，Res(C)=((x-1)M(x)M*(x))且Tor(C)=(x-1)。 與定理3類似可證，T or(C)的Hamming距離d2=2 ，R es(C)的Hamming距離d1≥4 。由 定 理2，?(C) 是3 元[2n,2n-2m-2,4]LCD碼。由引理1，R es(C)是 3元[n,n-2m-1,d ≥4]LCD碼。 證畢

由定理4，可以得到如下兩類具體的LCD碼。

推論2設n=3m-1，其中m≥2為正整數(shù)。設β是一個n次 本原單位根且M(x)是β在F3上的極小多項式。設C=((x-1)M(x),u(x-1)) 是 環(huán)R上長度為n的循環(huán)碼，則?(C) 是3元[2·3m-2,2·3m-2m-4,4] L C D 碼，且R es(C) 是3 元[3m-1,3m-2m-2,d ≥4]LCD碼。

下面分析定理4構造的LCD碼的性能?；谝陨戏治觯瑢τ诘钟鶄刃诺拦艉湾e誤注入攻擊，對固定的長度n和 維數(shù)k，構造Hamming距離盡可能大的LCD碼是一個重要的問題。當n=3m-1時，由Hamming界，長度為n、 維數(shù)為n-2m-1的3元線性碼的Hamming距離d≤6。由界(2)，不存在3元[n,n-2m-1,6]線性碼。因此，根據(jù)線性碼的理論界，長度為n、 維數(shù)為n-2m-1的3元線性碼的Hamming距離d≤5。同理，根據(jù)線性碼的理論界，當n=2(3m-1)時 ，長度為n、 維數(shù)為n-2m-2的3元線性碼的Hamming距離d ≤5。因此，推論2構造的兩類3元LCD碼的Hamming距離與理論界相差1，具有較好的參數(shù)。一方面，與線性碼的理論界比較，定理4可以構造參數(shù)好的LCD碼。另一方面，與碼表[39]比較，定理4可以構造已知參數(shù)最好的LCD碼。下面給出兩個具體的例子加以說明。

例4設β∈F32是x2+2x+2的 一個零點，則β是 8次本原單位根。顯然，(x2+2x+2)*=x2+x+2。設C=((x-1)(x2+2x+2)(x2+x+2),u(x-1))是環(huán)R上長度為8 的循環(huán)碼。由推論2，?(C)是3元[16,10,4] LCD碼，且R es(C)是3元 [8,3,4] LCD碼。由碼表[39]，不存在3元[ 16,10,d ≥5]線性碼，因此?(C)是最優(yōu)的3元LCD碼。同理，由碼表[39]，長度為8維數(shù)為3的3元線性碼的Hamming距離的最大值為5。因此，R es(C)是幾乎最優(yōu)的3元LCD碼。

例5設β ∈F33是x3+2x+1的一個零點，則β是2 6次本原單位根。顯然

最后，將本文構造的3元LCD碼與現(xiàn)有文獻進行比較。文獻[18]利用組合的方法構造了3元

LCD碼。文獻[21]利用J-仿射變種碼的子域子碼，構造了長度滿足一定約束條件的3元LCD碼。文獻[22]利用定義集方法構造了幾類LCD碼。文獻[26]構造了長度n≤20的3元LCD碼。文獻[33]利用定義集方法構造了Hamming距離為3的最優(yōu)LCD碼。通過比較發(fā)現(xiàn)，本文構造了新參數(shù)的3元LCD碼。與線性碼的理論界和碼表比較，本文構造的4類3元LCD碼具有較好的參數(shù)。

4 結束語

造Hamming距離大于4的最優(yōu)3元LCD碼是進一步的研究問題。