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 decoding algorithm with reduced complexity for non-binary LDPC codes over large fields

Jun Ting Lin, Zhiyuan Yan

Published May 1, 2013• 2 citations
Publisher

Abstract

Non-binary low-density parity-check (NB-LDPC) codes outperform their binary counterparts in some cases, but their high decoding complexity is a significant hurdle to their applications. In this paper, we propose a decoding algorithm with reduced computational complexities and smaller memory requirements for NB-LDPC codes over large fields. First, a simplified algorithm is proposed to reduce the computational complexity of variable node processing. To reduce memory requirements, existing NB-LDPC decoders often truncate the message vectors to a limited number nmof values. However, the memory requirements of these decoders remain high when the field size is large, since nmneeds to be large enough to alleviate error performance degradation. In this paper, an improved trellised based check node processing algorithm is proposed to significantly reduce the memory requirement. The number of elements in a variable-to-check message is reduced to nv(nvm). The sorted log likelihood ratio (LLR) vector of a check-to-variable message is approximated using a piece-wise linear function. Thus, only few LLRs are stored and other LLRs are computed on-the-fly when needed. For each a priori message, most LLRs are approximated with a linear function. Our numerical results demonstrate that the proposed decoding algorithm outperforms existing algorithms. Two LLR generation units (LGUs) are proposed to compute LLR vectors for check-to-variable messages, and the two LGUs require only a fraction of the area needed to store nmLLRs.

DOI
10.1109/iscas.2013.6572189

Related papers

Reduced-complexity check node processing for non-binary LDPC decoding

Xinmiao Zhang, Fang Cai

Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than their binary counterparts when the code length is moderate. Check node processing is one bottleneck in NB-LDPC decoding. Various techniques have been proposed to simplify the check node processing. Particularly, the computation complexity can be reduced by employing an iterative forward-backward scheme. However, this scheme requires large memory to store intermediate results. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding. The proposed scheme first chooses a limited number of variable-to-check messages, then the check-to-variable messages to all connected variable nodes are generated independently. Employing the proposed architecture, the area requirement of the check node processing for an (837, 726) NB-LDPC code over GF (25) can be reduced to 22.5% of that of the previous work with the same processing speed and error-correcting performance.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2010•2 citations

Reduced-Complexity Decoder Architecture for Non-Binary LDPC Codes

Xinmiao Zhang, Fang Cai

Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes when the code length is moderate at the cost of higher decoding complexity. The high complexity is mainly caused by the complicated computations in the check node processing and the large memory requirement. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding algorithm. The proposed scheme first sorts out a limited number of the most reliable variable-to-check (v-to-c) messages, then the check-to-variable (c-to-v) messages to all connected variable nodes are derived independently from the sorted messages without noticeable performance loss. Compared to the previous iterative forward-backward check node processing, the proposed scheme not only significantly reduced the computation complexity, but eliminated the memory required for storing the intermediate messages generated from the forward and backward processes. Inspired by this novel c-to-v message computation method, we propose to store the most reliable v-to-c messages as “compressed” c-to-v messages. The c-to-v messages will be recovered from the compressed format when needed. Accordingly, the memory requirement of the overall decoder can be substantially reduced. Compared to the previous Min-max decoder architecture, the proposed design for a (837, 726) code overGF(25) can achieve the same throughput with only 46% of the area.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•May 12, 2010•83 citations

Reduced-complexity extended Min-sum check node processing for non-binary LDPC decoding

Xinmiao Zhang, Fang Cai

Non-binary low-density parity-check (NB-LDPC) codes can achieve higher coding gain than binary LDPC codes when the code length is moderate at the cost of higher complexity. One major step of NB-LDPC decoding is check node processing. Previously, iterative forward-backward approaches are employed to implement this step. However, the storage of the intermediate results of the forward and backward computations requires large memory. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the extended Min-sum NB-LDPC decoding. The proposed scheme only stores a limited number of sorted variable-to-check messages. Then the check-to-variable messages for different variable node are generated independently. For a (837, 726) NB-LDPC code over GF(25), the proposed architecture only requires 64% of the area of the previous design with the same throughput and error-correcting performance.

IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)•Aug 1, 2010•5 citations

Reduced-memory forward-backward check node processing architecture for non-binary LDPC decoding

Xinmiao Zhang, Fang Cai

When the code length is moderate, non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than their binary counterparts at the cost of higher decoding complexity. The check node processing is a major bottleneck of NB-LDPC decoding. Its computation complexity can be reduced by an iterative forward-backward scheme. Nevertheless, large memory is required in this scheme to store intermediate results. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding. The proposed scheme first sorts out a limited number of the most reliable input messages. Then the forward and backward processes are carried out using only these messages. In addition, an innovative approach is developed to derive the output messages from only a small number of intermediate results without noticeable performance loss. Accordingly, both the memory requirement and computation complexity are greatly reduced. For an example (837, 726) NB-LDPC code over GF(25), our proposed check node processing architecture can achieve at least 34% area reduction and about the same throughput compared to previous efforts based on the original forward-backward scheme.

IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)•Aug 1, 2011•3 citations

Memory-Reduced Non-Binary LDPC Decoding With Accumulative Bubble Check

Injun Choi, Ji-Hoon Kim

