Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
247
views
273
downloads
Cite This
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=logN 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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
A. G. Peker, “Belief propagation decoding of polar codes under factor graph permutations,” M.S. - Master of Science, Middle East Technical University, 2018.