Efficient VLSI Architectures for Non-binary Low Density Parity Check Decoding

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 thesis, two VLSI designs for NB-LDPC decoders based on two novel check node processing schemes are proposed.The first design is based on forward-backward check node processing. A novel scheme and corresponding architecture are developed to implement the elementary step of the check node processing. In our design, layered decoding is applied and only nm less than q messages are kept on each edge of the associated Tanner graph. The computation units and the scheduling of the computations are optimized in the context of layered decoding to reduce the area requirement and increase the speed. This thesis also introduces an overlapped method for the check node processing among different layers to further speed up the decoding. From complexity and latency analysis, our design is much more efficient than any previous design. Our proposed decoder for a (744, 653) code over GF(32) has also been synthesized on a Xilinx Virtex-2 Pro FPGA device. It can achieve a throughput of 9.30 Mbps when 15 decoding iterations are carried out.The second design is based on a proposed trellis based check node processing scheme. 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 over GF(32) can achieve the same throughput with only 46% of the area.