Non-binary (NB) low-density parity check (LDPC) codes offer stronger error correcting capability than binary LDPC codes. However, the improvement is accompanied by a considerable increase in the decoding complexity and a huge memory requirement, especially in the check node (CN). To overcome these limitations, we propose a memory-reduced NB-LDPC decoding method with an accumulative bubble check (a-bubble check) algorithm. The proposed a-bubble check reduces the memory requirements of the CNs by using the differences between the log-likelihood ratio entries. In addition, we propose a non-uniform memory structure to further decrease the memory capacity of the CN processor. For the GF(64)(160, 80) NB-LDPC code, the proposed memory-reduced NB-LDPC decoding architecture achieves a memory requirement reduction of 32.4% for the CNs and 16.2% for the entire decoder without degrading the error correction capability.

IEEE Transactions on Circuits & Systems II Express Briefs•Oct 10, 2017•4 citations

Reduced-Complexity Decoding of LDPC Codes

Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.

IEEE Transactions on Communications•Jul 1, 2005•27 citations
Non-binary low-density parity-check (NB-LDPC) codes outperform their binary counterparts in some cases, but their high decoding complexity is a significant hurdle to their applications. In this paper, we propose a decoding algorithm with reduced computational complexities and smaller memory requirements for NB-LDPC codes over large fields. First, a simplified algorithm is proposed to reduce the computational complexity of variable node processing. To reduce memory requirements, existing NB-LDPC decoders often truncate the message vectors to a limited number nmof values. However, the memory requirements of these decoders remain high when the field size is large, since nmneeds to be large enough to alleviate error performance degradation. In this paper, an improved trellised based check node processing algorithm is proposed to significantly reduce the memory requirement. The number of elements in a variable-to-check message is reduced to nv(nvm). The sorted log likelihood ratio (LLR) vector of a check-to-variable message is approximated using a piece-wise linear function. Thus, only few LLRs are stored and other LLRs are computed on-the-fly when needed. For each a priori message, most LLRs are approximated with a linear function. Our numerical results demonstrate that the proposed decoding algorithm outperforms existing algorithms. Two LLR generation units (LGUs) are proposed to compute LLR vectors for check-to-variable messages, and the two LGUs require only a fraction of the area needed to store nmLLRs.
Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than their binary counterparts when the code length is moderate. Check node processing is one bottleneck in NB-LDPC decoding. Various techniques have been proposed to simplify the check node processing. Particularly, the computation complexity can be reduced by employing an iterative forward-backward scheme. However, this scheme requires large memory to store intermediate results. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding. The proposed scheme first chooses a limited number of variable-to-check messages, then the check-to-variable messages to all connected variable nodes are generated independently. Employing the proposed architecture, the area requirement of the check node processing for an (837, 726) NB-LDPC code over GF (25) can be reduced to 22.5% of that of the previous work with the same processing speed and error-correcting performance.
Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes when the code length is moderate at the cost of higher decoding complexity. The high complexity is mainly caused by the complicated computations in the check node processing and the large memory requirement. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding algorithm. The proposed scheme first sorts out a limited number of the most reliable variable-to-check (v-to-c) messages, then the check-to-variable (c-to-v) messages to all connected variable nodes are derived independently from the sorted messages without noticeable performance loss. Compared to the previous iterative forward-backward check node processing, the proposed scheme not only significantly reduced the computation complexity, but eliminated the memory required for storing the intermediate messages generated from the forward and backward processes. Inspired by this novel c-to-v message computation method, we propose to store the most reliable v-to-c messages as “compressed” c-to-v messages. The c-to-v messages will be recovered from the compressed format when needed. Accordingly, the memory requirement of the overall decoder can be substantially reduced. Compared to the previous Min-max decoder architecture, the proposed design for a (837, 726) code overGF(25) can achieve the same throughput with only 46% of the area.
Non-binary low-density parity-check (NB-LDPC) codes can achieve higher coding gain than binary LDPC codes when the code length is moderate at the cost of higher complexity. One major step of NB-LDPC decoding is check node processing. Previously, iterative forward-backward approaches are employed to implement this step. However, the storage of the intermediate results of the forward and backward computations requires large memory. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the extended Min-sum NB-LDPC decoding. The proposed scheme only stores a limited number of sorted variable-to-check messages. Then the check-to-variable messages for different variable node are generated independently. For a (837, 726) NB-LDPC code over GF(25), the proposed architecture only requires 64% of the area of the previous design with the same throughput and error-correcting performance.
When the code length is moderate, non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than their binary counterparts at the cost of higher decoding complexity. The check node processing is a major bottleneck of NB-LDPC decoding. Its computation complexity can be reduced by an iterative forward-backward scheme. Nevertheless, large memory is required in this scheme to store intermediate results. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding. The proposed scheme first sorts out a limited number of the most reliable input messages. Then the forward and backward processes are carried out using only these messages. In addition, an innovative approach is developed to derive the output messages from only a small number of intermediate results without noticeable performance loss. Accordingly, both the memory requirement and computation complexity are greatly reduced. For an example (837, 726) NB-LDPC code over GF(25), our proposed check node processing architecture can achieve at least 34% area reduction and about the same throughput compared to previous efforts based on the original forward-backward scheme.
Non-binary (NB) low-density parity check (LDPC) codes offer stronger error correcting capability than binary LDPC codes. However, the improvement is accompanied by a considerable increase in the decoding complexity and a huge memory requirement, especially in the check node (CN). To overcome these limitations, we propose a memory-reduced NB-LDPC decoding method with an accumulative bubble check (a-bubble check) algorithm. The proposed a-bubble check reduces the memory requirements of the CNs by using the differences between the log-likelihood ratio entries. In addition, we propose a non-uniform memory structure to further decrease the memory capacity of the CN processor. For the GF(64)(160, 80) NB-LDPC code, the proposed memory-reduced NB-LDPC decoding architecture achieves a memory requirement reduction of 32.4% for the CNs and 16.2% for the entire decoder without degrading the error correction capability.
Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.