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 \nparity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding \nalgorithms for binary LDPC codes. \nWe first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q) \nbased on message-passing algorithms. Short cycles in an NB-LDPC code may be even \nmore harmful to its performance if they do not satisfy the so-called full rank condition \n(FRC). This is because they may induce low-weight codewords or absorbing sets in that \ncase. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as \nthe number of short cycles for analyzing the performance of an NB-LDPC code. In order to \ncount those cycles, we first develop a novel message-passing algorithm and identify how it \nis related to the FRC.We then propose a low-complexity algorithmfor counting the number \nof short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short \ncycles. The proposed algorithm is not only theoretically validated, but its computational \nand storage complexities are also computed. It does not require cycle enumeration with \nhigh complexity, and therefore is still feasible even in the case of large code length, say \n≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal \nrule to choose a nonzero element for a given edge and propose a low-complexity algorithm \nfor designing an NB-LDPC code with low error floor. Furthermore, several design examples \nare presented to verify the validity of the proposed design algorithm. \nSecondly, we propose a low-complexity decoding algorithm for binary LDPC codes over \nthe binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding \nalgorithm for binary LDPC codes and has lower computational complexity than the \nsum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it \nhas performance degradation. Furthermore, reducing the number of bits for representing \nmessages to two in a decoding algorithm for further reducing computational and storage \ncomplexities, causes significant performance losses. In order to minimize the performance \ndegradation and computational and storage complexities, we propose a low-complexity \ndecoding algorithm which uses several decoders with two-bit precision for binary LDPC \ncodes over the BSC. The proposed algorithm adaptively changes decoders according to \nthe number of unsatisfied check nodes at each iteration. Compared with the SPA using \nfloating-point operations, the proposed decoding algorithm greatly reduces computational \nand storage complexities with negligible performance losses. Numerical results show that \nthe proposed decoding algorithm has similar performance to the SPA with floating-point \noperations over the BSC. \nIn the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes \nfor the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms \nB (GDB) and E (GDE) for binary LDPC codes have much lower computational \ncomplexity and much less required memory size than the SPA. This is because GDB and \nGDE only use binary or integer operations, while the SPA requires real operations and \na look-up table. However, they are hardly used in commercial communication systems \nsince they have poorer performance than the SPA. Layered-division multiplexing (LDM) \nis considered in ATSC 3.0 in order to deliver multiple broadcasting streams with distinct \nrobustness in a single radio frequency channel. Due to the unique characteristic of the \nLDM, we propose to use GDB or GDE rather than the SPA for decoding the core layer signal \nat fixed receivers. Numerical results show that the computational complexity and the \nrequired memory size can be reduced without any performance loss by about 50 percent \nand 80 percent, respectively, when GDB and GDE are employed.

•Jan 1, 2018•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

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

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

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
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 \nparity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding \nalgorithms for binary LDPC codes. \nWe first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q) \nbased on message-passing algorithms. Short cycles in an NB-LDPC code may be even \nmore harmful to its performance if they do not satisfy the so-called full rank condition \n(FRC). This is because they may induce low-weight codewords or absorbing sets in that \ncase. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as \nthe number of short cycles for analyzing the performance of an NB-LDPC code. In order to \ncount those cycles, we first develop a novel message-passing algorithm and identify how it \nis related to the FRC.We then propose a low-complexity algorithmfor counting the number \nof short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short \ncycles. The proposed algorithm is not only theoretically validated, but its computational \nand storage complexities are also computed. It does not require cycle enumeration with \nhigh complexity, and therefore is still feasible even in the case of large code length, say \n≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal \nrule to choose a nonzero element for a given edge and propose a low-complexity algorithm \nfor designing an NB-LDPC code with low error floor. Furthermore, several design examples \nare presented to verify the validity of the proposed design algorithm. \nSecondly, we propose a low-complexity decoding algorithm for binary LDPC codes over \nthe binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding \nalgorithm for binary LDPC codes and has lower computational complexity than the \nsum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it \nhas performance degradation. Furthermore, reducing the number of bits for representing \nmessages to two in a decoding algorithm for further reducing computational and storage \ncomplexities, causes significant performance losses. In order to minimize the performance \ndegradation and computational and storage complexities, we propose a low-complexity \ndecoding algorithm which uses several decoders with two-bit precision for binary LDPC \ncodes over the BSC. The proposed algorithm adaptively changes decoders according to \nthe number of unsatisfied check nodes at each iteration. Compared with the SPA using \nfloating-point operations, the proposed decoding algorithm greatly reduces computational \nand storage complexities with negligible performance losses. Numerical results show that \nthe proposed decoding algorithm has similar performance to the SPA with floating-point \noperations over the BSC. \nIn the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes \nfor the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms \nB (GDB) and E (GDE) for binary LDPC codes have much lower computational \ncomplexity and much less required memory size than the SPA. This is because GDB and \nGDE only use binary or integer operations, while the SPA requires real operations and \na look-up table. However, they are hardly used in commercial communication systems \nsince they have poorer performance than the SPA. Layered-division multiplexing (LDM) \nis considered in ATSC 3.0 in order to deliver multiple broadcasting streams with distinct \nrobustness in a single radio frequency channel. Due to the unique characteristic of the \nLDM, we propose to use GDB or GDE rather than the SPA for decoding the core layer signal \nat fixed receivers. Numerical results show that the computational complexity and the \nrequired memory size can be reduced without any performance loss by about 50 percent \nand 80 percent, respectively, when GDB and GDE are employed.
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.
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.
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.
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.