CPM-LDPC Codes Attaining the Minimum-Distance Bound

Abstract

We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most $(J+1)!$, where $J$ is the column weight. For every fixed pair of column and row weights $2\le J<L$, we show that this bound is attained for all sufficiently large integer lift sizes. First, we give one integer exponent matrix independent of the lift size $P$. Second, we show that independent uniform exponent choices attain the bound with probability $1-O_{J,L}(P^{-1})$. Both proofs use cycle conditions required by low-weight codewords and a lower bound on the number of terms in vectors satisfying polynomial check equations. Neither construction requires $P$ to be prime. We also give small-lift arrays attaining the bound 24 for $J=3$, $L=4,\dots ,8$, and arrays with distance at least 28 for $J=4$, $L=5,\dots ,8$, together with computational distance verification.

arXiv comment13 pages, 1 figure, 2 tables. Verification code and data: https://github.com/kasaikenta/cpm-ldpc-distance