Коды для обнаружения и исправления ошибок

Общие сведения о кодах. Виды кодов.

Коды обнаружения и/или исправления ошибок применяются в СВТ для контроля правильности передач информации между устройствами и внутри устройств машины, а также для контроля всего процесса обработки информации на машине.

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

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

Избыточные коды. Вместо таких систематических повторных передач, на которые тратится дополнительное время и которые не всегда позволяют обнаружить устойчивую ошибку, в машинах применяются не простые, а избыточные коды. Это коды, в которых для представления информации используется лишь часть всех возможных знаковых комбинаций. Другая часть комбинаций в избыточных кодах является запрещенной. Появление запрещенных комбинаций расценивается как ошибка, что и фиксируется схемами контроля машины. Например, в простом четырехзначном коде все 16 комбинаций нулей и единиц используются для изображения чисел от 0 до 15. Любая ошибка даст новую, но опять-таки разрешенную комбинацию, т. е. одно из чисел от 0 до 15. В результате ошибка останется необнаруженной.

Если наложить запрет на часть комбинаций, например, восемь, а остальные восемь использовать для изображения чисел от 0 до 7, то любая ошибка в знаке приведет к появлению запрещенной комбинации, которая и будет обнаружена машиной (табл. 1).

Таблица 1

Десятичное число

Двоичный код

Десятичное число

Двоичный код

0000

0011 0101

0110

1001

1010 1100

1111

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

Систематические коды. В машинах применяются коды, которые называются систематическими. К систематическим относятся коды, состоящие из п двоичных символов, т из которых используются для представления информации (информационные символы), a k=п-т -для обнаружения и исправления ошибок (проверочные символы). Избыточность RИ в таком коде равна отношению полного числа двоичных символов к минимальному числу символов, необходимых для передачи той же информации, т. е.

Величина RИ определяет эффективность кода или степень уменьшения информационной емкости канала.

Для характеристики кодов часто пользуются понятием относительной избыточности R, которая выражается как

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

Использование кодов с исправлением ошибок очень усложняет аппаратуру и снижает пропускную способность канала, поэтому применение таких кодов может быть оправдано лишь в особо ответственных случаях, например:

- при работе системы без надзора в течение длительного времени;

- в сложных системах, в которых ошибка может вывести из строя всю установку (например, машины, управляющие работой крупного технологического объекта);

- для передачи сигналов при наличии сильных помех, которые не могут быть подавлены.

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

В целом, учитывая эти соображения, можно сформулировать основные требования, предъявляемые к коду:

1. Код должен обнаруживать наиболее часто встречающиеся виды ошибок.

2. Заданная степень обнаружения ошибки должна достигаться присоединением к сообщению минимального количества избыточной информации (минимального числа контрольных разрядов).

3. Процедуры кодирования и декодирования должны быть по возможности простыми и быстрыми.

Корректирующая способность кода. Способность кода обнаруживать или исправлять ошибки характеризуется минимальным значением кодового расстояния d. Кодовым расстоянием между двумя словами (комбинациями) называется число разрядов, в которых соответствующие символы не совпадают. Если длина слова п, то кодовое расстояние может принимать значение от 1 до п. Если код имеет хотя бы две комбинации, отличающиеся друг от друга в одном разряде, то минимальное расстояние данного кода равно единице. Другими словами, минимальное кодовое расстояние — это минимальное количество двоичных разрядов, которое достаточно изменить для того, чтобы одну информационную комбинацию превратить в другую.

Простой код имеет минимальное расстояние d=1. Для избыточных кодов dmin > 1. Если, например, d=2, то любые две комбинации, данного кода отличаются не менее чем в двух разрядах. Любая одиночная ошибка не сможет превратить данную комбинацию в какую-либо разрешенную, а приведет к появлению запрещенной. Следовательно, такая ошибка будет обнаружена. Таким образом, для обнаружения одиночной ошибки (искажения в одном из разрядов числа) достаточно иметь код с d=2.

