论文部分内容阅读
长为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界的一个更加简单的新证明。