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

差错控制码在实现计算机、通信、存储系统和无线网络的高度可靠操作方面继续发挥着重要作用。大多数码是在二进制对称信道（BSC）的错误模型下开发的，其中1到0错误的概率与0到1错误的概率相同。然而，最近开发的VLSI系统和存储器系统的错误性质是不同的。本计画考虑两个重要的误差模型，有限大小误差模型和符号插入/删除误差模型。本计画将针对这些错误模式探讨有效的错误控制码。 将考虑这些码的最佳设计和有效的编码/解码算法。此外，使用引脚效率的“平衡码”，其中每个码字包含相同数量的0和1，在VLSI系统中的噪声降低将进行调查。还计划在硅中实现平衡码并研究其性能。研究成果可以应用于广泛的领域，以实现更可靠的计算，通信和网络系统。该项目还将有助于加强教育和推广活动的本科生，研究生，和代表性不足的学生在PI的机构，包括他们在项目中。平衡码技术是克服现代VLSI芯片间通信噪声的一种新技术。与目前使用的“差分信令”技术相比，平衡码技术在引脚数方面是有效的。例如，为了在两个芯片之间传送k个数据位，差分信令方法需要k个额外的引脚，而平衡编码方法仅需要log_2（k）个额外的引脚。本计画将研究平衡码，以达到有效的超大型积体电路实现。本计画也将增进与零错误容量码相关的所有有限大小错误更正码的设计知识。自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.