一類有限非鏈環(huán)上的循環(huán)碼及其Gray映射

鐘家偉

（安徽信息工程學(xué)院 通識(shí)教育與外國(guó)語學(xué)院，蕪湖 241000）

有限環(huán)上的循環(huán)碼因其生成矩陣形式較為簡(jiǎn)單，編碼譯碼方面容易實(shí)現(xiàn)，因此在數(shù)字通信中得到廣泛的應(yīng)用，是一類重要的線性碼。有限環(huán)上的循環(huán)碼目前被廣泛的應(yīng)用于代數(shù)編碼的理論中，并且取得了矚目的成就。近年來，隨著通信技術(shù)對(duì)編碼要求的提升，編碼理論的研究從有限鏈環(huán)上碼的研究延伸至有限非鏈環(huán)上碼的研究，構(gòu)造出了許多參數(shù)接近各種界的最優(yōu)碼。BETSUMIYA K 和 ZHU 等人［1-2］對(duì)環(huán)F2+vF2上的線性碼與循環(huán)碼進(jìn)行了研究。ZHU等人隨后在文獻(xiàn)［3］中將相關(guān)結(jié)論推廣至環(huán)Fp+vFp(v2=v)上，得到環(huán)上的(1-2v)常循環(huán)碼的構(gòu)造方法。YILDIZ B等人［4-6］對(duì)環(huán)F2+vF2+uF2+uvF2上的循環(huán)碼和自對(duì)偶碼的相關(guān)結(jié)構(gòu)和性質(zhì)進(jìn)行了研究。文獻(xiàn)［7-8］分別介紹了環(huán)F2+vF2+uF2+uvF2上兩類常循環(huán)碼的結(jié)構(gòu)，并通過所構(gòu)造的Gray映射得到了一系列最優(yōu)碼和漸進(jìn)優(yōu)碼。文獻(xiàn)［9］研究Fp+vFp+uFp+uvFp上的Gray映射得到其上一類常循環(huán)碼。近年來，有限非鏈環(huán)的研究取得了許多成果［10-12］，文獻(xiàn)［13］介紹了利用環(huán)Fp+uFp+u2Fp+vFp+uvFp+u2vFp+v2Fp+uv2Fp+u2v2FP的λ-常循環(huán)碼得出一類構(gòu)造量子碼的方法。

為了能夠得出更多符合現(xiàn)代通信技術(shù)需求的具有良好參數(shù)的最優(yōu)碼，首先通過計(jì)算給出了環(huán)F2+uF2+vF2+uvF2上極大理想，研究了環(huán)F2+uF2+vF2+uvF2上循環(huán)碼的結(jié)構(gòu)。定義了環(huán)F2+uF2+vF2+uvF2上碼長(zhǎng)為n的循環(huán)碼到二元域上長(zhǎng)為4n的準(zhǔn)循環(huán)碼的Gray映射，并證明其保距性。研究得出此類環(huán)上循環(huán)碼存在的充要條件，最后舉例說明一類二元準(zhǔn)循環(huán)最優(yōu)碼的構(gòu)造方法。

1 環(huán)?上線性碼

令環(huán) ? =F2+uF2+vF2+uvF2，其中u2=0，v2=v，uv=vu，R=F2+uF2，則可知?=R[v]/(v2-v)。計(jì)算得出?的理想：

可知?是一個(gè)有限非鏈環(huán)，故?不是局部環(huán)，?的極大理想為(u+v)和(1+u+v)。

令C是?上長(zhǎng)為n的碼字，即為?n的一個(gè)子集。若C是?n的一個(gè)?-子模，則稱C為?上長(zhǎng)為n的線性碼。記??為?的非零子集，給定任意λ∈R?，定義?上的λ-循環(huán)移位為σλ(x0,x1,…,xn-1)=(λxn-1,x0,…,xn-2)。當(dāng)λ=1時(shí)，有σ(C)=C成立，則稱C為?上的循環(huán)碼。C上的碼字c=(c0,c1,…,cn-1)可以等價(jià)表示為n-1次多項(xiàng)式c(x)=c0+c1x+ … +cn-1xn-1，則?上長(zhǎng)為n的碼等價(jià)于商環(huán)?[x]/(xn-1)的多項(xiàng)式，xc(x)為c(x)在?[x]/(xn-1)中的一個(gè)循環(huán)移位。?可以看作R上的向量空間，?上長(zhǎng)為n的循環(huán)碼是環(huán)?[x]/(xn-1)的一個(gè)理想。

2 環(huán)?上的循環(huán)碼

定義2.1 對(duì)于?上任意長(zhǎng)為n的碼字x=(x0,x1,…,xn-1) ∈ ?n，其中xi=ri+vqi，0 ≤i≤n-1，ri,qi∈R。?上任意長(zhǎng)為n的線性碼到R上長(zhǎng)為2n的線性碼的Gray映射為：

