On Codes with Support-Constrained Parity Checks
For coding theorists and practitioners designing LDPC, locally repairable, or quantum error-correcting codes with hardware constraints, this work provides fundamental limits and achievability results, while revealing limitations of a common construction approach.
The paper derives the optimal minimum distance achievable for linear codes with arbitrary support constraints on the parity-check matrix and shows it is achievable over sufficiently large fields. It also demonstrates that, unlike the generator-matrix setting, the optimal distance cannot always be realized by subcodes of generalized Reed-Solomon codes, providing a counterexample based on K_{6,6}.
We study linear codes that maximize minimum distance subject to arbitrary support constraints on the parity-check matrix. Such constraints arise naturally in the design of LDPC codes, locally repairable codes, and hardware-constrained systems where each parity check must involve only a limited number of code symbols. They are also essential in quantum error correction, where sparse stabilizers reduce measurement noise and respect the connectivity constraints of physical qubit architectures. We derive the optimal minimum distance possible given support constraints on the parity-check matrix and show it is achievable over sufficiently large fields. When this maximum distance coincides with the Singleton bound for unconstrained parity check matrices, the dual GM-MDS construction yields generalized Reed--Solomon codes obeying the mask. In the generator-matrix setting, the GM-MDS theorem guarantees that the optimal distance can always be achieved by a subcode of a generalized Reed--Solomon code while satisfying arbitrary support constraints. We show that this is not true for the parity-check setting. We exhibit a set of support constraints, derived from the vertex-edge incidence of $K_{6,6}$, for which the optimal minimum distance cannot be realized by any subcode of a generalized Reed--Solomon code over any field. We also analyze structured constraint families -- regular, balanced, and cyclic masks -- through numerical optimization, providing design guidance for practical code constructions.