CIF: Small: Collaborative Research: Error Correction with Natural Redundancy

CIF：小型：协作研究：利用自然冗余进行纠错

• 批准号: 1717884
• 负责人: Jehoshua Bruck
• 金额: $ 16.67万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1717884&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Error

Part 1: Nontechnical description of the projectThis project studies the fundamental problem of removing errors from data by using internal structures of data. It shows that the vast amount of data stored in current data-storage systems possess very rich structures; therefore, by fully exploiting them for error correction, the reliability of data-storage systems can be improved significantly. The project studies several fundamental aspects of this technology, including how to discover and characterize the highly complex structures of various types of data, how to use them to correct errors in data efficiently to improve the reliability of data-storage systems, how to combine the technology with existing error-correction techniques that are based on adding external redundancy to data, and how to implement the technology in practical data-storage systems. This project addresses a critical issue of the modern society: how to ensure that data can be stored reliably at large scale and over a long time. The new technology has the potential to substantially improve the dependability of information infrastructure, which accesses vast amounts of data frequently for scientific and industrial computing. The project is interdisciplinary in nature: it combines multiple scientific fields including information theory, machine learning, big data analysis and algorithm design, and aims to educate students and contribute to workforce development for next-generation storage systems. The project conjugates rigorous theoretical analysis and significant practical applications, to foster collaboration between academia and industry, and create new scientific advances with combined efforts.Part 2: Technical description of the projectThis project studies how to use the inherent redundancy in big data for error correction. Examples of big data include languages, images, databases, and others. The inherent redundancy is integrated with error-correcting codes (ECC) for effective error correction. The objective is to elevate data reliability in storage systems to the next level. To achieve this goal, new techniques will be developed to discover various types of inherent redundancy in both compressed and uncompressed data. New approaches will be explored to combine inherent-redundancy decoders and ECC decoders for effective error correction. Fundamental limits of both capacity and computational complexity will be studied for error correction using inherent redundancy.This project combines error correction with machine learning and is interdisciplinary in nature. It will expand the current knowledge on error correction in multiple ways. First, it uses techniques in natural language processing and deep learning to discover new types of redundancy in big data that are suitable for error correction, and which extend beyond current knowledge in joint source-channel coding. This includes redundancy discovery techniques for data already compressed by various compression algorithms. Second, it explores decoding algorithms for ECCs with not only regular ECC-imposed redundancy, but also irregular inherent redundancy. It extends existing error correction schemes to cast the fundamental limits of inherent redundancy for error correction, in terms of both capacity and computational complexity. Third, by integrating a theoretical study with practical systems, a foundation can be laid for next-generation systems that store and transmit big data.Modern society relies increasingly heavily on digital data. With the explosive amount of data generated each day, it is essential to make advances in error correction that can catch the speed of data explosion. This project aims at improving data reliability significantly to the next level, and improvements in this direction can be highly beneficial to the daily work and life of the modern society. This project, being interdisciplinary between coding theory and machine learning, can foster collaboration between the information theory and computer science communities. The project combines rigorous theoretical analysis with significant practical applications, to foster collaboration between academia and industry, and create new scientific advances with combined efforts. The proposed research will be integrated with engineering education by developing new courses for graduate and undergraduate students, and involving under-represented, domestic and international students in advanced research. The results will be actively publicized in national/international conferences and journals.

