朱士信，黃　磊

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

環(huán)R+vR+v2R上線性碼的MacWilliams恒等式

朱士信，黃磊

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

通過構(gòu)造Gray映射，對環(huán)R+vR+v2R上線性碼進行了研究.定義了環(huán)R+vR+v2R上線性碼的Lee重量及其幾類重量計數(shù)器，給出了環(huán)R+vR+v2R上線性碼及其對偶碼之間的各種重量分布的MacWilliams恒等式.利用這些恒等式，不用求出環(huán)R+vR+v2R上線性碼的對偶碼便可得到對偶碼的各種重量分布.

線性碼；Gray映射；對偶碼；重量計數(shù)器；MacWilliams恒等式

1　引言

上世紀九十年代中期，Hammons等人利用有限環(huán)Z4上的線性碼在Gray映射下得到了具有高糾錯性能的Prepatata碼與Kerdock碼[1]，這一發(fā)現(xiàn)使有限環(huán)上編碼理論研究獲得重大突破.自此，有限環(huán)上的碼受到了廣泛的研究.隨后，人們又發(fā)現(xiàn)有限環(huán)上的線性碼不僅可以用于無線通信網(wǎng)絡(luò)中的糾錯方案設(shè)計，而且可以用于構(gòu)造空時碼[2]，這表明有限環(huán)上的糾錯碼具有廣闊的應(yīng)用前景，從而激發(fā)人們對有限環(huán)上線性碼濃厚的研究興趣.文獻[3,4]研究了有限鏈環(huán)上的循環(huán)碼和負循環(huán)碼，其中給出了循環(huán)碼和負循環(huán)碼的結(jié)構(gòu).碼的重量分布一直是編碼理論研究的一個重要分支，而針對環(huán)上碼的重量分布也取得了很多結(jié)果，文獻[5]中研究了有限域上碼的各種重量分布，給出了幾類重量計數(shù)器的定義與性質(zhì)；文獻[6]對環(huán)Z4上碼的各種重量分布的MacWilliams恒等式進行了研究；文獻[7,8]研究了環(huán)Z4和Galois環(huán)上線性碼的廣義Hamming重量，而文獻[9,10]研究了環(huán)Zk和Galois環(huán)上線性碼的MacWilliams恒等式；文獻[11]中研究了環(huán)F2+uF2上線性碼的Lee重量和Hamming重量的MacWilliams恒等式;文獻[12]給出了環(huán)F2+uF2+u2F2上線性碼李重量分布的MacWilliams恒等式;文獻[13]研究了環(huán)Fp+uFp+u2Fp上線性碼的完全重量計數(shù)和對稱重量計數(shù)的MacWilliams恒等式.但是，對于有限非鏈環(huán)上碼的各種重量的MacWilliams恒等式的研究并不太多，文獻[14～16]研究了環(huán)F2+vF2和Fp+vFp上線性碼的各種重量的MacWilliams恒等式.

本文首先定義了環(huán)R+vR+v2R(v3=v)上的線性碼，其中R是極大理想為〈λ〉的有限鏈環(huán)，p為剩余域R/〈λ〉的特征，且p為奇數(shù).然后定義了這些線性碼的Lee重量計數(shù)器、Hamming重量計數(shù)器、廣義對稱重量計數(shù)器和完全重量計數(shù)器，最后研究了環(huán)R+vR+v2R上線性碼線性碼及其對偶碼之間的各種重量分布的MacWilliams恒等式.這些結(jié)果為利用R+vR+v2R上線性碼構(gòu)造R的剩余域上的碼提供了重要的理論依據(jù)，同時，它對設(shè)計R+vR+v2R上線性碼的編碼與譯碼算法具有直接的指導意義.

2　準備知識

設(shè)R=R+vR+v2R={x+vy+v2z|x,y,z∈R}，其中v3=v，R是極大理想為〈λ〉的有限鏈環(huán)，p為剩余域R/〈λ〉的特征且為奇數(shù).容易驗證環(huán)R不是有限鏈環(huán).設(shè)α1=2-1v+2-1v2，α2=-2-1v+2-1v2和α3=1-v2，易證它們是R中相互正交的冪等元，且〈α1〉={α1x|x∈R}，〈α2〉={α2x|x∈R}和〈α3〉={α3x|x∈R}是R的三個相互互素的理想，由中國剩余定理易證R?〈α1〉⊕〈α2〉⊕〈α3〉.由此可知R中的任意元素可唯一表示為c=α1a+α2b+α3d，其中a,b,d∈R.

