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:1004.5367 · IEEE Transactions on Information Theory

Multiplicatively Repeated Nonbinary LDPC Codes

Kenta Kasai, David Declercq, Charly Poulliat, Kohichi Sakaniwa

Published Oct 1, 2011• 45 citations
arXivHTMLPDF

Abstract

We propose nonbinary LDPC codes concatenated with multiplicative repetition codes. By multiplicatively repeating the (2,3)-regular nonbinary LDPC mother code of rate 1/3, we construct rate-compatible codes of lower rates 1/6, 1/9, 1/12,.... Surprisingly, such simple low-rate nonbinary LDPC codes outperform the best low-rate binary LDPC codes so far. Moreover, we propose the decoding algorithm for the proposed codes, which can be decoded with almost the same computational complexity as that of the mother code.

DOI
10.1109/tit.2011.2162259

Related papers

Rate-compatible non-binary LDPC codes concatenated with multiplicative repetition codes

Kenta Kasai, David Declercq, Charly Poulliat +1 more

We propose non-binary LDPC codes concatenated with multiplicative repetition codes. To the best of the authors' knowledge, for the transmissions over the memoryless binary-input output-symmetric channels, 2m-ary the (2,dc)-regular LDPC code for m ~ 8 and dc≥ 3 is the best code so far among codes with moderate code length. By multiplicatively repeating the 2m-ary (2,3)-regular LDPC code of rate 1/3, we construct rate-compatible codes of lower rates 1/6,1/9,1/12,.... Surprisingly, such simple low-rate codes outperform the best low-rate binary codes so far.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•13 citations

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Dina Goldin, David Burshtein

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.

IEEE Transactions on Information Theory•Aug 6, 2012•17 citations

On the Serial Concatenation of LDPC Codes

Fedor I. Ivanov, Aleksey Kuvshinov

Concatenated codes are effectively used in different approaches of error-correcting theory. We suggest new concatenated code construction that is composed of outer LDPC code and a particular designed inner LDPC code. Special optimization procedure was developed to obtain inner code with specific error-correcting characteristics. We apply the decoder of woven codes to this construction, while reducing the complexity of decoding procedure compared to a classic decoder of LDPC code. Furthermore, we improve the performance of our scheme with puncturing the code symbols. The resulting concatenated construction outperforms low-rate LDPC from the 5G standard. Besides this, we demonstrate the performance of code with a special parity-check matrix consisting of parity-check matrices of inner and outer codes from our suggested construction.

International Conference on Advanced Technologies, Systems and Services in Telecommunications (TELSIKS)•Oct 25, 2023•3 citations

Nonbinary LDPC Codes

W.E. Ryan, Shu Wen Lin

Although a great deal of research effort has been expended on the design, construction, encoding, decoding, performance analysis, and applications of binary LDPC codes in communication and storage systems, very little has been done on nonbinary LDPC codes in these respects. The first study of nonbinary LDPC codes was conducted by Davey and MacKay in 1998. In their paper, they generalized the SPA for decoding binary LDPC codes to decode q -ary LDPC codes, called QSPA . Later, in 2000, MacKay and Davey introduced a fast-Fourier-transform (FFT)-based QSPA to reduce the decoding computational complexity of QSPA. This decoding algorithm is referred to as FFT-QSPA. MacKay and Davey's work on FFT-QSPA was further improved by Barnault and Declercq in 2003 and Declercq and Fossorier in 2007. Significant works on the design, construction and analysis of nonbinary LDPC codes didn't appear until the middle of 2000. Results in these works are very encouraging. They show that nonbinary LDPC codes have a great potential to replace widely used RS codes in some applications in communication and storage systems. This chapter is devoted to nonbinary LDPC codes. Just like binary LDPC codes, nonbinary LDPC codes can be classified into two major categories: (1) random-like nonbinary codes constructed by computer under certain design criteria or rules; and (2) structured nonbinary codes constructed on the basis of algebraic or combinatorial tools, such as finite fields and finite geometries.

Cambridge University Press eBooks•Sep 17, 2009•0 citations

On Several Kinds of Non-binary Rate-compatible LDPC Codes

XU Jia-pin

Several kinds of non-binary rate-compatible LDPC codes with strong error-detecting ability and low complexity in encoding and decoding are studied and constructed.An efficient punctured encoding algorithm of parity bit is proposed,thus to get high-performance non-binary RC-LDPC codes.The punctured algorithm,based on the non-binary mother code with high performance and medium bit rate(1/2 rate),adopts efficient structured punctured algorithm and designs the high-performance error correction codes in a wide rate range(for example,from 1/10 to 9/10).The simulation results indicate that this algorithm is better in performance than the conventional random puncturing algorithm and the puncturing algorithm based on node grouping and sorting.

Communications technology•Jan 1, 2012•0 citations

Irregular Generalized LDPC codes in Practical Communication Scenarios

Irina E. Bocharova, Boris D. Kudryashov, Sander Mikelsaar

