一类环上循环码的结构特征与周期分布
|
摘要
循环码是线性分组码的一类重要子码,在理论和应用中都有着重要的科研价值。循环码比一般线性码拥有更多代数结构,因而引起编码和密码理论研究者的兴趣与关注。循环码的自身特性,又使得其在信息传递中更容易实现编译。随着有限域上循环码的编码理论的日益成熟,人们开始研究有限环上的循环码,已经有不少文献对剩余类环Z_4和四个元素的环F_2+u~2F_2上的循环码进行了研究,但对于八元环F_2+u~2F_2+u~2F_2上的循环码的研究却很少。本文主要研究八元环F_2+u~2F_2+uF_2上的循环码的结构和其周期分布。
循环码的周期分布,是一个较新的概念,其实质就是计数问题,与循环码的质量分布、码长、信息率一样,都是循环码的参数问题。杨义先、胡正名教授于1992年首次提出纠错码的周期分布概念后,引起了编码与密码领域的学者们的关注,许多学者都对有限域Fq上的循环码的周期分布做了进一步的研究,给出了一些计算码的周期分布的公式。探究循环码的周期分布,可以给出更好的非线性循环码,构造纠错能力更强的重码和置换码等,具有实际应用价值。
本文的主要工作:
(1)研究了R+F_2+u~2F_2+u~2F_2这类因式分解不唯一环上的一元多项式分解的一些性质,证明了x~n+1在R[x]中关于基本多项式的分解在不计较相伴元的前提下与它在F_2[x]中的分解相同,为R+F_2+u~2F_2+u~2F_2上循环码的研究奠定了基础。
(2)研究了R+F_2+uF_2+u~2F_2上奇数长循环码的结构,给出码长为n(n为奇数)的R+循环码的个数,即为x~n+1分解式中基本不可约因子的个数。
(3)讨论了环R+F_2+u~2F_2+u~2F_2上循环码的周期分布,给出奇数长循环码的周期分布计算公式。
Cyclic codes are an important sub-category of linear codes, invaluable in both theory and practice. Owing to their more rigorous algebraic structure over normal linear codes, cyclic codes are given particular attention by coding theorists and cryptographers. Cyclic codes also permit easier encoding and decoding in data transfer due to their properties.
As theories for cyclic codes over finite fields mature, research has begun on cyclic codes over finite rings. Current literature mostly cover cyclic codes over the residual class ring Z 4and the four-element ring F_2 + uF_2, but there exists scarce literature on the eight-element ring F_2 + u~2F_2 + u~2F_2. This paper mainly discusses the structure and period distribution of cyclic codes over the eight-element ring F_2 + uF_2 + u F_2.
The period distribution of cyclic codes is a novel idea in coding theory. At its core is a counting problem, which is a parameter of the code much like its quality distribution, code length and information rate. After the concept of period distribution was first proposed by Professors Yixian Yang and Zhengming Hu in 1992, many coding theorists and cryptographers have conducted research on, and yielded formulas for, period distribution of cyclic codes over finite fields Fq . By investigating the period distributions of codes, one can obtain better non-linear cyclic codes, as well as weight codes and permutation codes with stronger error-correction capabilities. There exist important practical uses of period distributions.
The main contributions of this paper are as follows.
(1) we discuss the factorization properties of polynomials with one variable over the non-unique factorization rings R + F_2 + u~2F_2 + u~2F_2. We prove that x n+ 1 yields the same basic polynomial factorization in R[ x ] and F_2 [ x ], disregarding associated elements, This forms the basis of research on cyclic codes over F_2 + u~2F_2 + u F_2.
(2) We discuss the structure of odd-length cyclic codes over F_2 + u~2F_2 + u~2F_2, and give the number of R-cyclic codes of code length n . This is the number of irreducible elements in the factorization of x~n+ 1.
(3) We discuss the period distribution of cyclic codes over F_2 + u~2F_2 + u~2F_2, and give the formula for calculating periodic distributions of odd-length cyclic codes.
循环码的周期分布,是一个较新的概念,其实质就是计数问题,与循环码的质量分布、码长、信息率一样,都是循环码的参数问题。杨义先、胡正名教授于1992年首次提出纠错码的周期分布概念后,引起了编码与密码领域的学者们的关注,许多学者都对有限域Fq上的循环码的周期分布做了进一步的研究,给出了一些计算码的周期分布的公式。探究循环码的周期分布,可以给出更好的非线性循环码,构造纠错能力更强的重码和置换码等,具有实际应用价值。
本文的主要工作:
(1)研究了R+F_2+u~2F_2+u~2F_2这类因式分解不唯一环上的一元多项式分解的一些性质,证明了x~n+1在R[x]中关于基本多项式的分解在不计较相伴元的前提下与它在F_2[x]中的分解相同,为R+F_2+u~2F_2+u~2F_2上循环码的研究奠定了基础。
(2)研究了R+F_2+uF_2+u~2F_2上奇数长循环码的结构,给出码长为n(n为奇数)的R+循环码的个数,即为x~n+1分解式中基本不可约因子的个数。
(3)讨论了环R+F_2+u~2F_2+u~2F_2上循环码的周期分布,给出奇数长循环码的周期分布计算公式。
Cyclic codes are an important sub-category of linear codes, invaluable in both theory and practice. Owing to their more rigorous algebraic structure over normal linear codes, cyclic codes are given particular attention by coding theorists and cryptographers. Cyclic codes also permit easier encoding and decoding in data transfer due to their properties.
As theories for cyclic codes over finite fields mature, research has begun on cyclic codes over finite rings. Current literature mostly cover cyclic codes over the residual class ring Z 4and the four-element ring F_2 + uF_2, but there exists scarce literature on the eight-element ring F_2 + u~2F_2 + u~2F_2. This paper mainly discusses the structure and period distribution of cyclic codes over the eight-element ring F_2 + uF_2 + u F_2.
The period distribution of cyclic codes is a novel idea in coding theory. At its core is a counting problem, which is a parameter of the code much like its quality distribution, code length and information rate. After the concept of period distribution was first proposed by Professors Yixian Yang and Zhengming Hu in 1992, many coding theorists and cryptographers have conducted research on, and yielded formulas for, period distribution of cyclic codes over finite fields Fq . By investigating the period distributions of codes, one can obtain better non-linear cyclic codes, as well as weight codes and permutation codes with stronger error-correction capabilities. There exist important practical uses of period distributions.
The main contributions of this paper are as follows.
(1) we discuss the factorization properties of polynomials with one variable over the non-unique factorization rings R + F_2 + u~2F_2 + u~2F_2. We prove that x n+ 1 yields the same basic polynomial factorization in R[ x ] and F_2 [ x ], disregarding associated elements, This forms the basis of research on cyclic codes over F_2 + u~2F_2 + u F_2.
(2) We discuss the structure of odd-length cyclic codes over F_2 + u~2F_2 + u~2F_2, and give the number of R-cyclic codes of code length n . This is the number of irreducible elements in the factorization of x~n+ 1.
(3) We discuss the period distribution of cyclic codes over F_2 + u~2F_2 + u~2F_2, and give the formula for calculating periodic distributions of odd-length cyclic codes.
引文
[1] Shannon C E. A Mathematical Theory of Communication[J]. Bell System Tech. Journal, 1948(27): 379-423,625-656.
[2] Hamming R. Error-Detecting and Error-Correcting Codes[J]. Bell System Tec- h. Journal, 1950(29): 147-160.
[3] Bose R, Chaudhuri D R. On a Class of Error-Correcting Binary Group Codes [J]. Inform Control, 1960(3): 68-79.
[4] Bose R, Chaudhuri D R. Further Results on Error-Correcting Binary Group C- odes[J]. Inform Control, 1960(3): 279-290.
[5] Hocquenghem A. Codes Correcteurs d’erreurs[J]. Chillers, 1959(2): 144-156.
[6] Gopph V D. Codes on Algebraic Curves[J]. Soviet Math. Dokl., 1981(24):75- 91.
[7] Goppa V D. Algebraic-Geometric Codes[J]. Math.USSR. Izvestiya, 1983(21): 75-91.
[8] Wolfmann J. Negacyclic and Cyclic Codes over Z 4[J]. IEEE Trans. Inform. T- heory, 1999,45(7): 2527-2532.
[9] Pless V S, Qian Z Q. Cyclic Codes and Quadratic Residue Codes over Z 4[J].I- EEE Trans. Inform. Theory, 1996,42(5): 1594-1600.
[10]钱建发,朱士信.2k1Z+环上长度为2e的常循环码[J].兰州大学学报, 2007,43 (1):135-137.
[11]胡万宝. 2kZ +线性负循环码[J].纯粹数学与应用数学, 2004,20(3):229-224.
[12]钱建发,朱士信. F_2 + uF_2 + + u kF_2环上的循环码[J].通信学报, 2006,27(9):86-88.
[13] Qian J F, Zhang L N, Zhu S X. (1 + u)Consta-Cyclic and Cyclic Codes over F_2 + uF_2[J]. Appl. Math. Letters, 2006(19): 820-823.
[14] Byrne E. Decoding a Class of Lee Metric Codes over Galois Rings[J]. IEEE Tr- ans. Inform. Theory, 2002,48(4): 966-975.
[15] Babu N S, Zimmermann K H. Decoding of Linear Codes over Galois Rings[J]. IEEE Trans. Inform. Theory, 2001,47(4): 1599-1603.
[16] Tapia-Recillas H, Vega G. Some Constacyclic Codes over 2kZ and Binary Quasi- Cyclic Codes[J]. Disc. Appl. Math., 2003,128(1): 305-316.
[17] Carlet C. 2kZ +Linear Codes[J]. IEEE Trans. Inform. Theory, 1998(4): 1543-1547.
[18] Ling S, Blackford T.Zpk1++Linear Codes[J]. IEEE Trans. Inform. Theory, 2002, (48): 2592-2605.
[19]余海峰,朱士信.环F_2 + uF_2上线性码及其对偶码的二元象[J].电子与信息学报,2006,28(11):2121-2123.
[20] Macwilliam F J, Sloane N J A. The Theory of Error-Correcting Codes[M]. Am- sterdam: North-Holland, 1977:201-267.
[21] Roth R, Seroussl G. On Cyelic MDS Codes of Length q over GF ( q )[J]. IE- EE Trans. Inform. Theory, 1986,32(2): 284-285.
[22] Tucker A. Applied Combinatories[M]. John Wiley and Sons, 1984.
[23]杨义先,胡正名.纠错码的周期分布[J].通信学报,1992,13(3):50-54.
[27]符方伟,沈世镒.循环码的周期分布的新的计算公式[J].通信学报,1996, 17(2):1-6.
[28] Bonnecaza A, Udaya P. Cyclic Codes and Self-Dual Codes over F_2 + uF_2[J].I- EEE Trans. Inform. Theory, 1999 (45):4-5.
[29] Moisio,M.J. The Moments of a Kloosterman Sum and the Weight Distribution of a Zetterberg-Type Binary Cyclic Code[J]. IEEE Trans. Inform. Theory, 2007 53(2): 843-847.
[30]李超,谢冬青.循环码周期分布的反问题[J].应用科学学报,2000,18(2):101-103.
[31]聂灵沼,丁石孙.代数学引论[M].北京:高等教育出版社,2005.
[32]郑宝东,张春蕊.矩阵与编码[M].北京:科学出版社,2009.
[33] Atiyah M F, MacDonald I G. Introduction to Commutative Algebra[M]. Addi- son-Wesley, 1969.
[34]万哲先.代数与编码[M].北京:高等教育出版社,2007.
[35]杨义先,林须端.编码密码学[M].北京:人民邮电出版社,1992.
[36]肖国镇,卿斯汉.编码理论[M].北京:国防工业出版社,1993:1-305.
[37]王萼芳,石生明.高等代数[M].北京:高等教育出版社,2004:243-320.
[38]刘玉君,邓承志.准循环码和双环循环码的研究[J].信息工程大学学报,2007,8(4):487-489.
[39]盖新貌.环F_2 + uF_2上循环码的结构特征与周期分布[D].合肥:国防科技大学,2006.
[40] Wan Z X. Quaternary Codes[M]. Singapore: World Scientific, 1997.
[41] Mcdonald B R. Finite Rings with Identity[M]. New York: Marcel Dekker,1974.
[42] Bonnecaze A, Udaya P. Cyclic Codes and Self-Dual Codes over F_2 + uF_2[J].I- EEE Trans. Inform. Theory, 1999,45(5):1250-1255.
[43]万哲先.代数导引[M].北京:科学出版社,2004.
[44] Feng Q Q, Zhou W G. Cyclic Code and Self-Dual Code over F_2 + uF_2+u~2 F_2[J]. Mathematical Research Exposition, 2009,29(3):500-506.
[45]施加敏.有限环上线性码的结构及其秩的研究[D].合肥:合肥工业大学,2007.
[2] Hamming R. Error-Detecting and Error-Correcting Codes[J]. Bell System Tec- h. Journal, 1950(29): 147-160.
[3] Bose R, Chaudhuri D R. On a Class of Error-Correcting Binary Group Codes [J]. Inform Control, 1960(3): 68-79.
[4] Bose R, Chaudhuri D R. Further Results on Error-Correcting Binary Group C- odes[J]. Inform Control, 1960(3): 279-290.
[5] Hocquenghem A. Codes Correcteurs d’erreurs[J]. Chillers, 1959(2): 144-156.
[6] Gopph V D. Codes on Algebraic Curves[J]. Soviet Math. Dokl., 1981(24):75- 91.
[7] Goppa V D. Algebraic-Geometric Codes[J]. Math.USSR. Izvestiya, 1983(21): 75-91.
[8] Wolfmann J. Negacyclic and Cyclic Codes over Z 4[J]. IEEE Trans. Inform. T- heory, 1999,45(7): 2527-2532.
[9] Pless V S, Qian Z Q. Cyclic Codes and Quadratic Residue Codes over Z 4[J].I- EEE Trans. Inform. Theory, 1996,42(5): 1594-1600.
[10]钱建发,朱士信.2k1Z+环上长度为2e的常循环码[J].兰州大学学报, 2007,43 (1):135-137.
[11]胡万宝. 2kZ +线性负循环码[J].纯粹数学与应用数学, 2004,20(3):229-224.
[12]钱建发,朱士信. F_2 + uF_2 + + u kF_2环上的循环码[J].通信学报, 2006,27(9):86-88.
[13] Qian J F, Zhang L N, Zhu S X. (1 + u)Consta-Cyclic and Cyclic Codes over F_2 + uF_2[J]. Appl. Math. Letters, 2006(19): 820-823.
[14] Byrne E. Decoding a Class of Lee Metric Codes over Galois Rings[J]. IEEE Tr- ans. Inform. Theory, 2002,48(4): 966-975.
[15] Babu N S, Zimmermann K H. Decoding of Linear Codes over Galois Rings[J]. IEEE Trans. Inform. Theory, 2001,47(4): 1599-1603.
[16] Tapia-Recillas H, Vega G. Some Constacyclic Codes over 2kZ and Binary Quasi- Cyclic Codes[J]. Disc. Appl. Math., 2003,128(1): 305-316.
[17] Carlet C. 2kZ +Linear Codes[J]. IEEE Trans. Inform. Theory, 1998(4): 1543-1547.
[18] Ling S, Blackford T.Zpk1++Linear Codes[J]. IEEE Trans. Inform. Theory, 2002, (48): 2592-2605.
[19]余海峰,朱士信.环F_2 + uF_2上线性码及其对偶码的二元象[J].电子与信息学报,2006,28(11):2121-2123.
[20] Macwilliam F J, Sloane N J A. The Theory of Error-Correcting Codes[M]. Am- sterdam: North-Holland, 1977:201-267.
[21] Roth R, Seroussl G. On Cyelic MDS Codes of Length q over GF ( q )[J]. IE- EE Trans. Inform. Theory, 1986,32(2): 284-285.
[22] Tucker A. Applied Combinatories[M]. John Wiley and Sons, 1984.
[23]杨义先,胡正名.纠错码的周期分布[J].通信学报,1992,13(3):50-54.
[27]符方伟,沈世镒.循环码的周期分布的新的计算公式[J].通信学报,1996, 17(2):1-6.
[28] Bonnecaza A, Udaya P. Cyclic Codes and Self-Dual Codes over F_2 + uF_2[J].I- EEE Trans. Inform. Theory, 1999 (45):4-5.
[29] Moisio,M.J. The Moments of a Kloosterman Sum and the Weight Distribution of a Zetterberg-Type Binary Cyclic Code[J]. IEEE Trans. Inform. Theory, 2007 53(2): 843-847.
[30]李超,谢冬青.循环码周期分布的反问题[J].应用科学学报,2000,18(2):101-103.
[31]聂灵沼,丁石孙.代数学引论[M].北京:高等教育出版社,2005.
[32]郑宝东,张春蕊.矩阵与编码[M].北京:科学出版社,2009.
[33] Atiyah M F, MacDonald I G. Introduction to Commutative Algebra[M]. Addi- son-Wesley, 1969.
[34]万哲先.代数与编码[M].北京:高等教育出版社,2007.
[35]杨义先,林须端.编码密码学[M].北京:人民邮电出版社,1992.
[36]肖国镇,卿斯汉.编码理论[M].北京:国防工业出版社,1993:1-305.
[37]王萼芳,石生明.高等代数[M].北京:高等教育出版社,2004:243-320.
[38]刘玉君,邓承志.准循环码和双环循环码的研究[J].信息工程大学学报,2007,8(4):487-489.
[39]盖新貌.环F_2 + uF_2上循环码的结构特征与周期分布[D].合肥:国防科技大学,2006.
[40] Wan Z X. Quaternary Codes[M]. Singapore: World Scientific, 1997.
[41] Mcdonald B R. Finite Rings with Identity[M]. New York: Marcel Dekker,1974.
[42] Bonnecaze A, Udaya P. Cyclic Codes and Self-Dual Codes over F_2 + uF_2[J].I- EEE Trans. Inform. Theory, 1999,45(5):1250-1255.
[43]万哲先.代数导引[M].北京:科学出版社,2004.
[44] Feng Q Q, Zhou W G. Cyclic Code and Self-Dual Code over F_2 + uF_2+u~2 F_2[J]. Mathematical Research Exposition, 2009,29(3):500-506.
[45]施加敏.有限环上线性码的结构及其秩的研究[D].合肥:合肥工业大学,2007.