Корректирующее кодирование
Разработчики сетей создали две основные стратегии для борьбы с ошибками. Каждый метод основывается на добавлении к передаваемым данным некоторой избыточной информации. В одном случае этой информации должно быть достаточно, чтобы выявить, какие данные должны были прийти. В другом случае избыточной информации должно быть достаточно только для того, чтобы получатель понял, что произошла ошибка (без указания ее типа) и запросил повторную передачу. Первая стратегия использует коды, называющиеся корректирующими, или кодами с исправлением ошибок. Вторая — код с обнаружением ошибок. Использование кода с обнаружением ошибок часто называют прямым исправлением ошибок.
Каждая стратегия занимает свою, так сказать, экологическую нишу. В высоконадежных каналах, таких как оптоволокно, дешевле использовать код с обнаружением ошибок и просто заново передавать случайные поврежденные блоки. Однако, скажем, беспроводные соединения, в которых может возникать множество ошибок, чаще используют коды с избыточностью, достаточной для того, чтобы приемник мог определить, какие данные должны были прийти. Это надежнее, чем полагаться на повторную передачу, которая тоже, возможно, не сможет пройти без ошибок.
Чтобы понять, как могут обнаруживаться и исправляться ошибки, необходимо рассмотреть подробнее, что же представляет собой ошибка. Обычно кадр состоит из т битов данных (то есть информационных битов) и г избыточных или контрольных битов. Пусть полная длина кадра равна n (то есть n = m + r). Набор из n бит, содержащий информационные и контрольные биты, часто называют n-битовым кодовым словом или кодовой комбинацией. Канальный уровень управления передачей компьютерные сети
Если рассмотреть два кодовых слова, например 10001001 и 10110001, можно определить число различающихся в них соответствующих разрядов. В данном /Примере различаются 3 бита. Для нахождения этого числа нужно сложить два кодовых слова по модулю 2 (операция «исключающее или») и сосчитать количество единиц в результате, например:
Количество битов, которыми различаются два кодовых слова, называется кодовым расстоянием, или расстоянием между кодовыми комбинациями в смысле Хэмминга (Hamming, 1950). Смысл этого числа состоит в том, что если два кодовых слова находятся на кодовом расстоянии d, то для преобразования одного кодового слова в другое понадобится d ошибок в одиночных битах.
В большинстве приложений передачи данных все 2m возможных сообщений являются допустимыми, однако благодаря использованию контрольных битов не все 2n возможных кодовых слов используются. Зная алгоритм формирования контрольных разрядов, можно построить полный список всех допустимых кодовых слов и в этом списке найти такую пару кодовых слов, кодовое расстояние между которыми будет минимальным. Это расстояние называется минимальным кодовым расстоянием кода, или расстоянием всего кода в смысле Хэмминга.
Способности кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Для обнаружения d ошибок в одном кодовом слове необходим код с минимальным кодовым расстоянием, равным d + 1, поскольку d однобитовых ошибок не смогут изменить одну допустимую комбинацию так, чтобы получилась другая допустимая комбинация. Когда приемник встречает запрещенную кодовую комбинацию, он понимает, что при передаче произошла ошибка. Аналогично, для исправления d ошибок в одном кодовом слове требуется код с минимальным кодовым расстоянием, равным 2d+1, так как в данном случае даже при d однобитовых ошибках результат окажется ближе к исходному кодовому слову, чем к любому другому, и, следовательно, его можно будет однозначно восстановить.
В качестве простейшего примера кода с обнаружением ошибок рассмотрим код, в котором к данным добавляется один бит четности. Бит четности выбирается таким образом, чтобы количество единиц во всем кодовом слове было четным (или нечетным). Например, при посылке числа 10110101 с добавлением бита четности в конце оно становится равным 101101011, тогда как 10110001 преобразуется в 101100010. Код с единственным битом четности имеет кодовое расстояние, равное 2, так как любая однократная ошибка в любом разряде образует кодовое слово с неверной четностью. Такой код может использоваться для обнаружения однократных ошибок.