Устройство для обнаружения и ис-пРАВлЕНия ОшибОК B блОКАХ ВычиСли-ТЕльНОй МАшиНы Советский патент 1981 года по МПК G06F11/08 

Изобретение относится к вычислительной технике и может быть использо вано для обнаружения и исправления ошибок в тракте приема-передачи дискретных данных (например, при считывании данных из оперативной памяти в устройство управления памятью вычислительной машины).. Устройство для обнаружения и исправления ошибок представляющее собой систему памяти, организованную в виде набора одноразрядных матриц, и блоктранслятор, осуществляющий кодирование информации в случае записи, и обнаружение и исправление ошибки в случае чтения. Этот блок-транслятор ориентирован на взаимодействие со специфически организованной памятью, используемой в аэрокосмических вычислительных системах ijОднако быстродействие предлагаемого устройства ограничено. Наиболее близким к предлагаемому изобретению техническим решением явля ется устройство, которое содержит входной регистр, блок коррекции информации, дешифратор, выходной регистр, формирователь синдрома ошибки, две. схемы сравнения, блок коррекции четности, селектор четности, селектор псевдоэталонного кода Хэмминга, селектор информации, корректор псевдоэталонного кода Хэмминга, регистр четности, контрольную схему сравнения, корректор контрольного кода Хэмминга, буферный регистр, два логических элемента И, регистр синдромов, генератор четности. Данное устройство имеет более высокое быстродействие и предназначено для использования в тракте чтения данных из полупроводниковой оперативной памяти современник универсальных вычислительных машин 2. Однако в этом устройстве в целях контроля оборудования требуется повторное определение синдрома ошибки для циклически сдвинутой информации. .38 Поэтому быстродействие этого устройiCTsa ограничивается из-за необходимости использовать оборудование для / обнаружения и исправления ошибок по Хэммингу два раза последовательно при считывании каждого слова данных из оперативной памяти. Кроме того, обнаруживаются не всенеисправности обо рудования, что может приводить к искажению данных на выходе, при этом устройство содержит избыточное оборудование. Цель изобретения - цовышение быс.тродействия устройства и достоверности передачи данных путем введения средст аппаратногоконтроля оборудования, не требующих использование оборудования для обнарулсения и исправления ошибок по Хэммингу два раза последовательно при передаче слова данных. Для достижения поставленной цели в устройство для обнаружения и исправ ления ошибок в блоках вычислительной машины, содержащее входной регистр, управляющий вход которого является первым управляющим входом устройства, информационный вход - информационным входом устройства, контрольный вход контрольным входом устройства, а выход подключен к информационному входу блока коррекции информации, адресный вход которого соединен с выходом дешифратора, а выход - с информационным входом выходного регистра, управляющий вход является вторым управляющим входом устройства, а первый выход - информациониым выходом устройства, первый формирователь синдрома ош1бки, выход синдрома которого подключен к первому вхо ду первой схемы сравнения, выход которой является Первым выходом ошибки устройства, блок коррекции четности, вход коррекции которого подключен к выходу корректируемой ошибки дешифратора, н вторую схему сравнения, введены блок контроля дешифратора, формирователь контрольного кода по четности скорректированной информации и второй формирователь синдрома ошибки выход которого соединед со вторым вх дом первой схемы сравнения, а вход с выходом входного регистра и со вхо дом первого формирователя синдрома ошибки, выход контроля,по четности которого подключен ко входу контроля по«четности блока коррекции четности а выход синдрома - ко входу дешифра2 .4 тора и ко входу синдрома блока контроля дешифратора,.входы корректируемой ошибки, некорректируемой ошибки и неразрешенных комбинаций которого соединены с выходами корректируемой ошибки, некорректируемой ошибки и неразрешенных комбинаций дешифратора, соответственно, а выход является вторым выходом ошибки устройства, выход блока коррекции четности.подключен к первому входу второй схемы сравнения, второй вход которой соединен с выходом формирователя контрольного кода по четности скорректированной информации, вход которого подключен ко второму выходу выходного регистра, а выход является выходом контрольных разрядов по четности устройства, выход второй схемы сравнения является третьим выходом ошибки устройства. Предлагаемое техническое решение обеспечивает обнаружение и исправление ошибок по Хэммингу без повторного использования оборудования, вырабатывающего синдром ошибки, что позволяет исключить из состава устройства селектор псевдоэталонного кода Хэмминга, регистр четности, регистр синдромов, селектор информации. На фиг. 1 представлена блок-схема устройства для обнаружения и исправления ошибок в блоках вычислительной машины; на фиг. 2 - блок-схема формирователя синдрома ошибки; на фиг.З блок-схема блока коррекции информации; на фиг. 4 - блок-схема формирователя контрольного кода по четности скорректированной информации; на фиг. 5 - блок-схема блока коррекции четности; на фиг. 6 - кодировочная таблица для используемого кода ХэмМинга; на фиг. 7 - таблица декодирования синдрома ошибки. Устройство для обнаружения и исправления ошибок в блоках вычислительной машины содержит входной регистр 1, первый формирователь 2 синдрома ошибки, схему 3 сравнения, дешифратор 4, блок 5 коррекции информации, блок 6 коррекции четности, выходной регистр 7, формпрователь 8 контрольного кода по четности скорректированной информ&ции, схему 9 сравнения, блок 10 контроля дешифратора, включающий в себя один логический элемент 11 сложения по модулю два на восемь ВхоДов (по числу разрядов в синдроме ошибки} , один логический элемент 12 сложения

