IEEE Montréal Keynote Event: Universal Noise Centric Decoding
Please join us for this year IEEE Montréal Keynote Event.
- Date: 13 May 2021
- Time: 06:00 PM to 08:00 PM (Eastern Time)
- Speaker: Professor Muriel Medard
- Organized by: IEEE Montreal Section
- Registration: https://events.vtools.ieee.org/m/268217
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. His proposed algorithm used on random codes and a code centric maximum Maximum Likelihood (ML) decoding, where channel outputs are compared to all possible input codewords to select the most likely candidate based on the observed channel output. Despite its mathematical elegance, his code centric decoding 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.
In collaboration with Ken Duffy and his group, we introduce a new algorithm, Guessing Random Additive Noise Deceasing (GRAND) for a noise-centric, rather than code-centric, ML decoding. The receiver rank orders noise effect sequences from most likely to least likely, and guesses accordingly. When inverting, in decreasing order of likelihood, noise effect sequences from the received signal, the first instance that results in an element of the code-book is the ML decoding. Our results show that, with GRAND, even extremely simple codes, such as CRCs, match or outperform state-of-the-art code/decoder pairs, indicating that the choice of decoder is likely to be more important than that of code.
We illustrate the practical usefulness of our approach and discuss its hardware implementation, done with Rabia Yazicigil and her group. The complexity of the decoding is, for the sorts of channels generally used in commercial applications, quite low, unlike code-centric ML and the chip is able to decode any linear code.