Globecom

A low-complexity soft-output decoder for polar codes

Ubaid U. Fayyaz, John R. Barry

Published Dec 1, 2013• 6 citations

Abstract

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.

DOI: 10.1109/glocom.2013.6831481

Related papers

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 CommunicationsApr 24, 2014166 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 proceedingsMay 1, 20165 citations

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) SystemsJul 12, 201612 citations

Computational Complexity Reduced Belief Propagation Algorithm for Polar Code Decoders

Arvid B. van den Brink, Marco J.G. Bekooij

The belief propagation algorithm is desirable for a polar code based decoder, because of the potentially low latency and the ability of integration in digital signal processing units or other multi-core processor systems to parallelize the computations. Although belief propagation polar code decoder algorithms have the ability for a highly parallelized imple-mentation, the algorithms require many iterations to achieve a comparable frame error rate and bit error rate with respect to a successive cancellation polar code algorithm. The iterative nature of the belief propagation algorithms also result in a higher computational complexity, i.e. O(IN(2log_{2} N-1)) compared to the computational complexity O(Nlog_{2}N) of the successive cancellation decoder algorithm. In this paper we propose several simplifications for a simplified belief propagation algorithm for polar code decoders, where the arithmetic complexity of the nodes is reduced. The proposed belief propagation algorithm shows preliminary results of a net reduction of the arithmetic complexity of ≈ 13%. This reduction is a result of the reduced number of arithmetic operations, i.e., additions, compares, and multiplications, without a lost in error-correcting performance.

Feb 3, 20210 citations

Simplified Early Stopping Criterion for Polar Codes

Jianming Cui, Jun Li, Yanfei Dong +2 more

Belief propagation (BP) algorithm of polar codes suffers from very high computational complexity when the iteration number becomes larger. In this paper, an early stopping criterion is proposed to avoid unnecessary iterations efficiently. The proposed only needs to detect whether the proportion of unchanged soft-output messages in a detection space exceeds a threshold. The proposed iteration can achieve a desired trade-off between complexity and decoding performance. Simulation results have shown that when the maximum iteration number is 40, the flooding BP (FO-BP) decoder with the proposed criterion can reduce 82.17% of iterations at 3.5dB compared with the FO-BP decoder without early stopping criterion. The proposed criterion costs Nl32 additions and Nl32 comparisons, where N indicates the code length, which effectively reduces the computational complexity.

IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC)Sep 1, 20184 citations

Enhancing Belief Propagation Decoding of Polar Codes: A Reinforcement Learning Approach

Mohsen Moradi, Salman Habib, David G. M. Mitchell

Short block-length polar-like codes showcase exceptional error correction performance (ECP) using sequential decoding or successive cancellation list decoding with a large list size. However, achieving a high level of reliability with these methods involves high-latency decoding. To meet the growing demand for low-latency communication with acceptable complexity, belief propagation (BP) decoding emerges as an attractive option, although its ECP is known to fall short of those high-latency alternatives. In this paper, we propose an enhanced BP decoding approach for polar codes, leveraging reinforcement learning (RL) to optimize the message-passing schedule. Moreover, we investigate the design of the polar code rate profile and corresponding Tanner graph representation to enhance the benefits of RL. Numerical results demonstrate a performance gain of more than 1 dB for polar codes with a length of 128 and a rate of 0.5 compared to conventional BP decoding alone at highEb/N0values, demonstrating the promise of the proposed approach.

IEEE Communications LettersApr 9, 20253 citations