Код без ошибок

В начале сентября в возрасте 82 лет умер советский и российский математик Владимир Иосифович Левенштейн. С его именем связано открытие, сыгравшее важную роль в развитии передачи информации с помощью двоичного кода. Мы решили вспомнить об этой статье Левенштейна, опубликованной еще в 1965 году, которая до сих остается самой цитируемой работой российского математика, включенной в мировую базу научных ресурсов.

Владимир Иосифович был автором многих замечательных работ: в 1978 году он вместе с Григорием Кабатянским получил лучшие на сегодняшний день асимптотические оценки плотности упаковки шаров. Годом позже он (одновременно с математиками Эндрю Oдлыжко и Нилом Слоуном) решил проблему контактных чисел для размерностей 8 и 24. Контактное число — это число шаров единичного радиуса, которые могут одновременно касаться одного такого же шара. На плоскости (где, разумеется, речь идет о кругах) контактное число равно 6, в трехмерном пространстве — 12, в четырехмерном — 24, в пятимерном — ... а вот тут уже точно неизвестно, доказано только, что это значение лежит между 40 и 44. Вообще говоря, для n>4 контактное число точно вычислено только для двух размерностей — 8 (там оно равно 240) и 24 (контактное число — 196560) — это и сделал Владимир Левенштейн в работе 1979 года.

Но самой известной стала совсем короткая, всего в несколько страниц, статья Левенштейна, опубликованная в докладах АН СССР в 1965 году (.pdf, на англ. языке). Она касалась проблемы передачи информации — как сделать читаемым сообщение, которое нужно отправить через некачественный канал определенного вида. В этой работе Владимир Левенштейн ввел понятие особой метрики — расстояния между последовательностями нулей и единиц, которое стали называть редакторской метрикой, или расстоянием Левенштейна, и широко используют и сегодня в самых разных областях — от машинных переводчиков до генетики.

Согласно базе Google Scholar, на эту работу с тех пор сделано 8123 ссылки (и их количество продолжает расти почти каждый день на две-три) — это одна из самых, а может быть и просто самая цитируемая статья в истории российской и советской математики, в этом отношении Владимиру Левенштейну удалось опередить даже великого советского математика Андрея Николаевича Колмогорова (1903-1987), на самую цитируемую статью которого (.pdf, на англ. языке) сослались (на день написания этой заметки) 8089 раз.

Об основных результатах статьи-рекордсмена мы расскажем подробнее.

Пусть у нас есть канал связи, передающий информацию в виде двоичного кода. Он может приводить к искажениям разного рода, их в общем можно отнести к одному из трех типов — это замена (1 на 0 или 0 на 1), выпадение ( когда 0 или 1 переходят в пустое множество) и вставка (когда пустое множество переходит в ноль или один). Поставим задачу так: можно ли особым образом составить исходное сообщение так, чтобы на выходе, несмотря на замены, выпадения и вставки, информация осталась бы максимально понятной?

Будем называть кодом некое множество двоичных слов одинаковой длины. Будем говорить, что код К способен исправить s выпадений (вставок), если из разных слов кода нельзя получить одно и то же слово, делая не более чем s выпадений (вставок).

Например: код, состоящий из двух слов длины 5 — 00001 и 10111 может исправить два выпадения. Действительно, из первого слова с помощью одного выпадения можно получить такие два слова: 0001 и 0000, а с помощью двух выпадений еще два — 000 и 001. А из 10111 одним выпадением получаем 1011, 0111 и 1111, а двумя — 101, 111 и 011. Видно, что все слова в этих двух наборах разные. На практике это означает, что если мы будем передавать слова кода по не слишком качественному каналу, который может допустить до двух выпадений, по результату можно однозначно восстановить исходное слово. Видите на выходе 111? Вам отправили 10111. Получили 0001? На входе было 00001.

Этот пример — про коды, способные исправлять выпадения. На самом деле, он же подойдет для вставок. Вариантов, которые можно получить из исходных слов с помощью не более чем двух вставок, довольно много, и мы не будем их приводить. Да это и не нужно, потому что можно доказать лемму: если код K способен исправить s выпадений, он способен исправить любые выпадения и вставки, количество которых в сумме не больше s. Доказательство очень простое, но чтобы была ясна идея, давайте для простоты разберемся, почему код, способный исправить 2 выпадения, исправит и две вставки. Действительно: пусть из двух разных слов кода x и y с помощью двух вставок получается одно и то же слово z. Давайте удалим из z и те символы, на которые оно отличается от x, и те, на которые оно отличается от y. Получилось слово w, и если подумать, его можно получить и из x и из y не более чем двумя выпадениями. Противоречие!

В этой же логике на множестве всех двоичных слов можно задать метрику: расстоянием r между двумя словами будем называть минимальное общее количество вставок и выпадений, которое нужно произвести, чтобы получить одно слово из другого. Например, расстояние между 00001 и 10111 из нашего примера — 6, так как чтобы из первой последовательности получить вторую, в нее нужно добавить три единицы и удалить три нуля. Ясно, что r симметрична и выдерживает неравенство треугольника, поэтому это действительно метрика в математическом смысле — сейчас ее называют «редакторской метрикой». Очевидно, что код K может исправить s вставок/выпадений, если и только если редакторское расстояние между двумя любыми словами из K строго меньше 2s.

