In this paper, we obtain lower and upper bounds on the minimum distance dmin of low-density parity-check (LDPC) codes. The bounds are derived by categorizing the non-zero codewords of an LDPC code into two categories of elementary and non-elementary. The first category contains codewords whose induced subgraph has only degree-2 check nodes. We propose an efficient search algorithm that can find the elementary codewords of an LDPC code with weight less than a certain value amax, exhaustively. We also derive a lower bound Lne on the weight of non-elementary codewords. By performing the search with amax = Lne, we either obtain an elementary codeword with the smallest weight dmin, or establish the lower bound of Lne on 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.

Additional Metadata
Keywords Decoding, Linear codes, NP-hard problem, Parity check codes, Search problems, Upper bound
Persistent URL dx.doi.org/10.1109/LCOMM.2017.2767028
Journal IEEE Communications Letters
Citation
Hashemi, Y. (Yoones), & Banihashemi, A. (2017). Tight Lower and Upper Bounds on the Minimum Distance of LDPC Codes. IEEE Communications Letters. doi:10.1109/LCOMM.2017.2767028