其中，r=(r0,r1,…,rn-1),q=(q0,q1,…,qn-1)。

引理2.2［2］令C是?上長(zhǎng)為n的線性碼，

易知C1和C2也是R上的線性碼，根據(jù)中國(guó)剩余定理可得：

定理2.3 ?n上的線性碼C=(1+v)C1⊕vC2是循環(huán)碼，當(dāng)且僅當(dāng)C1和C2均是R上長(zhǎng)為n的循環(huán)碼。

證明：令C是?上長(zhǎng)為n的循環(huán)碼，σ(c)=(cn-1,c0,…,cn-2)為c的一個(gè)循環(huán)移位，取任意c=(c0,c1,…,cn-1) ∈C，其中ci=ri+vqi，ri，qi∈R，0≤i≤n-1。則σ(c)=σ(r)+vσ(q)=(1+v)σ(r)+v(σ(r)+σ(q))。不妨設(shè)r=(r0,r1,…,rn-1)∈C1，q=(q0,q1,…,qn-1)∈C2，則σ(r) ∈C1，σ(q)∈C2，得出C1和C2都是R上長(zhǎng)為n的循環(huán)碼。

若C1和C2為R上長(zhǎng)為n的循環(huán)碼，取r=(r0,r1,…,rn-1) ∈C1，q=(q0,q1,…,qn-1) ∈C2，則r+q∈C2，假設(shè)ci=ri+vqi,0≤i≤n-1。由于C1和C2都是R上長(zhǎng)為n的循環(huán)碼，則有σ(r)∈C1，σ(r+q)∈C2。對(duì)于c=(c0,c1,…,cn-1)，有σ(c)=(1+v)σ(r)+v(σ(r)+σ(q))∈C。得出C是?上的循環(huán)碼。

引理 2.4［14］設(shè)C是F2+uF2上長(zhǎng)為n的循環(huán)碼，其中n≡ 1（mod2），則存在唯一的f、g、h使得：

其中，f、g、h∈F2[x]為首一多項(xiàng)式，且xn-1=fgh。

令 ?n[x]=?[x]/(xn-1)，多項(xiàng)式f∈F2[x]的互反多項(xiàng)式記作f?(x)=xkc(x-1)，下面研究得出?上長(zhǎng)為n的循環(huán)碼的生成多項(xiàng)式，其中n≡ 1（mod2）。

定理2.5設(shè)C為?上長(zhǎng)為n的循環(huán)碼，其中n≡ 1（mod2），則存在唯一多項(xiàng)式fi、gi、hi，i=1,2，使得：

其中，f1g1h1=f2g2h2=xn-1為首一多項(xiàng)式。

證明：由引理2.2知?上任一循環(huán)碼C可表示為C=(1+v)C1⊕vC2，由引理2.4可得C1=(g1+uh1),C2=(g2+uh2)，其中f1g1h1=f2g2h2=xn-1。取C中任意的碼字多項(xiàng)式：

其 中，r(x)、q(x)∈Rn[x]。顯 然，C? ((1+v)(g1+uh1),v(g2+uh2))。

多項(xiàng)式((1+v)(g1+uh1),v(g2+uh2))上任意元素根據(jù)引理2.2可表示為：

其中，k1(x)、k2(x) ∈Rn[x]。故必然存在r(x)、q(x) ∈Rn[x]，使得：

因此，((1+v)(g1+uh1),v(g2+uh2))?C，

綜上可知C=((1+v)(g1+uh1),v(g2+uh2))。

定理2.6 設(shè)C=(1+v)C1⊕vC2為?上長(zhǎng)為n的循環(huán)碼，其中n≡ 1（mod2），則有：

其中，g1(x)是C1的生成多項(xiàng)式；g2(x)是C2的生成多項(xiàng)式。

證明：令g(x)=(1+v)g1(x)+vg2(x)，其中g(shù)1(x)是C1的生成多項(xiàng)式，g2(x)是C2的生成多項(xiàng)式。由定理2.2可知，若C為?上長(zhǎng)為n的循環(huán)碼，其中n≡ 1（mod2），則有C=((1+v)g1(x)，vg2(x))，顯然(g(x)) ?C。

由 (1+v)g1(x)=(1+v)g(x)，vg2(x)=vg(x)，可得C?(g(x))。

綜上，可得C=(1+v)g1(x)+vg2(x)。

根據(jù)文獻(xiàn)［13］，結(jié)合定理2.6，易得以下推論：

推論 2.7 若n≡ 1（mod2），則環(huán) ?n[x]是一個(gè)主理想環(huán)。

