Корректирующее кодирование.

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

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

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

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

В качестве простейшего примера кода с обнаружением ошибок рассмотрим код, в котором к данным добавляется один бит четности. Бит четности выбирается таким образом, чтобы количество единиц во всем кодовом слове было четным (или нечетным). Например, при посылке числа 10110101 с добавлением бита четности в конце оно становится равным 101101011, тогда как 10110001 преобразуется в 101100010. Код с единственным битом четности имеет кодовое расстояние, равное 2, так как любая однократная ошибка в любом разряде образует кодовое слово с неверной четностью. Такой код может использоваться для обнаружения однократных ошибок.

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

0000000000, 0000011111, 1111100000 и 1111111111.

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

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

Этот теоретический предел может быть достигнут на практике с помощью метода Хэмминга

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: