Коды с обратной связью, исправляющие вставки и выпадения

Рассматривается задача передачи информации по комбинаторному каналу со вставками и выпадениями и обратной связью. Предположим, что отправитель передает $n$ двоичных символов один за другим по каналу, в котором могут происходить вставки и выпадения. После передачи каждого символа отправитель узнает, какие вставки и выпадения произошли в канале, и адаптирует алгоритм кодирования. Целью статьи является разработка стратегии кодирования, позволяющей безошибочно передавать максимальное количество информации в предположении, что общее количество вставок и выпадений не превосходит $\tau n$ для некоторой константы $\tau$, $0<\tau<1$. Мы покажем, как эта задача может быть сведена к задаче передачи информации по каналу с замещениями. Таким образом, максимальная асимптотическая скорость кодов для комбинаторного канала со вставками и выпадениями с обратной связью полностью установлена. Вычисление максимальной асимптотической скорости кодов для комбинаторного канала с замещениями и обратной связью было частично выполнено Берлекэмпом и окончено позже Зигангировым. Однако доказательство Зигангирова нижней оценки скорости достаточно сложное. Мы возвращаемся к результату Зигангирова и представляем более подробное доказательство нижней границы.