Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 69, Issue 10, Pages 6401-6413Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2023.3289055
Keywords
DNA storage; error-correcting codes; deletions; insertions; burst error
Ask authors/readers for more resources
This study focuses on deletion and insertion errors in DNA-based storage and communication systems. An upper bound on the size of binary codes that can correct a (t, s)-burst error is provided, demonstrating the minimum redundancy required for such codes. An explicit construction for binary (t, s)-burst correcting codes for the case where t = 2s is also presented.
by applications in DNA-based storage and communication systems, we study deletion and insertion errors simultaneously in a burst. In particular, we study a type of error named t-deletion-s-insertion-burst ((t, s)-burst for short) which is a generalization of the (2, 1)-burst error proposed by Schoeny et al. Such an error deletes t consecutive symbols and inserts an arbitrary sequence of length s at the same coordinate. We provide a sphere-packing upper bound on the size of binary codes that can correct a (t, s)-burst error, showing that the redundancy of such codes is at least log(n - t + 2) + t -1. For t = 2s, an explicit construction of binary (t, s)-burst correcting codes with redundancy log n + (t - s - 1) log log n + O-t(1) is given, where O-t(.) suppresses factors that depend only on t. Additionally, we construct a binary (3, 1)-burst correcting code with redundancy at most log n + 9, which is optimal up to an additive constant.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available