CRII: CCF: Low-Complexity Coding at Optimal Length

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

Coding theory has for long focused on designing error-correcting codes with the assumption that the length of the transmission message can be made as large as desired. Modern settings, however, such as the Internet of Things and machine-to-machine communication, require devices to communicate short messages with very small delays while maintaining a high degree of reliability. This conjures up a long-standing challenge in coding theory: design low-complexity channel codes that provide high reliability and low latency. This project aims to develop error-correcting technologies well-suited to such demands of the evolving information infrastructure. This research will investigate two rich classes of code-designs: stream codes and Reed-Muller codes. Stream codes, recently proposed by the investigator and co-authors, combine the powerful features of convolutional encoding and iterative decoding, while Reed-Muller codes are classic code designs that have recently been shown to achieve capacity in erasure channels. Preliminary studies suggest that both stream and Reed-Muller codes have remarkable performance at short lengths, but using highly complex decoders, posing the issue of whether computationally efficient decoder may be found. This project focuses on developing novel algorithmic and analytical frameworks aiming to: (i) design efficient decoding algorithms; (ii) develop new theoretical frameworks for the analysis of the proposed algorithms; and (iii) establish fundamental length-rate-complexity trade-offs in the non-asymptotic regime. 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.