Belief propagation decoding of polar codes under factor graph permutations

Peker, Ahmet Gökhan
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.


An Investigation on belief propagation decoding of polar codes
Doğan, Orkun; Diker Yücel, Melek; Department of Electrical and Electronics Engineering (2015)
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. Thes...
Galois structure of modular forms of even weight
Gurel, E. (Elsevier BV, 2009-10-01)
We calculate the equivariant Euler characteristics of powers of the canonical sheaf on certain modular curves over Z which have a tame action of a finite abelian group. As a consequence, we obtain information on the Galois module structure of modular forms of even weight having Fourier coefficients in certain ideals of rings of cyclotomic algebraic integers. (c) 2009 Elsevier Inc. All rights reserved.
A new concatenated type construction for LCD codes and isometry codes
CARLET, Claude; Guneri, Cem; Özbudak, Ferruh; SOLÉ, Patrick (2018-03-01)
We give a new concatenated type construction for linear codes with complementary dual (LCD) over small finite fields. In this construction, we need a special class of inner codes that we call isometry codes. Our construction generalizes a recent construction of Carlet et al. (2014-2016) and of Gtineri et al. (2016). In particular, it allows us to construct LCD codes with improved parameters directly.
Dynamic signaling games with quadratic criteria under Nash and Stackelberg equilibria
Yuksel, Serdar; Sarıtaş, Serkan; Gezici, Sinan (2020-05-01)
This paper considers dynamic (multi-stage) signaling games involving an encoder and a decoder who have subjective models on the cost functions. We consider both Nash (simultaneous-move) and Stackelberg (leader-follower) equilibria of dynamic signaling games under quadratic criteria. For the multi-stage scalar cheap talk, we show that the final stage equilibrium is always quantized and under further conditions the equilibria for all time stages must be quantized. In contrast, the Stackelberg equilibria are a...
Repeated - root cyclic codes and matrix product codes
Özadam, Hakan; Özbudak, Ferruh; Department of Cryptography (2012)
We study the Hamming distance and the structure of repeated-root cyclic codes, and their generalizations to constacyclic and polycyclic codes, over finite fields and Galois rings. We develop a method to compute the Hamming distance of these codes. Our computation gives the Hamming distance of constacyclic codes of length $np^s$\ in many cases. In particular, we determine the Hamming distance of all constacyclic, and therefore cyclic and negacyclic, codes of lengths p^s and 2p^s over a finite field of charac...
Citation Formats
A. G. Peker, “Belief propagation decoding of polar codes under factor graph permutations,” M.S. - Master of Science, Middle East Technical University, 2018.