M.Sc Thesis

M.Sc StudentAbramov Herzel
SubjectResearch and Implementation of Polar Codes for Processes
with Memory
DepartmentDepartment of Electrical and Computer Engineering
Supervisor ASSOCIATE PROF. Ido Tal
Full Thesis textFull thesis text - English Version


Polar codes are a novel family of error correcting codes, discovered in 2009 by Prof. Erdal Arıkan. Since their discovery, they have been generalized in many ways. Two important generalizations are to channels with a non-binary input alphabet and to channels with memory. In this thesis, we tackle two computational problems related to these generalizations.

The first problem we consider is how to efficiently construct polar codes for channels with non-binary input. If done naively, such a construction would require an intractably large amount of time. In this thesis, we implement a construction method outlined in [1]. Specifically, we implement both a degrading and an upgrading algorithm for channels with non-binary input. This is done in order to find the usable polar channels: those that have high enough entropy when not conditioned on the output (in order to facilitate shaping), and with low enough entropy when conditioned on the output (in order to facilitate decoding). The first criterion is met by considering an upgraded channel and the second by considering a degraded channel.

The second problem we consider is how to speed-up the successive cancellation list decoder for channels with memory. A straightforward implementation would require time O( |S|3L N log(N)), where |S| is the number of states in the underlying Markov process representing the channel, L is the list size, and N is the block-length. We have identified two sub-calculations that are amenable to parallelization via GPGPUs (General Purpose Graphics Processing Units). Specifically, the calculations related to the memory of the channel, in which we iterate over the states in the Markov chain, can be parallelized. Moreover, one can parallelize the recursive calculations related to each polar channel.

[1] “An Upgrading Algorithm with Optimal Power Law”, O. Ordentlich, I. Tal. Submitted to IEEE Trans. Inform. Theory.