環(huán)Z4上自對(duì)偶碼的構(gòu)造

袁 健,朱士信,開曉山

(1.合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院,安徽合肥 230009;2.東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室,江蘇南京 210096)

?

環(huán)Z4上自對(duì)偶碼的構(gòu)造

袁 健1,2,朱士信1,2,開曉山1,2

(1.合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院,安徽合肥 230009;2.東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室,江蘇南京 210096)

Gray映射；線性碼；自對(duì)偶碼

1 引言

2 環(huán)Z4+vZ4上的線性碼

定理1[6]若C為Z4上長(zhǎng)為n的類型Ⅱ碼，則dE(C)≤8?n/24」+8；若C為Z4上長(zhǎng)為n的類型Ⅰ碼，則當(dāng)n≡23(mod24)時(shí)，dE(C)≤8?n/24」+12,否則dE(C)≤8?n/24」+8.

稱達(dá)到定理1中上界的自對(duì)偶碼為Z4上的極優(yōu)碼.下面介紹有限環(huán)Z4+vZ4={a+bv|a,b∈Z4},其中v2=1.為簡(jiǎn)便起見，用R表示環(huán)Z4+vZ4.環(huán)R是一個(gè)特征為4的含幺交換環(huán)，并且R可以看作多項(xiàng)式剩余類環(huán)Z4[v]/〈v2-1〉.R的單位元素組成的集合為

U={1,3,1+2v,3+2v,v,3v,2+v,2+3v}，

R的非單位元素組成的集合為

N={0,2,2v,2+2v,1+v,3+v,1+3v,3+3v}.

將R的非單位分為兩個(gè)集合：N1={0,2,2v,2+2v}和N2={1+v,3+v,1+3v,3+3v}.容易驗(yàn)證：

環(huán)R有7個(gè)不同的理想，它們分別為：

{0}，Z4+vZ4，{0,2+2v}，〈2〉={0,2,2v,2+2v}，〈1+v〉={0,1+v,2+2v,3+3v}，〈1+3v〉={0,1+3v,2+2v,3+v}，〈2,1+v〉={0,2,2v,2+2v,1+v,3+v,1+3v,3+3v}.

因此，R是一個(gè)最大理想為〈2,1+v〉的局部環(huán)，剩余域?yàn)镕2.因?yàn)椤?,1+v〉在R中的零化理想Ann(〈2,1+v〉)={0,2+2v}在F2上的維數(shù)為1，所以R是一個(gè)局部Frobenius環(huán)[10,11].

其中ci=ai+biv，i=0,1,…,n-1.顯然，φ是一個(gè)雙射.根據(jù)歐幾里得重量定義，容易得到下面結(jié)論：

在Rn上引入內(nèi)積.對(duì)于任意x=(x1,x2,…,xn),y=(y1,y2,…,yn)∈Rn，定義x·y=x1y1+x2y2+…+xnyn.R上的長(zhǎng)為n的線性碼C的對(duì)偶碼定義為C⊥={x∈Rn|x·c=0,?c∈C}.易證C⊥也是R上的長(zhǎng)為n的線性碼.因?yàn)镽是一個(gè)Frobenius環(huán)，所以有|C||C⊥|=16n(參見[10]).

3 R上自對(duì)偶碼及其Gray像

設(shè)C是R上的線性碼， 若C?C⊥，則稱C為R上自正交碼；若C=C⊥，則稱C為R上自對(duì)偶碼.R中由元素2生成的理想〈2〉可以看作R上長(zhǎng)為1的自對(duì)偶碼，利用直積的方法[11]，容易看到環(huán)R上存在任意長(zhǎng)度的自對(duì)偶碼.任取c=(c1,c2,…,cn-1)∈C，用nU(c)表示c的屬于U的分量數(shù)目，nN2(c)表示c的屬于N2的分量數(shù)目.為了構(gòu)造Z4上自對(duì)偶碼，首先給出R上自對(duì)偶碼的性質(zhì).

定理3 設(shè)C為R上長(zhǎng)為n的線性碼，則下面結(jié)論成立：

(1) 若C是自正交碼，則對(duì)于任一碼字c∈C，nN2(c)≡0(mod2)且nU(c)≡0(mod4).因此，R上自正交碼的每個(gè)碼字的歐幾里得重量都是4的倍數(shù).

(2)若C是自對(duì)偶碼，則C包含全2向量和全(2+2v)向量.

