Binary codes correct multiple data errors with less extra data
Binary Codes Correcting Multiple Edits via Polynomial Hashing and Entropy Recycling
Information TheoryDiscrete Mathematics
Summary
When data gets changed by mistakes like deletions, insertions, or substitutions, it can cause problems in storage and communication. The authors show new ways to design codes that fix multiple such errors in binary data using fewer extra bits than before. They use special polynomial hashing and a method called entropy recycling to pack more information efficiently. These codes come with algorithms that can be run quickly to encode and decode data.
What this means in practice
- •For dna storage engineers: Create data storage systems on DNA that can reliably correct multiple insertion, deletion, and substitution errors efficiently.$Commercial implications: Enables commercial DNA data storage products with improved error correction using fewer redundant bits.
- •For memory device designers: Design racetrack memory systems that correct multiple edits while minimizing extra coding overhead.
Authors
Quan D. Bui, Shuche Wang, Van Khu Vu
Abstract
Codes in the Levenshtein metric that can correct multiple edits (including deletions, insertions, and substitutions) have attracted a lot of attention recently owing to their application in DNA-based storage and racetrack memories. In this work, we present new techniques for designing explicit binary codes of length $n$ that correct $t$ edits with at most $(2t+1)\log n+O_t(\log\log n)$ bits of redundancy. We first propose to use a polynomial hash to construct a systematic code that corrects $t$ edits with $(4t+2)\log n+O_t(\log\log n)$ bits of redundancy. Then we observe that there are many polynomial hashes like this, some are good, some are bad. So, we propose the second technique, called entropy recycling, to use the indices of good hashes to carry information. As a consequence, we obtain a partial-systematic code of length $n$ that corrects $t$ edits with at most $(2t+1)\log n+O_t(\log\log n)$ bits of redundancy. Finally, we provide deterministic polynomial-time encoding and decoding algorithms for our code.