РАЗДЕЛ 1. МАШИНЫ ПОСТОЯННОГО ТОКА
В оперативной памяти применяют код Хэмминга, позволяющий исправлять ошибки.
Код Хэмминга строится таким образом, что к имеющимся информационным разрядам слова добавляется определенное число контрольных разрядов, которые формируются перед записью слова в ОП и вместе с информационными разрядами слова записываются в память.
При считывании слова контрольная аппаратура образует из прочитанных информационных и контрольных разрядов корректирующее число, которое равно «0» при отсутствии ошибки либо указывает место ошибки, например двоичный порядковый номер ошибочного разряда в слове. Ошибочный разряд автоматически корректируется изменением его состояния на противоположное.
В общем случае при использовании кода Хемминга n-разрядное число имеет m информационных k = n - m контрольных разрядов.
Поскольку ошибка может произойти в одном из n разрядов или вообще отсутствовать, то число контрольных разрядов должно позволять фиксировать одно из (n+1) событий. Поэтому:
k ³ log 2 (n+1).
Откуда
m £ n – log2 (n+1).
Значения m и k для некоторых n-разрядных кодов, вычисленные в соответствии с полученными выражениями, приведены в таблице 1.
Таблица 1
| n | ||||||||||||||||
| m | ||||||||||||||||
| k |
Разряды слова, представленного кодом Хемминга, нумеруются от единицы до (k+m). Контрольные разряды помещаются в разрядные позиции с номерами 1, 2, 4, 8, ..., 2k-1. Остальные m разрядов можно поместить в любом порядке между контрольными позициями. Каждый из контрольных разрядов –результат проверки на четность определенной группы разрядов п- разрядного кода. Если в данной группе разрядов число единиц четное, то в соответствующий контрольный разряд записывается 0, если нечетное – 1.
В таблице 2 приведены группы проверяемых разрядов для k = 5.
Таблица 2
| Номер проверки | Позиция контрольн. разр. | Проверяемые разряды числа |
| 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, … 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, … 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, … 8, 9, 10, 11, 12, 13, 20, 21, 22, … 16, 17, 18, 19, 20, 21, 22, … |
Младший разряд контрольного слова (1-я позиция) охватывает те разряды n-разрядного числа, номера которых, представленные в двоичном коде, имеют 1 в первом разряде. Второй разряд контрольного слова охватывает те разряды числа, номера которых имеют 1 во втором разряде и т. д.
Процедуру исправления одиночной ошибки с помощью кода Хемминга рассмотрим на примере передачи чисел от 0 до 9. Как следует из первой таблицы, для этого случая n = 7, m = 4, k = 3. Контрольные разряды будут размещаться в позициях 1, 2, 4 (помечены звездочкой в табл. ниже).
| - | * ** | |
| Десятичное число | Двоичный код | Код Хемминга |
Предположим, что передается число 7, которому соответствует код Хемминга 0110100. Предположим также, что произошла ошибка в разряде 6, т. е. принят код 0010100. Декодирующее устройство производит сверку соответствующих групп разрядов. В результате будет сформирован код контрольного слова 110 указывает номер разряда, в котором произошла ошибка. На 6-м выходе дешифратора появится сигнал единички, который просуммируется по модулю 2 с 6-м разрядом искаженного числа. В результате после схемы сложения по модулю 2 получим код числа 7 без искажений.
Необходимо отметить, что код Хемминга имеет большую избыточность, чем коды с проверкой на четность, однако позволяет в течение длительного времени (до следующего отказа) работать на неисправном оборудовании, что существенно повышает надежность ЭВМ.
РАЗДЕЛ 1. МАШИНЫ ПОСТОЯННОГО ТОКА
Дата добавления: 2014-12-09; просмотров: 790;