IEEE Transactions on Circuits & Systems II Express Briefs

An Area-Efficient Relaxed Half-Stochastic Decoding Architecture for Nonbinary LDPC Codes

Xin-Ru Lee, Chih‐Wen Yang, Chih-Lung Chen, Hsie-Chia Chang, Chen‐Yi Lee

Published Nov 7, 2014• 4 citations

Abstract

This brief presents an area-efficient relaxed half-stochastic nonbinary low-density parity-check (NB-LDPC) decoder. A novel decoding algorithm, namely, cumulative tracking forecast memory with concealing channel values (CTFM-CC) is proposed to reduce algorithm complexity and maintain bit-error-rate performance as well. Furthermore, the hardware complexity of variable node units (VNUs) is reduced through a truncated architecture, which only keeps the most reliable n probability density functions. To deal with the sum-product-algorithm-to-stochastic conversion of VNU, a dynamic random number generation method, which is used for sampling a stochastic symbol, is also proposed. With these features, a (168, 84) regular-(2,4) NB-LDPC code over GF(16) decoder is implemented in a 90-nm process. According to the results of postlayout simulation, this decoder can deliver a throughput of 1.13 Gb/s with a hardware efficiency of 0.90 Mb/s/K-gate at 286 MHz. Compared to related rate-1/2 NB-LDPC decoders, the proposed decoder achieves the highest hardware efficiency with similar error-correcting capability.

DOI: 10.1109/tcsii.2014.2368616

Related papers

Simplified Variable Node Unit Architecture for Nonbinary LDPC Decoder

Huyen Pham Thi, The Cuong Dinh, Xuan Nghia Pham +2 more

Nonbinary low-density-parity-check (NB-LDPC) code outperforms their binary counterpart in terms of error-correcting performance and error-floor property when the code length is moderate. However, the drawback of NB-LDPC decoders is high complexity and the complexity increases considerably when increasing the Galois-field order. In this paper, a simplified basic-set trellis min-max (sBS-TMM) algorithm that is especially efficient for high-order Galois Fields, is proposed for the variable node processing to reduce the complexity of the variable node unit (VNU) as well as the whole decoder. The decoder architecture corresponding to the proposed algorithm is designed for the (837, 726) NB-LDPC code over GF(32). The implementation results using 90-nm CMOS technology show that the proposed decoder architecture reduces the gate count by 21.35% and 9.4% with almost similar error-correcting performance, compared to the up-to-date works.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)Nov 1, 20192 citations

Relaxed Min-Max Decoder Architectures for Nonbinary Low-Density Parity-Check Codes

Fang Cai, Xinmiao Zhang

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.

IEEE Transactions on Very Large Scale Integration (VLSI) SystemsDec 4, 201240 citations

A 21.66 Gbps Nonbinary LDPC Decoder for High-Speed Communications

Jing Tian, Jun Ting Lin, Zhongfeng Wang

Compared to binary Low-Density Parity-Check (LDPC) codes, nonbinary LDPC (NB-LDPC) codes have better error correction performance under short-to-moderate block lengths or high-order modulations. Traditional min-sum-based soft decoding algorithms for NB-LDPC codes suffer from large computational complexity, which leads to inefficient hardware implementations. The Multiple-symbol-reliability weighted Bit-Reliability-Based (MwBRB) hard decoding algorithm achieves a good tradeoff between error correction performance and decoding complexity. However, efficient hardware implementations based on the MwBRB algorithm have not been investigated. In this brief, an improved layered MwBRB algorithm is first proposed, which results in faster convergence rate than the MwBRB algorithm. Then, an ultra-high-throughput low-complexity decoder architecture with an efficient partially parallel processing schedule is also presented. Finally, the proposed architecture is coded with RTL and synthesized under the TSMC 90-nm CMOS technology. The synthesis results demonstrate that the proposed decoder for a (837, 726) quasi-cyclic NB-LDPC code over GF(25) achieves a throughput of 21.66 Gbps and an area efficiency of 4.77 Gbps/M-gates under the TSMC 90-nm CMOS technology. The proposed decoder reaches a throughput more than 20 Gbps for the first time among the prior NB-LDPC decoders, and the area efficiency is far beyond the state-of-the-art designs.

IEEE Transactions on Circuits & Systems II Express BriefsMay 19, 201710 citations

Stochastic Decoding of LDPC Codes over GF(q)

Gabi Sarkis, Saied Hemati, Shie Mannor +1 more

Despite the outstanding performance of non-binary low-density parity-check (LDPC) codes over many communication channels, they are not in widespread use yet. This is due to the high implementation complexity of their decoding algorithms, even those that compromise performance for the sake of simplicity. In this paper, we present three algorithms based on stochastic computation to reduce the decoding complexity. The first is a purely stochastic algorithm with error-correcting performance matching that of the sum-product algorithm (SPA) for LDPC codes over Galois fields with low order and a small variable node degree. We also present a modified version which reduces the number of decoding iterations required while remaining purely stochastic and having a low per-iteration complexity. The second algorithm, relaxed half-stochastic (RHS) decoding, combines elements of the SPA and the stochastic decoder and uses successive relaxation to match the error-correcting performance of the SPA. Furthermore, it uses fewer iterations than the purely stochastic algorithm and does not have limitations on the field order and variable node degree of the codes it can decode. The third algorithm, NoX, is a fully stochastic specialization of RHS for codes with a variable node degree 2 that offers similar performance, but at a significantly lower computational complexity. We study the performance and complexity of the algorithms; noting that all have lower per-iteration complexity than SPA and that RHS can have comparable average per-codeword computational complexity, and NoX a lower one.

IEEE Transactions on CommunicationsFeb 6, 201327 citations

Efficient Shuffled Decoder Architecture for Nonbinary Quasi-Cyclic LDPC Codes

Jun Ting Lin, Zhiyuan Yan

In this brief, a shuffled schedule (SS) of the min-max decoding algorithm is proposed for nonbinary low-density parity-check (LDPC) codes. To increase the throughput and reduce the memory requirement, a modified SS (MSS) with much simpler check node processing is also proposed, based on a new shuffled merge algorithm. Numerical simulations for three LDPC codes with different lengths and rates over GF(32) show: 1) both SS and MSS converge faster and have slightly better error performance than the flooding schedule, and 2) the degradation of the MSS in error performance as well as convergence rate is negligible. Finally, an efficient decoder architecture based on the MSS is proposed for quasi-cyclic LDPC codes. The proposed decoder architecture further enhances the decoding throughput with improved check and variable node processing units. The implementation results of an (837, 726) LDPC decoder over GF(32) demonstrate that the proposed architecture outperforms those in previous works.

IEEE Transactions on Very Large Scale Integration (VLSI) SystemsOct 18, 201220 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) SystemsMay 12, 201083 citations