Nonasymptotic Upper Bounds for Deletion Correcting Codes

DOI10.1109/TIT.2013.2257917MaRDI QIDQ5346436zbMATH OpenOpenAlexFDO

Authors Ankur A. Kulkarni, Negar Kiyavash

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.3128

Mathematics Subject Classification ID

Hypergraphs (05C65) Burst-correcting codes (94B20) Other types of codes (94B60)

Abstract: Explicit non-asymptotic upper bounds on the sizes of multiple-deletion correcting codes are presented. In particular, the largest single-deletion correcting code for $q$-ary alphabet and string length $n$ is shown to be of size at most $frac{q}^n-q(q-1)(n-1)$. An improved bound on the asymptotic rate function is obtained as a corollary. Upper bounds are also derived on sizes of codes for a constrained source that does not necessarily comprise of all strings of a particular length, and this idea is demonstrated by application to sets of run-length limited strings. The problem of finding the largest deletion correcting code is modeled as a matching problem on a hypergraph. This problem is formulated as an integer linear program. The upper bound is obtained by the construction of a feasible point for the dual of the linear programming relaxation of this integer linear program. The non-asymptotic bounds derived imply the known asymptotic bounds of Levenshtein and Tenengolts and improve on known non-asymptotic bounds. Numerical results support the conjecture that in the binary case, the Varshamov-Tenengolts codes are the largest single-deletion correcting codes.

Cited in

(4)

• Duplication-correcting codes
• On the Varshamov-Tenengolts construction on binary strings
• On Optimal k-Deletion Correcting Codes
• Balanced reconstruction codes for single edits

This page was built for publication: Nonasymptotic Upper Bounds for Deletion Correcting Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346436)