On the Minimum Distance of Low-Density Parity-Check Codes with Parity-Check Matrices Constructed from Permutation Matrices

Abstract

An ensemble of codes defined by parity-check matrices composed of M ´ M permutation matrices is considered. This ensemble is a subensemble of the ensemble of low-density parity-check (LDPC) codes considered by Gallager [Low-Density Parity-Check Codes, Cambridge: MIT Press, 1963]. We prove that, as M ® ¥, the minimum distance of almost all codes in the ensemble grows linearly with M. We also show that in several cases the asymptotic minimum-distance-to-block-length ratio for almost all codes in the ensemble satisfies Gallager’s bound.