Код С Исправлением Выпадений И Вставок

- код, предназначенный для исправления ошибок двух типов, встречающихся при передаче и перфорации информации. Выпадением буквы в слове b=b1 ...bn длины пв нек-ром алфавите Вназ. Преобразование слова b в слово b' = b1. .bi-1bi+1 ...,b п длины п-1, Для числа Ns(b) слов, получаемых из слова р выпадениями sбукв, справедливы следующие оценки где т(Р) - число серий слова b (серией слова b=b1, . B п наз. Слово такое, что 1) bi+1=...=bj, 2) если то ' 3) если j<n, то ). В частности, N1(b)=t(b). Вставкой буквы в слове b=b1 ...b п наз. Преобразование слова b в слово b' = b1 . Bibbi. .bn длины n+1, где и Число слов, получаемых из произвольного слова b длины пвставками s букв алфавита В, равно где r- число букв алфавита В.

Множество Кслов в алфавите Вназ. Кодом с исправлением s выпадений (вставок, выпадений или вставок), если никакое слово в алфавите Вне может быть получено из двух различных слов из К в результате s или менее выпадений (вставок, выпадений или вставок) букв в каждом из них. Функция, определенная на парах (b1, b2) слов в алфавите Ви равная минимальному числу выпадений и вставок букв, преобразующих b1 в b2, является метрикой. Множество Кслов в алфавите Вявляется кодом с исправлением s выпадений (вставок, выпадений или вставок) тогда и только тогда, когда расстояние между любыми двумя различными словами из Кбольше 2s, так что указанные три определения кодов эквивалентны. Примером кода с исправлением одного выпадения или одной вставки является множество слов {b=b1 .

Bn} длины пв алфавите В={0, 1}, для к-рых . Число слов в этом коде равно где суммирование производится по всем нечетным делителям dчисла n+1 и j(d) - функция Эйлера, и является асимптотически максимальным при В. И. Левенштейн..