幾類二元等重碼的構(gòu)造

周四維,張莉,李躍新

(1.湖北大學知行學院,湖北 武漢 430011；2.湖北大學數(shù)學與計算機科學學院,湖北 武漢 430062)

等重碼,尤其是二元等重碼在糾錯碼理論和通信理論中都有著重要的應(yīng)用,如它在差錯控制系統(tǒng)(ARQ)[1-2]中的應(yīng)用.作為一種檢測碼,其應(yīng)用非常簡單,在檢測中只需檢測接受到碼字中1的數(shù)目就可確定傳輸是否正確.

一個參數(shù)為(n,M,d,w)的等重碼指的是一類碼字的長度為n,所含碼字的個數(shù)為M,碼字之間的極小漢明距離為d且每個碼字的漢明重量均為w的碼.關(guān)于等重碼的研究,主要涉及到3個方面的問題.其一是關(guān)于等重碼的構(gòu)造,即如何構(gòu)造參數(shù)為(n,M,d,w)的等重碼.其二是對于給定的參數(shù)為(n,d,w)的等重碼,確定其理論上存在的碼字個數(shù)的理論界.一般地,這個理論上存在的碼字最大個數(shù)記為A(n,d,w).其三是在前一問題的基礎(chǔ)上確定A(n,d,w)的具體值并構(gòu)造出相應(yīng)參數(shù)的碼.相對于等重碼的構(gòu)造而言,碼所含碼字個數(shù)的研究比較困難.如果等式M=A(n,d,w)成立,則稱一個該參數(shù)為(n,M,d,w)的等重碼是最優(yōu)的.關(guān)于等重碼的構(gòu)造,可參見文獻[3-6],其中亦包含一些最優(yōu)等重碼.而關(guān)于等重碼的碼字個數(shù)的理論界,可參見文獻[7-8].至于A(n,d,w)的具體值的研究,可參考文獻[9].

本文中主要討論二元等重碼的構(gòu)造并分析所得碼是否是最優(yōu)這兩個方面的問題.首先通過差集和幾乎差集所對應(yīng)的序列來構(gòu)造等重碼,并詳細討論所得等重碼的各個參數(shù).考慮到差集所對應(yīng)序列具有兩值自相關(guān)性以及幾乎差集對應(yīng)三值自相關(guān)序列,并給出一個基于單條序列的等重碼的一般構(gòu)造方法.這是本文中的第一部分,即等重碼的構(gòu)造.第二部分即是分析上述所構(gòu)造的等重碼的最優(yōu)性問題.從這一部分的討論可以知道,在這類構(gòu)造中,從碼字的個數(shù)來看,基于差集構(gòu)造出的等重碼較之其他幾類要好些,這是由構(gòu)造方法所決定的.并且,從中得到了一類最優(yōu)等重碼.需要說明的事,這類碼的參數(shù)不全是新的,其中只有部分是新的.另外,有些碼的參數(shù)雖然不是新的,但對應(yīng)的碼字是新的.

1 預備知識

1.1碼的參數(shù)介紹對于一個長度為n的碼x=(x1,x2,…,xn),它的漢明重量wt(x)定義為碼字中非零元的個數(shù),即wt(x)=|{i:xi≠0,1≤i≤n}|.兩個碼字之間的漢明距離則定義為

d(x,y)=|{i:xi≠yi,1≤i≤n}|,

其中y=(y1,y2,…,yn).若x和y都是二元碼,則d(x,y)=wt(x⊕y),其中⊕表示模2運算.

設(shè)C是一個含有M個碼字的碼,即C={ci:1≤i≤M},碼C的極小距離定義為

d=min{d(ci,cj):ci,cj∈C,i≠j}.

碼的極小距離是一個非常重要的概念,它與碼的糾錯能力密切相關(guān).比如對于一個分組碼來說,若要在碼字內(nèi)檢測出d個隨機錯誤,則要求碼的極小距離至少是d+1；若要碼字內(nèi)糾正d個隨機錯誤,則要求碼的極小距離至少是2d+1[3].

1.2 序列的相關(guān)函數(shù)

定義1設(shè)a={a(0),a(1),…,a(N-1)}和b={b(0),b(1),…,b(N-1)}是兩個周期為N的二元序列,它們之間的周期相關(guān)函數(shù)在移位0≤τ≤N-1處的定義為

其中i+τ為模N運算.

1.3循環(huán)差集差集與序列,尤其是二元最優(yōu)序列之間具有緊密的聯(lián)系.在這一小節(jié)中,我們主要介紹循環(huán)差集和幾乎差集的概念以及它們的一些簡單性質(zhì).

定義2設(shè)G是一個階為υ的加法群,令D={d1,d2,…,dk}.如果G中每一個非零元在多重集{d1-d2:d1,d2∈D,d1≠d2}中恰好出現(xiàn)λ次,則稱D是一個參數(shù)為(υ,k,λ)的差集.特別地,如果G為循環(huán)群Zυ=Z/υZ,那么稱D是一個參數(shù)為(υ,k,λ)的循環(huán)差集.

差集是一個重要的數(shù)學工具.在本文中,我們只需用到差集的一些簡單性質(zhì).更多關(guān)于差集的敘述可參見文獻[10].

引理1[10]設(shè)D={d1,d2,…,dk}是一個參數(shù)為(υ,k,λ)的循環(huán)差集,則有k(k-1)=(υ-1)λ,且D的補集是一個參數(shù)為(υ,υ-k,υ-2k+λ)的循環(huán)差集.

定義3設(shè)(A,+)是一個階為n的Abel群,令S={s1,s2,…,sk}.當w取遍A中所有非零元時,如果|{s+w:s∈S}∩S|等于λ總共出現(xiàn)μ次以及等于λ+1總共出現(xiàn)n-1-μ次,則稱S是一個參數(shù)為(υ,k,λ,μ)的幾乎差集.

與差集類似,幾乎差集也有類似于引理1的性質(zhì),在此不再詳述.

2 二元等重碼的構(gòu)造

(1)

對由差集構(gòu)造的上述二元序列s,它的自相關(guān)函數(shù)是兩值的,具體結(jié)論如下.

根據(jù)上面的引理,我們首先可以通過如下方式構(gòu)造一類等重碼.

構(gòu)造1設(shè)序列s由參數(shù)為(υ,k,λ)的差集如(1)式所定義,且令L為左循環(huán)移位算子,即Li(s)=(si,si+1,…,si-1),其中下標進行的是模υ運算.定義集合C1={Lτ(s):0≤τ≤υ-1}

(2)

基于構(gòu)造1得到的等重碼具有以下性質(zhì).

定理1如(2)式定義的集合C1構(gòu)成一個參數(shù)為(υ,υ,2k-2λ,υ-k)的二元等重碼.

定理1的證明根據(jù)序列s和集合C1的定義,C1中的碼字的長度為υ,碼字的漢明重量為υ-k,且集合C1所含有的碼字個數(shù)為υ.因此,我們只需討論C1中碼字之間的距離.任取C1中的兩個碼字c1=Lτ1(s),c2=Lτ2(s),0≤τ1,τ2≤υ-1.于是,C1和C2之間的漢明距離為d=wt(Lτ1(s)⊕Lτ2(s)).

不失一般性,假設(shè)τ2>τ1,則由移位算子L的定義不難驗證

d=wt(Lτ1(s)⊕Lτ2(s))=wt(s⊕Lτ2-τ1(s)).

繼而可得 (υ-wt(s⊕Lτ2-τ1(s)))-wt(s⊕Lτ2-τ1(s))=υ-4k+4λ,

即d=wt(s⊕Lτ2-τ1(s))=2k-2λ,

證畢.

通過序列的自相關(guān)函數(shù),我們還可以通過以下方式構(gòu)造出另一類等重碼.

構(gòu)造2設(shè)序列s由參數(shù)為(υ,k,λ)的差集如(1)式所定義,且令L為左循環(huán)移位算子,定義集合

C2={s⊕Lτ(s):Rs(τ)=υ-4k+4λ,1≤τ≤υ-1}

(3)

對于上述定義的集合C2,我們可以證明以下結(jié)論.

定理2如(3)式定義的集合C2構(gòu)成一個參數(shù)為(υ,υ-1,2k-2λ,2k-2λ)的二元等重碼.

定理2的證明由集合C2的定義可知,C2中含有一個υ-1個碼字且碼字的長度為υ.任務(wù)C2中的一個碼字C=s⊕Lτ(s),1≤τ≤υ-1.不妨設(shè)C的漢明重量為w,則根據(jù)序列s的自相關(guān)函數(shù)值可得

即有w=wt(c)=2k-2λ.因此,下面我們需要證明C中碼字之間的極小距離也是2k-2λ.任取C2中的兩個碼字c1=s⊕Lτ1(s),c2=s⊕Lτ2(s),1≤τ1,τ2≤υ-1.于是,結(jié)合碼字之間距離的定義可知,C1和C2之間的漢明距離為d=wt(s⊕Lτ1(s)⊕s⊕Lτ2(s))=wt(Lτ1(s)⊕Lτ2(s)).

仍然假設(shè)τ2>τ1,則可驗證d=wt(Lτ1(s)⊕Lτ2(s))=wt(s⊕Lτ2-τ1(s)).

故而,類似前面關(guān)于碼字重量的討論,有d=2k-2λ.證畢.

推論1若υ=3k-2λ,則C2∪{s}構(gòu)成一個參數(shù)為(υ,υ,2k-2λ,2k-2λ)的二元等重碼.

推論1的證明由序列s的定義,即(1)式可知,wt(s)=υ-k.所以結(jié)合已知條件υ=3k-2λ可知,wt(s)=υ-k=2k-2λ.另一方面,s與C2中碼字之間的距離為

d=wt(s⊕s⊕Lτ(s))=wt(Lτ(s))=wt(s).

于是,再根據(jù)定理2可知上述推論成立.證畢.

對于一個參數(shù)為(υ,k,λ)的差集,由引理1有(υ-1)λ=k(k-1),再結(jié)合條件υ=3k-2λ,消去參數(shù)υ可解得k=2λ+1或k=λ,其中解k=λ需舍棄,否則得到υ=k=λ,所以代入k=2λ+1,有υ=4λ+3,即推論1中對應(yīng)的差集參數(shù)為(4λ+3,2λ+1,λ).注意到此時Rs(τ)=υ-4k+4λ=-1,即序列s是一個理想兩值自相關(guān)序列.

需要說明的是,在一定條件下,C1和C2∪{s}是一致的.為了得到不同類的碼,下面我們給出C1和C2∪{s}不等價的條件.為此,我們需要以下定義.

定義4對于一個周期為N的二元序列s,我們稱序列s具有三項式特性,如果對任一i,1≤i≤N-1,均存在一個j,1≤j≤N-1使得s⊕Li(s)=Lj(s)成立.

比如,m序列就是一個具有三項式特性的序列.事實上,具有三項式特性的序列并不多.而且,具有理想兩值自相關(guān)的序列不一定就具有三項式特性.

關(guān)于構(gòu)造1和構(gòu)造2之間的關(guān)系,我們有

命題1對于構(gòu)造1和構(gòu)造2中的序列s,若s具有三項式特性,則C1和C2∪{s}是同一碼；否則,則C1和C2∪{s}是不同的兩種碼.

上述構(gòu)造1和構(gòu)造2都是從兩值自相關(guān)序列而來,通過自相關(guān)函數(shù)取值的分布性質(zhì),從不同的組合方式來構(gòu)造等重碼.構(gòu)造的關(guān)鍵是兩值自相關(guān)序列,本質(zhì)是差集.自然地,我們想知道,如果(1)式的定義中,集合D是一個幾乎差集,結(jié)果會是怎樣呢？我們是否可以構(gòu)造新的等重碼？

類似地,與引理2一樣,我們有下面的引理.

引理3[11]設(shè)二元序列s=(s0,s1,…,sυ-1)是由參數(shù)為(υ,k,λ,μ)的幾乎差集D定義的如(1)式的序列,則序列s的自相關(guān)函數(shù)是三值的,且當τ取遍{0,1,…,υ-1}時,自相關(guān)函數(shù)的分布為

構(gòu)造3設(shè)序列s由參數(shù)為(υ,k,λ,μ)的幾乎差集如(1)式所定義,且令L為左循環(huán)移位算子,定義集合C3={Lτ(s):0≤τ≤υ-1}

(4)

結(jié)合引理3,我們可證明下面的結(jié)論.

定理3如(4)式定義的集合C3構(gòu)成一個參數(shù)為(υ,υ,d,υ-k)的二元等重碼,其中d≥2k-2λ-2,且碼字之間的距離是2k-2λ或者是2k-2λ-2.

定理3證明由序列s的定義,集合C3中的碼字長度為υ,碼字的漢明重量為υ-k且C3中含有的碼字個數(shù)為υ.下面,我們討論C3中碼字之間的距離.任取C3中的兩個碼字c1=Lτ1(s),c2=Lτ2(s),τ1≠τ2且0≤τ1,τ2≤υ-1.于是,C1與C2之間的漢明距離為

d=wt(Lτ1(s)⊕Lτ2(s)).

類似于定理1中的討論,結(jié)合序列的自相關(guān)函數(shù)即引理3,不難得到

d=2k-2λ,或d=2k-2λ-2.

證畢.

與差集對應(yīng)的序列類似,利用幾乎差集定義的序列也能用來構(gòu)造形如

的二元等重碼.

類似于定理2 的證明,我們可得到如下結(jié)論.

從上面的構(gòu)造可以看出,通過差集或者是幾乎差集可以構(gòu)造出不同參數(shù)的二元等重碼.事實上,從序列的角度來看,基于序列的自相關(guān)性,也可以構(gòu)造二元等重碼.而且,可以將上面的構(gòu)造推廣到一般情形.

設(shè)二元序列s=(s0,s1,…,sυ-1),且當τ取遍{0,1,…,υ-1}時,自相關(guān)函數(shù)的分布為

(5)

構(gòu)造4設(shè)二元序列s的自相關(guān)函數(shù)滿足(5)式,定義集合C4={Lτ(s):0≤τ≤υ-1}

(6)

類似于定理3的證明,不難得到如下結(jié)論.

定理4設(shè)u=max{u1,u2,…,um},則如(6)式定義的C4構(gòu)成一個參數(shù)為(υ,υ,d,w)的二元等重碼,其中w=wt(s)且d≥(υ-u)/2.

則也有如下類似結(jié)果.

3 碼的參數(shù)分析及實例

對于一個給定參數(shù)為(n,M,d,w)的等重碼,它的最優(yōu)性的討論是一個比較困難的問題.首先,需要找到合適的關(guān)于A(n,d,w)的理論上界.對于不同參數(shù)的(n,d,w)等重碼,人們從不同角度討論了A(n,d,w)的理論上界,也得到了一些結(jié)果,如Plotkin界[12],Johnson界[7]等.其次,需要證明M=A(n,d,w).在這一節(jié)中,我們引用非遞歸的Johnson界[7]或文獻[13]中討論常復合碼的界來分析上一節(jié)中所構(gòu)造出來的等重碼,因為對于二元而言,常復合碼實際上就是等重碼.

引理4[14]對于一個參數(shù)為(n,d,w)的二元等重碼,如果nd-2nw+2w2>0,則

下面我們就用這個理論界來分析第2部分中所構(gòu)造出來的部分等重碼.

設(shè)D是一個參數(shù)為(υ,k,λ)的循環(huán)差集,且滿足條件υ-4k+4λ=-1.則由定理1可知,此時C1構(gòu)成一個參數(shù)為(υ,υ,2k-2λ,υ-k)的等重碼.根據(jù)命題1有k(k-1)=λ(υ-1),再結(jié)合條件υ-4k+4λ=-1可得υ=2k+1或者υ=2k-1.于是可討論如下情形.

(1)若υ=2k+1.此時有(υ,k,λ)=(4λ+3,2λ+1,λ).于是

nd-2nw+2w2=υ(2k-2λ)-2υ(υ-k)+2(υ-k)2=2(λ+1)>0.

另一方面,由定理1可知,參數(shù)為(υ,υ,2k-2λ,υ-k)的等重碼已構(gòu)造出來,由定義即有A(n,d,w)≥υ,因此A(n,d,w)=υ.故而此時C1是最優(yōu)的.

(2)若υ=2k-1.此時有(υ,k,λ)=(4λ-1,2λ,λ).從而

nd-2nw+2w2=υ(2k-2λ)-2υ(υ-k)+2(υ-k)2=2λ>0.

類似(1)可知A(n,d,w)=υ.故而此時C1是最優(yōu)的.

命題2設(shè)D是一個參數(shù)為(υ,k,λ)的循環(huán)差集,且滿足條件υ-4k+4λ=-1.則由構(gòu)造1得到的等重碼C1是最優(yōu)碼.