Чтобы можно было не только обнаружить, но и исправить одиночную ошибку, необходимо иметь код с d3. В этом случае любая одиночная ошибка создает запрещенную комбинацию, отличающуюся от правильной в одном разряде, а от любой другой разрешенной - в двух разрядах. Этого достаточно, чтобы определить искаженный разряд и исправить его. Исправление заключается в поочередном изменении значений каждого разряда слова (0 на 1 и 1 на 0) с проверкой на запрещенность. Если после замены символа комбинация остается запрещенной, символ в данном разряде вновь восстанавливается. Очевидно, что комбинация окажется разрешенной в единственном случае — когда будет инвертирован ошибочный разряд, поскольку одиночная ошибка изменила символ только в одной позиции.

Рассуждая аналогичным образом, можно показать, что для обнаружения двойных ошибок необходим код с d=3, а для их исправления - код с d=5.

Следовательно, чтобы избыточный код позволял обнаруживать групповые ошибки кратностью t, он должен иметь минимальное кодовое расстояние dt+1. В самом деле, одновременная ошибка в t разрядах слова создает новую комбинацию, отстоящую от истинной на расстояние t. Чтобы новая комбинация не совпала с какой-либо другой разрешенной комбинацией, расстояние между этими комбинациями (новой и любой соседней разрешенной) должно быть хотя бы на единицу больше, чем t.

Для исправления t-кратной ошибки необходимо, чтобы новая (искаженная) комбинация не только не совпадала с какой-либо разрешенной, но и оставалась ближе по кодовому расстоянию к истинной, чем к любой соседней разрешенной комбинации. От истинной комбинации новая отстоит на расстоянии t. От любой другой разрешенной комбинации она должна отстоять не менее чем на t+1. Следовательно, кодовое расстояние между истинной комбинацией и соседней разрешенной должно быть не меньше суммы этих значений: d2t+1.

Контроль передачи информации

Код с проверкой четности. Код с проверкой четности является простейшим избыточным кодом. Он образуется добавлением к группе информационных разрядов одного избыточного (контрольного) разряда.

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

Минимальное расстояние кода d=2, поэтому код с проверкой четности обнаруживает все одиночные ошибки и все случаи нечетного числа ошибок (3, 5, 7 и т. д.). При одновременном возникновении двух или другого четного числа ошибок код с проверкой четности их не обнаруживает (четность при этом не нарушается).

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

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

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

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

При параллельной передаче информации обычно применяются логические схемы определения четности суммы единиц.

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

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

После передачи числа в приемном устройстве производится k проверок на четность всех k контрольных групп. После каждой проверки в специальный регистр ошибок записывается 0, если результат проверки свидетельствует об отсутствии ошибки на проверяемых позициях данной группы, и 1, если результат свидетельствует о наличии ошибки. Таким образом, каждая проверка заканчивается записью в соответствующий разряд регистра 0 или 1. Полученная последовательность нулей и единиц образует двоичное число, называемое проверочным, которое должно указывать номер позиции (разряда слова) с искаженным символом

Учитывая необходимость записи в двоичном коде номера любого из т+k разрядов принятой комбинации, а также то, что отсутствию ошибки в этой комбинации будет соответствовать число, составленное только из нулей, проверочное число должно описывать т+k+1 событий. Следовательно, для k (количества необходимых для этих целей контрольных разрядов) будет справедливо неравенство:

Поскольку п = т + k, можно записать:

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

Таблица 2

m n k

1 3

5 9

6 10

7 11 4

8 12 4

9 13

14 4

11 15 4

12 17 5

Способ разбивки информационных разрядов на контрольные группы и определение номеров позиций контрольных разрядов следует непосредственно из структуры натурального ряда чисел, представленного в двоичной форме.

Рассмотрим это на примере 13-разрядного двоичного числа (п = 13).

