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

IEEE International Symposium on Circuits and Systems proceedings

A Novel Low-Complexity Joint Coding and Decoding Algorithm for NB-LDPC Codes

Suwen Song, Jing Tian, Jun Ting Lin, Zhongfeng Wang

Published May 1, 2019• 6 citations
Publisher

Abstract

Non-binary low-density parity-check (NB-LDPC) codes exhibit a much better performance than their binary counterparts, especially for moderate codeword length and high-order modulation. However, their decoding algorithms suffer from very high computational complexity. In this paper, a low-complexity algorithm is proposed, named parity-check erased algorithm (PCEA), where an additional parity check bit is added to each symbol of the codeword when encoding and a series of simple operations are performed based on these bits during decoding. As a universal joint coding and decoding algorithm, the PCEA can be combined with arbitrary NB-LDPC encoding schemes and decoding algorithms based on message passing. The proposed algorithm facilitates significant improvement of decoding performance with a small decrease of the code rate. Additionally, it usually has an even better performance than a nearly same-rate code constructed by the original method, and requires much lower decoding complexity due to smaller size of the parity check matrix.

DOI
10.1109/iscas.2019.8702165

Related papers

Hybrid Message-Passing Algorithm and Architecture for Decoding Cyclic Non-binary LDPC Codes

Yichao Lu, Gang He, Guifen Tian +1 more

Recently, non-binary low-density parity-check (NB-LDPC) codes starts to show their superiority in achieving significant coding gains when moderate codeword lengths are adopted. However, the overwhelming decoding complexity keeps NB-LDPC codes from being widely employed in modern communication devices. This paper proposes a hybrid message-passing decoding algorithm which consumes very low computational complexity. It achieves competitive error performance compared with conventional Min-max algorithm. Simulation result on a (255,174) cyclic code shows that this algorithm obtains at least 0.5dB coding gain over other state-of-the-art low-complexity NB-LDPC decoding algorithms. A partial-parallel NB-LDPC decoder architecture for cyclic NB-LDPC codes is also developed based on this algorithm. Optimization schemes are employed to cut off hard decision symbols in RAMs and also to store only part of the reliability messages. In addition, the variable node units are redesigned especially for the proposed algorithm. Synthesis results demonstrate that about 24.3% gates and 12% memories can be saved over previous works.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2013•0 citations

Parallel Symbol-Flipping Decoding for Non-Binary LDPC Codes

Chao-Cheng Huang, Chi‐Jen Wu, Chao‐Yu Chen +1 more

A new low-complexity parallel symbol-flipping decoding algorithm for non-binary low-density parity-check (NB-LDPC) codes is proposed. The algorithm outperforms quite a number of existing reliability-based message-passing algorithms, and its computation complexity is smaller than that of almost all the previously proposed iterative decoding algorithms for NB-LDPC codes. It is suitable for decoding NB-LDPC codes whose parity-check matrices have large column weights.

IEEE Communications Letters•Jun 1, 2013•25 citations

A reduced complexity decoding algorithm for NB-LDPC codes

Suwen Song, Jun Ting Lin, Jing Tian +1 more

Non-binary low-density parity-check (NB-LDPC) codes perform much better than their binary counterparts, when codeword length is moderate or high-order modulation is used. However, the implementation of a NB-LDPC decoder usually suffers from excessive hardware complexity and large memory requirement. Many new algorithms and decoding schedules have been introduced in recent literatures to reduce the decoding complexity in further. However, the complexity of current decoding algorithms for NB-LDPC codes is still high. In this paper, a two-extra-column trellis min-sum algorithm (TEC-TMSA) is proposed. The TEC-TMSA combines the two-extra-column method and the trellis min-sum algorithm in an intelligent way. Since only the minimum value of a row needs to be sorted out for configuration constructions, the computational complexity of the proposed TEC-TMSA is much lower than that of the TMSA. Furthermore, we develop a novel location-fixed selection scheme, which significantly decreases the number of required comparison operations in the TEC-TMSA with negligible performance loss.

IEEE International Conference on Communication Technology (ICCT)•Oct 1, 2017•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

Low-Complexity Symbol-Flipping Decoding Algorithms for Nonbinary LDPC Codes

박성현

