🔢 mathematics

On Codes with Support-Constrained Parity Checks

This paper investigates linear codes with support-constrained parity checks, deriving optimal minimum distances and demonstrating that while the GM-MDS theorem guarantees optimal distance for generator-matrix constraints, this guarantee fails for parity-check constraints, as evidenced by a counterexample derived from the $K_{6,6}$ graph.

Original authors: Barron Han, Hikmet Yildiz, Babak Hassibi

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Barron Han, Hikmet Yildiz, Babak Hassibi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master architect designing a digital fortress. This fortress is built to protect a secret message. The strength of the fortress is measured by how much damage it can take before the secret is lost. In the world of coding theory, this strength is called the minimum distance. The more "noise" or corruption the code can handle, the stronger the fortress.

Usually, to build a super-strong fortress, you need a massive, complex network of guards (parity checks) watching over every part of the message. But in the real world, resources are limited. You might not have enough guards, or your guards might only be able to talk to their immediate neighbors due to physical wiring constraints (like in a computer chip) or the laws of physics (like in quantum computers).

This paper, titled "On Codes with Support-Constrained Parity Checks," asks a simple but difficult question: If we force our guards to only watch specific, limited groups of people, how strong can our fortress still be?

Here is a breakdown of their findings using everyday analogies:

1. The Blueprint and the Rules

Think of the parity-check matrix as a blueprint for the fortress. It lists who watches whom.

The Constraint (The Mask): The authors introduce a "mask." Imagine a stencil placed over the blueprint. If a spot on the stencil is black, that guard cannot watch that person. If it's clear, they can.
The Goal: They want to know the maximum strength (minimum distance) possible when you are forced to work within these blacked-out spots.

The Good News: The authors figured out a mathematical formula to calculate the absolute best strength possible for any given stencil. They proved that if you have a big enough "toolbox" (a large enough number system or "field"), you can always build a code that hits this theoretical maximum strength.

2. The "Golden Standard" vs. Reality

In the world of coding, there is a legendary family of codes called Generalized Reed-Solomon (GRS) codes. Think of these as the "Golden Standard" fortresses. They are famous because:

They are incredibly strong.
They are easy to fix (decode) quickly.
They are well-understood.

In a different scenario (looking at the message generation rather than the checks), mathematicians proved that any optimal fortress could be built as a variation of these Golden Standard codes. It was like saying, "No matter what weird rules you give me, I can always build the best house using bricks from this specific, famous factory."

The Big Surprise:
The authors asked: "Does this hold true for our parity-check fortress?"
The Answer: No.

They found a specific, tricky blueprint (based on a shape called $K_{6,6}$ , which is like a grid of 6 left nodes connected to 6 right nodes) where the math says a perfect fortress should exist. However, they proved that no variation of the Golden Standard (GRS) code can ever build this specific fortress.

The Analogy:
Imagine you are told, "You must build a house that fits inside this weirdly shaped hole."

The math says, "Yes, a house fits there perfectly."
The old rule said, "You can build that house using only bricks from the Golden Factory."
This paper says, "Actually, for this specific hole, the Golden Factory's bricks just don't fit. You have to use a completely different, custom-built brick."

This is a major discovery because it shows that the "Golden Standard" isn't a universal solution for all types of constraints. Sometimes, you need to invent entirely new types of codes.

3. The "Quantum" and "Storage" Connection

Why does this matter? The paper mentions two main places where these "limited guard" rules naturally happen:

Distributed Storage (Cloud Drives): If you store a file across many servers, a server might only be able to talk to its neighbors. You need codes that respect these local connections.
Quantum Computing: Quantum computers are very sensitive. To check for errors, you need to measure qubits. But you can't connect every qubit to every other qubit; they are physically stuck in a specific layout. You need "sparse" checks (guards that only look at a few neighbors) to avoid breaking the delicate quantum state.

4. The "Cyclic" Trap

The authors also looked at patterns that repeat in a circle (cyclic masks), which are popular because they are easy to build in hardware.

The Finding: Just because a pattern is neat and repetitive (cyclic) doesn't mean it's the strongest possible.
The Analogy: Imagine you are arranging chairs in a circle. You might think, "A perfect circle is the most efficient way to seat everyone." But the authors found cases where a slightly messy, non-circular arrangement actually allows for a stronger fortress. Following the "neat circle" rule can actually make your code weaker.

Summary

The Problem: How strong can a code be if we force the error-checking rules to be sparse (limited connections)?
The Solution: They found the exact mathematical limit for this strength.
The Twist: They proved that unlike other coding scenarios, you cannot always achieve this perfect strength using the famous "Generalized Reed-Solomon" family of codes. Sometimes, the rules are so specific that the standard "Golden" tools fail.
The Takeaway: To build the best codes for modern hardware (like quantum computers or efficient storage), we can't just rely on old, standard recipes. We sometimes need to design completely new, custom structures that break the mold.

Technical Summary: On Codes with Support-Constrained Parity Checks

Problem Statement

This paper investigates the fundamental limits of linear codes when the parity-check matrix is subject to arbitrary support constraints (sparsity patterns). Unlike the well-studied generator-matrix setting, where support constraints restrict which message symbols can contribute to a codeword, this work focuses on constraints that dictate which code symbols can participate in each parity-check equation.

Such constraints arise naturally in several domains:

LDPC Codes and Hardware: Limiting the number of terms per check equation (row weight) or the frequency of symbol access (column weight) to reduce decoding complexity and hardware connectivity requirements.
Distributed Storage: Locally repairable codes (LRCs) and partial MDS codes require specific sparsity patterns to enable local recovery.
Quantum Error Correction: In CSS constructions, sparse parity-check matrices correspond to low-weight stabilizer measurements, which are essential for reducing noise and respecting physical qubit connectivity.

