黃素娟，孫中華，朱士信

（1.合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院,安徽合肥 230601；2.智能互聯(lián)系統(tǒng)安徽省實驗室,安徽合肥 230009）

1 引言

循環(huán)碼是一類重要的線性碼，許多高效的糾錯碼都是循環(huán)碼，如Golay 碼和RS碼等.重根循環(huán)碼作為一類特殊的循環(huán)碼受到廣泛關(guān)注.Chen［1］在其博士論文中研究了碼長為2n（n是奇數(shù)）的二元重根循環(huán)碼的最小距離（相關(guān)結(jié)論亦可查閱文獻(xiàn)［2］）.Gastagnoli 等人［3］證明了重根循環(huán)碼的最小距離可以用一組單根循環(huán)碼的最小距離來表示，并證明了重根循環(huán)碼是漸進(jìn)壞的.基于這一理論，編碼學(xué)者們確定了幾類重根循環(huán)碼的最小距離（參閱文獻(xiàn)［4～6］和它們的引用）.van Lint［7］通過(u|u+v)構(gòu)造證明了碼長為2n（n是奇數(shù)）的二元重根循環(huán)碼可以通過兩個碼長為n的二元循環(huán)碼來構(gòu)造，并構(gòu)造了參數(shù)為[2m-2，2m-m-3，4]的最優(yōu)二元循環(huán)碼.然而，由于重根循環(huán)碼是漸進(jìn)壞的，此后關(guān)于重根循環(huán)碼最優(yōu)性的討論相對較少.

最新的研究結(jié)果表明，重根循環(huán)碼在量子糾錯碼和符號對碼的構(gòu)造中有重要作用.以重根循環(huán)碼為載體，文獻(xiàn)［8～11］構(gòu)造了幾類參數(shù)優(yōu)的量子重根循環(huán)碼，文獻(xiàn)［12］構(gòu)造了幾類參數(shù)好的非二元量子同步碼.文獻(xiàn)［13］和文獻(xiàn)［14］，利用重根循環(huán)碼的代數(shù)結(jié)構(gòu)，確定了幾類重根循環(huán)碼的最小對距離，由此構(gòu)造了幾類有最大符號對距離的符號對碼，從而說明重根循環(huán)碼在符號對讀信道上有較好的糾錯能力.重根循環(huán)碼的糾錯能力是這兩類應(yīng)用中的一個關(guān)鍵點(diǎn)，因此，分析重根循環(huán)碼的糾錯能力并探討它的最優(yōu)性，是一個有趣的問題.

一個p元[n，k，d]線性碼C稱為距離最優(yōu)的是指不存在參數(shù)為[n，k，≥d+1]的p元線性碼.碼C稱為維數(shù)最優(yōu)的是指不存在參數(shù)為[n，≥k+1，d]的p元線性碼.本文基于循環(huán)碼的代數(shù)的結(jié)構(gòu)，首先，構(gòu)造了幾類最小距離是4 的距離最優(yōu)二元重根循環(huán)碼，特別地，其中一類距離最優(yōu)碼也是維數(shù)最優(yōu)的線性碼；其次，構(gòu)造了一類最小距離是3 的距離和維數(shù)都是最優(yōu)的非二元重根循環(huán)碼；最后，構(gòu)造了兩類最小距離是4 的距離最優(yōu)非二元循環(huán)碼.本文的研究結(jié)果表明，重根循環(huán)碼可以產(chǎn)生小距離的最優(yōu)線性碼.

2 預(yù)備知識

設(shè)p是一個素數(shù)，F(xiàn)p是p階有限域.設(shè)n是一個正整數(shù)，是Fp上n維行向量空間.的每個k維子空間稱為一個碼長為n且維數(shù)為k的p元線性碼，記作[n，k].設(shè)x∈，向量x的Hamming 重量定義為x非零分量的個數(shù)，記作wt(x).設(shè)x，y∈，向量x和y的Hamming 距離定義為x-y的Hamming 重量，記作dist(x，y)，即dist(x，y)=wt(x-y).一個p元[n，k]線性碼C的最小距離定義為

