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

Modelirovanie, optimizaciâ i informacionnye tehnologii.

Development of adaptive exponential min sum decoding algorithm

Wenbin Zhang, M. Ibrahem, V.M. Saklakov

Published Oct 8, 2024• 0 citations
Publisher

Abstract

This paper presents an optimized min sum (MS) decoding algorithm with low complexity and high decoding performance for LDPC short codes. The MS algorithm has low computational complexity and is simple to deploy. The MS decoding algorithm, while demonstrating a performance gap compared to the belief propagation (BP) and likelihood ratio BP (LLR-BP) decoding algorithms, shows significant potential for optimization. To improve the decoding performance of traditional MS algorithm, secondary external information is introduced into the control node (CNs) update operations of MS algorithm and optimized as adaptive exponential correction factor (AECF). The optimized MS algorithm is named as adaptive exponential exponential MS decoding algorithm (AEMS). The decoding efficiency of the AEMS algorithm for regular, irregular and LDPC codes of the Consultative Committee on Space Data Systems (CCSDS) was extensively tested, then the complexity of the AEMS algorithm was analyzed and compared with other decoding algorithms. The results show that the AEMS algorithm outperforms the offset MS (OMS) and normalized MS (NMS) algorithms in decoding performance, and outperforms the BP algorithm as the signal-to-noise ratio (SNR) gradually increases. В статье представлен оптимизированный алгоритм декодирования минимальной суммы (MS) с низкой сложностью и высокой производительностью декодирования для коротких кодов LDPC. Алгоритм MS имеет низкую вычислительную сложность и прост в развертывании. По сравнению с алгоритмом декодирования распространения убеждения (BP) и отношения правдоподобия BP (LLR-BP) он показывает разрыв в производительности декодирования, но алгоритм декодирования MS имеет высокий потенциал оптимизации. Для улучшения производительности декодирования традиционного алгоритма MS в операции обновления контрольных узлов (CN) алгоритма MS вводится вторичная внешняя информация и оптимизируется как адаптивный экспоненциальный поправочный коэффициент (AECF). Оптимизированный алгоритм MS назван адаптивным экспоненциальным алгоритмом декодирования MS (AEMS). Эффективность декодирования алгоритма AEMS для обычных, нерегулярных и LDPC-кодов консультативного комитета по системам космических данных (CCSDS) была всесторонне протестирована, затем был проведен анализ и сравнение сложности алгоритма AEMS с другими алгоритмами декодирования. Результаты показывают, что алгоритм AEMS превосходит алгоритмы смещенного MS (OMS) и нормализованного MS (NMS) по производительности декодирования, а также превосходит алгоритм BP по мере постепенного увеличения отношения сигнал/шум (SNR).

DOI
10.26102/2310-6018/2024.47.4.019

Related papers

An Adaptive Exponential Min Sum Decoding Algorithm

Weijia Zhang, Dushantha Nalin K. Jayakody

The belief propagation (BP) algorithm for low density parity check (LDPC) codes has proven to have excellent performance and is close to the Shannon limit. However, the high computational complexity is not conducive to realistic use. Although the min sum algorithm (MSA) improves the computational convenience and applicability. It also weakens its decoding capability. In order to improve the decoding performance of MSA and exploit the potential, this paper propose an adaptive exponential correction factor. This can improve the decoding performance of MSA. Adaptive exponential min sum algorithm (AEMSA) demonstrate a noticeable improvement over the normalized min sum algorithm (NMSA) and the BP algorithm in high signal to noise ratio (SNR). AEMSA is also a simple, efficient, low power consuming and highly potential decoding algorithm that can be applied in hardware implementations.

Conference on Cloud and Internet of Things (CIoT)•Mar 20, 2023•3 citations

IMPROVED MIN-SUM DECODING ALGORITHM FOR IRREGULAR LDPC CODES

А В Башкиров, Свиридова Ирина Владимировна, Т.Д. Ижокина +3 more

