In comparison to the forward-backward update of extended min-sum (EMS) algorithm, the trellis EMS (T-EMS) algorithm for non-binary low density parity check codes (NB-LDPC) introduces an extra trellis column during check nodes (CNs) updates, significantly enhancing parallelism and facilitating hardware implementation. However, in high-order or high code rate scenarios, the T-EMS algorithm exhibits considerable latency caused by excessive configurations searching for the largest reliability selection. To address this, the paper propose an enhanced algorithm, named as path reduction T-EMS (RT-EMS) algorithm, to simplify the configuration space through applying an additional filtering to the elements in each column of the trellis, retaining only the elements that are deemed more trustworthy from the column’s perspective. Moreover, a data compensation strategy is also proposed to tackle the data scarcity issues for some syndrome values in the extra trellis column. Finally, the simulation results demonstrate that RT-EMS algorithm can achieve more than 50% complexity reduction with a negligible performance degradation.
In comparison to the forward-backward update of extended min-sum (EMS) algorithm, the trellis EMS (T-EMS) algorithm for non-binary low density parity check codes (NB-LDPC) introduces an extra trellis column during check nodes (CNs) updates, significantly enhancing parallelism and facilitating hardware implementation. However, in high-order or high code rate scenarios, the T-EMS algorithm exhibits considerable latency caused by excessive configurations searching for the largest reliability selection. To address this, the paper propose an enhanced algorithm, named as path reduction T-EMS (RT-EMS) algorithm, to simplify the configuration space through applying an additional filtering to the elements in each column of the trellis, retaining only the elements that are deemed more trustworthy from the column’s perspective. Moreover, a data compensation strategy is also proposed to tackle the data scarcity issues for some syndrome values in the extra trellis column. Finally, the simulation results demonstrate that RT-EMS algorithm can achieve more than 50% complexity reduction with a negligible performance degradation.
Non-binary low-density parity-check (NB-LDPC) codes show larger coding gain and lower error floor than their binary counterparts in many cases. However, the existing soft decoding algorithms of NB-LDPC codes generally suffer from high computational complexity. Recently, the trellis-based extended min-sum (T-EMS) decoding algorithm has attracted much attention since it can achieve good decoding performance with high parallelism and low computational complexity. In this paper, we propose two new methods to further reduce the computational complexity and enhance the decoding performance. Firstly, we introduce, with theoretical justification, a universal scheme called threshold-based shrinking (TS) scheme, which facilitates significant reduction of computational complexity for decoding of NB-LDPC codes. Secondly, we present a modified two-extra-column (TEC) scheme and apply it to the T-EMS. Furthermore, a high-performance low-complexity decoding algorithm, named TEC-TEMS algorithm, is obtained. Combining the TS scheme with the TEC-TEMS, the new algorithm, named TS-TEC-TEMS algorithm, achieves much lower computational complexity and has negligible performance loss compared to the TEC-TEMS. For a 256-ary (256, 203) example code, compared to the T-EMS, the computational complexities of the TEC-TEMS and TS-TEC-TEMS algorithms are reduced by more than 50% and nearly 90%, respectively. Moreover, the TEC-TEMS and TS-TEC-TEMS both outperform the T-EMS by about 0.3dB when the frame error rate (FER) is around 10-5.
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.
In this paper, we proposed a modified Trellis extended min-sum (T-EMS) algorithm with L truncations for non-binary low density parity check (NB-LDPC) codes. The proposed algorithm achieves to reduce complexity of T-EMS algorithm, especially on large order Galois fields GF(q). In order to improve the error-correcting performance of the algorithm, an elitist selection (ES) strategy is presented, which enlarges the belief value of the selected symbols. As a proof, the simulation results and complexity analysis show that with the increase of q, the complexity decreases obviously. However, in the case of a suitable L value, the LT-EMS algorithm with ES strategy is not inferior to the T-EMS algorithm in performance. In addition, the ES strategy can accelerate the convergence rate and reduce the number of iterations of the decoding process, which will enhance the decoding throughput.
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 paper, we propose a new method to implement the Extended Min-Sum (EMS) algorithm based on trellis representation of inputting messages to the check node. The original EMS reduces the decoding complexity by choosing only nmmost reliable values and by introducing the idea of configuration sets conf(nm, nc), where ncis the number of deviations from the most reliable output configuration. We propose to work directly on the deviation space by building a configuration trellis based on delta messages, which serves as a new reliability measure. The algorithm is called trellis-EMS (T-EMS). By using the new trellis representation, only nc+1 minimum values from each row of the trellis need to be considered, which reduces the ordering complexity. The trellis representation in the deviation space also reduces the number of output configurations tested, without any performance degradation. Our method is especially suitable for moderate field size q and large check node degree nonbinary LDPC codes.
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.