中国剩余码

第24卷第2期数学研究与评论VoL 24 No. 22004F5 JOURNAL OF MATHEMATICAL RESEARCH AND EXPOSITION May 200中国剩余码张爱丽刘秀峰1.复旦大学计算机科学系,上海20043312.西南交通大学应用数学系,四川成都610031)搞要:本文利用弱区组设计和环论中的“中国剩余定理”杓造了中国剩余码这种新型线性码是将同余类环R/I∩I2∩…∩,中的同余类作为信息位,将R/J嵌入R/n∩2n…∩L,视其为R/n∩nan…∩L的子环,R/J在R/1∩n2∩…∩中的陪集作为监督维线中国剩余码中存在一系列码率较高的码类,它是孙子码的本质推广关键词:线性码;同余类;陪集;环分类号:AMS(200013H/ CLC Dumber o153文獻标识码:A文章编号:1000341X(2004)020347-06建立在有限域基础上的经典代数编码方法已日臻完善,而以组合设计为基础的编码理论是现代编码理论的一个重要分支,组合编码以其超限译码能力,功能的多样性,使用的灵活性及编译码器的简单化,模块化的结构正受到国内外编码界的关注与重视.组合设计为组合编码奠定了理论基础,探索新型的组合设计是组合编码的核心研究问题之一,组合设计的一些新的特性不仅揭示了组合设计与线性码的内在规律,同时也为构造新型的线性码指出了一条路径,文献[1]和[2]提出了“孙子码”,它是受我国古代的“孙子定理”的启发,利用整数环上的理想和同余类而得到的一种新型线性码本文就是将这种编码方法推广到一般的带1的交换环,并利用1998年由本文作者提出的弱区组设计的概念给出了一种新型的编码方法为此我们先介绍弱区组设计的概念定义1(弱区组设计)设b,,r,k,λ均为正整数,X=(x1,x2,…,x},其中x1,x23,…,x是两两互异的元素B1,B2,…,B为X的b个子集(其中允许出现重复的子集),图={B1,B2,…,B},以下将称B为区组,j=1,2,…b,即使B与B为重复的子集但i≠j我们仍然将B4与B视为不同的区组如果(X,)满足下列条件(1)对于任意的j∈1,2,…,b},恒有|B≥k,并且存在B4使得|B|=k(2)设B={B1≤j≤b,x∈B}(1≤i≤v),对任意的∈(1,2,…,v),恒有|B°≥r,并且存在B使得|B|=r;(3)当1≤i≠j≤v时,恒有|B∩B|≤λ,则称(X,)为X上的一个弱区组设计,记为WBD(b,v,r,k,A)·收稿日期:2001-03-05作者简介:张爱丽(1959),女,博士,副教授,现工作单位是西南交通大学数学系347中国煤化工CNMHG由定义可以看出:弱区组设计(WBD)是平衡不完全区组设计(BIBD)和异元平衡区组设计(DBBD)的推广,WBD不要求每个区组包含同样多的元素,也不要求每个元素在区组中出现的次数相等或者每两个区组的交集包含同样多的元素更重要的是,弱区组设计与线性码在同构意义下是一一对应的任给一个弱区组设计WBD(b,U,,k,A),存在一个线性码C[n,h,d]与之对应其中nh,d分别表示码长维数与极小码距并且诸参数满足:n=b+v,h=v,[/4+1≤d≤r+1,[表示不小于/A的最小整数反之任给定一个线性码C[n,h,d],则存在一个弱区组设计WBD(b,v,r,k,),使得该弱区组设计对应的线性码C1=C1[b+v,,d]与C同构设WBD(b,v,r,k,)表示一个弱区组设计,A=(a1)b是它的关联矩阵,即∫1,如果x∈B,0,如果x;∈B,其中X={x1,x2,…,x}表示WBD的顶点集,={B1,B2,…,B}表示区组族令G表示下面的分块矩阵G=(,A),其中表示v阶单位矩阵,则以G为生成矩阵的线性码就是WBD对应的线性码C[n,h,d]即以WBD的顶点为信息位以区组为监督维线,同时以关联矩阵为监督关系的线性码就是C[nh,d]引理设R是带1的交换环,I1,I2,…,是R的s个两两互素的理想,并且R/为有限环,|R/I,|=m;,=1,2,…,5,J1=I:∩I3∩…∩I,J2=l1∩I3∩…∩r,J=l1∩l2∩…∩l-1(1)|R/1∩n2n…∩H=Ⅱm;(2)|R/,|=(mm2…m,)/m,证明(1)因为l1,I2,…,是环R中两两互素的理想,由“中国剩余定理,则有环的自然同构R/l1n2∩…∩L,R/1R/I2…④R/,a(mod∩)→(a(modl1),a(modl2),…,a(modl2)按假设|R/I,=m,1≤i≤s,对于任意的a∈R/l1∩I2∩…∩I,a能够一意地表示为因此,R/1∩I2∩…∩I,=m1m2…m1(2)因为R/J,=R/I1∩…∩I-1∩I+∩…∩L,再根据“中国剩余定理”,可以得到R/J≈R/1④…⊕R/I-1R/+1…R/I,348中国煤化工CNMHGa(modJ4)→(a(modI1),…,a(modI-1),a(modI,+1),…,a(mod)),所以有|R/J=m1…m-m+1…m,=(m1m2…m,)m定理1(1)设R是带1的交换环,l1,12,…,是R的5个两两互素的理想,并且R/I,为有限环,1≤i≤5;I=l1nI2∩…∩I,J1=l2∩I3∩…∩I,r,∩I3∩…∩LJ=I∩I2∩…∩L(3)设|R/|=m1,1≤i≤5;(4)设R/J,中含有n个同余类,每一个同余类选取一个代表元素得到y,y2…,y,用R/I·中的同余类作信息位,定义监督维线B1=(∈R/I,=x+I,x≡y(modJ1)},1≤j≤nB2=(|∈R/,=x+I,x≡y(mod/2)},1≤j≤n2lB,={∈RH·,=x+I,xy(mod)},1≤j≤n按照上述信息位和监督维线,可得到一个[n,h,d]线性码,这里n,h,d分别表示码长维数和极小码距,并且有∏m),h=Ⅱm,d=5+1(1)设是R/l1∩I2∩…∩的任意一个元素,x∈R是z的代表元素,即x+I°因为R有如下同余类分解式R=(y+JU(y2+J)∪…U(y+J注意到不同的同余类没有公共元素,则x必属于分解式中唯一的同余类则被J对应的监督维线Bn,Ba,…,B1恰监督一次因此每个信息位恰被监督s次(2)每两个不同的信息位至多包含于一条监督维线之中事实上,设z1,z2包含于两条不同的监督维线B1和B2,即1,x2}s(B,∩B,,),1,2∈RI°,王1≠x2,1=x1+I,2=x2+I,x1≠x2(mod'),x1,x2∈R,并且(1,)≠(2,1),1≤i1,≤,1≤h≤m,1≤力≤n1(1)x2≡y(modJ1),349中国煤化工CNMHG首先注意到i≠i2倘若i1=i2,则j1≠j则x1=y(mod1),1≤h≤n1,x≡y(mod),1≤h≤m1,则y=y(modJ1),与方≠方矛盾由(1)式可得0(mod,)x1-x2≡0(modJ,)(2)因为≠,4=,,,=Q,所以山三1则I1-I2=0(mod, )x1-x2≡0(modl;)x一x∈小1,x-x∈I1则x1-x2∈J1∩1=h1∩l2n…∩1=1即1-2=0,这里0表示RI中的零元这与z1≠王2矛盾(3)我们来计算信息位的个数.因为R/·中的同余类表示信息位,所以只需计算R/r|·按照引理,则|R/|=|R/∩2∩…∩|=Ⅱm,(4)我们来计算监督维线的条数.因为以理想J为模的监督维线有n=|R/条,=1,2,…,再根据引理,有|R/J4(mm…m,m)=1Ⅱm因此分别以J1,J1,…,为模的监督维线Bn,1≤≤nB,1≤还≤n…,B,1≤j≤n合计(∑(1/m)m)条(5)设该线性码对应的弱区组设计是WBD(b,U,r,k,A),容易看出Ⅱm),0=Ⅱm,r=5,k=1.m声因为R/I1∩…∩I≈R/1R/2…R/R/J,R/1由…R∥I-1R/I+1…⊕R/,(6)所以R/J可以嵌人R/r∩2∩…∩I,视为R/1∩I2∩…∩L的一个子环注意到B;=1∈8/,十,=y(m0),1≤n,1R其m,kH-mm,则以理想J为模的监督维线的容量(即容纳信息位的个数)等于(Ⅱm(Ⅱm)=m因此,参数k=min{m1,m2,…,m}6)从面得到这个线性码的码长n=b+v=Ⅱm+∑(Ⅱm),维数h=Im,极小码距d满足不等式[]+1≤d≤r+1.即d=s+1350中国煤化工CNMHG定义2定理1给出的线性码,我们将它命名为中国剩余码注中国剩余码本质上是将同余类环R/1∩I2∩…∩I,中的同余类作为信息位,将R/J嵌入R/1∩I2∩…∩I,视为R/1∩I2∩…∩的子环将R/在R/1∩l∩…∩I中的陪集作为监督维线定理2设中国剩余码的码率为n,m的意义与定理1中的相同,1≤i≤5,则7=M(M+∑M),其中M=1m1,1≤i≤证明略推论如果m1≤m1≤…≤m则中国剩余码的码率η有下列估计式7≥m1/(m1+s)证明因为m1≤m2≤…≤m,且M=(1/m,Ⅱm,故M≥M1≥…≥M.由定2得到:7=M/(M+∑M)≥M/(M+sM)=(mm2…m)/(mm…m十m,m…m)例设F[]表示有限域F,上的全体多项式构成的环,即Fx]={f(x)|f(x)=∑ax,a4∈F,0≤i≤n,0≤n<∞),其中p为一个素数则F[x]是一个带1的交换环将F[x作为定理1中的R设l1和l2分别为x和x+1生成的主理想,即1=(x),l2=(x+1)因为x+1-x=1,故l1+l2=R,l1与l2互素容易看出R/1={=k十I1,k=0,1,…,p一1},R/I2={=k+I2,k=0,1,…,p一1}所以,|R∥1=P,|R/I2l=p按照定理1得到一个线性码C=C[n,h,,其中(1)码长:n=m1m2+m1+m2=p2+2p;(2)维数:h=m1m2=p2;(3)极小码距:d=s+1=3;(4)码率:7=在定理1所给出的“中国剩余码”中,特取R为整数环Z设m1,m2,…,m是5个两两互素的正整数,将m1,m2,…,m,各自生成的主理想作为I1,I2,…,I,即那么I1,I2,…,是R的5个两两互素的理想,并且R/I1∩I2∩…∩I={1,2,…,M}(modM)351中国煤化工CNMHGR/J=R/1n…∩I-1∩+∩…∩L,={1,2,…,M1}(modM),M=M/m,1≤i≤s.参考文献[1]刘秀峰张爱丽,仿射流形码和射影流形码[]西南交通大学学报,199,33(4):470-474.LIU Xiu-feng, ZHANG Ai-li. Affine manifold codes and projective manifold codes [J]. Journal ofuthwest Jiaotong University, 1998, 33(4):470-474. (in Chinese)[2]张爱丽.弱区组设计与一类新型线性码的研究[D]博士学位论文,西南交通大学,199ZHANG Ai-li. Study on weak block designs and a new class of linear codes [D]. Ph.D. Thesis, South-west Jiaotong University, 1999. (in Chinese)[3] JACOBSON. Theory of Rings [M]. New York,1943,68-80.[4]靳蕃.组合设计与编码[M]成都:西南交通大学出版社,1990,361-395.JIN Fan. Combinatorial Designs and Coding [M]. Chengdu: Publishing House of Southwest JiaotongUniversity, 1990, 361-395. (in Chinese)[5] Van Lint J H. Introduction to Coding Theory [M]. Berlin: Springer-Verlag, 1982, 15-83[6] Van der Waerden B L.代数学(I)[M].曹锡华,曾肯成郝炳新译,北京:科学出版社,1976:450494Van der Waerden B L. Algebra (I)[M]. Translated by Cao Xi-hua, ZENG Ken-cheng, HAO Bing-xin. Beijing: Science Publishing House, 1976, 450-494. (in ChineseChinese Remainder CodesZHANG Ai-Ii'lU Xiu-feng(1. Dept. of Computer Science, Fudan University, Shanghai 200433, China;2. Dept. of Appl. Math., Southwest Jiaotong University, Chengdu 610031, China)Abstract: Chinese remainder codes are constructed by applying the weak block design andChinese remainder theorem of ring theory. The new type of linear codes are to take the con-gruence class in the congruence class ring R/l1∩Iz∩…∩ I for the information bit,toem-bedR/ Ji into r/l;nI2∩…∩Inas& subring of R/l1nIn…∩I., and to regard thecosets of r/JinR/1∩I2∩…∩ I as check lines. There exist many code classes in Chineseremainder codes, which have higher code rate. Chinese remainder codes are essential generalization of Sun Zhi codesKey words t linear code; congruence class; coset; ring352中国煤化工CNMHG