碼長為n、維數(shù)為k和最小距離為d的p元線性碼，記作[n，k，d].一個p元[n，k，d]線性碼的三個參數(shù)滿足球包界［15］：

對于p＞3元[n，k，d]線性碼，文獻(xiàn)［16］證明

一個碼長n的p元線性碼C稱為循環(huán)碼是指對任意 的(c0，c1，…，cn-1) ∈C，有(cn-1，c0，…，cn-2) ∈C.定義映射

則碼長為n的p元線性碼C是循環(huán)碼當(dāng)且僅當(dāng)σ(C)={σ(c)|c ∈C}是商環(huán)R的理想.眾所周知，商環(huán)R是主理想環(huán)，因此，對于每個碼長為n的p元循環(huán)碼C，存在唯一的多項式g(x) ∈Fp[x]使得g(x)|(xn-1) 且C=g(x)R=(g(x))，g(x)稱為碼C的生成多項式，并且碼C的維數(shù)dim(C)=n-deg(g(x)).設(shè)n=pe?，其中e和?是非負(fù)整數(shù)且gcd(?，p)=1.記ord?(p)為p模? 的階，即使得pl≡1(mod ?)的最小正整數(shù).設(shè)ord?(p)=m，則在Fpm上存在一個?次本原單位根α.設(shè)Z?=是整數(shù)模? 的剩余類環(huán).定義Z?上等價關(guān)系～：i～j??s∈Z，ips≡j(modn).用Λ表示等價類構(gòu)成的集合，則

其中cl(i) 表示i所在的等價類.對于0 ≤i≤n-1，F(xiàn)p[x]上以αi為根的次數(shù)最低首一多項式稱作αi在Fp上的極小多項式.容易驗證，αi在Fp上的極小多項式為(x-αj) ∈Fp[x].進(jìn)一步可證，式（4）為x?-1 在Fp[x]上的不可約分解且xn-1=(x?-1)pe=當(dāng)e=0 時，碼長為n的p元循環(huán)碼稱為單根循環(huán)碼；當(dāng)e≥1 時，碼長為n的p元循環(huán)碼稱為重根循環(huán)碼.對于單根循環(huán)碼的最小距離有如下著名的界［15］.

引理1設(shè)p是一個素數(shù)，n是一個正整數(shù)且gcd(n，p)=1.設(shè)α是一個n次本原單位根.設(shè)C是一個碼長為n且生成多項式為g(x)的p元循環(huán)碼.如果存在整數(shù)b，c1，c2且gcd(c1，n)=gcd(c2，n)=1使得

是g(x)的根，則碼C的最小距離d(C) ≥δ+s.

當(dāng)s=0 時，引理1 稱為BCH 界.對于重根循環(huán)碼的最小距離，Gastagnoli等人［3］提出了如下理論.

設(shè)x?-1 在Fp[x] 上的不可約分解為x?-1=m1(x)m2(x)…mr(x)，則碼長為n的p元循環(huán)碼C的生成多項式可唯一表示為g(x)=其中0 ≤si≤pe，i=1，2，…，r.對于0 ≤t≤pe-1，定義

引理2碼長為n且生成多項式為g(x)=的p元重根循環(huán)碼的最小距離d(C)=min{Pt·d()|0 ≤t≤pe-1}.

3 主要結(jié)果

基于重根循環(huán)碼的代數(shù)結(jié)構(gòu)，本節(jié)構(gòu)造了幾類最優(yōu)碼.

3.1 二元最優(yōu)重根循環(huán)碼

下面構(gòu)造最優(yōu)二元重根循環(huán)碼.對任意的正整數(shù)?，記v2(?)表示? 的2-進(jìn)制展開中非零項的最高次冪，即如果v2(?)=i，則? 的2-進(jìn)制展開為?0+?12+…+?i-12i-1+2i.

定理1設(shè)? 是奇數(shù)且? ≥3，e是正整數(shù)，則存在參數(shù)為[2e?，2e?-2e-1-ord?(2)-1，4]的二元重根循環(huán)碼C(e，?).當(dāng)v2(?2)-ord?(2) ≥2e-1-2e+2 時，C(e，?)是距離最優(yōu)的二元線性碼.

