Code with correction of deletions and insertions

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 .