因υ-4k+4λ=-1,由引理2,此時對應(yīng)的即是二元理想兩值自相關(guān)序列.從序列的角度,比如m序列,一些相應(yīng)的最優(yōu)二元等重碼已經(jīng)構(gòu)造出來.因此命題2中所得到的最優(yōu)二元等重碼在參數(shù)上并不都是新的.再結(jié)合命題1可知,若差集對應(yīng)的二元序列不具有三項式特性,則等重碼C2∪{s}不同于C1且是最優(yōu)的,更重要的是,C2∪{s}中的碼字之間不循環(huán)等價.值得考慮的是,對于υ-4k+4λ≠-1的情況,是否會得到最優(yōu)二元等重碼？

例1設(shè)D是一個參數(shù)為(2n-1,2n-1,2n-2)的Singer差集,則由構(gòu)造1得到的是參數(shù)為(2n-1,2n-1,2n-1,2n-1-1)的最優(yōu)等重碼.

例3設(shè)D是一個參數(shù)為(4N,2N,N-1,N)的幾乎差集,則基于(1)式定義的序列的自相關(guān)分布滿足條件

于是由構(gòu)造3可知,C3此時是一個參數(shù)為(4N,4N,2N,2N)的二元等重碼.驗證可知,這類碼不能用引理4來判定它是否最優(yōu).這類碼的參數(shù)比較特殊,它的最優(yōu)性與4N階Hadamrd矩陣的存在與否有著密切的聯(lián)系,見文獻[14].如果不存在4N階Hadamrd矩陣,這類碼能否達到最優(yōu)尚不可知.

4 結(jié)論

本文中主要給出了幾類基于單個序列構(gòu)造的二元等重碼,并結(jié)合碼的定義和序列的自相關(guān)性確定了碼的各個參數(shù).通過分析碼的最優(yōu)性表明,序列自相關(guān)函數(shù)取值個數(shù)越少,所構(gòu)造的等重碼的參數(shù)可能就會越好.結(jié)合已有的理論界,我們證明了基于理想兩值自相關(guān)序列構(gòu)造的等重碼可以達到最優(yōu).對于其他情況,是否還能找到最優(yōu)等重碼尚不可知,這是下一步要研究的問題.

[1] Wang X M,,Yang Y X.On the undetected error probability of nonlinear binary constantweight codes[J].IEEE Trans Commu,1994,42(7):2390-2393.

[2] Fu F W,Xia S T.Binary constant weight codes for error detection[J].IEEE Trans Inform Theory,1998,44(3):1294-1299.

[3] MacWilliams F J,Sloane N J.The theory of error-correcting codes[M].Amsterdam,The Netherlands:North-Holland,1977.

[4] Chee Y M,Ling S. Constructions for q-ary constant-weight codes[J].IEEE Trans Inform Theory,2007,53(1):135-146.

[5] Fu F W,Han Vinck A J,Shen S Y.On the construction of constant-weight codes[J].IEEE Trans Inform Theory,1998,44(1):328-333.

[6] Zeng F X. Properties ofm-sequence and construction of constant weight codes[J].IEICE Trans Fundamentals,2005, E88-A(12):3675-3676.

[7] Johnson S M.A new upper bound for error-correcting codes[J].IEEE Trans.Inform.Theory,1962,8(3):203-207.

[8] Agrell E,Vardy A,Zeger K.Upper bounds for constant-weight codes[J].IEEE Trans Inform Theory,2000,46(7):2373-2395.

[9] Brouwer A E,Shearer James B,Sloane N I A,et al.A new table of constant weight codes[J].IEEE Trans Inform Theory,1990, 36(6):1344-1380.

[10] Baumert L D.Cyclic difference sets[M].New York:Springer-verlag,1971.

[11] Arasu K T,Ding C,Helleseth T,et al. Almost difference sets and their sequences with optimal autocorrelation[J].IEEE Trans Inf Theory, 2001,47(7):2934-2943.

[12] Ploktin M.Binary codes with specified minimum distance[J].IEEE Trans Inf Theory, 1960,6(4):445-450.

[13] Luo Y,Fu F W,Vinck A J H,et al.On constant composition codes overZq[J].IEEE Trans Inf Theory,2003,49(11):3010-3016.

[14] Semakov K V,Zinoviev V A.Balanced codes and tactical configurations(in Russian)[J].Probl Peredach Inform,1969,5(3)：28-37.