Belief propagation decoding using factor graph permutations

Download

index.pdf

Date

2019

Author

Tosun, Berna

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

88
views

73
downloads

Capacity-achieving polar codes, introduced by Arıkan have attracted significant attention over a decade. The bottleneck in coding is the decoder structure that achieves good performance with low hardware implementation cost and high throughput. Unlike the successive cancellation decoder, belief propagation decoder that can be improved by decoding on multiple factor graphs, allows for parallel decoding. For a polar code of length N, there are ({u1D459}{u1D45C}{u1D454}2{u1D441})!={u1D45B}!different permutations of the layers in the factor graph. Multiple factor graph belief propagation decoders that employ {u1D45B}factor graphs have the complexity of O({u1D441}(log{u1D441})2), and the choice of proper sets among {u1D45B}!factor graphs for performance optimization is a challenging topic that has not yet been fully explored. n this thesis, belief propagation decoding performance of polar codes over the additive white Gaussian noise channel is studied, by using single or multiple factor graphs within the decoder. The performance gap between the best and worst single factor graph decoders is found; and for multiple factor graph decoders, it is shown that random choice of factor graphs is incompetent for long code lengths. Two set-choice methods, MaxSON and MaxofMax rules are suggested for multiple factor graph decoders with nelements, as an alternative to the cyclically shifted set of factor graphs. viPerformance of proposed set-choice rulesare compared with cyclic, randomand two other multiple factor graph belief propagation decoders given in the literature, for different code lengths with 6 ≤{u1D459}{u1D45C}{u1D454}2{u1D441}≤14

Subject Keywords

Coding theory., Keywords: Polar Codes, Belief Propagation, Multiple Factor Graph Decoder.

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Polar codes: performance over fading channels and convergence to reed-muller codes Özvarış, Irmak; Diker Yücel, Melek.; Department of Electrical and Electronics Engineering (2019) Polar codes introduced in 2008 by Erdal Arıkan have been proven to achieve Shannon capacity for any binary-input discrete memoryless channel. Being adopted as a part of the official coding scheme for the 5G standard, up-to-date research has moved from theory to practical applications, albeit keeping the connection with its ancestors. This thesis aims to address these two topics, narrowing down firstly to the performance of polar codes on fading binary symmetric channels and then to the relationship between ...
TIMED AUTOMATA ROBUSTNESS ANALYSIS VIA MODEL CHECKING Bendik, Jaroslav; Sencan, Ahmet; Aydın Göl, Ebru; Cerna, Ivana (2022-01-01) Timed automata (TA) have been widely adopted as a suitable formalism to model time-critical systems. Furthermore, contemporary model-checking tools allow the designer to check whether a TA complies with a system specification. However, the exact timing constants are often uncertain during the design phase. Consequently, the designer is often able to build a TA with a correct structure, however, the timing constants need to be tuned to satisfy the specification. Moreover, even if the TA initially satisfies t...
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...
Nuclear Fission-Nuclear Fusion algorithm for global optimization: a modified Big Bang-Big Crunch algorithm YALÇIN, YAĞIZER; Pekcan, Onur (Springer Science and Business Media LLC, 2020-04-01) This study introduces a derivative of the well-known optimization algorithm, Big Bang-Big Crunch (BB-BC), named Nuclear Fission-Nuclear Fusion-based BB-BC, simply referred to as N2F. Broadly preferred in the engineering optimization community, BB-BC provides accurate solutions with reasonably fast convergence rates for many engineering problems. Regardless, the algorithm often suffers from stagnation issues. More specifically, for some problems, BB-BC either converges prematurely or exploits the promising r...
Deconvolution and preequalization with best delay LS inverse filters Tuncer, Temel Engin (Elsevier BV, 2004-11-01) A new method for finding the best delay for the design of least-squares (1,S) inverse filters is introduced. It is shown that there is a considerable difference between the LS errors of a best delay filter and an arbitrary LS inverse filter. Proposed method is an effective and computationally efficient approach for the design of LS optimum filters. Deconvolution problem is considered and the MSE performances of pseudoinverse, preequalization and LS inverse filtering are investigated. In this respect, the th...

Citation Formats

B. Tosun, “Belief propagation decoding using factor graph permutations,” Thesis (M.S.) -- Graduate School of Natural and Applied Sciences. Electrical and Electronics Engineering., Middle East Technical University, 2019.