一類循環(huán)碼的準循環(huán)子碼

凌國慶, 朱士信

(合肥工業(yè)大學 數(shù)學學院,安徽 合肥 230601)

0 引 言

在經(jīng)典糾錯碼理論中,循環(huán)碼有著良好的代數(shù)結構,它不僅在構造方面有一定的優(yōu)勢,而且在譯碼方面也有著成熟的理論,因此在糾錯碼理論中占有重要的地位。

文獻[1]首次將循環(huán)碼推廣到了準循環(huán)碼。若長度為ml的線性碼C的任一碼字經(jīng)過l次循環(huán)移位后仍屬于C,且l是具有該性質的最小正整數(shù),則C被稱為指數(shù)為l的準循環(huán)(quasi-cyclic code,QC)碼。

近年來,QC碼由于其可得到一些好的參數(shù)的碼而得到廣泛的關注,例如碼表中碼[256, 23, 104]和[102, 26, 32]等[2-3]。文獻[4]研究了環(huán)Fp+uFp+…+ukFp上的準循環(huán)碼,并指出該環(huán)上準循環(huán)碼可看作環(huán)Fp上的準循環(huán)碼;文獻[5]研究了環(huán)R=Zps上長為mn的準循環(huán)碼的結構,確定了其等價于An的A-子模,其中A=R[x]/(xm-1);文獻[6]研究了環(huán)Fq+uFq(u2=0)上準循環(huán)碼的結構,確定了該環(huán)上任意長度準循環(huán)碼的生成元表示形式及其最小生成元集。

超奇異曲線上有理點的數(shù)目與循環(huán)碼的一些確定子碼的重量分布有關,并且這些子碼都是QC碼[7],因此循環(huán)碼的QC子碼得到了廣泛關注。文獻[8]利用循環(huán)碼的跡表示[9]得到了一類循環(huán)碼的QC子碼的所有可能的指數(shù)及對應于某一指數(shù)的QC子碼的個數(shù)。

本文分3種情況討論了任意長度的雙糾錯二元本原BCH碼對偶碼的QC子碼的指數(shù)及對應于指數(shù)的個數(shù)結果。

1 預備知識

令n和N為滿足N=qn-1的正整數(shù),α為N次本原單位根。若C為Fq上碼長為N的循環(huán)碼,且對偶碼的零點為αi1,…,αis,其中，ij≥1對任意j成立且ij來自于模N的兩兩不同的q-分圓陪集,則C的跡表示[9]為:

C={(TrFqn/Fq(λ1αki1+…+λsαkis))0≤k≤N-1:

λj∈Fqn,1≤j≤s}

(1)

考慮C的線性子碼:

C′={(TrFqn/Fq(β1αki1+…+βsαkis))0≤k≤N-1:

βj∈Vj?Fqn, 1≤j≤s}

(2)

其中,Vj為Fqn的線性子空間。

若對j(1≤j≤s),ij所在的分圓陪集的大小均為n,則有如下引理成立。

定義集合

1≤a1,…,am≤u,1≤t1,…,tm≤s;

若i≠j,則ti≠tj}{qn-1},

對?l∈I,C有指數(shù)為l的QC子碼,且沒有任何其他指數(shù)的QC子碼。

記A={A1,…,As}表示Fqn的線性子空間集,并定義了形如(2)式的子碼CA。顯然,對于2個線性子空間集A={A1,…,As}、B={B1,…,Bs},定義子碼CA和CB,CA=CB當且僅當Aj=Bj對?j(1≤j≤s)成立。故C的指數(shù)為l的QC子碼的個數(shù)等于使得CV為C的指數(shù)為l的QC子碼的Fqn的線性子空間集V={V1,…,Vs}的數(shù)目。

Fqn的非零Fq-子空間的個數(shù)由下列q-二項式系數(shù)決定:

(3)

{(x1,…,xt):xj∈{0,1,…,aj}, 1≤j≤t}。

對于域F,P為F的子空間,F1為F的子域。若P是F1-子空間,但對任意滿足F1?F2?F的域F2來說,P不是F2-子空間,則稱P為域F的極大F1-子空間。

2 BCH碼對偶碼的QC子碼

令n和N為正整數(shù),且有N=2n-1,并令α為N次本原單位根,則碼長為N的二元雙糾錯BCH碼對偶碼的跡表示為:

C={TrF2n/F2(λαk+βα3k)0≤k≤N-1:λ,β∈F2n}

(4)

注意到,當n≠2時,1所在的模N的2-分圓陪集為C1={1,2,22,…,2n-1},該集合中元素個數(shù)為n;3所在的模N的2-分圓陪集為C3={3,3·2,3·22,…,3·2n-1},下面證明該集合中元素個數(shù)也為n。

