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

International Symposium on Information Theory and its Applications

Permuted successive cancellation decoder for polar codes

Harish Vangala, Emanuele Viterbo, Yi Hong

Published Dec 11, 2014• 16 citations
OpenAlex

Abstract

Abstract—We study a new variant of Arikan’s successive cancellation decoder (SCD) for polar codes. We first propose a new decoding algorithm on a new decoder graph, where the various stages of the graph are permuted. We then observe that, even though the usage of the permuted graph doesn’t affect the encoder, it can significantly affect the decoding performance of a given polar code. The new permuted successive cancellation decoder (PSCD) typically exhibits a performance degradation, since the polar code is optimized for the standard SCD. We then present a new polar code construction rule matched to the PSCD and show in simulations that this can yield BER gains for high code rates. For lower rates we observe that the polar code matched to a given PSCD performs as well as the original polar code with the standard SCD. We also see that a PSCD with a reversal permutation can lead to a natural decoding order, avoiding the standard bit-reversal decoding order in SCD without any loss in performance. Keywords—Successive cancellation decoder, permuted succes-sive cancellation decoder, decoding order, permuted polar code construction, permutation invariance of the polar encoder. I.

Related papers

A new multiple folded successive cancellation decoder for polar codes

Harish Vangala, Emanuele Viterbo, Yi Hong

We consider a new variant of successive cancellation decoder (SCD) for polar codes based on the concept of folding, which was proposed in [1], [2] as technique to reduce the decoding latency at the cost of a higher computational complexity. In this paper, we first formally define the multiple folding operation (iterated κ times), which decomposes the original encoding graph into a number of smaller polar encoding graphs. More specifically, we show that the multiple folding gives rise to a two stage interpretation of the graph representing the polar encoder and the SCD. Based on this, we propose the improved multiple folded successive cancellation decoder (IMFSCD), which combines SCD in one stage and maximum-likelihood decoding in the other. This decoder exhibits a latency gain by a factor of 2κ, still retaining a complexity close to the classic SCD. The small increase in complexity is due to a short maximum likelihood decoder (MLD) used in place of a SCD in the last decoding stage within the IMFSCD. Moreover, we observe by simulation that the decoder performance is exactly the same as that of an SCD at all rates.

IEEE Information Theory Workshop (ITW)•Nov 1, 2014•8 citations

Permutation Decoding of Polar Codes

Mikhail Kamenev, Yulia Kameneva, Oleg Kurmaev +1 more

A new permutation decoding approach for polar codes is presented. The proposed decoder can be used to achieve the error correction performance of a successive cancellation list (SCL) decoder, while it can either improve latency of the SCL decoder or decrease its hardware complexity. As opposed to the SCL algorithm, the proposed permutation algorithm can be implemented without sorting operation. It is shown that the error correction performance of the algorithm is similar to that of the SCL decoder for polar codes. Moreover, a new construction aiming to improve the error correction performance of polar codes under the proposed algorithm is presented.

arXiv:1901.05459•International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY)•Oct 1, 2019•32 citations

Belief propagation decoding of polar codes on permuted factor graphs

Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer +1 more

We show that the performance of iterative belief propagation (BP) decoding of polar codes can be enhanced by decoding over different carefully chosen factor graph realizations. With a genie-aided stopping condition, it can achieve the successive cancellation list (SCL) decoding performance which has already been shown to achieve the maximum likelihood (ML) bound provided that the list size is sufficiently large. The proposed decoder is based on different realizations of the polar code factor graph with randomly permuted stages during decoding. Additionally, a different way of visualizing the polar code factor graph is presented, facilitating the analysis of the underlying factor graph and the comparison of different graph permutations. In our proposed decoder, a high rate Cyclic Redundancy Check (CRC) code is concatenated with a polar code and used as an iteration stopping criterion (i.e., genie) to even outperform the SCL decoder of the plain polar code (without the CRC-aid). Although our permuted factor graph-based decoder does not outperform the SCL-CRC decoder, it achieves, to the best of our knowledge, the best performance of all iterative polar decoders presented thus far.

