置换码的界及构造的研究
|
摘要
长为n,最小距离为d的置换码(阵列)记为(n,d)置换码,是关于某n个元素的置换的集合C,并且对任意不同的x,y∈C,它们之间的汉明距离至少为d。令P(n,d)记为(n,d)置换码的码元数量的最大可能值。若(n,d)置换码C的大小|C| =P(n,d)则称之为最优化置换码。P(n,d)的值的研究被认为是置换码研究的基本问题。
置换码曾在上世纪70年代有过零星的研究,由于Vinck (Coded modulation forpowerline communications, Proc. Int. J. Elec. Commun., vol. 54, no. 1, 2000)提出置换码可应用于电力线通信上的纠错编码,而重新引起了学术界的研究兴趣。本文主要对置换码理论的最基本问题–置换码的上、下界和构造–进行了深入研究。我们取得的
主要结果如下所列:
1.我们证明了一个关于P(n,d)和PΩ(n,d)的不等式。
2.我们给出了P(n,d,w)的若干基本性质,然后基于它们分别给出P(n, 2k)和P(n,2k + 1)的新上界。当常数α,β满足某些条件时,若d =βn~α,则新上界渐近优于以往的上界。
3.基于Jiang和Vardy提出的图论框架,给出了P(n,d)的Gilbert-Varshamov下界的三个改进。
4.通过考虑覆盖球的交集,给出了P(n,d)的Gilbert-Varshamov下界的二个改进。
5.提出了从(n,d)置换码分别构造(n - 1,d - 3)和(n - 1,d - 2)置换码的方法,由此给出当n和d取某些情况时置换码的新下界。
6.提出两个由有限域上的分式多项式构造置换码的方法,并由此得到置换码的一些新下界。
7.证明了阶为n,最小度为d的置换群和(n,d)置换码的关系,由此得到置换码的一些新下界。
8.给出了由二元码构造置换码的三个新构造,前两个构造建立了P(n,d),DP(n,d)和CP(n,d)之间的一些令人感兴趣的不等式,后一个构造比直接构造更加有效地利用距离保持映射从二元码构造置换码。
9.广义码是各种具体码的抽象形式,包括置换码和二元码等。给出广义码的Gilbert-Varshamov界的一个简单新证明,接着证明了一个简单随机构造算法只需要较低的复杂度就能以较大的概率得到较大的码,而以前的Altruisitic算法由于复杂度太高实际上难以实现。当简单随机构造算法应用于构造置换码时,与Keevash和Ku提出的半随机构造算法比较,不仅没有苛刻的实现条件,而且需要更少的时间。
10.二元码和置换码有着密切关系。我们给出了二元码距离分布的几个新的线性不等式,给出改进Johnson界的一个更加简单的新证明。
A permutation code(array) of length n and minimum distance d, denoted by (n,d)permutation code, is a set of permutations C from some fixed set of n elements such thatthe Hamming distance between distinct members x, y∈C is at least d. Let P(n,d) denotethe maximum size of an (n,d) permutation code. A (n,d) permutation code C such that|C| = P(n,d) is called optimal. The study of the numbers P(n,d) is considered to be theessential problem of permutation code.
Permutation codes are somewhat studied in the 1970s. Vinck (Coded modulation forpowerline communications, Proc. Int. J. Elec. Commun., vol. 54, no. 1, 2000) renewedinterest in permutation codes by proposing it as an error correcting code for powerline com-munications. In this paper, we focus on the most essential problems on theory of permutationcodes– the bounds and constructions. Our main results are listed as followed:
1. We prove a relation between P(n,d) and PΩ(n,d).
2. We give some elementary properties of P(n,d,w), and then use them to show newupper bounds on P(n, 2k) and P(n, 2k + 1). For constantα,βsatisfying certainconditions, whenever d =βnα, the new upper bounds are asymptotically better thanthe previous ones.
3. Based on the graph theorem framework presented by Jiang and Vardy, we give threeimprovements over the Gilbert-Varshamov lower bounds on P(n,d).
4. By considering the covered balls intersection, we give two improvements over theGilbert-Varshamov lower bounds on P(n,d).
5. By presenting constructions of (n-1,d-3) and (n-1,d-2) permutation codes from(n,d) permutation codes, some new lower bounds for permutation codes are given forspecial cases for n and d.
6. We present two constructions of permutation codes from factional polynomials overfinite field, which produce some new lower bounds for permutation codes.
7. We show a relation between permutation group with degree n and minimal degree dand (n,d) permutation codes, which leads to some new lower bounds for permutationcodes.
8. We present three new constructions of permutation codes from binary codes, in whichthe first two constructions lead to some interested inequalities on P(n,d),DP(n,d)and CP(n,d), and the third construction gives larger permutation codes from knownbinary codes using preserve-distance mapping compared to direct construction.
9. The generalized code is the generalized form of concrete code, including permutationcodes, binary codes, et. al.. We give a new simple proof of Gilbert-Varshamov boundfor generalized codes, and present a simple random construction algorithm with lowercomplexity which is proved to obtain large code with significant probability, while theprevious Altruisitic algorithm is too complexity to be realized. Compared with semi-random construction presented by Keevash and Ku, the simple random constructionalgorithm does not require the strict conditions for realization and needs less timewhen it is applied to the constructions of permutation codes.
10. The binary code has closed relations with permutation code. We give several newinequalities for distance distributions of binary codes, and presented an new proof ofthe improved Johnson bound which is simpler than the original one.
置换码曾在上世纪70年代有过零星的研究,由于Vinck (Coded modulation forpowerline communications, Proc. Int. J. Elec. Commun., vol. 54, no. 1, 2000)提出置换码可应用于电力线通信上的纠错编码,而重新引起了学术界的研究兴趣。本文主要对置换码理论的最基本问题–置换码的上、下界和构造–进行了深入研究。我们取得的
主要结果如下所列:
1.我们证明了一个关于P(n,d)和PΩ(n,d)的不等式。
2.我们给出了P(n,d,w)的若干基本性质,然后基于它们分别给出P(n, 2k)和P(n,2k + 1)的新上界。当常数α,β满足某些条件时,若d =βn~α,则新上界渐近优于以往的上界。
3.基于Jiang和Vardy提出的图论框架,给出了P(n,d)的Gilbert-Varshamov下界的三个改进。
4.通过考虑覆盖球的交集,给出了P(n,d)的Gilbert-Varshamov下界的二个改进。
5.提出了从(n,d)置换码分别构造(n - 1,d - 3)和(n - 1,d - 2)置换码的方法,由此给出当n和d取某些情况时置换码的新下界。
6.提出两个由有限域上的分式多项式构造置换码的方法,并由此得到置换码的一些新下界。
7.证明了阶为n,最小度为d的置换群和(n,d)置换码的关系,由此得到置换码的一些新下界。
8.给出了由二元码构造置换码的三个新构造,前两个构造建立了P(n,d),DP(n,d)和CP(n,d)之间的一些令人感兴趣的不等式,后一个构造比直接构造更加有效地利用距离保持映射从二元码构造置换码。
9.广义码是各种具体码的抽象形式,包括置换码和二元码等。给出广义码的Gilbert-Varshamov界的一个简单新证明,接着证明了一个简单随机构造算法只需要较低的复杂度就能以较大的概率得到较大的码,而以前的Altruisitic算法由于复杂度太高实际上难以实现。当简单随机构造算法应用于构造置换码时,与Keevash和Ku提出的半随机构造算法比较,不仅没有苛刻的实现条件,而且需要更少的时间。
10.二元码和置换码有着密切关系。我们给出了二元码距离分布的几个新的线性不等式,给出改进Johnson界的一个更加简单的新证明。
A permutation code(array) of length n and minimum distance d, denoted by (n,d)permutation code, is a set of permutations C from some fixed set of n elements such thatthe Hamming distance between distinct members x, y∈C is at least d. Let P(n,d) denotethe maximum size of an (n,d) permutation code. A (n,d) permutation code C such that|C| = P(n,d) is called optimal. The study of the numbers P(n,d) is considered to be theessential problem of permutation code.
Permutation codes are somewhat studied in the 1970s. Vinck (Coded modulation forpowerline communications, Proc. Int. J. Elec. Commun., vol. 54, no. 1, 2000) renewedinterest in permutation codes by proposing it as an error correcting code for powerline com-munications. In this paper, we focus on the most essential problems on theory of permutationcodes– the bounds and constructions. Our main results are listed as followed:
1. We prove a relation between P(n,d) and PΩ(n,d).
2. We give some elementary properties of P(n,d,w), and then use them to show newupper bounds on P(n, 2k) and P(n, 2k + 1). For constantα,βsatisfying certainconditions, whenever d =βnα, the new upper bounds are asymptotically better thanthe previous ones.
3. Based on the graph theorem framework presented by Jiang and Vardy, we give threeimprovements over the Gilbert-Varshamov lower bounds on P(n,d).
4. By considering the covered balls intersection, we give two improvements over theGilbert-Varshamov lower bounds on P(n,d).
5. By presenting constructions of (n-1,d-3) and (n-1,d-2) permutation codes from(n,d) permutation codes, some new lower bounds for permutation codes are given forspecial cases for n and d.
6. We present two constructions of permutation codes from factional polynomials overfinite field, which produce some new lower bounds for permutation codes.
7. We show a relation between permutation group with degree n and minimal degree dand (n,d) permutation codes, which leads to some new lower bounds for permutationcodes.
8. We present three new constructions of permutation codes from binary codes, in whichthe first two constructions lead to some interested inequalities on P(n,d),DP(n,d)and CP(n,d), and the third construction gives larger permutation codes from knownbinary codes using preserve-distance mapping compared to direct construction.
9. The generalized code is the generalized form of concrete code, including permutationcodes, binary codes, et. al.. We give a new simple proof of Gilbert-Varshamov boundfor generalized codes, and present a simple random construction algorithm with lowercomplexity which is proved to obtain large code with significant probability, while theprevious Altruisitic algorithm is too complexity to be realized. Compared with semi-random construction presented by Keevash and Ku, the simple random constructionalgorithm does not require the strict conditions for realization and needs less timewhen it is applied to the constructions of permutation codes.
10. The binary code has closed relations with permutation code. We give several newinequalities for distance distributions of binary codes, and presented an new proof ofthe improved Johnson bound which is simpler than the original one.
引文
[1] I.F.Blake. Permutation codes for discrete channels. IEEE Trans. Inf. Theory, IT-20(1):138–140, 1974.
[2] L.F.Blake, G.Cohen, and M.Deza. Coding with permutations. Inform. Contr., 43:1–19, 1979.
[3] M. Deza and S. A. Vanstone. Bounds on permutation arrays. J. Statist. Planning andInference, 2:197–209, 1978.
[4] P. Frankl and M. Deza. On the maximum number of permutations with given maximalor minimal distance. J. Combin. Theory, Ser. A, 22:352–360, 1977.
[5] A. J. H. Vinck, J. Ha¨ing, and T. Wadayama. Coded m-fsk for power-line commu-nications. In Proc. IEEE Int.. Symp. Information Theory, page 137, Sorrento, Italy,2000.
[6] A. J. H. Vinck and J. Ha¨ring. Coding and modulation for power-line communications.In Proc. Int. Symp. Power Line Communication, Limerick, Ireland, Apr. 5-7 2000.
[7] 樊昌信,詹道庸,徐炳祥,吴成柯. 通信原理. 国防工业出版社, 1995.
[8] 王新梅,肖国镇. 纠错码–原理与方法. 西安电子科技大学出版社, 西安, 1991.
[9] C.E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., 27:379–423,623–656, July,October 1948.
[10] J.H. van Lint. Introduciton to Coding Theory. Springer Verlag, 1991.
[11] Beniamin Mounits and Tuvi Etzion. Improved upper bounds on sizes of codes. IEEETrans. Inform. Theory, 48(4):880–886, Apr. 2002.
[12] S. Litsyn. Handbook of Coding Theory, volume 1, chapter An updated table of thebest binary codes known, pages 463–498. Amsterdam, The Netherlands: Elsevier,1998.
[13] Tao Jiang and Alexander Vardy. Asymptotic improvement of gilbert-varshamovbound on the size of binary codes. IEEE Trans. Inform. Theory, 50(8):1655–1664,August 2004.
[14] Van Vu and Lei Wu. Improving the gilbert-varshamov bound for q-ary codes. IEEETrans. Inform. Theory, 51(9):3200–3208, September 2005.
[15] A. Barg, S. Guritman, and J. Simonis. Strengthening the gilbert-varshamov bound.Linear Algebra Appl., 307:119–129, 2000.
[16] F. Fabris. Sharphening the gilbert-varshamov bound in the finite case. J. Discr. Math.Sci. Cryptogr., 4:65–75, 2001.
[17] Venkatesan Guruswami. Constructions of codes from number fields. IEEE TRANS.INFORM. THEORY, 49(3):594–603, March 2003.
[18] A. Ashikhmin, A. Barg, and S. Litsyn. Estimates of the distance distribution of codesand designs. IEEE Trans. Inform. Theory, 47(3):1050–1061, March 2001.
[19] Alexander Barg and Andrew McGregor. Distance distribution of binary codes and theerror probability of decoding. IEEE Trans. Inform. Theory, 51(12):4237–4246, Dec.2005.
[20] Heeralal Janwa. Some new upper bounds on the covering radius of binary linearcodes. IEEE Trans. Inform. Theory, pages 110–122, 1989.
[21] Richard A. Brualdi, Vera S. Pless, and Richard M Wilson. Short codes with a givencovering radius. IEEE Trans. Inform. Theory, pages 99–109, 1989.
[22] Andrew Klapper. Improved multicovering bounds from linear inequalities and super-codes. IEEE Trans. Inform. Theory, 50(3):532–536, March 2004.
[23] Changyan Di, Thomas J. Richardson, and Rudiger L. Urbanke. Weight distributionof low-density parity-check codes. IEEE Trans. Inform. Theory, 52(11):4839–4855,Nov. 2006.
[24] Heide Gluesing-Luerssen. On the weight distribution of convolutional codes. LinearAlgebra and Its Applications, 408(1-3):298–326, Oct. 2005.
[25] Erik Agrell, Alexander Vardy, and Kenneth Zeger. Upper bounds for constant-weightcodes. IEEE Trans. Inform. Theory, 46(7):2373–2395, Nov. 2000.
[26] Michael Braun. Construction of linear codes with large minimum distance. IEEETRANSACTIONS ON INFORMATION THEORY, 50(8):1687–1691, 2004.
[27] A.C. Lobstein and V.A. Zinoviev. On new perfect binary nonlinear codes. ApplicableAlgebra in Engineering, Communications and Computing, 8(5):415–420, 1997.
[28] Iiro S. Honkala and Heikki O. Hamalainen. New construction for covering codes.IEEE Trans. Inform. Theory, 34(5):1343–1344, Sep. 1988.
[29] Alexander A. Davydov. Constructions and families of covering codes and saturatedsets of points in projective geometry. IEEE Trans. Inform. Theory, 41(6):2071–2080,Nov. 1995.
[30] Mattias Svanstro¨m, Patric R. J. O¨sterga?rd, and Galina T. Bogdanova. Bounds andconstructions for ternary constant-composition codes. IEEE Trans. Inform. Theory,48(1):101–111, 2002.
[31] Yuan Luo, Fang-Wei Fu, A.J. Han Vinck, and Wende Chen. On constant-compositioncodes over Zq. IEEE Trans. Inform. Theory, 49(11):3010–3016, Nov. 2003.
[32] Fang-Wei Fu, Torleiv Kl?ve, Yuan Luo, and K. Victor Wei. On equidistant constantweight codes. Discrete Applied Mathematics, 128(1):157–164, May 2003.
[33] Jian Gu and Tom Fuja. A generalized gilbert-varshamov bound derived via analysis ofa code-search algorithm. IEEE Trans. Inform. Theory, 39(3):1089–1093, May 1993.
[34] 王新梅. 纠错码发展概况及其最近进展. 通信学报, pages 69–77, 1982年7月第三期.
[35] W. W. Perterson. Error-Correcting Codes. MIT Press, Cambridge, MA, 1961.
[36] E.H. Berlekamp. Algebraic Coding Theory. McGraw-Hill, New York, 1968.
[37] J.M. Wozencraft and B. Reiffen. Sequential Decoding. MIT Press, Cambridge, 1961.
[38] J.L. Massey. Threshold Decoding. MIT Press, MIT Press, 1963.
[39] G. D. Forney. Concatenated Codes. MIT Press, Cambridge, 1966.
[40] G. Ungerboeck. Channel coding with multilevel/phase signaling. IEEE Trans. Inform.Theory, 25:55–67, Jan. 1982.
[41] C. Berrou, A. Glavieux, and P. Thitimajshima. Near shannon limit error-correctingcoding and decoding: Turbo-codes. In Proc. ICC’93, pages 1064–1070, May 1993.
[42] R G. Gallager. Low density parity check codes. IRE Transactions on InlormaLionTheory, 8(3):208–220, 1962.
[43] R G. Gallager. Low Density Parity Check Codes. MIT Press, Cambridge, Mass, 1963.
[44] G.J. Simmons. Authentication theory /coding theory. In Proc of the CRYPTO’84,volume 196 of LNCS, pages 411–432, Berlin, 1985. Springer-Verlag.
[45] R.S. Safavi-Naini and J.R. Seberry. Error correcting codes for authentication andsubliminal channels. IEEE Trans on Information Theory, 37(1):13–17, 1991.
[46] G.A. Kabatianskii, Ben Smeets, and T. Johansson. On the cardinality of systematicauthentication codes via error correcting codes. IEEE Trans on Information Theory,42(2):566–578, 1996.
[47] D.R. Stinson. The combinatorics of authentication and secrecy codes. Journal ofCryptology, (2):23–49, 1990.
[48] R.J. McEliece. A Public-Key Cryptosystem Based on Algebraic Coding Theory, chap-ter DSN Progress. Report 42-44, pages 114–116. Jet Propulsion Laboratory, Pasadena,CA, January and February 1978.
[49] H. Niederreiter. Knapsackes type problems of control and information cryptosystemsand theory. algebraic coding theory, 15(2):159–166, 1986.
[50] J. Stern. A new identification scheme based on syndrome decoding. In D.R.Stinson,editor, Advances in Cryptology-Crypto’93, volume 773 of Lecture Notes in ComputerScience, pages 13–21. Springer-Verla, 1994.
[51] J.P.Jordan. A variant of a public-key cryptosystem based on goppa codes. SigactNews, 15(1):61–66, 1983.
[52] T.R.N.Rao. Cryptosystems using algebraic codes. In Int. Conf. on Computer Systems& Signal Processing, Bangalore, India, December 1984.
[53] T.R.N.Rao and K.H.Nam. Private-key algebraic-coded cryptosystems. InA.M.Odlyzko, editor, Advances in Cryptology-Proceedings of Crypto’86, volume 263of Lecture Notes in Computer Science, pages 35–48. Springer-Verlag, 1987.
[54] T.R.N.Rao and K.H.Nam. Private-key algebraic-erode encryption. IEEETrans.Inform.Theory, 35(4):829–833, 1989.
[55] Y.X. Li and X.M. Wang. A joint authentication and encryption scheme based onalgebraic coding theory. In H.F. Mattson, T.Mora, and T.R.N.Rao, editors, Appliedalgebra, Algebraic algorithms and Error Correcting Codes 9, volume 539 of LNCS,pages 241–245. Springer-Verlag, 1991.
[56] W. Meier and O. Staffelbach. Fast correlation attacks on certain stream ciphers. InAdvances in Cryptology -EUROCRYPT’88, volume 330 of LNCS, pages 301–314,1988.
[57] W. Meier and O. Staffelbach. Fast correlation attacks on certain stream ciphers. Jour-nal of Cryptology, 1:159–176, 1989.
[58] 杨礼珍. 非线性组合流密码的快速相关攻击研究. 硕士论文, 西安电子科技大学,1月2001.
[59] P. Delsarte. An algebraic approach to the associate schemes of coding theory. PhilipsRes. Rep., Suppl., 10, 1973.
[60] R. A. Bailey. Association Schemes/Designed Experiments, Algebra and Combina-torics. Number 84 in Cambridge Studies in Advanced Mathematics. 2004.
[61] 张煦. 电源线通信系统的可能发展. 光纤与电缆及其应用技术, (6), 2003.
[62] Niovi Pavlidou, A.J.Han Vinck, Javad Yazdanl, and Bahram Honary. Power line com-munications: state of the art and future trends. IEEE Communications Magazine,pages 34–40, April 2003.
[63] Kenneth W.Shun. Permutation coding and mfsk modulation for frequency selectivechannel. In PIMRC 2002. IEEE, 2002.
[64] H. C. Ferreira and A. J. H. Vinck. Interference cancellation with permutation trelliscodes. In Proc. IEEE Vehicular Technology Conference, volume 5, pages 2401–2407,2000.
[65] Hendrik C.Ferreira, A.J.Han Vinck, Theo G.Swart, and Ian de Beer. Permutationtrellis codes. IEEE Trans. Commun., 53(11):1782–1789, Nov. 2005.
[66] D.R.de la Torre, C.J.Colbourn, and A.C.H.Ling. An application of permutation arraysto block ciphers. Cong. Number., 145:5–7, 2000.
[67] Wensong Chu, Charles J. Colbourn, and Peter Dukes. Constructions for permutationcodes in powerline communications. Designs, Codes and Cryptography, 32:51–64,2004.
[68] H. Tarnanen. Upper bounds on permutation codes via linear programming. Europ. J.Combin., 20:101–114, 1999.
[69] T.Kl?ve. A combinatorial problem motivated by a data transmission application. InProc. Norsk Informatikkonf. (NIK), pages 55–66, 2000.
[70] Charles J.Colbourn, Torleiv Kl?ve, and Alan C. H. Ling. Permutation arrays for pow-erline communication and mutually orthogonal latin squares. IEEE Trans. Inform.Theory, 50(6):1289–1291, June 2004.
[71] T. Wadayama and A. J. H. Vinck. A multilevel construction of permutation codes.In IEICE Trans. Fundamentals Electron., Commun. Comp. Sci., volume 84, pages2518–2522, 2001.
[72] A. J. Han Vinck, Juergen Haering, and Tadashi Wadayam. Coded m?fsk for powerline communications. In ISIT 2000, pages 25–30, Sorrento, Italy, June 2000. IEEE.
[73] Cunsheng Ding, Fang-Wei Fu, Torleiv Kl?ve, and K. V.K.-W. Wei. Construction ofpermutation arrays. IEEE Trans. Inform. Theory, 48(4):977–980, 2002.
[74] Fang-Wei Fu and Torleiv Kl?ve. Two constructions of permutation arrays. IEEETrans. Inform. Theory, 50(5):881–883, May 2004.
[75] Jen-Chun Chang, Rong-Jaye Chen, Toleiv Kl?ve, and Shi-Chun Tsai. Distance-preserving mapping from binary vectors to permutations. IEEE Transaction on In-formation Theory, 49(4):1054–1059, 2003.
[76] Jen-Chun Chang. Distance-increasing mappings from binary vectors to permutations.IEEE Trans. Inform. Theory, 51(1):359–363, Jan. 2005.
[77] Theo G. Swart and Hendrik C. Ferreira. A generalized upper bound and a multilevelconstruction for distance-preserving mappings. IEEE Trans. Inf. Theory, 52(8):3685–3695, Aug. 2006.
[78] Yen-Ying Huang, Shi-Chun Tsai, and Hsin-Lung Wu. On the construction of permu-tation arrays via mappings from binary vectors to permutations. Des Codes Crypt,40(2):139–155, Aug. 2006.
[79] Kwankyu Lee. New distance-preserving maps of odd length. IEEE Trans. Inform.Theory, 50(10):2539–2543, Oct. 2004.
[80] Kwankyu Lee. Cyclic constructions of distance-preserving maps. IEEE Trans. Inform.Theory, 51(12):4392–4396, DECEMBER 2005.
[81] Kwankyu Lee. Distance-increasing maps of all lengths by simple mapping algorithms.IEEE Trans. Inform. Theory, 52(7):3344–3348, July 2006.
[82] Peter Keevash and Cheng Yeaw Ku. A random construction for permutation codesand the covering radius. Des Codes Crypt, (41):79–86, 2006.
[83] R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, second edition,1997.
[84] H. C. Ferreira, D. A. Wright, and A. L. Nel. Hamming distance preserving mappingsand trellis codes with constrained binary symbols.
[85] C. A. French. Distance preserving run-length limited codes. IEEE Trans. Magn.,25(5):4093–4095,, Sep. 1989.
[86] J.-C. Chang, R.-J. Chen, S.-C. Tsai, and Torleiv Kl?ve. Distance preseving mappingfrom binary vectors to permutations. In ISIT 2003, page 14, Yokohama Japan, June29 - July 4 2003. IEEE.
[87] R.Battiti and M.Protasi. Reactive local search for the maximum clique problem. Al-gorithmica, 29:610–637, 2001.
[88] B.Bolloa′s. Random Graphs. London, U.K.: Academic, 1985.
[89] R.Lidl and H.Niederreiter. Finite Fields, volume 20 of Encyclopedia of Mathematicsand its Applications. Cambridge University Press, Cambridge, UK, 1997.
[90] John D.Dixon and Brian Mortimer. Permutation Groups. Springer-Verlag, 1996.
[91] M. Liebeck and J. Saxl. Minimal degrees of primitive permutation groups, with anapplication to monodromy groups of covers of riemann surfaces. In Proc. LondonMath. Soc., volume 3 of 63, pages 266–314.
[92] B.Huppert and N.Blackburn. Finite Groups III. Springer-Verlag, 1982.
[93] V.D.Kolesnik and V.Y.Krachkovsky. Generating functions and lower bounds on ratesfor limited error-correcting codes. IEEE Trans. Inform. Theory, 37(3):778–788, May1991.
[94] Ludo M. G. M. Tolhuizen. The generalized gilbert-varshamov bound is implied bytura′n’s theorem. IEEE Trans. Inform. Theory, 43(5):1605–1606, SEPTEMBER1997.
[95] M. R. Best, A. E. Brouwer, F. J. MacWilliams, A. M. Odlyzko, and N. J. A. Sloane.Bounds for binary codes of length less than 25. IEEE Trans. Inform. Theory, IT-24:81–93, Jan. 1978.
[96] M.R.Best. Binary codes with a minimum distance of four. IEEE Trans. Inform.Theory, IT-26:738–742, 1980.
[97] C. L. N. van Pul. On bounds on codes. Master’s thesis, Dept. Math. and Comput.Science, Eindhoven Univ. Technol., Eindhoven, The Nether-lands, Aug. 1982.
[98] I. Honkala. Bounds for binary constant weight and covering codes. Licentiate the-sis,Dept. Math., Univ. of Turku, Turku, Finland, Mar. 1987.
[99] F. J. MacWilliams and N. J. A. Sloane. Sloane, The Theory of Error-Correcting Codes.Amsterdam, The Netherlands: North-Holland, 1977.
[100] R. L. Graham and N. J. A. Sloane. Lower bounds for constant weight codes. IEEETrans. Inform. Theory, IT-26:37–43, Jan. 1980.
[101] A. E. Brouwer, J. B. Shearer, N. J. A. Sloane, and W. D. Smith. A new table of constantweight codes. IEEE Trans. Inform. Theory, 36:1334–1380, Nov. 1990.
[102] S. M. Johnson. Upper bounds for constant weight error correcting codes. Discr. Math.,3:109–124, 1972.– 104 –
[103] V. I. Levenshtein. Upper-bound estimates for fixed-weight codes. Probl. Inform.Transm., 7(4):281–287, Jan. 1974. (Original appearance in Russian in Probl. Pered.Inform., vol. 7, pp. 3–12, Oct.–Dec. 1971).
[104] Alexander Schrijver. New code upper bounds from the terwilliger algebra andsemidefinite programming. IEEE Trans. Inform. Theory, 51(8):2859 – 2866, Aug.2005.
[105] S.M.Johnson. A new upper bound for error-correcting codes. IRE Trans. Inform.Theory, IT-8:203–207, Apr. 1962.
[106] M. Plotkin. Binary codes with specified minimum distance. IRE Trans. Inform. The-ory, IT-6:445–450, Sept. 1960.
[107] V. I. Levenshtein. The application of hadamard matrices to a problem in coding.Probl. Kibern., 5:123–136, 1961. English translation in Probl. Cybernetics, vol. 5, pp.166–184, 1964.
[2] L.F.Blake, G.Cohen, and M.Deza. Coding with permutations. Inform. Contr., 43:1–19, 1979.
[3] M. Deza and S. A. Vanstone. Bounds on permutation arrays. J. Statist. Planning andInference, 2:197–209, 1978.
[4] P. Frankl and M. Deza. On the maximum number of permutations with given maximalor minimal distance. J. Combin. Theory, Ser. A, 22:352–360, 1977.
[5] A. J. H. Vinck, J. Ha¨ing, and T. Wadayama. Coded m-fsk for power-line commu-nications. In Proc. IEEE Int.. Symp. Information Theory, page 137, Sorrento, Italy,2000.
[6] A. J. H. Vinck and J. Ha¨ring. Coding and modulation for power-line communications.In Proc. Int. Symp. Power Line Communication, Limerick, Ireland, Apr. 5-7 2000.
[7] 樊昌信,詹道庸,徐炳祥,吴成柯. 通信原理. 国防工业出版社, 1995.
[8] 王新梅,肖国镇. 纠错码–原理与方法. 西安电子科技大学出版社, 西安, 1991.
[9] C.E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., 27:379–423,623–656, July,October 1948.
[10] J.H. van Lint. Introduciton to Coding Theory. Springer Verlag, 1991.
[11] Beniamin Mounits and Tuvi Etzion. Improved upper bounds on sizes of codes. IEEETrans. Inform. Theory, 48(4):880–886, Apr. 2002.
[12] S. Litsyn. Handbook of Coding Theory, volume 1, chapter An updated table of thebest binary codes known, pages 463–498. Amsterdam, The Netherlands: Elsevier,1998.
[13] Tao Jiang and Alexander Vardy. Asymptotic improvement of gilbert-varshamovbound on the size of binary codes. IEEE Trans. Inform. Theory, 50(8):1655–1664,August 2004.
[14] Van Vu and Lei Wu. Improving the gilbert-varshamov bound for q-ary codes. IEEETrans. Inform. Theory, 51(9):3200–3208, September 2005.
[15] A. Barg, S. Guritman, and J. Simonis. Strengthening the gilbert-varshamov bound.Linear Algebra Appl., 307:119–129, 2000.
[16] F. Fabris. Sharphening the gilbert-varshamov bound in the finite case. J. Discr. Math.Sci. Cryptogr., 4:65–75, 2001.
[17] Venkatesan Guruswami. Constructions of codes from number fields. IEEE TRANS.INFORM. THEORY, 49(3):594–603, March 2003.
[18] A. Ashikhmin, A. Barg, and S. Litsyn. Estimates of the distance distribution of codesand designs. IEEE Trans. Inform. Theory, 47(3):1050–1061, March 2001.
[19] Alexander Barg and Andrew McGregor. Distance distribution of binary codes and theerror probability of decoding. IEEE Trans. Inform. Theory, 51(12):4237–4246, Dec.2005.
[20] Heeralal Janwa. Some new upper bounds on the covering radius of binary linearcodes. IEEE Trans. Inform. Theory, pages 110–122, 1989.
[21] Richard A. Brualdi, Vera S. Pless, and Richard M Wilson. Short codes with a givencovering radius. IEEE Trans. Inform. Theory, pages 99–109, 1989.
[22] Andrew Klapper. Improved multicovering bounds from linear inequalities and super-codes. IEEE Trans. Inform. Theory, 50(3):532–536, March 2004.
[23] Changyan Di, Thomas J. Richardson, and Rudiger L. Urbanke. Weight distributionof low-density parity-check codes. IEEE Trans. Inform. Theory, 52(11):4839–4855,Nov. 2006.
[24] Heide Gluesing-Luerssen. On the weight distribution of convolutional codes. LinearAlgebra and Its Applications, 408(1-3):298–326, Oct. 2005.
[25] Erik Agrell, Alexander Vardy, and Kenneth Zeger. Upper bounds for constant-weightcodes. IEEE Trans. Inform. Theory, 46(7):2373–2395, Nov. 2000.
[26] Michael Braun. Construction of linear codes with large minimum distance. IEEETRANSACTIONS ON INFORMATION THEORY, 50(8):1687–1691, 2004.
[27] A.C. Lobstein and V.A. Zinoviev. On new perfect binary nonlinear codes. ApplicableAlgebra in Engineering, Communications and Computing, 8(5):415–420, 1997.
[28] Iiro S. Honkala and Heikki O. Hamalainen. New construction for covering codes.IEEE Trans. Inform. Theory, 34(5):1343–1344, Sep. 1988.
[29] Alexander A. Davydov. Constructions and families of covering codes and saturatedsets of points in projective geometry. IEEE Trans. Inform. Theory, 41(6):2071–2080,Nov. 1995.
[30] Mattias Svanstro¨m, Patric R. J. O¨sterga?rd, and Galina T. Bogdanova. Bounds andconstructions for ternary constant-composition codes. IEEE Trans. Inform. Theory,48(1):101–111, 2002.
[31] Yuan Luo, Fang-Wei Fu, A.J. Han Vinck, and Wende Chen. On constant-compositioncodes over Zq. IEEE Trans. Inform. Theory, 49(11):3010–3016, Nov. 2003.
[32] Fang-Wei Fu, Torleiv Kl?ve, Yuan Luo, and K. Victor Wei. On equidistant constantweight codes. Discrete Applied Mathematics, 128(1):157–164, May 2003.
[33] Jian Gu and Tom Fuja. A generalized gilbert-varshamov bound derived via analysis ofa code-search algorithm. IEEE Trans. Inform. Theory, 39(3):1089–1093, May 1993.
[34] 王新梅. 纠错码发展概况及其最近进展. 通信学报, pages 69–77, 1982年7月第三期.
[35] W. W. Perterson. Error-Correcting Codes. MIT Press, Cambridge, MA, 1961.
[36] E.H. Berlekamp. Algebraic Coding Theory. McGraw-Hill, New York, 1968.
[37] J.M. Wozencraft and B. Reiffen. Sequential Decoding. MIT Press, Cambridge, 1961.
[38] J.L. Massey. Threshold Decoding. MIT Press, MIT Press, 1963.
[39] G. D. Forney. Concatenated Codes. MIT Press, Cambridge, 1966.
[40] G. Ungerboeck. Channel coding with multilevel/phase signaling. IEEE Trans. Inform.Theory, 25:55–67, Jan. 1982.
[41] C. Berrou, A. Glavieux, and P. Thitimajshima. Near shannon limit error-correctingcoding and decoding: Turbo-codes. In Proc. ICC’93, pages 1064–1070, May 1993.
[42] R G. Gallager. Low density parity check codes. IRE Transactions on InlormaLionTheory, 8(3):208–220, 1962.
[43] R G. Gallager. Low Density Parity Check Codes. MIT Press, Cambridge, Mass, 1963.
[44] G.J. Simmons. Authentication theory /coding theory. In Proc of the CRYPTO’84,volume 196 of LNCS, pages 411–432, Berlin, 1985. Springer-Verlag.
[45] R.S. Safavi-Naini and J.R. Seberry. Error correcting codes for authentication andsubliminal channels. IEEE Trans on Information Theory, 37(1):13–17, 1991.
[46] G.A. Kabatianskii, Ben Smeets, and T. Johansson. On the cardinality of systematicauthentication codes via error correcting codes. IEEE Trans on Information Theory,42(2):566–578, 1996.
[47] D.R. Stinson. The combinatorics of authentication and secrecy codes. Journal ofCryptology, (2):23–49, 1990.
[48] R.J. McEliece. A Public-Key Cryptosystem Based on Algebraic Coding Theory, chap-ter DSN Progress. Report 42-44, pages 114–116. Jet Propulsion Laboratory, Pasadena,CA, January and February 1978.
[49] H. Niederreiter. Knapsackes type problems of control and information cryptosystemsand theory. algebraic coding theory, 15(2):159–166, 1986.
[50] J. Stern. A new identification scheme based on syndrome decoding. In D.R.Stinson,editor, Advances in Cryptology-Crypto’93, volume 773 of Lecture Notes in ComputerScience, pages 13–21. Springer-Verla, 1994.
[51] J.P.Jordan. A variant of a public-key cryptosystem based on goppa codes. SigactNews, 15(1):61–66, 1983.
[52] T.R.N.Rao. Cryptosystems using algebraic codes. In Int. Conf. on Computer Systems& Signal Processing, Bangalore, India, December 1984.
[53] T.R.N.Rao and K.H.Nam. Private-key algebraic-coded cryptosystems. InA.M.Odlyzko, editor, Advances in Cryptology-Proceedings of Crypto’86, volume 263of Lecture Notes in Computer Science, pages 35–48. Springer-Verlag, 1987.
[54] T.R.N.Rao and K.H.Nam. Private-key algebraic-erode encryption. IEEETrans.Inform.Theory, 35(4):829–833, 1989.
[55] Y.X. Li and X.M. Wang. A joint authentication and encryption scheme based onalgebraic coding theory. In H.F. Mattson, T.Mora, and T.R.N.Rao, editors, Appliedalgebra, Algebraic algorithms and Error Correcting Codes 9, volume 539 of LNCS,pages 241–245. Springer-Verlag, 1991.
[56] W. Meier and O. Staffelbach. Fast correlation attacks on certain stream ciphers. InAdvances in Cryptology -EUROCRYPT’88, volume 330 of LNCS, pages 301–314,1988.
[57] W. Meier and O. Staffelbach. Fast correlation attacks on certain stream ciphers. Jour-nal of Cryptology, 1:159–176, 1989.
[58] 杨礼珍. 非线性组合流密码的快速相关攻击研究. 硕士论文, 西安电子科技大学,1月2001.
[59] P. Delsarte. An algebraic approach to the associate schemes of coding theory. PhilipsRes. Rep., Suppl., 10, 1973.
[60] R. A. Bailey. Association Schemes/Designed Experiments, Algebra and Combina-torics. Number 84 in Cambridge Studies in Advanced Mathematics. 2004.
[61] 张煦. 电源线通信系统的可能发展. 光纤与电缆及其应用技术, (6), 2003.
[62] Niovi Pavlidou, A.J.Han Vinck, Javad Yazdanl, and Bahram Honary. Power line com-munications: state of the art and future trends. IEEE Communications Magazine,pages 34–40, April 2003.
[63] Kenneth W.Shun. Permutation coding and mfsk modulation for frequency selectivechannel. In PIMRC 2002. IEEE, 2002.
[64] H. C. Ferreira and A. J. H. Vinck. Interference cancellation with permutation trelliscodes. In Proc. IEEE Vehicular Technology Conference, volume 5, pages 2401–2407,2000.
[65] Hendrik C.Ferreira, A.J.Han Vinck, Theo G.Swart, and Ian de Beer. Permutationtrellis codes. IEEE Trans. Commun., 53(11):1782–1789, Nov. 2005.
[66] D.R.de la Torre, C.J.Colbourn, and A.C.H.Ling. An application of permutation arraysto block ciphers. Cong. Number., 145:5–7, 2000.
[67] Wensong Chu, Charles J. Colbourn, and Peter Dukes. Constructions for permutationcodes in powerline communications. Designs, Codes and Cryptography, 32:51–64,2004.
[68] H. Tarnanen. Upper bounds on permutation codes via linear programming. Europ. J.Combin., 20:101–114, 1999.
[69] T.Kl?ve. A combinatorial problem motivated by a data transmission application. InProc. Norsk Informatikkonf. (NIK), pages 55–66, 2000.
[70] Charles J.Colbourn, Torleiv Kl?ve, and Alan C. H. Ling. Permutation arrays for pow-erline communication and mutually orthogonal latin squares. IEEE Trans. Inform.Theory, 50(6):1289–1291, June 2004.
[71] T. Wadayama and A. J. H. Vinck. A multilevel construction of permutation codes.In IEICE Trans. Fundamentals Electron., Commun. Comp. Sci., volume 84, pages2518–2522, 2001.
[72] A. J. Han Vinck, Juergen Haering, and Tadashi Wadayam. Coded m?fsk for powerline communications. In ISIT 2000, pages 25–30, Sorrento, Italy, June 2000. IEEE.
[73] Cunsheng Ding, Fang-Wei Fu, Torleiv Kl?ve, and K. V.K.-W. Wei. Construction ofpermutation arrays. IEEE Trans. Inform. Theory, 48(4):977–980, 2002.
[74] Fang-Wei Fu and Torleiv Kl?ve. Two constructions of permutation arrays. IEEETrans. Inform. Theory, 50(5):881–883, May 2004.
[75] Jen-Chun Chang, Rong-Jaye Chen, Toleiv Kl?ve, and Shi-Chun Tsai. Distance-preserving mapping from binary vectors to permutations. IEEE Transaction on In-formation Theory, 49(4):1054–1059, 2003.
[76] Jen-Chun Chang. Distance-increasing mappings from binary vectors to permutations.IEEE Trans. Inform. Theory, 51(1):359–363, Jan. 2005.
[77] Theo G. Swart and Hendrik C. Ferreira. A generalized upper bound and a multilevelconstruction for distance-preserving mappings. IEEE Trans. Inf. Theory, 52(8):3685–3695, Aug. 2006.
[78] Yen-Ying Huang, Shi-Chun Tsai, and Hsin-Lung Wu. On the construction of permu-tation arrays via mappings from binary vectors to permutations. Des Codes Crypt,40(2):139–155, Aug. 2006.
[79] Kwankyu Lee. New distance-preserving maps of odd length. IEEE Trans. Inform.Theory, 50(10):2539–2543, Oct. 2004.
[80] Kwankyu Lee. Cyclic constructions of distance-preserving maps. IEEE Trans. Inform.Theory, 51(12):4392–4396, DECEMBER 2005.
[81] Kwankyu Lee. Distance-increasing maps of all lengths by simple mapping algorithms.IEEE Trans. Inform. Theory, 52(7):3344–3348, July 2006.
[82] Peter Keevash and Cheng Yeaw Ku. A random construction for permutation codesand the covering radius. Des Codes Crypt, (41):79–86, 2006.
[83] R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, second edition,1997.
[84] H. C. Ferreira, D. A. Wright, and A. L. Nel. Hamming distance preserving mappingsand trellis codes with constrained binary symbols.
[85] C. A. French. Distance preserving run-length limited codes. IEEE Trans. Magn.,25(5):4093–4095,, Sep. 1989.
[86] J.-C. Chang, R.-J. Chen, S.-C. Tsai, and Torleiv Kl?ve. Distance preseving mappingfrom binary vectors to permutations. In ISIT 2003, page 14, Yokohama Japan, June29 - July 4 2003. IEEE.
[87] R.Battiti and M.Protasi. Reactive local search for the maximum clique problem. Al-gorithmica, 29:610–637, 2001.
[88] B.Bolloa′s. Random Graphs. London, U.K.: Academic, 1985.
[89] R.Lidl and H.Niederreiter. Finite Fields, volume 20 of Encyclopedia of Mathematicsand its Applications. Cambridge University Press, Cambridge, UK, 1997.
[90] John D.Dixon and Brian Mortimer. Permutation Groups. Springer-Verlag, 1996.
[91] M. Liebeck and J. Saxl. Minimal degrees of primitive permutation groups, with anapplication to monodromy groups of covers of riemann surfaces. In Proc. LondonMath. Soc., volume 3 of 63, pages 266–314.
[92] B.Huppert and N.Blackburn. Finite Groups III. Springer-Verlag, 1982.
[93] V.D.Kolesnik and V.Y.Krachkovsky. Generating functions and lower bounds on ratesfor limited error-correcting codes. IEEE Trans. Inform. Theory, 37(3):778–788, May1991.
[94] Ludo M. G. M. Tolhuizen. The generalized gilbert-varshamov bound is implied bytura′n’s theorem. IEEE Trans. Inform. Theory, 43(5):1605–1606, SEPTEMBER1997.
[95] M. R. Best, A. E. Brouwer, F. J. MacWilliams, A. M. Odlyzko, and N. J. A. Sloane.Bounds for binary codes of length less than 25. IEEE Trans. Inform. Theory, IT-24:81–93, Jan. 1978.
[96] M.R.Best. Binary codes with a minimum distance of four. IEEE Trans. Inform.Theory, IT-26:738–742, 1980.
[97] C. L. N. van Pul. On bounds on codes. Master’s thesis, Dept. Math. and Comput.Science, Eindhoven Univ. Technol., Eindhoven, The Nether-lands, Aug. 1982.
[98] I. Honkala. Bounds for binary constant weight and covering codes. Licentiate the-sis,Dept. Math., Univ. of Turku, Turku, Finland, Mar. 1987.
[99] F. J. MacWilliams and N. J. A. Sloane. Sloane, The Theory of Error-Correcting Codes.Amsterdam, The Netherlands: North-Holland, 1977.
[100] R. L. Graham and N. J. A. Sloane. Lower bounds for constant weight codes. IEEETrans. Inform. Theory, IT-26:37–43, Jan. 1980.
[101] A. E. Brouwer, J. B. Shearer, N. J. A. Sloane, and W. D. Smith. A new table of constantweight codes. IEEE Trans. Inform. Theory, 36:1334–1380, Nov. 1990.
[102] S. M. Johnson. Upper bounds for constant weight error correcting codes. Discr. Math.,3:109–124, 1972.– 104 –
[103] V. I. Levenshtein. Upper-bound estimates for fixed-weight codes. Probl. Inform.Transm., 7(4):281–287, Jan. 1974. (Original appearance in Russian in Probl. Pered.Inform., vol. 7, pp. 3–12, Oct.–Dec. 1971).
[104] Alexander Schrijver. New code upper bounds from the terwilliger algebra andsemidefinite programming. IEEE Trans. Inform. Theory, 51(8):2859 – 2866, Aug.2005.
[105] S.M.Johnson. A new upper bound for error-correcting codes. IRE Trans. Inform.Theory, IT-8:203–207, Apr. 1962.
[106] M. Plotkin. Binary codes with specified minimum distance. IRE Trans. Inform. The-ory, IT-6:445–450, Sept. 1960.
[107] V. I. Levenshtein. The application of hadamard matrices to a problem in coding.Probl. Kibern., 5:123–136, 1961. English translation in Probl. Cybernetics, vol. 5, pp.166–184, 1964.