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:2003.00714 · IEEE Communications Letters

Design of Low Complexity Non-Binary LDPC Codes with an Approximated Performance-Complexity Tradeoff

Yang Yu, Wen Chen

Published Feb 22, 2012• 9 citations
arXivHTMLPDF

Abstract

By presenting an approximated performance-complexity tradeoff (PCT) algorithm, a low-complexity non-binary low density parity check (LDPC) code over q-ary-input symmetric-output channel is designed in this manuscript which converges faster than the threshold-optimized non-binary LDPC codes in the low error rate regime. We examine our algorithm by both hard and soft decision decoders. Moreover, simulation shows that the approximated PCT algorithm has accelerated the convergence process by 30% regarding the number of the decoding iterations.

DOI
10.1109/lcomm.2012.021612.112467

Related papers

Design of irregular LDPC codes with optimized performance-complexity tradeoff

Benjamin Smith, Masoud Ardakani, Wei Yu +1 more

The optimal performance-complexity tradeoff for error-correcting codes at rates strictly below the Shannon limit is a central question in coding theory. This paper proposes a numerical approach for the minimization of decoding complexity for long-block-length irregular low-density parity-check (LDPC) codes. The proposed design methodology is applicable to any binary-input memoryless symmetric channel and any iterative message-passing decoding algorithm with a parallel-update schedule. A key feature of the proposed optimization method is a new complexity measure that incorporates both the number of operations required to carry out a single decoding iteration and the number of iterations required for convergence. This paper shows that the proposed complexity measure can be accurately estimated from a density-evolution and extrinsic-information transfer chart analysis of the code. A sufficient condition is presented for convexity of the complexity measure in the variable edge-degree distribution; when it is not satisfied, numerical experiments nevertheless suggest that the local minimum is unique. The results presented herein show that when the decoding complexity is constrained, the complexity-optimized codes significantly outperform threshold-optimized codes at long block lengths, within the ensemble of irregular codes.

IEEE Transactions on Communications•Feb 1, 2010•68 citations

Design of Low-Density Parity-Check Codes and Their Decoding Algorithms

조성혜

In this thesis, we propose low-complexity designing algorithms for non-binary low-density parity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding algorithms for binary LDPC codes. We first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q) based on message-passing algorithms. Short cycles in an NB-LDPC code may be even more harmful to its performance if they do not satisfy the so-called full rank condition (FRC). This is because they may induce low-weight codewords or absorbing sets in that case. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as the number of short cycles for analyzing the performance of an NB-LDPC code. In order to count those cycles, we first develop a novel message-passing algorithm and identify how it is related to the FRC.We then propose a low-complexity algorithmfor counting the number of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short cycles. The proposed algorithm is not only theoretically validated, but its computational and storage complexities are also computed. It does not require cycle enumeration with high complexity, and therefore is still feasible even in the case of large code length, say ≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal rule to choose a nonzero element for a given edge and propose a low-complexity algorithm for designing an NB-LDPC code with low error floor. Furthermore, several design examples are presented to verify the validity of the proposed design algorithm. Secondly, we propose a low-complexity decoding algorithm for binary LDPC codes over the binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding algorithm for binary LDPC codes and has lower computational complexity than the sum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it has performance degradation. Furthermore, reducing the number of bits for representing messages to two in a decoding algorithm for further reducing computational and storage complexities, causes significant performance losses. In order to minimize the performance degradation and computational and storage complexities, we propose a low-complexity decoding algorithm which uses several decoders with two-bit precision for binary LDPC codes over the BSC. The proposed algorithm adaptively changes decoders according to the number of unsatisfied check nodes at each iteration. Compared with the SPA using floating-point operations, the proposed decoding algorithm greatly reduces computational and storage complexities with negligible performance losses. Numerical results show that the proposed decoding algorithm has similar performance to the SPA with floating-point operations over the BSC. In the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes for the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms …

•Jan 1, 2018•0 citations

Non-binary low-density parity-check codes for the q-ary erasure channel

Giuliano Garrammone, Enrico Paolini, Balázs Matuz +2 more

The finite-length design of non-binary low-density parity-check (LDPC) codes for the q-ary erasure channel under maximum a posteriori (MAP) decoding is addressed. A low-complexity MAP decoding algorithm is reviewed for which a code design strategy is proposed. In particular, it is illustrated how a judicious code design permits to find a trade-off between performance in terms of codeword error rate (CER) and decoding complexity. As an example, the performance curve of a short (400, 200) code on the memoryless 4-ary erasure channel tightly approaches the Singleton bound at least down to a CER of 10-8.