Low-density parity-check (LDPC) codes have been shown to have near Shannon-limit performance when a probabilistic decoding is used and the code length goes to infinity. On the other hand, non-binary low-density parity-check (NB-LDPC) codes outperform binary LDPC codes for short code lengths. However, the coding gain of NB-LDPC codes comes from the expense of computational complexity. \n \nIn this thesis, we consider the problem of a trade-off between reasonable complexity and good error-rate performance of decoding nonbinary LDPC codes over GF($q$). We first introduce the existing decoding algorithms of nonbinary LDPC codes and compare with decoding algorithms of binary LDPC codes. Second, low-complexity decoding algorithms of nonbinary LDPC codes is considered and two low-complexity symbol-flipping algorithms based on D-SFDP is proposed. These algorithms outperform the existing D-SFDP algorithm by improving the flipping metric. Proposed algorithms provide good trade-off between complexity and error performance.

•Jan 1, 2018•0 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
Non-binary low-density parity-check (NB-LDPC) codes exhibit a much better performance than their binary counterparts, especially for moderate codeword length and high-order modulation. However, their decoding algorithms suffer from very high computational complexity. In this paper, a low-complexity algorithm is proposed, named parity-check erased algorithm (PCEA), where an additional parity check bit is added to each symbol of the codeword when encoding and a series of simple operations are performed based on these bits during decoding. As a universal joint coding and decoding algorithm, the PCEA can be combined with arbitrary NB-LDPC encoding schemes and decoding algorithms based on message passing. The proposed algorithm facilitates significant improvement of decoding performance with a small decrease of the code rate. Additionally, it usually has an even better performance than a nearly same-rate code constructed by the original method, and requires much lower decoding complexity due to smaller size of the parity check matrix.
Recently, non-binary low-density parity-check (NB-LDPC) codes starts to show their superiority in achieving significant coding gains when moderate codeword lengths are adopted. However, the overwhelming decoding complexity keeps NB-LDPC codes from being widely employed in modern communication devices. This paper proposes a hybrid message-passing decoding algorithm which consumes very low computational complexity. It achieves competitive error performance compared with conventional Min-max algorithm. Simulation result on a (255,174) cyclic code shows that this algorithm obtains at least 0.5dB coding gain over other state-of-the-art low-complexity NB-LDPC decoding algorithms. A partial-parallel NB-LDPC decoder architecture for cyclic NB-LDPC codes is also developed based on this algorithm. Optimization schemes are employed to cut off hard decision symbols in RAMs and also to store only part of the reliability messages. In addition, the variable node units are redesigned especially for the proposed algorithm. Synthesis results demonstrate that about 24.3% gates and 12% memories can be saved over previous works.
Non-binary low-density parity-check (NB-LDPC) codes perform much better than their binary counterparts, when codeword length is moderate or high-order modulation is used. However, the implementation of a NB-LDPC decoder usually suffers from excessive hardware complexity and large memory requirement. Many new algorithms and decoding schedules have been introduced in recent literatures to reduce the decoding complexity in further. However, the complexity of current decoding algorithms for NB-LDPC codes is still high. In this paper, a two-extra-column trellis min-sum algorithm (TEC-TMSA) is proposed. The TEC-TMSA combines the two-extra-column method and the trellis min-sum algorithm in an intelligent way. Since only the minimum value of a row needs to be sorted out for configuration constructions, the computational complexity of the proposed TEC-TMSA is much lower than that of the TMSA. Furthermore, we develop a novel location-fixed selection scheme, which significantly decreases the number of required comparison operations in the TEC-TMSA with negligible performance loss.
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.
Low-density parity-check (LDPC) codes have been shown to have near Shannon-limit performance when a probabilistic decoding is used and the code length goes to infinity. On the other hand, non-binary low-density parity-check (NB-LDPC) codes outperform binary LDPC codes for short code lengths. However, the coding gain of NB-LDPC codes comes from the expense of computational complexity. \n \nIn this thesis, we consider the problem of a trade-off between reasonable complexity and good error-rate performance of decoding nonbinary LDPC codes over GF(qqq). We first introduce the existing decoding algorithms of nonbinary LDPC codes and compare with decoding algorithms of binary LDPC codes. Second, low-complexity decoding algorithms of nonbinary LDPC codes is considered and two low-complexity symbol-flipping algorithms based on D-SFDP is proposed. These algorithms outperform the existing D-SFDP algorithm by improving the flipping metric. Proposed algorithms provide good trade-off between complexity and error performance.
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.