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

Asia-Pacific Conference on Communications Technology and Computer Science (ACCTCS)

An Improved Min-Sum Polar Code Decoding Algorithm

Mingyuan Fang

Published Feb 1, 2023• 0 citations
Publisher

Abstract

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.

DOI
10.1109/acctcs58815.2023.00124

Related papers

Reduced-Complexity Belief Propagation Decoding for Polar Codes

Jung-Hyun Kim, Inseon Kim, Gangsan Kim +1 more

We propose three effective approximate belief propagation decoders for polar codes using Maclaurin's series, piecewise linear function, and stepwise linear function. The proposed decoders have the better performance than that of existing approximate belief propagation polar decoders, min-sum decoder and normalized min-sum decoder, and almost the same performance with that of original belief propagation decoder. Moreover, the proposed decoders achieve such performance without any optimization process according to the code parameters and channel condition unlike normalized min-sum decoder, offset min-sum decoder, and their variants.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2017•2 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, 2016•8 citations

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 Systems•May 20, 2020•43 citations

Improved Recurrent Neural Network based BP Decoding Algorithm for Polar Codes

Xue-lu DENG, Da-qin PENG

In recent years, the emerging Deep Learning (DL) technology has made progress in the field of decoding. Current polar code neural network decoder has faster convergence speed and better Bit Error Rate (BER) performance than Belief Propagation (BP) decoding. However, it still has the problem of high computational complexity. Therefore, in order to improve this problem, this paper adopts the idea of improving information update in the iterative process, and proposes a Recurrent Neural Network (RNN) Offset Min-Sum (OMS) BP decoding algorithm that improves Left information update (RNN-OMSBP-L) . The simulation results show that, compared with the Deep Neural Network (DNN) BP(DNN-BP) decoding algorithm, this algorithm replaces all multiplications with a cost of 6.25% addition. Compared with the current optimized RNN OMS and approximate BP(RNN-OMS-BP) decoding algorithm, the decoding algorithm in this paper uses improved information to reduce 25% of the addition operations with almost no loss in BER performance, while saving part of the storage space overhead. Under the same BER performance, it reduces the number of iterations by 37.5%.

•Aug 1, 2022•0 citations

A Improved Min-Sum Algorithm for LDPC Codes

Zhang Rong-rong

Among the decoding algorithm for low-density parity-check(LDPC) code,belief propagation(BP) algorithm has good performance but high complexity,while min-sum algorithm has simple implementation complexity but worse performance.Considering the trade-off between performance and complexity,the relationship between the value of overestimate under min-sum algorithm and the input information is analyzed,and an improved min-sum algorithm is proposed.Simulation results show that the improved min-sum algorithm remains similar performance with the traditional BP algorithm,but has less complexity.

Microcomputer Information•Jan 1, 2010•0 citations

Different perspective and approach to implement adaptive normalised belief propagation-based decoding for low-density parity check codes

Panupat Poocharoen, Mario Edgardo Magana

In this study, the authors propose an improved version of the min-sum algorithm for low-density parity check code decoding, which the authors call ‘adaptive normalised BP-based’ algorithm. Their decoder provides a compromise solution between belief propagation and the min-sum algorithms by adding an exponent offset to each variable node's intrinsic information in the check node update equation. The extrinsic information from the min-sum decoder is then adjusted by applying a negative power of the two scale factor, which can be easily implemented by right shifting the min-sum extrinsic information. The difference between their approach and other adaptive normalised min-sum decoders is that the authors select the normalisation scale factor using a clear analytical approach based on the underlying principles. The simulation results show that the proposed decoder outperforms the min-sum decoder and performs very close to the BP decoder with lower complexity.

IET Communications•Oct 16, 2012•5 citations
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.
We propose three effective approximate belief propagation decoders for polar codes using Maclaurin's series, piecewise linear function, and stepwise linear function. The proposed decoders have the better performance than that of existing approximate belief propagation polar decoders, min-sum decoder and normalized min-sum decoder, and almost the same performance with that of original belief propagation decoder. Moreover, the proposed decoders achieve such performance without any optimization process according to the code parameters and channel condition unlike normalized min-sum decoder, offset min-sum decoder, and their variants.
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.
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.
In recent years, the emerging Deep Learning (DL) technology has made progress in the field of decoding. Current polar code neural network decoder has faster convergence speed and better Bit Error Rate (BER) performance than Belief Propagation (BP) decoding. However, it still has the problem of high computational complexity. Therefore, in order to improve this problem, this paper adopts the idea of improving information update in the iterative process, and proposes a Recurrent Neural Network (RNN) Offset Min-Sum (OMS) BP decoding algorithm that improves Left information update (RNN-OMSBP-L) . The simulation results show that, compared with the Deep Neural Network (DNN) BP(DNN-BP) decoding algorithm, this algorithm replaces all multiplications with a cost of 6.25% addition. Compared with the current optimized RNN OMS and approximate BP(RNN-OMS-BP) decoding algorithm, the decoding algorithm in this paper uses improved information to reduce 25% of the addition operations with almost no loss in BER performance, while saving part of the storage space overhead. Under the same BER performance, it reduces the number of iterations by 37.5%.
Among the decoding algorithm for low-density parity-check(LDPC) code,belief propagation(BP) algorithm has good performance but high complexity,while min-sum algorithm has simple implementation complexity but worse performance.Considering the trade-off between performance and complexity,the relationship between the value of overestimate under min-sum algorithm and the input information is analyzed,and an improved min-sum algorithm is proposed.Simulation results show that the improved min-sum algorithm remains similar performance with the traditional BP algorithm,but has less complexity.
In this study, the authors propose an improved version of the min-sum algorithm for low-density parity check code decoding, which the authors call ‘adaptive normalised BP-based’ algorithm. Their decoder provides a compromise solution between belief propagation and the min-sum algorithms by adding an exponent offset to each variable node's intrinsic information in the check node update equation. The extrinsic information from the min-sum decoder is then adjusted by applying a negative power of the two scale factor, which can be easily implemented by right shifting the min-sum extrinsic information. The difference between their approach and other adaptive normalised min-sum decoders is that the authors select the normalisation scale factor using a clear analytical approach based on the underlying principles. The simulation results show that the proposed decoder outperforms the min-sum decoder and performs very close to the BP decoder with lower complexity.