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

International Conference on Wireless Communications, Networking and Mobile Computing

Accelerated Q-Ary Low-Density Parity-Check Codes Decoding with Message Selection

Xiangmin Shen, Francis C. M. Lau

Published Sep 1, 2009• 0 citations
Publisher

Abstract

Immediate generalization of Gallager's binary low-density parity-check (LDPC) codes gave birth to the LDPC codes over GF(q), which demonstrated error performance exceeding that of binary codes with compromised complexity. Various methods had been proposed for the decoder with an aim to simplifying the belief propagation algorithm. One of the algorithms was the "extended min-sum (EMS)" decoder which concerned only a limited number of incoming messages at the checks. In this paper, we propose a modification to further simplify the EMS decoder without sacrificing performance.

DOI
10.1109/wicom.2009.5302908

Related papers

Q-ary LDPC decoder with euclidean-distance-based sorting criterion

Xiao Xia Shen, Francis C. M. Lau

Q-ary low-density parity-check (LDPC) codes, compared with binary ones, produce a better error performance but with a higher decoding complexity. Various solutions, such as speeding up single operations or reducing the total number of operations, have been proposed for accelerating the decoding process. In this letter, we propose a modification to the extended min-sum (EMS) decoding algorithm. The aim is to improve the decoding speed without sacrificing any error performance over an additive white Gaussian noise (AWGN) channel environment.

IEEE Communications Letters•May 1, 2010•3 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

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

Decoding Algorithms for Nonbinary LDPC Codes Over GF$(q)$

David Declercq, M.P.C. Fossorier

In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes

IEEE Transactions on Communications•Apr 1, 2007•724 citations

An Efficient Short High-Order Non-Binary LDPC Decoder Architecture Using a Message-Adaptation EMS Algorithm

Wei-Xiang Chu, Ting-An Hu, Huang–Chang Lee +2 more

Short non-binary (NB) low-density parity-check (LDPC) codes provide excellent error rate performance compared to their binary counterparts. This paper presents an efficient layered decoder architecture for short high-order non-binary LDPC codes. A hardware-friendly message-adaptation extended Min-Sum (MA-EMS) algorithm is proposed, where a variety of truncation sizes and message compressions are used, such that the number of decoding cycles and the storage requirements can be reduced. A configurable design that supports a variety of truncation sizes is also proposed such that the hardware efficiency can be significantly increased. An early termination (ET) scheme is used so as to decrease the required number of decoding cycles. These techniques can greatly reduce the complexity of the decoder with almost no loss in performance. To demonstrate these techniques, a (64, 32) 256-ary LDPC decoder is implemented in a 90 nm process, which can provide a throughput of 322.9 Mbps and occupies an area of 6.74 mm2. The proposed MA-EMS decoder is able to achieve a similar error-rate performance and a much better area efficiency compared to the original EMS decoder.

IEEE Access•Jan 1, 2021•8 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
Immediate generalization of Gallager's binary low-density parity-check (LDPC) codes gave birth to the LDPC codes over GF(q), which demonstrated error performance exceeding that of binary codes with compromised complexity. Various methods had been proposed for the decoder with an aim to simplifying the belief propagation algorithm. One of the algorithms was the "extended min-sum (EMS)" decoder which concerned only a limited number of incoming messages at the checks. In this paper, we propose a modification to further simplify the EMS decoder without sacrificing performance.
Q-ary low-density parity-check (LDPC) codes, compared with binary ones, produce a better error performance but with a higher decoding complexity. Various solutions, such as speeding up single operations or reducing the total number of operations, have been proposed for accelerating the decoding process. In this letter, we propose a modification to the extended min-sum (EMS) decoding algorithm. The aim is to improve the decoding speed without sacrificing any error performance over an additive white Gaussian noise (AWGN) channel environment.
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.
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.
Decoding Algorithms for Nonbinary LDPC Codes Over GF(q)(q)(q)
In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes
Short non-binary (NB) low-density parity-check (LDPC) codes provide excellent error rate performance compared to their binary counterparts. This paper presents an efficient layered decoder architecture for short high-order non-binary LDPC codes. A hardware-friendly message-adaptation extended Min-Sum (MA-EMS) algorithm is proposed, where a variety of truncation sizes and message compressions are used, such that the number of decoding cycles and the storage requirements can be reduced. A configurable design that supports a variety of truncation sizes is also proposed such that the hardware efficiency can be significantly increased. An early termination (ET) scheme is used so as to decrease the required number of decoding cycles. These techniques can greatly reduce the complexity of the decoder with almost no loss in performance. To demonstrate these techniques, a (64, 32) 256-ary LDPC decoder is implemented in a 90 nm process, which can provide a throughput of 322.9 Mbps and occupies an area of 6.74 mm2. The proposed MA-EMS decoder is able to achieve a similar error-rate performance and a much better area efficiency compared to the original EMS decoder.
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.