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

IEEE Information Theory Workshop (ITW)

A new multiple folded successive cancellation decoder for polar codes

Harish Vangala, Emanuele Viterbo, Yi Hong

Published Nov 1, 2014• 8 citations
Publisher

Abstract

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.

DOI
10.1109/itw.2014.6970858

Related papers

Permuted successive cancellation decoder for polar codes

Harish Vangala, Emanuele Viterbo, Yi Hong

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.

International Symposium on Information Theory and its Applications•Dec 11, 2014•16 citations

Fast Successive-Cancellation-Based Decoders of Polar Codes

Maryam Haghighi Ardakani, Muhammad Hanif, Masoud Ardakani +1 more

The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code.

IEEE Transactions on Communications•Mar 19, 2019•62 citations

High Performance Low Latency Parallel Successive Cancelation Decoder Structures for Polar Codes

Abdelkareim Alrtaimi, Orhan Gazi

Multi-Parallel SCD Polar Coding BEC Polar codes are decoded using successive cancellation (SC) algorithm where likelihood ratios (LRs) for data bits are calculated in a sequential manner, and decisions are made using the calculated LRs.During the decoding of an information bit, the decision results for the predecessor bits are used, and a wrongly decided predecessor bit has negative effect on the accurate calculation of the LR for the information bit being decoded.In SC algorithm, when LR=1, the information bit is decoded as u _i=0, however, such a decision has 50% of chance of being correct.In this paper, we propose improved polar decoders utilizing a number of SC decoders.We consider the case of LR=1, and propose polar decoder structures for the more accurate calculation of the LRs of the successor bits.

Cankaya University Journal of Humanities and Social Sciences•Nov 1, 2020•0 citations

A Muti-Bit Flip Successive Cancellation Decoder for Polar Codes

Xiaonan Jiang, Xiaoming Niu, Ruihuan Tian +3 more

A decoding algorithm for polar codes based on successive cancellation is proposed in this paper, which determines the location of multiple bit errors by calculating the maximum likelihood result of successive cancellation decoding, and achieves the improvement of decoding performance by flipping the values of multiple bits. Simulation results show that the proposed multi-bit flip decoding algorithm exhibits better performance than the single-bit flip decoding algorithm with the same-order computational complexity under the additive white Gaussian noise (AWGN). In addition, as the signal-to-noise ratio (SNR) increases, the complexity of the proposed algorithm approaches that of the successive cancellation decoder.

International Symposium on Antennas, Propagation and EM Theory (ISAPE)•Oct 23, 2024•1 citation

An Improved Multiple Bit-Flipping Successive Cancellation Decoding Algorithm for Polar Codes

Sha Sha, Li Guo Zhang, Yejun He

Although original successive cancellation flip (SCF) decoding of the polar codes can identify the first error position and flip the error, decoding still fails when other errors occur after the corrected error bit. Therefore, the improvement of the block error rate (BLER) performance is limited. In this paper, we present an improved algorithm that can correct multiple error bits, named as improved multiple bit-flipping successive cancellation decoding algorithm. First, multiple sets are constructed by calculating the log likelihood ratio (LLR) of each information bit. Then, a bit is selected and corrected from the first set when original decoding fails; two bits are selected and flipped from the second set when all bits in the first set cannot be successfully decoded; when all bits combinations in the second set are flipped but the output vector still does not match the input vector, three bits are selected and corrected from the third set. Simulation results show that the BLER performance of the improved algorithm is better than that of the successive cancellation list decoding (SCL) decoding algorithm with a list size of L = 8 for N = 256. When N = 1024 and SNR = 3 dB, the BLER performance of improved algorithm is slightly better than that of SCL decoding algorithm with a list size of L = 4.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 21, 2020•1 citation

Improved Polar Decoder Utilizing Neural Network in Fast Simplified Successive-Cancellation Decoding

Jiaxin Fang, Chunwu Liu