假設C3中元素個數(shù)小于n,則存在i(0

當n=2時,碼長太短,不予考慮。故對循環(huán)碼C,可以應用引理1。

考慮C的線性子碼:

C′={TrF2n/F2(λ1αk+β1α3k)0≤k≤N-1:

λ1∈V?F2n,β1∈W?F2n}

(5)

其中,V、W為F2n的線性子空間。有如下2個結論:

(1) 設d1滿足V為F2d1-子空間,d1|n,且d1為滿足這樣性質的最大正整數(shù);d2滿足W為F2d2-子空間,d2|n,且d2為滿足該性質的最大正整數(shù)。

令l=lcm(l1,l2),若l≠2n-1=N,則C′是C的指數(shù)為l的QC子碼。

(2) 令F2d1,…,F2du為擴張F2n/F2的全部中間域,其中,d1=1;du=n。對j′(1≤j′≤u),令

則由引理2知,Ai表示F2n的非零極大Fi-子空間的個數(shù)。記

對j=(j1j2…jk)∈H,令min{i,j}=m=(m1…mk),其中,ml=min{il,jl}對?l(1≤l≤k)成立。

定理1 lcm(Li,Lj)=Lm,其中,m=min{i,j}。

其次有：

下面將分3種情形(情形1:2|/n;情形2:2|n但3|/n;情形3:2|n且3|n)來計算二元雙糾錯BCH碼對偶碼的QC子碼的指數(shù)及對應于確定指數(shù)的QC子碼的個數(shù)。

情形12不整除n。

I={Li:i=(i1i2…ik)∈H且i≠0}。

證明記I1=I2={Li:i=(i1…ik)∈H},I3={lcm(Li,Lj):i,j∈H}。

由定理1知,lcm(Li,Lj)=Lm,其中,m=min{i,j}∈H,因此I3=I1=I2。注意到L0=2n-1,有I=(I1∩I2∩I3){2n-1}={Li:i=(i1i2…ik)∈H且i≠0}。

證明C的一個QC子碼具有如下形式:

C′={TrF2n/F2(λαk+βα3k)0≤k≤N-1:

λ∈V?F2n,β∈W?F2n},

其中,V、W?F2n為定義在擴張F2n/F2的某個中間域上的子空間。

為簡便起見,用V:Fi表示V是極大Fi-子空間,W=0表示W(wǎng)為零子空間,則可得到指數(shù)為Li的QC子碼的V和W的選擇,列舉如下:

V:Fi,W=0;V=0,W:Fi;

V:Fj,W:Fm滿足min{j,m}=i。

以上各種選擇方法的個數(shù)分別為:

以上3項相加即可得到結果。

情形2 2整除n但3不整除n。

I={Li:i∈H且i≠0}∪{Li/3:

i∈H且i1=0且i≠0}。

注意到L0/3=L(1 0 … 0),于是有I′=(I1∪I2){2n-1}。

下證I3?I1∪I2,即可得到I=(I1∪I2∪I3){2n-1}=I′。

當i1≠0時,有3|/Li,因為3|Lm且Li|Lm,故Li|Lm/3,所以lcm(Li,Lj/3)=Lm/3∈I2。

綜上可得I3?I1∪I2。

證明(1) 得到指數(shù)為Li(i=(1 0 … 0))的QC子碼的V和W的選擇可列舉如下:

V:Fi=F4,W=0;V=0,W:Fi=F4;

V=0,W:F0=F2;

V:Fj,W:Fm滿足:min{j,m}=0,

j1≠0,m1=0;

V:Fj,W:Fm滿足min{j,m}=i,m1≠0。

以上各種選擇方法的個數(shù)分別為:

(2) 得到指數(shù)為Li(i≠(1 0 … 0),i1≠0)的QC子碼的V和W的選擇可列舉如下:

V=0,W:Fi;V:Fi,W=0;

V:Fj,W:Fm滿足min{j,m}=i,m1≠0。

以上各種選擇方法的個數(shù)分別為:

(3) 得到指數(shù)為Li(i1=0)的QC子碼的V和W的選擇可列舉如下:

V:Fi,W=0;

V:Fj,W:Fm滿足min{j,m}=i,m1≠0;

V:Fj,W:Fm滿足min{j,m}=i,j1=m1=0。

以上各種選擇方法的個數(shù)分別為:

(4) 得到指數(shù)為Li/3(i1=0,i≠0)的QC子碼的V和W的選擇可列舉如下:

V=0,W:Fi;V:Fj,

W:Fm滿足min{j,m}=i,j1≠0,m1=0。

以上各種選擇方法的個數(shù)分別為:

情形32整除n且3整除n。

I={Li:i≠0}∪{Li/3:i1=0或i2≠a2,i≠0}。

證明與定理4證明類似。

(6)Ai個指數(shù)為Li/3的QC子碼,其中,i1≠0,i2=a2。

證明與定理5證明類似。

3 結 論

對于長度為N=2n-1的二元雙糾錯BCH碼的對偶碼C,本文通過對n進行如下分類:2|/n、2|n但3|/n、2|n且3|n,解決了C的QC子碼的指數(shù)及對應于確定指數(shù)的QC子碼個數(shù)2個大問題。