Scheduling-based Efficient LDPC Decoding Algorithm

Dongho Kim, Ye-Hoon Lee

Sangjoon Park

This paper proposes an efficient scheduling algorithm for the layered decoding of block low-density parity-check (LDPC) codes. To efficiently configure check node-based scheduling groups, the proposed algorithm utilizes the base matrix of the block LDPC code for a block-by-block scheduling group configuration; i.e., the proposed algorithm generates a scheduling group of check nodes, satisfying the weight condition of the layered decoding, which is performed in block units (including several check nodes). Therefore, unlike the conventional scheduling algorithms performed in node units, the proposed algorithm can efficiently generate scheduling groups for layered decoding at low computational complexity and memory requirements. In addition, to accelerate the decoding convergence speed, check nodes are allocated in each scheduling group such that messages from check nodes up to the current group are delivered as evenly as possible to bit nodes. Simulation results confirm that the proposed algorithm can accelerate decoding convergence compared to other block-based scheduling algorithms for layered decoding of block LDPC codes.

Vikram Arkalgud Chandrasetty, Syed Mahfuzul Aziz

In‐Cheol Park, Se-Hyeon Kang

The fully parallel LDPC decoding architecture can achieve high decoding throughput, but it suffers from large hardware complexity caused by a large set of processing units (PUs) and complex interconnections. A practical solution of area-efficient decoders is to use the partially parallel architecture in which a PU is shared for several rows or columns. It is important in the partially parallel architecture to determine the rows or columns to be processed in a PU and their processing order. The dependencies between rows and columns should be considered to minimize the overall processing time by overlapping the decoding operations. This paper proposes an efficient scheduling algorithm that can be applied to general LDPC codes, which is based on the concept of matrix permutation. Experimental results show that the proposed scheduling achieves a higher decoding rate, leading to a reduction of 25% processing time on average. A 1024-bit rate-1/2 LDPC decoder, employing the proposed scheduling algorithm, provides almost 1 Gbps decoding throughput and occupies one-fifth the area compared to the fully parallel decoder.

E. Sharon, Simon N. Litsyn, Jacob Goldberger

An efficient decoding schedule for low-density parity-check (LDPC) codes that outperforms the conventional approach, in terms of both complexity and performance, is presented. Conventionally, in each iteration, all symbol nodes and, subsequently, all the check nodes, send messages to their neighbors ("flooding schedule"). In contrast, in the proposed method, the updating of nodes is performed according to a serial schedule which propagates the information twice as fast. A density evolution (DE) algorithm for asymptotic analysis of the new schedule is derived, showing that, when working near the code's capacity, the decoder converges in approximately half the number of iterations. In addition, a concentration theorem is proved, showing that, for a randomly chosen serial schedule, code graph, and decoder input, the decoder's performance approaches its expected one as predicted by the DE algorithm, when the code length increases.

Amrit Pal Singh, Sanjay Sharma