TU2.R6.1

Improved Non-Asymptotic Lower Bound on the Size of Optimal Insertion/Deletion Correcting Code

Yuhang Pi, Zhifang Zhang, Chinese Academy of Sciences, University of Chinese Academy of Sciences., China; Yaqian Zhang, Shanghai Jiao Tong University, China
Session:
Biology: Insertions and Deletions
Track:
17: Information and Coding in Biology
Location:
Sigma/Delta
Presentation Time:
Tue, 9 Jul, 11:30 - 11:50
Session Chair:
Maël Le Treust, CNRS
Abstract
In this paper, we provide non-asymptotic upper bounds on the size and average size of $s$-insertion $s$-deletion balls. As a corollary, we conclude an explicit non-asymptotic lower bound on the size of optimal $s$-insertion/deletion correcting code which is a strict improvement of Levenshtein’s lower bound given in 2002. Particularly, in the case of single insertion/deletion, comparing with Levenshtein’s bound, we reduce the gap to the maximum potential lower bound by at least $1/3$.
Session TU2.R6
TU2.R6.1: Improved Non-Asymptotic Lower Bound on the Size of Optimal Insertion/Deletion Correcting Code
Yuhang Pi, Zhifang Zhang, Chinese Academy of Sciences, University of Chinese Academy of Sciences., China; Yaqian Zhang, Shanghai Jiao Tong University, China
TU2.R6.2: New Construction of $q$-ary Codes Correcting a Burst of at most $t$ Deletions
Wentu Song, Kui Cai, Tony Quek, Singapore University of Technology and Design, Singapore
TU2.R6.3: Improving the Singleton-type Upper Bounds for Non-Linear Deletion Correcting Codes
Shiqin Liu, Chen Wang, Shandong University, China; Gennian Ge, Capital Normal University, China; Yiwei Zhang, Shandong University, China
TU2.R6.4: On Fixed Length Systematic All Limited Magnitude Zero Deletion/Insertion Error Control Codes
Luca Tallini, University of Teramo, Italy; Hoang Vu, Bella Bose, Oregon State University, United States
Resources
View Manuscript