?上線性碼C的對(duì)偶碼定義為：

推論2.8 設(shè)C為?上長(zhǎng)為n的循環(huán)碼，n≡ 1（mod2），則C⊥也為?上循環(huán)碼。

設(shè)多項(xiàng)式e(x)∈?n[x]是循環(huán)碼的生成多項(xiàng)式，滿足e2(x)=e(x)，則稱e(x)為環(huán) ?n[x]的冪等生成元。

定理2.9 設(shè)C=(1+v)C1⊕vC2為?上長(zhǎng)為n的循環(huán)碼，n≡ 1（mod2），則存在冪等生成元e(x)=(1+v)e1(x)+ve2(x)，滿足C=(e(x))。其中，e1(x)是C1(x)的冪等生成元，e2(x)是C2(x)的冪等生成元，并且冪等生成元e(x)是唯一。

證明：由e1(x)是C1(x)的冪等生成元，e2(x)是C2(x)的冪等生成元，記e(x)=(1+v)e1(x)+ve2(x)，根據(jù)定理 2.9可知，C=((1+v)e1(x)+ve2(x))。由e(x)2=((1+v)e1(x)+ve2(x))2=(1+v)e1(x)+ve2(x)=e(x)，知e(x)是碼C的冪等生成元。若定義e′(x)是碼C的另一冪等元，顯然e′(x) ?e(x)。

另一方面，設(shè)e′(x)=m(x)e(x)，則e(x)=e′(x)e(x)=m(x)e(x)e(x)=me(x)e′(x)，反 之，同理可知e′(x)e(x)=e(x)。綜上可得e′(x)=e(x)，即碼C的冪等生成元是唯一。

下面研究了環(huán)?上循環(huán)碼的對(duì)偶碼的冪等生成元。

定理2.10 設(shè)C=(e(x))為?上長(zhǎng)為n的循環(huán)碼，n≡ 1（mod2），其中e(x)為循環(huán)碼C的冪等生成元，則1-e(x-1)為C的對(duì)偶碼C⊥的冪等生成元。

證明：假設(shè)C=(1+v)C1⊕vC2，e1(x)是C1(x)的冪等生成元，e2(x)是C2(x)的冪等生成元。由定理2.3得C1(x)、C2(x)為?上的循環(huán)碼，由定理 2.9 可得e1(x-1)、e2(x-1)分別為C1、C2的冪等生成元。由推論2.8可知，C⊥也為?上循環(huán)碼，故對(duì)C⊥也可通過C⊥=(1+v)C1⊥⊕vC2⊥進(jìn)行表示，因?yàn)?1+v)(1-e1(x-1))+v(1-e2(x-1))=1-e(x-1)，故C⊥的冪等生成元可表示為1-e(x-1)。

3 環(huán)?上的Gray映射

糾錯(cuò)碼的重量和距離作為兩個(gè)重要參數(shù)，是衡量是否為優(yōu)碼的重要指標(biāo)。首先定義環(huán)?上元素的Lee重量，具體如下：

對(duì)于環(huán)?上任意長(zhǎng)為n的碼字c=(c0,c1,…，cn-1)，定義c的 Lee重量為：

定義 3.1［14］環(huán)R=F2+uF2上線性碼的 Lee重量為：

R到F2的映射：

Rn到F22n的保距映射：

其 中，c=(a0+ub0,a1+ub1,…,an-1+ubn-1)；a=(a0,a1,…,an-1)；b=(b0,b1,…,bn-1)。

通過定義2.1中所定義的?n到R2n的映射φ1和定義3.1中Rn到F22n的映射φ2，首先定義 ?n上Lee距離到F24n上Hamming距離的保距映射φ，然后證明其為保距映射。

定義3.2 定義（?，Lee距 離）到（F42，Hamming距離）的映射θ：

其中，a、b、c、d∈F2。

（?n，Lee距離）到（F4n2，Hamming距離）的Gray映射φ：

定義3.3 設(shè)C為環(huán)?上長(zhǎng)為n的線性碼，φ(C)為碼C的Gray映射，碼C的Lee距離為：

φ(C)的Hamming距離為：

推論 3.4（?,Lee距離）到（F24，Ham ming距離）的Gray映射φ是保距映射。

推論3.5 設(shè)C為?上長(zhǎng)為n的線性碼，則φ(C)為二元域上長(zhǎng)為4n的線性碼。

推論3.6 設(shè)C為?上長(zhǎng)為n的循環(huán)碼，n≡ 1（mod2），則有：

其中，f1g1h1=f2g2h2=xn-1。

定理3.7設(shè)C為?上長(zhǎng)為n的線性碼，則其對(duì)偶碼滿足φ(C⊥)=φ(C)⊥。

