Построение памяти повышенной надежности (стр. 1 )

Построение памяти повышенной надежности

Корректирующие коды

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

¨ код Хэмминга;

¨ групповые коды;

¨ циклические коды и др.

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

Разрядность контрольного кода определяется из соотношения

2r ³ n + 1 или 2r - r - 1 ³ k,

где k - число разрядов информационного слова;

r - число дополнительных контрольных разрядов;

n = r + k - передаваемое кодовое число.

Следовательно, если r=5, то можно контролировать от 11 до 26 информационных разрядов, а при r=6 от 27 до 57 разрядов.

Для образования контрольного кода Хэмминга (КХ) используется проверочная матрица Н размерности r x n, где r - число контрольных бит; n = k + r, где k - разрядность информационного слова; n - длина кодового слова, записываемого в память.

Рассмотрим одну из методик формирования модифицированного кода Хэмминга.

Данный код является избыточным и разделимым.

Матрица Н кода КО-ОД должна удовлетворять следующим условиям:

1) векторы-столбцы матрицы Н не должны быть нулевыми и должны отличаться друг от друга;

2) сумма двух векторов-столбцов матрицы Н не должна равняться нулю или любому третьему вектору-столбцу матрицы Н.

Рассмотрим процесс формирования контрольного кода и синдрома ошибок на примере 5-разрядного информационного слова. Для контрольного кода потребуется четыре дополнительных разряда (2r - r - 1 ³ n) и один дополнительный бит для определения двойной ошибки:

d4 d3 d2 d1 d0 - информационное слово;

с4 c3 с2 с1 c0 - номер бита кода Хэмминга;

СТ С3 С2 С1 С0 - контрольный код Хэмминга, где бит СТ необходим для обнаружения двойной ошибки.

В соответствии со сформулированными требованиями разработаем проверочную матрицу для данного примера.

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

Таблица 1.1. Исходная матрица Но Таблица 1.2. Этап 1

………… ………… ………… ………… ………….

На основании матрицы Но строится матрица Н в два этапа:

¨ на первом этапе путем перестановки столбцов матрицы Но так, чтобы в подматрице справа образовалась единичная подматрица размерностью r x r (табл. 1.2);

¨ на втором этапе из оставшихся столбцов вычеркиваются те, которые не удовлетворяют требованию 2 для формирования проверочной матрицы Н (табл. 1.3).

Для определения контрольного кода Хэмминга (КХ) для данной проверочной матрицы составим булевы выражения для формирования бит кода Хэмминга С0, С1, С2, С3 и СТ (система выражений 1).

d4 d3 d2 d1 d0	c4 c3 c2 c1 c0
A A A B B B C C C D D D F F F F F	1 1 1 1 1

В табл. 2 приведены примеры внесения одиночных и двойных ошибок в разряды считанного информационного слова или кода Хэмминга СT-С0 (отмечено звездочкой и выделением жирным шрифтом). Синдром ошибки ST-S0 может быть получен сложением по модулю 2 считанного из ОЗУ контрольного кода и вновь полученного контрольного кода от считанного информационного слова:

ST-S0 = (CT-C0)считанный Å (СT-С0)полученный.

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

Таблица 2. Примеры коррекции ошибок по синдрому

Исходное число d4 d3 d2 d1 d0	Код Хэмминга СТ С3 С2 С1 С0	Синдром ошибки ST S3 S2 S1 S0	Местоположение и тип ошибки (вектор ошибки)
1 0 1 0* 1 0* 1 1* 1 1 1 0* 1 0 1 0* 0*	0* 1 0 0 0* 1 1 1* 0 1 1		d1 00 d0 00 d3 01 d4 10 CT 00 C1 00 C3 00 Двойная ошибка

Таблица 3. Типы ошибок по синдрому

ST	Биты S3-S0	Тип ошибки
0	Все нули	Нет ошибки
1	Все нули	Ошибка бита CT
1	Один бит или более равен 1	Исправимая ошибка, если ошибочный бит определяется по табл. 1
0	Один бит равен 1	Ошибка бита С3-С0
0	Более одного бита равны 1	Двойная ошибка

Другой алгоритм для обнаружения и исправления одиночной ошибки в информационном слове и в битах контрольного кода Хэмминга без выделения двойной ошибки (без бита СТ) можно представить в следующем виде:

1) проверяется условие S3-S0 = S = 0. Если S=0, то считанное слово безошибочное;

2) если S ¹ 0, необходимо найти соответствие между синдромом ошибки и столбцом матрицы Н. Поиск выполняется с помощью дешифратора или ПЗУ;

3) если S совпадает с i-м столбцом матрицы Н, то это значит, что i-й бит кодового слова содержит ошибку и должен быть исправлен путем его инвертирования;

4) если S не совпадает ни с одним из столбцов матрицы Н, то ошибка неисправима (двойная или большей кратности).

Например, если считано слово:

Слово Код Хэмминга Синдром ошибки

1 0 1 0*1