Из табл. 2 видно, что для формирования корректирующего кода 13-разрядное число должно содержать девять информационных и четыре контрольных разрядов. Следовательно, по числу контрольных разрядов вся комбинация должна состоять из четырех контрольных групп.

Разбивка числа на контрольные группы производится следующим образом (табл. 3).

Первая группа (первая проверка) охватывает все позиции кода, номер которых в двоичной системе счисления имеет единицу в первом разряде (1, 3, 5, 7, 9, 11, 13). Вторая группа (вторая проверка) включает позиции, номер которых имеет единицу во втором разряде (2, 3, 6, 7, 10) и т. д.

Разряды 1, 2, 4, 8, каждый из которых принадлежит только одной контрольной группе, используются в качестве контрольных, а остальные разряды, одновременно принадлежащие разным группам, — в качестве информационных.

Таблица 3

Номер разряда числа n

В десятичной системе счисления

В двоичной системе счисления

В десятичной системе счисления

В двоичной системе счисления

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

Таким образом, при контроле правильности приема 13-разрядного числа производятся четыре проверки на четность. Первая проверка охватывает позиции первой группы (с записью результата проверки в первый разряд), вторая — позиции второй группы (результат записывается во второй разряд) и т. д.

В качестве иллюстрации рассмотрим принцип определения ошибки при передаче числа в коде Хэмминга на простом примере. Пусть передается число 1011, преобразованное в 7-разрядный корректирующий код (см. табл. 3).

В табл. 4 в первой строке показан код переданной комбинации. Контрольные разряды (выделены шрифтом) автоматически записываются при формировании передаваемого кода в соответствии с рассмотренным правилом проверки на четность: знак первого разряда (1) записан как результат суммирования (по модулю 2) знаков 3, 5 и 7-й позиций кода; знак второго разряда (0) — как результат суммирования знаков второй группы (3, 6 и 7-й позиции); знак четвертого разряда (0) — как результат суммирования знаков третьей группы (5, 6 и 7-й позиции).

Таблица 4

Число

Номер разряда числа

Передаваемое Принятое

0 0

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

Произведем три проверки на четность в соответствии с установленным правилом. (При проверках учитывается и контрольный разряд.)

Первая проверка (1, 3, 5, 7) дает 1; вторая проверка (2, 3, 6, 7) дает 1; третья проверка (4, 5, 6, 7) дает 1. Получаем проверочное число 111 (семь), которое указывает на ошибку в седьмом разряде принятой комбинации. Следовательно, для исправления ошибки символ в седьмом разряде необходимо инвертировать. Процесс исправления ошибки производится на машине автоматически.

Код Хэмминга легко может быть расширен до d == 4 (исправление одиночной и обнаружение двойной ошибки), С этой целью к k контрольным разрядам добавляется еще один контрольный разряд, который используется для контроля по четности всего кодового слова, включая и контрольные разряды, что позволяет дополнительно осуществлять общую проверку всего слова на четность.

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

Циклические коды обязаны своему названию благодаря особенности, которая заключается в том, что если n-значная информационная комбинация а0 а1 a2…an принадлежит к данному коду, то и комбинация аn a0.a1…a.n-1, в которой произведена циклическая перестановка символов, также принадлежит к этому коду.

Такая особенность циклического кода позволяет сравнительно просто организовать кодирование и декодирование информации, что достигается использованием сдвигающего регистра с обратной связью, обладающего циклическими свойствами.

Принцип построения циклического кода основан на следующем. Любая двоичная кодовая комбинация может быть представлена а виде полинома (п — 1)-й степени некоторой переменной х, коэффициентами которого являются двоичные символы соответствующих разрядов числа. Например, число 1011001 (младшие разряды справа) представляется полиномом шестой степени:

1*x6+0*x5+1*x4+1*x3+0*x2+0*x1+1*x0=

x6+x4+x3+1.

