Combinatorial Alphabet-Dependent Bounds for Insdel Codes
- 25 February 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (5) , 3544-3559
Abstract
Error-correcting codes resilient to synchronization errors such as insertions and deletions are known as insdel codes. In this paper, we present several new combinatorial upper and lower bounds on the maximum size of q-ary insdel codes. Our main upper bound is a sphere-packing bound obtained by solving a linear programming (LP) problem. It improves upon previous results for cases when the distance d or the alphabet size q is large. Our first lower bound is derived from a connection between insdel codes and matchings in special hypergraphs. This lower bound, together with our upper bound, shows that for fixed block length n and edit distance d, when q is sufficiently large, the maximum size of insdel codes is $ \frac {q^{n-\frac {d}{2}+1}}{\binom {n}{\frac {d}{2}-1}}(1 \pm o(1))$ . The second lower bound refines Alon et al.’s recent logarithmic improvement on Levenshtein’s GV-type bound and extends its applicability to large q and d.Keywords
All Related Versions
Funding Information
- European Research Council (852953)
- National Natural Science Foundation of China (12371523)
This publication has 41 references indexed in Scilit:
- Approximate generalized Steiner systems and near-optimal constant weight codesJournal of Combinatorial Theory, Series A, 2024
- Improved bounds for codes correcting insertions and deletionsDesigns, Codes and Cryptography, 2024
- Spectrum of sizes for perfect 2-deletion-correcting codes of length 4Designs, Codes and Cryptography, 2013
- A Combinatorial Construction for Perfect Deletion-Correcting CodesDesigns, Codes and Cryptography, 2001
- Efficient Reconstruction of Sequences from Their Subsequences or SupersequencesJournal of Combinatorial Theory, Series A, 2001
- Existence of Perfect 3-Deletion-Correcting CodesDesigns, Codes and Cryptography, 1998
- A linear programming perspective on the Frankl?R dl?Pippenger theoremRandom Structures & Algorithms, 1996
- On the construction of perfect deletion-correcting codes using design theoryDesigns, Codes and Cryptography, 1995
- A note on Ramsey numbersJournal of Combinatorial Theory, Series A, 1980
- Some general results of coding theory with applications to the study of codes for the correction of synchronization errorsInformation and Control, 1969