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
.
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