Как не ошибаться

Прошу прощения, вы сказали «bofab»?

Плоскость Фано подсказывает нам, как без всякого риска играть в трансильванскую лотерею из семи чисел, но как насчет лотереи штата Массачусетс? Существует множество конечных геометрий с количеством точек, б
о

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

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

1110101…

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

1010101…

На первый взгляд может показаться, что это сообщение не очень отличается от предыдущего, но, если изменение одного бита информации приведет к замене команды «включить правый двигатель» на команду «включить левый двигатель», у спутника могут возникнуть серьезные проблемы.
Спутники ст
о

ят очень дорого, а значит, лучше избегать подобных проблемных ситуаций. Когда вы пытаетесь поговорить с приятелем на бурной вечеринке, то имеете возможность повторить сказанное, и ваши слова не утонут в общем шуме. Данный способ применим и в нашем случае: в исходном сообщении можно продублировать каждый бит, отправив 00 вместо 0 и 11 вместо 1:

11 11 11 00 11 00 11…

Теперь, когда космический луч выбьет второй бит сообщения, спутник увидит такую последовательность:

10 11 11 00 11 00 11…

Спутник
знает
, что каждый сегмент из двух бит должен представлять собой либо 00, либо 11, а значит, сигнал «10» – признак того, что что-то не в порядке. Но что именно? Спутнику трудно разобраться с этим, поскольку он не знает, в каком именно месте помеха исказила сигнал, не существует способа определить, как выглядело исходное сообщение – 00 или 11.
Но и эту проблему можно исправить, повторив каждый бит три раза вместо двух:

111 111 111 000 111 000 111…

Предположим, сообщение приходит в искаженном виде:

101 111 111 000 111 000 111…

Теперь спутник готов к этому. Он знает, что первый сегмент из трех бит должен представлять собой 000 или 111, а значит, присутствие 101 означает, что что-то пошло не так. Но, если в исходном сообщении была бы последовательность 000, это означало бы, что искажены два бита, расположенные в непосредственной близости друг от друга, – маловероятное событие, учитывая редкость космических лучей, искажающих сообщения. Следовательно, у спутника есть все основания применить принцип большинства: если два из трех бит содержат 1, велика вероятность, что в исходном сообщении была последовательность 111.

Вы только что увидели пример
кода с исправлением ошибок
 – протокол обмена данными, позволяющий получателю устранять ошибки в искаженном сигнале
[221]
. Эта идея, как практически и все остальное в теории информации, сформулирована в вышедшей в 1948 году и ставшей сразу классической работе Клода Шеннона Mathematical Theory of Communication («Математическая теория связи»)
[222]
.

Математическая теория коммуникации! Звучит несколько претенциозно, не так ли? Разве коммуникация – не сугубо человеческий вид деятельности, который нельзя свести к холодным цифрам и формулам?
Я хочу, чтобы вы понимали: я от всей души поддерживаю и 
настоятельно рекомендую
демонстрировать жесткий скептицизм по отношению к любым заявлениям, что ту или иную сущность можно объяснить, или укротить, или полностью понять математическими средствами.

Тем не менее история математики представляет собой историю агрессивной территориальной экспансии, поскольку математические методы становятся все более всеобъемлющими и богатыми, а математики находят способы изучать вопросы, которые раньше считались находящимися вне их области знаний. В наше время словосочетание «математическая теория вероятностей» выглядит вполне обычным, но когда-то могло показаться большим перегибом: математика занималась только изучением определенного и истинного, а не случайного и возможного! Ситуация изменилась, когда Паскаль, Бернулли и другие математики открыли математические законы, описывающие действие случая

[223]
. Математическая теория бесконечности? До работы Георга Кантора в XIX столетии изучение бесконечности было не столько наукой, сколько теологией; сейчас мы понимаем теорию Кантора о множественности бесконечностей, каждая из которых бесконечно больше предыдущей, настолько п
о
лно, что преподаем эту тему первокурсникам, изучающим математику. (По правде сказать, она действительно поражает их воображение.)

Формальные математические модели не охватывают все детали того феномена, который описывают, они и не должны этого делать. Например, существуют вопросы о случайности – на них теория вероятностей не дает ответа. В понимании некоторых людей проблемы, остающиеся вне досягаемости математики, представляют собой самые интересные вопросы. Но в наши дни было бы ошибкой размышлять о случае, не опираясь на теорию вероятностей. Если не верите мне, спросите Джеймса Харви. Или, что еще лучше, спросите об этом у людей, чьи деньги он выиграл.

