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.
