Проблема состоит в том, чтобы передать информацию по каналу, изображенному на рис.1 и 2, как можно быстрее и надежнее. Решение, предлагаемое специалистами по теории кодирования, состоит в том, чтобы передавать по каналу связи не произвольные последовательности нулей и единиц, а только последовательности специального вида, называемые кодовыми словами. Список всех допустимых кодовых слов называется кодом. Он известен отправителю сообщений и их получателю, которые сотрудничают между собой, чтобы исключить ошибки, могущие возникнуть при передаче сообщения.
сообщение кодовое слово
│ │
┌──────────┐ шум ┌───────────┐
┌───────────┐да │Кодирующее│00000 ┌───────────┐01000│ Декоди- │Да
│Отправитель│───│ │──────│канал связи│─────│ рующее │───>
└───────────┘нет│устройство│11111 └───────────┘ │ устройство│
└──────────┘ │ └───────────┘
Принято
Рис. 3. Простой код с исправлением ошибок, состоящий из двух кодовых слов 00000 и 11111. Принятая последовательность 01000 правильно декодирована как сообщение "да".
Сообщения представлены кодовыми словами. Всякий раз, когда требуется послать то или иное сообщение, по каналу связи передается соответствующее кодовое слово. Получатель принимает некий (возможно, искаженный) вариант кодового слова, и декодирующее устройство должно определить, какое кодовое слово было послано, и тем самым восстановить переданное сообщение. На рис.3 показан простой пример кода: имеются всего два кодовых слова 00000 и 11111 длиной 5, соответствующих, например, сообщениям "да" и "нет". Предположим, что передано "да". Ему соответствует кодовое слово 00000, которое (из-за шума) принято как 01000. Декодирующее устройство учитывает малую вероятность ошибок (см. рис. 2) и поэтому решает, что было передано кодовое слово 00000, соответствующее сообщению "да". В общем случае декодирующее устройство выбирает кодовое слово, в каком-то смысле "наиболее близкое" к принятой последовательности нулей и единиц.
Сказанному можно придать точный смысл, если ввести понятие расстояния между двумя последовательностями сигналов. Расстоянием Хэмминга Рх(u,v) между двумя последовательностями u=(u1, u2, ..., un) и v=(v1, v2, ..., vn) длинной n называется число мест, в которых они различаются. Например,
Рх(010000,00000)=1,
Рх(010000,11111)=4.
Введя расстояние Хемминга, мы получаем возможность дать тому, кто занимается декодированием, более точные инструкции: принятую последовательность нулей и единиц следует декодировать как ближайшее к ней (в смысле расстояния Хемминга) кодовое слово. Именно оно с наибольшей вероятностью совпадает с переданным кодовым словом. Эта процедура изображена на рис. 3. Мы видим, что декодирующее устройство смогло исправить одну ошибку. В действительности такой позволяет исправить любые две ошибки. Например, если передана последовательность 00000, а принята последовательность 011000 (с ошибками во втором и третьем знаках), то последовательность 01100 все же ближе к истинному кодовому слову, чем к последовательности 11111. В то же время ясно, что такой код не может исправить три ошибки (приняв последовательность 11100, мы декодировали ее неправильно как 11111). Таким образом, рассматриваемый нами код позволяет исправить не более двух ошибок.
Как показывают те же рассуждения, для любого кода наиболее существенным параметром является минимальное расстояние Хемминга между кодовыми словами
d= min Px (u,v), при u неравно v
где минимум берется по всем парам различных кодовых слов u и v.
Действительно, если число ошибок не превышает e=[(d-1)/2], то
принятый "вектор"(последовательность сигналов -- "координат"
вектора) ближе к истинному кодовому слову, чем к любому другому.
Резюмируя, можно утверждать, что код с минимальным расстоянием d между кодовыми словами есть код, исправляющий e=[(d-1)/2] ошибок.