Двойная проверка на четность

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

Код Хэмминга

К систематическим кодам также относится и код Хэмминга, который позволяет не только обнаруживать, но и исправлять ошибки. В этом коде каждая кодовая комбинация состоит из m информационных а k контрольных элементов. Так, например, в семиэлементном коде Хэмминга n=7, m=4, k=3 (для всех остальных элементов существует специальная таблица). Контрольные символы 0 или 1 записываются в первый, второй и четвертый элементы кодовой комбинации, причем в первый элемент - в соответствии с контролем на четность для третьего, пятого и седьмого элементов, во второй - для третьего, шестого и седьмого элементов, и в четвертый - для пятого - седьмого элементов. В соответствии с этим правилом комбинация 1001 будет представляться в коде Хэмминга как 0011001, и в этом виде она будет представляться в канал связи.

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

Для устранения этой ошибки необходимо изменить находящийся в этом элементе символ на обратный.

Код Хэмминга имеет существенный недостаток: при обнаружении любого числа ошибок он исправляет лишь одиночные ошибки. Избыточность семиэлементного кода Хэмминга равна 0,43. При увеличении значности кодовых комбинаций увеличивается число проверок, но уменьшается избыточность кода. К тому же код Хэмминга не позволяет обнаружить групповые ошибки, сконцентрированные в пакетах. Длина пакета ошибок представляет собой увеличенную на единицу разность между именами старшего и младшего ошибочных элементов.

Код с постоянным числом нулей или единиц

Распространенным кодом, но не относящимся к группе неразделенных, является код с постоянным числом нулей или единиц или код M из N. Так, семиэлементный код имеет соотношение единиц и нулей, равное 3: 4. Кодирование и декодирование выполняются заменой одной кодовой группой другой. Например, комбинация 01110 посылается в канал связи в виде 0101010. На приемном конце она вновь декодируется в 01110. Фирма IMB использует восьмиэлементный код, содержащий четыре единицы и четыре нуля.

Подсчет контрольных сумм

Еще одной формой проверки ошибок служит подсчет контрольных сумм. Это несложный способ, который обычно применяется вместе с контролем ошибок с помощью эхоплекса или проверки на четность/нечетность. Сущность его состоит в том, что передающая ПЭВМ суммирует численные значения всех передаваемых символов.

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

Метод CRC

Последним словом в области контроля ошибок в сфере ПЭВМ является циклическая проверка с избыточным кодом (CRC - cyclic redunduncy check). Она широко используется в протоколах HDLC, SDLC, но в индустрии ПЭВМ появилась сравнительно недавно.

Поле контроля ошибок включается в кадр передающим узлом. Его значение получается как некоторая функция от содержимого всех других полей. В принимающем узле производятся идентичные вычисления еще одного поля контроля ошибок. Эти поля затем сравниваются; если они совпадают, велика вероятность того, что пакет был передан без ошибок. Этот процесс, как уже было упомянуто, называется циклическим контролем по избыточности (CRC), а поле называется контрольной последовательностью кадра (КПК). В случае несовпадения, возможно, имела место ошибка передачи, и принимающая станция посылает сигнал, означающий, что необходимо повторить передачу кадра.

При вычислении КПК используется производящий полином 16+12+5+1.

Вычисление и использование кода CRC производится в соответствии со следующими правилами:

·   К содержимому кадра добавляется набор нулей, количество которых равно длине поля КПК.

·   Образованное таким образом число делится на производящий полином, который содержит на один разряд больше, чем КПК, и который в качестве старшего и младшего разрядов имеет единицы.

·   Остаток от деления помещается в поле КПК и передается в приемник.

·   Приемник выполняет деление содержимого кадра и поля КПК на полином.

·   Если результат равен некоторому определенному числу, считается, что передача выполнена без ошибок.

Метод CRC позволяет обнаруживать всевозможные кортежи ошибок длиной не более шестнадцати разрядов, вызываемых одиночной ошибкой, а также 99,9984% всевозможных более длинных кортежей ошибок.