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 International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)

List Selection and Decision Fusion Scheme for Belief Propagation List Decoding of Polar Codes

Zi Qi Chen, Li Li, Zheng Ma, Ping Zhi Fan

Published Sep 1, 2019• 7 citations
Publisher

Abstract

To the best of our knowledge, Belief Propagation List (BPL) decoding achieves the best error-correction performance within the class of BP based polar code decoding algorithms. It regards different permutations of the polar code factor graph as a range of available "decoding lists" for individually executing the BP algorithm. Then, a minimum Euclidean distance criterion is employed to combine these individual decisions. However, we demonstrated that simply increasing the number of lists involved in the BPL algorithm does not always improve its performance. Instead, we exploit the extrinsic information transfer (EXIT) chart technology to verify the efficiency of a decoding list. Based on this analysis, an efficient list selection scheme is proposed. In the same spirit, in order to mitigate the impact of relatively inferior decoding lists on other selected decoding lists, new decision fusion schemes are also designed. Benefiting from these improvements of BPL algorithm, performance gains are evidenced in our simulation results.

DOI
10.1109/pimrc.2019.8904186

Related papers

Belief Propagation List Decoding of Polar Codes

Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer +1 more

We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.

arXiv:1806.10503•IEEE Communications Letters•Jun 26, 2018•161 citations

Improved Belief Propagation List Decoding for Polar Codes

Binghao Li, Baoming Bai, Min Zhu +1 more

In this paper, we present an improved belief propagation list (BPL) decoding algorithm for polar codes. Rather than getting L factor graphs (FGs) at random and cyclic shift permutation, we use the upper bounds on the block error propability of polar codes with different FGs as the metric to choose the best L FGs. By observing the bounds of different FGs, we propose a heuristic method to reduce search complexity. Simulation results show that there is only a gap of 0.2 dB between the frame error rate (FER) performance of the improved BPL decoder using RM16-GA construction and that of length-1024 5G polar code decoded by SCL with the same list size of 32 at FER =10-4. Moreover, with the proposed FG selection method, BPL decoding can reduce clock cycles by 97.74% compared with the SCL decoding.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•10 citations

CRC-Aided Belief Propagation with Permutated Graphs Decoding of Polar Codes

Liyun Dai, Li Huang, Yaohui Bai +2 more

It has been shown that the permutation factor graph is an effective method to improve the performance of belief propagation (BP) decoding. The research of belief propagation list (BPL) algorithm based on permutation factor graph has also made great progress, but the complexity of decoding process is still too high. In order to compromise performance and complexity, in this work, we focus on the iterative convergence of BPL decoding algorithm, and propose an early termination BPL algorithm based on multiple CRCs. The results show that the improved BPL decoding scheme can provide higher throughput and achieve similar decoding performance with the existing BPL decoding under the same simulation condition.

IEEE International Conference on Electronic Information and Communication Technology (ICEICT)•Nov 13, 2020•4 citations

High-Throughput Flexible Belief Propagation List Decoder for Polar Codes

Yuqing Ren, Yifei Shen, Leyu Zhang +4 more

Owing to its high parallelism, belief propagation (BP) decoding is highly amenable to high-throughput implementations and thus represents a promising solution for meeting the ultra-high peak data rate of future communication systems. However, for polar codes, the error-correcting performance of BP decoding is far inferior to that of the widely used CRC-aided successive cancellation list (SCL) decoding algorithm. To close the performance gap to SCL, BP list (BPL) decoding expands the exploration of candidate codewords through multiple permuted factor graphs (PFGs). From an implementation perspective, designing a unified and flexible hardware architecture for BPL decoding that supports various PFGs and code configurations presents a big challenge. In this paper, we propose the first hardware implementation of a BPL decoder for polar codes and overcome the implementation challenge by applying a hardware-friendly algorithm that generates flexible permutations on-the-fly. First, we derive the graph selection gain and provide a sequential generation (SG) algorithm to obtain a near-optimal PFG set. We further prove that any permutation can be decomposed into a combination of multiple fixed routings, and we design a low-complexity permutation network to satisfy the decoding schedule. Our BPL decoder not only has a low decoding latency by executing the decoding and permutation generation in parallel, but also supports an arbitrary list size without any area overhead. Experimental results show that, for length-1024 polar codes with a code rate of one-half, our BPL decoder with 32 PFGs has a similar error-correcting performance to SCL with a list size of 4 and achieves a throughput of 25.63 Gbps and an area efficiency of 29.46 Gbps/mm$^{2}$ at SNR=4.0dB, which is 1.82$\times$ and 4.33$\times$ faster than the state-of-the-art BP flip and SCL decoders,~respectively

arXiv:2210.13887•Oct 25, 2022•4 citations

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

Belief propagation list decoding for polar codes: Performance analysis and software implementation on GPU

Zhanxian Liu, Wei Li, Lei Sun +3 more

