pipette
ESEspañol

A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors

Neehar Verma, Camilla Hollanti, Razane Tajeddine

Preprint

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.