EE Seminar: On the Performance of Polar Codes in Various Communication Problems
Speaker: Dina Goldin
Ph.D. student under the supervision of Prof. David Burshtein
Wednesday, January 17th, 2018 at 15:00
Room 011, Kitot Bldg., Faculty of Engineering
On the Performance of Polar Codes in Various Communication Problems
Abstract
Arikan has introduced polar codes and showed that, for a sufficiently large blocklength, they can be used for reliable communications at rates arbitrarily close to the symmetric capacity (i.e., the mutual information between a uniform input distribution and the channel output) of an arbitrary binary-input channel. Their code construction is based on a phenomenon called “channel polarization”
Arikan also proposed encoding and decoding schemes, whose complexities scale as , whereis the blocklength of the code.
We derive improved upper bounds on the blocklength required to communicate over binary-input channels using polar codes, below some given error probability. For that purpose, an improved bound on the number of non-polarizing channels is obtained.
The first result is that the blocklength required to communicate reliably scales at most aswhere R is the code rate andthe symmetric capacity of the channel,. The results are then extended to polar lossy source coding at rateof a source with symmetric distortion-rate function.
The blocklength required scales at most as , whereis the maximal allowed gap between the actual average (or typical) distortion and.
The polarization process of polar codes over a prime 
-ary alphabet is studied as well. Previously it has been shown that the scaling of the blocklength of polar codes with prime alphabet size scales polynomially with respect to the inverse of the gap between code rate and channel capacity. However, except for the binary case, the degree of the polynomial in the bound is extremely large. In this work, a different approach to computing the degree of this polynomial for any prime alphabet size is shown. This approach yields a lower degree polynomial for various values of the alphabet size that were examined. It is also shown that even lower degree polynomial can be computed with an additional numerical effort.
A concatenated coding scheme over binary memoryless symmetric (BMS) channels using a polarization transformation followed by outer sub-codes is analyzed as well. Achievable error exponents and upper bounds on the error rate are derived. The first bound is obtained using outer codes which are typical linear codes from the ensemble of parity check matrices whose elements are chosen independently and uniformly. As a byproduct of this bound, it determines the required rate split of the total rate to the rates of the outer codes. A lower bound on the error exponent that holds for all BMS channels with a given capacity is then derived. Improved bounds and approximations for finite blocklength codes using channel dispersions (normal approximation), as well as converse and approximate converse results, are also obtained. The bounds are compared to actual simulation results from the literature. For the cases considered, when transmitting over the binary input additive white Gaussian noise channel, there was only a small gap between the normal approximation prediction and the actual error rate of concatenated BCH-polar codes.
