Computer Science – Information Theory
Scientific paper
2010-08-07
SIAM Journal on Discrete Mathematics, vol. 24, no. 1, pp. 33-55, 2010
Computer Science
Information Theory
23 pages
Scientific paper
10.1137/090751311
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 Levenshte\u{\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.
Chee Yeow Meng
Ge Gennian
Ling Alan C. H.
No associations
LandOfFree
Spectrum of Sizes for Perfect Deletion-Correcting Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Spectrum of Sizes for Perfect Deletion-Correcting Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spectrum of Sizes for Perfect Deletion-Correcting Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-593831