WorksPhysics and Astronomy
Vanishing Relative Distance of Uniformly Random CSS LDPC Codes Built from Permutation Matrices
Abstract
Classical random regular low-density parity-check codes can have minimum distance growing linearly with block length. We study CSS check matrices formed as full arrays of arbitrary permutation matrices, sampled uniformly subject to commutation. For fixed column weight and fixed even row weight , we prove that the relative minimum distance converges to zero in probability as , with block length . We analyze the weight enumerators that count all nontrivial logical representatives after excluding stabilizers. A coefficientwise lower bound shows that, at every fixed relative weight along even-weight sequences, exponentially many such representatives exist with high probability. Their typical and mean counts have exponent lower bound , where is the binary entropy function. We compare this bound with the classical LDPC and dense CSS mean weight-distribution exponents. The existence, with high probability, of a logical operator below every fixed target weight yields the distance conclusion.