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 Circuits and Systems proceedings

A high throughput belief propagation decoder architecture for polar codes

Jun Ting Lin, Jin Sha, Li Li, Chenrong Xiong, Zhiyuan Yan, Zhongfeng Wang

Published May 1, 2016• 5 citations
Publisher

Abstract

The belief propagation (BP) decoding algorithm not only is an alternative to the successive cancelation (SC) decoders of polar codes, but also provides soft outputs that are necessary for joint detection and decoding. The BP decoders with the flooding schedule achieve high throughput with excessive hardware cost especially when the block length is large. The soft-cancelation (SCAN) decoders for polar codes have reduced memory complexity compared to the BP decoders based on the flooding schedule. The simplified SC aided reduced complexity soft-cancelation (S-RCSC) decoders further reduce the computational and memory complexity of the SCAN decoders at the cost of negligible error performance degradation. Both the SCAN and S-RCSC decoders have limited throughput due to their serial decoding schedules. In this paper, we first propose an improved S-RCSC (IS-RCSC) decoding algorithm and then present a high throughput decoder architecture based on our IS-RCSC algorithm. Our IS-RCSC decoding algorithm performs the message passing on a binary tree representation of a polar code. Compared to the S-RCSC decoding algorithm, our IS-RCSC decoding algorithm accelerates the computing of the returned soft messages when certain types of nodes are activated. The corresponding hardware architecture of our IS-RCSC decoder is also proposed. In terms of area efficiency, the hardware implementation results demonstrate that our IS-RCSC decoders are 19% to 43% better than decoders in the literature.

DOI
10.1109/iscas.2016.7527193

Related papers

Efficient Soft Cancelation Decoder Architectures for Polar Codes

Jun Ting Lin, Zhiyuan Yan, Zhongfeng Wang

The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Jul 12, 2016•12 citations

Hardware implementation of a soft cancellation decoder for polar codes

Guillaume Berhault, Camille Leroux, Christophe Jégo +1 more

Polar Codes can provably achieve the capacity of discrete memoryless channels. In order to make practical, it is necessary to propose efficient hardware decoder architectures. In this paper, the first hardware decoder architecture implementing the Soft-output CANcellation (SCAN) decoding algorithm, is presented. This decoder was implemented on Field Programmable Gate Array (FPGA) devices. The proposed architecture is parametrizable for any number of iterations without adding hardware complexity. The SCAN decoder architecture is compared to another soft-output decoder that implements a Belief Propagation (BP) algorithm. The SCAN decoder can reach a higher throughput than a BP decoder, with a lower memory footprint. Moreover, only one iteration with the SCAN algorithm leads to better decoding performance than 50 iterations of the BP algorithm.

Conference on Design and Architectures for Signal and Image Processing•Sep 1, 2015•13 citations

Iterative Decoding Based on Concatenated Belief Propagation for CRC-Aided Polar Codes

Satoshi Tajima, Takumi Takahashi, Shinsuke Ibi +1 more

This paper proposes a novel iterative decoder based on concatenated belief propagation (BP) for CRC-aided polar codes. Compared to the conventional BP-based decoders for polar codes, soft cancellation (SCAN) decoder can generate a log likelihood ratio (LLR) of coded bit with lower computational complexity without sacrificing the detection capability. Unfortunately, its performance is not as good as that of CRC-aided successive cancellation list decoder (SCLD) although SCAN decoder has advantage of hardware implementation. To compensate the performance gap, we exploit CRC structure for not only error detection but also error correction with the assistance of its error correction capability at a short code length by exchanging LLRs between SCAN decoder and BP decoder on the basis of CRC. Moreover, the sub-optimal criterion for selecting a parity check matrix of CRC for BP decoder is proposed. Finally, computer simulations are conducted to confirm the validity of our proposed method. The proposed method can obtain the gain of about 0.6 dB at BER=10-3compared to the native SCAN decoder without requiring huge memory size as in SCLD.

Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)•Nov 1, 2018•7 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

A low-complexity soft-output decoder for polar codes

Ubaid U. Fayyaz, John R. Barry

A widely used soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper we propose a low-complexity alternative for soft-output decoding of polar codes that offers comparable performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is about 5% of the total complexity of the belief propagation decoder for the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.