證明 (1) 設(shè)C是R上的自正交碼，則對(duì)任一c∈C，c·c=0.但在R中，

c·c=nN2(c)(2+2v)+nU(c)

=2nN2(c)+nU(c)+(2nN2(c))v.

因此，

nN2(c)≡0(mod2)且nU(c)≡0(mod4).

注意到N2中的元素的歐幾里得重量都是2，N1中的元素的歐幾里得重量為0或4或8，即是4的倍數(shù)，而U中元素的歐幾里得重量模4余1.由此可得，R上自正交碼的每個(gè)碼字的歐幾里得重量都是4的倍數(shù).

(2) 在環(huán)R中，容易驗(yàn)證：當(dāng)r∈U時(shí)，r·(2+2v)=2+2v；當(dāng)r∈N時(shí)，r·(2+2v)=0.

設(shè)C是R上的自對(duì)偶碼，對(duì)任一c∈C，(2+2v,2+2v,…,2+2v)·c=nU(c)(2+2v).由(1)知，nU(c)是4的倍數(shù)，從而(2+2v,2+2v,…,2+2v)∈C⊥=C，即C中包含全2+2v向量.同理,C也包含全2向量.

由定理3(1)，R上自對(duì)偶碼的每個(gè)碼字的歐幾里得重量都是4的倍數(shù).同時(shí)，由于R中2+2v的歐幾里得重量為8，根據(jù)定理3(2)，R上自對(duì)偶碼中一定存在歐幾里得重量是8的倍數(shù)的碼字.由此，我們引入下面定義：

定義1 設(shè)C是R上的自對(duì)偶碼，若它的每個(gè)碼字的歐幾里得重量都是8的倍數(shù)，則稱C為類型Ⅱ碼，否則稱C為類型Ⅰ碼.

為了構(gòu)造Z4上自對(duì)偶碼，下面考慮R上自對(duì)偶碼的Gray像.

定理4 設(shè)C為R上長(zhǎng)為n的線性碼，則φ(C⊥)=φ(C)⊥.而且，若C是R上長(zhǎng)為n自對(duì)偶碼，則φ(C)為Z4上長(zhǎng)為2n的自對(duì)偶碼.若C是R上長(zhǎng)為n的類型 Ⅱ碼，則φ(C)為Z4上長(zhǎng)為2n的類型Ⅱ碼.

證明 因?yàn)棣帐且粋€(gè)雙射保距映射，并且

|φ(C⊥)|=|C⊥|=16n/|C|=42n/|φ(C)|=|φ(C)⊥|，

所以

于是

從而φ(C⊥)=φ(C)⊥.

注意到R上由2生成的長(zhǎng)為1的自對(duì)偶碼是類型Ⅰ碼，利用直積方法[11]可知，R上任意長(zhǎng)的類型Ⅰ碼都存在，而對(duì)于R上類型Ⅱ碼有下面的結(jié)果：

定理5 環(huán)R上長(zhǎng)為n的類型Ⅱ碼存在當(dāng)且僅當(dāng)n是4的倍數(shù).

證明 由文獻(xiàn)[6]可知，對(duì)于Z4上長(zhǎng)為N的自對(duì)偶碼，僅當(dāng)N是8的倍數(shù)時(shí)，存在Z4上長(zhǎng)為N的類型Ⅱ碼.因?yàn)棣帐潜＞嘤成?，所以若R上長(zhǎng)為n的類型Ⅱ碼存在，則n是4的倍數(shù).反過(guò)來(lái)，設(shè)n是4的倍數(shù)，令C=〈(v,1,1,1),(3,v,1,3),(3,3,v,1),(3,1,3,v)〉，則C是R上長(zhǎng)為4的類型Ⅱ碼.C的歐幾里得重量計(jì)數(shù)器為WC(z)=1+128z8+126z16+z32.因此，C是一個(gè)參數(shù)為(4,44,8)的類型Ⅱ碼.根據(jù)文獻(xiàn)[11,Lemma 3.2]，C×C,C×C×C,C×C×C×C,……分別為R上長(zhǎng)為8,12,16,……的類型Ⅱ碼.所以，當(dāng)n是4的倍數(shù)時(shí)，R上長(zhǎng)為n的類型Ⅱ碼存在.

下面給出類型Ⅰ碼和類型Ⅱ碼的歐幾里得重量的上界.

