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

Conference on Design and Architectures for Signal and Image Processing

Hardware implementation of a soft cancellation decoder for polar codes

Guillaume Berhault, Camille Leroux, Christophe Jégo, Dominique Dallet

Published Sep 1, 2015• 15 citations
Publisher

Abstract

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.

DOI
10.1109/dasip.2015.7367252

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

FPGA Implementation of Recurrent Neural Network-Based Polar Decoder

Ziad Ibrahim, Yasmine A. H. Fahmy

Polar codes are part of the 5G technology enablers as they nearly achieve memoryless channels capacity. Recently, many researchers explored Machine-learning (ML) techniques to increase the effectiveness of polar codes decoders. Recurrent Neural Network Belief Propagation decoders (RNN-BP) demonstrated superior efficiency in fewer cycles than standard Polar decoders, as traditional Belief propagation decoders performed poorly throughout a limited number of iterations. In this paper, we present the first implementation of the RNN-BP on Field Programmable Gate Arrays (FPGA). Two implementations are presented in this paper. The first one uses a single processing unit, and the second one is enhanced by multiple processing units with a pipeline register. The multiple processing units’ design of RNN-BP shows much higher throughput which is 17x of belief propagation decoder implementation and 3x of the Soft-output CANcellation (SCAN) decoder implementation. We also achieved better BER than the two mentioned implementations 7. 08x than the original BP and 4. 5x better than the SCAN implementation. The combined memory and registers resource consumption in our design is less than the compared two implementations while consuming a larger number of look-up tables (LUTs).

International Japan-Africa Conference on Electronics, Communications, and Computations (JAC-ECC)•Dec 19, 2022•0 citations

A high throughput belief propagation decoder architecture for polar codes

Jun Ting Lin, Jin Sha, Li Li +3 more

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.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2016•5 citations

Efficient Soft-Cancellation Flip Decoding of Polar Codes

Yangcan Zhou, Zijian Qin, Zhongfeng Wang

The soft-cancellation (SCAN) is a low-complexity soft-output decoding algorithm of polar codes. However, the performance of the SCAN is inferior for short to medium codes. To address this issue, an efficient SCAN Flip decoding algorithm devoted to correct the first erroneous bit in the SCAN is proposed in this letter. The minimum dissemination characteristic of the SCAN decoding is found and analyzed. Besides, an on-the-fly critical set method is proposed to narrow down the range of flip locations. Moreover, before each flipping trial, cleaning of some internal messages is performed to avoid the negative impact of previous wrong message propagation. Numerical results show that the proposed algorithm has better error-correction performance and lower average number of iterations than state-of-the-art SCAN Flip decoding algorithms.

IEEE Communications Letters•Jun 27, 2024•1 citation

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

Improved Soft Cancellation Decoding of Polar Codes

Mingyue You, Zhifeng Ma

The soft cancellation decoding of polar codes achieves a better performance than the belief propagation decoding with lower computational time and space complexities. However, because the soft cancellation decoding is based on the successive cancellation decoding, the decoding efficiency and performance with finite-length blocks can be further improved. Exploiting the idea of the successive cancellation list decoding, the soft cancellation decoding can be improved in two aspects: one is by adding branch decoding to the error-prone information bits to increase the accuracy of the soft information, and the other is through using partial iterative decoding to reduce the time and computational complexities. Compared with the original method, the improved soft cancellation decoding makes progress in the error correction performance, increasing the decoding efficiency and reducing the computational complexity, at the cost of a small increase of space complexity.

Journal of Beijing Institute of Technology•Sep 30, 2020•0 citations
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.
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 are part of the 5G technology enablers as they nearly achieve memoryless channels capacity. Recently, many researchers explored Machine-learning (ML) techniques to increase the effectiveness of polar codes decoders. Recurrent Neural Network Belief Propagation decoders (RNN-BP) demonstrated superior efficiency in fewer cycles than standard Polar decoders, as traditional Belief propagation decoders performed poorly throughout a limited number of iterations. In this paper, we present the first implementation of the RNN-BP on Field Programmable Gate Arrays (FPGA). Two implementations are presented in this paper. The first one uses a single processing unit, and the second one is enhanced by multiple processing units with a pipeline register. The multiple processing units’ design of RNN-BP shows much higher throughput which is 17x of belief propagation decoder implementation and 3x of the Soft-output CANcellation (SCAN) decoder implementation. We also achieved better BER than the two mentioned implementations 7. 08x than the original BP and 4. 5x better than the SCAN implementation. The combined memory and registers resource consumption in our design is less than the compared two implementations while consuming a larger number of look-up tables (LUTs).
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 soft-cancellation (SCAN) is a low-complexity soft-output decoding algorithm of polar codes. However, the performance of the SCAN is inferior for short to medium codes. To address this issue, an efficient SCAN Flip decoding algorithm devoted to correct the first erroneous bit in the SCAN is proposed in this letter. The minimum dissemination characteristic of the SCAN decoding is found and analyzed. Besides, an on-the-fly critical set method is proposed to narrow down the range of flip locations. Moreover, before each flipping trial, cleaning of some internal messages is performed to avoid the negative impact of previous wrong message propagation. Numerical results show that the proposed algorithm has better error-correction performance and lower average number of iterations than state-of-the-art SCAN Flip decoding algorithms.
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.
The soft cancellation decoding of polar codes achieves a better performance than the belief propagation decoding with lower computational time and space complexities. However, because the soft cancellation decoding is based on the successive cancellation decoding, the decoding efficiency and performance with finite-length blocks can be further improved. Exploiting the idea of the successive cancellation list decoding, the soft cancellation decoding can be improved in two aspects: one is by adding branch decoding to the error-prone information bits to increase the accuracy of the soft information, and the other is through using partial iterative decoding to reduce the time and computational complexities. Compared with the original method, the improved soft cancellation decoding makes progress in the error correction performance, increasing the decoding efficiency and reducing the computational complexity, at the cost of a small increase of space complexity.