A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
In the authors' words
We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most insdel errors with fixed list size , and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size .
Main resultLimitation the authors admit
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.