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.00734

Binary Representaion for Non-binary LDPC Code with Decoder Design

Yang Yu, Wen Chen, Jun Li, Xiao Ma, Baoming Bai

Published Mar 2, 2020• 1 citation
arXivHTMLPDF

Abstract

The equivalent binary parity check matrices for the binary images of the cycle-free non-binary LDPC codes have numerous bit-level cycles. In this paper, we show how to transform these binary parity check matrices into their cycle-free forms. It is shown that the proposed methodology can be adopted not only for the binary images of non-binary LDPC codes but also for a large class of binary LDPC codes. Specifically, we present an extended $p$-reducible (EPR) LDPC code structure to eliminate the bit-level cycles. For the non-binary LDPC codes with short length symbol-level cycles, the EPR-LDPC codes can largely avoid the corresponding short length bit-level cycles. As to the decoding of the EPR-LDPC codes, we propose a hybrid hard-decision decoder and a hybrid parallel decoder for binary symmetric channel and binary input Gaussian channel, respectively. A simple code optimization algorithm for these binary decoders is also provided. Simulations show the comparative results and justify the advantages, i.e., better performance and lower decoding complexity, of the proposed binary constructions.

DOI
10.48550/arxiv.2003.00734

Related papers

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

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

On Bit-Level Decoding of Nonbinary LDPC Codes

Mu Zhang, Kui Cai, Qin Huang +1 more

This paper addresses binary message-passing (MP) decoding for nonbinary low-density parity-check (NB-LDPC) codes based on the binary image of Galois field symbols. The parity-check matrix of NB-LDPC codes in binary form is used to perform MP. The corresponding nonbinary check node (CN) update and variable node (VN) update can thus be decomposed to a set of binary sub-CN updates and sub-VN updates with much lower computational complexity. In particular, we start from adapting the binary parity-check matrix with Gaussian elimination. Then, we add redundant rows to the parity-check matrix instead of adaptation to further improve the performance. A min-max operation based on the expanded matrix is proposed for the CN update. It not only decreases the computational complexity incurred by Gaussian elimination but also improves the error performance. Simulation results show that the bit-level decoding with min-max operation can achieve similar error performance as the extended min-sum algorithm, but the computational complexity can be lower than the min-sum algorithm for binary LDPC codes.

IEEE Transactions on Communications•Apr 17, 2018•15 citations

Computation of Parity Check Matrices for Binary EG-LDPC Codes used in Communication Systems

Jyothi Chinna Babu, C. Chinnapu Reddy

The Low Density Parity Check (LDPC) are direct codes, which are true block and Shannon Limit codes.These codes are attained least error floors of data bits for data transfer applications used in communication systems.However, the proposed LDPC codes are more beneficial than Turbo codes because of reduction in the decoding complexity and detection of the errors in less cycle time.This results the reduction of decoding time, low decoding latency, complexity and as well as least error floorings in communication, when the transmitted data contains multiple error bits.This paper is proposed to represent the majority logic decoding/detecting of LDPC codes.This paper proposes the Generation of Originator and Parity estimated matrices for the Binary LDPC Codes.Here, the proposed techniques are hard decision decrypting and soft decision decrypting schemes.These schemes uses majority logic decoding based on the data transmission and reception in communication channel.This paper also elaborates the effective calculation of Euclidean distance and algorithm for constructing the LDPC codes.

Helix•Feb 28, 2019•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

Generalized Binary Representation for the Nonbinary LDPC Code With Decoder Design

Yang Yu, Wen Chen, Jun Li +2 more

In this paper, we consider the performance-optimized nonbinary low-density parity check code over general linear group, i.e.,$\bar{\cal C}$. A new methodology for constructing the binary representation [generalized binary representation (GBR)] of$\bar{\cal C}$is proposed, which can be optimized with regard to both degree distributions and girth. As to the decoding of the GBR, we develop a low-complexity hybrid parallel decoding process. It is shown that the decoding performance of the GBR under the proposed binary decoding process could closely approach the decoding performance of its mother code$\bar{\cal C}$under nonbinary belief propagation decoding. A simple code optimization algorithm for the GBR is also provided. Simulations show the comparative results and justify the advantages of the proposed constructions.

IEEE Transactions on Communications•Jul 30, 2014•6 citations
The equivalent binary parity check matrices for the binary images of the cycle-free non-binary LDPC codes have numerous bit-level cycles. In this paper, we show how to transform these binary parity check matrices into their cycle-free forms. It is shown that the proposed methodology can be adopted not only for the binary images of non-binary LDPC codes but also for a large class of binary LDPC codes. Specifically, we present an extended ppp-reducible (EPR) LDPC code structure to eliminate the bit-level cycles. For the non-binary LDPC codes with short length symbol-level cycles, the EPR-LDPC codes can largely avoid the corresponding short length bit-level cycles. As to the decoding of the EPR-LDPC codes, we propose a hybrid hard-decision decoder and a hybrid parallel decoder for binary symmetric channel and binary input Gaussian channel, respectively. A simple code optimization algorithm for these binary decoders is also provided. Simulations show the comparative results and justify the advantages, i.e., better performance and lower decoding complexity, of the proposed binary constructions.
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.
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 …
This paper addresses binary message-passing (MP) decoding for nonbinary low-density parity-check (NB-LDPC) codes based on the binary image of Galois field symbols. The parity-check matrix of NB-LDPC codes in binary form is used to perform MP. The corresponding nonbinary check node (CN) update and variable node (VN) update can thus be decomposed to a set of binary sub-CN updates and sub-VN updates with much lower computational complexity. In particular, we start from adapting the binary parity-check matrix with Gaussian elimination. Then, we add redundant rows to the parity-check matrix instead of adaptation to further improve the performance. A min-max operation based on the expanded matrix is proposed for the CN update. It not only decreases the computational complexity incurred by Gaussian elimination but also improves the error performance. Simulation results show that the bit-level decoding with min-max operation can achieve similar error performance as the extended min-sum algorithm, but the computational complexity can be lower than the min-sum algorithm for binary LDPC codes.
The Low Density Parity Check (LDPC) are direct codes, which are true block and Shannon Limit codes.These codes are attained least error floors of data bits for data transfer applications used in communication systems.However, the proposed LDPC codes are more beneficial than Turbo codes because of reduction in the decoding complexity and detection of the errors in less cycle time.This results the reduction of decoding time, low decoding latency, complexity and as well as least error floorings in communication, when the transmitted data contains multiple error bits.This paper is proposed to represent the majority logic decoding/detecting of LDPC codes.This paper proposes the Generation of Originator and Parity estimated matrices for the Binary LDPC Codes.Here, the proposed techniques are hard decision decrypting and soft decision decrypting schemes.These schemes uses majority logic decoding based on the data transmission and reception in communication channel.This paper also elaborates the effective calculation of Euclidean distance and algorithm for constructing the LDPC codes.
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 consider the performance-optimized nonbinary low-density parity check code over general linear group, i.e.,Cˉ\bar{\cal C}Cˉ. A new methodology for constructing the binary representation [generalized binary representation (GBR)] ofCˉ\bar{\cal C}Cˉis proposed, which can be optimized with regard to both degree distributions and girth. As to the decoding of the GBR, we develop a low-complexity hybrid parallel decoding process. It is shown that the decoding performance of the GBR under the proposed binary decoding process could closely approach the decoding performance of its mother codeCˉ\bar{\cal C}Cˉunder nonbinary belief propagation decoding. A simple code optimization algorithm for the GBR is also provided. Simulations show the comparative results and justify the advantages of the proposed constructions.