Устройство для обнаружения и ис-правления ошибок b блоках вычисли-тельной машины

 

Союз Советски к

Социалистическив

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К ABTOPCNObAУ CBHPETEllbCTBY пп840912 (6! ) Дополнительное к авт. свил-ву (22)Заявлено 26.09.79 (2!) 2821016/18-24 (51)M. Кя.

Я 06 F 11/08 с присоединением заявки ¹

Госудорствониый коиитет

СССР (23) Приоритет— по делам изобретений и открытий (53) УДК 681 ° 325 (088. 8) Опубликовано 23. 06. 81. Бюллетень,% 23

Дата опубликования описания 25. 06. 8 1 (72) Авторы изобретения

А. И. Слуцкин и Е. Б, Юркова (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ

ОШИБОК 3 БЛОКАХ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ

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

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

Однако быстродействие предлагаемого устройства ограничено.

Наиболее близким к предлагаемому изобретению техническим решением являO

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

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

Однако в этом устройстве в целях контроля оборудования требуется повторное определение синдрома ошибки для циклически сдвинутой информации. з 84О9

Поэтому быстродействие этого устрой:ства ограничивается из-за необходимости использовать оборудование для обнаружения и исправления ошибок по

Хэммингу два раза последовательно при

5 считывании каждого слова данных из оперативной памяти. Кроме того, об наруживаются не все неисправности обо-! рудования, что может приводить к искажению данных на выходе, при этом устройство содержит избыточное оборудование.

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

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

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

45 выходу корректируемой ошибки дешифратора, и вторую схему сравнения, введены блок контроля дешифратора, формирователь контрольного кода по четности скорректированной информации и второй формирователь синдрома ошибки, 50 выход которого соединен со вторым входом первой схемы сравнения, а вход— с выходом входного регистра и со входом первого формирователя синдрома

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

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

На фиг. 1 представлена блок-схема устройства для обнаружения и исправления ошибок в блоках вычислительной машины; на фиг. 2 — блок-схема формирователя синдрома ошибки; на фиг.З блок †схе блэка коррекции информации; на фиг. 4 — блок-схема формирователя контрольного кода по четности скорректированной информации; на фиг. 5 — блок-схема блока коррекции четности; на фиг. 6 — кодировочная таблица для используемого кода Хэмминга; на фиг. 7 — таблица декодирования синдрома ошибки.

Устройство для обнаружения и исправления ошибок в блоках вычислительной машины содержит входной регистр 1, первый формирователь 2 синдрома ошибки, схему 3 сравнения, дешифратор 4, блок 5 коррекции информации, блок 6 коррекции четности, выходной регистр 7, формирователь 8 контрольного кода по четности скорректированной информации, схему 9 сравнения, блок IQ контроля дешифратора, включающий в себя один логический элемент 11 сложения по модулю два на восемь входов (по числу разрядов в синдроме ошибки), один логический элемент 12 сложения

84091 2 по модулю два на два входа, четыре логических элемента HE 13, два логических элемента И 14 на два входа, один логический элемент ИЛИ !5 на .четыре входа, второй формирователь 16 синдрома ошибки, информационный вход 17 устройства, вход 18 контрольных разрядов по Хэммингу, вход 19 информации и контрольных разрядов первого формирователя синдрома ошибки, выход 20 контрольных разрядов по четности первого формирователя синдрома ошибки, выход 21 синдрома ошибки первого формирователя сийдрома ошибки, адресный вход 22 блока коррекции информации, информационный вход 23 блока коррекции информации, информационный выход 24 блока. коррекции информа-"ции, вход 25 коррекции блока коррекции четности, вход 26 контрольных разрядов по четности блока коррекции четности, выход 27 скорректированной четности блока коррекции четности, информационный вход 28 формирователя контрольного кода по четности скорректированной информации, информаци1онный выход 29 устройства, выход 30 контрольных разрядов по четности устройства, первый управляющий вход 31 устройства, второй управляющий вход 32З, . устройства, первый выход 33 ошибки устройства, второй выход 34 ошибки устройства, третий выход 35 ошибки устройства.

Формирователь синдрома ошибки (фиг.2) содержит восемь (по числу байтов в 64-х разрядном двойном слове) восьмивходовых логических элементов 36 сложения по модулю два, представляющих собой формирователь контрольного 4О

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

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

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

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

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

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

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

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

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

Контрольные разряды по Хэммингу вырабатываются в соответствии с таблицей на фиг. I, где знаком "Х" помечены те информационные разряды, которые.участвуют в образовании данного контрольного разряда по Хэммингу. Поскольку неправильно выработанный синдром ошибки может привести к неправильной коррекции информации, в устройство введен второй формирователь 16 синдрома ошибки, дублирующий первый. Синдромы ошибки с выхода 21 формирователя 2 и с выхода второго формирователя 16 поступают на входы схемы 3 срав- . нения. В случае несравнения выработан7 84091 ных синдромов вырабатывается сигнал

1ошибки на выходе 33. Далее синдром ошибки с выхода 21 формирователя 2 поступает на вход дешифратора 4. Дешифратор 4 декодирует разряды синдро5 ма ошибки в соответствии с таблицей на фиг. 2, где символами S„(i=0-:7) обозначены разряды синдрома ошибки, знаком + обозначена комбинация разрядов синдрома ошибки {все они равны нулю), при которой коррекция данных не требуется. Пустая клетка таблицы на фиг. 2 соответствует комбинации разрядов синдрома ошибки, которая указывает на некорректируемую (напри- мер, двойную) ошибку данных, числами от 0 до 63 и символами С (i=0-.7)

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

Так как используемый код Хэмминга обладает избыточностью, то часть ком- 5 бинаций разрядов синдрома, отмеченных символом Н (недопустимые комбинации), определяет ошибку аппаратуры дешифратора. Сигналы дешифратора 4, позиционйо определяющие номер одного из 64-х разрядов данных с ошибкой, поступают на вход 22 блока коррекции информации. Поскольку часто скорректированную информацию передают с контрольными разрядами по четности (например, 35 считанную с контрольными разрядами по Хэммингу из оперативной памяти, информацию передают в блок — запросчик с контрольными разрядами по четности), нет необходимости корректировать конт4, рольные разряды по Хэммингу. На вход 23 блока коррекции информации поступает информация с регистра 1. Так как неправильно декодируемый дешифратором 4 синдром ошибки может привести к не- 45 правильной коррекции информации, введен блок 10 контроля дешифратора. Из таблицы на фиг. 2 следует, что корректируемой ошибке в информационных или контрольных разрядах соответствует нечетный синдром ошибки; некорректируемой ошибке и ситуации, когда ошибки нет, соответствует четный синдром.

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

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

Данные со второго информационного выхода регистра 7 поступают на вход 28 формирователя контрольного кода по четности скорректированной информации. Выработанные контрольные разряды подаются на выход 30.

Для контроля тракта передачи информации с входного регистра на выходной, а также для контроля работы блока коррекции информации и формирователя контрольного кода по четности скорректированной информации используется блок 6 коррекции четности, на вход 26 которого поступает. побайтная четность принятой информации с выхода 20 первого формирователя 2 синдрома ошибки, а на вход 25 — сигнал о том, что должна быть коррекция в информационном разряде. Таким образом, на выходе 27 получаем предсказанную четность информации (c учетом коррекции), которая поступает на первый вход схемы 9 сравнения, на второй вход которой поступает четность скорректированной информации из блока 8. В случае несравнения на выходе 34 вырабатывается сигнал ошибки.

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

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

Хэммингу для каждого передаваемого слова данных производится один раз.

Это позволяет увеличить быстродействие при передаче данных в два раза.

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

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

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

Устройство для обнаружения и исправления ошибок в блоках вычислительной машины, содержащее входной регистр, управляющий вход которого,. является первым управляющим входом устройства, контрольный вход — контрольным входом устройства, а выход подключен к информационному входу блока коррекции информации, адресный вход которого соединен с выходом дешифратора, а выход — с информационным о входом выходного регистра, управляющий вход которого является вторым управляющим входом устройства, а пер— вый выход — информационным выходом устройства, первый формирователь синд- 5 рома ошибки, выход синдрома которого подключен к первому входу первой схемы сравнения, выход которой является первым выходом ошибки устройства, блок коррекции четности, вход коррекции которого подключен к выходу корректируемой ошибки дешифратора, и вторую схему сравнения, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства и достоверности передачи данных, в него введены блок контроля дешифратора, формирователь контрольного кода по четности скорректированной информации и второй формирователь синдро- 4О

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

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

1. Carthy С.F. А memory System

design which can tolerate multiple

storage array faults. Prac. 7th Аппи

Southeast Sump SYst.Theory AuburnTuskege. Ala 1975 New-York.

2. Авторское свидетельство СССР по заявке 1"- 2546739/24, 29.05. 78 (прототип).

840912 к

Ъ

Ъ

М, ЪС х

Ъс

ФС

Ъю х

Ъ< ъа х к

ЪС,"

Ъ4 х н .Ъ

Эе х

Э

Ъч х к к к х м х к с к к к к

Ъа к к к с к к к

Ъ

3С

Ъ<

Э4

ЭС

Мф к

ЬС ьс

Ъ< ъС м эс

Ъ4, к эс

Ъ4

3С

ЭС вС

SIC

1С

Ьф ъ4 эс к к

М, ЪС м

Ф ъ

Ф

Фц с х х

3С, х к к к

МС к

OC э4

° С

lC

Э4 м

° 4 к

Э4

М х

rc ьс к м

° 4

1С

° с

ВС

3С

3К х мв

ЭФ к к к

3С

М к

ЪС к

Э С

ЪС н

ФС х эс

3С к

Ъ4 х к к к н

ЪС

ЪС к к

ФС м

М к

Ъ< с к к м

ЭС к

K х х

М, х к

3С к к к к н к х х к

ЭС к

ЪС к х к х к х

Ъа(х х

ЭС

Ъс к

840912

Заказ 4768/73 Тираж 745.ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

Ра ская наб. . 4 5

Подписное

113035, Москва, Ж 35, уш, д /

Филиал ППП Патент", r. Ужгород, ул. Проектная, 4

Составитель Н. Быкова

Редактор Н. Пушнен ова Техред М.Майорош Корректор А.Гриценко