8
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Guess & Check Codes for Deletions, Insertions, and Synchronization

Preprint

,

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### 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 are zero-error single deletion $$(\delta=1)$$ correcting codes, and have 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, up to $$\delta$$ deletions occurring in a binary string. Moreover, we show that GC codes can also correct up to $$\delta$$ insertions. 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.

### Most cited references10

• Record: found

### Asymptotically good codes correcting insertions, deletions, and transpositions

(1999)
Bookmark
• Record: found

### On multiple insertion/deletion correcting codes

(2002)
Bookmark
• Record: found

### Capacity Upper Bounds for the Deletion Channel

Bookmark

### Author and article information

###### Journal
2017-05-24
1705.09569