arXiv:1801.04299•IEEE Wireless Communications and Networking Conference•Apr 1, 2018•72 citations

Belief Propagation With Permutated Graphs of Polar Codes

Liping Li, Liangliang Liu

The belief propagation (BP) decoding of polar codes provides better bit error rate (BER) and packet error rate (PER) performance than the successive cancelation (SC) decoding. It has been reported in the literature that the graph of BP decoding of polar codes can be permuted to provide even better decoding performance. In this paper, we theoretically prove that all permutations of the graph are equivalent in terms of the polar encoding. For BP decoding, it is shown that permutations of the layers of the graph also permute the bit channels. A principle which protects the weakest information bit channel is provided in the paper. Two parallel BP decoders, one employing the standard graph and the other selected based on the selection principle, are also proposed to work together. The simulation results show that when the total number of iterations is fixed, the proposed BP decoding can have the same performance as the existing permutation scheme while provides a higher throughput.

IEEE Access•Jan 1, 2020•8 citations

Improved Permutation-Based Successive Cancellation Decoding of Polar Codes

Mikhail Kamenev

Polar codes have been recently shown to have an automorphism group larger than the lower-triangular affine group. Permutations from this group can be used in an automorphism successive cancellation (SC) decoding algorithm providing a lower latency compared to that of successive cancellation list decoding. In this paper, we demonstrate that any permutation from the automorphism group of Reed-Muller codes is suitable for permutation-based SC decoding of polar codes. Specifically, a code obtained by a permutation that is not in the automorphism group of the code, but is in the automorphism group of Reed-Muller codes, is shown to be a polar subcode. Simulations results show that these additional permutations allow improving performance of the automorphism SC decoding algorithm limited to the permutations from the automorphism group of the code.

International Siberian workshops and tutorials on electron devices and materials•Jun 30, 2021•8 citations

A Hybrid OSD-SC Decoding Algorithm for Polar Codes

Yusheng Xing, Guofang Tu

In this paper, we propose a low complexity hybrid ordered statistics decoding (OSD) successive cancellation (SC) decoding algorithm for the polar codes. By replacing smaller size SC decoder with OSD decoder, we can improve the error correcting performance of the SC algorithm. The size of the OSD decoder can be changed to control the trade-off between the decoding complexity and the error correcting performance of the proposed algorithm. We also provide a method to further simplify the proposed algorithm. Simulation results show that the proposed algorithm offers about 0.3 dB gain comparing to the SC at target bit error rate (BER) 10-5with code length N = 1024, 512,256 and code rate R = 1 /3. The impact of the OSD size is also simulated and analyzed.

