M.Sc Thesis | |

M.Sc Student | Abramov Herzel |
---|---|

Subject | Research and Implementation of Polar Codes for Processes with Memory |

Department | Department of Electrical and Computer Engineering |

Supervisor | ASSOCIATE PROF. Ido Tal |

Full Thesis text |

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|*^{3}*L 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*.