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:2102.07994

Belief Propagation List Ordered Statistics Decoding of Polar Codes

Guy Mogilevsky, David Burshtein

Published Feb 16, 2021• 0 citations
arXivHTMLPDF

Abstract

It is shown how to combine ordered statistics decoding (OSD) with CRC-aided belief propagation list (CBPL) decoding of polar codes. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on CBPL. For reprocessing orders higher than one, we suggest partial reprocessing, where only error patterns associated with the least reliable part of the belief propagation decoded most reliable independent bits are considered. This type of partial reprocessing offers a trade-off between performance and computational complexity.

DOI
10.48550/arxiv.2102.07994

Related papers

Improving Belief Propagation List Decoding of Polar Codes by Post-Processing

Yonatan Urman, Guy Mogilevsky, David Burshtein

CRC-aided belief propagation list (CBPL) is a low latency, high throughput decoder for polar codes. In this work, it is shown that CBPL decoding of polar codes over the additive white Gaussian noise channel can be substantially improved using ordered statistics post-processing that only requires a very low reprocessing order (e.g., order one). We present efficient implementations of the ordered statistics post-processing with a trade-off between computational complexity and error rate.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•0 citations

Efficient Belief Propagation List Ordered Statistics Decoding of Polar Codes

Yonatan Urman, Guy Mogilevsky, David Burshtein

New algorithms for efficient decoding of polar codes (which may be CRC-augmented), transmitted over either a binary erasure channel (BEC) or an additive white Gaussian noise channel (AWGNC), are presented. We start by presenting a new efficient exact maximum likelihood decoding algorithm for the BEC based on inactivation decoding and analyze its computational complexity. This algorithm applies a matrix triangulation process on a sparse polar code parity check matrix, followed by solving a small size linear system over GF(2). We then consider efficient decoding of polar codes, transmitted over the AWGNC. The algorithm applies CRC-aided belief propagation list (CBPL) decoding, followed by ordered statistics decoding (OSD) of low order. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on plain CBPL. To implement the OSD efficiently, we adapt the matrix triangulation algorithm from the BEC case. We also indicate how the decoding algorithms can be implemented in parallel for low latency decoding. Numerical simulations are used to evaluate the performance and computational complexity of the new algorithms.

arXiv:2107.05965•Jul 13, 2021•1 citation

CRC-Aided Belief Propagation List Decoding of Polar Codes

Marvin Geiselhart, Ahmed Elkelesh, Moustafa Ebada +2 more

Although iterative decoding of polar codes has recently made huge progress based on the idea of permuted factor graphs, it still suffers from a non-negligible performance degradation when compared to state-of-the-art CRC-aided successive cancellation list (CA-SCL) decoding. In this work, we show that iterative decoding of polar codes based on the belief propagation list (BPL) algorithm can approach the error-rate performance of CA-SCL decoding and, thus, can be efficiently used for decoding the standardized 5G polar codes. Rather than only utilizing the cyclic redundancy check (CRC) as a stopping condition (i.e., for error-detection), we also aim to benefit from the error-correction capabilities of the outer CRC code. For this, we develop two distinct soft-decision CRC decoding algorithms: a Bahl-Cocke-Jelinek-Raviv (BCJR)-based approach and a sum product algorithm (SPA)-based approach. Further, an optimized selection of permuted factor graphs is analyzed and shown to reduce the decoding complexity significantly. Finally, we benchmark the proposed CRC-aided belief propagation list (CA-BPL) decoding to state-of-the-art 5G polar codes under CA-SCL decoding and, thereby, showcase an error-rate performance not just close to the CA-SCL but also close to the maximum likelihood (ML) bound as estimated by ordered statistic decoding (OSD).

arXiv:2001.05303•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•52 citations

Ordered Statistic Decoding for Short Polar Codes

Daolong Wu, Ying Li, Xudong Guo +1 more

