Reliable communication over noisy channels by Guessing Random Additive Noise Decoding (GRAND)

In 1948 Claude Shannon published his remarkable paper "A Mathematical
Theory of Communication", which formed the basis for the digital
communication revolution that was to follow, and gave rise to the field
of Information Theory. As part of that ground-breaking work, he
identified the greatest rate at which data can be communicated over a
noisy channel, and also provided an algorithm for achieving it. Despite
its mathematical elegance, his algorithm is impractical, and much work
in the intervening 70 years has focused on identifying more practical
approaches that enable reliable communication at high rates. That work
is ongoing and, for example, Polar Codes, first introduced by Erdal
Arikan in 2009, have recently been adopted as one of the two coding
schemes to be used in the 5G cellular standard.

In this two part talk we revisit communication over a noisy channel
through the lens of a new universal channel decoding algorithm called
GRAND (Guessing Random Additive Noise Decoding), which we introduced in
2018. GRAND has surprising practical and theoretical features that set
it apart from earlier approaches. The first part of this talk provides
an introduction to the problem of reliable communication and focuses on
an algorithmic description of GRAND, attempting to explain why we are
investing significant effort in its development. The second part of the
talk contains gory detail of the mathematics that underpins the
algorithm's theoretical analysis, a probabilistic topic called Guesswork
whose formalism dates back to 1994. Analysis of GRAND provides an
alternate means for proving of Shannon's original channel
coding theorem, giving rise to several new insights along the way. In
both parts of the presentation, ongoing work and open problems will be
discussed.

The talk is based on collaborative work with Muriel Medard and her group
at MIT.