Tata Institute of Fundamental Research

A brief introduction to polar codes

STCS Student Seminar
Speaker: Sreejata Kishor Bhattacharya
Organiser: Arghya Chakraborty
Date: Friday, 2 Sep 2022, 14:00 to 15:00
Venue: A201

(Scan to add to calendar)
Abstract:  In his seminal work in 1948 (A Mathematical Theory of Communication) Shannon introduced the capacity of a channel: the maximum rate at which information can be reliably communicated across a channel. Shannon proved that for every memoryless channel there exists error correcting codes which achieve rate arbitrarily close to capacity. However Shannon's proof was an existential one: he was unable to give any efficient encoding and decoding scheme that would allow communication over a channel at rates close to capacity. This remained a major open problem until 2008 when Erikan introduced polar codes. These codes achieve Shannon capacity over any symmetric memoryless channel, and in special cases such as BSC (binary symmetric channel) and BEC (binary erasure channel) have efficient decoding algorithms as well. We shall discuss polar codes in the special case of BSC: we shall give an overview of their encoding and decoding schemes.