© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

IET Communications

Low‐latency low‐complexity heap‐based extended min‐sum algorithms for non‐binary low‐density parity‐check codes

Youngjun Hwang, Kyeongcheol Yang, Kyungwhoon Cheun

Published Apr 29, 2015• 3 citations

Abstract

The extended min‐sum (EMS) and improved EMS (I‐EMS) algorithms for non‐binary low‐density parity‐check codes over GF( q ) significantly reduce the decoding complexity with an acceptable performance degradation, but they suffer from high latency because of many serial computations, including a sorting process. On the other hand, the trellis‐based EMS algorithm can greatly reduce the latency, but it does not solve the complexity problem in high‐order fields ( q ≥ 64). To improve the latency problem with low‐complexity advantages, the authors propose heap‐based EMS (H‐EMS) and heap‐based I‐EMS (HI‐EMS) algorithms that are modifications of the EMS and I‐EMS algorithms, respectively. The authors also propose double H‐EMS and double HI‐EMS algorithms trading off the latency against the performance by heaping messages twice. Numerical results show that the H‐EMS algorithm has 2.74–9.52 times lower latency than the EMS algorithm with a negligible performance degradation over a wide range of code rates, whereas the HI‐EMS algorithm has 1.20–1.62 times lower latency than the I‐EMS algorithm. Furthermore, the proposed algorithms may be employed regardless of the decoding schedules.

DOI: 10.1049/iet-com.2014.1107

Related papers

A Low-Complexity EMS Algorithm with Dynamic Message Truncation for Non-Binary LDPC Codes

Fulong Wang, Ming Zhan, Qian Zhang +4 more

The extended min-sum (EMS) algorithm is adopted for non-binary low density parity check (NB-LDPC) codes. The high complexity of EMS algorithm is a hot topic in recent years. Aiming at the problem, a low-complexity EMS algorithm based on NB-LDPC codes is proposed. Dynamic bubble-check (DBC) algorithm in elementary check node (ECN) steps is adopted to reduce the complexity of check node. Furthermore, the proposed algorithm dynamically truncates the length of the message vector by the number of decoding iterations. Taking the length of message vector truncated again as half of the original one as an example, the simulation results and complexity are analyzed. Analysis shows that, compared to the EMS algorithm, computational complexity of comparisons and real additions of check node of the proposed algorithm have reduced by about 70% and 25% respectively. Meantime, the decoding performance of the proposed algorithm approach that of EMS algorithm and the loss is only near 0.08 dB when the bit error rate (BER) is 10−3and the Galois field$GF(q)(q=16)$.

•Oct 14, 2021•0 citations

A Low-Complexity Adaptive Extended Min-Sum Algorithm for Non-Binary LDPC Codes

Minho Kim, Kyeong-Bin Park, Ki‐Seok Chung

The extended min-sum algorithm (EMS) for decoding non-binary low density parity check (NB-LDPC) codes reduces the decoding complexity by truncating the message vector by retaining only the most reliable symbols. However, the EMS algorithm does not consider that the noise of the received codeword is gradually reduced as the iteration count goes up. In this paper, we propose a low-complexity adaptive EMS algorithm, called threshold-based EMS (TB-EMS). The TB-EMS algorithm has a simple adaptive rule to calculate the new message vector length compared to the A-EMS. The proposed algorithm selects one of two message vector lengths. Experimental results show that the proposed algorithm reduces the decoding complexity with minimal performance degradation compared with the EMS algorithm. Further, the decoding performance of the TB-EMS is better than A-EMS.

International Conference on Computational Intelligence and Applications (ICCIA)•Jun 1, 2020•3 citations

A modified extended min‐sum algorithm based on posterior probability thresholding for non‐binary low‐density parity‐check codes

Yatong Zhao, Liqian Wang, Miao Zhu +4 more

Abstract This letter focuses on improving the error correction performance of the extended min‐sum (EMS) decoding algorithm. Introducing factor/offset modifications in the check node update process of the EMS algorithm can improve the performance. Based on this, the authors propose a novel threshold‐based modified EMS algorithm that introduces the factor/offset in a targeted manner by setting a threshold for the posterior probability. Simulation results show that an additional performance gain of the order of 0.08 dB is obtained with the proposed method without significantly increasing the complexity of the method.