環(huán)R上長度為n的碼C是Rn的非空子集，若C是Rn的R-子模，則稱C是環(huán)R上長度為n的線性碼.對Rn中任意的兩個元素x=(x0,x1,…,xn-1)和y=(y0,y1,…,yn-1)，定義它們的內(nèi)積為

x·y=x0y0+x1y1+…+xn-1yn-1

若x·y=0，則稱x與y正交.對環(huán)Rn上長度為n的線性碼C，其對偶碼為

C⊥={x|x·y=0,?y∈C}

若C=C⊥，則稱C為自對偶碼.

引理1[11]設(shè)C是環(huán)Rn上長度為n的線性碼，定義

C1={a∈Rn|?b,d∈Rn,α1a+α2b+α3d∈C}，

C2={b∈Rn|?a,d∈Rn,α1a+α2b+α3d∈C}，

C3={d∈Rn|?a,b∈Rn,α1a+α2b+α3d∈C}，

則C1,C2和C3為域R上長度為n的線性碼，且C有唯一表示C=α1C1⊕α2C2⊕α3C3.

3　Gray映射

定義R到R3的Gray映射φ為：對任意的c∈R，φ(c)=(a,b,d)，其中c=α1a+α2b+α3d，a,b,d∈R.由此定義R中元素c=α1a+α2b+α3d的Lee重量為wL(c)=wH(a,b,d).對于環(huán)R上線φ可以自然擴展到Rn，定義Rn到R3n的Gray映射為：對任意的c=(c0,c1,…,cn-1)∈Rn，

Φ(c)=(a0,a1,…,an-1,b0,b1,…,bn-1，

d0,d1,…,dn-1)∈R3n

定理1設(shè)C是環(huán)R上長度為n的線性碼，則

(1)C⊥是環(huán)R上長度為n的線性碼.

(2)Φ(C)=C1?C2?C3，且|C|=|C1||C2||C3|.

證明(1)是顯然成立的.對任意的(a,b,d)∈C1?C2?C3，其中 a∈C1，b∈C2，d∈C3.由引理1可知存在x,y,z∈C以致于x=α1a+α2b′+α3d′,y=α1a′+α2b+α3d″和z=α1a″+α2b″+α3d，其中a′,a″,b′,b″,d′,d″∈R.由于C是線性的，我們有

c=α1x+α2y+α3z=α1a+α2b+α3d∈C，

而Φ(c)=(a,b,d)∈Φ(C)，因此

Φ(C)?C1?C2?C3.

另一方面，對任意的(a,b,d)∈Φ(C)，設(shè)c=α1a+α2b+α3d.由于Φ是一個環(huán)同構(gòu)映射，必有c∈C，由引理1我們得到a∈C1，b∈C2和d∈C3.由此推知Φ(C)?C1?C2?C3，因此我們有Φ(C)=C1?C2?C3.由于Φ是同構(gòu)映射，則|C|=|Φ(C)|=|C1||C2||C3|.對任意的c=α1a+α2b+α3d∈C，c′=α1a′+α2b′+α3d′∈C⊥，其中a,a′,b,b′d,d′∈Rn.由 c·c′=0，則a·a′=b·b′=d·d′=0，由此推知

Φ(c)·Φ(c′)=(a,b,d)·(a′,b′,d′)

=a·a′+b·b′+d·d′

=0

因此Φ(c′)∈Φ(C)⊥，推知Φ(C⊥)?Φ(C)⊥.另一方面，我們有

|C⊥|=|Φ(C⊥)|=|Rn|/|C|=|R3n|/|C|，

|Φ(C⊥)|=|Φ(C)⊥|=|R3n|/|Φ(C)|=|R3n|/|C|，

|Φ(C⊥)|=|Φ(C)⊥|=|R3n|/|C|，

推論1設(shè)C是環(huán)R上長度為n的線性碼，則C是設(shè)環(huán)R上長度為n的自對偶碼碼當且僅當C1，C2和C3均是環(huán)R上長度為n的自對偶碼，當且僅當Φ(C)為環(huán)R上長度為3n的自對偶碼.

4　線性碼的MacWilliams恒等式