證明設(shè)α是F2擴(kuò)域上的?次本原單位根，m(x)是α在F2上的極小多項式.設(shè)C(e，?)是碼長為n=2e? 且生成多項式為m(x)的二元重根循環(huán)碼，則

首先，證明d(C(e，?))=4.設(shè)是碼長為? 且生成多項式為(x+1)m(x)的二元循環(huán)碼.因為α0，α1，α2是(x+1)m(x)的零點(diǎn)，由BCH 界，d()≥4.設(shè)是碼長為?且生成多項式為x+1的二元循環(huán)碼，則d(Cˉ1)=2.容易驗證P：=min{Pt：2e-1+1 ≤t≤2e-1}=4.由引理2，d(C(e，?))=min{d()，2d()，P}=4.

最后，證明C(e，?)的最優(yōu)性.假設(shè)存在參數(shù)為[2e?，2e?-2e-1-ord?(2)-1，≥5] 的二元碼，由球包界（1），

而不等式左端

矛盾.因此，C(e，?)是距離最優(yōu)的二元線性碼.

注1定理1 的距離最優(yōu)約束條件是充分的.通過計算機(jī)搜索，定理1可以產(chǎn)生39個碼長不超過256的距離最優(yōu)二元重根循環(huán)碼，其中36 個碼長滿足定理1 中的約束條件，與碼表［17］比較，36個距離最優(yōu)二元碼中有11 個碼是維數(shù)最優(yōu)的.詳見表1.其中帶#的碼表示不滿足約束條件的最優(yōu)碼，帶*的碼表示維數(shù)最優(yōu)碼.由此可以看出，盡管重根循環(huán)碼是漸近壞的，但仍存在小距離的最優(yōu)重根循環(huán)碼.

表1 最小距離是4的最優(yōu)二元重根循環(huán)碼

由定理1，可以得到一系列最小距離是4 的最優(yōu)二元線性碼.下面給出幾類具體的最優(yōu)二元重根循環(huán)碼.

推論1設(shè)m，e是正整數(shù)且m≥max{2e-1-2e+3，2}，則存在參數(shù)為[2m+e-2e，2m+e-3·2e-1-m-1，4]的距離最優(yōu)二元重根循環(huán)碼.特別地，當(dāng)e∈{1，2}時，參數(shù)為[2m+e-2e，2m+e-3·2e-1-m-1，4]的二元重根循環(huán)碼也是維數(shù)最優(yōu)碼.

證明設(shè)?=2m-1，則v2(?2)=2m-1且ord?(2)=m.由定理1，存在參數(shù)為[2m+e-2e，2m+e-3·2e-1-m-1，4]的距離最優(yōu)二元重根循環(huán)碼.

假設(shè)存在參數(shù)為[2m+e-2e，k≥2m+e-3·2e-1-m，4]的二元線性碼.由界（2），1+n-1 ≤2n-k-1，即2m-1 ≤2n-1-e-k≤.當(dāng)e∈{1，2} 時，m+2e-1-e-1=m-1，所以2m-1 ≤2m-1，矛盾.故參數(shù)為[2m+e-2e，2m+e-3·2e-1-m-1，4]的距離最優(yōu)碼也是維數(shù)最優(yōu)碼.

推論2設(shè)e是正整數(shù)，m是偶數(shù)且m≥2e-1-2e+6，則存在參數(shù)為

的距離最優(yōu)二元重根循環(huán)碼.

所以v2(?2)=2m-4.由定理1，結(jié)論成立.

推論3設(shè)m是正偶數(shù)且e∈{1，2，3，4}，則存在參數(shù)為[3(2m+e+2e)，3·2m+e+5·2e-1-2m-1，4]的距離最優(yōu)二元重根循環(huán)碼.

證明設(shè)?=3(2m+1)，則ord?(2)=2m且v2(?2)=2m+3.當(dāng)e∈{1，2，3，4}時，

由定理1，結(jié)論成立.

推論4設(shè)m≥3 是正奇數(shù)且e∈{1，2，3，4}，則存在參數(shù)為[3(2m+e-2e)，3·2m+e-7·2e-1-2m-1，4]的距離最優(yōu)二元重根循環(huán)碼.