т. е. вектор ошибки Е=00и синдром ошибки S=1001 совпадает с первым столбцом матрицы Н, то это свидетельствует об ошибке в этой позиции кодового слова (бит d1).

Аппаратура кода Хэмминга

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

На рис. 2 схема генерации синдрома ошибки реализована на элементах "Исключающее ИЛИ" с формированием бита ST. Элемент ИЛИ формирует сигнал равенства синдрома ошибки нулю, а совместная дешифрация сигналов ST и SK дает четыре комбинации осведомительных сигналов классификации типа ошибки по табл. 3 (вариант 1) или на элементе "И" формируется сигнал неисправимой ошибки (вариант 2).

Схема определения ошибочного бита (рис. 3) может быть реализована на обычном дешифраторе на четыре входа, на выходах которого формируется унитарный код с одной "1" для комбинаций, совпадающих с синдромом ошибки из поверочной матрицы Н (табл. 1.3), только при обнаружении одиночной ошибки. Этот код в дальнейшем выполняет функции вектора ошибки Е и используется в схеме коррекции ошибки.

Схема определения ошибочного бита может быть реализована и на ПЗУ (но задержка может получиться больше) (рис. 4). Такая реализация позволяет гибко изменять типы матриц Н путем перепрограммирования (прошивки) БИС ПЗУ, но может увеличить время коррекции считанного слова.

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

Коррекция одиночной ошибки в информационных битах или битах кода Хэмминга выполняется на логических элементах «Исключающее ИЛИ» по вектору ошибки Е, причем коррекция контрольного бита по нечетности выполняется только для вектора ошибок информационного слова.

Аппаратурная реализация

системы контроля по коду КО-ОД

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

Рассмотрим алгоритм работы системы контроля КО-ОД.

При записи:

¨ информация из процессора поступает в RgDI в виде 64-разрядного слова и 8 бит нечетности для каждого байта слова (рис. 5), а адрес для записи - в RgA;

¨ с выходов RgDI через MS1 слово поступает на генератор кода Хэмминга и бит нечетности GKH для формирования кода Хэмминга СТ-С0 и контрольных бит нечетности байт К7-К0. На схеме сравнения (Сх. ср.) определяется правильность приема информации из процессора в RgDI путем сравнения бит контрольного кода нечетности, принятых из процессора, и бит нечетности, сформированных схемой GKH;

¨ если сигнал ошибки передачи по нечетности не выработан, то сформированный код Хэмминга СТ-С0 с выходов GKH вместе с информационными разрядами слова записывается в ОП;

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

¨ если попытка восстановления информации классифицируется как постоянный отказ, то устанавливается триггер ошибки и вырабатывается сигнал прерывания от схем контроля и блокируется запись в ОП, иначе выполняется запись слова и бит кода Хэмминга СТ-С0 в ОП.

Чтение из ОП

1. Из ОП считываются 64 бита слова и 8 бит кода Хэмминга СТ-С0 сч. Считанное 64-разрядное слово через MS1 поступает на схемы генератора формирования кода Хэмминга и бит нечетности байт слова.

2. Полученные в GKH биты СТ-С0н сравниваются со считанными из ОП битами СТ-С0 сч. и при их несовпадении схема определения синдрома ошибки (Сх. ОСО) формирует код синдрома ошибки ST-S0, определяющего номер позиции ошибочного бита в слове (матрица Н), а также тип ошибки на схеме классификации ошибок (одиночная или двойная).

3. При одиночной ошибке по коду синдрома ошибки ST-S0 схема определения вектора ошибки (Сх. ОВО) формирует код вектора ошибки Е, а в схеме коррекции ошибок выполняется ее исправление путем инверсии ошибочного бита, а также выполняется изменение бита нечетности того байта, в котором выполнена коррекция. Скорректированная информация поступает в RgRD, а из него в процессор.

4. Неисправимая (двойная) ошибка ОП вызывает установку бита ошибки в Тош и прерывание от схем контроля. Все случаи ошибок, обнаруженные при обращении к памяти, фиксируются в пункте 5.

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

Самоконтролируемая система контроля по коду Хэмминга

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

Тогда в предыдущий алгоритм необходимо ввести некоторые изменения и дополнения.

Запись в ОП выполняется без изменений алгоритма.

При чтении в пункте 1 считанное из ОП слово поступает в RgDО, и далее параллельно выполняется алгоритм проверки работоспособности схем контроля, т. е. данные из RgDО через MS1 поступают на входы GKH1 для получения нового кода Хэмминга и бит нечетности считанного слова и параллельно для формирования нового кода Хэмминга и бит нечетности на входы GKH2. Полученные контрольные биты нечетности и кода Хэмминга СТ-С0н, сравниваются на схемах сравнения (Сх. ср.2 и Сх. ср.3), и принимается решение о работоспособности аппаратуры контроля, т. е. если хотя бы одна схема сравнения вырабатывает сигнал неравенства кодов, то формируется сигнал прерывания от схем контроля и фиксируется тип ошибки в регистре ошибок.

Методы исправления двойных ошибок

Последовательная коррекция