Belief propagation decoding of polar codes under factor graph permutations

Download

index.pdf

Date

2018

Author

Peker, Ahmet Gökhan

Metadata

Show full item record

Item Usage Stats

357
views

353
downloads

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.

Subject Keywords

Coding theory.

URI

http://etd.lib.metu.edu.tr/upload/12621849/index.pdf
https://hdl.handle.net/11511/27067

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

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...
A study on the set choice of multiple factor graph belief propagation decoders for polar codes Akdoğan, Şükrü Can; Diker Yücel, Melek; Department of Electrical and Electronics Engineering (2018) Polar codes are linear block codes with low encoding and decoding complexity that are proven to achieve the channel capacity for any given binary-input discrete memoryless channel as the codeword length {u1D441} goes to infinity. The main idea of polar codes is about channel polarization. Special factor graphs are used to represent the encoding and decoding structure of polar codes. These factor graphs consist of {u1D45B} stages for ({u1D441},{u1D43E}) codes, where {u1D45B} = {u1D459}{u1D45C}{u1D454}2{u1D44...

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.