盧嘯華，王永超，丁 洋

(上海大學理學院，上海 200444)

常循環(huán)碼是循環(huán)碼的一種推廣，具有嚴謹?shù)拇鷶?shù)結構，可以非常容易地進行編碼和譯碼.準循環(huán)碼是循環(huán)碼的另一個自然推廣，是已漸進好的. 有限域上的準扭碼是一類重要的分組碼，常循環(huán)碼和準循環(huán)碼都是它的特例. Daskalov 等[1]構造了七類三元準扭碼，改進了最小距離的下界. Ackerman 等[2]利用準扭碼和其對偶碼構造了一些新的五元線性碼. Aydin 等[3]研究了1-生成準扭碼. Saleh 等[4]研究了具有補對偶碼的1-生成準扭碼.

Gilbert-Varshamov 界是糾錯碼中一個非常重要的界. 隨機碼有很大概率達到Gilbert-Varshamov 界. 然而，“是否存在一類達到漸進Gilbert-Varshamov 界的循環(huán)碼”這一問題尚未得到解決[5-6]. 為了解決這個問題，一些學者開始考慮循環(huán)碼的變形. Shi 等[7]證明了存在漸進好的加性常循環(huán)碼. Mi 等[8]證明了一簇指數(shù)隨碼長變化的準循環(huán)碼是漸近好的.Kasami 等[9]證明了一類信息率為1/2 的二元準循環(huán)碼可以達到一個比Gilbert-Varshamov 界稍微弱一點的界. Bazzi 等[6]證明了一類隨機的二元阿貝爾群碼有很大的概率能達到Gilbert-Varshamov 界. Fan 等[10]將Bazzi 等[6]的結論推廣到了q元阿貝爾群碼. 本工作證明了一類q元準扭碼可以達到Gilbert-Varshamov 界.

1 預備知識

1.1 線性碼

Fq表示含有q個元素的有限域，F(xiàn)nq表示Fq上的n維向量空間. 對于任意的x=(x1，x2，··· ，xn)∈Fnq，x的Hamming 重量(用符號wt(x)來表示)被定義為非零分量xi的個數(shù)，即

對于任意的x，y ∈Fnq，x和y之間的Hamming 距離d(x，y)被定義為

Fnq的非空子集C被稱為一個碼長為n的q元碼，碼C的最小距離d(C)被定義為

碼C的相對最小距離δ(C)和信息率R(C)分別被定義為

若C是的k維Fq-子空間，則稱C是參數(shù)為[n，k]的q元線性碼. 顯然，q元[n，k]線性碼C的信息率為R(C)=k/n[11].

定義1(信息集) 設C ?是維數(shù)為k的線性碼. 一個集合A={i1，i2，··· ，ik} ?{1，2，··· ，n}稱為線性碼C的信息集，指C到的投影映射，即

是一個雙射.

定義2(平衡碼) 一個線性碼C被稱為平衡碼，指存在整數(shù)r≥1 和碼C的信息集A1，A2，··· ，Au，使得對于任意的i(1 ≤i≤n)，有

式中，A1，A2，··· ，Au可以相同.

在0 ≤x≤1-q-1上的q元熵函數(shù)Hq(x)被定義為

引理1[10]設線性碼C是維數(shù)為k的平衡碼，B是C的一個非空子集. 令

若0 ≤δB≤1-q-1，則

碼的各個參數(shù)之間存在著彼此制約的關系. 設αq(δ)表示Fq上相對最小距離為δ的q元碼的最大信息率. 糾錯碼的一個主要問題就是確定αq(δ)的值，而漸進的Gilbert-Varshamov 界給出了αq(δ)的一個下界.

命題1(漸進的Gilbert-Varshamov 界)[11]設q≥2. 若0＜δ≤1-q-1，則

1.2 準扭碼和不可約多項式

Fq[X]表示所有系數(shù)在Fq中的一元多項式的全體. 設n，m是兩個正整數(shù)，且滿足m | n，gcd(n，q)=1. 令l=n/m，則對于任意的a ∈Fnq可以寫成如下形式:

