Kutupsal kodlar için çok faktör diyagramlı inanç yayılımı çözücülerinde küme seçimi üzerine bir çalışma.

Akdoğan, Şükrü Can

Published Jan 1, 2018• 0 citations

Abstract

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.

Related papers

Kutupsal kodların faktör grafiği permütasyonlarıyla inanç yayılımı kod çözümü.

Peker, Ahmet Gökhan

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.

Jan 1, 20180 citations

On the Decoding of Polar Codes on Permuted Factor Graphs

Nghia Doan, Seyyed Ali Hashemi, Marco Mondelli +1 more

Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10-4.

arXiv:1806.11195GlobecomDec 1, 201887 citations

On LP decoding of polar codes

Naveen Goela, Satish Babu Korada, Michael Gastpar

Polar codes are the first codes to provably achieve capacity on the symmetric binary-input discrete memoryless channel (B-DMC) with low encoding and decoding complexity. The parity check matrix of polar codes is high-density and we show that linear program (LP) decoding fails on the fundamental polytope of the parity check matrix. The recursive structure of the code permits a sparse factor graph representation. We define a new polytope based on the fundamental polytope of the sparse graph representation. This new polytope P is defined in a space of dimension O(N logN) where N is the block length. We prove that the projection of P in the original space is tighter than the fundamental polytope based on the parity check matrix. The LP decoder over P obtains the ML-certificate property. In the case of the binary erasure channel (BEC), the new LP decoder is equivalent to the belief propagation (BP) decoder operating on the sparse factor graph representation, and hence achieves capacity. Simulation results of SC (successive cancellation) decoding, LP decoding over tightened polytopes, and (ML) maximum likelihood decoding are provided. For channels other than the BEC, we discuss why LP decoding over P with a linear objective function is insufficient.

IEEE Information Theory Workshop (ITW)Aug 1, 2010121 citations

Graph-theoretic Aspects of Polar Codes

Jessalyn Bolkema

In 2008, Arikan introduced a powerful family of polar codes, which are the first codes to demonstrably achieve Shannon capacity. Polar codes are built on (and named for) the phenomenon of channel polarization: a mechanism for synthetically increasing and decreasing the reliabilities of a set of channels until some fraction are perfectly noiseless and the remaining channels are completely noisy. In Arikan’s initial publication, this is achieved with a simple recursive binary transform, and shortly thereafter, it was shown by Korada et al. that polarization is a very general phenomenon achieved by many different (not necessarily binary) recursive transforms. Transmission is straightforward once the reliable channels have been identified, but this task is difficult, both computationally and theoretically. Moreover, the guarantees of polar code performance come to fruition only as the code length goes to infinity. Polar codes do not compare favorably to, e.g., low-density parity-check codes at finite block lengths. Motivated by these concerns, this dissertation investigates graph-theoretic properties of polar codes in the context of belief propagation decoding. We first define the class of encoding trellises applicable to the polar coding framework and give a graph- theoretic criterion for polarization. A fundamental contribution is the introduction of the tensor-like join of trellises: a graph product which supplies a direct connection to the matrix construction of polar codes. We leverage the tensor-like join throughout as a mechanism for understanding both graph-theoretic structures and decoding outcomes. We build up a family of acyclic auxiliary graphs, called computation graphs, in order to study belief propagation analytically. In this context, we show that the tensor-like join is sufficient as a construction mechanism and moreover, that such constructions endow computation graphs with powerful structural properties. Following Wiberg, we extend the notion of a deviation as an indicator for decoding failure in the polar computation graph framework. We provide a recursive characterization of the deviation set for Arikan’s polar codes. Finally, looking to the future, we focus on further applications of the tools developed herein.

Jan 1, 20180 citations

Belief Propagation List Decoding of Polar Codes

Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer +1 more

We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.

arXiv:1806.10503IEEE Communications LettersJun 26, 2018161 citations

Polar Codes: Finite Length Implementation, Error Correlations and Multilevel Modulation

Mani Bastani Parizi

Shannon, in his seminal work, formalized the transmission of data over a communication channel and determined its fundamental limits. He characterized the relation between communication rate and error probability and showed that as long as the communication rate is below the capacity of the channel, error probability can be made as small as desirable by using appropriate coding over the communication channel and letting the codeword length approach infinity. He provided the formula for capacity of discrete memoryless channel. However, his proposed coding scheme was too complex to be practical in communication systems. Polar codes, recently introduced by Arikan, are the first practical codes that are known to achieve the capacity for a large class of channel and have low encoding and decoding complexity. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length as it goes to infinity. However, it is interesting to investigate their performance in finite length as this is the case in all practical communication schemes. In this dissertation, after a brief overview on polar codes, we introduce a practical framework for simulation of error correcting codes in general. We introduce the importance sampling concept to efficiently evaluate the performance of polar codes with finite bock length. Next, based on simulation results, we investigate the performance of different genie aided decoders to mitigate the poor performance of polar codes in low to moderate block length and propose single-error correction methods to improve the performance dramatically in expense of complexity of decoder. In this context, we also study the correlation between error events in a successive cancellation decoder. Finally, we investigate the performance of polar codes in non-binary channels. We compare the code construction of Sasoglu for Q-ary channels and classical multilevel codes. We construct multilevel polar codes for Q-ary channels and provide a thorough comparison of complexity and performance of two methods in finite length.

Jan 1, 20124 citations