584091

о модулю два на два входа, четыре огических элемента НЕ 13, два логических элемента И 14 на два входа, один логический элемент ИЛИ 15 на .четыре входа, второй формирователь 16 j синдрома ошибки, информационный вход 17 устройства, вход 18 контрольных разрядов по Хэммингу, вход 19 информации и контрольных разрядов первого формирователя синдрома ошибки, о выход 20 контрольных разрядов по четности первого формирователя синдрома ошибки, выход 21 синдрома ошибки первого формирователя синдрома ошибки, адресный вход 22 блока коррекции ин- 55 формации, информационный вход 23 блока коррекции информации, информационный выход 24 блока.коррекции информации, вход 25 коррекции блока коррекции четности, вход 26 контрольных 20 разрядов по четности блока коррекции четности, выход 27 скорректированной четности блока коррекции четности, информационный вход 28 формирователя контрольного кода по четности скор- 25 ректированной информации, информацинный выход 29 устройства, выход 30 контрольных разрядов по четности устройства, первый управляющий вход 31 устройства,второй управляющий вход устройства, первый выход 33 ошибки устройства, второй выход 34 ошибки устройства, тре„тий выход 35 ошибки устройства.

Формирователь синдрома ошибки (фиг.2) содержит восемь (по числу байтов в 64-х разрядном двойном .слове) восьмивходовых логических элементов 36 сложения по модулю два, представляющих собой формирователь контрольного 40 кода по четности, восемь (по числу контрольных разрядов по Хэммингу) логических элементов 37 сложения по модулю два на 19 входов каждый (в соответствии с таблицей 1), вход 19 ин- 45 формации и контрольных разрядов, выход 20 контрольных разрядов по четности, выход 21 синдрома ошибки.

Блок коррекции информации (фиг.З) содержит 64 (по числу разрядов в двои- jo ном слове) логических элементов 38 сложенця по модулю два на два входа каждый, адресный вход 22, информационный вход 23, информационный выход 24.

Формирователь контрольного кода четности скорректированной информации (фиг. 4) содержит восемь (по числу, байтов в 64-х разрядном двойном слове) логических элементов 39 сложения

26

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

Блок коррекции четности (фиг.5) содержит логический элемент 40 сложения по модулю два на девять входов, вход 25 коррекции, вход 26 контрольных разрядов по четности, выход 27 скорректированной четности.

Устройство работает следующим образом.

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

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

Передаваемое двойное слово (б4-е разряда) и восемь контрольных разрядов по Хэммингу поступают по. входам 17 и 18 соответственно на входной регистр 1, запись на который разрешается управляющим сигналом, поступающим на вход 31.

Информация и контрольные разряды

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

