自正交负循环码和随机拟阿贝尔码
|
摘要
本文主要研究两类码：有限域上自正交的负循环码和随机的拟阿贝尔码.
在第一章中,我们概述了本文所研究问题的背景及国内外研究现状,并简述了本文取得的结果.
在第二章中,我们研究了有限域上码长和域的特征互素的非零的自正交负循环码的存在性.利用有限域上多项式的分解和互反多项式,我们给出了非零的自正交负循环码存在的充要条件.
在第三章中,我们分两种情况研究了有限域上的随机拟阿贝尔码.首先,我们考虑余指数固定,指数趋于无穷的随机拟阿贝尔码.利用一阶矩和二阶矩方法,我们证明了GV界是相变点：对于给定的常数δ,若随机码的码率小于GV界在δ点的函数值,则码的相对距离大于δ的概率当指数趋于无穷时以1为极限；另一方面,若码率大于GV界在δ点的函数值,则上述概率以0为极限,其中GV界是指由Gilbert-Varshamov给出的渐进相对距离为δ的码能达到的最大码率的下界.作为推论,余指数固定的达到GV界的拟阿贝尔码是渐进好码.
我们也考虑了指数固定,余指数增长的随机拟阿贝尔码.利用一阶矩方法,我们证明了,对于给定的常数δ,当随机码的码率小于GV界在δ点的函数值时,码的相对距离大于δ的概率当余指数趋于无穷时以1为极限.进一步,利用素数定理,我们证明了指数为常数的达到GV界的拟阿贝尔码是渐进好码.
特别的,我们考虑了指数为2的自对偶的随机拟阿贝尔码.利用一阶矩方法和素数定理,我们证明了指数为2的自对偶的拟阿贝尔码是渐进好码.
This dessertation is focusing on topics of self-orthogonal negacyclic codes and random quasi-abelian codes over finite fields.
Chapter2presents necessary and sufficient conditions for the existence of nonzero self-orthogonal negacyclic codes over the finite field, of which the lengths are coprime to the characteristic of the underlying field.
Chapter3deals with random quasi-abelian codes over the finite field with q elements. For a random code with co-index fixed and index growing up, we prove that the GV-bound is a threshold point:as index becomes extremely large, the probability of the relative distance of the random code being greater than a given δ approaches1if the rate of the code is less than the GV-bound at δ; whereas, the probability approaches0if the rate is larger than the GV-bound at δ. As a consequence, there exist numerous asymptotically good quasi-abelian codes with parameters attaining the GV-bound.
For a random quasi-abelian code with index fixed and co-index growing up, if the rate of the code is less than the GV-bound at a given δ, we prove that the probability of the relative distance of the random codes being greater than δ approaches1as the co-index goes to infinity. By Prime Number Theorem, we prove the existence of good quasi-abelian codes with fixed index which attain the GV-bound.
Particularly, we prove that self-dual2-quasi-abelian codes are asymptotically good.
在第一章中,我们概述了本文所研究问题的背景及国内外研究现状,并简述了本文取得的结果.
在第二章中,我们研究了有限域上码长和域的特征互素的非零的自正交负循环码的存在性.利用有限域上多项式的分解和互反多项式,我们给出了非零的自正交负循环码存在的充要条件.
在第三章中,我们分两种情况研究了有限域上的随机拟阿贝尔码.首先,我们考虑余指数固定,指数趋于无穷的随机拟阿贝尔码.利用一阶矩和二阶矩方法,我们证明了GV界是相变点：对于给定的常数δ,若随机码的码率小于GV界在δ点的函数值,则码的相对距离大于δ的概率当指数趋于无穷时以1为极限；另一方面,若码率大于GV界在δ点的函数值,则上述概率以0为极限,其中GV界是指由Gilbert-Varshamov给出的渐进相对距离为δ的码能达到的最大码率的下界.作为推论,余指数固定的达到GV界的拟阿贝尔码是渐进好码.
我们也考虑了指数固定,余指数增长的随机拟阿贝尔码.利用一阶矩方法,我们证明了,对于给定的常数δ,当随机码的码率小于GV界在δ点的函数值时,码的相对距离大于δ的概率当余指数趋于无穷时以1为极限.进一步,利用素数定理,我们证明了指数为常数的达到GV界的拟阿贝尔码是渐进好码.
特别的,我们考虑了指数为2的自对偶的随机拟阿贝尔码.利用一阶矩方法和素数定理,我们证明了指数为2的自对偶的拟阿贝尔码是渐进好码.
This dessertation is focusing on topics of self-orthogonal negacyclic codes and random quasi-abelian codes over finite fields.
Chapter2presents necessary and sufficient conditions for the existence of nonzero self-orthogonal negacyclic codes over the finite field, of which the lengths are coprime to the characteristic of the underlying field.
Chapter3deals with random quasi-abelian codes over the finite field with q elements. For a random code with co-index fixed and index growing up, we prove that the GV-bound is a threshold point:as index becomes extremely large, the probability of the relative distance of the random code being greater than a given δ approaches1if the rate of the code is less than the GV-bound at δ; whereas, the probability approaches0if the rate is larger than the GV-bound at δ. As a consequence, there exist numerous asymptotically good quasi-abelian codes with parameters attaining the GV-bound.
For a random quasi-abelian code with index fixed and co-index growing up, if the rate of the code is less than the GV-bound at a given δ, we prove that the probability of the relative distance of the random codes being greater than δ approaches1as the co-index goes to infinity. By Prime Number Theorem, we prove the existence of good quasi-abelian codes with fixed index which attain the GV-bound.
Particularly, we prove that self-dual2-quasi-abelian codes are asymptotically good.
引文
[1]S. A. Aly, A. Klappenecker, P. K. Sarvepalli, "Duadic group algebra codes", arXiv:cs/0701060,2007.
[2]G. K. Bakshi, M. Raka, "Self-dual and self-orthogonal negacyclic codes of length 2pn over a finite field", Finite Fields Appl., vol.19, pp.39-54,2013.
[3]A. Barg, G. D. Forney, "Random codes:Minimum distances and error expo-nents", IEEE Trans. Inform. Theory, vol.48, pp.2568-2573,2002.
[4]L. M. J. Bazzi, S. K. Mitter, "Some randomized code constructions from group actions", IEEE Trans. Inform. Theory, vol.52, pp.3210-3219,2006.
[5]T. Blackford, "Negacyclic duadic codes", Finite Fields Appl., vol.14, pp.930-943,2008.
[6]I. F. Blake, S. Gao, R. C. Mullin, "Explicit factorization of X2k+1 over Fp with prime p≡3(mod 4)", Appl. Algebra Engrg. Comm. Comput., vol.4, pp. 89-94,1993.
[7]C. L. Chen, W. W. Peterson, E. J. Weldon, "Some results on quasi-cyclic codes", Information and Control, vol.15, pp.407-423,1969.
[8]V. Chepyzhov, "New lower bounds for minimum distance of linear quasi-cyclic and almost linear quasi-cyclic codes", Problemy Peredechi Inform., vol.28, pp. 33-44,1992.
[9]Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, John Wiley & Sons, Inc.,1991.
[10]B. K. Dey, B. S. Rajan, "Codes Closed Under Arbitrary Abelian Group of Permutations", SIAM J. Discrete Math., vol.18, pp.1-18,2004.
[11]H. Q. Dinh, "Repeated-root constacyclic codes of length 2ps", Finite Fields Appl., vol.18, pp.133-143,2012.
[12]H. Q. Dinh, "Structure of repeated-root constacyclic codes of length 3ps and their duals", Discrete Math., vol.313, pp.983-991,2013.
[13]Yun Fan, San Ling, Hongwei Liu, "Matrix product codes over finite commuta-tive Frobenius rings", Des. Codes Cryptogr., published online:July 2012. DOI 10.1007/s10623-012-9726-y.
[14]Yun Fan, San Ling, Hongwei Liu, Jing Shen and Chaoping Xing, "Cumulative distance enumerators of random codes and their thresholds", arXiv:1212.5679, 2012.
[15]Yun Fan, Jing Shen, "On the phase transitions of random k-constraint satis-faction problems", Artificial Intelligence, vol.175, pp.914-927,2011.
[16]W. Fu, T. Feng, "On self-orthogonal group ring codes", Des. Codes Cryptogr., vol.50, pp.203-214,2009.
[17]N. E. Gilbert, "A comparison of signalling alphabets", Bell Sys. Tech. Journal, vol.31, pp.504-522,1952.
[18]M. Greferath, M. E. O'Sullivan, "On bounds for codes over Frobenius rings under homogeneous weights", Discrete Math., vol.289, pp.11-24,2004.
[19]R. W. Hamming, "Error detecting and error codes", Bell Sys. Tech. Journal, vol.29, pp.147-160,1950.
[20]Helmut Hasse, "Uber die Dichte der primzahlen p, fur die eine vorgegebene ganzrationale zahl a≠0 von gerader bzw. ungerader ordnung mod.p ist", Math. Annalen, vol.166, pp.19-23,1966.
[21]W. C. Huffman, "On the classification and enumeration of self-dual codes", Finite Fields Appl., vol.11, pp.451-490,2005.
[22]W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press,2003.
[23]B. Huppert, N. Blackburn, Finite Groups II, Springer Verlag, Berlin,1982.
[24]Y. Jia, S. Ling, C. Xing, "On self-dual cyclic codes over finite fields", IEEE Trans. Inform. Theory, vol.57, pp.2243-2251,2011.
[25]X. Kai, S. Zhu, "On cyclic self-dual codes", Appl. Algebra Engrg. Comm. Com-put., vol.19, pp.509-525,2008.
[26]T. Kasami, "A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2", IEEE Trans. Inform. Theory, vol.20, pp.679-683,1974.
[27]L. Kathuria, M. Raka, "Existence of cyclic self-orthogonal codes:A note on a result of Vera Pless", Adv. Math. Commun., vol.6, pp.499-503,2012.
[28]J. C. Lagarias, "The set of primes dividing the Lucas numbers has density 2/3", Pacific J. Math, vol.118, pp.449-461,1985.
[29]R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 2008.
[30]San Ling, P. Sole, "Good self-dual quasi-cyclic codes exist", IEEE Trans. In-form. Theory, vol.49, pp.1052-1053,2003.
[31]C. Martinez-Perez, W. Willems, "Self-dual double-even 2-quasi-cyclic transitive codes are asymptotically good", IEEE Trans. Inform. Theory, vol.53, pp.4302-4308,2007.
[32]J. L. Massey, "On the fractional weight of distinct binary n-tuples", IEEE Trans. Inform. Theory, vol.20, pp.130,1974.
[33]B.R. McDonald, Finite Rings with Identity, Marcel Dekker Incorporated,1974.
[34]M. Mezard, A. Montanari, Information, Physics and Computation, Oxford Uni-versity Press,2009.
[35]M. Mitzenmacher, E. Upfal, Probability and Computing:Randomized Algo-rithm and Probabilistic Analysis, Cambridge Univ. Press,2005.
[36]A. A. Nechaev, T. Khonol'd, "Weighted modules and representations of codes", Probl. Peredachi Inf., vol.35, pp.18-39,1999.
[37]F. Ozbudak, P. Sole, "Gilbert-Varshamov type bounds for linear codes over finite chain rings", Adv. Math. Commun., vol.1, pp.99-109,2007.
[38]J. N. Pierce, "Limit distribution of the minimum distance of random linear codes", IEEE Trans. Inf. Theory, vol.13, pp.595-599,1967.
[39]P. H. Piret, "An upper bound on the weight distribution of some codes", IEEE Trans. Inform. Theory, vol.31, pp.520-521,1985.
[40]V. Pless, "Cyclotomy and cyclic codes, the unreasonable effectiveness of number theory", "Proc. Sympos. Appl. Math.", vol.46, pp.91-104,1992.
[41]I. E. Shparlinsky, "On weight enumerators of some codes", Problemy Peredechi Inform., vol.2, pp.43-48,1986.
[42]N. J. A. Sloane, J. G. Thompson, "Cyclic self-dual codes", IEEE Trans. Inform. Theory, vol.29, pp.364-367,1983.
[43]R. R. Varshamov, "Estimate of the number of signals in error-correcting codes" (in Russian), Dokl. Acad. Nauk, vol.117, pp.739-741,1957.
[44]Z. Wan, Lectures on Finite Fields and Galois Rings, World Scientific Publishing Co. Pte. Ltd,2003.
[45]S. K. Wasan, "Quasi Abelian codes", Publ. Inst. Math. (Beograd) N.S., vol.21, pp.201-206,1977.
[46]W. Willems, "A note on self-dual group codes", IEEE Trans. Inform. Theory, vol.48, pp.3107-3109,2002.
[2]G. K. Bakshi, M. Raka, "Self-dual and self-orthogonal negacyclic codes of length 2pn over a finite field", Finite Fields Appl., vol.19, pp.39-54,2013.
[3]A. Barg, G. D. Forney, "Random codes:Minimum distances and error expo-nents", IEEE Trans. Inform. Theory, vol.48, pp.2568-2573,2002.
[4]L. M. J. Bazzi, S. K. Mitter, "Some randomized code constructions from group actions", IEEE Trans. Inform. Theory, vol.52, pp.3210-3219,2006.
[5]T. Blackford, "Negacyclic duadic codes", Finite Fields Appl., vol.14, pp.930-943,2008.
[6]I. F. Blake, S. Gao, R. C. Mullin, "Explicit factorization of X2k+1 over Fp with prime p≡3(mod 4)", Appl. Algebra Engrg. Comm. Comput., vol.4, pp. 89-94,1993.
[7]C. L. Chen, W. W. Peterson, E. J. Weldon, "Some results on quasi-cyclic codes", Information and Control, vol.15, pp.407-423,1969.
[8]V. Chepyzhov, "New lower bounds for minimum distance of linear quasi-cyclic and almost linear quasi-cyclic codes", Problemy Peredechi Inform., vol.28, pp. 33-44,1992.
[9]Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, John Wiley & Sons, Inc.,1991.
[10]B. K. Dey, B. S. Rajan, "Codes Closed Under Arbitrary Abelian Group of Permutations", SIAM J. Discrete Math., vol.18, pp.1-18,2004.
[11]H. Q. Dinh, "Repeated-root constacyclic codes of length 2ps", Finite Fields Appl., vol.18, pp.133-143,2012.
[12]H. Q. Dinh, "Structure of repeated-root constacyclic codes of length 3ps and their duals", Discrete Math., vol.313, pp.983-991,2013.
[13]Yun Fan, San Ling, Hongwei Liu, "Matrix product codes over finite commuta-tive Frobenius rings", Des. Codes Cryptogr., published online:July 2012. DOI 10.1007/s10623-012-9726-y.
[14]Yun Fan, San Ling, Hongwei Liu, Jing Shen and Chaoping Xing, "Cumulative distance enumerators of random codes and their thresholds", arXiv:1212.5679, 2012.
[15]Yun Fan, Jing Shen, "On the phase transitions of random k-constraint satis-faction problems", Artificial Intelligence, vol.175, pp.914-927,2011.
[16]W. Fu, T. Feng, "On self-orthogonal group ring codes", Des. Codes Cryptogr., vol.50, pp.203-214,2009.
[17]N. E. Gilbert, "A comparison of signalling alphabets", Bell Sys. Tech. Journal, vol.31, pp.504-522,1952.
[18]M. Greferath, M. E. O'Sullivan, "On bounds for codes over Frobenius rings under homogeneous weights", Discrete Math., vol.289, pp.11-24,2004.
[19]R. W. Hamming, "Error detecting and error codes", Bell Sys. Tech. Journal, vol.29, pp.147-160,1950.
[20]Helmut Hasse, "Uber die Dichte der primzahlen p, fur die eine vorgegebene ganzrationale zahl a≠0 von gerader bzw. ungerader ordnung mod.p ist", Math. Annalen, vol.166, pp.19-23,1966.
[21]W. C. Huffman, "On the classification and enumeration of self-dual codes", Finite Fields Appl., vol.11, pp.451-490,2005.
[22]W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press,2003.
[23]B. Huppert, N. Blackburn, Finite Groups II, Springer Verlag, Berlin,1982.
[24]Y. Jia, S. Ling, C. Xing, "On self-dual cyclic codes over finite fields", IEEE Trans. Inform. Theory, vol.57, pp.2243-2251,2011.
[25]X. Kai, S. Zhu, "On cyclic self-dual codes", Appl. Algebra Engrg. Comm. Com-put., vol.19, pp.509-525,2008.
[26]T. Kasami, "A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2", IEEE Trans. Inform. Theory, vol.20, pp.679-683,1974.
[27]L. Kathuria, M. Raka, "Existence of cyclic self-orthogonal codes:A note on a result of Vera Pless", Adv. Math. Commun., vol.6, pp.499-503,2012.
[28]J. C. Lagarias, "The set of primes dividing the Lucas numbers has density 2/3", Pacific J. Math, vol.118, pp.449-461,1985.
[29]R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 2008.
[30]San Ling, P. Sole, "Good self-dual quasi-cyclic codes exist", IEEE Trans. In-form. Theory, vol.49, pp.1052-1053,2003.
[31]C. Martinez-Perez, W. Willems, "Self-dual double-even 2-quasi-cyclic transitive codes are asymptotically good", IEEE Trans. Inform. Theory, vol.53, pp.4302-4308,2007.
[32]J. L. Massey, "On the fractional weight of distinct binary n-tuples", IEEE Trans. Inform. Theory, vol.20, pp.130,1974.
[33]B.R. McDonald, Finite Rings with Identity, Marcel Dekker Incorporated,1974.
[34]M. Mezard, A. Montanari, Information, Physics and Computation, Oxford Uni-versity Press,2009.
[35]M. Mitzenmacher, E. Upfal, Probability and Computing:Randomized Algo-rithm and Probabilistic Analysis, Cambridge Univ. Press,2005.
[36]A. A. Nechaev, T. Khonol'd, "Weighted modules and representations of codes", Probl. Peredachi Inf., vol.35, pp.18-39,1999.
[37]F. Ozbudak, P. Sole, "Gilbert-Varshamov type bounds for linear codes over finite chain rings", Adv. Math. Commun., vol.1, pp.99-109,2007.
[38]J. N. Pierce, "Limit distribution of the minimum distance of random linear codes", IEEE Trans. Inf. Theory, vol.13, pp.595-599,1967.
[39]P. H. Piret, "An upper bound on the weight distribution of some codes", IEEE Trans. Inform. Theory, vol.31, pp.520-521,1985.
[40]V. Pless, "Cyclotomy and cyclic codes, the unreasonable effectiveness of number theory", "Proc. Sympos. Appl. Math.", vol.46, pp.91-104,1992.
[41]I. E. Shparlinsky, "On weight enumerators of some codes", Problemy Peredechi Inform., vol.2, pp.43-48,1986.
[42]N. J. A. Sloane, J. G. Thompson, "Cyclic self-dual codes", IEEE Trans. Inform. Theory, vol.29, pp.364-367,1983.
[43]R. R. Varshamov, "Estimate of the number of signals in error-correcting codes" (in Russian), Dokl. Acad. Nauk, vol.117, pp.739-741,1957.
[44]Z. Wan, Lectures on Finite Fields and Galois Rings, World Scientific Publishing Co. Pte. Ltd,2003.
[45]S. K. Wasan, "Quasi Abelian codes", Publ. Inst. Math. (Beograd) N.S., vol.21, pp.201-206,1977.
[46]W. Willems, "A note on self-dual group codes", IEEE Trans. Inform. Theory, vol.48, pp.3107-3109,2002.