【作者】 杨礼珍；

【导师】 陈克非；

【作者基本信息】 上海交通大学 ， 计算机应用技术， 2007， 博士

【摘要】 长为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界的一个更加简单的新证明。更多还原

【Abstract】 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.更多还原