Polar codes using successive-cancellation decoding always suffer from high latency for its serial nature. Fast simplified successive-cancellation decoding algorithm improves the situation in theoretically but not performs well as expected in practical for the workload of nodes identification and the existence of many short blocks. Meanwhile, Neural network (NN) based decoders have appeared as potential candidates to replace conventional decoders for polar codes. But the exponentially increasing training complexity with information bits is unacceptable which means it is only suitable for short codes. In this paper, we present an improvement that increases decoding efficiency without degrading the error-correction performance. The long polar codes are divided into several sub-blocks, some of which can be decoded adopting fast maximum likelihood decoding method and the remained parts are replaced by several short codes NN decoders. The result shows that time steps the proposed algorithm need only equal to 79.8% of fast simplified successive-cancellation decoders require. Moreover, it has up to 21.2 times faster than successive-cancellation decoding algorithm. More importantly, the proposed algorithm decreases the hardness when applying in some degree.

Journal of Computer and Communications•Jan 1, 2020•2 citations
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.
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.
The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code.
Multi-Parallel SCD Polar Coding BEC Polar codes are decoded using successive cancellation (SC) algorithm where likelihood ratios (LRs) for data bits are calculated in a sequential manner, and decisions are made using the calculated LRs.During the decoding of an information bit, the decision results for the predecessor bits are used, and a wrongly decided predecessor bit has negative effect on the accurate calculation of the LR for the information bit being decoded.In SC algorithm, when LR=1, the information bit is decoded as u _i=0, however, such a decision has 50% of chance of being correct.In this paper, we propose improved polar decoders utilizing a number of SC decoders.We consider the case of LR=1, and propose polar decoder structures for the more accurate calculation of the LRs of the successor bits.
A decoding algorithm for polar codes based on successive cancellation is proposed in this paper, which determines the location of multiple bit errors by calculating the maximum likelihood result of successive cancellation decoding, and achieves the improvement of decoding performance by flipping the values of multiple bits. Simulation results show that the proposed multi-bit flip decoding algorithm exhibits better performance than the single-bit flip decoding algorithm with the same-order computational complexity under the additive white Gaussian noise (AWGN). In addition, as the signal-to-noise ratio (SNR) increases, the complexity of the proposed algorithm approaches that of the successive cancellation decoder.
Although original successive cancellation flip (SCF) decoding of the polar codes can identify the first error position and flip the error, decoding still fails when other errors occur after the corrected error bit. Therefore, the improvement of the block error rate (BLER) performance is limited. In this paper, we present an improved algorithm that can correct multiple error bits, named as improved multiple bit-flipping successive cancellation decoding algorithm. First, multiple sets are constructed by calculating the log likelihood ratio (LLR) of each information bit. Then, a bit is selected and corrected from the first set when original decoding fails; two bits are selected and flipped from the second set when all bits in the first set cannot be successfully decoded; when all bits combinations in the second set are flipped but the output vector still does not match the input vector, three bits are selected and corrected from the third set. Simulation results show that the BLER performance of the improved algorithm is better than that of the successive cancellation list decoding (SCL) decoding algorithm with a list size of L = 8 for N = 256. When N = 1024 and SNR = 3 dB, the BLER performance of improved algorithm is slightly better than that of SCL decoding algorithm with a list size of L = 4.
Polar codes using successive-cancellation decoding always suffer from high latency for its serial nature. Fast simplified successive-cancellation decoding algorithm improves the situation in theoretically but not performs well as expected in practical for the workload of nodes identification and the existence of many short blocks. Meanwhile, Neural network (NN) based decoders have appeared as potential candidates to replace conventional decoders for polar codes. But the exponentially increasing training complexity with information bits is unacceptable which means it is only suitable for short codes. In this paper, we present an improvement that increases decoding efficiency without degrading the error-correction performance. The long polar codes are divided into several sub-blocks, some of which can be decoded adopting fast maximum likelihood decoding method and the remained parts are replaced by several short codes NN decoders. The result shows that time steps the proposed algorithm need only equal to 79.8% of fast simplified successive-cancellation decoders require. Moreover, it has up to 21.2 times faster than successive-cancellation decoding algorithm. More importantly, the proposed algorithm decreases the hardness when applying in some degree.