Online Tutorial for Polar Codes (LTHC)

Objective

The problem of achieving the maximum rate at which reliable transmission is possible over a channel, i.e., the capacity of a channel, dates back to the work by Shannon in 1948 and the construction of a capacity-achieving code which could be encoded and decoded in a low complexity fashion soon turned out to be a formidable problem. Recently, polar codes have been introduced in [1] and they have drawn the attention of the research community since they are able to achieve the capacity of binary-input memoryless symmetric channels with encoding and decoding complexity $\Theta(N\ log\,N)$ and error probability decaying roughly as $2^{-\sqrt{N}}$, where $N$ is the block length of the code. Since then, the polar coding paradigm has been widely explored and several interesting problems have been addressed:

  • the scaling law between the rate and the block length when the target error probability is fixed;

  • the robustness with respect to quantization;

  • the development and analysis of several decoders which allow to improve the performance of the originally proposed successive cancellation decoder;

  • source coding schemes based on polarization for lossless and lossy source coding;

  • construction of polar codes which are not channel-dependent, but are universal, in the sense that a single polar code can be used to transmit reliably over a whole class of channels of fixed capacity;

  • polar codes for channel with non-binary input alphabet;

  • polar codes for network scenarios, e.g., the relay channel, the broadcast channel, the inference channel, the multiple access channel, etc…

  • and many more…

The aim of this project is to develop an online tutorial thought for a broad audience to illustrate the advantages and applications, but also the disadvantages and open questions in the eld of polar coding. The tutorial should be interactive in the sense that it should contain demos to allow trade-o s between parameters and performance comparisons.

Prerequisites

The student is required to have some basic knowledge of information theory and coding. Programming skills are also recommended.

Supervisors

Marco Mondelli, INR 038, tel: +41 21 69 37514, email: marco.mondelli@ep .ch Rüdiger Urbanke, INR 116, tel: +41 21 69 37695, email: rudiger.urbanke@ep .ch

References

[1] E. Arikan, “Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051-3073, July 2009.