IEEE Information Technology, Networking, Electronic and Automation Control Conference (ITNEC)•Mar 1, 2019•4 citations
Abstract—We study a new variant of Arikan’s successive cancellation decoder (SCD) for polar codes. We first propose a new decoding algorithm on a new decoder graph, where the various stages of the graph are permuted. We then observe that, even though the usage of the permuted graph doesn’t affect the encoder, it can significantly affect the decoding performance of a given polar code. The new permuted successive cancellation decoder (PSCD) typically exhibits a performance degradation, since the polar code is optimized for the standard SCD. We then present a new polar code construction rule matched to the PSCD and show in simulations that this can yield BER gains for high code rates. For lower rates we observe that the polar code matched to a given PSCD performs as well as the original polar code with the standard SCD. We also see that a PSCD with a reversal permutation can lead to a natural decoding order, avoiding the standard bit-reversal decoding order in SCD without any loss in performance. Keywords—Successive cancellation decoder, permuted succes-sive cancellation decoder, decoding order, permuted polar code construction, permutation invariance of the polar encoder. I.
We consider a new variant of successive cancellation decoder (SCD) for polar codes based on the concept of folding, which was proposed in [1], [2] as technique to reduce the decoding latency at the cost of a higher computational complexity. In this paper, we first formally define the multiple folding operation (iterated κ times), which decomposes the original encoding graph into a number of smaller polar encoding graphs. More specifically, we show that the multiple folding gives rise to a two stage interpretation of the graph representing the polar encoder and the SCD. Based on this, we propose the improved multiple folded successive cancellation decoder (IMFSCD), which combines SCD in one stage and maximum-likelihood decoding in the other. This decoder exhibits a latency gain by a factor of 2κ, still retaining a complexity close to the classic SCD. The small increase in complexity is due to a short maximum likelihood decoder (MLD) used in place of a SCD in the last decoding stage within the IMFSCD. Moreover, we observe by simulation that the decoder performance is exactly the same as that of an SCD at all rates.
A new permutation decoding approach for polar codes is presented. The proposed decoder can be used to achieve the error correction performance of a successive cancellation list (SCL) decoder, while it can either improve latency of the SCL decoder or decrease its hardware complexity. As opposed to the SCL algorithm, the proposed permutation algorithm can be implemented without sorting operation. It is shown that the error correction performance of the algorithm is similar to that of the SCL decoder for polar codes. Moreover, a new construction aiming to improve the error correction performance of polar codes under the proposed algorithm is presented.
We show that the performance of iterative belief propagation (BP) decoding of polar codes can be enhanced by decoding over different carefully chosen factor graph realizations. With a genie-aided stopping condition, it can achieve the successive cancellation list (SCL) decoding performance which has already been shown to achieve the maximum likelihood (ML) bound provided that the list size is sufficiently large. The proposed decoder is based on different realizations of the polar code factor graph with randomly permuted stages during decoding. Additionally, a different way of visualizing the polar code factor graph is presented, facilitating the analysis of the underlying factor graph and the comparison of different graph permutations. In our proposed decoder, a high rate Cyclic Redundancy Check (CRC) code is concatenated with a polar code and used as an iteration stopping criterion (i.e., genie) to even outperform the SCL decoder of the plain polar code (without the CRC-aid). Although our permuted factor graph-based decoder does not outperform the SCL-CRC decoder, it achieves, to the best of our knowledge, the best performance of all iterative polar decoders presented thus far.
The belief propagation (BP) decoding of polar codes provides better bit error rate (BER) and packet error rate (PER) performance than the successive cancelation (SC) decoding. It has been reported in the literature that the graph of BP decoding of polar codes can be permuted to provide even better decoding performance. In this paper, we theoretically prove that all permutations of the graph are equivalent in terms of the polar encoding. For BP decoding, it is shown that permutations of the layers of the graph also permute the bit channels. A principle which protects the weakest information bit channel is provided in the paper. Two parallel BP decoders, one employing the standard graph and the other selected based on the selection principle, are also proposed to work together. The simulation results show that when the total number of iterations is fixed, the proposed BP decoding can have the same performance as the existing permutation scheme while provides a higher throughput.
Polar codes have been recently shown to have an automorphism group larger than the lower-triangular affine group. Permutations from this group can be used in an automorphism successive cancellation (SC) decoding algorithm providing a lower latency compared to that of successive cancellation list decoding. In this paper, we demonstrate that any permutation from the automorphism group of Reed-Muller codes is suitable for permutation-based SC decoding of polar codes. Specifically, a code obtained by a permutation that is not in the automorphism group of the code, but is in the automorphism group of Reed-Muller codes, is shown to be a polar subcode. Simulations results show that these additional permutations allow improving performance of the automorphism SC decoding algorithm limited to the permutations from the automorphism group of the code.
In this paper, we propose a low complexity hybrid ordered statistics decoding (OSD) successive cancellation (SC) decoding algorithm for the polar codes. By replacing smaller size SC decoder with OSD decoder, we can improve the error correcting performance of the SC algorithm. The size of the OSD decoder can be changed to control the trade-off between the decoding complexity and the error correcting performance of the proposed algorithm. We also provide a method to further simplify the proposed algorithm. Simulation results show that the proposed algorithm offers about 0.3 dB gain comparing to the SC at target bit error rate (BER) 10-5with code length N = 1024, 512,256 and code rate R = 1 /3. The impact of the OSD size is also simulated and analyzed.