Spectrum of Sizes for Perfect Deletion-Correcting Codes

DOI10.1137/090751311zbMATH Open1210.94116arXiv1008.1343OpenAlexW3104081359MaRDI QIDQ3084211

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

Publication date: 15 March 2011

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

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.

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

zbMATH Keywords

perfect codesoptimal codesgroup divisible designsdeletion-correcting codesdirected packings

Mathematics Subject Classification ID

Could not fetch data.

Related Items (3)

Title not available (Why is that?) ⋮ Spectrum of sizes for perfect 2-deletion-correcting codes of length 4 ⋮ Some combinatorial constructions for optimal perfect deletion-correcting codes

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)