In this letter, the ordered statistic decoding (OSD) is considered to decode short polar codes. Since the number of tested codewords is high in the original OSD, a threshold-based OSD is proposed to reduce the complexity. The analysis shows that the threshold affects the OSD in two ways. One is the error floor in high signal-to-noise ratio (SNR) region while the other is the reduction of the number of tested codewords. The estimation on the BLER performance in high SNR region and the average number of tested codewords are discussed. After that, CRC-aided OSD is proposed to further improve the performance of polar codes. Simulation results show that a well-designed threshold-based OSD can reduce the complexity without significant performance loss. And a higher order OSD decoder is needed if OSD is used to decoding moderate or long polar codes. It is also illustrated that the CRC-aided OSD outperforms the CRC-aided list decoding when the code rate is high. When code rate is low, the result inverses.

IEEE Communications Letters•Mar 7, 2016•50 citations

A Novel Flip-List-Enabled Belief Propagation Decoder for Polar Codes

Qasim Jan, Shahid Hussain, Muhammad Furqan +3 more

Due to the design principle of parallel processing, belief propagation (BP) decoding is attractive, and it provides good error-correction performance compared with successive cancellation (SC) decoding. However, its error-correction performance is still inferior to that of successive cancellation list (SCL) decoding. Consequently, this paper proposes a novel flip-list- (FL)-enabled belief propagation (BP) method to improve the error-correction performance of BP decoding for polar codes with low computational complexity. The proposed technique identifies the vulnerable channel log-likelihood ratio (LLR) that deteriorates the BP decoding result. The FL is utilized to efficiently identify the erroneous channel LLRs and correct them for the next BP decoding attempt. The preprocessed channel LLR through FL improves the error-correction performance with minimal flipping attempts and reduces the computational complexity. The proposed technique was compared with the state-of-the-art BP, i.e., BP bit-flip (BP-BF), generalized BP-flip (GBPF), cyclic redundancy check (CRC)-aided (CA-SCL) decoding, and ordered statistic decoding (OSD), algorithms. Simulation results showed that the FL-BP had an excellent block error rate (BLER) performance gain up to 0.7 dB compared with BP, BP-BF, and GBPF decoder. Besides, the computational complexity was reduced considerably in the high signal-to-noise ratio (SNR) regime compared with the BP-BF and GBPF decoding methods.

Electronics•Sep 18, 2021•9 citations

A Polar Subcode Approach to Belief Propagation List Decoding

Marvin Geiselhart, Ahmed Elkelesh, Jannis Clausius +1 more

Permutation decoding gained recent interest as it can exploit the symmetries of a code in a parallel fashion. Moreover, it has been shown that by viewing permuted polar codes as polar subcodes, the set of usable permutations in permutation decoding can be increased. We extend this idea to pre-transformed polar codes, such as cyclic redundancy check (CRC)-aided polar codes, which previously could not be decoded using permutations due to their lack of automorphisms. Using belief propagation (BP)-based subdecoders, we showcase a performance close to CRC-aided SCL (CA-SCL) decoding. The proposed algorithm outperforms the previously best performing iterative CRC-aided belief propagation list (CA-BPL) decoder both in error-rate performance and decoding latency.

