Компьютерные сети. 6-е изд. - Эндрю Таненбаум

(r). В блочном коде (block code) r вычисляется как простая функция от m: r и m связаны друг с другом, как если бы они находились в огромной таблице соответствий. В систематическом коде (systematic code) m пересылается напрямую вместе с r и не кодируется перед отправкой. В линейном коде (linear code) r вычисляется как линейная функция от m. Очень часто используется функция исключающего ИЛИ (XOR) или суммирование по модулю 2. Это означает, что для кодирования используются такие операции, как умножение матриц или простые логические схемы. Далее в этом разделе речь пойдет о линейных систематических блочных кодах (если не будет указано иное).

Допустим, полная длина фрейма равна n (то есть n = m + r). Обозначим это как (n, m)-код. Набор из n бит, содержащий информационные и контрольные биты, часто называют n-битным кодовым словом, или кодовой комбинацией (codeword). Кодовая норма (code rate), или просто норма, — это часть кодового слова, несущая информацию, которая не является избыточной, то есть m/n. На практике значения нормы могут сильно отличаться. Например, для зашумленного канала обычной нормой считается 1/2, то есть половина полученной информации будет избыточной. В каналах высокого качества норма близка к единице и к большим сообщениям добавляется лишь несколько контрольных битов.

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

10001001

10110001

00111000

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

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

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

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

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

0000000000, 0000011111, 1111100000 и 1111111111

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

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

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

(m + r + 1) ≤ 2r (3.1)

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

Кроме того, этот теоретический нижний предел может быть достигнут с помощью метода Хэмминга (Hamming, 1950). В кодах Хэмминга биты кодового слова нумеруются последовательно слева направо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4, 8, 16 и т.д.), являются контрольными. Остальные биты (3, 5, 6, 7, 9, 10 и т.д.) заполняются m битами данных. Такой шаблон для кода Хэмминга (11, 7) с 7 битами данных и 4 контрольными битами показан на илл. 3.6. Каждый контрольный бит обеспечивает сумму по модулю 2 или четность некоторой группы битов, включая себя самого. Один бит может входить в несколько вычислений контрольных битов. Чтобы определить, в какие группы контрольных сумм будет входить бит данных в k-й позиции, следует разложить k на степень двойки. Например, 11 = 8 + 2 + 1, а 29 = 16 + 8 + 4 + 1. Каждый бит проверяется только теми контрольными битами, номера которых входят в этот ряд разложения (например, 11-й бит проверяется битами 1, 2 и 8). В нашем примере контрольные биты вычисляются для проверки на четность суммы в сообщении, представляющем букву «A» в кодах ASCII.

Илл. 3.6. Пример кода Хэмминга (11, 7), исправляющего однобитную ошибку

Расстояние Хэмминга этого кода равно 3, то есть он позволяет исправлять одиночные ошибки (или распознавать двойные). Причина такой сложной нумерации битов данных и контрольных битов становится очевидной, если рассмотреть процесс декодирования. Когда приходит кодовое слово, приемник учитывает значения полученных