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
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
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
A study on the set choice of multiple factor graph belief propagation decoders for polar codes
Download
index.pdf
Date
2018
Author
Akdoğan, Şükrü Can
Metadata
Show full item record
Item Usage Stats
196
views
104
downloads
Cite This
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{u1D441}. Each stage contains {u1D441}/2 many Z-shaped connections between specific input-output pairs. Defining the height of a Z connection as the node distance between its input (or output) nodes; Stage-{u1D456} that occurs only once in a factor graph for each {u1D456} = 1, … , {u1D45B}, contains Z-shapes of height 2 ({u1D456}−1) . Encoding is done with a specific factor graph, whose Z connections are ordered from the largest to the smallest, that we refer to as the “reference factor graph, {u1D45B}…321”. However, belief propagation decoding can be implemented with one of the {u1D45B}! different factor graphs, by permuting the stages of the reference factor graph. In this thesis, we study on belief propagation decoding of rate ½ polar codes over a binary erasure channel, using single or multiple factor graphs within the decoder. In order to classify the factor graphs, we propose the “stage order number”, in addition to the “number of frozen variables” and “capacity sum” parameters considered by [Doğan, 2015] and [Peker, 2018]. For {u1D45B} = 6, single factor graph decoding performances of {u1D45B}! factor graphs are demonstrated and related to the mentioned three parameters. Construction of compatible factor graph sets, in order to get better performance in multiple-factor graph decoding is studied and their performance is found for {u1D45B} = 6, 7, … , 11 by simulations. Since the sets, consisting of factor graphs with parameters varying in wide ranges seem to have better performance, we propose the “Set Choice” algorithm to compose factor graph sets with ensured variety. Multiple decoders using sets of ⌈{u1D45B}/2⌉ factor graphs obtained by this algorithm can achieve similar performance to that of the cyclic set of {u1D45B} factor graphs.
Subject Keywords
Decoders (Electronics).
,
Signal processing.
URI
http://etd.lib.metu.edu.tr/upload/12622344/index.pdf
https://hdl.handle.net/11511/27401
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...
A novel two-step pseudo-response based adaptive harmonic balance method for dynamic analysis of nonlinear structures
Sert, Onur; Ciğeroğlu, Ender (Elsevier BV, 2019-09-01)
Harmonic balance method (HBM) is one of the most popular and powerful methods, which is used to obtain response of nonlinear vibratory systems in frequency domain. The main idea of the method is to express the response of the system in Fourier series and converting the nonlinear differential equations of motion into a set of nonlinear algebraic equations. System response can be obtained by solving this nonlinear equation set in terms of the unknown Fourier coefficients. The accuracy of the solution is great...
A Distributed Fault-Tolerant Topology Control Algorithm for Heterogeneous Wireless Sensor Networks
Bagci, Hakki; KÖRPEOĞLU, İBRAHİM; Yazıcı, Adnan (Institute of Electrical and Electronics Engineers (IEEE), 2015-04-01)
This paper introduces a distributed fault-tolerant topology control algorithm, called the Disjoint Path Vector (DPV), for heterogeneous wireless sensor networks composed of a large number of sensor nodes with limited energy and computing capability and several supernodes with unlimited energy resources. The DPV algorithm addresses the k-degree Anycast Topology Control problem where the main objective is to assign each sensor's transmission range such that each has at least k-vertex-disjoint paths to superno...
Belief propagation decoding of polar codes under factor graph permutations
Peker, Ahmet Gökhan; Yücel, Melek Diker; Department of Electrical and Electronics Engineering (2018)
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...
On higher order approximations for hermite-gaussian functions and discrete fractional Fourier transforms
Candan, Çağatay (Institute of Electrical and Electronics Engineers (IEEE), 2007-10-01)
Discrete equivalents of Hermite-Gaussian functions play a critical role in the definition of a discrete fractional Fourier transform. The discrete equivalents are typically calculated through the eigendecomposition of a commutator matrix. In this letter, we first characterize the space of DFT-commuting matrices and then construct matrices approximating the Hermite-Gaussian generating differential equation and use the matrices to accurately generate the discrete equivalents of Hermite-Gaussians.
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
Ş. C. Akdoğan, “A study on the set choice of multiple factor graph belief propagation decoders for polar codes,” M.S. - Master of Science, Middle East Technical University, 2018.