對于任意的λ ∈F*q，令Rm，λ表示剩余類環(huán)Fq[X]/(Xm-λ). 由于Fmq和Rm，λ之間存在Fq-線性同構，因此可將向量u= (u0，u1，··· ，um-1)∈和多項式看成是一樣的.

定義3(準扭碼) 設n，m是兩個正整數(shù)，且滿足m | n，gcd(n，q) = 1. 令l=n/m. 對于任意的λ ∈線性碼C被稱為(λ，l)-準扭碼. 具體指，若

則

特別地: 當l= 1 時，C恰為λ-常循環(huán)碼; 當λ= 1 時，C恰為指數(shù)為l的準循環(huán)碼; 當l=λ=1 時，C恰為循環(huán)碼.

定義映射

Φ是Fq上的線性同構，且有如下的性質.

命題2設n，m是兩個正整數(shù)，且滿足m|n，gcd(n，q) = 1. 令l=n/m，則對于任意的λ ∈，碼C ?Fnq是(λ，l)-準扭碼當且僅當Φ(C)是的Rm，λ- 子模.

證明 設碼C是(λ，l)-準扭碼. 由于Φ是Fq上的線性同構，因此對于加法運算、Φ(C)與有限域Fq的數(shù)乘運算都是封閉的. 在Rm，λ中Xm=λ，因此對于任意的c ∈C，有

而XΦ(c)對應C中的碼字:

故XΦ(c)∈Φ(C). 因此對于任意的r(X)∈Rm，λ，有r(X)Φ(c)∈Φ(C)，即Φ(C)是的Rm，λ-子模.

若Φ(C)是的Rm，λ-子模，則通過上面的討論可知，C是(λ，l)-準扭碼.

定義4(1-生成準扭碼) (λ，l)-準扭碼C被稱為1-生成準扭碼，指的Rm，λ-子模Φ(C)是由

生成的，并且稱a(X)為C的生成元.

類似地，也可以定義1-生成準扭碼的生成多項式.

定義5設(λ，l)-準扭碼C ?Fnq是1-生成準扭碼，且其生成元是

則稱

為1-生成準扭碼C的生成多項式.

注1若1-生成準扭碼C ?Fnq的生成多項式是g(X)，則C的維數(shù)是m-degg(X).

引理2[12]設λ ∈，整數(shù)m≥2，則多項式Xm -λ在Fq上是不可約的，當且僅當以下兩個條件同時成立: ①設λ在中的階是e，則m的每個素因子可以整除e，但不能整除(q-1)/e; ②若m ≡0 mod 4，則q ≡1 mod 4.

利用引理2，可以給出下面幾個不可約多項式的例子.

(1) 當q= 7 時，設α是的本原元，λ=α2，則對于任意的正整數(shù)e，x3e -λ在F7上是不可約的.

(2) 當q= 16 時，設α是的本原元，λ=α5，則對于任意的正整數(shù)e，x3e -λ在F16上是不可約的.

(3) 當q= 81 時，設α是的本原元，λ=α5，則對于任意的正整數(shù)e，x2e -λ在F81上是不可約的.

2 3 個引理

為了證明任意一個1-生成準扭碼有很大概率達到漸進Gilbert-Varshamov 界，先證明一些引理.

因為Fq的特征與m互素，所以多項式Xm-λ在Fq上可以分解成如下形式:

式中，f1(X)，f2(X)，··· ，fr(X)是不同的不可約多項式. 令dλ=min{degfi(X):1 ≤i≤r}.

引理3設λ ∈F*q. 令a0(X)，a1(X)，··· ，al-1(X)是從Fq[X]中隨機選取的次數(shù)小于m的多項式. 當l和m趨向于無窮，且l的增長速度大于logq m時，事件

發(fā)生的概率趨向于1.

證明 設a0(X)，a1(X)，··· ，al-1(X)是從Fq[X]中隨機選取的次數(shù)小于m的多項式，令