證明設(shè)?=3(2m-1)，則ord?(2)=2m.當(dāng)m=3時，v2(?2)=8；當(dāng)m≥5 時，v2(?2)=2m+3.容易驗證，當(dāng)e∈{1，2，3，4} 時，v2(?2)-ord?(2) ≥2e-1-2e+2.由定理1，結(jié)論成立.

推論5設(shè)m是正整數(shù)且e∈{2，3}，則存在參數(shù)為[2m+e+2e，2m+e+2e-1-2m-1，4]的距離最優(yōu)二元重根循環(huán)碼.

證 明設(shè) ?=2m+1，則 ord?(2)=2m且v2(?2)=2m.當(dāng)e∈{2，3}時，v2(?2)-ord?(2) ≥2e-1-2e+2.由定理1，結(jié)論成立.

3.2 非二元最優(yōu)循環(huán)碼

本小節(jié)將構(gòu)造幾類非二元最優(yōu)碼.

定理2設(shè)p是一個奇素數(shù)，m是一個正整數(shù)，λ≥2且λ|(p-1)，則存在參數(shù)為

的距離和維數(shù)都是最優(yōu)的p元重根循環(huán)碼.

證明設(shè)?=，α是Fp擴(kuò)域上的? 次本原單位根，m(x)是α在Fp上的極小多項式.設(shè)C是碼長為n=p? 且生成多項式為(x-1)2m(x)的p元重根循環(huán)碼，則dim(C)=n-2-m.

設(shè)是碼長為? 且生成多項式為(x-1)m(x)的p元循環(huán)碼.因為α0和α1是(x-1)m(x)的零點(diǎn)，由BCH界，d()≥3.設(shè)是碼長為?且生成多項式為x-1的p元循環(huán)碼，則d(Cˉ1)=2.容易驗證，

下面討論碼C的最優(yōu)性.由球包界（1）推出，不存在參數(shù)為[p?，p?-2-m，≥5]的p元線性碼.假設(shè)存在參數(shù)為[p?，p?-2-m，4]的p元線性碼，由界（3），1+(n-1)(p-1) ≤pn-1-dim(C)=pm+1，矛盾.因此，C是距離最優(yōu)的p元循環(huán)碼.同理，假設(shè)存在參數(shù)為[p?，k≥p?-1-m，3]的p元線性碼，由球包界（1），1+n(p-1) ≤pn-k≤pm+1，矛盾.因此，碼C是維數(shù)最優(yōu)的p元循環(huán)碼.

由定理2推出，存在如下最優(yōu)的p元重根循環(huán)碼.

推論6設(shè)p是一個奇素數(shù)且m是正整數(shù)，則

（i）存在參數(shù)為[pm+1-p，pm+1-p-2-m，3]的距離和維數(shù)都是最優(yōu)的p元重根循環(huán)碼；

（ii）存在參數(shù)為

的距離和維數(shù)都是最優(yōu)的p元重根循環(huán)碼；

（iii）如果p≥5，存在參數(shù)為

的距離和維數(shù)都是最優(yōu)的p元重根循環(huán)碼.

例1當(dāng)p=3時，定理2構(gòu)造了一類參數(shù)為[3m+1-3，3m+1-5-m，3]的最優(yōu)三元循環(huán)碼.對于短碼長，表2給出了它們的生成多項式，與碼表［17］比較，定理2 證明存在最優(yōu)重根循環(huán)碼.

表2 最小距離是3的最優(yōu)三元重根循環(huán)碼

例2當(dāng)p=5時，定理2構(gòu)造了兩類最優(yōu)五元循環(huán)碼，它們的參數(shù)分別為[5m+1-5，5m+1-7-m，3]和對于短碼長，表3 給出了它們的生成多項式，與碼表［17］比較，定理2 證明存在最優(yōu)重根循環(huán)碼.

表3 最小距離是3的最優(yōu)五元重根循環(huán)碼

下面構(gòu)造最小距離是4的最優(yōu)p元循環(huán)碼.