定理6 設(shè)dE是R上長(zhǎng)為n的類型Ⅰ碼或類型Ⅱ碼的歐幾里得重量，則dE≤8?n/12」+8.

證明 由定理4，如果C是R上長(zhǎng)為n的類型Ⅱ碼或類型Ⅰ碼，那么φ(C)為Z4上長(zhǎng)為2n的類型Ⅱ碼或類型Ⅰ碼.因?yàn)棣帐潜＞嘤成?，根?jù)定理1立即可以得到結(jié)論.因?yàn)?n≠23(mod24)，所以dE的上界不變.

若R上自對(duì)偶碼滿足定理6中的上界dE=8?n/12」+8，則稱C為環(huán)R上的極優(yōu)碼.

4 Z4上自對(duì)偶碼

本節(jié)，利用前面的結(jié)論，再結(jié)合計(jì)算機(jī)程序搜索R上類型Ⅰ碼和類型Ⅱ碼，由此構(gòu)造Z4上的自對(duì)偶碼.

例1 考慮R上長(zhǎng)為1的自對(duì)偶碼.取C1=〈2〉，則C1是R上的參數(shù)為(1,4,4)的類型Ⅰ最優(yōu)碼，其歐幾里得重量計(jì)數(shù)器為WC1(z)=1+2z4+z8.因此，φ(C1)是Z4上參數(shù)為(2,4022,4) 的類型Ⅰ碼.

例2 考慮R上長(zhǎng)為2的自對(duì)偶碼.取C2=〈(1+v,1-v),(2,2)〉，則C2是R上參數(shù)為(2,16,4)的類型Ⅰ最優(yōu)碼，其歐幾里得重量計(jì)數(shù)器為WC2(z)=1+8z4+6z8+z16.因此，φ(C2)是Z4上參數(shù)為(4,4122,4) 類型Ⅰ碼.

例3 考慮R上長(zhǎng)為3的自對(duì)偶碼.取C3=〈(0,1+v,1-v),(1+v,0,1-v),(2,2,2)〉，則C3是R上參數(shù)為(3,64,4)的極優(yōu)類型Ⅰ碼，其歐幾里得重量計(jì)數(shù)器為WC3(z)=1+12z4+27z8+20z12+3z16+z24.因此，φ(C3)是Z4上參數(shù)為(6,4222,4) 的類型Ⅰ碼.

例4 考慮R上長(zhǎng)為4的自對(duì)偶碼.在定理6的證明中，已經(jīng)給出一個(gè)R上的長(zhǎng)為4的(4,44,8)的極優(yōu)類型Ⅱ碼.該碼的Gray象是四元OCTA碼[1].若C4是R上的長(zhǎng)為4，且由下面5個(gè)向量生成的線性碼：(1,3,1,1+2v)，(0,2+2v,0,2+2v)，(2+v,2+v,1,3+2v)，(0,2,3+v,1+v)和(0,0,2,2)，則C4是R上參數(shù)為(4,256,8)的極優(yōu)類型Ⅱ碼，其歐幾里得重量計(jì)數(shù)器為WC4(z)=1+132z8+118z16+4z24+z32.因此，φ(C4)是Z4上參數(shù)為(8,4322,8)的極優(yōu)類型Ⅱ碼.

例5 考慮R上長(zhǎng)為6的自對(duì)偶碼.設(shè)C6是R上的長(zhǎng)為6，且由下列向量生成線性碼：(1-v,1-v,1-v,1-v,1-v,1-v)，(0,2v,0,0,0,2)，(0,0,2v,0,0,2)，(0,0,0,2v,0,2)，(0,0,0,0,2v,2)，(0,0,0,0,0,2+2v)，(2,0,0,0,0,2)，(0,2,0,0,0,2)，(0,0,2,0,0,2)，(0,0,0,2,0,2)，(0,0,0,0,2,2)，則C6是R上參數(shù)為(6,46,8)的極優(yōu)類型Ⅰ碼，其歐幾里得重量計(jì)數(shù)器為

WC6(z)=1+66z8+2048z12+495z16+924z24

+495z32+66z40+z48.

因此，φ(C6)是Z4上參數(shù)為(12,41210,8)的極優(yōu)類型Ⅰ碼.

例6 考慮R上長(zhǎng)為8的自對(duì)偶碼.

+15382z32+764z40+244z48+4z56+z64.

+17088z24+13056z28+6932z32+2560z36+608z40+128z44+28z48+z64.

(1,0,0,0,2+2v,3v,3v,3v),

