Construction of Optimal Edit Metric Codes
The edit distance between two strings is the minimal number of substitutions, deletions, or insertions required to transform one string into another. An error correcting code over the edit metric includes features from deletion-correcting codes as well as the more traditional codes defined using Hamming distance. Applications of edit metric codes include the creation of robust tags over the DNA alphabet.This paper explores the theory underlying edit metric codes for small alphabets. The size of a sphere about a word is heavily dependent on its block structure, or its partition into maximal subwords of a single symbol. This creates a substantial divergence from the theory for the Hamming metric.An optimal code is one with the maximum possible number of eodewords for its length and minimum distance. We provide tables of bounds on code sizes for edit codes with short length and small alphabets. We describe issues relating to exhaustive searches and present several heuristics for constructing codes.
Sheridan K.Houghten Dan Ashlock Jessie Lenarz
Dept.of Computer Science Brock University St.Catharines, ON, Canada L2S 3A1 Dept.of Mathematics & Statistics University of Guelph Guelph, ON, Canada, NlG 2R4 Dept.of Math.& Computer Science Concordia College Moorhead, MN, USA 56562
国际会议
2006年IEEE信息理论国际会议(Proceedings of 2006 IEEE Information Theory Workshop ITW06)
成都
英文
259-263
2006-10-22（万方平台首次上网日期，不代表论文的发表时间）