International Conference on Communications•Jun 1, 2013•4 citations

E-IHRB Decoder Architectures for Non-Binary LDPC Codes

Madamsetti, Kalyani, M, Suseela

In the information theory , the non- binary low density parity check  (NB-LDPC) code is a  linear error correcting code , a method of transmitting message over a  noisy transmission channel. LDPCcodes are  capacity-approaching codes , which  means  that  practical constructions exist  that allow the noise threshold to be set very close to the theoretical maximum for a symmetric memory less channel.Using iterative  belief propagation techniques, NB-LDPC codes can be decoded in time linear to their block length. Non-binary low-density parity-check codes can achieve higher performance than their binary counterparts. Recently, two algorithms were developed for decoding NB-LDPC codes: iterative hard reliability-based majority-logic decoding (IHRB-MLGD) and iterative soft reliability-based majority-logic decoding (ISRB-MLGD has better performance-complexity tradeoffs than previous algorithms. This paper first proposes message-passing in such a way that we can reduce the memory consumption to a greater extent at the same time there should not be performance loss. By using enhanced iterative reliability-based majority-logic decoding algorithms we can achieve effective complexity-performance and noise free design. Compared to previous designs, our proposed decoders have at least tens of times lower complexity with moderate coding gain loss.

•Aug 31, 2014•0 citations

Design of Convergence-Optimized Non-Binary LDPC Codes over

Yang Yu, Wen Chen, Lili Wei

In this letter, we present a hybrid iterative decoder for non-binary low density parity check (LDPC) codes over binary erasure channel (BEC), based on which the recursion of the erasure probability is derived to design non-binary LDPC codes with convergence-optimized degree distributions. The resulting one-step decoding tree is cycle-free and achieves lower decoding complexity. Experimental studies show that the proposed convergence-optimization algorithm accelerates the convergence process by 33%.

•Jan 1, 2012•0 citations

Cooperative decoder design for non-binary LDPC code with coefficients selection

Yang Yu, Wen Chen, Jun Li +1 more

In this paper we design novel decoders for non-binary low density parity check (LDPC) codes. For a non-binary LDPC code C over the field Fqof size q for some q > 0, we propose two novel cooperative decoders, each composed of a binary component decoder and a q-ary component decoder in a concatenated manner, to obtain excellent decoding performance. Specifically to reduce the complexity of the cooperative decoders, we design a hybrid q-ary component decoder. Then, we propose an algorithm to construct the parity check matrix to eliminate the bit-level cycles. Simulations show that the decoding performance of the proposed algorithm approaches the capacity limit within 0.2dB at BER= 10−4.

Globecom•Dec 1, 2013•2 citations
By presenting an approximated performance-complexity tradeoff (PCT) algorithm, a low-complexity non-binary low density parity check (LDPC) code over q-ary-input symmetric-output channel is designed in this manuscript which converges faster than the threshold-optimized non-binary LDPC codes in the low error rate regime. We examine our algorithm by both hard and soft decision decoders. Moreover, simulation shows that the approximated PCT algorithm has accelerated the convergence process by 30% regarding the number of the decoding iterations.
The optimal performance-complexity tradeoff for error-correcting codes at rates strictly below the Shannon limit is a central question in coding theory. This paper proposes a numerical approach for the minimization of decoding complexity for long-block-length irregular low-density parity-check (LDPC) codes. The proposed design methodology is applicable to any binary-input memoryless symmetric channel and any iterative message-passing decoding algorithm with a parallel-update schedule. A key feature of the proposed optimization method is a new complexity measure that incorporates both the number of operations required to carry out a single decoding iteration and the number of iterations required for convergence. This paper shows that the proposed complexity measure can be accurately estimated from a density-evolution and extrinsic-information transfer chart analysis of the code. A sufficient condition is presented for convexity of the complexity measure in the variable edge-degree distribution; when it is not satisfied, numerical experiments nevertheless suggest that the local minimum is unique. The results presented herein show that when the decoding complexity is constrained, the complexity-optimized codes significantly outperform threshold-optimized codes at long block lengths, within the ensemble of irregular codes.
In this thesis, we propose low-complexity designing algorithms for non-binary low-density parity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding algorithms for binary LDPC codes. We first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q) based on message-passing algorithms. Short cycles in an NB-LDPC code may be even more harmful to its performance if they do not satisfy the so-called full rank condition (FRC). This is because they may induce low-weight codewords or absorbing sets in that case. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as the number of short cycles for analyzing the performance of an NB-LDPC code. In order to count those cycles, we first develop a novel message-passing algorithm and identify how it is related to the FRC.We then propose a low-complexity algorithmfor counting the number of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short cycles. The proposed algorithm is not only theoretically validated, but its computational and storage complexities are also computed. It does not require cycle enumeration with high complexity, and therefore is still feasible even in the case of large code length, say ≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal rule to choose a nonzero element for a given edge and propose a low-complexity algorithm for designing an NB-LDPC code with low error floor. Furthermore, several design examples are presented to verify the validity of the proposed design algorithm. Secondly, we propose a low-complexity decoding algorithm for binary LDPC codes over the binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding algorithm for binary LDPC codes and has lower computational complexity than the sum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it has performance degradation. Furthermore, reducing the number of bits for representing messages to two in a decoding algorithm for further reducing computational and storage complexities, causes significant performance losses. In order to minimize the performance degradation and computational and storage complexities, we propose a low-complexity decoding algorithm which uses several decoders with two-bit precision for binary LDPC codes over the BSC. The proposed algorithm adaptively changes decoders according to the number of unsatisfied check nodes at each iteration. Compared with the SPA using floating-point operations, the proposed decoding algorithm greatly reduces computational and storage complexities with negligible performance losses. Numerical results show that the proposed decoding algorithm has similar performance to the SPA with floating-point operations over the BSC. In the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes for the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms …
The finite-length design of non-binary low-density parity-check (LDPC) codes for the q-ary erasure channel under maximum a posteriori (MAP) decoding is addressed. A low-complexity MAP decoding algorithm is reviewed for which a code design strategy is proposed. In particular, it is illustrated how a judicious code design permits to find a trade-off between performance in terms of codeword error rate (CER) and decoding complexity. As an example, the performance curve of a short (400, 200) code on the memoryless 4-ary erasure channel tightly approaches the Singleton bound at least down to a CER of 10-8.
In the information theory , the non- binary low density parity check  (NB-LDPC) code is a  linear error correcting code , a method of transmitting message over a  noisy transmission channel. LDPCcodes are  capacity-approaching codes , which  means  that  practical constructions exist  that allow the noise threshold to be set very close to the theoretical maximum for a symmetric memory less channel.Using iterative  belief propagation techniques, NB-LDPC codes can be decoded in time linear to their block length. Non-binary low-density parity-check codes can achieve higher performance than their binary counterparts. Recently, two algorithms were developed for decoding NB-LDPC codes: iterative hard reliability-based majority-logic decoding (IHRB-MLGD) and iterative soft reliability-based majority-logic decoding (ISRB-MLGD has better performance-complexity tradeoffs than previous algorithms. This paper first proposes message-passing in such a way that we can reduce the memory consumption to a greater extent at the same time there should not be performance loss. By using enhanced iterative reliability-based majority-logic decoding algorithms we can achieve effective complexity-performance and noise free design. Compared to previous designs, our proposed decoders have at least tens of times lower complexity with moderate coding gain loss.
In this letter, we present a hybrid iterative decoder for non-binary low density parity check (LDPC) codes over binary erasure channel (BEC), based on which the recursion of the erasure probability is derived to design non-binary LDPC codes with convergence-optimized degree distributions. The resulting one-step decoding tree is cycle-free and achieves lower decoding complexity. Experimental studies show that the proposed convergence-optimization algorithm accelerates the convergence process by 33%.
In this paper we design novel decoders for non-binary low density parity check (LDPC) codes. For a non-binary LDPC code C over the field Fqof size q for some q > 0, we propose two novel cooperative decoders, each composed of a binary component decoder and a q-ary component decoder in a concatenated manner, to obtain excellent decoding performance. Specifically to reduce the complexity of the cooperative decoders, we design a hybrid q-ary component decoder. Then, we propose an algorithm to construct the parity check matrix to eliminate the bit-level cycles. Simulations show that the decoding performance of the proposed algorithm approaches the capacity limit within 0.2dB at BER= 10−4.