In this paper, we use a column-wise, row-wise approach for efficiently choosing reliable messages in decoding non-binary Low-Density Parity-Check (LDPC) codes, and build configurations with those reliable messages for updating check nodes. This method decreases the number of configurations compared to conventional trellis-based decoding algorithms. In addition, a novel algorithm with precomputed messages is proposed which improves decoding performance. Using the reduced configuration set with the improved message updating scheme it is shown that we can achieve an improved decoding performance while reducing the hardware complexity. Compared to trellis-based decoders, the proposed decoder reduces the number of required operations in computing check-to-variable messages and achieves better error-correcting performance.
In this paper, we use a column-wise, row-wise approach for efficiently choosing reliable messages in decoding non-binary Low-Density Parity-Check (LDPC) codes, and build configurations with those reliable messages for updating check nodes. This method decreases the number of configurations compared to conventional trellis-based decoding algorithms. In addition, a novel algorithm with precomputed messages is proposed which improves decoding performance. Using the reduced configuration set with the improved message updating scheme it is shown that we can achieve an improved decoding performance while reducing the hardware complexity. Compared to trellis-based decoders, the proposed decoder reduces the number of required operations in computing check-to-variable messages and achieves better error-correcting performance.
In this paper, we present an improvement and a new implementation of a simplified decoding algorithm for non-binary low density parity-check codes (NB-LDPC) in Galois fields GF(q). The base algorithm that we use is the Extended Min-Sum (EMS) algorithm, which has been widely studied in the recent literature, and has been shown to approach the performance of the belief propagation (BP) algorithm, with limited complexity. In our work, we propose a new way to compute modified configuration sets, using a trellis representation of incoming messages to check nodes. We call our modification of the EMS algorithm trellis-EMS (T-EMS). In the T-EMS, the algorithm operates directly on the deviation space by considering a trellis built from differential messages, which serves as a new reliability measure to sort the configurations. We show that this new trellis representation reduces the computational complexity, without any performance degradation. In addition, we show that our modifications of the algorithm allows to greatly reduce the decoding latency, by using a larger degree of hardware parallelization.
This paper presents a low complexity non-binary LDPC decoding algorithm,whose complexity can be reduced in the following two ways.First,a new truncation scheme is presented to define the processing/non-processing check node subsets.The check nodes with relatively high reliability are not required to be processed,which can reduce the complexity.Second,for the check nodes in the processing subset,we further present a k-order message truncation for the states and branches of the check node Trellis.In the decoding iterations,only those live states/branches are involved in the message updating process,which can further reduce the computational loads at check nodes.Simulation results show that the presented algorithm performs very closely to several existing improved EMS decoding algorithms,but it has the lowest complexity when decoding the non-binary LDPC codes constructed both in low/high order fields.%
In the check node (CN) update of non-binary message-passing algorithms, each element of reliability vectors takes the same computational complexity. However, our analysis indicates that various elements in the same vector have various correct probabilities, thus have different contributions to error performance. In order to match computational complexity with correct probability, all elements in a vector are partitioned into different sets. For the extended min-sum (EMS) decoding, various strategies are applied for sets according to their correct probability. For the trellis-based EMS decoding, it is interesting that set partition only involves fixed paths, thus it does not need to search over the whole trellis of a CN. Complexity analysis and simulation results show that the proposed algorithms efficiently decode non-binary low-density parity-check codes, including ultra-sparse ones.
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 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.
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.