球填装和球面上填装问题的研究

论文摘要

欧式空间上的球填装问题和球面上的填装问题已经研究了好几个世纪了，但至今仍未完全解决。本论文研究这两类问题，主要结果如下：利用虚二次数域上的素理想的性质，并结合好的参数的纠错码，我们给出一类稠密球填装的新的构造。利用此构造，我们具体计算了维数n≤62中一些稠密的球填装。其中有不少达到目前已知最好的结果，特别的在59和61维分别超出目前已知的结果。在我们构造的基础上，对于高维渐近情况我们还计算得到一些有意思的结果。球面上的填装问题等价于一类球码的研究。N．J．A．Sloane利用二元码给出了球码的一种构造。我们同样给出一种将三元码转化为球码的新的构造。在此两个构造的基础上，通过寻找一类好的参数的代数几何码，我们给出在多项式时间实现的球码的渐近下界。我们继续利用编码中Gilbert-Varshamov界证明的思想，又给出在指数时间实现的球码的渐近下界，并且证明了E．A．Shamsiev和A．D．Wyner分别给出的存在性的下界是可以指数时间实现的。我们还讨论了球填装问题和球面填装问题对一类超球体的情形。首先我们给出将纠错码和已知的超球体上的填装链接在一起的构造方法。利用好的参数的码我们得到一类稠密的超球体填装。并改进了J．A．Rush和N．J．A．Sloane给出的渐近下界。对于经典球填装的情形，我们还给出两类Gilbert-Varshamov型的界，并通过数值计算，在维数512-1048584的稠密球填装的情况中，我们改进了目前已知的最好结果。接着我们又研究了一个超球体的最大接触数。我们给出了Gilbert-Varshamov型的下界，然后又利用达到Gilbert-Varshamov界的二元码和代数几何码分别给出了指数时间和多项式时间实现的下界。这三类界都几乎改进了D．G．Larman和宗传明给出的结果。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 选题背景及国内外研究动向
• 1.2 本文的内容安排
• 第2章 纠错码
• 2.1 纠错码的基本概念
• 2.2 Gilbert-Varshamov界
• 2.3 代数几何码
• 2.3.1 Goppa构造
• 2.3.2 渐近结果
• 第3章 球填装问题
• 3.1 预备知识
• 3.1.1 基本定义
• 3.1.2 格填装
• 3.1.3 几类重要的格填装及性质
• 3.2 球填装与纠错码
• 3.2.1 几类经典构造
• 3.2.2 复格上的构造
• 3.2.3 虚二次域上的构造
• 第4章 球面上填装问题
• 4.1 球码的概念
• 4.2 球码与纠错码
• 4.2.1 二元码上球码的构造
• 4.2.2 三元码上球码的构造
• 4.3 高维球码的渐近结果
• 4.3.1 多项式时间构造
• 4.3.2 指数时间构造
• 第5章 一类超球体的研究
• 5.1 基本定义
• 5.2 超球体的填装问题
• 5.2.1 概述
• 5.2.2 链接构造
• 5.2.3 渐近结果
• 5.2.4 σ=2的高维情况
• 5.3 超球体的最大接触数
• 5.3.1 概述
• 5.3.2 G-V型下界
• 5.3.3 二元码给出的下界
• 第6章 结论
• 6.1 论文的主要工作
• 6.2 进一步开展的工作
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果