CIF: Small: Decoding Error-Correcting Codes using Large-Scale Decomposition Methods

CIF：小型：使用大规模分解方法解码纠错码

• 批准号: 1217058
• 负责人: Robert Nowak
• 金额: $ 42.41万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217058&HistoricalAwards=false
• 关键词: CIF; Small; Decoding; Error; Correcting

This research draws upon techniques from large-scale optimization to develop new decoding algorithms for error-correcting codes. Initial results yield a scalable decoding algorithm for linear programming decoding that runs as fast as state-of-the-art decoders, has a simple schedule, robust convergence guarantees, and achieves better empirical performance than standard decoding algorithms when the signal-to-noise ratio is high. The decoding algorithm will have a transformative effect on the types of codes used in high-reliability applications including storage, optical networks, and microprocessor architectures. This project will develop further results, analyzing in detail algorithmic behavior in the "error floor regime" where the signal-to-noise ratio is high. It will examine the algorithmic robustness to the specifics of hardware implementation, and investigate other applications in coding such as high-density, non-binary, and rank-metric codes. The PIs will extend the algorithmic methods to applications beyond decoding error-correcting codes, investigating large-scale data processing applications in graphical models and statistical estimation. The research thrusts of the project are well suited for incorporation into the PIs' courses in digital communication, optimization, and information processing for "big data" problems more broadly.

本研究利用大规模最佳化的技术来发展新的错误校正码的解码演算法。 初始结果产生一个可扩展的解码算法的线性规划解码，运行速度一样快的最先进的解码器，具有简单的时间表，强大的收敛保证，并实现更好的经验性能比标准的解码算法时，信噪比高。 解码算法将对高可靠性应用中使用的代码类型产生变革性影响，包括存储，光网络和微处理器架构。该项目将开发进一步的结果，详细分析在信噪比高的“错误平层制度”中的算法行为。 它将检查算法的鲁棒性的硬件实现的细节，并调查在编码，如高密度，非二进制和秩度量码的其他应用。PI将算法方法扩展到解码纠错码之外的应用，研究图形模型和统计估计中的大规模数据处理应用。 该项目的研究重点非常适合纳入PI的数字通信，优化和更广泛的“大数据”问题的信息处理课程。