Над такими полиномами можно производить все математические действия в соответствии с известными законами алгебры за исключением сложения, которое, в отличие от обычной алгебры, осуществляется по модулю 2 (поразрядное сложение без учета переносов).

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

Кодирование заключается в составлении на основе информационной двоичной комбинации G(х), подлежащей кодированию, такого многочлена F(х), который должен делиться без остатка на заранее выбранный порождающий полином Р(х) степени k, с помощью которого и происходит образование циклического кода.

Следовательно, если (например, при приеме числа) деление многочлена F(х) на многочлен Р(х) даст остаток R(х), это будет означать появление ошибки в переданной комбинации.

Наиболее простым способом получения F(х) было бы перемножение многочленов G(х) и Р(х). Однако этот способ неприемлем, так как в этом случае полученный код окажется несистематическим — в нем не будут выделены контрольные разряды. Поэтому кодовая комбинация F(х) строится следующим образом. Информационный многочлен, G(х), подлежащий кодированию, умножается на xk. Полученный многочлен G(х)хk делится на порождающий полином Р(х) для определения остатка R(х), после чего остаток складывается (по модулю 2) с G(х)xk. Таким образом, получаем:

Принимая во внимание, что при делении многочлена G(х)xk на порождающий полином Р(х) помимо остатка R(х) получается частное, можно записать:

где Q (х) — частное от деления (в работе не используется). Поскольку суммирование производится по модулю 2 (сложение и вычитание производятся одинаково), то, перенеся R (х) в левую часть равенства, получим:

откуда следует, что кодовый многочлен F(х) кратен значению Р(х) и при отсутствии ошибки должен делиться на Р(х) без остатка. Кроме того, G(х)хk имеет нули в k разрядах (умножение производилось путем сдвига слова), следовательно, старшие разряды т кодовой комбинации F(х) представляют собой разряды двоичной комбинации G(х), т. е. являются информационными. Младшие разряды k кодовой комбинации F(х) отводятся под остаток R(х) и представляют собой контрольные разряды.

В процессе передачи комбинации F(х) могут возникнуть помехи, которые исказят передаваемую информацию. Неправильно принятую комбинацию Н(х) можно в этом случае представить следующим образом:

где Е(х) - многочлен ошибок, имеющий ненулевой член в каждом искаженном разряде при правильно принятой информации Е(х) = 0.

Основным признаком появления ошибки, как уже говорилось, служит появление остатка при делении Н(х) на Р(х) Однако возможен случай, когда остаток не появится даже при наличии ошибки — это если Е(х) без остатка разделится на Р(х) Следовательно, для обнаружения ошибки необходимо выполнить еще одно условие Е(х) не должен делиться на Р(х) без остатка. Этого добиваются за счет определенного выбора числа членов и степени старшего разряда порождающего полинома Р(х)

В качестве примера в табл. 5 приведен вид многочлена Р(х) и количество контрольных разрядов для данной кодовой комбинации, при которых циклический код позволяет обнаруживать все одиночные и двойные ошибки.

Проследим теперь процесс преобразования числа в циклический код и декодирования на конкретном примере.

Таблица 5

Порождающий полином Р(х)

Число разрядов

х3+х +1

х4+х +1

x5 +x2+l

4 5

Пусть дано число 11010 Искомый код образуется с помощью порождающего полинома Р(х) степени k. Для нашего случая Р(х) = х3+х+1 (п < 7), что соответствует коду 1011.

Следующим этапом является умножение информационной комбинации, подлежащей кодированию, G(х) на xk (в нашем случае k = 3), что соответствует сдвигу кодируемого числа на k разрядов влево (в сторону старших разрядов). Полученный после сдвига многочлен G(х)хk делится на Р(х) для определения остатка, разряды которого представляют собой контрольные знаки. Так как необходимо найти только остаток (частное не используется), на практике вместо обычного деления производится вычитание по модулю 2 (или сложение) делителя из делимого и получающихся разностей до тех пор, пока разность не будет иметь более низкую степень, чем делитель. Эта последняя разность и есть искомый остаток, который необходимо дописать в информационную комбинацию. Таким образом, после сдвига числа приступаем к последовательному вычитанию из него кода порождающего полинома 1011