以下證明首一多項式d(X)=1 的概率至少是1-m/ql.

假設degd(X)≥1，則存在Xm-λ的不可約因式f(X)，使得f(X)|d(X)，即

因為a0(X)，a1(X)，··· ，al-1(X)是從Fq[X]中隨機選取的次數(shù)小于m的多項式，所以對于每一個i，f(X)|ai(X)的概率最大為

又因為Xm-λ有r個不同的不可約因式，所以degd(X)≥1 的概率最大為

這表明首一多項式d(X)=1 的概率至少為1-m/ql. 當l和m趨向于無窮，且l的增長速度大于logq m時，1-m/ql是趨向于1 的. 引理得證.

設I是Rm，λ= Fq[X]/(Xm -λ)的一個理想. 由于Rm，λ是主理想整環(huán)，因此可設I=〈h(X)〉，其中h(X)是首一多項式且h(X)|(Xm-λ)，則易知I的維數(shù)是m-degh(X).令Ωt表示主理想整環(huán)Rm，λ所有維數(shù)為t的理想組成的集合. 由文獻[6]可以類似地得到如下兩個引理.

引理4主理想整環(huán)Rm，λ維數(shù)為t的理想的個數(shù)|Ωt|滿足

證明 設I ?Rm，λ是Rm，λ維數(shù)為t的理想. 因為Rm，λ= Fq[X]/(Xm -λ)是主理想整環(huán)，所以存在唯一的首一多項式h(X)滿足h(X)|(Xm -λ)和degh(X) =m-t，使得I是由h(X)生成的.

由

式中，f1(X)，f2(X)，··· ，fr(X)是不同的不可約多項式，可以得到

其中fi1(X)，fi2(X)，··· ，fiv(X)是Xm-λ的不可約因式. 因為degh(X)=m-t，degfij(X)≥dλ(1 ≤j≤v)，所以式(2)右端中最多有t/dλ個因式，進而h(X)最多有rt/dλ種選擇，故

引理得證.

引理5設I是Rm，λ維數(shù)為t的理想，w是滿足0 ≤w≤(1-q-1)m的整數(shù). 令

有

證明 設I是主理想整環(huán)Rm，λ維數(shù)為t的理想，則I對應于Fq上一個維數(shù)為t的λ-常循環(huán)碼CI. 設J是CI的一個信息集，定義

因為CI是一個常循環(huán)碼，所以σ(J)也是CI的一個信息集. 在信息集{σi(J) : 0 ≤i≤m -1}中，每個i恰好包含在|J|個信息集里，則CI是平衡碼. 由引理1 可令B=I(w)，，因此

引理得證.

3 達到Gilbert-Varshamov 界的準扭碼

利用群環(huán)上的群作用，Bazzi等[6]和Fan等[10]證明了準阿貝爾群碼可以達到Gilbert-Varshamov 界. 本工作類似地證明了1-生成準扭碼也可以達到Gilbert-Varshamov 界. 首先給出這類準扭碼的構造.

設

式中，a0(X)，a1(X)，··· ，al-1(X)是從Fq[X]中隨機選取的次數(shù)小于m的多項式. 令Ca表示由a(X)生成的碼長為n=ml的1-生成(λ，l)-準扭碼.

定理1設Ca是由式(6)中a(X)生成的準扭碼，且

若0＜δ≤1-q-1，且

則Ca的相對最小距離小于δ的概率不超過

證明 令P表示準扭碼Ca的最小距離小于lmδ的概率. 對于非零多項式f(X)∈Rm，λ，E(f，a)表示事件

式中，wt(f(X))表示多項式f(X)非零系數(shù)的個數(shù)，則

其中Dt:={f(X)∈Rm，λ:deg(gcd(f(X)，Xm-λ))=m-t}，Pra[E(f，a)]表示事件E(f，a)發(fā)生的概率. 對于任意的多項式f(X)∈Rm，λ