Decoding Desarguesian spread codes beyond half minimum distance
Information TheoryDiscrete Mathematics
Summary
The authors study a type of error-correcting code called Desarguesian spread codes, which are used to protect information in certain mathematical spaces. They show that the usual method for decoding these codes can still correctly fix errors even when more errors occur than previously thought. Building on this, they create a new decoding method that can uniquely recover the original information even when pieces are both added and removed, as long as some conditions are met. They also improve their algorithm with two tweaks that allow it to handle more errors, similar to the standard decoder.
Authors
Ermes Franch, Chunlei Li, Angelica Piccirillo
Abstract
Spread codes are a well-known family of constant-dimension subspace-metric codes. For constant dimension $k$ and ambient space dimension $n$ being a multiple of $k$, these codes have minimum distance $2k$ and a rich geometric structure. In this paper, we study the decoding capabilities of the Nearest Neighbor Decoder for Desarguesian spread codes, establishing that unique decoding is still achievable beyond half the minimum distance. Motivated by this, we develop a new decoding algorithm to uniquely decode Desarguesian spread codes in the presence of both insertions and deletions, which increase and decrease, respectively, the dimension of the transmitted codeword. Even when the sum of the dimensions of insertions and deletions exceeds half the minimum distance, provided that deletions are of dimension at most $k-2$, the algorithm succeeds with a small decoding failure. We also propose two refinements to this algorithm that, empirically, can handle nearly as many insertions as the Nearest Neighbor Decoder.