Polar codes are a class of codes discovered recently, which are proved to have capacity-achieving performance. The hardware implementations of successive cancellation (SC) decoding and List SC decoding are increasing dramatically now. However, throughput of these hardware structures remain to be improved on the one hand. On the other hand, stochastic computation is now wildly used because it uses simple structures to implement complicated mathematical operations and thus improves the throughput. This paper extends the application of stochastic computation to the decoding of polar codes. A family of SC decoders based on stochastic computation are proposed, including decoders based on bipolar stochastic computation(BSC-SC), low bits stochastic computation(LBSC-SC) and improved stochastic computation(ISC-SC). These methods have high generality and improve the throughput over SC decoder while having 0.5dB loss in decoding performance. The proposed 32-bit ISC-SC decoder has a better decoding accuracy and improves throughput over BSC-SC. It also reduces the hardware cost and latency compared to LBSC-SC decoder.
Polar codes are a class of codes discovered recently, which are proved to have capacity-achieving performance. The hardware implementations of successive cancellation (SC) decoding and List SC decoding are increasing dramatically now. However, throughput of these hardware structures remain to be improved on the one hand. On the other hand, stochastic computation is now wildly used because it uses simple structures to implement complicated mathematical operations and thus improves the throughput. This paper extends the application of stochastic computation to the decoding of polar codes. A family of SC decoders based on stochastic computation are proposed, including decoders based on bipolar stochastic computation(BSC-SC), low bits stochastic computation(LBSC-SC) and improved stochastic computation(ISC-SC). These methods have high generality and improve the throughput over SC decoder while having 0.5dB loss in decoding performance. The proposed 32-bit ISC-SC decoder has a better decoding accuracy and improves throughput over BSC-SC. It also reduces the hardware cost and latency compared to LBSC-SC decoder.
Representing continuous values by streams of random binary bits, stochastic decoding has shown advantages in both hardware efficiency and fault tolerance, therefore has been widely adopted by iterative decoding of error correction codes such as low-density parity-check (LDPC) codes and so on. Recently, polar codes, the first codes that can provably achieve the capacity of symmetric binary-input discrete memoryless channels (B-DMCs), have drawn a lot of attentions from both academia and industry. Although, polar codes with list successive cancellation (SC) decoding can outperform several best-known LDPC codes even within high error-rate regions, the linearly increasing hardware complexity makes its efficient implementation difficult. To this end, the stochastic list SC polar decoding algorithm is proposed in this paper to provide a good tradeoff between performance and complexity. In order to increase the decoding performance of stochastic list SC polar decoder, doubling probability approach is presented. The corresponding hardware architecture is also given. The approximate doubling approach is employed to facilitate the efficient implementation. Implementation results have shown that the proposed stochastic list SC polar decoder can achieve a good trade-off between performance and complexity.
Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from (3n-2) to (2n-2) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2Kbits simultaneously. This general approach, referred as 2K-bit reformulated SCL (2Kb-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2K-2-2 cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively.
Polar codes have emerged as the most favorable channel codes for their unique capacity-achieving property. To date, numerous approaches for efficient decoding of polar codes have been reported. However, these prior efforts focused on design of polar decoders via deterministic computation, while the behavior of stochastic polar decoder, which can have potential advantages such as low complexity and strong error-resilience, has not been studied in existing literatures. This paper, for the first time, investigates polar decoding using stochastic logic. Specifically, the commonly-used successive cancellation (SC) algorithm is reformulated into the stochastic form. Several methods that can potentially improve decoding performance are discussed and analyzed. Simulation results show that a stochastic SC decoder can achieve similar error-correcting performance as its deterministic counterpart. This work can pave the way for future hardware design of stochastic polar codes decoders.
Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency, and soft output with a high hardware cost. Stochastic computing, as a form of approximate computing, provides a potential low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. By utilizing the frozen bits of polar codes and stochastic computing, multiple novel optimization methods are presented to further speed up convergence and increase the hardware efficiency.
Polar codes have received recent attention due to their potential to be applied in advanced wireless communication protocols such as the fifth generation mobile communication system (5G). Among the existing decoding algorithms, Belief Propagation (BP) exhibits high-throughput, low-latency and soft output with a high hardware cost. A form of approximate computing called stochastic computing provides a low-cost implementation solution for the BP algorithm. However, existing stochastic BP decoders suffer from a relatively long decoding latency resulting in low hardware efficiency. In this paper, a novel bit-wise iterative stochastic decoding architecture for the BP algorithm is proposed to improve the throughput and hardware efficiency. Multiple methods at the algorithm and architecture levels are presented to further speed up convergence and hardware efficiency.
Multi-Parallel SCD Polar Coding BEC Polar codes are decoded using successive cancellation (SC) algorithm where likelihood ratios (LRs) for data bits are calculated in a sequential manner, and decisions are made using the calculated LRs.During the decoding of an information bit, the decision results for the predecessor bits are used, and a wrongly decided predecessor bit has negative effect on the accurate calculation of the LR for the information bit being decoded.In SC algorithm, when LR=1, the information bit is decoded as u _i=0, however, such a decision has 50% of chance of being correct.In this paper, we propose improved polar decoders utilizing a number of SC decoders.We consider the case of LR=1, and propose polar decoder structures for the more accurate calculation of the LRs of the successor bits.