论文标题
编码理论中的新方法：错误校正代码和香农容量
New Methods in Coding Theory: Error-Correcting Codes and the Shannon Capacity
论文作者
论文摘要
在本文中，我们在编码理论中介绍了几个结果，涉及误差校正代码和香农的能力。 1。我们对编码理论中半限定程序中矩阵的一般对称性减少。 2。我们将对称性降低应用于有效计算具有锤距离距离的非二元误差校正代码（与Bart Litjens和Lex Schrijver的联合工作）的非二元误差校正代码，具有LEE距离和二进制恒定重量代码。 3。我们探索了基于组合分式分裂性参数的非二进制代码的其他方法，以找到具有锤距离距离的非二进制代码的新上限。 4。我们使用半决赛编程求解器的输出来研究代码的唯一性和分类。我们的大多数分类结果都与二进制Golay代码的子代码有关。这是与安德里斯·布鲁瓦（Andries Brouwer）的联合合作。 5。我们考虑了圆形图的香农能力。圆形图$ c_ {d，q} $是带有顶点集$ \ mathbb {z} _q $（Q $的循环Q）的图形，其中两个不同的顶点在且仅当它们的距离（mod $ q $）严格小于$ d $的情况下，并且仅当它们的距离（mod $ q $）相邻。 $ C_ {D，Q} $的香农容量仅取决于Q/d的分数。我们证明，分配给每个有理数$ q/d $的功能$ c_ {d，q} $在整数点$ q/d $是连续的。此外，我们对$ 7 $ cycle的香农容量提供了新的下限。这是与Lex Schrijver的联合合作。 本文在Lex Schrijver的监督下在阿姆斯特丹大学写了。
In this thesis we present several results in coding theory, concerning error-correcting codes and the Shannon capacity. 1. We give a general symmetry reduction of matrices occuring in semidefinite programs in coding theory. 2. We apply the symmetry reduction to efficiently compute semidefinite programming upper bounds for nonbinary error-correcting codes equipped with the Hamming distance (joint work with Bart Litjens and Lex Schrijver), with the Lee distance and for binary constant weight codes. 3. We explore other methods to find new upper bounds for nonbinary codes with the Hamming distance, based on combinatorial divisibility arguments. 4. We study uniqueness and classification of codes, using the output of the semidefinite programming solver. Most of our classification results are related to subcodes of the binary Golay code. This is joint work with Andries Brouwer. 5. We consider the Shannon capacity of circular graphs. The circular graph $C_{d,q}$ is the graph with vertex set $\mathbb{Z}_q$ (the cyclic group of order q) in which two distinct vertices are adjacent if and only if their distance (mod $q$) is strictly less than $d$. The Shannon capacity of $C_{d,q}$ can be seen to only depend on the fraction q/d. We prove that the function which assigns to each rational number $q/d$ the Shannon capacity of $C_{d,q}$ is continuous at integer points $q/d$. Moreover, we give a new lower bound on the Shannon capacity of the $7$-cycle. This is joint work with Lex Schrijver. This thesis was written at the University of Amsterdam under supervision of Lex Schrijver.
