CAREER: Computationally Efficient Error-Correcting Codes and Their Applications

职业：计算高效的纠错码及其应用

• 批准号: 9701304
• 负责人: Daniel Spielman
• 金额: $ 31万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-01 至 2001-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9701304&HistoricalAwards=false
• 关键词: CAREER; Computationally; Efficient; Error; Correcting

The goals of this research are to improve the computational efficiency of error-correcting codes and to apply techniques from this effort to other problems of computation and information theory. Error-correcting codes are essential components of all electronic communication systems. New constructions for error-correcting codes that could be encoded and decoded very efficiently have recently been developed. The objectives of this research are to extend this initial work by: Improving the error-tolerance and speed of the explicit constructions of error-correcting codes based upon previously developed codes. Developing algorithms that can certify the quality of the randomized constructions. Using related techniques to improve the computational efficiency of other tasks vital to information theory and electronic communication. Developing quality implementations of the codes that will make it easier for engineers to test how these codes would perform in their own application areas. The educational goals of the proposed investigation are broader in scope. They involve the design of classes that teach graduate students about the larger mathematical framework on which this research rests. These classes should attract students from mathematics as well as computer science to learn about the new fascinating ways in which ideas from mathematics can be applied to solve important problems in computer science. These classes are designed to teach how connections in research are made as well as provide them with many areas ripe for connection. Eventually, these classes will teach the students another essential element of the principal investigator's research methodology: that of using computational experiments in mathematical research. They will learn how one can use computer experiments to make and test combinatorial conjectures. As they begin to see the computer as a tool that can aid them in their own research, they will inevitably become concerned with the efficie ncy of computational algorithms and gain intuition for which mathematical ideas might result in practical algorithms.***

本研究的目标是提高纠错码的计算效率，并将这项工作的技术应用于计算和信息论的其他问题。 纠错码是所有电子通信系统的基本组成部分。 最近已经开发出可以非常有效地编码和解码的纠错码的新构造。 本研究的目标是扩展这一初步的工作：提高容错性和速度的显式结构的纠错码的基础上以前开发的代码。开发算法，可以证明随机结构的质量。使用相关技术来提高对信息论和电子通信至关重要的其他任务的计算效率。开发代码的高质量实现，使工程师更容易测试这些代码在他们自己的应用领域中的性能。拟议调查的教育目标范围更广。 它们涉及课程的设计，这些课程教授研究生有关本研究所依赖的更大的数学框架。 这些课程应该吸引来自数学和计算机科学的学生，以了解数学思想可以应用于解决计算机科学中重要问题的新的迷人方式。 这些课程旨在教授研究中的联系是如何建立的，并为他们提供许多成熟的联系领域。 最终，这些课程将教给学生另一个主要研究者的研究方法的基本要素：在数学研究中使用计算实验。 他们将学习如何使用计算机实验来制作和测试组合图形。 当他们开始把计算机看作一种可以帮助他们进行研究的工具时，他们将不可避免地关心计算算法的效率，并获得数学思想可能导致实际算法的直觉。