51. Корова или ворона?

Вероятно, каждый читатель знает комичНЫе истории, СвяЗанные с перевранными телеграммами. Достаточно Телеграфисту заменить одНУ точку на тире или случайно ДобаВить лишний знак и Одна-две буквы окажутся неверным, а тогда и вся телеграмма может получить ЗНачение, Противоположное НУжному.

ОсобенНО опасны ошибки при передаче данных в быстродействующих вычислительных машинах. ИзвестеН Случай, когда из-за неправильно поставленной ЗАпятоЙ Американцам пришлось подорвать уже взлетевшую Ракету-носитель, — оШИбка в программе привела к Недопустимому отклонениЮ от расчетной траектории. Поэтому БорьБа с шумами, с искажеНИями ТЕкстов — оДНа из важНых Проблем теории переДАчи иНФормации.

Остроумный способ борьбы с помехами предложил АмеРиКанский математик Хемминг. Он ввел класс кодов, Обладающих тем свойством, что при сбое происходит автоматическое исправленИЕ, аппарат как бы сам УгадыВает правильНОе написаНиЕ передаваемого текста. Чтобы ПОНЯть приНЦип кода Хемминга, замЕТим, что неприятности часТО происходят из-за того, что некоторые слова пишутся почти одинаково. Рассказывают, что одНАжды редактор провинциальНОй газеты поместил такое сообщение о коронации Николая II «Митрополит возложил на голоВУ Его Императорского ВелИЧества ворону». На другой деНЬ было дано исправление опечатки: Вместо «ворону» чИТать «корову».

Если бы осмыслеННые слова отличалИСь друг от друга, по крайней мере, 3 буквами, то при ошибке в одНОм месте сразу можно было бы найти, где она произошла и как еЕ Надо исправить.

Конечно, менять естественные языки невозможно. Но искусственные языки, которыми пользуются при передаче сообщений — телеграфные кодЫ, коды в ЭВМ и т. Д., мОжно делать такими, чтобы в них осмысленные слова находились на достаточном удалении друг от друга. При ЭТом обычно используют лишь «слова», которые являются кортежами одной и той же длины П из цифр 0 и 1, а ЗА расстояние между двумя словами принимают число мест, в которых они отличаются друг от друга (например, 0011001 находится на расстоянии 4 от 0101010 — эти кортежи отличны на втором, третьем, шестом и седьмом местах).

А теперь зададим какое-нибудь НАтуральное число R И выберем такое множество Х слов, что любые два слова из Х находятся друг от друга на расстояниИ большем, чем . Тогда, если при передаче какого-НиБудь слова из Х будет допущено не более чем R ошИБок, легко узнать, к какому слову из Х ближе всего полученНОе сообщенИЕ, и тем самым вОСстановить правильный текст. Например, если выбраны «слова» 000000, 000111, 111000, 111111, Находящиеся друг от друга на расстоянии 3, а получено сообщеНИе 100111, то оно ближе всего ко второму кодовому слову, СообщениЕ ЖЕ 000100 блИЖе к первому кодовому слову. Значит, ТакоЙ код ИСправляет любую ошИБку в одном знаке. Построение самоисцеляющихся кодов, конечно, происходит не бЕСплатно — ЗАпас осмысленнЫХ слов оказывается Меньше, чем запас всех слов заДАнНОй длины П (впрочем, и в естественных языках не любая совокупность знаков имеет смысл).

Поэтому важно знать, много ли можно выбрать кортежей длины П из чисел 0 и 1 так, чтобы любые два ВыБранных кортежа отличались друг от друга по краЙНеЙ Мере в координатах (при этом ясно, что чем больше R, тем меньше должно получиться кортежей). А Это Уже комбинаторная задача, и мы переходим из областИ Теории передачи информации в область комбИНаторИКи.

К сожалению, точного ответа здесь датЬ нельзя, — ЗАдача слишком сложна. Но в таких случаях доВОльствуются приближенными оценками, ПоказывающимИ практическую применимость или НЕприменимость предлагАЕмого кода. Обозначим через число искомых кортежей, а через сумму вида Тогда справедливы неравенства

Сам Хемминг предложИЛ код, Основанный на двоичной Системе Счисления. Номер каждого места, на котором в кортеже стоИТ 1, записывают в двоИЧной Системе счИСлЕНия. Кодовыми словамИ считают лишь те кортежИ, для которых Совокупность полученных записей имеет в каждом разряде четное число едИНИЦ. Например, Кортеж 1011010 — кодовое слово, так как в нем единИЦы стоЯТ НА 1-м, 3-м, 4-м и 6-м местах, а записи этих чисел в ДвоичноЙ Системе Счисления имеют вид 001, 01l, 100, 110; мы вИДИМ, что в НаборЕ этИХ запИСей 1 встречается по 2 раза на всех 3 местах (на первом Месте В 3-й и 4-й ЗАписИ, на втором во 2-й и 4-й, а на третьем в 1-й И 2-й). А кортеж 1011000 не является кодоВЫм словом, так кАК двоичные запИСи чИСел 1, 3 и 4 ИМЕЮт вид 001, 01l и 100, а в Этих запИСях На 1-м и 2-м местах едИниЦы встречаются лИШь по одному Разу, Т. е, нечетное чИСло раз.

Нетрудно доказать, что два кортежа, удовлетворяющИХ УСЛоВИЮ Хемминга, отлИЧаются друг от друга по крайней мере в 3 местах. Поэтому такой код может ИСправлять одну ошИБку в каждОМ кОДовом слове. Для П = 6 кодовые слова Хемминга таковы: 000000, 001011, 010101, 011110, 100110, 110011, 111000.

ИзученИЕ и построенИЕ кодов, исправляющИХ ошИБкИ, стало сейчас важной главой прИКладной математИКИ, ИСпользующЕЙ комбИНаторику, теорию информации и МНогие ветвИ общей аЛГебры (поля Галуа, группы и т. Д.).

< Предыдущая		Следующая >