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.***

这项研究的目标是提高错误校正代码的计算效率，并将这项工作中的技术应用于计算和信息理论的其他问题。 纠正校正代码是所有电子通信系统的重要组成部分。 最近开发了可以非常有效地编码和解码的错误校正代码的新结构。 这项研究的目的是通过以下方式扩展此初始工作：改善基于先前开发的代码的错误校正代码的明确结构的误差和速度。开发可以证明随机结构质量的算法。使用相关技术提高对信息理论和电子通信至关重要的其他任务的计算效率。开发代码的质量实现，这将使工程师更容易测试这些代码在自己的应用领域中的性能。拟议调查的教育目标在范围上更广泛。 它们涉及课程的设计，这些课程向研究生讲述了这项研究所基于的更大的数学框架。 这些课程应吸引来自数学的学生以及计算机科学，以了解可以应用数学想法来解决计算机科学中重要问题的新有趣方式。 这些课程旨在教授如何建立研究中的联系，并为它们提供许多领域的连接领域。 最终，这些班级将教学学生的另一个基本要素：在数学研究中使用计算实验的方法。 他们将学习如何使用计算机实验来制作和测试组合猜想。 当他们开始将计算机视为可以帮助他们进行自己研究的工具时，他们将不可避免地会关注计算算法的效率，并获得直觉，而数学思想可能会导致实际算法。*** ***。