設(shè)C是環(huán)R上長度為n的線性碼，用Bi表示C中Lee重量為i的碼字的個數(shù)，其中0≤i≤3n，稱{B0,B1,…,B3n}為C的Lee重量分布，稱

為C的廣義對稱重量計數(shù)器；wH(c)=w1(c)+w2(c)+w3(c)，稱

為C的Hamming重量計數(shù)器.設(shè)q=|R/〈λ〉|，則|R|=q3l.本文約定R={g1,g2,…,gq3l}，其中g(shù)1,g2,…,gq3l互不相同，且按一定的順序排列.約定g1=0，對Rn中元素c=(c0,c1,…,cn-1)，記ni(c)為c中值為gi的元素成分個數(shù)，其中1≤i≤q3l，稱

為C的完全重量計數(shù)器.對任意的gi∈R，記I(i)=wL(gi)，其中1≤i≤q3l.

定理2設(shè)C是環(huán)R上長度為n的線性碼，則下面等式成立：

(1)LeeC(X,Y)=SweC(X3,X2Y,XY2,Y3)；

(2)SweC(X0,X1,X2,X3)=CweC(XI(1),XI(2),…,

XI(q3l))

(3)HamC(X,Y)=SweC(X,Y,Y,Y)；

(4)LeeC(X,Y)=HamΦ(C)(X,Y)；

(5)HamC(X,Y)=CweC(X,Y,…,Y).

證明

(1)對任意的c∈C，

n=w0(c)+w1(c)+w2(c)+w3(c)，

wL(c)=w1(c)+2w2(c)+3w3(c).

于是

=SweC(X3,X2Y,XY2,Y3)

(2)若I(i)=j，其中1≤i≤q3l，0≤j≤3，則ni(c)計數(shù)于wj(c)，因此容易驗證等式成立.

(3)因為wH(c)=w1(c)+w2(c)+w3(c)，則

=SweC(X,Y,Y,Y)

(4)由定義可知

因為wL(c)=wH(Φ(c))，而Φ是一個Rn到R3n的同構(gòu)映射，則

=LeeC(X,Y)

(5)因為g1=0，顯然

wH(c)=n2(c)+n3(c)+…+nq3l(c)，

則

=HamC(X,Y)

其中aj,i,bj,i,dj,i∈Fp，0≤i≤m-1,0≤j≤l-1.

對任意的

定義在R上復(fù)值映射θc為：對任意的

θ1(c′+c″)=θ1(c′)θ1(c″).

將θc擴展到Rn上，對固定的c∈Rn，定義Rn到R的復(fù)值映射Θc為：對任意的c′∈Rn，Θc(c′)=θ1(c·c′).我們先給出下面引理.

證明容易驗證

Rr,s,t=〈α1λr〉⊕〈α2λs〉⊕〈α3λt〉

為環(huán)R的所有非零理想，其中0≤r,s,t≤l.令

則

我們可以將其寫為

而

=0

定理3設(shè)C是環(huán)R上長度為n的線性碼，則

CweC⊥(X1,X2,…,Xq3l)

則

=|C|CweC⊥(X1,X2,…,Xq3l)

另一方面，

推知

其中δ(x,y)為Kronecker-Delta函數(shù).容易驗證

而

由完全重量計數(shù)器的定義可知

綜上所述，

CweC⊥(X1,X2,…,Xq3l)

證明由定理2的(5)可知HamC⊥(X,Y)=CweC⊥(X,Y,…,Y).因為g1=0，若X2=…=Xq3l=Y，則

X-Y,…,X-Y)

推知

·(X-Y)n2(c)+…+nq3l(c)

因為wH(c)=n2(c)+n3(c)+…+nq3l(c)，則

HamC⊥(X,Y)

下面研究廣義對稱重量計數(shù)器的MacWilliams恒等式，設(shè)

D0={0}，

D1=(〈α1〉∪〈α2〉∪〈α3〉)D0，

D3=R(D2∪D1∪D0)，

容易驗證Dj中元素的Lee重量為j，其中0≤j≤3.我們先給出下面定理：

定理4對任意的g∈R，有

(1)若g∈D0，則

(2)若g∈D1，則

(3)若g∈D2，則

(4)若g∈D3，則

證明

(1)g∈D0時g=0，則

(2)g∈D1時，不妨令g∈〈α1〉{0}，則

=-1+2(ql-1)=2ql-3，

(3)g∈D1時，不妨令g∈(〈α1〉{0})⊕(〈α2〉){0})，