定理3設(shè)p是一個奇素數(shù)，m和n是正整數(shù)，n|(p2m-1)且n＞pm+1.設(shè)gcd(pm+1，n)=τ，λ=且ordλ(p)=s，當(dāng)

時，存在參數(shù)為[n，n-1-2m-s，4]的距離最優(yōu)p元循環(huán)碼.

證明因為n|(p2m-1)且n＞pm+1，則ordn(p)=2m.設(shè)α∈是一個n次本原單位根，m(x)是α在Fp上的極小多項式，則deg(m(x))=2m.設(shè)(x)是在Fp上的極小多項式，下證deg((x))=s.顯然，deg((x)) 是使(pm+1)(pl-1) ≡0(modn) 成立的最小正整數(shù).注意到

于是deg((x))=s.設(shè)C是碼長為n且生成多項式為g(x)=(x-1)m(x)(x) 的p元 循 環(huán) 碼，則dim(C)=n-1-2m-s.

一方面，因為α0，α1，αpm，是g(x)的零點(diǎn)，由引理1，d(C) ≥4.另一方面，假設(shè)存在參數(shù)為[n，n-1-2m-s，≥5]的p元線性碼.由球包界（1），

由此推出

矛盾.因此，C是最小距離為4的最優(yōu)p元循環(huán)碼.

由定理3推出，存在如下最優(yōu)的p元循環(huán)碼.

推論7設(shè)p是一個奇素數(shù)且m是一個正整數(shù)，則

（i）對任意的n|(p2-1)且n＞p+1，存在參數(shù)為[n，n-4，4]的距離最優(yōu)p元循環(huán)碼；

（ii）如果m≥2，對任意的e|(p-1)，s≥2 且s|m，存在參數(shù)為

的距離最優(yōu)p元循環(huán)碼；

（iii）對任意的?|(p2-1)且? ≥p+1，存在參數(shù)為[(p2+1)?，(p2+1)?-7，4]的距離最優(yōu)p元循環(huán)碼；

（iv）對任意的e|(p2-1)且e＜p2-1，存在參數(shù)為的距離最優(yōu)p元循環(huán)碼；

（v）如果p≥5 且m≥4，對任意的e|(p2-1)，存在參數(shù)為的距離最優(yōu)p元循環(huán)碼；

（vi）如果m≥3，存在參數(shù)為

的距離最優(yōu)三元循環(huán)碼；

（vii）如果m≥5，存在參數(shù)為

的距離最優(yōu)三元循環(huán)碼；

（viii）如果p≥5，對任意的?|(p-1)且? ≥2，存在參數(shù)為[(pm+1)?，(pm+1)?-2-2m，4]的距離最優(yōu)p元循環(huán)碼.

證明（i）～（viii）的證明類似，下面僅給出（v）的證明，其余略去.

由定理3，存在參數(shù)為[n，n-1-3m，4]的距離最優(yōu)p元循環(huán)碼.

下面構(gòu)造最小距離是4的最優(yōu)p元重根循環(huán)碼.

定理4設(shè)p是一個奇素數(shù)，m和? 是正整數(shù)，?|(p2m-1)且? ＞pm+1.設(shè)gcd(pm+1，?)=τ，λ=且ordλ(p)=s，當(dāng)

時，存在參數(shù)為[p?，p?-2m-s-3，4]的距離最優(yōu)p元重根循環(huán)碼.

證明與定理3類似，可證ord?(p)=2m.設(shè)α∈是一個? 次本原單位根，m(x)是α在Fp上的極小多項式，且(x) 是在Fp上的極小多項式，則deg(m(x))=2m且deg((x))=s.設(shè)C是碼長為p?且生成多項式為(x-1)3m(x)(x)的p元循環(huán)碼，則dim(C)=n-3-2m-s.與定理3 類似可證，C是參數(shù)為[p?，p?-2m-s-3，4]的距離最優(yōu)p元線性碼.

由定理4推出，存在如下最優(yōu)的p元重根循環(huán)碼.

推論8設(shè)p是一個奇素數(shù)且m是一個正整數(shù)，則

