Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

Peker, Ahmet Gökhan

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

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.

Related papers

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

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.

•Jan 1, 2018•0 citations

Polar Codes: Characterization of Exponent, Bounds, and Constructions

Satish Babu Korada, Eren Şaşoğlu, Rudiger L. Urbanke

Polar codes were recently introduced by Arıkan. They achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the $2 \times 2$ matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was shown by Arıkan and Telatar that this construction achieves an error exponent of $\frac12$, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding $\frac12$. We first show that any $\ell \times \ell$ matrix none of whose column permutations is upper triangular polarizes symmetric channels. We then characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding $\frac12$. Further, we give a general construction based on BCH codes which for large $n$ achieves exponents arbitrarily close to 1 and which exceeds $\frac12$ for size 16.

arXiv:0901.0536•Jan 5, 2009•30 citations

Decoding Reed-Muller and Polar Codes by Successive Factor Graph Permutations

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

Reed-Muller (RM) and polar codes are a class of capacity-achieving channel coding schemes with the same factor graph representation. Low-complexity decoding algorithms fall short in providing a good error-correction performance for RM and polar codes. Using the symmetric group of RM and polar codes, the specific decoding algorithm can be carried out on multiple permutations of the factor graph to boost the error-correction performance. However, this approach results in high decoding complexity. In this paper, we first derive the total number of factor graph permutations on which the decoding can be performed. We further propose a successive permutation (SP) scheme which finds the permutations on the fly, thus the decoding always progresses on a single factor graph permutation. We show that SP can be used to improve the error-correction performance of RM and polar codes under successive-cancellation (SC) and SC list (SCL) decoding, while keeping the memory requirements of the decoders unaltered. Our results for RM and polar codes of length 128 and rate 0.5 show that when SP is used and at a target frame error rate of 10-4, up to 0.5 dB and 0.1 dB improvement can be achieved for RM and polar codes respectively.

arXiv:1807.03912•International Symposium on Turbo Codes and Iterative Information Processing•Dec 1, 2018•45 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, 2010•121 citations

Non-binary polar codes using Reed-Solomon codes and algebraic geometry codes

Ryuhei Mori, Toshiyuki Tanaka

Polar codes, introduced by Arıkan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.

arXiv:1007.3661•IEEE Information Theory Workshop (ITW)•Aug 1, 2010•94 citations

Improved Hybrid RM-Polar Codes and Decoding on Stable Permuted Factor Graphs

Wu Wei, Zhen Zhai, Paul H. Siegel

A new family of modified polar codes and a new permutation selection scheme for belief propagation list (BPL) decoding are presented. We first propose a new code construction methodology to interpolate between Reed-Muller (RM) codes and polar codes. By taking advantage of an existing partial order on bit-channels whose corresponding indices share the same Hamming weight, we analyze the complexity of the new construction method. It is shown that we need to compute the reliability of roughly a fraction 1/log3/2N of all the bit-channels contained in the subset. Then, we explore a special family of factor-graph layer permutations called stable permutations (SPs) that preserve a specified information set when the corresponding bit permutations are applied to message bit indices. Simulation results show that the error-rate performance of the new family of codes is better than that of 5G polar codes under successive cancellation list (SCL) decoding. In addition, the SP selection scheme stands out as a preferred one for BPL decoding in terms of error-rate performance, while the average number of iterations per belief propagation (BP) decoder on the permuted factor graph is close to that of the original BP decoder when an early stopping condition is applied.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•3 citations
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.
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.
Polar codes were recently introduced by Arıkan. They achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the 2×22 \times 22×2 matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was shown by Arıkan and Telatar that this construction achieves an error exponent of 12\frac1221​, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding 12\frac1221​. We first show that any ℓ×ℓ\ell \times \ellℓ×ℓ matrix none of whose column permutations is upper triangular polarizes symmetric channels. We then characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding 12\frac1221​. Further, we give a general construction based on BCH codes which for large nnn achieves exponents arbitrarily close to 1 and which exceeds 12\frac1221​ for size 16.
Reed-Muller (RM) and polar codes are a class of capacity-achieving channel coding schemes with the same factor graph representation. Low-complexity decoding algorithms fall short in providing a good error-correction performance for RM and polar codes. Using the symmetric group of RM and polar codes, the specific decoding algorithm can be carried out on multiple permutations of the factor graph to boost the error-correction performance. However, this approach results in high decoding complexity. In this paper, we first derive the total number of factor graph permutations on which the decoding can be performed. We further propose a successive permutation (SP) scheme which finds the permutations on the fly, thus the decoding always progresses on a single factor graph permutation. We show that SP can be used to improve the error-correction performance of RM and polar codes under successive-cancellation (SC) and SC list (SCL) decoding, while keeping the memory requirements of the decoders unaltered. Our results for RM and polar codes of length 128 and rate 0.5 show that when SP is used and at a target frame error rate of 10-4, up to 0.5 dB and 0.1 dB improvement can be achieved for RM and polar codes respectively.
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.
Polar codes, introduced by Arıkan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.
A new family of modified polar codes and a new permutation selection scheme for belief propagation list (BPL) decoding are presented. We first propose a new code construction methodology to interpolate between Reed-Muller (RM) codes and polar codes. By taking advantage of an existing partial order on bit-channels whose corresponding indices share the same Hamming weight, we analyze the complexity of the new construction method. It is shown that we need to compute the reliability of roughly a fraction 1/log3/2N of all the bit-channels contained in the subset. Then, we explore a special family of factor-graph layer permutations called stable permutations (SPs) that preserve a specified information set when the corresponding bit permutations are applied to message bit indices. Simulation results show that the error-rate performance of the new family of codes is better than that of 5G polar codes under successive cancellation list (SCL) decoding. In addition, the SP selection scheme stands out as a preferred one for BPL decoding in terms of error-rate performance, while the average number of iterations per belief propagation (BP) decoder on the permuted factor graph is close to that of the original BP decoder when an early stopping condition is applied.