則

則我們有

=3-2ql

定理5設(shè)C是環(huán)R上長度為n的線性碼，則

SweC⊥(X0,X1,X2,X3)

X0+(2ql-3)X1+(q2l-4ql+3)X2-(ql-1)2X3,

X0+(ql-3)X1+(3-2ql)X2+(ql-1)X3，

X0-3X1+3X2-X3)

證明由定理2的(2)可知

SweC⊥(X0,X1,X2,X3)=CweC⊥(XI(1),XI(2),…,XI(q3l))

根據(jù)定理3可知

SweC⊥(X0,X1,X2,X3)

其中1≤s≤q3l，則

SweC⊥(X0,X1,X2,X3)

因為|D0|=1，|D1|=3(ql-1)，|D2|=3(ql-1)2，|D3|=(ql-1)3和Dj中元素的Lee重量為j，其中0≤j≤3，利用定理4可以推知

=(X0+3(ql-1)X1+3(ql-1)2X2+(ql-1)3X3)w0(c)

(X0+(2ql-3)X1+(q2l-4ql+3)X2

-(ql-1)2X3)w1(c)(X0+(ql-3)X1+(3-2ql)X2

+(ql-1)X3)w2(c)(X0-3X1+3X2-X3)w3(c)=SweC(X0+3(ql-1)X1+3(ql-1)2X2+(ql-1)3X3，X0+(2ql-3)X1+(q2l-4ql+3)X2-(ql-1)2X3，

X0+(ql-3)X1+(3-2ql)X2+(ql-1)X3，

X0-3X1+3X2-X3)

因此

SweC⊥(X0,X1,X2,X3)

X0+(2ql-3)X1+(q2l-4ql+3)X2-(ql-1)2X3,

X0+(ql-3)X1+(3-2ql)X2+(ql-1)X3，

X0-3X1+3X2-X3)

注由定理2的(3)可知

HamC⊥(X,Y)=SweC⊥(X,Y,Y,Y)，

利用定理5我們可以得到

HamC⊥(X,Y)

X0+(2ql-3)Y+(q2l-4ql+3)Y-(ql-1)2Y，

X+(ql-3)Y+(3-2ql)Y+(ql-1)Y，

X-3Y+3Y-Y)，

化簡得到

HamC⊥(X,Y)

這與推論2一致.

推論3設(shè)C是環(huán)R上長度為n的線性碼，則

證明根據(jù)定理2可知

LeeC⊥(X,Y)=SweC⊥(X3,X2Y,XY2,Y3)

再利用定理5容易驗證.

例設(shè)C是環(huán)F3+vF3+v2F3上長度為2的線性碼，且C={(0，0),(1,1),(2,2)}，容易得知C的Lee重量分布為B0=1,B6=2.下面利用上面的理論來求C⊥的Lee重量分布.

(1)顯然LeeC(X,Y)=X6+2Y6，由推論3可知

化簡為

LeeC⊥(X,Y)=X6+30X4Y2+40X3Y3

+90X2Y4+60XY5+22Y6

因此C⊥的Lee重量分布為

+2(X0-3X1+3X2-X3)2)

則

LeeC⊥(X,Y)=SweC⊥(X3,X2Y,XY2,Y3)

+2(X3-3X2Y+3XY2-Y3)2)

化簡為

LeeC⊥(X,Y)=X6+30X4Y2+40X3Y3

+90X2Y4+60XY5+22Y6

與第一種方法相符.

5　結(jié)束語

本文研究有限環(huán)R+vR+v2R上線性碼的各種重量計數(shù)器，其中R是特征為奇素數(shù)方冪的有限鏈環(huán)，給出了環(huán)R+vR+v2R上線性碼線性碼及其對偶碼之間的各種重量分布的MacWilliams恒等式.本文研究結(jié)果不僅為探索R+vR+v2R上線性碼的碼字結(jié)構(gòu)提供了重要的方法，而且也為計算R+vR+v2R上線性碼譯碼誤碼率提供重要的依據(jù).如何利用得到的R+vR+v2R上線性碼的各種MacWilliams恒等式，設(shè)計編碼與譯碼算法是一個值得探索的問題.

[1]Hammons J A R,Kumar P V,Calderbank A R,et al.The Z4-linearity of Kerdock,Preparata,Goethals,and related codes[J].IEEE Transactions on Information Theory,1994,40 (2):301-319.

