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

Помимо этого, следует помнить, что коды ошибок относятся к прикладной математике. Если только вы не крупный специалист по полям Галуа или свойствам слабо заполненных матриц, используйте надежные коды, полученные из проверенных источников, и не пытайтесь конструировать собственные. В действительности, так делается во многих стандартных протоколах; одни и те же коды будут встречаться вам снова и снова. Далее мы подробно изучим простой код, а затем коснемся нескольких более сложных. Так вы сможете лучше понять преимущества и недостатки различных кодов и познакомиться с кодами, применяемыми на практике.

3.2.1. Коды с исправлением ошибок

Мы рассмотрим четырех разных кода с исправлением ошибок:

1.    Коды Хэмминга.

2.    Двоичные сверточные коды.

3.    Коды Рида—Соломона.

4.    Коды с малой плотностью проверок на четность.

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

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

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

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