Интуитивно ясно, что число слов в исправляющем ошибки коде не должно быть слишком большим — чем больше слов, тем больше шансов, что какие-то результаты вставок и выпадений совпадут. Можно ли оценить размер L_s(n) максимального кода из слов длины n, способного исправить s выпадений/вставок? Левенштейн приводит асимптотическую оценку: при n стремящемся к бесконечности:

2^s(s!)²2ⁿ / n^2s ≲ L_s(n) ≲ s! 2ⁿ / n^s

Из этой оценки (ее не очень сложное, но техническое доказательство можно найти в оригинальной работе) следует ключевой результат статьи: размер максимального по количеству слов кода, исправляющего одну вставку/выпадение, растет довольно быстро с n:

L₁(n) ~ 2ⁿ / n

В ходе доказательства этого утверждения автор указывает (следуя конструкции Варшамова-Тененгольца) явный способ построения кодов, исправляющих одно выпадение. Пусть n — некое число букв, m хотя бы на единицу превышает n, и а — один из возможных остатков по модулю m, то есть число от 0 до m-1. Будем брать такие слова из n букв x_1... x_n, что сумма всех i*x_i дает остаток а по модулю m. Оказывается, набор всех таких слов для фиксированных n, m и а — код, исправляющий одно выпадение (а значит, как мы уже знаем, и вставку).

Тут, конечно, нужен пример, и давайте возьмем n=4, m=5, а =0. Четырехбуквенных двоичных слов конечно же 16 — это 0000, 0001, 0010, 0100, 1000, 0011, 0110, 1100, 1001, 1010, 0101, 0111, 1110, 1011, 1101, 1111. Пусть X(w) — сумма произведений номера позиции с цифрой, стоящей на этой позиции в слове w, тогда

X(0000) = 0, X(0001) = 4, X(0010) = 3, X(0100) = 2, X(1000) = 1, X (0011) = 7, X(0110) = 5, X(1100) = 3, X(1001) = 5, X(1010) = 4, X(0101) = 6, X(0111) = 9, X(1110) = 6, X(1011) = 8, X(1101) = 7, X(1111) = 10.

По модулю 5 остаток 0 здесь имеют четыре слова — 0000, 0110, 1001 и 1111. Легко убедиться, что код из этих четырех слов исправляет выпадения, то есть, если вспомнить исходную проблему, отправляя эти слова через канал, который может случайным образом удалить одну букву, вы все равно сможете расшифровать исходное сообщение.

Кстати, теперь можно разобраться, как доказывается основное утверждение — о числе таких кодов. Исходя из предыдущей асимптотической оценки, достаточно проверить, что выполняется неравенство:

L₁(n) ≥ 2ⁿ / (n+1)

Возьмем m = n+1. Ясно, что любое бинарное слово длины n входит в один из кодов, построенных по n, n+1 и некоему остатку а. Общее число бинарных слов — 2^n, а кодов столько же, сколько остатков, то есть n+1. Значит, хотя бы в одном из них должно быть не меньше 2^n/(n+1) слов. Вуаля. Для случая с n=4 теорема утверждает, что найдется хотя бы один код, исправляющий одну вставку/выпадение, количество слов в котором не меньше 16/5. Действительно — чуть выше мы построили код из четырех слов.

В этой совсем небольшой статье Владимир Левенштейн также обращается к кодам, исправляющим вставки, выпадения и замены, и дает оценку на максимальную длину такого кода (обратите внимание, что поскольку канал стал еще хуже, то и число слов в коде сократилось):

2^n-1 / n ≤ M₁ (n) ≤ 2ⁿ / (n+1)

Кроме того, он вкратце обсуждает возможную практическую проблему: передавая по некачественному каналу подряд идущие слова даже хорошего кода, на выходе нужно как-то выяснить, где заканчивается одно и начинается другое. Для этого автор предложил «довешивать» в начало и конец слов кода специальные узнаваемые разделительные последовательности, которые не повлияют на способность кода исправлять ошибки и которые можно узнать в выходном сигнале.

И все же главных результатов статьи, которым она и обязана своим рекордным цитированием, два. Во-первых, это явное построение кодов, исправляющих одну ошибку. Эту задачу Левенштейн решил в 1965 году и за прошедшие более чем полвека мы практически не продвинулись — способа явного построения оптимальных кодов, исправляющих большее количество ошибок, никто до сих пор не придумал (хотя достигнуты кое-какие асимптотически результаты). Во-вторых, это «редакторское» расстояние между двоичными словами, которое определяется как минимальное количество вставок, выпадений и замен (в общем варианте определения), необходимое, чтобы превратить одно слово в другое.

Сергей Немалевич