Polar Coding Without Alphabet Extension for Asymmetric Models

TLDR

Polar coding for asymmetric channels and lossy source coding with nonuniform sources or asymmetric distortion is challenging because optimal symbol distributions are often nonuniform, and Gallager's mapping scheme becomes complex when these distributions cannot be approximated by simple rational numbers. The authors propose a new polar coding scheme that attains channel capacity without alphabet extension for asymmetric settings. The scheme achieves this by leveraging results from polar coding for lossless compression. It achieves a better tradeoff between complexity and decoding error probability in many cases.

Abstract

This paper considers polar coding for asymmetric settings, that is, channel coding for asymmetric channels and lossy source coding for nonuniform sources and/or asymmetric distortion measures. The difficulty for asymmetric settings comes from the fact that the optimal symbol distributions of codewords are not always uniform. It is known that such nonuniform distributions can be realized by Gallager's scheme which maps multiple auxiliary symbols distributed uniformly to an actual symbol. However, the complexity of Gallager's scheme increases considerably for the case that the optimal distribution cannot be approximated by simple rational numbers. To overcome this problem for the asymmetric settings, a new polar coding scheme is proposed, which can attain the channel capacity without any alphabet extension by invoking results on polar coding for lossless compression. It is also shown that the proposed scheme achieves a better tradeoff between complexity and decoding error probability in many cases.