Globecom•Dec 1, 2013•6 citations

Low-Complexity Soft-Output Decoding of Polar Codes

Ubaid U. Fayyaz, John R. Barry

The state-of-the-art soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper, we propose a low-complexity alternative for soft-output decoding of polar codes that offers better performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is only 4% of the total complexity of the belief propagation decoder for a rate one-half polar code of dimension 4096 in the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.

IEEE Journal on Selected Areas in Communications•Apr 24, 2014•166 citations
The belief propagation (BP) decoding algorithm not only is an alternative to the successive cancelation (SC) decoders of polar codes, but also provides soft outputs that are necessary for joint detection and decoding. The BP decoders with the flooding schedule achieve high throughput with excessive hardware cost especially when the block length is large. The soft-cancelation (SCAN) decoders for polar codes have reduced memory complexity compared to the BP decoders based on the flooding schedule. The simplified SC aided reduced complexity soft-cancelation (S-RCSC) decoders further reduce the computational and memory complexity of the SCAN decoders at the cost of negligible error performance degradation. Both the SCAN and S-RCSC decoders have limited throughput due to their serial decoding schedules. In this paper, we first propose an improved S-RCSC (IS-RCSC) decoding algorithm and then present a high throughput decoder architecture based on our IS-RCSC algorithm. Our IS-RCSC decoding algorithm performs the message passing on a binary tree representation of a polar code. Compared to the S-RCSC decoding algorithm, our IS-RCSC decoding algorithm accelerates the computing of the returned soft messages when certain types of nodes are activated. The corresponding hardware architecture of our IS-RCSC decoder is also proposed. In terms of area efficiency, the hardware implementation results demonstrate that our IS-RCSC decoders are 19% to 43% better than decoders in the literature.
The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.
Polar Codes can provably achieve the capacity of discrete memoryless channels. In order to make practical, it is necessary to propose efficient hardware decoder architectures. In this paper, the first hardware decoder architecture implementing the Soft-output CANcellation (SCAN) decoding algorithm, is presented. This decoder was implemented on Field Programmable Gate Array (FPGA) devices. The proposed architecture is parametrizable for any number of iterations without adding hardware complexity. The SCAN decoder architecture is compared to another soft-output decoder that implements a Belief Propagation (BP) algorithm. The SCAN decoder can reach a higher throughput than a BP decoder, with a lower memory footprint. Moreover, only one iteration with the SCAN algorithm leads to better decoding performance than 50 iterations of the BP algorithm.
This paper proposes a novel iterative decoder based on concatenated belief propagation (BP) for CRC-aided polar codes. Compared to the conventional BP-based decoders for polar codes, soft cancellation (SCAN) decoder can generate a log likelihood ratio (LLR) of coded bit with lower computational complexity without sacrificing the detection capability. Unfortunately, its performance is not as good as that of CRC-aided successive cancellation list decoder (SCLD) although SCAN decoder has advantage of hardware implementation. To compensate the performance gap, we exploit CRC structure for not only error detection but also error correction with the assistance of its error correction capability at a short code length by exchanging LLRs between SCAN decoder and BP decoder on the basis of CRC. Moreover, the sub-optimal criterion for selecting a parity check matrix of CRC for BP decoder is proposed. Finally, computer simulations are conducted to confirm the validity of our proposed method. The proposed method can obtain the gain of about 0.6 dB at BER=10-3compared to the native SCAN decoder without requiring huge memory size as in SCLD.
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
A widely used soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper we propose a low-complexity alternative for soft-output decoding of polar codes that offers comparable performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is about 5% of the total complexity of the belief propagation decoder for the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.
The state-of-the-art soft-output decoder for polar codes is a message-passing algorithm based on belief propagation, which performs well at the cost of high processing and storage requirements. In this paper, we propose a low-complexity alternative for soft-output decoding of polar codes that offers better performance but with significantly reduced processing and storage requirements. In particular we show that the complexity of the proposed decoder is only 4% of the total complexity of the belief propagation decoder for a rate one-half polar code of dimension 4096 in the dicode channel, while achieving comparable error-rate performance. Furthermore, we show that the proposed decoder requires about 39% of the memory required by the belief propagation decoder for a block length of 32768.