Characterization of Problematic Graphical Structures of LDPC Codes and the Corresponding Efficient Search Algorithms

The main reason for the popularity of LDPC codes is their near Shannon limit performance with relatively low decoding complexity algorithms. These codes have been adopted in number of standards such as IEEE 802.11n, IEEE 802.16e, IEEE 802.22, IEEE 802.3an, DVB-T2 and DVB-S2. These codes seem to be strong candidates for FEC in optical networks, 5G networks and Data Storage Systems.

Finite-length LDPC codes under iterative decoding algorithms suffer from the error floor phenomenon. In the past decade, a lot of attempts have been made to study and solve this problem.

It's well-known that trapping sets are the main culprit in the error-floor of (binary and non-binary) LDPC codes in BEC, BSC and AWGNC under soft and hard decision iterative decoders. The knowledge of harmful Trapping sets has been used in three applications: (1) estimating the performance of LDPC codes in the error floor region, (2) modifying iterative decoders to have better error floor performance and (3) constructing LDPC codes with low error floors.

However, attaining such knowledge, regardless of differences in the graphical structure of these sets and the sparsity of the underlying graph, is a hard problem. Most of the works on trapping sets in the literature are non-exhaustive, are concerned with relatively small TSs, or are applicable to relatively short block lengths.

Solution

We modeled the problem of finding exhaustive list of trapping sets as a graph theory problem with various scenarios.

We proposed a novel approach called DPL to solve this problem:

DPL-based algorithms have been implemented in MATLAB for:

Characterization and Search of Stopping sets in regular and irregular LDPC codes.



Applications

The approaches proposed in the literature for finding these problematic structures were not applicable to practical LDPC codes. For the first time, one can use DPL-based algorithms to find the problematic structures of different LDPC codes with any given block length, rate, degree distribution, in different channels, and under different iterative decoders: