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

Oregon State University, Corvallis OR

Investigators

Abstract

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.