31 Аппаратные методы контроля арифметических и логических операций.

Аппаратный:

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

Должен обеспечивать:

1)   контроль данных

2)   контроль команд – имеется дескриптор выполняемости, если он взведен – это команда, иначе – данные.

3)   контроль адресов – не выходит ли адрес за пределы сегмента (при сегментно-страничной организации)

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

Классическая схема свертки:

F = G. 2) сопоставление – на равенство.

Можно  вместо КР использовать ОР – то есть, получаем дублирование (по крайней мере, это один из возможных режимов). Если идет речь об обнаружении и исправлении ошибок, то дублирование не спасет.

В основе корректирующих кодов лежит следующая идея. Для кон­троля двоичного информационного кода длиной М бит добавим к ней К дополни­тельных контрольных разрядов. В этом случае из возможных N = 2^М"^К комбинаций интерес представляют только L = 2^м последовательностей, которые называют: разрешенными. Оставшиеся N - L последовательностей назовем запрещенными. Если при обработке (записи в память, считывании или передаче) разрешенной кодовой последовательности произойдут ошибки и возникнет одна из запрещенных после­довательностей, то тем самым эти ошибки обнаруживаются. Если же ошибки пре­вратят одну разрешенную последовательность в другую, то такие ошибки не могут быть обнаружены. Благодаря свойствам контрольных разрядов, характерным для конкретных методов контроля, в некоторых случаях возможно определить не только наличие, но и местоположение ошибки, а также произвести её коррекцию.

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

Более эффективным представляется код, предложенный Ричардом Хэммингом и носящий его имя (код Хэмминга).

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

Сначала определим требуемую длину корректирующего кода. В соответствии с рис., на вход схемы сравнения поступают два К-разрядных значения. Срав­нение производится путем поразрядной операции «исключающее ИЛИ» (сложе­ние по модулю 2) над входными кодами. Результатом является так называемое слово синдрома. В зависимости от того, было ли совпадение входных кодов или нет, соответствующий бит синдрома будет равен 0 или 1.

Слово синдрома состоит из К разрядов, то есть его возможные значения лежат в диапазоне от 0 до 2^К - 1. Значение 0 соответствует случаю, когда ошибки не об­наружено, остальные 2^К — 1 случая свидетельствуют о наличии ошибки и указывают на ее местоположение.

Поскольку ошибка может возникнуть в любом из М битов данных или К контрольных битов, мы должны иметь 2^к - 1 > М + К. Это выраже­ние позволяет определить число битов, необходимое для исправления одиночной ошибки в М-разрядных данных. В нашем примере, для 8-разрядных слов требуется четыре корректирующих разряда.

Для удобства будем формировать четырехразрядный синдром со следующими характеристиками:

- Если синдром содержит все нули, значит, не обнаружено ни одной ошибки.

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

- Если в синдроме в единичное состояние установлены несколько битов, то чис­ленное значение синдрома соответствует позиции ошибки в данных, для исправ­ления которой необходимо инвертировать бит в этой позиции (нумерация с единицы!).

Для поддержания этих свойств под контрольные разряды отводятся те биты, чьи позиционные номера пред­ставляют собой степень числа 2 (табл. 2). Отдельный контрольный разряд от­вечает за определенные биты данных. Так, разрядная позиция n контролируется теми битами Р_i, которые делают справедливым соотношение = n. Например, раз­ряд данных с позиционным номером 7₁₀ (0111₂) контролируется битами 4, 2 и 1 (7 = 4 + 2 + 1), а разряд с номером 10₁₀ (1010₂) - битами 8 и 2 (10 = 8 + 2).