Belief propagation decoding of polar codes under factor graph permutations

---

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: 2018

Öğrenci: AHMET GÖKHAN PEKER

Danışman: MELEK DİKER

Özet:

Polar codes, introduced by Arıkan, are linear block codes that can achieve the capacity of symmetric binary-input discrete memoryless channels with low encoding and decoding complexity. Polar codes of block length N are constructed by channel polarization method, which consists of channel combining and splitting operations to obtain N polarized subchannels from N copies of binary-input discrete memoryless channels. As N grows, symmetric channel capacities of the polarized subchannels converge to either 0 or 1. Polar codes are also close cousins of Reed-Muller codes and start to differ from each other for N≥32. Encoding and decoding of polar or Reed-Muller codes can be performed by using a factor graph, obtained from the n-th Kronecker product G=F^(⊗n) of F=[(1&0@1&1)] with N=2^n. Such a factor graph contains n=log⁡N stages; hence, by changing the order of stages with respect to each other, n! different factor graphs can be obtained. In the literature, some decoders using multiple factor graphs instead of a single factor graph are suggested. Therefore, it is of interest whether i) the K×N generator matrix of the code chosen by K active bits at the input of the encoder, and ii) the sum of the capacities of the K active channels that connect each input bit to the output vector of the encoder are invariant under stage permutations. In this study, we give an alternative proof of the fact that the answer to the first question is positive. It is also shown that the sum of the capacities of the K active channels is not invariant under stage permutations. Belief Propagation decoding performances on single and multiple factor graph decoders of polar and Reed-Muller codes over binary erasure channels are evaluated and compared. For multiple factor graph decoders, practical choice of factor graph sets that gives the best performance with low complexity is examined.