🔢 mathematics

Decoding Desarguesian spread codes beyond half minimum distance

This paper extends the decoding capabilities of Desarguesian spread codes beyond half the minimum distance by establishing unique decoding via a Nearest Neighbor Decoder and introducing a new algorithm that successfully handles combined insertions and deletions, provided the deletions are limited to dimension at most $k-2$ .

Original authors: Ermes Franch, Chunlei Li, Angelica Piccirillo

Published 2026-07-21

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Ermes Franch, Chunlei Li, Angelica Piccirillo

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 sending a secret message through a chaotic, magical river. Instead of writing letters on paper, you are sending a floating island made of math. In the world of network coding, data travels as "subspaces"—think of them as invisible, multi-dimensional shapes floating in a giant, high-dimensional ocean. The goal is to send a specific shape (your message) from point A to point B. But the river is tricky. Sometimes, the current eats parts of your island (deletions), shrinking it. Other times, the river dumps random debris onto your island (insertions), making it bigger and messier.

To fix this, scientists use "codes," which are like a special dictionary of allowed shapes. If you receive a messy, distorted shape, you try to find the closest match in your dictionary. Usually, if the mess isn't too big—specifically, if the total amount of missing and extra stuff is less than half the distance between any two valid shapes—you can perfectly reconstruct the original. This is the "half minimum distance" rule, a safety net that has been the gold standard for a long time. But what if the river is extra chaotic, and the mess is bigger than that safety net? Can we still save the message? This is the puzzle researchers have been trying to solve, especially for a very elegant type of code called "Desarguesian spread codes," which are built on beautiful geometric patterns but have been hard to decode when the noise gets too loud.

This paper takes a bold step into that noisy territory. The authors, Ermes Franch, Chunlei Li, and Angelica Piccirillo, propose a new way to decode these specific codes even when the errors exceed the traditional safety limit. They don't just rely on finding the "closest" shape; instead, they use a clever two-step dance called "Expand and Reduce." Imagine you have a crumpled, dirty piece of paper (the received message). First, you "expand" it by stretching it out in many directions at once. If the paper was just a little torn (deletions), this stretching magically fills in the holes, restoring the original shape. If the paper was covered in mud (insertions), the stretching makes the mud spread out even wider, making it easier to spot.

Next, they "reduce" the shape. This is like squeezing the stretched paper through a series of tiny, specific filters. The magic is that the original shape (the valid code) is special: it fits perfectly through these filters and stays intact. The random mud, however, gets squeezed out and disappears. By combining these two moves—stretching to fix holes and squeezing to wash away dirt—they can recover the message even when the total noise is larger than half the minimum distance.

The paper introduces three versions of this decoder. The first, "Expand and Reduce" (ER), is the basic version. It works well, but it has a limit on how much dirt it can handle. The second, "Expand Reduce Expand" (ERE), adds a final stretch at the end to catch messages that were almost recovered but needed a little extra help. The third, "Filtered ERE," is the most sophisticated. It acts like a sieve, running the message through many different combinations of stretching and squeezing to filter out the noise before trying to reconstruct the final shape.

The results are promising but come with a caveat. The authors show through computer simulations that these algorithms can successfully decode messages even when the noise is quite heavy, provided the "dirt" (insertions) isn't too massive compared to the "holes" (deletions). They found that if the deletions are limited to a certain amount (specifically, removing at most $k-2$ dimensions), they can handle a surprising amount of insertions. However, they also discovered a hard limit: if the random noise becomes too large and starts to look like a valid shape from the dictionary, even their best algorithm can't tell the difference. This isn't a failure of their math, but a fundamental limit of the geometry itself.

In short, this paper doesn't just say "we can fix it"; it says "we can fix it more than before, and here is exactly how far we can push the limit before the river becomes too wild to navigate." They prove that unique decoding is possible beyond the old half-distance barrier, offering a new, probabilistic tool that works with high success rates as the mathematical "field" gets larger. It's a significant upgrade for sending data through the most turbulent digital rivers, turning a previously unsolvable mess into a recoverable message, provided the chaos doesn't get quite out of hand.

Technical Summary: Decoding Desarguesian Spread Codes Beyond Half Minimum Distance

Problem Statement
Subspace codes are utilized in random linear network coding to correct errors and erasures introduced by an operator channel. In this setting, a transmitted vector space may suffer from deletions (loss of dimensions due to erasures) and insertions (addition of erroneous dimensions). While Nearest Neighbor Decoders (NND) for constant-dimension codes are guaranteed to uniquely decode received spaces within half the minimum distance, existing algorithms for Desarguesian spread codes have been restricted to this radius and, crucially, to cases where the received subspace dimension does not exceed the codeword dimension ( $k$ ).

Previous work by Gorla, Manganiello, and Rosenthal [15, 9] provided efficient bounded-distance decoding for Desarguesian spread codes but was limited to received spaces $R$ where $\dim(R) \le k$ and the distance was strictly less than $k$ (half the minimum distance of $2k$ ). This left open the problem of decoding when insertions cause the received dimension to exceed $k$ , or when the total error weight (sum of insertions and deletions) exceeds the unique decoding radius.

