盧嘯華，王永超，丁 洋

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

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

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

1 預(yù)備知識(shí)

1.1 線性碼

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

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

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

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

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

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

是一個(gè)雙射.

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

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

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

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

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

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

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

1.2 準(zhǔn)扭碼和不可約多項(xiàng)式

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

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

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

則

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

定義映射

Φ是Fq上的線性同構(gòu)，且有如下的性質(zhì).

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

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

而XΦ(c)對(duì)應(yīng)C中的碼字:

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

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

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

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

類似地，也可以定義1-生成準(zhǔn)扭碼的生成多項(xiàng)式.

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

則稱

為1-生成準(zhǔn)扭碼C的生成多項(xiàng)式.

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

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

利用引理2，可以給出下面幾個(gè)不可約多項(xiàng)式的例子.

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

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

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

2 3 個(gè)引理

為了證明任意一個(gè)1-生成準(zhǔn)扭碼有很大概率達(dá)到漸進(jìn)Gilbert-Varshamov 界，先證明一些引理.

因?yàn)镕q的特征與m互素，所以多項(xiàng)式Xm-λ在Fq上可以分解成如下形式:

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

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

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

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

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

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

因?yàn)閍0(X)，a1(X)，··· ，al-1(X)是從Fq[X]中隨機(jī)選取的次數(shù)小于m的多項(xiàng)式，所以對(duì)于每一個(gè)i，f(X)|ai(X)的概率最大為

又因?yàn)閄m-λ有r個(gè)不同的不可約因式，所以degd(X)≥1 的概率最大為

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

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

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

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

由

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

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

引理得證.

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

有

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

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

引理得證.

3 達(dá)到Gilbert-Varshamov 界的準(zhǔn)扭碼

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

設(shè)

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

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

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

則Ca的相對(duì)最小距離小于δ的概率不超過(guò)

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

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

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