[2]Tarokh V,Seshadri N,Calderbank A R.Space-time codes for high data rate wireless communication:Performance criterion and construction[J].IEEE Transactions Information Theory,1998,44:744-765.

[3]Dinh H Q,López-Permouth S R.Cyclic and negacyclic codes over finite chain rings[J].IEEE Transactions on Information Theory,2005,50(8):1728-1744.

[4]Hu Peng,Li Hui,Liu Xiusheng.The generator polynomials of cyclic and negecyclic codes over finite chain ring[J].Mathematics in Picture and Theory,2011,41(2):217-221.

[5]MacWilliams F J,Sloane N J A.The Theory of Error-Correcting Codes[M].Elsevier,1977.

[6]Wan Zhexian.Quaternary Codes[M].Singapore:World Scientic Pub Co,1997.25-70.

[7]Ashikhmin A E.Generalized Hamming weights for Z4- linear codes[A].Proceedings of 1994 IEEE International Symposium on Information Theory[C].IEEE,1994.306-306.

[8]Ashikhmin A E.On generalized Hamming weights for Galois ring linear codes[J].Designs,Codes and Cryptography,1998,14(2):107-126.

[9]朱士信.Zk線性碼的對稱形式的MacWilliams恒等式[J].電子與信息學報,2003,25(7):901-906.

Zhu Shixin.A symmetrized MacWilliams identity of Zk-linear code[J].Journal of Electronics & Information Technology,2003,25(7):901-906.(in Chinese)

[10]Wan Zhexian.The MacWilliams identity for linear codes over Galois rings[A].Numbers Information and Complexity[C].Netherlands:Kluwer Academic Publishers,2000.333-338.

[11]余海峰,朱士信.環(huán)F2+uF2上線性碼及其對偶碼的MacWilliams恒等式[J].中國科學技術(shù)大學學報,2006,36(2):1285-1288.

[12]梁華,唐元生.環(huán)F2+uF2+u2F2上線性碼的MacW-illiams恒等式[J].數(shù)學的實踐與認識,2010,40(23):200-205.

[13]許小芳,毛琪莉.環(huán)Fp+uFp+u2Fp上線性碼的MacWilliams恒等式[J].數(shù)學雜志,2013,33(3):519-524.

[14]施敏加,朱士信,李平.環(huán)F2+vF2上線性碼的MacWi-lliams恒等式[J].計算機應(yīng)用研究,2008,25(4):1134-1135.

[15]劉修生,劉花璐.環(huán)Fp+vFp上線性碼的MacWilliams恒等式[J].山東大學學報(理學版),2013,(12):61-65.

[16]施敏加,楊善林.非主理想環(huán)Fp+vFp上線性碼的MacWilliams恒等式[J].電子學報,2011,39(10):2449-2453.

Shi Minjia,Yang Shanlin.Macwilliams identities of linear codes over non-principal ideal ring Fp+vFp[J].Acta Electronica Sinica,2011,39(10):2449-2453.(in Chinese)

朱士信男，1962年生于安徽樅陽.教授、博士生導師.合肥工業(yè)大學數(shù)學學院院長，中國密碼學會理事，安徽省數(shù)學會副理事長.研究方向為代數(shù)編碼與密碼、非線性移位寄存器等.

E-mail：zhushixin@hfut.edu.cn

黃磊男，1989年生于江西上高.2015年畢業(yè)于合肥工業(yè)大學，碩士.研究方向為代數(shù)編碼與密碼.

E-mail：18756096707@163.com

MacWilliams Identities of Linear Codes Over Ring R+vR+v2RZHU

Shi-xin，HUANG Lei

(School of Mathematics,Hefei University of Technology,Hefei,Anhui 230009,China)

By constructing gray map,linear codes over ring R+vR+v2R are studied.The Lee weight and several classes of weight enumerators about linear codes over ring R+vR+v2R are defined,the MacWilliams identities of weight distributions between the linear codes and their dual codes over ring R+vR+v2R are given.According to these identities,we can get the weight distributions of dual codes directly without obtaining the dual codes of linear codes over ring R+vR+v2R.

linear code;Gray map;dual code;weight enumerator;MacWilliams identity

2014-12-26；

2015-07-13；責任編輯：李勇鋒

國家自然科學基金(No.61370089)

TN911.22

A

0372-2112 (2016)07-1567-07

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.07.007