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.