Belief propagation (BP) decoding outputs soft information and can be naturally used in iterative receivers. BP list (BPL) decoding provides comparable error-correction performance to the successive cancellation list (SCL) decoding. In this paper, we firstly introduce an enhanced code construction scheme for BPL decoding to improve its error-correction capability. Then, a GPU-based BPL decoder with adoption of the new code construction is presented. Finally, the proposed BPL decoder is tested on NVIDIA RTX3070 and GTX1060. Experimental results show that the presented BPL decoder with early termination criterion achieves above 1 Gbps throughput on RTX3070 for the code (1024, 512) with 32 lists under good channel conditions.

China Communications•May 10, 2023•4 citations
To the best of our knowledge, Belief Propagation List (BPL) decoding achieves the best error-correction performance within the class of BP based polar code decoding algorithms. It regards different permutations of the polar code factor graph as a range of available "decoding lists" for individually executing the BP algorithm. Then, a minimum Euclidean distance criterion is employed to combine these individual decisions. However, we demonstrated that simply increasing the number of lists involved in the BPL algorithm does not always improve its performance. Instead, we exploit the extrinsic information transfer (EXIT) chart technology to verify the efficiency of a decoding list. Based on this analysis, an efficient list selection scheme is proposed. In the same spirit, in order to mitigate the impact of relatively inferior decoding lists on other selected decoding lists, new decision fusion schemes are also designed. Benefiting from these improvements of BPL algorithm, performance gains are evidenced in our simulation results.
We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.
In this paper, we present an improved belief propagation list (BPL) decoding algorithm for polar codes. Rather than getting L factor graphs (FGs) at random and cyclic shift permutation, we use the upper bounds on the block error propability of polar codes with different FGs as the metric to choose the best L FGs. By observing the bounds of different FGs, we propose a heuristic method to reduce search complexity. Simulation results show that there is only a gap of 0.2 dB between the frame error rate (FER) performance of the improved BPL decoder using RM16-GA construction and that of length-1024 5G polar code decoded by SCL with the same list size of 32 at FER =10-4. Moreover, with the proposed FG selection method, BPL decoding can reduce clock cycles by 97.74% compared with the SCL decoding.
It has been shown that the permutation factor graph is an effective method to improve the performance of belief propagation (BP) decoding. The research of belief propagation list (BPL) algorithm based on permutation factor graph has also made great progress, but the complexity of decoding process is still too high. In order to compromise performance and complexity, in this work, we focus on the iterative convergence of BPL decoding algorithm, and propose an early termination BPL algorithm based on multiple CRCs. The results show that the improved BPL decoding scheme can provide higher throughput and achieve similar decoding performance with the existing BPL decoding under the same simulation condition.
Owing to its high parallelism, belief propagation (BP) decoding is highly amenable to high-throughput implementations and thus represents a promising solution for meeting the ultra-high peak data rate of future communication systems. However, for polar codes, the error-correcting performance of BP decoding is far inferior to that of the widely used CRC-aided successive cancellation list (SCL) decoding algorithm. To close the performance gap to SCL, BP list (BPL) decoding expands the exploration of candidate codewords through multiple permuted factor graphs (PFGs). From an implementation perspective, designing a unified and flexible hardware architecture for BPL decoding that supports various PFGs and code configurations presents a big challenge. In this paper, we propose the first hardware implementation of a BPL decoder for polar codes and overcome the implementation challenge by applying a hardware-friendly algorithm that generates flexible permutations on-the-fly. First, we derive the graph selection gain and provide a sequential generation (SG) algorithm to obtain a near-optimal PFG set. We further prove that any permutation can be decomposed into a combination of multiple fixed routings, and we design a low-complexity permutation network to satisfy the decoding schedule. Our BPL decoder not only has a low decoding latency by executing the decoding and permutation generation in parallel, but also supports an arbitrary list size without any area overhead. Experimental results show that, for length-1024 polar codes with a code rate of one-half, our BPL decoder with 32 PFGs has a similar error-correcting performance to SCL with a list size of 4 and achieves a throughput of 25.63 Gbps and an area efficiency of 29.46 Gbps/mm2^{2}2 at SNR=4.0dB, which is 1.82×\times× and 4.33×\times× faster than the state-of-the-art BP flip and SCL decoders,~respectively
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).
Belief propagation (BP) decoding outputs soft information and can be naturally used in iterative receivers. BP list (BPL) decoding provides comparable error-correction performance to the successive cancellation list (SCL) decoding. In this paper, we firstly introduce an enhanced code construction scheme for BPL decoding to improve its error-correction capability. Then, a GPU-based BPL decoder with adoption of the new code construction is presented. Finally, the proposed BPL decoder is tested on NVIDIA RTX3070 and GTX1060. Experimental results show that the presented BPL decoder with early termination criterion achieves above 1 Gbps throughput on RTX3070 for the code (1024, 512) with 32 lists under good channel conditions.