第一部分：项目的非技术性描述该项目研究通过使用数据的内部结构从数据中删除错误的基本问题。这表明，当前数据存储系统中存储的大量数据具有非常丰富的结构，充分利用这些结构进行纠错，可以显著提高数据存储系统的可靠性。该项目研究了这一技术的几个基本方面，包括如何发现和描述各种类型数据的高度复杂结构，如何利用它们有效地纠正数据中的错误以提高数据存储系统的可靠性，如何将这一技术与现有的基于向数据添加外部冗余的纠错技术相结合，以及如何在实际的数据存储系统中实现该技术。该项目解决了现代社会的一个关键问题：如何确保数据可以大规模和长时间可靠地存储。这项新技术有可能大大提高信息基础设施的可靠性，因为信息基础设施经常访问大量数据，用于科学和工业计算。该项目具有跨学科性质：它结合了多个科学领域，包括信息理论，机器学习，大数据分析和算法设计，旨在教育学生并为下一代存储系统的劳动力发展做出贡献。该项目结合严谨的理论分析和重要的实际应用，促进学术界和产业界的合作，共同努力创造新的科学进步。第二部分：项目技术说明本项目研究如何利用大数据中固有的冗余进行纠错。大数据的例子包括语言、图像、数据库等。固有的冗余与纠错码（ECC）集成，以进行有效的纠错。其目标是将存储系统中的数据可靠性提升到一个新的水平。为了实现这一目标，将开发新的技术来发现压缩和未压缩数据中的各种类型的固有冗余。将探索新的方法来结合联合收割机的固有冗余解码器和ECC解码器的有效纠错。本项目将研究使用固有冗余进行纠错的容量和计算复杂性的基本限制。本项目将纠错与机器学习相结合，具有跨学科性质。它将以多种方式扩展当前关于纠错的知识。首先，它使用自然语言处理和深度学习技术来发现大数据中适合纠错的新型冗余，并且超出了联合信源信道编码的现有知识。这包括针对已经由各种压缩算法压缩的数据的冗余发现技术。其次，研究了既有规则ECC附加冗余又有不规则ECC固有冗余的ECC译码算法。它扩展了现有的纠错方案，以消除纠错的固有冗余的基本限制，在容量和计算复杂性方面。第三，将理论研究与实际系统相结合，为下一代大数据存储和传输系统奠定基础。现代社会对数字数据的依赖程度越来越高。随着每天生成的数据量呈爆炸式增长，必须在纠错方面取得进展，以赶上数据爆炸的速度。该项目旨在将数据的可靠性大幅提高到一个新的水平，这方面的改进对现代社会的日常工作和生活非常有益。该项目是编码理论和机器学习之间的跨学科，可以促进信息理论和计算机科学社区之间的合作。该项目将严格的理论分析与重要的实际应用相结合，以促进学术界和工业界之间的合作，并共同努力创造新的科学进步。拟议的研究将通过为研究生和本科生开发新课程，并让代表性不足的国内和国际学生参与高级研究，与工程教育相结合。研究结果将在国家/国际会议和期刊上积极公布。

项目成果

What is the Value of Data? on Mathematical Methods for Data Quality Estimation

• DOI: 10.1109/isit44484.2020.9174311
• 发表时间: 2020-01
• 期刊: 2020 IEEE International Symposium on Information Theory (ISIT)
• 作者: Netanel Raviv;Siddhartha Jain;Jehoshua Bruck

Two Deletion Correcting Codes from Indicator Vectors

指示向量的两个删除校正代码

• DOI: 10.1109/isit.2018.8437868
• 发表时间: 2020
• 期刊: IEEE transactions on information theory
• 影响因子: 2.5
• 作者: Sima, J.;Raviv, N. and
• 通讯作者: Raviv, N. and

Download and Access Trade-offs in Lagrange Coded Computing

• DOI: 10.1109/isit.2019.8849547
• 发表时间: 2019-01
• 期刊: 2019 IEEE International Symposium on Information Theory (ISIT)
• 作者: Netanel Raviv;Qian Yu;Jehoshua Bruck;A. Avestimehr

Correcting Deletions in Multiple-Heads Racetrack Memories

纠正多头赛道存储器中的删除

• DOI: 10.1109/isit.2019.8849783
• 发表时间: 2019
• 期刊: International Symposium on Information Theory and its Applications
• 作者: Sima, J.;Bruck, J.
• 通讯作者: Bruck, J.

Evolution of $k$ -Mer Frequencies and Entropy in Duplication and Substitution Mutation Systems

复制和替换突变系统中 $k$ -Mer 频率和熵的演化

• DOI: 10.1109/tit.2019.2946846
• 发表时间: 2020
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Lou, Hao;Schwartz, Moshe;Bruck, Jehoshua;Farnoud, Farzad
• 通讯作者: Farnoud, Farzad