Decoding Desarguesian spread codes beyond half minimum distance

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.