Как не ошибаться - Страница 105

105

Это и есть тайная геометрия кода Хэмминга. Кодовое слово представляет собой совокупность трех точек на плоскости Фано, образующих прямую линию. Изменение одного бита в строке равносильно прибавлению или исключению одной точки. Следовательно, если исходное кодовое слово было не 0000000, искаженное сообщение, которое вы получите, соответствует множеству из двух или из четырех точек. Если вы получите множество из двух точек, вам известно, как найти недостающую точку: это просто третья точка на единственной прямой, соединяющей две полученные вами точки. Что если вы получите множество из четырех точек, имеющее вид «прямая плюс одна дополнительная точка»? В таком случае вы можете сделать вывод, что правильное сообщение состоит из тех трех точек в вашем множестве, которые образуют прямую линию. Здесь есть одна тонкость: откуда вам известно, что существует только один способ выбора такого множества из трех точек? Давайте обозначим точки символами A, B, C и D. Если точки A, B и C лежат на прямой линии, тогда A, B и C должны быть тем самым множеством точек, которое намеревался передать вам отправитель. Но что если A, C и D также расположены на одной прямой? Не беспокойтесь: это невозможно, поскольку прямая, содержащая точки A, B и C, а также прямая, содержащая точки A, С и D, имели бы две общие точки – А и С. Однако две прямые линии могут пересекаться только в одной очке – таково правило. Другими словами, благодаря аксиомам геометрии код Хэмминга имеет такое же магическое свойство по исправлению ошибок, что и метод «повторить три раза»: если в процессе передачи в сообщении будет искажен один бит, получатель может вычислить, какое сообщение намеревался передать отправитель. Однако вместо увеличения времени передачи сообщения в три раза ваш новый усовершенствованный код позволяет отправлять семь бит на каждые три бита исходного сообщения, что обеспечивает более эффективный коэффициент 2,33.

Открытие кодов с исправлением ошибок, как первых кодов Хэмминга, так и разработанных впоследствии более эффективных кодов, преобразило проектирование информационных систем. Больше не требовалось создавать системы с двойной проверкой, нуждающиеся в столь сильной защите – защите, которая полностью исключала бы возможность ошибок. После открытий Хэмминга и Шеннона было достаточно сделать ошибки просто редкими, чтобы гибкость кода с исправлением позволяла нейтрализовать любые искажения. В настоящее время коды с исправлением ошибок используются в тех случаях, когда необходимо обеспечить быструю и надежную передачу данных. Орбитальный модуль Mariner 9 отправлял снимки поверхности Марса на Землю с использованием одного из таких кодов, кода Адамара. Компакт-диски кодируются с помощью кода Рида – Соломона – именно поэтому они звучат идеально, даже если их поцарапать. (Читатели, родившиеся после 1990 года и не знающие, что такое компакт-диски, могут просто вспомнить о картах флеш-памяти, в которых среди прочего используется код Боуза – Чоудхури – Хоквингема, чтобы предотвратить нарушение целостности данных.) Код вашего банка шифруется с помощью простого кода, который называется «контрольная сумма». Это не код с исправлением ошибок, а просто код с обнаружением ошибок, подобный протоколу «повторить каждый бит дважды». Если вы напечатаете одну цифру неправильно, компьютер, выполняющий перевод, может не понять, какое число вы на самом деле имели в виду, но он хотя бы определит, что что-то не так, и не отправит ваши деньги не в тот банк.

Не совсем ясно, когда именно Хэмминг понял весь диапазон применения своего нового метода, однако его руководство в Bell наверняка отдавало себе отчет, что стоит за его открытием. Хэмминг выяснил это, когда попытался опубликовать свою работу:

...

Патентный отдел не давал разрешение на публикацию до тех пор, пока не была обеспечена патентная защита… Я не верил, что они могут запатентовать кучку математических формул. Я так им и сказал. Они ответили: «Вот увидите». И были правы. С тех пор я понимаю, что плохо знаю патентное законодательство, поскольку часто бывает так, что вы вынуждены патентовать такие вещи, которые не нуждаются в этом, и это возмутительно.

Однако математика двигается вперед быстрее, чем патентное бюро. Швейцарский математик и физик Марсель Голей узнал об идеях Хэмминга от Шеннона и разработал много новых кодов, не зная о том, что Хэмминг разрабатывал такие же коды за завесой патентного права. Голей опубликовал свои работы первым, что повлекло за собой путаницу в отношении авторских прав, которая сохраняется до сих пор. Что касается патента, в Bell его получили, но потеряли право взимать деньги за лицензию в рамках антимонопольного соглашения 1956 года.

Что делает код Хэмминга столь эффективным? Чтобы понять это, необходимо взглянуть на ситуацию под другим углом и поставить вопрос так: что могло бы стать причиной его провала?

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

Что мы имеем в виду, когда говорим про «близость» одного блока к другому? На первый взгляд может показаться, что мы используем метафору, поскольку блоки двоичных знаков не имеют местоположения. По твердому убеждению Хэмминга, понятие близости отнюдь не метафора и таковой не должна восприниматься – именно в этом и заключался его важный концептуальный вклад. Он ввел новое понятие расстояния, которое теперь называется расстоянием Хэмминга. Концепция расстояния была адаптирована к новой математике информации точно так же, как расстояние Евклида и Пифагора было адаптировано к геометрии плоскости. Хэмминг дал простое определение: расстояние между двумя блоками символов – это количество битов, которые необходимо изменить, чтобы превратить один блок в другой. Таким образом, расстояние между кодовыми словами 0010111 и 0101011 равно 4; чтобы превратить первое кодовое слово во второе, необходимо изменить биты во второй, третьей, четвертой и пятой позициях.

105