Non-binary low-density parity-check (NB-LDPC) codes exhibit excellent error correction performance at the cost of high computational complexity of the decoding algorithm. A logarithmic quantization scheme is proposed to reduce the VLSI implementation cost of the Min-Max decoding algorithm, by scaling down the complexity of the check node calculations that are the prime bottleneck in NB-LDPC decoding. The proposed scheme is also shown to be robust against certain types of errors, and thus enables excellent error correction capabilities even for aggressively reduced wordlengths, relative to traditional, uniform quantization schemes that exhibit either poor waterfall region performance or high error floors for a similar number of bits. The proposed scheme is directly applicable to existing architectures with few modifications and is shown to reduce the computational complexity by up to 40%, especially for large field orders.
Non-binary low-density parity-check (NB-LDPC) codes exhibit excellent error correction performance at the cost of high computational complexity of the decoding algorithm. A logarithmic quantization scheme is proposed to reduce the VLSI implementation cost of the Min-Max decoding algorithm, by scaling down the complexity of the check node calculations that are the prime bottleneck in NB-LDPC decoding. The proposed scheme is also shown to be robust against certain types of errors, and thus enables excellent error correction capabilities even for aggressively reduced wordlengths, relative to traditional, uniform quantization schemes that exhibit either poor waterfall region performance or high error floors for a similar number of bits. The proposed scheme is directly applicable to existing architectures with few modifications and is shown to reduce the computational complexity by up to 40%, especially for large field orders.
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.
Binary Low-Density Parity-Check (LDPC) codes are a type of error correction code known to exhibit excellent error-correcting capabilities, and have increasingly been applied as the forward error correction solution in a multitude of systems and standards, such as wireless communications, wireline communications, and data storage systems. In the pursuit of codes with even higher coding gain, non-binary LDPC (NB-LDPC) codes defined over a Galois field of order q have risen as a strong replacement candidate. For codes defined with similar rate and length, NB-LDPC codes exhibit a significant coding gain improvement relative to that of their binary counterparts.Unfortunately, NB-LDPC codes are currently limited from practical application by the immense complexity of their decoding algorithms, because the improved error-rate performance of higher field orders comes at the cost of increasing decoding algorithm complexity. Currently available ASIC implementation solutions for NB-LDPC code decoders are simultaneously low in throughput and power-hungry, leading to a low energy efficiency.We propose several techniques at the algorithm level as well as hardware architecture level in an attempt to bring NB-LDPC codes closer to practical deployment. On the algorithm side, we propose several algorithmic modifications and analyze the corresponding hardware cost alleviation as well as impact on coding gain. We also study the quantization scheme for NB-LDPC decoders, again in the context of both the hardware and coding gain impacts, and we propose a technique that enables a good tradeoff in this space. On the hardware side, we develop a FPGA-based NB-LDPC decoder platform for architecture prototyping as well as hardware acceleration of code evaluation via error rate simulations. We also discuss the architectural techniques and innovations corresponding to our proposed algorithm for optimization of the implementation. Finally, a proof-of-concept ASIC chip is realized that integrates many of the proposed techniques. We are able to achieve a 3.7x improvement in the information throughput and 23.8x improvement in the energy efficiency over prior state-of-the-art, without sacrificing the strong error correcting capabilities of the NB-LDPC code.
Compared to binary low-density parity-check (LDPC) codes, nonbinary (NB) LDPC codes can achieve higher coding gain when the codeword length is moderate, but at the cost of higher decoding complexity. One major bottleneck of NB-LDPC decoding is the complicated check node processing. In this paper, a novel relaxed check node processing scheme is proposed for the min-max NB-LDPC decoding algorithm. Each finite field element of GF(2p) can be uniquely represented by a linear combination of p independent field elements. Making use of this property, an innovative method is developed in this paper to first find a set of the p most reliable variable-to-check messages with independent field elements, called the minimum basis. Then, the check-to-variable messages are efficiently computed from the minimum basis. With very small performance loss, the complexity of the check node processing can be substantially reduced using the proposed scheme. In addition, efficient VLSI architectures are developed to implement the proposed check node processing and the overall NB-LDPC decoder. Compared to the most efficient prior design, the proposed decoder for a (837, 726) NB-LDPC code over GF(25) can achieve 52% higher efficiency in terms of throughput-over-area ratio.
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 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.