Electronics Letters•Oct 6, 2022•1 citation

Trellis-Based Extended Min-Sum Algorithm for Non-Binary LDPC Codes and its Hardware Structure

Erbao Li, David Declercq, Kiran Gunnam

In this paper, we present an improvement and a new implementation of a simplified decoding algorithm for non-binary low density parity-check codes (NB-LDPC) in Galois fields GF(q). The base algorithm that we use is the Extended Min-Sum (EMS) algorithm, which has been widely studied in the recent literature, and has been shown to approach the performance of the belief propagation (BP) algorithm, with limited complexity. In our work, we propose a new way to compute modified configuration sets, using a trellis representation of incoming messages to check nodes. We call our modification of the EMS algorithm trellis-EMS (T-EMS). In the T-EMS, the algorithm operates directly on the deviation space by considering a trellis built from differential messages, which serves as a new reliability measure to sort the configurations. We show that this new trellis representation reduces the computational complexity, without any performance degradation. In addition, we show that our modifications of the algorithm allows to greatly reduce the decoding latency, by using a larger degree of hardware parallelization.

IEEE Transactions on Communications•May 15, 2013•104 citations

Combined normalized and offset extended min sum decoding algorithm for LDPC codes over GF (q)

Md Murad Hossain, Mohammad Rakibul Islam

In this paper the combined normalized and offset extended min sum (EMS) is proposed for efficient decoding of non-binary low density parity check (LDPC) codes. EMS is the approximation of the sum product algorithm for reducing the computation complexity. However there is a performance gap between EMS and SP algorithm due to this approximation. The approximate check node messages of the extended min sum are compensated by both normalized and offset factor. The normalized factor and offset factor is determined for one iteration and is kept constant for all SNRs and iterations. It will shown in bit error rate simulation of (1008, 504) LDPC code over GF (4) that combined normalized offset extended min sum has superior performance than normalized and offset extended min sum. However, it requires only extra one multiplication for each cycle.

International Conference on Computer and Information Technology (ICCIT)•Dec 1, 2011•0 citations

An adaptive EMS algorithm for nonbinary LDPC codes

Youngjun Hwang, Sunghye Cho, Kyeongcheol Yang

The extended min-sum (EMS) algorithm for decoding low-density parity-check codes over the finite field with q elements significantly reduces decoding complexity by truncating each message of length q into a message of effective length nm. The number of effectively dominant components in each truncated message may gradually decrease with the number of decoding iterations. Based on this observation, we propose a novel adaptive EMS algorithm, called a two-length EMS (TL-EMS) algorithm. It chooses one of two candidate values as the effective message length nmfor each message by reflecting the concept called message separation. Numerical results show that it can significantly reduce the computational complexity with little performance degradation.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•2 citations

The extended min‐sum (EMS) and improved EMS (I‐EMS) algorithms for non‐binary low‐density parity‐check codes over GF( q ) significantly reduce the decoding complexity with an acceptable performance degradation, but they suffer from high latency because of many serial computations, including a sorting process. On the other hand, the trellis‐based EMS algorithm can greatly reduce the latency, but it does not solve the complexity problem in high‐order fields ( q ≥ 64). To improve the latency problem with low‐complexity advantages, the authors propose heap‐based EMS (H‐EMS) and heap‐based I‐EMS (HI‐EMS) algorithms that are modifications of the EMS and I‐EMS algorithms, respectively. The authors also propose double H‐EMS and double HI‐EMS algorithms trading off the latency against the performance by heaping messages twice. Numerical results show that the H‐EMS algorithm has 2.74–9.52 times lower latency than the EMS algorithm with a negligible performance degradation over a wide range of code rates, whereas the HI‐EMS algorithm has 1.20–1.62 times lower latency than the I‐EMS algorithm. Furthermore, the proposed algorithms may be employed regardless of the decoding schedules.

