Все мы знаем, что дураки учатся на своих ошибках, а умные люди на чужих. Но имеет ли это какое-то отношение к математике? Не правда ли это? Можно ли создать теорию исправления ошибок?
Такая теория существует, она называется «теория кодирования». К сожалению, она не имеет дела с ошибками по жизни — это не так просто, и математическая модель не очень ясна. Но тем не менее такая теория есть.
Первая работа по теории кодирования была опубликована известным ученым Ричардом Уэсли Хэммингом в 1950 году. Привело его к этой работе следующее: после окончания университета он занимался тем, что сейчас бы назвали численными методами, и работал сначала в Лос-Аламосе над Манхэттенским проектом, то есть над созданием ядерной бомбы, а потом почти сразу, в 1946 году, перешел в Bell Labs. Это та великая лаборатория, в которой было сделано, наверное, самое большое количество открытий второй половины XX века. Там он продолжал заниматься численными методами, решать уравнения на первых вычислительных машинах.
Вычислительные машины были огромными, ненадежными, потому что на лампах, и для их охлаждения требовались не «ниагары», но большое количество воды, и тем не менее они часто сбоили. Программисты того времени, чтобы бороться со сбоями, делили задачу на этапы, и после каждого этапа программа должна была записать или распечатать результаты. Тогда задачи были простенькие по теперешним понятиям, в основном счет.
Зачем это делалось? Так как эти компьютеры были ненадежными, у них было такое устройство, как сигнал тревоги. Когда работа шла неверно, когда они обнаруживали ошибку, то звучал сигнал тревоги, и работа прекращалась. Соответственно, человек мог с этого места посмотреть назад, какое было первое от этого места правильно посчитанное значение, и продолжать счет дальше. Хэмминг оставлял свою работу на выходные и уходил спокойно отдыхать, а приходя, обнаруживал, что машина работала впустую, потому что в некий момент происходила ошибка, но никого не было, его не было, чтобы остановить. Значит, все его труды пропадали даром. Тогда у него возникла совершенно естественная даже не идея, а вопрос: если машина умеет обнаруживать ошибки, почему бы не научить ее, чтобы она их исправляла?
Как машина обнаруживает ошибки? Это совсем просто. У нас есть то, чем работает машина, — это двоичные записи из нулей и единичек, и мы просто добавляем туда еще один разряд, который называется проверка на четность. В этот разряд мы пишем единичку, если в информации у нас нечетное число единиц, и нолик, если число единиц в информации было четное. Тогда в результирующей последовательности с еще одним добавленным символом у нас всегда четное число единиц. Поэтому соответствующее устройство проверяет, было ли там четное число единиц — то, с чем оно работает. Если да, то продолжает работать, если нет, то работает этот самый аларм.
Что пришло в голову Хэммингу? Он подумал, почему, собственно, проверять все значения? Может, одного проверочного символа недостаточно? Может быть, добавить не один, а два, три, четыре — столько, сколько понадобится, и исправлять?
И он придумал для начала, наверное, самый известный код — так называемый (7,4) код Хэмминга.
4 означает, что мы будем защищать от ошибок 4 бита информации, а 7 — что для этого мы к 4 информационным битам добавим 3 проверочных. Итого у нас всего будет 7 бит. Нам нужно написать три проверочных соотношения.
В первое соотношение попадают все нечетные позиции, то есть 1-я, 3-я, 5-я и 7-я. Во второе соотношение попадают позиции 2, 3 — следующие две позиции мы пропускаем — и 6, 7. Последнее, третье, соотношение тоже очень простое — это последние 4 позиции. Казалось бы, и все.
Какой во всем этом смысл? Эти проверочные соотношения будем проверять, как в случае обычной проектной отчетности. Но будем делать это три раза. Одно соотношение, второе и третье. Если проверка выполняется, то мы пишем в соответствующую позицию нолик, если не выполняется, то единичку. У нас получается вектор из 3 бит, который называется синдромом. Синдромом — потому что если все соотношения выполнены, то это кодовое слово, наш вектор не болен. А если есть хотя бы одна единичка, то он болен, и мы будем его лечить.
Как мы собираемся его лечить? Посмотрим на этот вектор из 3 нулей и единичек и, как нас в школе учат, напишем систему линейных уравнений: 3 уравнения с 7 неизвестными, и там столбцы коэффициентов. Мы найдем, где стоит столбец, равный синдрому, и скажем: ошибка была ровно в этой позиции. Более того, в данном случае это совсем просто: синдром, если на него посмотреть как на целое число в двоичном представлении, — это и есть место, где произошла ошибка.
Мы что-то придумали, это работает, но для ученых всегда важно знать: это самое лучшее — то, что мы придумали, или можно сделать лучше? Хэмминг тут же показал, что нет. Что мы сделали? Мы семью битами передали 16 сообщений, 4 информационных бита. А вот 17 сообщений — не говоря уже о 5 битах, а просто 17 сообщений — мы уже так передать, так закодировать не сможем. Почему? Ответ довольно простой, и заодно мы подумаем, какую, собственно, задачу мы решаем. Мы сделали конструкцию. Конструкцию чего? Что такое код, исправляющий одиночную ошибку?
Как происходит одиночная ошибка? Код — это произвольное множество двоичных векторов какой-то фиксированной длины, в данном случае у нас была длина 7. Мы выбрали какое-то подмножество, назвали его кодом. Теперь мы передаем в канал, в памяти пишем кодовое слово. В результате одиночной ошибки наше кодовое слово может измениться. Каким образом? Какой-то бит будет инвертирован, нолик превратится в единицу, единичка в нолик. Когда будет нехорошо? Нехорошо будет, если мы посылаем по тому же самому каналу другое сообщение, в нем происходит другая ошибка, а в результате на выходе получается одно и то же слово. Тогда мы, как буриданов осел, не знаем, что нам выбрать: воду или охапку сена. Чтобы этого не случилось, нам нужно, чтобы они были разными.
Сколько других векторов у нас получается из одного вектора длиной 7 с помощью одной ошибки? Можно сделать ошибку в любой из 7 позиций, это 7 векторов, 7 последовательностей, плюс самый исходный вектор — 8. Теперь каждое кодовое слово тем самым порождает 8 слов, а всего слов 128. Значит, больше написать я не могу — 128 поделить на 8. Это как раз и есть тот ответ, который мы хотели получить, — 16.
Теперь можно перейти к тому, что венгры любят называть уличной математикой. Мы останавливаем человека на улице, даем ему какую-то простую математическую задачу и говорим: попробуй-ка ее решить. Она должна быть такой простой, чтобы ее можно было понять сразу, и должна выглядеть так наивно, чтобы он мог подумать, что сейчас ее и решит, особенно если пообещать какой-нибудь денежный приз.
Так, кстати, начинал (не по этой причине) великий венгерский математик Эрдёш. Он к своим задачам приделывал такие таги — сколько долларов он заплатит за ее решение. Суммы по теперешним дням небольшие и большей частью невостребованные.
Вот какую задачу ему дали: «Представим себе, что у нас есть алфавит из двух букв: А и Б», — чтобы не пугать человека с улицы, нули и единички заменяем на А и Б. Напишите нам побольше слов длиной 7, 8, 10 — то, которое мы вам скажем, — так, чтобы они различались как минимум в трех позициях. Почему в трех — это легко понять из того, о чем мы только что говорили: чтобы одиночные ошибки не привели к коллизии. Если у нас расстояние 2, то легко привести тот же пример, который приведет к такой коллизии, когда два разных слова в результате одиночных ошибок приведут в одно и то же.
Что наука знает в качестве ответов? Задача кажется совсем простой, но Хэмминг сказал: если длина 7, то слов у нас 16, если длина 8, то слов у нас оказывается 20, если длина 9, то слов оказывается 40, дальше хочется сказать, что 80, но нет — 72 и 144. И как ни странно, чтобы доказать, что 72, понадобилось довольно много времени, и было доказано только в 1999 году, и компьютер здесь почти ни при чем. Это для тех, кто любит поиграть числами, чтобы доказать, что нет кода из 73 позиций, надо было перебрать все подмножества мощности 73 из 1024 точек. Это какое-то число, не поддающееся ни сегодняшним, ни завтрашним компьютерам. Мы знаем эти ответы до 15 включительно, а потом мы знаем только асимптотику, и то асимптотика — это вещь такая приятная, но в каком-то смысле неожиданная.
Чего мы не знаем? Например, мы не знаем аналоги кода Хэмминга для цифр, мы не знаем, есть они или нет.
Можно ли сделать так же, как сделал Хэмминг, для алфавита из 10 букв: 0, 1, 2… 9. Эта задача, которой столько же лет, сколько теории кодирования, она совершенно не поддается пока своему решению.
Коды, исправляющие ошибки, были рождены практикой. Сами коды Хэмминга до сих пор используются на практике, но не для передачи информации, а для защиты памяти компьютеров — они до сих пор там популярны. Для того чтобы исправлять ошибки в коммуникациях — а они нас окружают сейчас везде, — нам нужно исправлять не одиночные ошибки, а десятки, сотни, может быть, даже тысячи ошибок в зависимости от той длины кода, который мы выбираем. Здесь, к сожалению, теория не дает окончательных ответов. Все это достаточно быстроразвивающаяся область, особенно потому, что идет постоянный запрос от того, что мы сами каждый день в каком-то смысле «кушаем»: от интернета, от мобильной телефонии. Вы можете легко вспомнить, что еще не так давно мы были довольны, когда у нас был телефонный модем, который работал со скоростями несколько килобит в секунду, а сейчас мы недовольны, если это несколько мегабит в секунду. Впереди, к 2020 году, должно быть очередное «светлое будущее» под названием 5G, и какие там будут коды и что они будут делать — это пока вопрос нерешенный.
