Back to Search
Start Over
Guess & Check Codes for Deletions and Synchronization
- Publication Year :
- 2017
-
Abstract
- We consider the problem of constructing codes that can correct $\delta$ deletions occurring in an arbitrary binary string of length $n$ bits. Varshamov-Tenengolts (VT) codes can correct all possible single deletions $(\delta=1)$ with an asymptotically optimal redundancy. Finding similar codes for $\delta \geq 2$ deletions is an open problem. We propose a new family of codes, that we call Guess & Check (GC) codes, that can correct, with high probability, a constant number of deletions $\delta$ occurring at uniformly random positions within an arbitrary string. The GC codes are based on MDS codes and have an asymptotically optimal redundancy that is $\Theta(\delta \log n)$. We provide deterministic polynomial time encoding and decoding schemes for these codes. We also describe the applications of GC codes to file synchronization.<br />Comment: Accepted in ISIT 2017
- Subjects :
- Computer Science - Information Theory
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1702.04466
- Document Type :
- Working Paper