Binary Reconstruction Codes for Correcting One Deletion and One Substitution
IEEE Transactions on Information Theory · 2026-06 · 72 (6) · 3733-3752
DOI: 10.1109/tit.2026.3688516 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-06. Verfasst von Yuling Li und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 46 Literaturangaben. Gefördert von: National Key Research and Development Program of China, National Natural Science Foundation of China, Beijing Scholars Program.
Abstract (Originalsprache)
In this paper, we investigate binary reconstruction codes capable of correcting one deletion and one substitution. We define the single-deletion single-substitution ball function $ \mathcal {B} $ as a mapping from a sequence to the set of sequences that can be derived from it by performing one deletion and one substitution. A binary $(n,N;\mathcal {B})$ -reconstruction code is defined as a collection of binary sequences of length $ n $ such that the intersection size between the single-deletion single-substitution balls of any two distinct codewords is strictly less than $ N $ . This property ensures that each codeword can be uniquely reconstructed from $ N $ distinct elements in its single-deletion single-substitution ball. Our main contribution is to demonstrate that when $ N $ is set to $ 4n - 8 $ , $ 3n - 4 $ , $ 2n + 9 $ , $ n+21 $ , 31, and 7, the redundancy of binary $(n,N;\mathcal {B})$ -reconstruction codes can be 0, 1, 2, $ \log \log n + 3 $ , $ \log n + 1 $ , and $ 3\log n + 4 $ , respectively, where the logarithm is on base two.
Förderung
- National Key Research and Development Program of China
- National Natural Science Foundation of China
- Beijing Scholars Program
Zitieren
APA
Li, Y., Sun, Y., & Ge, G. (2026). Binary Reconstruction Codes for Correcting One Deletion and One Substitution. IEEE Transactions on Information Theory, 72(6), 3733-3752. https://doi.org/10.1109/tit.2026.3688516
Vancouver
Li Y, Sun Y, Ge G. Binary Reconstruction Codes for Correcting One Deletion and One Substitution. IEEE Transactions on Information Theory. 2026;72(6):3733-3752. doi:10.1109/tit.2026.3688516
BibTeX
@article{Li2026,
author = {Li, Yuling and Sun, Yubo and Ge, Gennian},
title = {Binary Reconstruction Codes for Correcting One Deletion and One Substitution},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {6},
pages = {3733--3752},
doi = {10.1109/tit.2026.3688516}
}
EUVIMED