The central questions addressed are:

Given a specific support mask $M$ , what is the maximum achievable minimum distance $d_{\min}$ ?
Can this optimal distance always be achieved by a subcode of a Generalized Reed–Solomon (GRS) code, as is the case for generator-matrix constraints (via the GM-MDS theorem)?

Methodology and Theoretical Framework

1. Structural Rank and Distance Bounds

The authors formalize the problem using a binary mask $M \in \{0, 1\}^{m \times n}$ , where $M_{ij}=0$ implies the entry $H_{ij}$ in the parity-check matrix must be zero. They define two key structural parameters derived from the mask's bipartite graph representation:

Structural Row Rank ( $\rho(M)$ ): The maximum rank achievable by any matrix obeying the mask. This determines the dimension of the resulting code.
Structural Kruskal Rank ( $\tau(M)$ ): The largest integer $s$ such that every subset of $s$ columns has a support size at least equal to the subset size.

Theorem 1 establishes that for any field size $q > \Delta(M)$ (where $\Delta(M)$ is a bound dependent on $\rho$ and $\tau$ ), there exists a parity-check matrix $H$ obeying $M$ with rank $\rho(M)$ and minimum distance $d_{\min} = \tau(M) + 1$ . This result is proven non-constructively using the Schwartz–Zippel lemma on symbolic matrices, demonstrating that the optimal distance is achievable over sufficiently large fields.

2. The MDS Regime and Dual GM-MDS

When the derived bound coincides with the Singleton bound (i.e., the code is MDS), the paper connects the problem to the Dual GM-MDS construction. If the mask satisfies a specific column expansion condition (analogous to the generator-matrix condition), a GRS code exists whose parity-check matrix obeys the mask. This is achieved by constructing a GRS generator matrix obeying the "dual" mask and taking its dual code.

3. Vandermonde Certificates and the GRS Subcode Question

The paper introduces the concept of a Full-Rank Vandermonde Certificate to determine if a sparse parity-check code can be realized as a subcode of a GRS code. A mask admits such a certificate if the parity-check matrix $H$ can be factored as $AH = V$, where $V$ is a Vandermonde matrix and $A$ is a full-rank matrix. This factorization would imply the code is a subcode of a GRS code.

Key Contributions and Results

1. Optimal Distance Characterization

The paper provides a tight, expansion-based bound on the minimum distance of sparse parity-check codes ( $d^*_{\min} = \tau(M) + 1$ ) and proves its achievability over large fields. This generalizes previous results that were often limited to specific structured masks or generator-matrix settings.

2. Negative Result on GRS Subcodes

A primary contribution is the demonstration that, unlike the generator-matrix setting, optimal distance codes under parity-check constraints cannot always be realized as subcodes of Generalized Reed–Solomon codes.

Counterexample: The authors construct a specific mask $M_{K_{6,6}}$ $M_{K_{6, 6}}$ derived from the vertex-edge incidence matrix of the complete bipartite graph $K_{6,6}$ $K_{6, 6}$ .
- Parameters: $n=36, m=12$ , yielding a target distance $d=6$ .
- The mask satisfies $\rho(M)=12$ and $\tau(M)=5$ , implying an optimal $[36, 24, 6]$ code exists over large fields.
- Theorem 6 proves that no full-rank Vandermonde certificate exists for this mask over any field. The proof relies on algebraic geometry, showing that the existence of such a certificate would force the evaluation points of the Vandermonde matrix to satisfy a system of fractional-linear involutions that eventually leads to a contradiction regarding the linear independence of the moment curve vectors.
Implication: This establishes a fundamental asymmetry between the generator-matrix and parity-check settings: while the GM-MDS theorem guarantees GRS subcodes for optimal generator-constrained codes, no such guarantee exists for parity-constrained codes.

3. Analysis of Structured Masks

The paper analyzes specific families of masks to provide design guidance:

Regular, Balanced, and Cyclic Masks: These are relevant for hardware implementation and quantum systems.
Numerical Optimization: Exhaustive searches for small parameters ( $n=9, 16$ $n = 9, 16$ ) reveal that:
- Cyclic structure alone is insufficient to maximize distance (e.g., for $n=9, m=5, w=3$ , the cyclic optimum is $d=3$ while the general optimum is $d=4$ ).
- The distance bound is not monotonic with respect to row weight $w$ in balanced-cyclic masks.
2-Regular Masks: The authors prove that 2-regular masks (corresponding to multigraphs) are limited to the distance of a block repetition code, $d \le \lfloor n/(n-m) \rfloor$ .

Significance and Claims

The paper claims to provide the first rigorous characterization of the optimal minimum distance for linear codes under arbitrary parity-check support constraints. Its significance lies in:

Theoretical Limit: Establishing that the structural Kruskal rank $\tau(M)$ is the precise limit for minimum distance, achievable over large fields.
Structural Asymmetry: Proving that the powerful structural guarantees of the GM-MDS theorem (realizability via GRS subcodes) do not extend to the parity-check setting. The $K_{6,6}$ counterexample serves as a definitive boundary for algebraic constructions in this domain.
Practical Guidance: By analyzing structured masks (regular, cyclic, balanced), the paper offers insights for designing codes in LDPC, LRC, and quantum error correction contexts where hardware constraints dictate sparsity patterns. It highlights that while structured masks are desirable for implementation, they may inherently sacrifice optimal distance compared to unstructured optimal masks.

The authors conclude that while generic existence is guaranteed, the lack of a universal algebraic construction (like GRS) for parity-constrained codes remains an open challenge, particularly for designing codes with near-optimal distance and efficient decoding for fault-tolerant quantum computing.