CCF:SHF: Small: Some New Class of Error Control Codes for VLSI and Computer Systems

在实现计算机、通信、存储系统和无线网络的高度可靠操作方面，差错控制码继续发挥重要作用。大多数码都是在二进制对称信道(BSC)的错误模型下产生的，其中1到0错误的概率与0到1错误的概率相同。然而，最近开发的VLSI系统和存储系统的错误性质是不同的。本项目考虑了两个重要的误差模型，有限量级误差模型和符号插入/删除误差模型。本项目将研究这些错误模型的有效差错控制码。将考虑码的优化设计和这些码的高效编码/译码算法。此外，还将研究使用管脚高效的“平衡码”(其中每个码字包含相等数量的0和1)的VLSI系统中的降噪问题。此外，还计划在硅片中实现平衡码，并研究其性能。研究成果可以应用于更广泛的领域，以实现更可靠的计算、通信和网络系统。该项目还将通过将本科生、研究生和代表人数不足的学生纳入项目，帮助加强他们的教育和外展活动。在现代VLSI芯片到芯片通信中克服噪声的平衡码技术是一种新颖的技术。与目前使用的“差分信令”技术相比，平衡码技术在管脚数方面是有效的。例如，为了在两个芯片之间传送k个数据比特，差分信令方法需要k个额外的管脚，而平衡编码方法仅需要log_2(K)个额外的管脚。该项目将研究平衡代码，目的是实现高效的VLSI实现。该项目还将提高与零差错容量码相关的所有有限幅度纠错码的设计知识。自1958年Shannon提出信道零差错容量的概念以来，本课题首次提出将零差错容量作为实现有限幅度差错信道系统编码的一种手段。50多年来，构造能够纠正符号插入/删除的码一直是一个公开的研究问题。基于初等对称函数的概念设计有限幅度纠错码是一种新的方法，这种码在使用的冗余度方面是有效的，在编解码复杂度方面也是有效的。本项目中研究的基本对称函数技术也可用于设计纠正符号插入和删除的代码。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Error-control codes continue to play a major role in achieving highly reliable operations of computers, communications, storage systems, and wireless networks. Most of the codes are developed under the error model of Binary Symmetric Channel (BSC), where the probability of a 1 to 0 error is the same as the probability of a 0 to 1 error. However, the error natures of the recently developed VLSI systems and memory systems are different. This project considers two important error models, the limited magnitude error model and the insertion/deletion of symbol error model. This project will investigate efficient error-control codes for these error models. The optimal design of codes and the efficient encoding/decoding algorithms for these codes will be considered. In addition, noise reduction in VLSI systems using pin-efficient "balanced codes," where each codeword contains an equal number of zeros and ones, will be investigated. It is also planned to implement the balanced codes in silicon and study their performance. The research results can be applied to broad areas in order to achieve more reliable computing, communications, and network systems. The project will also help enhance education and outreach activities of undergraduate, graduate, and underrepresented students at the PIs' institution by including them in the project. The balanced-code technique to overcome noise in modern VLSI chip-to-chip communications is novel. Compared to the currently used "differential-signaling" techniques the balanced-code technique is efficient in terms of the pin count. For example, to communicate k data bits between two chips, the differential-signaling method requires k extra pins, whereas the balanced coding method requires only log_2 (k) extra pins. This project will investigate balanced codes with the aim to achieve efficient VLSI implementation. This project will also advance the design knowledge of all limited-magnitude error-correcting codes, which are related to the zero-error capacity codes. Since the introduction of the concept of zero-error capacity of a channel in 1958 by Shannon, this project, for the first time, proposes the zero-error capacity as a means to achieving systematic codes for the limited-magnitude error channel. Constructing codes capable of correcting t insertion/deletion of symbols has been an open research problem for more than 50 years. Designing limited-magnitude error-correcting codes based on the concept of elementary symmetric functions is a novel approach, and the codes are efficient in terms of redundancy used, and also in terms of encoding and decoding complexities. The elementary symmetric-function technique investigated in this project can also be used to design codes correcting the insertion and deletion of symbols.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.