Aналитический подход к определению оптимальной функции постобработки для минимальной операции в алгоритме MIN-SUM, ранее полученный для обычных кодов проверки на четность с низкой плотностью (LDPC-коды), распространяется на нерегулярные коды LDPC. Оптимальное выражение постобработки для нестандартного случая варьируется от одного контрольного узла к другому, а также от одной итерации к следующей. Для практического использования необходимо аппроксимировать эту оптимальную функцию. В отличие от обычного случая, когда можно было бы использовать уникальную функцию постобработки на протяжении всего процесса декодирования без потери производительности битовых ошибок, для нерегулярных кодов критически важно варьировать постобработку от одной итерации к следующей, чтобы добиться хорошей производительности. С использованием этого подхода было выявлено, что качество битовых ошибок от алгоритма распространения доверия соответствует улучшению на 1 дБ по сравнению с MIN-SUM алгоритмом без постобработки. Сначала будет представлен обзор подхода и представлена аналитическая основа для оптимальной постобработки. Далее будет представлена оптимальная функция постобработки для нерегулярных кодов и обсуждены возможные упрощения. И наконец, показаны результаты моделирования и преимущества аппроксимации We extended an analytical approach to determining the optimal post-processing function for the minimum operation in the MIN-SUM algorithm, previously obtained for conventional low density parity check codes (LDPC codes), to irregular LDPC codes. The optimal post-processing expression for the non-standard case varies from one control node to another, as well as from one iteration to the next. For practical use, it is necessary to approximate this optimal function. Unlike the usual case where one could use a unique post-processing function throughout the entire decoding process without sacrificing bit code performance, it is critical for irregular codes to distinguish post-processing from one iteration to the next in order to achieve good performance. Using this approach, we found that the quality of bit errors from the trust algorithm corresponds to an improvement of 1 level compared to the MIN-SUM algorithm without post-processing. First, we provide an overview and analytical framework for optimal post-processing. Then, we present the optimal post-processing function for irregular codes and discuss possible simplifications. Finally, we show the simulation results and the benefits of the approximation

Вестник Воронежского государственного технического университета•Nov 19, 2021•0 citations

Min-Sum decoding of irregular LDPC codes with adaptive scaling based on mutual information

Florence Alberge

Min-Sum decoding (MS) is an alternative to belief propagation decoding with substantially lower complexity. MS often results in an overestimation of the log likelihood ratio (LLR) in particular in the early stage of the iterative process. A linear post-processing is usually performed as a compensation. With regular low density parity check codes (LDPC), a fixed scaling of the LLR yields sufficiently good results. In contrast, adaptive strategies are mandatory with irregular codes. It is well known that the scaling factor is an increasing function of the reliability of the LLR. In most of the publications, the scaling factor is envisioned as a function of both the iteration number and the signal-to-noise ratio. It is proposed here to use the mutual information between extrinsics as a measure of the reliability of the LLR. A practical implementation is derived with reasonable complexity. Compared to the literature, the proposed method yields slightly better results in terms of BER and a significant reduction in the number of iterations.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2016•8 citations

Adaptive-Normalized/Offset Min-Sum Algorithm

Xiaofu Wu, Yue Song, Ming Jiang +1 more

An adaptive-normalized/offset min-sum (AN-/AO-MS) algorithm for decoding low-density parity-check (LDPC) codes is proposed. Unlike the normalized/offset min-sum (NMS/OMS) algorithm, the normalization/offset factor is adaptively adjusted according to the state of check nodes in each iteration. Simulation results show that the proposed AN-/AO-MS algorithm can perform better than the NMS/OMS algorithm while still preserving the low complexity of the min-sum algorithm.

IEEE Communications Letters•Jul 1, 2010•63 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

Optimally quantized offset min-sum algorithm for flexible LDPC decoder

Daesun Oh, Keshab K. Parhi

