Mathematical Sciences: Binary Linear Codes: Nonexistence and Classification Theorems

9623205 Jaffe该奖项为一个项目提供资金，该项目涉及寻找和实现用于分类二进制线性代码的算法。这些算法是用一种正在开发的语言编写的，这种语言便于对二进制线性码的证明进行机械验证。一种方法是采用一个广义权重枚举器，并使用它来生成一个线性规划问题，就像Delsarte对普通权重枚举器所做的那样。这些线性规划问题往往很大，因此通常不适合手工计算。一个特别有前途的权重枚举器是由n的分区产生的拆分权重枚举器，其中n是代码的长度。利用这种方法和其他方法，将证明关于二进制线性码的许多新的具体结果。反过来，这些可能会提出新的算法和封闭形式的一般陈述。这项研究是关于纠错码的，这是数学组合学、计算机科学和电气工程中的一个基本主题。当信息必须通过有噪声的信道从一个地方传输到另一个地方时，这种编码是必不可少的。例如，它们被用于激光唱机，将数字音乐从CD表面传输到播放器内部，以及用于地球和轨道卫星之间的通信。纠错码的工作原理是创造性地在传输的信息中加入冗余，使接收器能够检测并纠正传输过程中出现的错误，这些错误是由（例如）CD表面的灰尘或宇宙射线引起的。如果代码允许检测和纠正许多错误，而不会产生过多冗余的代价，那么它就是好的。这个奖项既资助寻找好的代码，也资助研究它们能有多好的数学限制。

9623205 Jaffe This award provides funding for a project involving the search for and implementation of algorithms for classifying binary linear codes. These algorithms are codified in a language, under development, which facilitates the mechanical verification of proofs about binary linear codes. One method is to take a generalized weight enumerator, and use it to generate a linear programming problem, as Delsarte did with the ordinary weight enumerator. Thse linear programming problems tend to be large, and thus are not generally amenable to hand calculation. One particularly promising weight enumerator is the split weight enumerator arising from a partition of n, where n is the length of the code. Using this method and others, many new specific results about binary linear codes will be proved. In turn, these may suggest new algorithms and closed-form general statements. This research is about error-correcting codes, a fundamental topic in mathematical combinatorics, computer science, and electrical engineering. Such codes are indispensable whenever information must be transferred across noisy channels from one place to another. For example,they are used in compact disk players to get digitized music from the surface of the CD to the inside of the player, and in communications between the earth and orbiting satellites. Error-correcting codes work by creatively incorporating redundancy into the transmitted message, to permit the receiver to detect and correct those errors introduced in transit, which were caused by (for instance) dust on the surface of the CD or cosmic rays. A code is good if it allows the detection and correction of many errors without incurring the expense of excessive redundancy. This award funds both a search for good codes and an investigation into the mathematical limitations of how good they can be.