M.Sc Thesis
M.Sc Student Pereg Uziahu Channel Upgradation for Non-Binary Input Alphabets and MACs Department of Electrical Engineering Professor Ido Tal

Abstract

By Shannon's seminal paper in 1948, we know that information can be sent reliably over a channel at all rates below channel capacity. This can be achieved by appropriate coding, with a sufficiently large block length n.  Nevertheless, the so called Shannon's coding theorem is non-constructive, as it does not exhibit specific codes with efficient construction, encoding and decoding algorithms, and with rates that approach capacity. This work provides one of the tools required for the practical construction of capacity-achieving polar codes.

Consider a single-user or multiple-access channel with a large output alphabet. A method to approximate the channel by an upgraded version having a smaller output alphabet is presented and analyzed. The gain in sum-rate is controlled through fidelity parameter µ. The larger the fidelity parameter µ, the better the approximation on the one hand, but the larger the new output alphabet on the other.

No assumption is made on the symmetry of the original channel, and the input alphabet need not be binary. Also, the input distribution is given and it is not necessarily uniform (it may be arbitrary). Moreover the input distribution remains fixed during the upgradation procedure. The approximation method is instrumental when constructing polar codes for an asymmetric channel setting or in the wiretap setting. The method is also applicable when constructing polar codes for compression.

The family of polar codes has been recently introduced by Erdal Arɩkan. In his seminal paper, Arɩkan introduces capacity-achieving codes for a large class of channels. On top of being capacity achieving, polar codes have efficient algorithms for both encoding and decoding. Furthermore, Honda and Yamamoto present a simple and elegant capacity-achieving polar coding scheme for a memoryless channel, which is not necessarily binary, nor symmetric. Nevertheless, a straightforward attempt to carry out such a coding scheme is intractable (the complexity would be exponential in the code length). For many important scenarios, our algorithm provides a hitherto missing ``building-block'' required to efficiently implement a polar coding scheme.