Permutation Codes for Correcting a Burst of at Most t Deletions

EasyChair Preprint no. 8958

Abstract

Codes over permutations have received significant attention due to their applications in memory devices and powerline transmission systems. In this paper, we construct a family of permutation codes that are capable of correcting a burst of at most $t$ deletions with $\log n+O(\log\log n)$ bits of redundancy where $t$ is a constant, which significantly improves upon the state-of-the-art construction with redundancy $2t\log n$ bits.

Keyphrases: Burst of deletions, error-correcting codes, Permutation codes

@Booklet{EasyChair:8958,
  author = {Shuche Wang and Yuanyuan Tang and Ryan Gabrys and Farzad Farnoud},
  title = {Permutation Codes for Correcting a Burst of at Most t Deletions},
  howpublished = {EasyChair Preprint no. 8958},

  year = {EasyChair, 2022}}