arXiv:2205.06631•IEEE Information Theory Workshop (ITW)•Nov 1, 2022•8 citations
It is shown how to combine ordered statistics decoding (OSD) with CRC-aided belief propagation list (CBPL) decoding of polar codes. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on CBPL. For reprocessing orders higher than one, we suggest partial reprocessing, where only error patterns associated with the least reliable part of the belief propagation decoded most reliable independent bits are considered. This type of partial reprocessing offers a trade-off between performance and computational complexity.
New algorithms for efficient decoding of polar codes (which may be CRC-augmented), transmitted over either a binary erasure channel (BEC) or an additive white Gaussian noise channel (AWGNC), are presented. We start by presenting a new efficient exact maximum likelihood decoding algorithm for the BEC based on inactivation decoding and analyze its computational complexity. This algorithm applies a matrix triangulation process on a sparse polar code parity check matrix, followed by solving a small size linear system over GF(2). We then consider efficient decoding of polar codes, transmitted over the AWGNC. The algorithm applies CRC-aided belief propagation list (CBPL) decoding, followed by ordered statistics decoding (OSD) of low order. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on plain CBPL. To implement the OSD efficiently, we adapt the matrix triangulation algorithm from the BEC case. We also indicate how the decoding algorithms can be implemented in parallel for low latency decoding. Numerical simulations are used to evaluate the performance and computational complexity of the new algorithms.
Although iterative decoding of polar codes has recently made huge progress based on the idea of permuted factor graphs, it still suffers from a non-negligible performance degradation when compared to state-of-the-art CRC-aided successive cancellation list (CA-SCL) decoding. In this work, we show that iterative decoding of polar codes based on the belief propagation list (BPL) algorithm can approach the error-rate performance of CA-SCL decoding and, thus, can be efficiently used for decoding the standardized 5G polar codes. Rather than only utilizing the cyclic redundancy check (CRC) as a stopping condition (i.e., for error-detection), we also aim to benefit from the error-correction capabilities of the outer CRC code. For this, we develop two distinct soft-decision CRC decoding algorithms: a Bahl-Cocke-Jelinek-Raviv (BCJR)-based approach and a sum product algorithm (SPA)-based approach. Further, an optimized selection of permuted factor graphs is analyzed and shown to reduce the decoding complexity significantly. Finally, we benchmark the proposed CRC-aided belief propagation list (CA-BPL) decoding to state-of-the-art 5G polar codes under CA-SCL decoding and, thereby, showcase an error-rate performance not just close to the CA-SCL but also close to the maximum likelihood (ML) bound as estimated by ordered statistic decoding (OSD).
In this letter, the ordered statistic decoding (OSD) is considered to decode short polar codes. Since the number of tested codewords is high in the original OSD, a threshold-based OSD is proposed to reduce the complexity. The analysis shows that the threshold affects the OSD in two ways. One is the error floor in high signal-to-noise ratio (SNR) region while the other is the reduction of the number of tested codewords. The estimation on the BLER performance in high SNR region and the average number of tested codewords are discussed. After that, CRC-aided OSD is proposed to further improve the performance of polar codes. Simulation results show that a well-designed threshold-based OSD can reduce the complexity without significant performance loss. And a higher order OSD decoder is needed if OSD is used to decoding moderate or long polar codes. It is also illustrated that the CRC-aided OSD outperforms the CRC-aided list decoding when the code rate is high. When code rate is low, the result inverses.
Due to the design principle of parallel processing, belief propagation (BP) decoding is attractive, and it provides good error-correction performance compared with successive cancellation (SC) decoding. However, its error-correction performance is still inferior to that of successive cancellation list (SCL) decoding. Consequently, this paper proposes a novel flip-list- (FL)-enabled belief propagation (BP) method to improve the error-correction performance of BP decoding for polar codes with low computational complexity. The proposed technique identifies the vulnerable channel log-likelihood ratio (LLR) that deteriorates the BP decoding result. The FL is utilized to efficiently identify the erroneous channel LLRs and correct them for the next BP decoding attempt. The preprocessed channel LLR through FL improves the error-correction performance with minimal flipping attempts and reduces the computational complexity. The proposed technique was compared with the state-of-the-art BP, i.e., BP bit-flip (BP-BF), generalized BP-flip (GBPF), cyclic redundancy check (CRC)-aided (CA-SCL) decoding, and ordered statistic decoding (OSD), algorithms. Simulation results showed that the FL-BP had an excellent block error rate (BLER) performance gain up to 0.7 dB compared with BP, BP-BF, and GBPF decoder. Besides, the computational complexity was reduced considerably in the high signal-to-noise ratio (SNR) regime compared with the BP-BF and GBPF decoding methods.
Permutation decoding gained recent interest as it can exploit the symmetries of a code in a parallel fashion. Moreover, it has been shown that by viewing permuted polar codes as polar subcodes, the set of usable permutations in permutation decoding can be increased. We extend this idea to pre-transformed polar codes, such as cyclic redundancy check (CRC)-aided polar codes, which previously could not be decoded using permutations due to their lack of automorphisms. Using belief propagation (BP)-based subdecoders, we showcase a performance close to CRC-aided SCL (CA-SCL) decoding. The proposed algorithm outperforms the previously best performing iterative CRC-aided belief propagation list (CA-BPL) decoder both in error-rate performance and decoding latency.