The extended min-sum (EMS) algorithm is adopted for non-binary low density parity check (NB-LDPC) codes. The high complexity of EMS algorithm is a hot topic in recent years. Aiming at the problem, a low-complexity EMS algorithm based on NB-LDPC codes is proposed. Dynamic bubble-check (DBC) algorithm in elementary check node (ECN) steps is adopted to reduce the complexity of check node. Furthermore, the proposed algorithm dynamically truncates the length of the message vector by the number of decoding iterations. Taking the length of message vector truncated again as half of the original one as an example, the simulation results and complexity are analyzed. Analysis shows that, compared to the EMS algorithm, computational complexity of comparisons and real additions of check node of the proposed algorithm have reduced by about 70% and 25% respectively. Meantime, the decoding performance of the proposed algorithm approach that of EMS algorithm and the loss is only near 0.08 dB when the bit error rate (BER) is 10−3and the Galois field

GF(q)(q=16)

.

The extended min-sum algorithm (EMS) for decoding non-binary low density parity check (NB-LDPC) codes reduces the decoding complexity by truncating the message vector by retaining only the most reliable symbols. However, the EMS algorithm does not consider that the noise of the received codeword is gradually reduced as the iteration count goes up. In this paper, we propose a low-complexity adaptive EMS algorithm, called threshold-based EMS (TB-EMS). The TB-EMS algorithm has a simple adaptive rule to calculate the new message vector length compared to the A-EMS. The proposed algorithm selects one of two message vector lengths. Experimental results show that the proposed algorithm reduces the decoding complexity with minimal performance degradation compared with the EMS algorithm. Further, the decoding performance of the TB-EMS is better than A-EMS.

Abstract This letter focuses on improving the error correction performance of the extended min‐sum (EMS) decoding algorithm. Introducing factor/offset modifications in the check node update process of the EMS algorithm can improve the performance. Based on this, the authors propose a novel threshold‐based modified EMS algorithm that introduces the factor/offset in a targeted manner by setting a threshold for the posterior probability. Simulation results show that an additional performance gain of the order of 0.08 dB is obtained with the proposed method without significantly increasing the complexity of the method.

In this paper, we present an improvement and a new implementation of a simplified decoding algorithm for non-binary low density parity-check codes (NB-LDPC) in Galois fields GF(q). The base algorithm that we use is the Extended Min-Sum (EMS) algorithm, which has been widely studied in the recent literature, and has been shown to approach the performance of the belief propagation (BP) algorithm, with limited complexity. In our work, we propose a new way to compute modified configuration sets, using a trellis representation of incoming messages to check nodes. We call our modification of the EMS algorithm trellis-EMS (T-EMS). In the T-EMS, the algorithm operates directly on the deviation space by considering a trellis built from differential messages, which serves as a new reliability measure to sort the configurations. We show that this new trellis representation reduces the computational complexity, without any performance degradation. In addition, we show that our modifications of the algorithm allows to greatly reduce the decoding latency, by using a larger degree of hardware parallelization.

In this paper the combined normalized and offset extended min sum (EMS) is proposed for efficient decoding of non-binary low density parity check (LDPC) codes. EMS is the approximation of the sum product algorithm for reducing the computation complexity. However there is a performance gap between EMS and SP algorithm due to this approximation. The approximate check node messages of the extended min sum are compensated by both normalized and offset factor. The normalized factor and offset factor is determined for one iteration and is kept constant for all SNRs and iterations. It will shown in bit error rate simulation of (1008, 504) LDPC code over GF (4) that combined normalized offset extended min sum has superior performance than normalized and offset extended min sum. However, it requires only extra one multiplication for each cycle.

The extended min-sum (EMS) algorithm for decoding low-density parity-check codes over the finite field with q elements significantly reduces decoding complexity by truncating each message of length q into a message of effective length nm. The number of effectively dominant components in each truncated message may gradually decrease with the number of decoding iterations. Based on this observation, we propose a novel adaptive EMS algorithm, called a two-length EMS (TL-EMS) algorithm. It chooses one of two candidate values as the effective message length nmfor each message by reflecting the concept called message separation. Numerical results show that it can significantly reduce the computational complexity with little performance degradation.