КОД С ИСПРАВЛЕНИЕМ ВЫПАДЕНИЙ И ВСТАВОК

- код, предназначенный для исправления ошибок двух типов, встречающихся при передаче и перфорации информации. Выпадением буквы в слове b=b₁ ...b_n длины пв нек-ром алфавите Вназ. преобразование слова b в слово b' = b₁.. .b_i-1b_i+1 ...,b _п длины п-1, Для числа N_s(b) слов, получаемых из слова р выпадениями sбукв, справедливы следующие оценки где т(Р) - число серий слова b (серией слова b=b₁, ... b _п наз. слово такое, что 1) b_i+1=...=b_j, 2) если то ' 3) если j<n, то ). В частности, N₁(b)=t(b). Вставкой буквы в слове b=b₁ ...b _п наз. преобразование слова b в слово b' = b₁ ... b_ibb_i.. .b_n длины n+1, где и Число слов, получаемых из произвольного слова b длины пвставками s букв алфавита В, равно где r- число букв алфавита В. Множество Кслов в алфавите Вназ. кодом с исправлением s выпадений (вставок, выпадений или вставок), если никакое слово в алфавите Вне может быть получено из двух различных слов из К в результате s или менее выпадений (вставок, выпадений или вставок) букв в каждом из них. Функция, определенная на парах (b₁, b₂) слов в алфавите Ви равная минимальному числу выпадений и вставок букв, преобразующих b₁ в b₂, является метрикой. Множество Кслов в алфавите Вявляется кодом с исправлением s выпадений (вставок, выпадений или вставок) тогда и только тогда, когда расстояние между любыми двумя различными словами из Кбольше 2s, так что указанные три определения кодов эквивалентны. Примером кода с исправлением одного выпадения или одной вставки является множество слов {b=b₁ ... b_n} длины пв алфавите В={0, 1}, для к-рых . Число слов в этом коде равно где суммирование производится по всем нечетным делителям dчисла n+1 и j(d) - функция Эйлера, и является асимптотически максимальным при

В. И. Левенштейн.