An Investigation on Belief Propagation Decoding of Polar Codes

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Elektrik ve Elektronik Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2015

Öğrenci: ORKUN DOĞAN

Danışman: MELEK DİKER

Özet:

Polar codes are provably symmetric capacity achieving codes for any given binary input discrete memoryless channel, with low encoding and decoding complexities. Polar codes introduced by Erdal Arıkan in 2009 are based on the channel polarization. N binary channels are synthesized out of N copies of binary input discrete memoryless channels, such that as N goes to infinity each of the synthesized channel’s capacity goes to either 0 or 1; i.e., the channels are seen purely as noisy or noiseless channels. These synthesized channels are called polarized since they go towards extremes; as N goes to infinity, NI(W) of them are perfect and N(1-I(W)) of them are purely noisy channels. One has to send data through the noiseless channels and send frozen bits, which are known by the receiver as well, through purely noisy channels to achieve the channel capacity. Arıkan proposed the Successive Cancellation (SC) decoding with low complexity O(NlogN), and also used the Belief Propagation (BP) decoding that can perform better with the same complexity. In this thesis, the encoding of polar codes by means of channel polarization is examined and BP decoding that employs round iterations is implemented on a factor graph with logN stages, for the binary erasure channel (BEC). Each round iteration starts by forwarding only left messages from the encoder output to the input and proceeds with only right messages from the input to the output. The number of round iterations required for BP decoding of polar codes is determined by simulations. The performance dependence of the BP decoding algorithm upon factor graphs, corresponding number of frozen variables and related capacities of the synthesized information bit channels are examined. In addition, the performance of BP decoding using multiple factor graphs with logN and (logN)! parallel paths is compared to the case of single factor graph decoding.