International Conference on Information Technology in Medicine and Education

Look-Up-Table Decoding and Architecture Optimization for Scale-Min-Sum Polar Decoders

Xiumin Wang, Rui Gu, Jun Li, Haiyan Cao, Zhengquan Li

Published Oct 1, 2018• 0 citations

Abstract

As to realize believe propagation (BP) for polar decoding, the scaled min-sum (SMS) algorithm is widely used in hardware realization for polar decoders. However, the decoding performance of SMS algorithm is still not good as the length of polar codes increase, and its computing architecture,which called processing elements (PE) needs to be further optimized due to its long critical path. In this paper, referring to the method used in LDPC/Turbo decoding, a look-up-table (LUT) algorithm and its modified version called LUT-SMS are proposed for polar decoding. The simulation result shows that, compared with the SMS algorithm, the proposed LUT-SMS algorithm can lead to 0.3 dB extra decoding gain when the code length up to 2048. For a different trade-off, a new SMS computing architecture which has shorter computing path is proposed to solve the long delay of the polar decoders. The hardware implementation result shows that, the optimized SMS computing architecture can also achieve more than 32% increase in throughput for the case of (256,128) polar decoder without much extra hardware consumption. As a result, both these two optimization schemes have good promotion for polar decoding.

DOI: 10.1109/itme.2018.00189

Related papers

Deep Learning-Aided Belief Propagation Decoder for Polar Codes

Weihong Xu, Xiaosi Tan, Yair Be'ery +4 more

This paper presents deep learning (DL) methods to optimize polar belief propagation (BP) decoding and concatenated LDPC-polar codes. First, two-dimensional offset Min-Sum (2-D OMS) decoding is proposed to improve the error-correction performance of existing normalized Min-Sum (NMS) decoding. Two optimization methods used in DL, namely back-propagation and stochastic gradient descent, are exploited to derive the parameters of proposed algorithms. Numerical results demonstrate that there is no performance gap between 2-D OMS and exact BP on various code lengths. Then the concatenated OMS algorithms with low complexity are presented for concatenated LDPC-polar codes. As a result, the optimized concatenated OMS decoding yields error-correction performance with CRC-aided successive cancellation list (CA-SCL) decoder of list size 2 on length-1024 polar codes. In addition, the efficient hardware architectures of scalable polar OMS decoder are described and the proposed decoder is reconfigurable to support three code lengths (N = 256, 512, 1024) and two decoding algorithms (2-D OMS and concatenated OMS). The polar OMS decoder implemented on 65 nm CMOS technology achieves a maximum coded throughput of 5.4 Gb/s at Eb/N0= 4 dB for code length 1024 and 7.5 Gb/s at Eb/N0= 3.5 dB for code length 256, which are comparable to the state-of-the-art polar BP decoders. Moreover, a 5.1 Gb/s throughput at Eb/N0= 4 dB is achieved under concatenated OMS decoding mode for code length 1024 with a latency of 200 ns, which is superior to existing CA-SCL decoders that have similar error-correction performance.

IEEE Journal on Emerging and Selected Topics in Circuits and SystemsMay 20, 202043 citations

An Improved Min-Sum Polar Code Decoding Algorithm

Mingyuan Fang

In 2009, the presentation of polar code, the first theory to approach the Shannon limit of communication channel coding schemes. Thus, academics and business have focused on Polar codes. Research and worldwide standards have been offered one after another, establishing the groundwork for its real-world use.The paper proposes a min-sum decoding technique for enhanced Polar codes and revises the node update formula in the min-sum decoding algorithm by using the piecewise linear function to approximate the function ln cosh(x) in the belief propagation decoding algorithm. Compared to the min-sum decoding algorithm, the enhanced approach improves decoding performance while somewhat increasing complexity. Compared to the belief propagation decoding algorithm, this approach decreases computational complexity significantly and is simpler to implement in hardware. Based on the min-sum method and the belief propagation algorithm, this approach is offered as a balance between complexity and performance. The simulation results demonstrate that the enhanced min-sum decoding algorithm performs similarly to its predecessor. The performance of the degree propagation decoding method is almost identical to that of the min-sum decoding technique, which is superior.

Asia-Pacific Conference on Communications Technology and Computer Science (ACCTCS)Feb 1, 20230 citations

Improved Polar Decoder Based on Modular Neural Network Structure

