Exhaustive Weight Spectrum Analysis of LDPC Codes with Results for some well known Codes

April 14, 2009
Professor Martin Tomlinson
Fixed and Mobile Communications Research
University of Plymouth, UK


The indicative performance of an LDPC code may be determined from exhaustive analysis of the low weight spectral terms of the code’s stopping sets which by definition includes the low weight codewords. In a landmark paper in 2007, Rosnes and Ytrehus showed that exhaustive, low weight stopping set analysis of codes whose parity check matrix is sparse is feasible using a bounded tree search over the length of the code with no distinction between information and parity bits. For an (n, k) code the potential total search space is of size 2n but a good choice of bound dramatically reduces this search space to a practical size. Indeed the choice of bound is critical to the success of the algorithm. It is shown that an improved algorithm can be obtained if the bounded tree search is applied to a set of k information bits since the potential total search space is initially reduced to size 2k. Since such a restriction will only find codewords and not all stopping sets a class of bits is defined as unsolved parity bits and these are also searched as appended bits in order to find all low weight stopping sets. Weight spectrum results are presented for commonly used WiMax LDPC codes plus some other well known LDPC codes.