Single-Deletion Single-Substitution Correcting Codes

Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper deals with the fundamental task of constructing codes that can correct a single insertion or deletion along with a sin...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2023-12, Vol.69 (12), p.7659-7671
Main Authors: Smagloy, Ilia, Welter, Lorenz, Wachter-Zeh, Antonia, Yaakobi, Eitan
Format: Article
Language:English
Subjects:
Asymptotic properties
Codecs
Codes
Deletion
Error-correcting codes
Redundancy
Storage systems
Substitutes
Symbols
Synchronization
synchronization errors
Systematics
Upper bound
Upper bounds
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper deals with the fundamental task of constructing codes that can correct a single insertion or deletion along with a single substitution. A non-asymptotic upper bound on the size of non-binary single-deletion s -substitution correcting codes is derived, showing that the non-asymptotic redundancy of such a code of length n has to be at least (s+1) \log _{q} n . An explicit construction of binary single-deletion single-substitution correcting codes with at most 6 \log n + 8 redundancy bits is presented.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2023.3319088