中國剩余碼

第24卷第2期數學(xué)研究與評論VoL 24 No. 22004F5 JOURNAL OF MATHEMATICAL RESEARCH AND EXPOSITION May 200中國剩余碼張愛(ài)麗劉秀峰1.復旦大學(xué)計算機科學(xué)系,上海20043312.西南交通大學(xué)應用數學(xué)系,四川成都610031)搞要:本文利用弱區組設計和環(huán)論中的“中國剩余定理”杓造了中國剩余碼這種新型線(xiàn)性碼是將同余類(lèi)環(huán)R/I∩I2∩…∩,中的同余類(lèi)作為信息位,將R/J嵌入R/n∩2n…∩L,視其為R/n∩nan…∩L的子環(huán),R/J在R/1∩n2∩…∩中的陪集作為監督維線(xiàn)中國剩余碼中存在一系列碼率較高的碼類(lèi),它是孫子碼的本質(zhì)推廣關(guān)鍵詞:線(xiàn)性碼;同余類(lèi);陪集;環(huán)分類(lèi)號:AMS(200013H/ CLC Dumber o153文獻標識碼:A文章編號:1000341X(2004)020347-06建立在有限域基礎上的經(jīng)典代數編碼方法已日臻完善,而以組合設計為基礎的編碼理論是現代編碼理論的一個(gè)重要分支,組合編碼以其超限譯碼能力,功能的多樣性,使用的靈活性及編譯碼器的簡(jiǎn)單化,模塊化的結構正受到國內外編碼界的關(guān)注與重視.組合設計為組合編碼奠定了理論基礎,探索新型的組合設計是組合編碼的核心研究問(wèn)題之一,組合設計的一些新的特性不僅揭示了組合設計與線(xiàn)性碼的內在規律,同時(shí)也為構造新型的線(xiàn)性碼指出了一條路徑,文獻[1]和[2]提出了“孫子碼”,它是受我國古代的“孫子定理”的啟發(fā),利用整數環(huán)上的理想和同余類(lèi)而得到的一種新型線(xiàn)性碼本文就是將這種編碼方法推廣到一般的帶1的交換環(huán),并利用1998年由本文作者提出的弱區組設計的概念給出了一種新型的編碼方法為此我們先介紹弱區組設計的概念定義1(弱區組設計)設b,,r,k,λ均為正整數,X=(x1,x2,…,x},其中x1,x23,…,x是兩兩互異的元素B1,B2,…,B為X的b個(gè)子集(其中允許出現重復的子集),圖={B1,B2,…,B},以下將稱(chēng)B為區組,j=1,2,…b,即使B與B為重復的子集但i≠j我們仍然將B4與B視為不同的區組如果(X,)滿(mǎn)足下列條件(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時(shí),恒有|B∩B|≤λ,則稱(chēng)(X,)為X上的一個(gè)弱區組設計,記為WBD(b,v,r,k,A)·收稿日期:2001-03-05作者簡(jiǎn)介:張愛(ài)麗(1959),女,博士,副教授,現工作單位是西南交通大學(xué)數學(xué)系347中國煤化工CNMHG由定義可以看出:弱區組設計(WBD)是平衡不完全區組設計(BIBD)和異元平衡區組設計(DBBD)的推廣,WBD不要求每個(gè)區組包含同樣多的元素,也不要求每個(gè)元素在區組中出現的次數相等或者每?jì)蓚€(gè)區組的交集包含同樣多的元素更重要的是,弱區組設計與線(xiàn)性碼在同構意義下是一一對應的任給一個(gè)弱區組設計WBD(b,U,,k,A),存在一個(gè)線(xiàn)性碼C[n,h,d]與之對應其中nh,d分別表示碼長(cháng)維數與極小碼距并且諸參數滿(mǎn)足:n=b+v,h=v,[/4+1≤d≤r+1,[表示不小于/A的最小整數反之任給定一個(gè)線(xiàn)性碼C[n,h,d],則存在一個(gè)弱區組設計WBD(b,v,r,k,),使得該弱區組設計對應的線(xiàn)性碼C1=C1[b+v,,d]與C同構設WBD(b,v,r,k,)表示一個(gè)弱區組設計,A=(a1)b是它的關(guān)聯(lián)矩陣,即∫1,如果x∈B,0,如果x;∈B,其中X={x1,x2,…,x}表示W(wǎng)BD的頂點(diǎn)集,={B1,B2,…,B}表示區組族令G表示下面的分塊矩陣G=(,A),其中表示v階單位矩陣,則以G為生成矩陣的線(xiàn)性碼就是WBD對應的線(xiàn)性碼C[n,h,d]即以WBD的頂點(diǎn)為信息位以區組為監督維線(xiàn),同時(shí)以關(guān)聯(lián)矩陣為監督關(guān)系的線(xiàn)性碼就是C[nh,d]引理設R是帶1的交換環(huán),I1,I2,…,是R的s個(gè)兩兩互素的理想,并且R/為有限環(huán),|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,…,是環(huán)R中兩兩互素的理想,由“中國剩余定理,則有環(huán)的自然同構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的交換環(huán),l1,12,…,是R的5個(gè)兩兩互素的理想,并且R/I,為有限環(huán),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個(gè)同余類(lèi),每一個(gè)同余類(lèi)選取一個(gè)代表元素得到y,y2…,y,用R/I·中的同余類(lèi)作信息位,定義監督維線(xiàn)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按照上述信息位和監督維線(xiàn),可得到一個(gè)[n,h,d]線(xiàn)性碼,這里n,h,d分別表示碼長(cháng)維數和極小碼距,并且有∏m),h=Ⅱm,d=5+1(1)設是R/l1∩I2∩…∩的任意一個(gè)元素,x∈R是z的代表元素,即x+I°因為R有如下同余類(lèi)分解式R=(y+JU(y2+J)∪…U(y+J注意到不同的同余類(lèi)沒(méi)有公共元素,則x必屬于分解式中唯一的同余類(lèi)則被J對應的監督維線(xiàn)Bn,Ba,…,B1恰監督一次因此每個(gè)信息位恰被監督s次(2)每?jì)蓚€(gè)不同的信息位至多包含于一條監督維線(xiàn)之中事實(shí)上,設z1,z2包含于兩條不同的監督維線(xiàn)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)我們來(lái)計算信息位的個(gè)數.因為R/·中的同余類(lèi)表示信息位,所以只需計算R/r|·按照引理,則|R/|=|R/∩2∩…∩|=Ⅱm,(4)我們來(lái)計算監督維線(xiàn)的條數.因為以理想J為模的監督維線(xiàn)有n=|R/條,=1,2,…,再根據引理,有|R/J4(mm…m,m)=1Ⅱm因此分別以J1,J1,…,為模的監督維線(xiàn)Bn,1≤≤nB,1≤還≤n…,B,1≤j≤n合計(∑(1/m)m)條(5)設該線(xiàn)性碼對應的弱區組設計是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的一個(gè)子環(huán)注意到B;=1∈8/,十,=y(m0),1≤n,1R其m,kH-mm,則以理想J為模的監督維線(xiàn)的容量(即容納信息位的個(gè)數)等于(Ⅱm(Ⅱm)=m因此,參數k=min{m1,m2,…,m}6)從面得到這個(gè)線(xiàn)性碼的碼長(cháng)n=b+v=Ⅱm+∑(Ⅱm),維數h=Im,極小碼距d滿(mǎn)足不等式[]+1≤d≤r+1.即d=s+1350中國煤化工CNMHG定義2定理1給出的線(xiàn)性碼,我們將它命名為中國剩余碼注中國剩余碼本質(zhì)上是將同余類(lèi)環(huán)R/1∩I2∩…∩I,中的同余類(lèi)作為信息位,將R/J嵌入R/1∩I2∩…∩I,視為R/1∩I2∩…∩的子環(huán)將R/在R/1∩l∩…∩I中的陪集作為監督維線(xiàn)定理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,上的全體多項式構成的環(huán),即Fx]={f(x)|f(x)=∑ax,a4∈F,0≤i≤n,0≤n<∞),其中p為一個(gè)素數則F[x]是一個(gè)帶1的交換環(huán)將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得到一個(gè)線(xiàn)性碼C=C[n,h,,其中(1)碼長(cháng):n=m1m2+m1+m2=p2+2p;(2)維數:h=m1m2=p2;(3)極小碼距:d=s+1=3;(4)碼率:7=在定理1所給出的“中國剩余碼”中,特取R為整數環(huán)Z設m1,m2,…,m是5個(gè)兩兩互素的正整數,將m1,m2,…,m,各自生成的主理想作為I1,I2,…,I,即那么I1,I2,…,是R的5個(gè)兩兩互素的理想,并且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]劉秀峰張愛(ài)麗,仿射流形碼和射影流形碼[]西南交通大學(xué)學(xué)報,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]張愛(ài)麗.弱區組設計與一類(lèi)新型線(xiàn)性碼的研究[D]博士學(xué)位論文,西南交通大學(xué),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]成都:西南交通大學(xué)出版社,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.代數學(xué)(I)[M].曹錫華,曾肯成郝炳新譯,北京:科學(xué)出版社,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