High-rate irregular Generalized LDPC (GLDPC) codes with low-complexity constituent codes are studied. The main area of focus is the optimization of the underlying irregular binary LDPC codes and their matching with constituent codes. Finite length random coding bound on the maximum-likelihood decoding error probability of a random ensemble of irregular GLDPC codes is derived and compared with a similar bound for non-binary (NB) LDPC codes over small alphabets.A new algorithm for assigning columns of the parity-check matrix of a constituent code to nonzero elements of a base matrix of the quasi-cyclic (QC)-GLDPC code is presented. Examples of the constructed QC-GLDPC codes are given. The simulation results for frame error rate (FER) performance of the belief-propagation (BP) decoding for the QC-GLDPC codes are presented and compared with the same performance of NB QC-LDPC codes over small alphabets and binary LDPC codes in the WiFi and 5G standards.Both GLDPC codes and NB LDPC codes with sufficiently low decoding complexity are shown to outperform their binary LDPC counterparts, while GLDPC codes appear to be more advantageous in terms of decoding complexity.

IEEE Information Theory Workshop (ITW)•Nov 1, 2022•1 citation
We propose nonbinary LDPC codes concatenated with multiplicative repetition codes. By multiplicatively repeating the (2,3)-regular nonbinary LDPC mother code of rate 1/3, we construct rate-compatible codes of lower rates 1/6, 1/9, 1/12,.... Surprisingly, such simple low-rate nonbinary LDPC codes outperform the best low-rate binary LDPC codes so far. Moreover, we propose the decoding algorithm for the proposed codes, which can be decoded with almost the same computational complexity as that of the mother code.
We propose non-binary LDPC codes concatenated with multiplicative repetition codes. To the best of the authors' knowledge, for the transmissions over the memoryless binary-input output-symmetric channels, 2m-ary the (2,dc)-regular LDPC code for m ~ 8 and dc≥ 3 is the best code so far among codes with moderate code length. By multiplicatively repeating the 2m-ary (2,3)-regular LDPC code of rate 1/3, we construct rate-compatible codes of lower rates 1/6,1/9,1/12,.... Surprisingly, such simple low-rate codes outperform the best low-rate binary codes so far.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.
Concatenated codes are effectively used in different approaches of error-correcting theory. We suggest new concatenated code construction that is composed of outer LDPC code and a particular designed inner LDPC code. Special optimization procedure was developed to obtain inner code with specific error-correcting characteristics. We apply the decoder of woven codes to this construction, while reducing the complexity of decoding procedure compared to a classic decoder of LDPC code. Furthermore, we improve the performance of our scheme with puncturing the code symbols. The resulting concatenated construction outperforms low-rate LDPC from the 5G standard. Besides this, we demonstrate the performance of code with a special parity-check matrix consisting of parity-check matrices of inner and outer codes from our suggested construction.
Although a great deal of research effort has been expended on the design, construction, encoding, decoding, performance analysis, and applications of binary LDPC codes in communication and storage systems, very little has been done on nonbinary LDPC codes in these respects. The first study of nonbinary LDPC codes was conducted by Davey and MacKay in 1998. In their paper, they generalized the SPA for decoding binary LDPC codes to decode q -ary LDPC codes, called QSPA . Later, in 2000, MacKay and Davey introduced a fast-Fourier-transform (FFT)-based QSPA to reduce the decoding computational complexity of QSPA. This decoding algorithm is referred to as FFT-QSPA. MacKay and Davey's work on FFT-QSPA was further improved by Barnault and Declercq in 2003 and Declercq and Fossorier in 2007. Significant works on the design, construction and analysis of nonbinary LDPC codes didn't appear until the middle of 2000. Results in these works are very encouraging. They show that nonbinary LDPC codes have a great potential to replace widely used RS codes in some applications in communication and storage systems. This chapter is devoted to nonbinary LDPC codes. Just like binary LDPC codes, nonbinary LDPC codes can be classified into two major categories: (1) random-like nonbinary codes constructed by computer under certain design criteria or rules; and (2) structured nonbinary codes constructed on the basis of algebraic or combinatorial tools, such as finite fields and finite geometries.
Several kinds of non-binary rate-compatible LDPC codes with strong error-detecting ability and low complexity in encoding and decoding are studied and constructed.An efficient punctured encoding algorithm of parity bit is proposed,thus to get high-performance non-binary RC-LDPC codes.The punctured algorithm,based on the non-binary mother code with high performance and medium bit rate(1/2 rate),adopts efficient structured punctured algorithm and designs the high-performance error correction codes in a wide rate range(for example,from 1/10 to 9/10).The simulation results indicate that this algorithm is better in performance than the conventional random puncturing algorithm and the puncturing algorithm based on node grouping and sorting.
High-rate irregular Generalized LDPC (GLDPC) codes with low-complexity constituent codes are studied. The main area of focus is the optimization of the underlying irregular binary LDPC codes and their matching with constituent codes. Finite length random coding bound on the maximum-likelihood decoding error probability of a random ensemble of irregular GLDPC codes is derived and compared with a similar bound for non-binary (NB) LDPC codes over small alphabets.A new algorithm for assigning columns of the parity-check matrix of a constituent code to nonzero elements of a base matrix of the quasi-cyclic (QC)-GLDPC code is presented. Examples of the constructed QC-GLDPC codes are given. The simulation results for frame error rate (FER) performance of the belief-propagation (BP) decoding for the QC-GLDPC codes are presented and compared with the same performance of NB QC-LDPC codes over small alphabets and binary LDPC codes in the WiFi and 5G standards.Both GLDPC codes and NB LDPC codes with sufficiently low decoding complexity are shown to outperform their binary LDPC counterparts, while GLDPC codes appear to be more advantageous in terms of decoding complexity.