證明：令：

根據(jù)對(duì)偶碼的定義有x·y=0，故：

由上式可得：

故φ(C⊥) ?φ(C)⊥。

反之，易知φ是雙射，故有|φ(C)|=|C|和|φ(C⊥)|=|C⊥|成立，有|C|·|C⊥|=42n成立，得到|φ(C)|·|φ(C⊥)|=24n。根據(jù)推論3.6，不妨假設(shè)|C|= 4k12k2，則 |φ(C)|=|C|=4k12k2，|φ(C⊥)|=|C⊥|= 24n-2k1-k2，故 |φ(C⊥)|=|φ(C⊥)|。

綜上可得，φ(C⊥)=φ(C)⊥。

根據(jù)定義3.2中所構(gòu)造的環(huán)?n到域映射，對(duì)于任意的?n上的循環(huán)碼的碼字c=(c0,c1,…,cn-1)，定義上的準(zhǔn)循環(huán)移位ψs為：

定理3.8 設(shè)C為?上長(zhǎng)為n的循環(huán)碼，則φ(C)為二元域上長(zhǎng)為4n的循環(huán)碼。

定理3.9 設(shè)?上長(zhǎng)為n的循環(huán)碼C=(1+v)C1⊕vC2，n≡ 1（mod2），則C極小 Lee距離滿足：

其中，dL(C1)是C1的極小 Lee距離；dL(C2)是C2的極小Lee距離。

證明：由C=(1+v)C1⊕vC2，其中C1、C2為R上的循環(huán)碼，對(duì)應(yīng)碼C生成矩陣可以表示為：

其中，G1為C1的生成矩陣；G2為C2的生成矩陣。易知φ1(C)的生成矩陣可以為：

根據(jù)矩陣的結(jié)構(gòu)特點(diǎn)，得：

利用定理3.9，結(jié)合?上循環(huán)碼的結(jié)構(gòu)特點(diǎn)，通過?上循環(huán)碼的二元Gray象φ(C)可構(gòu)造一些參數(shù)較好的極小Hamming距離二元最優(yōu)碼或漸進(jìn)優(yōu)碼。

4 應(yīng)用舉例

例4.1當(dāng)n=3時(shí)，在二元域上中對(duì)x3-1進(jìn)行因式分解可得：

對(duì)于?循環(huán)碼C=(1+v)C1⊕vC2，取：

則可得φ1(C1)參數(shù)為[6,422,2]，φ1(C2)的參數(shù)為[6,42,2]。根據(jù)定理3.9可得二元域上的Lee距離dL(φ(C))=2，故所構(gòu)造的二元域上的準(zhǔn)循環(huán)碼φ(C)參數(shù)為[12,9,2]二元準(zhǔn)循環(huán)最優(yōu)碼。

例4.2 當(dāng)n=7時(shí)，在F2中對(duì)x7-1進(jìn)行分解可得：

對(duì)于C是?循環(huán)碼，取：

則可得φ1(C1)參數(shù)為 [14,4423,2]，φ1(C2)的參數(shù)為[14,462,2]。根據(jù)定理3.9可得二元域上的Lee距離dL(φ(C))=2，所得的碼C的 Gray二元象φ(C)是[28,24,2]二元準(zhǔn)循環(huán)最優(yōu)碼。

5 結(jié)論

為了更加全面的了解有限非鏈環(huán)的結(jié)構(gòu)性質(zhì)，并構(gòu)造一些二元域上最優(yōu)碼或漸近優(yōu)碼，更好解決通信中的糾錯(cuò)問題，首先對(duì)環(huán)F2+vF2+uF2+uvF2上的循環(huán)碼的結(jié)構(gòu)特征進(jìn)行研究，得出其生成多項(xiàng)式和冪等生成元.進(jìn)一步說明了環(huán)F2+vF2+uF2+uvF2上的循環(huán)碼結(jié)構(gòu)具有較易編譯的特點(diǎn)。構(gòu)造了從環(huán)上的循環(huán)碼到二元域上準(zhǔn)循環(huán)碼的Gray映射，證得其保距性，并同步證明了其對(duì)偶碼也是循環(huán)碼的結(jié)論，為后續(xù)構(gòu)造具有極小距離的最優(yōu)碼提供了理論依據(jù)。通過循環(huán)碼的結(jié)構(gòu)特點(diǎn)得出較好的極小Hamming距離二元最優(yōu)碼或漸進(jìn)優(yōu)碼。今后還可持續(xù)研究環(huán)F2+vF2+uF2+uvF2上的常循環(huán)碼、自正交碼和量子碼的結(jié)構(gòu)及其重量分布、覆蓋半徑、周期分布等相關(guān)性質(zhì)。