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

arXiv:0803.1094 · IEEE International Symposium on Information Theory (ISIT)

Min-Max decoding for non binary LDPC codes

Valentin Savin

Published Jul 1, 2008• 230 citations
arXivHTMLPDF

Abstract

Iterative decoding of non-binary LDPC codes is currently performed using either the sum-product or the min-sum algorithms or slightly different versions of them. In this paper, several low-complexity quasi-optimal iterative algorithms are proposed for decoding non-binary codes. The min-max algorithm is one of them and it has the benefit of two possible LLR domain implementations: a standard implementation, whose complexity scales as the square of the Galois field's cardinality and a reduced complexity implementation called selective implementation, which makes the min-max decoding very attractive for practical purposes.

DOI
10.1109/isit.2008.4595129

Related papers

An Adaptive Method to Improve the Iteration Efficiency for Non-binary LDPC Decoding

Jin Xu, Jun Xu, Hai Tian +2 more

Non-binary low density parity check codes can achieve better err-correcting performance than binary LDPC codes when the code length is moderate at the cost of higher decoding complexity. Min-Max decoding algorithm is one of the low-complexity quasi-optimal iterative algorithms. However, a problem of the Min-Max decoding algorithm is iteration inefficient in the case of low SNR. In this paper, an adaptive method is proposed based on the Min-Max decoding algorithm. By comparing the correlation among each iteration output, setting an appropriate threshold to determine whether ahead of the end of iteration, which makes the adaptive Min-Max decoding algorithm very attractive for practical purposes

DEStech Transactions on Computer Science and Engineering•May 5, 2017•0 citations

A subp-optimal log-domain decoding algorithm for non-binary LDPC codes

Chirag Dadlani, Ranjan Bose

Low-Density Parity-Check (LDPC) codes have gained significant popularity recently and have been recommended for various wireless standards of the future. Non-binary LDPC codes provide all the well-known advantages of binary LDPC codes but allow for much shorter block lengths. The sum-product decoding algorithm for non-binary LDPC codes is too complex for efficient implementation. Hence, we have represented the sum-product algorithm in a novel log-domain form in terms of operators defined earlier in literature. This form greatly simplifies the key step in the check-node processing and allows us to replace a max* operation in the decoder by a max operation. This leads to a sub-optimal decoding algorithm which we propose in this paper.

•Mar 23, 2010•1 citation

Memory efficient column-layered decoder design for non-binary LDPC codes

Kai He, Jin Sha, Zhongfeng Wang

Low-density parity-check (LDPC) codes constructed over the Galois field GF(q) (q>;2), which are also called non-binary LDPC codes, are an extension of binary LDPC codes with significantly better performance. In this paper, an efficient column-layered decoding algorithm, which can reduce the message memory as well as the average number of iterations dramatically, is proposed for min-max decoding. In addition, a non-uniform quantization scheme is developed for reducing the word length while achieving similar performances compared to a conventional quantization scheme. Meanwhile, the corresponding decoder architecture is also proposed.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2012•1 citation

Selective max‐min algorithm for low‐density parity‐check decoding

Ahmed Hareedy, Mohamed M. Khairy

With the growing importance of error correction in different communication systems, using an efficient and easily implementable code is always appreciated. One of the most important codes is the low‐density parity‐check (LDPC) code. Two main iterative decoding algorithms are usually used, namely the sum‐product (SP) algorithm (also referred to as belief propagation) and the min–sum (MS). The SP algorithm is more accurate but suffers from very high complexity. On the other hand, the MS algorithm has a much lower complexity at the expense of some performance degradation. To handle this performance degradation, many algorithms were presented in the literature as improvements for the MS, like the scaled MS and the offset MS. However, all those improved algorithms are more complex than the traditional MS. In this study, an efficient and low complexity LDPC decoding algorithm, called selective max–min (SMM), is proposed. The SMM performance is closer to SP than to MS as long as the average number of ones per column in the parity check matrix is around or less than 4 (which is the case for most of the communication systems using LDPC). On the other hand, the SMM exhibits only a minor complexity increase over traditional MS making it suitable for practical implementation.

IET Communications•Jan 1, 2013•4 citations

A revolving iterative algorithm for decoding algebraic quasi-cyclic LDPC codes

Keke Liu, Shu Lin, Khaled Abdel-Ghaffar