Появится ли когда-либо математическая теория сознания? Общества? Эстетики? Кто-то наверняка пытается создать такие теории, но пока безуспешно. Заявления такого рода д
о
лжно каждый раз подвергать сомнению, полагаясь на интуицию. Но также следует помнить, что в конечном счете они могут правильно интерпретировать некоторые вещи.

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

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

. Подобно тому как труба пропускает только определенное количество воды, канал связи также передает только определенный объем информации.
Однако для исправления ошибок не обязательно сокращать пропускную способность канала связи, как того требует протокол «повторить три раза». Шеннон знал, что их можно исправить более эффективно, поскольку Ричард Хэмминг, его коллега по Bell Labs, уже понял, как решить данную проблему.

У Хэмминга, молодого ветерана Манхэттенского проекта, в Bell Labs был доступ к десятитонной релейной вычислительной машине Model V, однако уровень его допуска позволял ему работать с этой машиной только по выходным
{191}

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

Первый шаг Хэмминга состоял в разбиении сообщения на блоки, состоящие из трех символов:

111 010 101…

Код Хэмминга
[224]
 – правило, в соответствии с которым каждый блок из трех цифр преобразуется в последовательность из семи цифр. Вот таблица кодирования:

000 → 0000000
001 → 0010111
010 → 0101011
011 → 0111100
101 → 1011010
110 → 1100110
100 → 1001101
111 → 1110001

Таким образом, кодированное сообщение будет выглядеть так:

1110001 0101011 1011010…

Перечисленные выше блоки из семи бит называются
кодовыми словами

. Эти восемь кодовых слов представляют собой единственные восемь блоков, которые разрешает данный код; если получатель видит что угодно другое, значит, что-то наверняка пошло не так. Предположим, вы получили блок 1010001. Вы знаете, что он не может быть правильным, потому что 1010001 – не кодовое слово. Более того, полученное вами сообщение отличается от кодового слова 1110001 всего на одну позицию. Другого кодового слова, которое было бы столь близким к искаженному сообщению, не существует. Следовательно, вы можете с довольно высокой степенью уверенности предположить, что кодовое слово, которое намеревался передать отправитель, – 1110001, а это означает, что соответствующий блок из трех цифр в исходном сообщении был 111.

Наверное, сейчас вы подумали, что нам просто повезло. Разве загадочное сообщение не могло быть близким к двум разным кодовым словам? В таком случае мы не имели бы возможности дать однозначную оценку. Но этого никогда не произойдет, и вот почему. Посмотрите еще раз на линии плоскости Фано:

124
135
167
257
347
236
456

Как бы вы описали данную геометрию компьютеру? Компьютеры любят, чтобы с ними разговаривали в нулях и единицах, поэтому нужно записать каждую линию в виде последовательности цифр 0 и 1, где 0 на позиции
n
 означает «точка
n
 находится на линии», а 1 на позиции
n
 означает «точка
n
 не находится на линии». Таким образом, первая линия, 124, будет представлена в таком виде:

0010111

а вторая, 135, – в таком:

0101011

Обратите внимание, что обе строки символов представляют собой кодовые слова из кода Хэмминга. В действительности семь ненулевых кодовых слов из кода Хэмминга в точности соответствуют семи линиям плоскости Фано. Код Хэмминга и плоскость Фано (а также, если уж на то пошло, оптимальная совокупность билетов для трансильванской лотереи) – один и тот же математический объект, но в разных нарядах!

Это и есть тайная геометрия кода Хэмминга. Кодовое слово представляет собой совокупность трех точек на плоскости Фано, образующих прямую линию. Изменение одного бита в строке равносильно прибавлению или исключению одной точки. Следовательно, если исходное кодовое слово было не 0000000, искаженное сообщение, которое вы получите, соответствует множеству из двух или из четырех точек
[225]

. Если вы получите множество из двух точек, вам известно, как найти недостающую точку: это просто третья точка на единственной прямой, соединяющей две полученные вами точки. Что если вы получите множество из четырех точек, имеющее вид «прямая плюс одна дополнительная точка»? В таком случае вы можете сделать вывод, что правильное сообщение состоит из тех трех точек в вашем множестве, которые образуют прямую линию. Здесь есть одна тонкость: откуда вам известно, что существует только
один

способ выбора такого множества из трех точек? Давайте обозначим точки символами
A, B, C
 и 
D
. Если точки
A, B
 и 
C
 лежат на прямой линии, тогда
A, B
 и 
C
 должны быть тем самым множеством точек, которое намеревался передать вам отправитель. Но что если
A, C
 и 
D
 также расположены на одной прямой? Не беспокойтесь: это невозможно, поскольку прямая, содержащая точки
A, B
 и 
C
, а также прямая, содержащая точки
A, С
 и 
D
, имели бы две общие точки –
А
 и 
С

. Однако две прямые линии могут пересекаться только в 
одной
очке – таково правило
[226]

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

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

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

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

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

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

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

. Что касается патента, в Bell его получили, но потеряли право взимать деньги за лицензию в рамках антимонопольного соглашения 1956 года
{194}
.
Что делает код Хэмминга столь эффективным? Чтобы понять это, необходимо взглянуть на ситуацию под другим углом и поставить вопрос так: что могло бы стать причиной его провала?
Помните: настоящее проклятие любого кода с исправлением ошибок – это блок цифр, который очень близок к 
двум

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

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

Восемь кодовых слов Хэмминга – хороший код, поскольку ни один блок из семи бит не находится на расстоянии Хэмминга между двумя кодовыми словами, равному 1. Если бы это было так, два кодовых слова были бы на расстоянии Хэмминга 2 друг от друга
[227]

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

Этот же принцип лежит в основе всех возможных каналов коммуникации, устойчивых к помехам. Именно так устроен естественный язык: если я напишу
lanvuage
вместо
language
(«язык»), вы поймете, что я имел в виду, поскольку в английском языке это единственное слово, которое можно получить посредством замены одной буквы в слове
lanvuage
. Безусловно, данный принцип не сработает при употреблении односложных слов:
dog, cog, bog
и 
log

 – каждое из этих слов имеет свое значение в английском языке, но всплеск шума, заглушающий первую фонему, не позволит распознать, что именно имелось в виду. Однако даже в таком случае можно использовать семантическое расстояние между словами, чтобы исправить ошибки. Если вас что-то укусило, значит, это
dog
(«собака»); если вы с чего-то упали, то это
log
(«бревно») и так далее.

Язык можно сделать более эффективным, но при этом возникает тот же негативный побочный эффект, с которым столкнулся Шеннон. В свое время многие люди, и упертые зануды и те, кто обладал математическими наклонностями,
[228]

потратили массу усилий на создание языков, которые обеспечили бы компактную и точную передачу информации без всякой избыточности, синонимии и двусмысленности – всего того, чем грешат такие языки, как английский. Священник Эдвард Пауэлл Фостер создал в 1906 году искусственный язык Ро, с тем чтобы заменить дебри английского словаря лексиконом, в котором значение каждого слова можно было логически вывести из его звучания
{195}

. Пожалуй, нет ничего удивительного в том, что среди горячих приверженцев языка Ро был Мелвилл Дьюи, который создал десятичную систему классификации, обеспечивающую расположение книг на полках библиотек в строгом порядке. Лаконичность языка Ро действительно заслуживает восхищения. Многие длинные английские слова, такие как
ingredient
, на языке Ро становятся гораздо короче – просто
cegab

. Однако подобная лаконичность имеет свою цену: она сопровождается потерей возможности исправлять ошибки, присутствующей в английском языке как встроенная функция. Это как маленькая, заполненная до отказа кабинка лифта, в которой у пассажиров нет дополнительного личного пространства. Другими словами, каждое слово на языке Ро очень похоже на многие другие слова, что создает возможности для путаницы. Например, на языке Ро «цвет» – это
bofab

. Но если вы измените всего одну букву, получаются следующие слова: «звук» –
bogab
; «электричество» –
bokab; bolab
 – «вкус». Более того, в логической структуре языка Ро слова с похожим звучанием имеют похожее значение. Это обстоятельство еще больше усугубляет ситуацию, поскольку не позволяет по контексту понять, что происходит. Слова
bofoc, bofof, bofog
и 
bofol

Все материалы, размещенные в боте и канале, получены из открытых источников сети Интернет, либо присланы пользователями  бота. 
Все права на тексты книг принадлежат их авторам и владельцам. Тексты книг предоставлены исключительно для ознакомления. Администрация бота не несет ответственности за материалы, расположенные здесь