View source for Code with correction of deletions and insertions

{{TEX|done}}

''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  $  \beta = b _ {1} \dots b _ {n} $
of length  $  n $
over some alphabet  $  B $
one means a transformation of  $  \beta $
into a word  $  \beta  ^  \prime  = b _ {1} \dots b _ {i-1} b _ {i+1} \dots b _ {n} $
of length  $  n - 1 $, 
$  1 \leq  i \leq  n $. 
The numbers  $  N _ {s} ( \beta ) $
of words obtainable from  $  \beta $
by deletion of  $  s $
letters satisfies the following estimates

$$ 
\left ( \begin{array}{c}
\tau ( \beta ) - s + 1 \\
 s
\end{array}
 \right ) \  \leq  \  N _ {s} ( \beta ) \  \leq  \  \left ( \begin{array}{c}
\tau ( \beta ) + s - 1 \\
 s
\end{array}
 \right ) .
$$

Here  $  \tau ( \beta ) $
is the number of series of  $  \beta $(
by a series of a word  $  \beta = b _ {1} \dots b _ {n} $
one means a word  $  b _ {i+1} \dots b _ {j} $, 
$  j \geq  i + 1 $, 
such that 1)  $  b _ {i+1} = \dots = b _ {j} $; 
2) if  $  i \geq  1 $, 
then  $  b _ {i} \neq b _ {i+1} $; 
and 3) if  $  j < n $, 
then  $  b _ {j+1} \neq b _ {j} $). 
In particular,  $  N _ {1} ( \beta ) = \tau ( \beta ) $. 
By an insertion of a letter in a word  $  \beta = b _ {1} \dots b _ {n} $
one means a transformation of  $  \beta $
into a word  $  \beta  ^  \prime  = b _ {1} \dots b _ {i} b b _ {i+1} \dots b _ {n} $
of length  $  n + 1 $, 
where  $  b \in B $
and  $  0 \leq  i \leq  n $. 
The number of words obtainable from an arbitrary word  $  \beta $
of length  $  n $
by the insertion of  $  s $
letters of an alphabet  $  B $
is equal to

$$ 
\sum _ { j=0 } ^ { s } 
\left ( \begin{array}{c}
n + s \\
 j
\end{array}
 \right )
( r - 1 )  ^ {j} ,
$$

where  $  r $
is the number of letters in  $  B $. 
A set  $  K $
of words over the alphabet  $  B $
is called a code for correction of  $  s $
deletions (insertions, deletions or insertions) if no word in  $  B $
can be obtained from two distinct words of  $  K $
as the result of  $  s $
or fewer deletions (insertions, deletions or insertions) of letters in each of them. The function defined on the pairs  $  ( \beta _ {1} ,\  \beta _ {2} ) $
of words in  $  B $
and equal to the minimum number of deletions and insertions of letters converting  $  \beta _ {1} $
into  $  \beta _ {2} $
is a metric. A set  $  K $
of words over the alphabet  $  B $
is a code for correction of  $  s $
deletions (insertions, deletions or insertions) if and only if the distance between any two distinct words of  $  K $
is greater than  $  2 s $, 
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  $  \{ \beta = b _ {1} \dots b _ {n} \} $
of length  $  n $
over the alphabet  $  B = \{ 0 ,\  1 \} $
for which  $  \sum _ {i=1}  ^ {n} i b _ {i} \equiv 0 $(
$   \mathop{\rm mod} \  n + 1 $). 
The number of words in this code is equal to

$$ 

\frac{1}{2 ( n + 1 )}

\sum \phi (d) 2 ^ {( n + 1 ) / d} ,
$$

where the sum is taken over all odd divisors  $  d $
of  $  n + 1 $
and  $  \phi (d) $
is the Euler function; it is asymptotically maximal as  $  n \rightarrow \infty $.