An effective reduced-complexity min-sum algorithm for decoding algebraic quasi-cyclic LDPC codes is presented. The proposed decoding algorithm significantly reduces the hardware implementation complexity, the size of memory required to store information, and the computational complexity of a decoder with no or a small loss in performance compared to the scaled min-sum algorithm.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•2 citations

A Low-complexity Iterative Decoding Algorithm for LDPC Codes

Pan Yu

Among the decoding algorithms for low-density parity-check(LDPC) code,sum-product algorithm(SPA) has the optimal performance but high complexity,while min-sum algorithm has simple implementation complexity but worse performance.Considering this performance-complexity contradiction,some modified min-sum algorithms are proposed.In this paper,researches are done based on one of the modified min-sum algorithms that is close to SPA in performance but the way modifying fraction works is simplified.Simplified algorithm remains similar in performance to sum-product algorithm but has a remarkably reduced implementation complexity.

Telecommunication Engineering•Jan 1, 2006•1 citation
Iterative decoding of non-binary LDPC codes is currently performed using either the sum-product or the min-sum algorithms or slightly different versions of them. In this paper, several low-complexity quasi-optimal iterative algorithms are proposed for decoding non-binary codes. The min-max algorithm is one of them and it has the benefit of two possible LLR domain implementations: a standard implementation, whose complexity scales as the square of the Galois field's cardinality and a reduced complexity implementation called selective implementation, which makes the min-max decoding very attractive for practical purposes.
Non-binary low density parity check codes can achieve better err-correcting performance than binary LDPC codes when the code length is moderate at the cost of higher decoding complexity. Min-Max decoding algorithm is one of the low-complexity quasi-optimal iterative algorithms. However, a problem of the Min-Max decoding algorithm is iteration inefficient in the case of low SNR. In this paper, an adaptive method is proposed based on the Min-Max decoding algorithm. By comparing the correlation among each iteration output, setting an appropriate threshold to determine whether ahead of the end of iteration, which makes the adaptive Min-Max decoding algorithm very attractive for practical purposes
Low-Density Parity-Check (LDPC) codes have gained significant popularity recently and have been recommended for various wireless standards of the future. Non-binary LDPC codes provide all the well-known advantages of binary LDPC codes but allow for much shorter block lengths. The sum-product decoding algorithm for non-binary LDPC codes is too complex for efficient implementation. Hence, we have represented the sum-product algorithm in a novel log-domain form in terms of operators defined earlier in literature. This form greatly simplifies the key step in the check-node processing and allows us to replace a max* operation in the decoder by a max operation. This leads to a sub-optimal decoding algorithm which we propose in this paper.
Low-density parity-check (LDPC) codes constructed over the Galois field GF(q) (q>;2), which are also called non-binary LDPC codes, are an extension of binary LDPC codes with significantly better performance. In this paper, an efficient column-layered decoding algorithm, which can reduce the message memory as well as the average number of iterations dramatically, is proposed for min-max decoding. In addition, a non-uniform quantization scheme is developed for reducing the word length while achieving similar performances compared to a conventional quantization scheme. Meanwhile, the corresponding decoder architecture is also proposed.
With the growing importance of error correction in different communication systems, using an efficient and easily implementable code is always appreciated. One of the most important codes is the low‐density parity‐check (LDPC) code. Two main iterative decoding algorithms are usually used, namely the sum‐product (SP) algorithm (also referred to as belief propagation) and the min–sum (MS). The SP algorithm is more accurate but suffers from very high complexity. On the other hand, the MS algorithm has a much lower complexity at the expense of some performance degradation. To handle this performance degradation, many algorithms were presented in the literature as improvements for the MS, like the scaled MS and the offset MS. However, all those improved algorithms are more complex than the traditional MS. In this study, an efficient and low complexity LDPC decoding algorithm, called selective max–min (SMM), is proposed. The SMM performance is closer to SP than to MS as long as the average number of ones per column in the parity check matrix is around or less than 4 (which is the case for most of the communication systems using LDPC). On the other hand, the SMM exhibits only a minor complexity increase over traditional MS making it suitable for practical implementation.
Among the decoding algorithms for low-density parity-check(LDPC) code,sum-product algorithm(SPA) has the optimal performance but high complexity,while min-sum algorithm has simple implementation complexity but worse performance.Considering this performance-complexity contradiction,some modified min-sum algorithms are proposed.In this paper,researches are done based on one of the modified min-sum algorithms that is close to SPA in performance but the way modifying fraction works is simplified.Simplified algorithm remains similar in performance to sum-product algorithm but has a remarkably reduced implementation complexity.