Namespaces
Variants
Actions

Code with correction of deletions and insertions

From Encyclopedia of Mathematics
Revision as of 16:55, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

code for correction of deletions and insertions

A code intended for the correction of errors of two types encountered in the transmission of information. By a deletion of a letter in a word of length over some alphabet one means a transformation of into a word of length , . The numbers of words obtainable from by deletion of letters satisfies the following estimates

Here is the number of series of (by a series of a word one means a word , , such that 1) ; 2) if , then ; and 3) if , then ). In particular, . By an insertion of a letter in a word one means a transformation of into a word of length , where and . The number of words obtainable from an arbitrary word of length by the insertion of letters of an alphabet is equal to

where is the number of letters in . A set of words over the alphabet is called a code for correction of deletions (insertions, deletions or insertions) if no word in can be obtained from two distinct words of as the result of or fewer deletions (insertions, deletions or insertions) of letters in each of them. The function defined on the pairs of words in and equal to the minimum number of deletions and insertions of letters converting into is a metric. A set of words over the alphabet is a code for correction of deletions (insertions, deletions or insertions) if and only if the distance between any two distinct words of is greater than , so that the above three definitions of a code are equivalent. An example of a code for correction of one deletion or one insertion is the set of words of length over the alphabet for which (). The number of words in this code is equal to

where the sum is taken over all odd divisors of and is the Euler function; it is asymptotically maximal as .

How to Cite This Entry:
Code with correction of deletions and insertions. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Code_with_correction_of_deletions_and_insertions&oldid=11397
This article was adapted from an original article by V.I. Levenshtein (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article