CIF: Small: Capacity via Symmetry

Duke University, Durham NC

Investigators

Abstract

Information theory studies the fundamental laws that govern information processing systems. For instance, the Shannon Capacity of a noisy channel is the largest rate (in bits per channel use) that bits can be reliably communicated. Information theory has had an enormous impact on how information is acquired, processed, compressed, and transmitted. Examples include channel coding and data compression, both of which are used extensively in Internet and cellular communications. This project focuses on connections between performance and codebook symmetry. One part focuses on using symmetry to help low-complexity decoders achieve near-optimum performance for codes relevant to 5G cellular standards. This project will also train several graduate students, hence an important broader impact of this project is the production of highly-trained workers in electrical engineering and computer science. Many theoretical results in information theory use random codebooks to encode messages. Researchers have long sought families of deterministic algebraic codes that provably achieve capacity. In a recent breakthrough, the PI and his coauthors showed that sequences of sufficiently symmetric codes achieve capacity on the binary erasure channel. Since Reed-Muller codes satisfy the required symmetry condition, we now know that such a code family was discovered by Muller in 1954, only 6 years after Shannon's introduction of channel capacity! The project focuses on whether symmetric codebooks can be used in more general settings to approach information-theoretic limits. In particular, the goals are to determine: (i) How general is the phenomenon of capacity via symmetry? (ii) What performance gains can be achieved in practice by exploiting symmetries? (iii) Can symmetry be utilized to approach the information-theoretic limits of other problems?