(0,1,0,0,3v,2+2v,2+3v,2+v),

(0,0,1,0,3v,2+v,2+2v,2+3v)，

(0,0,0,1,3v,2+3v,2+v,2+2v).

5 總結(jié)

[1]Hammons A R Jr,Kumar P V,Calderbank A R,Sloane N J A,Solé P. TheZ4-linearity of Kerdock,Preparata,Goethals and related codes [J]. IEEE Transactions on Information Theory,1994,40(2): 301-319.

[2]吳波，朱士信，李平. 環(huán)Fp+uFp上的Kerdock碼與Preparata碼[J]. 電子學(xué)報(bào)，2008,36(7): 1364-1367.

Wo Bo,Zhu Shi-xin,Li Ping. Kerdock codes and Preparata codes over ringsFp+uFp[J]. Acta Electronica Sinica,2008,36(7): 1364-1367. (in Chinese)

[3]朱士信，許和乾，施敏加. 環(huán)Z4上線性碼關(guān)于RT距離MacWalliams恒等式[J]. 電子學(xué)報(bào)，2009，37(5): 1115-1118.

Zhu Shi-xin,Xu He-qian,Shi Min-jia. MacWalliams identities of linear codes over ringZ4with respect to the RT metric [J]. Acta Electronica Sinica,2009,37(5): 1115-1118. (in Chinese)

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

Shi Min-jia,Yang Shan-lin. MacWilliams identities of linear codes over non-principal ideal ringFp+vFp[J]. Acta Electronica Sinica,2011,39(10): 2449-2453. (in Chinese)

[5]Bachoc C. Applications of coding theory to the construction of modular lattices [J]. Journal of Combinatorial Theory Series A,1997,78(1): 92-119.

[6]Bonnecaze A,Solé P,Bachoc C,Mourrain B. Type Ⅱ codes overZ4[J]. IEEE Transactions on Information Theory,1997,43(3): 969-976.

[7]Dougherty S T,Gaborit P,Harada M,Solé P. Type Ⅱ codes overF2+uF2[J]. IEEE Transactions on Information Theory,1999,45(1): 32-45.

[8]Yildiz B,Karadeniz S. Self-dual codes overF2+uF2+vF2+uvF2[J]. Journal of the Franklin Institute,2010,347(10):1888-1894.

[9]Yildiz B,Karadeniz S. Linear codes overZ4+uZ4: MacWilliams identities,projections,and formally self-dual codes [J]. Finite Fields and Their Applications,2014,27: 24-40.

[10]Wood J. Duality for modules over finite rings and applications to coding theory [J].The American Journal of Mathematics,1999,121(3): 555-575.

[11]Doughterty S T,Kim J L,Kulosman H,Liu H W. Self-dual codes over commutative Frobenius rings [J]. Finite Fields and Their Applications,2010,16(1): 14-26.

袁 健 男，1988年生，合肥工業(yè)大學(xué)博士生，研究方向?yàn)榇鷶?shù)編碼.

E-mail: yuanjian@mail.hfut.edu.cn

朱士信(通信作者) 男，1962年生，合肥工業(yè)大學(xué)教授，博士生導(dǎo)師，國(guó)家級(jí)教學(xué)名師，國(guó)家“萬(wàn)人計(jì)劃”第一批教學(xué)名師. 長(zhǎng)期從事編碼理論、序列密碼與信息安全等研究.

E-mail: zhushixin@hfut.edu.cn

開曉山 男，1975年生，合肥工業(yè)大學(xué)副教授，碩士生導(dǎo)師，主要從事編碼理論與信息安全研究.

E-mail: kxs6@sina.com

A Method for Construction Self-dual Codes over Z4

YUAN Jian1,2,ZHU Shi-xin1,2,KAI Xiao-shan1,2

(1.SchoolofMathematics,HefeiUniversityofTechnology,Hefei,Anhui230009,China; 2.NationalMobileCommunicationsResearchLaboratory,SoutheastUniversity,Nanjing,Jiangsu210096,China)

Gray map; linear codes; self-dual codes

2015-07-08;

2016-01-04; 責(zé)任編輯：馬蘭英

國(guó)家自然科學(xué)基金(No.61370089 );東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室開放研究基金(No.2014D04);安徽省自然科學(xué)基金(No.JZ2015AKZR0021,No.1508085SQA198)

TN991.22

A

0372-2112 (2016)11-2807-05

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.034