Reed-Muller Codes and Polar Codes

Corresponds to Lecture topic 7. Reed-Muller codes evaluate low-degree multivariate polynomials over $\mathbb F_2$ at every point of the Boolean hypercube — the same object analyzed via Fourier analysis in boolean-fourier-analysis-and-complexity-measures — and are built recursively via the Plotkin construction ($|u\,|\,u+v|$), which combines two smaller codes into a larger one with predictable rate and distance. Polar codes (Arikan) are a different recursive construction, also built from a Plotkin-like combining operation, but analyzed through channel polarization: repeatedly combining and splitting $n$ independent copies of a channel produces $n$ synthesized “bit channels” that, as $n\to\infty$, polarize — almost all become either essentially noiseless or essentially useless — and sending information only through the noiseless ones achieves Shannon capacity with an explicit, efficiently decodable construction, the first such capacity- achieving code for general binary-input symmetric channels.

Outline (TODO — flesh out each)

• Reed-Muller codes
• The Plotkin construction
• Polar codes — construction
• Channel polarization
• Capacity-achieving property and decoding