Polar Codes for the Binary Coded Side-Information Problem (LTHC)


Polar codes, introduced by Arikan in [1], have been demonstrated to achieve the capacity of any binary-input memoryless output-symmetric channel 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 original point-to-point communication scheme has been extended to several multi-terminal scenarios (e.g., the Gelfand-Pinsker, Wyner-Ziv, and Slepian-Wolf problems, the multiple-access channel, the interference channel, the relay channel, and the broadcast channel, just to name some), in order to provide low-complexity coding schemes capable of matching the information theoretic bounds.

A practical solution for the problem of binary source coding with coded side-information which employs LDPC codes and a trellis quantizer has been developed in [2].

The aim of this project is to develop a polar coding scheme suited for this problem. First, one would start from the study of the binary case, for which a closed-form expression of the achievable rate region is known. Then, it would be interesting to implement such a polar scheme and see how it compares to the scheme in [2] based on LDPC codes and, in general, to the state of the art. Finally, the description of a general polar scheme for the non-binary case can be considered.



The student is required to have a good knowledge of information theory and coding. No prior knowledge of polar codes is required. Programming skills are also appreciated.



Marco Mondelli, INR 038, tel: +41 21 69 37514, email: marco.mondelli@epfl.ch

Rüdiger Urbanke, INR 116, tel: +41 21 69 37695, email: rudiger.urbanke@epfl.ch



[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.

[2] A. Savard and C. Weidmann, “Improved decoding for binary source coding with coded side information,” in Proc. IEEE Inf. Theory Workshop (ITW), Sept. 2013.