Guessing Random Additive Noise Decoding (GRAND)

Tuesday, February 25, 2020 - 3:00pm to Wednesday, February 26, 2020 - 3:55pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Muriel Médard



Building and Room number



Claude Shannon's 1948 "A Mathematical Theory of Communication" provided the basis for the digital communication revolution. As part of that ground-breaking work, he identified the greatest rate (capacity) at which data can be communicated over a noisy channel. He also provided an algorithm for achieving it, based on random codes and a code-centric maximum Maximum Likelihood (ML) decoding, where channel outputs are compared to all possible codewords to select the most likely candidate based on the observed output. Despite its mathematical elegance, his algorithm is impractical from a complexity perspective and much work in the intervening 70 years has focused on co-designing codes and decoders that enable reliable communication at high rates.

We introduce a new algorithm for a noise-centric, rather than code-centric, ML decoding. The algorithm is based on the principle that the receiver rank orders noise sequences from most likely to least likely, and guesses noises accordingly. Subtracting noise from the received signal in that order, the first instance that results in an element of the code-book is the ML decoding. For common additive noise channels, we establish that the algorithm is capacity-achieving for uniformly selected code-books, providing an intuitive alternate approach to the channel coding theorem.  We illustrate the practical usefulness of our approach and the fact that it renders the decoding of random codes feasible. The complexity of the decoding is, for the sorts of channels generally used in commercial applications, quite low, unlike code-centric ML. 

This work is joint with Ken Duffy (Maynooth University).


Muriel Médard, Sc.D., is the Cecil H. Green Professor of Electrical Engineering and Computer Science (EECS) at MIT. She leads the Network Coding and Reliable Communications Group at the Research Laboratory for Electronics She is a fellow the Institute of Electrical and Electronics Engineers (IEEE), has been an editor for many publications, as well as Editor-in-Chief of the IEEE Journal on Selected Areas in Communications. She was President of the IEEE Information Theory Society and received its 2017 Wyner Service Award. She has served as a technical program committee co-chair of many of the major conferences in information theory, communications, and networking. She received the 2002 IEEE Kirchmayer Paper Prize, the 2009 IEEE Communication Society and Information Theory Society Joint Paper Award, the 2009 IEEE Bennett Paper Prize, the 2019 IEEE Transactions on Network Science and Engineering, the 2016 IEEE Vehicular Technology Evans Award, the 2016 IEEE Women in Communication Engineering Outstanding Achievement Award, the 2017 IEEE Communications Society Armstrong Award,  the 2016 IEEE Vehicular Technology James Evans Avant-Garde Award,  the 2018 ACM Sigcomm Test of Time Award, and several conference paper awards. She received the MIT Edgerton Faculty Achievement Award and the EECS Graduate Student Association Mentor Award.  She was named a Gilbreth Lecturer by the U.S. National Academy of Engineering. She is a member of the US National Academy of Inventors.