Methodology
The authors propose a probabilistic polynomial-time decoding framework based on two novel operations defined on subspaces of $\mathbb{F}_{q^n}$ : expansion and reduction. These operations leverage the algebraic structure of Desarguesian spread codes, which are orbits of the subfield $\mathbb{F}_{q^k}$ under the multiplicative group $\mathbb{F}_{q^n}^*$ .

Expansion ( $f_{exp}$ ): Defined as $f_{exp}(V, x) = \sum x_i V$ , this operation expands a subspace $V$ by multiplying it with a set of scalars $x$ . Theoretically, if $V$ is a subspace of a codeword $a\mathbb{F}_{q^k}$ , a sufficiently large expansion can reconstruct the full codeword $a\mathbb{F}_{q^k}$ . Conversely, for random insertion subspaces $B$ , expansion tends to increase their dimension or spread them out, but with high probability, they do not form a full $\mathbb{F}_{q^k}$ -linear space unless the expansion is excessive.
Reduction ( $f_{red}$ ): Defined as $f_{red}(V, y) = \bigcap y_i V$ , this operation intersects the subspace with its scalar multiples. This operation preserves $\mathbb{F}_{q^k}$ -linear subspaces (codewords) but tends to reduce random subspaces to the trivial space $\{0\}$ .

The core decoding strategy involves applying an expansion to the received space $R = U \oplus B$ (where $U$ is the surviving part of the codeword and $B$ is the random insertion) to recover the codeword structure, followed by reduction to eliminate the inserted noise.

Key Contributions and Algorithms
The paper introduces three decoding algorithms, progressively refining the approach to handle larger error weights and insertion dimensions:

Expand and Reduce (ER):
- Logic: Applies a single expansion step to $R$ using a vector $x$ of length $s$ , followed by iterative reduction.
- Capability: Can decode beyond half the minimum distance. It handles cases where the received dimension is larger than $k$ (insertions > deletions).
- Constraint: Success depends on choosing an expansion length $s$ such that $s \dim(U) \ge k$ (to recover the codeword) while ensuring the expansion of the insertion space $B$ does not accidentally generate a full $\mathbb{F}_{q^k}$ -linear subspace (which would lead to list decoding or failure).
- Result: Unique decoding is achievable with high probability (w.h.p.) as the field size $q$ increases, provided the dimension of deletions $d$ satisfies $d \le k(1 - 1/s)$ and the insertion dimension $t$ is bounded by specific theoretical limits derived from the expansion length.
Expand Reduce Expand (ERE):
- Logic: A refinement where the reduction phase is stopped one step before reaching $\{0\}$ , leaving a subspace contained within the original codeword, which is then re-expanded to full dimension.
- Improvement: This removes the strict requirement that the initial expansion must fully reconstruct the codeword immediately. It allows for a larger range of correctable insertions, specifically $t < (k-d)(r-1)$ .
Filtered ERE:
- Logic: Introduces a filtering step before the final ERE execution. It iteratively computes intersections of expanded received spaces with scaled versions of the received space to collect small subspaces likely to belong to the original codeword.
- Improvement: This method significantly increases the tolerance for insertions, handling dimensions up to $t < \frac{n-k}{2}$ , independent of the deletion dimension $d$ .
- Complexity: While the complexity is polynomial in $n$ for constant $k$ , it can become sub-exponential in extreme regimes (e.g., $k \approx \sqrt{n}$ ), though it remains superior to brute-force search.

Results and Experimental Validation
The authors implemented these algorithms in SageMath and conducted experiments with parameters $q=2$ , varying $n$ and $k$ .

ER Performance: The success rate drops sharply once the number of insertions exceeds the theoretical bound derived in Equation (12), confirming the tightness of the bound.
ERE Performance: Shows improved robustness over ER, maintaining high success rates for insertion counts that would cause ER to fail. The performance degradation is observed to be smoother than the sharp cutoff of ER.
Filtered ERE Performance: Demonstrates the ability to decode with high accuracy even when the number of insertions approaches the theoretical limit for unique decoding (near $t \approx \frac{n-k}{2}$ ).
Geometric Insight: The paper links the success of the NND to the concept of evasive subspaces. A decoding failure occurs if the projection of the insertion space $B$ onto the quotient space $\mathbb{F}_{q^n}/a\mathbb{F}_{q^k}$ intersects other spread elements with dimension $\ge k-d$ . The authors show that for random insertions, the probability of this "non-evasive" behavior drops to zero as $q \to \infty$ for insertion dimensions below a specific threshold, explaining the high success probability of their probabilistic approach.

Significance and Claims
The paper claims to resolve an open problem identified in [9] by providing a decoding algorithm that:

Works for received subspaces with dimension larger than the codeword dimension $k$ (handling insertions that outnumber deletions).
Achieves unique decoding beyond half the minimum distance ( $k$ ) with high probability, a regime where deterministic unique decoding is not guaranteed.
Provides a theoretical framework connecting subspace decoding to the geometric properties of evasive subspaces relative to Desarguesian spreads.

The authors emphasize that their approach is probabilistic; while it succeeds with high probability for random errors, it does not guarantee unique decoding for all error patterns beyond the half-distance radius. The work establishes that unique decoding is achievable in a broader error regime than previously thought possible for Desarguesian spread codes, provided the field size is sufficiently large and the error model is random.

More like this