Permutation Codes for Correcting a Burst of at Most t Deletions

EasyChair Preprint 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, Permutation codes, error-correcting 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 8958},
  year      = {EasyChair, 2022}}