（i）對任意的?|(p2-1)且? ≥(p+1)，存在參數(shù)為[p?，p?-6，4]的距離最優(yōu)p元重根循環(huán)碼；

（ii）如果m≥2，對任意的e|(p-1)，s≥2 且s|m，存在參數(shù)為

的距離最優(yōu)p元重根循環(huán)碼；

（iii）對任意的?|(p2-1)且? ≥p+1，存在參數(shù)為[(p3+p)?，(p3+p)?-9，4]的距離最優(yōu)p元重根循環(huán)碼；

的距離最優(yōu)三元重根循環(huán)碼；

（viii）如果p≥5，對任意的?|(p-1)且? ≥2，存在參數(shù)為[(pm+1+p)?，(pm+1+p)?-4-2m，4]的距離最優(yōu)p元重根循環(huán)碼.

注2定理3 和定理4 構(gòu)造了兩大類最小距離是4的最優(yōu)p元循環(huán)碼，其中定理4 構(gòu)造了距離最優(yōu)的重根循環(huán)碼，從而說明重根循環(huán)碼可以產(chǎn)生小距離的最優(yōu)碼.通過計算機(jī)搜索，本文構(gòu)造了9 個碼長不超243 的距離最優(yōu)三元碼，其中3 個碼是維數(shù)最優(yōu)碼，詳見表4，其中帶*的碼表示維數(shù)最優(yōu)碼.與碼表［17］比較，本文構(gòu)造了最優(yōu)循環(huán)碼.

表4 最小距離是4的最優(yōu)三元循環(huán)碼

注3當(dāng)定理3 和定理4 的最優(yōu)約束條件不滿足時，仍可以構(gòu)造達(dá)到碼表［17］的最優(yōu)碼，下面舉例說明.

例3設(shè)α是F3上不可約多項式x6+2x5+2x+2的根，則α是一個56 次本原單位根.設(shè)η=α28，則η在F3上的不可約多項式為x+1.設(shè)C1是碼長為56 且生成多項式為(x-1)(x+1)(x6+2x5+2x+2)的三元循環(huán)碼，由定理3的證明可得，C1是一個參數(shù)為[56，48，≥4]的三元循環(huán)碼.由Magma 計算得，d(C1)=4.與碼表［17］比較，C1是目前已知的最優(yōu)三元線性碼.設(shè)C2是碼長為168 且生成多項式為(x-1)3(x+1)(x6+2x5+2x+2)的三元重根循環(huán)碼，由定理4 的證明可得，C2是一個參數(shù)為[168，154，4]的三元重根循環(huán)碼.與碼表［17］比較，C2是目前已知的最優(yōu)三元線性碼.

4 結(jié)論

本文主要研究了重根循環(huán)碼的糾錯性能，并基于重根循環(huán)碼構(gòu)造了一系列最優(yōu)的線性碼.主要結(jié)果如下：（1）構(gòu)造了幾類最小距離是4 的最優(yōu)二元重根循環(huán)碼，特別地，構(gòu)造了一類維數(shù)和距離都是最優(yōu)的二元重根循環(huán)碼，這一結(jié)果可以視作文獻(xiàn)［7］中例3 的推廣；（2）構(gòu)造了一類最小距離是3的距離和維數(shù)都是最優(yōu)的非二元重根循環(huán)碼；（3）構(gòu)造了兩大類最小距離是4 的距離最優(yōu)的非二元循環(huán)碼.這些研究結(jié)果表明：重根循環(huán)碼中存在小距離的最優(yōu)線性碼.自然地，是否存在最小距離大于4 的最優(yōu)重根循環(huán)碼是一個值得進(jìn)一步研究的問題.文獻(xiàn)［13］和文獻(xiàn)［14］基于重根循環(huán)碼的代數(shù)結(jié)構(gòu)和最小Hamming 距離，確定了幾類循環(huán)碼的對距離，構(gòu)造了幾類極大距離可分符號對碼，從而說明重根循環(huán)碼有較好的糾正錯誤的能力.下一步將研究本文構(gòu)造的最優(yōu)碼的對距離，從而構(gòu)造參數(shù)優(yōu)的符號對碼.