Полученный остаток 010 дописывается к кодируемому числу 11010, что и дает искомый код: 11010010.

Проверка правильности кодирования (декодирование при приеме числа) состоит в выполнении деления закодированного числа на порождающий полином (1011). Как и при кодировании, здесь производится последовательное вычитание по модулю 2 делителя из делимого. При отсутствии ошибки деление будет выполнено без остатка:

При применении циклического кода в качестве корректирующего для исправления одиночных ошибок определение номера искаженного разряда производится по виду полученного остатка (между остатком и многочленом ошибок существует вполне определенная связь: ошибке в любой из п позиций соответствует один из 2k - 1 ненулевых остатков). Анализ остатка и исправление искаженного разряда производятся автоматически.

Следует отметить, что циклический код с d=3 считается циклическим вариантом кода Хэмминга, в котором в отличие от рассмотренной структуры последнего все контрольные разряды размещаются в конце информационной комбинации.

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

Существует много видов равновесных кодов, но наибольшее практическое применение получил код «2 из 5», т. е. две единицы из пяти знаков (табл. 6).

Таблица 6

Кодируемое число

Код «2 из 5»

Кодируемое число

Код «2 из 5»

01100

11000

10100

10010

01010

00110

10001

01001

00101

00011

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

Избыточность равновесного кода «2 из 5» выше, чем у обычного двоично-десятичного кода. Добавление пятого разряда увеличивает число возможных комбинаций (25 = 32), однако для изображения цифр используется только 10, которые выбираются так, чтобы минимальное кодовое расстояние было равно 2.

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

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

Контроль арифметических и логических операций

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

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

При выполнении операции над числами та же операция выполняется над их контрольными кодами, после чего контрольный код результата основной операции сравнивается с результатом аналогичной операции над контрольными кодами (остатками) исходных чисел.

Если сравнение указанных результатов дает совпадение, операция считается выполненной правильно, при не совпадении — фиксируется как ошибка.

Значение q выбирается с таким условием, чтобы:

1)любая одиночная ошибка приводила к нарушению условия сравнимости результатов по модулю q; 2)операций деления для определения остатка была заменена более простыми методами и осуществлялась по сравнительно несложным признакам делимости; 3) аппаратура, реализующая контроль по модулю, была возможна проще, а это возможно при меньших значениях q, когда контрольные коды имеют малое число разрядов.

Из первого условия следует, что в качестве основания нельзя выбирать числа 2, 4 и т. п., т. е. типа 2n (n - целое число), поскольку при этом одиночные ошибки в старших разрядах не нарушают сравнимости по модулю q и, следовательно, не могут быть обнаружены. Этому условию лучше всего, удовлетворяют основания типа 2n + 1. Если принять во внимание, что вероятность появления двойных ошибок крайне мала, то эффективность контроля при разных основаниях типа 2n ± 1 будет отличаться незначительно.

Контроль по модулю 3 позволяет просто и экономично реализовать проверку.

Контроль логических операций. К таким операциям относятся такие, как логическое сложение (ИЛИ), логическое умножение (И) и исключающее ИЛИ (сложение по модулю 2 или операция неравнозначности), не имеет такой структуры, как контроль арифметических операций. Объясняется это тем, что, в отличие от арифметических, логические операции выполняются поразрядно и результаты операции в каждом конкретном разряде определяется только состоянием соответствующих разрядов операндов, не связанных с другими разрядами числа. Следовательно, для большинства логических операций невозможно найти общие контрольные разряды, которые оказались бы совместимыми с данной операцией. Реализация же поразрядного схемного контроля в принципе возможна, но неэкономична так как это потребует резкого увеличения контрольной аппаратуры.

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

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

Коды для обнаружения и исправления ошибок