Контрольные разряды по Хэммингу вырабатываются в соответствии с таблицей на фиг. 1, где знаком X помечены те информационные разряды, которые участвуют в образовании данного контрольного разряда по Хэммингу. Поскольку неправильно выработанный синдром ошибки может привести к неправильной коррекции информации, в .устройство введен второй формирователь 16 синдрома ошибки, дублирующий первый. Синдромы ошибки с выхода 21 формирователя 2 и с выхода второго формирователя 16 поступают на входы схемы 3 сравнения. В случае несравнения выработан7841ных синдромов вырабатывается сигнал ошибки на выходе 33. Далее синдром ошибки с выхода 21 формирователя 2 поступает на вход дешифратора 4. Дешифратор 4 декодирует разряды синдрома опшбки в соответствии с таблицей на фиг. 2, где символами S -() обозначены разряды Ьиндрома ошибки, знаком обозначена комбинация разрядов синдрома ошибки (все они равНы нулю), при которой коррекция данных не требуется. Пустая клетка таблицы на фиг. 2 соответствует комбинации разрядов синдрома ошибки, которая указывает на некорректируемую (например, двойную) ошибку данных, числами от О до 63 и символами С () обозначены разряды данных и разряды контрольного кода по ХэммиР1гу соответственно. При таких комбинациях разрядов синдрома ошибки в названном разряде данных или контрольном разряде есть корректируемая ошибка. Так как используемый код Хэмминга обладает избыточностью, то часть комбинацИй разрядов синдрома, отмеченных символом Н (недопустимые комбинации) определяет ошибку аппаратуры дешифратора. Сигналы дешифратора 4, позицион но определяющие номер одного из 64-х разрядов данных с ошибкой, поступают на вход 22 блока коррекции информации. Поскольку часто скорректированную информацию передают с контрольными разрядами почетности (например считанную с контрольными разрядами по Хэммингу из оперативной памяти, информацию передают в блок-запросчик с контрольными разрядами по четности) нет необходимости корректировать конт рольные разряды по Хэммингу.На вход 23 блока коррекции информации поступает информация с регистра 1. Так как непр вильно декодируемый дешифратором 4 синдром ошибки может привести к неправильной коррекции информации, введен блок 10 контроля дешифратора. Из таблицы на фиг. 2 следует, что коррек тируемой ошибке в информационных или контрольньтх разрядах соответствует н четный синдром ошибки; некорректируемой ошибке и ситуации, когда ошибки нет, соответствует четный синдром. Дешифратор ошибки функцонирует неправильно, если есть сигнал на выходе неразрешенных комбинаций дешифратора, если нет сигнала на выходе корректируемой ошибки дешифратора, а синдром нечетный, если нет сигнала на выходе некорректируемой ошибки дешифратора, а синдром четный, н если дешифратор указывает одновременно на . корректируемую и некорректируемую ошибку. При этом на выходе 35 вырабатывается сигнал ошибки, информация с выхода 24 блока 5 коррекции информации поступает на выходной регистр 7, запись на который разрешается управляюш;им сигналом, поступаюш;им по входу 32, и с регистра7 подается на выход 29. Данные со второго информационного выхода регистра 7 поступают на вход 28 формирователя контрольного кода по четности скорректированной информации. Выработанные контрольные разряды подаются на выход 30. Для контроля тракта передачи информации с входного регистра на выходной, а также для-контроля работы блока коррекции информации и формирователя контрольного кода по четности скорректированной информации используется блок 6 Коррекции четности, на вход 26 Которого поступает, побайтная четность принятой информации с выхода 20 первого формирователя 2 синдрома ошибки, а на вход 25 - сигнал о том, что должна быть коррекция в информационном раз ряде. Таким образом, на выходе 27 получаем предсказанную четность информации (с. учетом коррекции) , которая поступает на первый вход схемы 9 сравнения, на второй вход которой поступает четность скорректированной информации из блока 8. В случае несравнения на выходе 34 вырабатывается сигнал ошибки. Повышение быстродействия достигнуто путем введения средств сквозного аппаратного контроля, не требующих использования оборудования для обна- , ружения и исправления ошибок по Хэммингу два раза последовательно при передаче каждого слова данных. В предлагаемом устройстве сквозной контроль работы оборудования построен таким образом, что операция обнаружения и исправления ошибок по ХэмМингу для каждого передаваемого слова данных производится один раз. Это позволяет увеличить быстродействие при передаче данных в два раза. Предлагаемое техническое решение позволяет существенно повысить достоверность передачи данных. Кроме того, не требуется оборудование для хране984091

ния промежуточных результатов контроля, что позволяет сократить оборудование примерно на 20% и тем самым также повысить достоверность передачи данных.,

Формула изобретения

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

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

Источники информации, принятые во внимание при экспертизе

1.Carthy C.F. А memory System design which can tolerate multiple storage array faults. Prac.7th Annu Southeast Sump Syst.Theory AuburnTuskege. Ala 1975. New-York.

2.Авторское свидетельство СССР по заявке № 2546739/24, 29.05.78 (прототип).

Л Ш

840912

Фиг.1

Фиг. 2

Ф«г.5

Фиг,

to

«S)

5