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

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

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

Для того чтобы понять, как исправляются ошибки, сначала необходимо познакомиться с самим понятием ошибки. Если рассмотреть два кодовых слова, например 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, ошибка будет исправлена неверно. Если ожидать все перечисленные ошибки, то их можно распознавать. Ни одно из полученных кодовых слов не входит в список допустимых. Следовательно, произошла ошибка. Очевидно, что в данном примере невозможно одновременно исправлять двойные ошибки и распознавать четверные, потому что для этого полученное кодовое слово нужно будет интерпретировать двумя разными способами.