Yuhan Yang, Jianquan Yang

With the wide application of Deep Neural Network (DNN) in the field of communication, this technique has also been applied in the coding and decoding technology, but there are few neural network structures with good performance in the decoder. This paper proposes a new polar code decoding network structure, which uses a modular network structure to train the empirical parameters in the iterative belief propagation (BP) algorithm model. The experiment part uses the new structure to implement scaling min-sum (SMS) algorithm and offset min-sum (OMS) algorithm. Through comparing the performance of the above algorithms with the traditional structure, it is found that the new structure has the advantages of better bit error rate (BER) and faster convergence performance compared with the traditional network structure.

Apr 1, 20230 citations

Improved LDPC decoding algorithms based on min-sum algorithm

Y.V. A. C. Kumara, Chandika Bandara Wavegedara

Low-Density Parity check (LDPC) codes offer high-performance error correction near the Shannon limit which employs large code lengths and some iterations in the decoding process. The conventional decoding algorithm of LDPC is the Log Likelihood Ratio based Belief Propagation (LLR BP) which is also known as the `Sum-Product algorithm' which gives the best decoding performance and requires the most computational complexity and implementations with increased hardware complexity. Another simpler variant of this algorithm is used which is known as `min-sum algorithm' which reduces computational complexity as well as hardware complexity but with reduced accuracy. This paper analyzes the reason min-sum algorithm is more prone to errors when compared to the sum-product algorithm, and puts forward two improved algorithms which improve the performance of the min-sum algorithm with comparable algorithmic complexity.

Moratuwa Engineering Research Conference (MERCon)Apr 1, 20168 citations

A Non-uniform Quantization-based Hardware Architecture for BP Decoding of Polar Codes

Xinyi Gu, Mohammad Rowshan, Yixuan Xie +1 more

Belief propagation (BP) decoding of polar codes benefits from the high parallelism in hardware implementation and consequently provides high throughput compared to successive cancellation-based decoding algorithms. As the evolved log-likelihood ratios (LLRs) in the decoding process have a wide dynamic range, the quantization error can degrade the error correction performance of the BP decoder. To reduce the quantization error in a uniform quantization scheme, we may need to use more bits for each LLR value which is not desirable due to the required memory space. In this paper, we design an efficient hardware architecture for non-uniformly quantized LLR messages in BP decoding where the arithmetic operations on logarithmically compressed messages are replaced with the mapping to precomputed results in lookup tables. By employing 5-bit non-uniform quantization, the designed BP decoder architecture reduces the required memory space by 37.5 percent compared to 8-bit uniform quantization while additionally improving the block error rate (BLER) by more than 0.1 dB in high SNR regimes. Compared to uniform quantization, the BLER improvement of the designed architecture is up to 0.4 dB when both quantization schemes use 5 bits for LLRs.

International Symposium on Communications and Information TechnologiesOct 16, 20233 citations

Low Complexity Implementations of Sum-Product Algorithm for Decoding Low-Density Parity-Check Codes

Daesun Oh, Keshab K. Parhi

In this paper, we propose low complexity implementations of sum-product algorithm (SPA) for decoding low-density parity-check (LDPC) codes. The finite precision implementations for SPA have an important tradeoff between the decoding performance and hardware complexity caused by two dominant area consuming factors. One is the memory for updated messages storage and the other is the look-up table (LUT) for implementation of nonlinear function Psi(x). The proposed two types of variable quantization schemes result in significant reductions of LUT sizes. Computer simulation results indicate that the performance losses of SPA with reduced LUT by proposed schemes are less than 0.05 dB compared to that of SPA with original LUT. Moreover, the proposed implementation offers a large reduction in the finite wordlength for storage of updated messages using a kind of compression technique without performance losses. As a result, using the proposed implementation based on variable quantization scheme and data compression technique, the novel proposed implementation for SPA decoder architecture offers significant reductions of 75% and 33% in hardware complexities of LUT and memories, respectively, without significant performance degradations over conventional uniform quantization scheme. Furthermore, since each LUT with variable (6:3) quantization scheme II has only 8 entries, its hardware implementation can be replaced with a small combination circuit instead of readonly-memory (ROM) for LUT

SiPS ... design and implementation - IEEE Workshop on Signal Processing SystemsOct 1, 200618 citations