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

arXiv:1401.3127

From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

Published Jan 14, 2014• 0 citations
arXivHTMLPDF

Abstract

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family ${\mathcal C}_{\rm inter} = \{C_α : α\in [0, 1]\}$, where $C_α \big |_{α= 1}$ is the original polar code, and $C_α \big |_{α= 0}$ is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of $α$. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family ${\mathcal C}_{\rm inter}$ even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

DOI
10.48550/arxiv.1401.3127

Related papers

From polar to Reed-Muller codes: A technique to improve the finite-length performance

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1]}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cintereven under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•14 citations

From Polar to Reed-Muller Codes: A Technique to Improve the Finite-Length Performance

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1j}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.

IEEE Transactions on Communications•Aug 1, 2014•137 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

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: 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, 2012•4 citations

Interpolation of Quantum Polar Codes and Quantum Reed-Muller Codes

Keita Hidaka, Dina Abdelhadi, Rudiger L. Urbanke

Good quantum error-correcting codes that fulfill practical considerations, such as simple encoding circuits and efficient decoders, are essential for functional quantum information processing systems. Quantum polar codes satisfy some of these requirements but lack certain critical features, thereby hindering their widespread use. Existing constructions either require entanglement assistance to produce valid quantum codes, suffer from poor finite-size performance, or fail to tailor polar codes to the underlying channel properties. Meanwhile, quantum Reed-Muller (RM) codes demonstrate strong performance, though no known efficient decoding algorithm exists for them. In this work, we propose strategies to interpolate between quantum polar codes and quantum RM codes, thus addressing the challenges of designing valid quantum polar codes without entanglement assistance and improving finite-size code performance.

arXiv:2505.22142•IEEE Information Theory Workshop (ITW)•Sep 29, 2025•0 citations
We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that "interpolates" between RM and polar codes, call this family Cinter={Cα:α∈[0,1]}{\mathcal C}_{\rm inter} = \{C_α : α\in [0, 1]\}Cinter​={Cα​:α∈[0,1]}, where Cα∣α=1C_α \big |_{α= 1}Cα​​α=1​ is the original polar code, and Cα∣α=0C_α \big |_{α= 0}Cα​​α=0​ is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of ααα. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter{\mathcal C}_{\rm inter}Cinter​ even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.
We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1]}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cintereven under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.
We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family Cinter= {Cα: α ∈ [0, 1j}, where Cα|α=1is the original polar code, and Cα|α=0is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.
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.
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.
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.
Good quantum error-correcting codes that fulfill practical considerations, such as simple encoding circuits and efficient decoders, are essential for functional quantum information processing systems. Quantum polar codes satisfy some of these requirements but lack certain critical features, thereby hindering their widespread use. Existing constructions either require entanglement assistance to produce valid quantum codes, suffer from poor finite-size performance, or fail to tailor polar codes to the underlying channel properties. Meanwhile, quantum Reed-Muller (RM) codes demonstrate strong performance, though no known efficient decoding algorithm exists for them. In this work, we propose strategies to interpolate between quantum polar codes and quantum RM codes, thus addressing the challenges of designing valid quantum polar codes without entanglement assistance and improving finite-size code performance.