Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Для того чтобы понять, как исправляются ошибки, сначала необходимо познакомиться с самим понятием ошибки. Если рассмотреть два кодовых слова, например 10001001 и 10110001, можно определить число отличающихся в них соответствующих разрядов. В данном примере отличаются 3 бита. Для нахождения этого числа нужно сложить два кодовых слова по модулю 2 (операция «исключающее или») и сосчитать количество единиц в результате, например:

10001001

+

10110001

00111000

Количество бит, которыми отличаются два кодовых слова, называется кодовым расстояниемили расстоянием между кодовыми комбинациями в смысле Хэмминга (Hamming, 1950). Смысл этого числа состоит в том, что если два кодовых слова находятся на кодовом расстоянии d, то для преобразования одного кодового слова в другое понадобится d ошибок в одиночных битах.

Зная алгоритм формирования контрольных разрядов, можно построить полный список всех допустимых кодовых слов и в этом списке найти такую пару кодовых слов, кодовое расстояние между которыми будет минимальным. Это расстояние называется минимальным кодовым расстояниемкода, или расстоянием всего кода в смысле Хэмминга.

В большинстве приложений передачи данных все 2 т возможных сообщений являются допустимыми, однако благодаря использованию контрольных бит не все 2 йвозможных кодовых слов используются. В действительности, если контрольных битов г, то допустимыми считаются лишь 2 т/2 иили 1/2 rкодовых слов, а не все возможные 2 т. Именно разреженность данных в пространстве кодовых слов позволяет получателю распознавать и исправлять ошибки.

Способности блочного кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Для надежного обнаружения d ошибок необходим код с минимальным кодовым расстоянием, равным d + 1, поскольку d однобитовых ошибок не смогут изменить одну допустимую комбинацию так, чтобы получилась другая допустимая комбинация. Когда приемник встречает запрещенную кодовую комбинацию, он понимает, что при передаче произошла ошибка. Аналогично, для исправления d ошибок требуется код с минимальным кодовым расстоянием, равным 2d + 1, так как в данном случае даже при d однобитовых ошибках результат окажется ближе к исходному кодовому слову, чем к любому другому и, следовательно, его можно будет однозначно восстановить. Это означает, что исходное кодовое слово можно восстановить уникальным образом, основываясь на предположении, что возникновение большого числа ошибок менее вероятно.

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

0000000000, 0000011111, 1111100000 и 1111111111

Этот код имеет расстояние, равное 5, это означает, что он может исправлять двойные ошибки и обнаруживать четверные ошибки. Если приемник получит кодовое слово 0000000111, ожидая только однобитные или двухбитные ошибки, он поймет, что оригинал должен быть равен 0000011111. Однако если тройная ошибка изменит 0000000000 на 0000000111, ошибка будет исправлена неверно. Если ожидать все перечисленные ошибки, то их можно распознавать. Ни одно из полученных кодовых слов не входит в список допустимых. Следовательно, произошла ошибка. Очевидно, что в данном примере невозможно одновременно исправлять двойные ошибки и распознавать четверные, потому что для этого полученное кодовое слово нужно будет интерпретировать двумя разными способами.

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

Попробуем создать код, состоящий из m информационных и r контрольных бит, способный исправлять одиночные ошибки. Каждому из 2 mдопустимых сообщений будет соответствовать n недопустимых кодовых слов, отстоящих от сообщения на расстояние 1. Их можно получить инвертированием каждого из n бит n-битового кодового слова. Таким образом, каждому из 2 mдопустимых сообщений должны соответствовать n + 1 кодовых комбинаций. Поскольку общее количество возможных кодовых комбинаций равно 2 n, получается, что (n + 1)2 m< 2 n. Так как n = m + r, это требование может быть преобразовано к виду: