Tight Lower and Upper Bounds on the Minimum Distance of LDPC Codes
Yoones Hashemi, Amir H. Banihashemi · IEEE Communications Letters · 2017
In this letter, we obtain lower and upper bounds on the minimum distance dminof low-density parity-check (LDPC) codes. The bounds are derived by categorizing the non-zero code words of an LDPC code into two categories of elementary and non-elementary. The first category contains code words whose induced subgraph has only degree-2 check nodes. We propose an efficient search algorithm that can find the elementary code words of an LDPC code with weight less than a certain value amax, exhaustively. We also derive a lower bound Lneon the weight of non-elementary code words. By performing the search with amax= Lne, we either obtain an elementary code word with the smallest weight dmin, or establish the lower bound of Lneon dmin. For the upper bound, we modify our search algorithm to reach elementary codewords of larger weights at the cost of being non-exhaustive. Once such a codeword is found, its weight acts as an upper bound on dmin. We examine a large number of regular and irregular LDPC codes, and demonstrate the efficiency and versatility of our technique in finding lower and upper bounds on, and in many cases the exact value of, dmin. Finding dmin, or establishing search-based lower or upper bounds, for many of the examined codes are out of the reach of any existing algorithm.