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

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

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

Конечно, много таким кодом не передашь, но для примера вполне достаточно. Еще важно, что получатель знает наш «словарь», то есть ожидает от нас либо 111000, либо 001110, либо 100011 и ничего другого.

Предположим, мы сначала передаем слово 111000. В результате не более чем одной ошибки (ошибки мы выделили жирным шрифтом) оно может превратиться в одно из слов:

111000, 011000, 101000, 110000, 111100, 111010, 111001, (3.1)

включая, как видите, само себя. Аналогично при передаче слова 001110 может получиться любое из слов:

001110, 101110, 011110, 000110, 001010, 001100, 001111. (3.2)

Наконец, для 100011 у нас выйдет:

100011, 000011, 110011, 101011, 100111, 100001, 100010. (3.3)

Замечательно то, что списки (3.1) (3.3) попарно не пересекаются. Иными словами, если на другом конце канала связи появляется любое слово из списка (3.1), получатель точно знает, что ему передавали именно слово 111000, а если появляется любое слово из списка (3.2) слово 001110; то же самое касается и списка (3.3). В этом случае говорят, что наш код исправил одну ошибку.

За счет чего произошло исправление? За счет двух факторов. Во-первых, получатель знал весь «словарь». Когда код передавался всего с одной ошибкой, выходило слово, которого в словаре не было.

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

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