An Investigation on belief propagation decoding of polar codes

Download

index.pdf

Date

2015

Author

Doğan, Orkun

Metadata

Show full item record

Item Usage Stats

166
views

140
downloads

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. These synthesized channels are called polarized since they go towards extremes; as N goes to infinity, NI(W) of them are perfect and N(1-I(W)) of them are purely noisy channels. One has to send data through the noiseless channels and send frozen bits, which are known by the receiver as well, through purely noisy channels to achieve the channel capacity. Arıkan proposed the Successive Cancellation (SC) decoding with low complexity O(NlogN), and also used the Belief Propagation (BP) decoding that can perform better with the same complexity. In this thesis, the encoding of polar codes by means of channel polarization is examined and BP decoding that employs round iterations is implemented on a factor graph with logN stages, for the binary erasure channel (BEC). Each round iteration starts by forwarding only left messages from the encoder output to the input and proceeds with only right messages from the input to the output. The number of round iterations required for BP decoding of polar codes is determined by simulations. The performance dependence of the BP decoding algorithm upon factor graphs, corresponding number of frozen variables and related capacities of the synthesized information bit channels are examined. In addition, the performance of BP decoding using multiple factor graphs with logN and (logN)! parallel paths is compared to the case of single factor graph decoding.

Subject Keywords

Signal theory (Telecommunication)., Signal processing., Information theory.

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

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...
Dimension reduced robust beamforming for towed arrays Topçu, Emre; Candan, Çağatay; Department of Electrical and Electronics Engineering (2015) Adaptive beamforming methods are used to obtain higher signal to interference plus noise ratio at the array output. However, these methods are very sensitive to steering vector and covariance matrix estimation errors. To overcome this issue, robust methods are usually employed. On the other hand, implementation of these robust methods can be computationally expensive for arrays with large number of sensors. Reduced dimension techniques aim to lower the computational load of adaptive beamforming algorithms w...
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.
On the Eigenstructure of DFT Matrices Candan, Çağatay (Institute of Electrical and Electronics Engineers (IEEE), 2011-03-01) The discrete Fourier transform (DFT) not only enables fast implementation of the discrete convolution operation, which is critical for the efficient processing of analog signals through digital means, but it also represents a rich and beautiful analytical structure that is interesting on its own. A typical senior-level digital signal processing (DSP) course involves a fairly detailed treatment of DFT and a list of related topics, such as circular shift, correlation, convolution operations, and the connectio...

Citation Formats

O. Doğan, “An Investigation on belief propagation decoding of polar codes,” M.S. - Master of Science, Middle East Technical University, 2015.