In this paper, we analyze the performance of quantized offset min-sum (MS) decoding algorithm and propose an optimally quantized offset MS algorithm for a flexible low-density parity-check (LDPC) decoder. It is known that the offset MS decoding algorithm is implemented with simplified hardware complexity and achieves good decoding performance. However, the finite precision effects in decoding LDPC codes result in performance different from floating point. The performance degradation is caused by different dynamic ranges of input data at high signal-to-noise ratio (SNR). The proposed offset MS algorithm uses the received data directly instead of log-likelihood ratio (LLR) data as the intrinsic information. It can achieve better performance than the conventional one since its offset factor is more effective at a wide range of SNR and the intrinsic information is quantized more robustly since it is independent of channel information. Also, it is possible for the proposed scheme to use a same quantization scheme for a flexible LDPC decoder, which can decode several kinds of LDPC codes. Simulation results show that our optimally quantized offset MS algorithms with 5-bits for (1728, 864) and (1728, 1296) irregular LDPC codes achieve better performance compared with the conventional offset MS algorithms with 6-bits quantization scheme.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Oct 1, 2008•14 citations
This paper presents an optimized min sum (MS) decoding algorithm with low complexity and high decoding performance for LDPC short codes. The MS algorithm has low computational complexity and is simple to deploy. The MS decoding algorithm, while demonstrating a performance gap compared to the belief propagation (BP) and likelihood ratio BP (LLR-BP) decoding algorithms, shows significant potential for optimization. To improve the decoding performance of traditional MS algorithm, secondary external information is introduced into the control node (CNs) update operations of MS algorithm and optimized as adaptive exponential correction factor (AECF). The optimized MS algorithm is named as adaptive exponential exponential MS decoding algorithm (AEMS). The decoding efficiency of the AEMS algorithm for regular, irregular and LDPC codes of the Consultative Committee on Space Data Systems (CCSDS) was extensively tested, then the complexity of the AEMS algorithm was analyzed and compared with other decoding algorithms. The results show that the AEMS algorithm outperforms the offset MS (OMS) and normalized MS (NMS) algorithms in decoding performance, and outperforms the BP algorithm as the signal-to-noise ratio (SNR) gradually increases. В статье представлен оптимизированный алгоритм декодирования минимальной суммы (MS) с низкой сложностью и высокой производительностью декодирования для коротких кодов LDPC. Алгоритм MS имеет низкую вычислительную сложность и прост в развертывании. По сравнению с алгоритмом декодирования распространения убеждения (BP) и отношения правдоподобия BP (LLR-BP) он показывает разрыв в производительности декодирования, но алгоритм декодирования MS имеет высокий потенциал оптимизации. Для улучшения производительности декодирования традиционного алгоритма MS в операции обновления контрольных узлов (CN) алгоритма MS вводится вторичная внешняя информация и оптимизируется как адаптивный экспоненциальный поправочный коэффициент (AECF). Оптимизированный алгоритм MS назван адаптивным экспоненциальным алгоритмом декодирования MS (AEMS). Эффективность декодирования алгоритма AEMS для обычных, нерегулярных и LDPC-кодов консультативного комитета по системам космических данных (CCSDS) была всесторонне протестирована, затем был проведен анализ и сравнение сложности алгоритма AEMS с другими алгоритмами декодирования. Результаты показывают, что алгоритм AEMS превосходит алгоритмы смещенного MS (OMS) и нормализованного MS (NMS) по производительности декодирования, а также превосходит алгоритм BP по мере постепенного увеличения отношения сигнал/шум (SNR).
The belief propagation (BP) algorithm for low density parity check (LDPC) codes has proven to have excellent performance and is close to the Shannon limit. However, the high computational complexity is not conducive to realistic use. Although the min sum algorithm (MSA) improves the computational convenience and applicability. It also weakens its decoding capability. In order to improve the decoding performance of MSA and exploit the potential, this paper propose an adaptive exponential correction factor. This can improve the decoding performance of MSA. Adaptive exponential min sum algorithm (AEMSA) demonstrate a noticeable improvement over the normalized min sum algorithm (NMSA) and the BP algorithm in high signal to noise ratio (SNR). AEMSA is also a simple, efficient, low power consuming and highly potential decoding algorithm that can be applied in hardware implementations.
Aналитический подход к определению оптимальной функции постобработки для минимальной операции в алгоритме MIN-SUM, ранее полученный для обычных кодов проверки на четность с низкой плотностью (LDPC-коды), распространяется на нерегулярные коды LDPC. Оптимальное выражение постобработки для нестандартного случая варьируется от одного контрольного узла к другому, а также от одной итерации к следующей. Для практического использования необходимо аппроксимировать эту оптимальную функцию. В отличие от обычного случая, когда можно было бы использовать уникальную функцию постобработки на протяжении всего процесса декодирования без потери производительности битовых ошибок, для нерегулярных кодов критически важно варьировать постобработку от одной итерации к следующей, чтобы добиться хорошей производительности. С использованием этого подхода было выявлено, что качество битовых ошибок от алгоритма распространения доверия соответствует улучшению на 1 дБ по сравнению с MIN-SUM алгоритмом без постобработки. Сначала будет представлен обзор подхода и представлена аналитическая основа для оптимальной постобработки. Далее будет представлена оптимальная функция постобработки для нерегулярных кодов и обсуждены возможные упрощения. И наконец, показаны результаты моделирования и преимущества аппроксимации We extended an analytical approach to determining the optimal post-processing function for the minimum operation in the MIN-SUM algorithm, previously obtained for conventional low density parity check codes (LDPC codes), to irregular LDPC codes. The optimal post-processing expression for the non-standard case varies from one control node to another, as well as from one iteration to the next. For practical use, it is necessary to approximate this optimal function. Unlike the usual case where one could use a unique post-processing function throughout the entire decoding process without sacrificing bit code performance, it is critical for irregular codes to distinguish post-processing from one iteration to the next in order to achieve good performance. Using this approach, we found that the quality of bit errors from the trust algorithm corresponds to an improvement of 1 level compared to the MIN-SUM algorithm without post-processing. First, we provide an overview and analytical framework for optimal post-processing. Then, we present the optimal post-processing function for irregular codes and discuss possible simplifications. Finally, we show the simulation results and the benefits of the approximation
Min-Sum decoding (MS) is an alternative to belief propagation decoding with substantially lower complexity. MS often results in an overestimation of the log likelihood ratio (LLR) in particular in the early stage of the iterative process. A linear post-processing is usually performed as a compensation. With regular low density parity check codes (LDPC), a fixed scaling of the LLR yields sufficiently good results. In contrast, adaptive strategies are mandatory with irregular codes. It is well known that the scaling factor is an increasing function of the reliability of the LLR. In most of the publications, the scaling factor is envisioned as a function of both the iteration number and the signal-to-noise ratio. It is proposed here to use the mutual information between extrinsics as a measure of the reliability of the LLR. A practical implementation is derived with reasonable complexity. Compared to the literature, the proposed method yields slightly better results in terms of BER and a significant reduction in the number of iterations.
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.
In this paper, we analyze the performance of quantized offset min-sum (MS) decoding algorithm and propose an optimally quantized offset MS algorithm for a flexible low-density parity-check (LDPC) decoder. It is known that the offset MS decoding algorithm is implemented with simplified hardware complexity and achieves good decoding performance. However, the finite precision effects in decoding LDPC codes result in performance different from floating point. The performance degradation is caused by different dynamic ranges of input data at high signal-to-noise ratio (SNR). The proposed offset MS algorithm uses the received data directly instead of log-likelihood ratio (LLR) data as the intrinsic information. It can achieve better performance than the conventional one since its offset factor is more effective at a wide range of SNR and the intrinsic information is quantized more robustly since it is independent of channel information. Also, it is possible for the proposed scheme to use a same quantization scheme for a flexible LDPC decoder, which can decode several kinds of LDPC codes. Simulation results show that our optimally quantized offset MS algorithms with 5-bits for (1728, 864) and (1728, 1296) irregular LDPC codes achieve better performance compared with the conventional offset MS algorithms with 6-bits quantization scheme.