Spectrum of sizes for perfect deletion-correcting codes

DOI10.1137/090751311MaRDI QIDQ3084211zbMATH OpenOpenAlexFDO

Authors Yeow Meng Chee, Gennian Ge, Alan C. H. Ling

Publication date 15 March 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

deletion-correcting codesdirected packingsgroup divisible designsoptimal codesperfect codes

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Combinatorial codes (94B25) Other types of codes (94B60)

Abstract: One peculiarity with deletion-correcting codes is that perfect $t$-deletion-correcting codes of the same length over the same alphabet can have different numbers of codewords, because the balls of radius $t$ with respect to the Levenshteu{i}n distance may be of different sizes. There is interest, therefore, in determining all possible sizes of a perfect $t$-deletion-correcting code, given the length $n$ and the alphabet size~$q$. In this paper, we determine completely the spectrum of possible sizes for perfect $q$-ary 1-deletion-correcting codes of length three for all $q$, and perfect $q$-ary 2-deletion-correcting codes of length four for almost all $q$, leaving only a small finite number of cases in doubt.

Recommendations

• Spectrum of sizes for perfect 2-deletion-correcting codes of length 4
• On perfect deletion-correcting codes
• The existence of the perfect deletion code with mixed length {4,5,6}
• Some combinatorial constructions for optimal perfect deletion-correcting codes
• scientific article; zbMATH DE number 4211968

Cited in

(6)

• Some combinatorial constructions for optimal perfect deletion-correcting codes
• On the construction of perfect deletion-correcting codes using design theory
• The existence of the perfect deletion code with mixed length {4,5,6}
• scientific article; zbMATH DE number 4211968 (Why is no real title available?)
• On perfect deletion-correcting codes
• Spectrum of sizes for perfect 2-deletion-correcting codes of length 4

This page was built for publication: Spectrum of sizes for perfect deletion-correcting codes

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