Hardware Decoders for Polar Codes: An Overview <s> B. Low-Complexity BP Decoders <s> 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. <s> BIB001 </s> Hardware Decoders for Polar Codes: An Overview <s> B. Low-Complexity BP Decoders <s> Capacity-achieving polar codes have gained significant attention in recent years. In general, polar codes can be decoded by either successive cancellation (SC) or the belief propagation (BP) algorithm. However, unlike SC decoders, performance optimizations for BP decoders have not been fully explored yet. In this paper, we explore novel early stopping criteria for polar BP decoding to significantly reduce energy dissipation and decoding latency. First, we propose two detection-type novel early stopping criteria for detecting valid outputs. For polar (1024, 512) codes, these two stopping criteria can reduce the number of iterations by up to 42.5% at 3.5 dB. Then, we propose a novel channel condition estimation approach, which can help select different stopping criteria in different SNR regions. Furthermore, the hardware architectures of polar BP decoders with the proposed stopping criteria are presented and developed. Synthesis results show that with the use of the proposed stopping criteria, the energy dissipation, and average latency of polar (1024, 512) BP decoder can be reduced by ${\hbox{10}}\% \!\sim\! {\hbox{30}}\%$ with ${\hbox{2}}\% \!\sim\! {\hbox{5}}\%$ hardware overhead, and average throughput can be increased by ${\hbox{20}}\% \!\sim\! {\hbox{55}}\%$ . <s> BIB002 </s> Hardware Decoders for Polar Codes: An Overview <s> B. Low-Complexity BP Decoders <s> Since its invention, polar code has received a lot of attention because of its capacity-achieving performance and low encoding and decoding complexity. Successive cancellation decoding (SCD) and belief propagation decoding (BPD) are two of the most popular approaches for decoding polar codes. SCD is able to achieve good error-correcting performance and is less computationally expensive as compared to BPD. However SCDs suffer from long latency and low throughput due to the serial nature of the successive cancellation algorithm. BPD is parallel in nature and hence is more attractive for high throughput applications. However since it is iterative in nature, the required latency and energy dissipation increases linearly with the number of iterations. In this work, we borrow the idea of SCD and propose a novel scheme based on sub-factor-graph freezing to reduce the average number of computations as well as the average number of iterations required by BPD, which directly translates into lower latency and energy dissipation. Simulation results show that the proposed scheme has no performance degradation and achieves significant reduction in computation complexity over the existing methods. <s> BIB003
In BIB001 , a low-complexity variant of the BP decoding algorithm called soft cancellation (SCAN) was proposed. Under that algorithm, soft messages propagate according to the schedule of SC decoding, resulting in an increased latency in O(N) clock cycles. However, the message propagation of SCAN was shown to be efficient and its overall complexity at low SNR regime was reduced by an order of magnitude compared to that of regular BP decoding. Similar to iterative decoders for LDPC or turbo codes, early stopping schemes can be used in BP decoders for polar codes. In BIB002 , threshold detections on messages are made after each iteration. When they satisfy certain criteria, decoding is stopped immediately. Furthermore, messages related to subgraphs are checked in BIB003 such that the operations in those sub-graphs can be stopped earlier. As a result, with the method of BIB002 , the average decoding complexity is reduced by around 30% with negligible performance degradation. The method in BIB003 further reduces the average complexity by 40%.