Устройство для исправления ошибок в блоках памяти Советский патент 1984 года по МПК G11C29/00 

равляющий вход : второго формирователя контрольных сигналов, выходы которого являются контрольными выходами устройства.

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

3. Устройство по nn.t и 2, о т дичающее с я тем, что блок

местного управления содержит дешифратор кода управления, входы которого являются входами блока, элементы ИЛИ с третьего по восьмой, элемент Ш1И-НЕ и элементы НЕ, причем первый выход дешифратора кода управления соединен с первыми входами третьего и седьмого элементов ИЛИ, второй и третий выходы дешифратора кода управления подключены соответственно к первьм входам шестого и восьмого элементов ИЛИ и входу первого элемента .НК и к первым входам пятого элемента |Ш1И, элемента ИЛИ-НЕ и второму входу Седьмого элемента ИЛИ, выход которого соединен со входом второго элемента НЕ, четвертый и пятый выходы дешифратора кода управления подключены соответственно ко вторым входам третьего и восьмого элементов ИЛИ и к первому входу четвертого элемента ИЛИ и вторым входам пятого и шестого элементов ИЛИ, шестой выход дешифратора кода управления соединен со вторым входом четвертого элемента ИЛИ, третьими входами пятого, шестого и восьмого элементов ИЛИ, а седьмой выход дешифратора кода управления с третьим входом первого элемента ИЛИ и вторым входом элемента ИЛИ-НЕ, выходы элементов ИЛИ, ИЛИ-НЕ, НЕ и выходы с первого по третий дешифратора кода управления являются выходами блока.

1. yctPCeiGTBO ДЛЯ ИШ1РАВШНИЯ ОШБОК В.ШЮКАХ , щее блок ввода и вьтода m tittaoiaKt блок обнаружения ошбоку j -etsn afs адреса о1вибкИу еор1 екфсфу{1яф1й блок первый фо1Я4Ировагел1 1сонтроЛ1 иы;|; ecilr налов и первый фо1 ироватеяь сягка лов ошибки, причем вШсоды дею1фра о ра адреса ошибки соедвневы с ода1ймй из входов корректируя го блока, йыходы которого йодкй чены к одному из входов блока ввода и вывода fttt4x p мации, выхоли ко1 орого сбедннены с другими входами ко{ рёктирующего блока и входами первого формирователя контрольных сигналов, вЫхоД которого подключен- к одному из входов первого формирователя сигналов о1вибки, о t личающееся тем что с Щелью расширения области применения устройства за счет обеспечения :возмояоюсти наращившия разрядности информационных слов с сохранением минимальной избыточности, в него введены регистр, второй формирователь контрольных сигналов, второй фо жиро- ватель сигналов ошибки, преобразователь кода ошибки и блок местного управления, одни из выходов которого соединены Соответственно с уйраВ-нямщ|Ф1и входами первого формирователя контрольных сигналов и с пёрвьш yttравляюфш В1СОДОМ формирователя сигвйповбщибКй другие входы которого (юдключены к выходсО регистра, причем другие выходы блока местного управления соединены соотве ствеино с упршзляйщвми входами Яреббразователя кода ошибки и с itepBb&i управ ляхяцим ВХОДСН4 второго формирователя Сигналов ошибки, одни входы которого подключены,к выходам первого фохмиродателя сигналов ошибки, а в ходы - ico входам блока обнаружения ошибок, второго формировате ш контрольных сигналов и одним ий входов 0 Преобразователя кода ошибки, выходы Которого соединены со вxoдa вi дешифС ратора адреса ошибки, другие входы преобразователя кода ошиёки и другие входы второго формирователя сигналов ошибки соединены со входами регистра и являются контрольными входами устройства, информационными входами и выходами которого являются вхоО ды и выходы блока ввода и вывода инсь фо1Я4ации, первый управляющий вход косо торого является ВХОДОМ разрешения вода устройства, а второй управляющий вход соединен с управляющим входом регистра и является входом разрешейня ввода устройства, индикаторными выходами которого являются выходы блока обнаружения ошибок, упразляющий вход которого и второй управляющий вход первого формирователя сигналов ошибки объединены и являются входом режима работы устройства, управляюорши входами которого являются входы блока местного управления и уп

Изобретение относится к вычислительной технике и системам передачи данных и предназначено для обнаружения многократных и исправления одиночных ошибок в ЗУ и магистралях передачи данных.

Известно устройство для исправления ошибок в блоках памяти, в котором обнаружение и исправление ошибок в блоках памяти производится с помощью корректируницих кодов Хемминга, для чего используются микросхемы,предназначенные для кодирования и декодирования информации, а также дополнительные БИС ЗУ для хранения контрольных разрядов

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

Наиболее близкие к данному изобретению является устройство для исправления ошибок в блоках памя,ти, в котором осуществляется исправление одиночных ошибок и обнаружение двойных и ряда многократных ошибок, содержащее блок задания направления обменом и триггеров, блок обнаружения ошибок, дешифратор адреса ошибок, корректи311рующий блок и формирователь контроль ных разрядов и формирователь синдрс ма ошибки, причем выход дешифратора адреса ошибки связан с корректирующим блоком, который при обнаружении одиночной ошибки в кодовом слове про изводит исправление ошибочного разряда и выдачу ее через блок задания направления обменом на внешний вывод. Выход блока задания направления обменом связи соединен с формировате лем контрольных разрядов, выход кото рого поступает на вход формирователя признака ошибки C2U.. В данном устройстве используется модифицированный код Хемминга. Недос татком данного устройства является фиксированная разрядность информационного слова, т.е. отсутствие возмож ности, наращивания разрядности o6pa6a тываемых информационных слов при сохранении минимальной избыточности, соответствующей модифицированному коду Хемминга. Указанный недостаток ограничивает область применения данного устройства, так как приводит к большим аппаратурным затратам и снижению надежности при обработке инфор мационных слов большой разрядности. Целью изобретения является расширение области применения устройства за счет обеспечения возможности нара щивания разрядности информационных слов с сохранением минимальной избы;точности, путем .объединения нескольких устройств. Поставленная цель достигается тем что в устройство для исправления ошибок в блоках памяти, содержащее блок ввода и вывода информации, блок обнаружения ошибок, дешифратор адреса ошибки, корректирующий блок, первый формирователь контрольных сигналов и первый формирователь сигналов ошибки, причем выходы дещифратора адреса ошибки соединены с одними из входов корректирующего блока, выходы которого подключены к одному из входов блока ввода и вьшода информации, выходы которого соединены с другими входами корректирующего блока и входами первого формирователя контрольных сигналов, выход которого подключен к одному из входов первого форми рователя сигналов ошибки, введены регистр, второй формирователь контрольных сигналов, второй формирова тель сигналов ошибки, преобразователь кода ошибки и блока местного управления, одни из выходов которого соединены соответственно с управляющими входами первого формиройателя . контрольных сигналов и с первым управляющим входом первого формирователя сигналов ошибки, другие входы которого подключены к выходам регистра, причем другие выходы блока местного управления соединены соответственно с управляющими входами преобразователя кода ошибки и с первым управляющим входом второго формирова|Теля сигналов ошибки, одни входы которого подключены к выходам первого |формирователя сигналов ошибки, а выходы - ко входам блока обнаружения ошибок, второго формирователя контрольных сигналов и одним из входов преобразователя кода ошибки, вьрсоды которого соединены со входами дешифратора адреса ошибки, другие входы преобразователя кода ошибки и другие входы второго формирователя сигналов ошибки соединены со входами регистра и являются контрольными входами устройства, информационными входами и .выходами которого являются входы и выходы блока ввода и вывода информации, первый управляющий вход которого является входом разрешения вывода устройства, а второй управляющий вход соединен с управляющим входом регистра и является входом разрешения ввода устройства, индикаторными выходами которого являются выходы блока обнаружения ошибок, управляющий вход которого и второй управляющий вход первого формирователя сигналов ошибки объединены и явлйются входом режима работы устройства, управляющими входами которого являются входы блока местного управления и управляющий вход второго формирователя контрольных сигналов, выходы которого являются контрольными выходами устройства. Кроме того, преобразователь кода ошибки содержит мультиплексоры с первого по седьмой, первые и вторые входы которых являются входами преобразователя, сумматоры по модулю два и элементы ИЛИ, причем выход шестого мультиплексора соединен с первыми входами первого и второго сумматоров по модулю два, выход седьмого мультиплексора подключен к первому входу третьего сумматора по модулю два. прямой и инверсный выходы которого соединены соответственно с первыми входами первого и второго элементов ИЛИ, вторые входы которых объединены выходы первого и второго сумматоров по модулю два, выходы мультиплексоро с первого по пятый и элементов ИЛИ являются выходами преобразователя, первые и вторые управляющие входы мультиплексоров соответственно объед нены и являются одними из управляющи входов преобразователя, другими управляющими входами которого являются вторые входы элементов ИЛИ, вторые входы первого, второго и третьего сумматоров по модулю два. Кроме того, блок местного управле ния содержит дешифратор кода управления, входы которого являются входа ми блока, элементы ШШ с третьего по восьмой, элемент ИЛИ-НЕ и элементы . НЕ, причем первый вькод дешифратора кода управления соединен с первыми входами, третьего и седьмого элементов ИЛИ, второй и третий выходы дешифратора кода управления подключены соответственно к первым входам шесто го и восьмого элементов ИЛИ и входу первого элемента НЕ и к первым входам пятого элемента ИЛИ, элемента ИЛИ-НЕ и вторрму входу седьмого элемента ИЛИ, выход которого соединен со входом второго элемента НЕ, четве тьш и пятый выходы дешифратора кода управления подключены соответственно ко вторым входам третьего и восьмого элементов ИЛИ и к первому входу четвертого элемента ИЛИ и вторым входам пятого и шестого элементов ШШ, шестой выход дешифратора кода управлени соединен со вторым входом четвертого элемента ИЛИ, третьими входс1ми пятого, шестого и восьмого элементов ИЛИ а седьмой выход дешифратора кода управления - с третьим входом первого элемента ИЛИ и вторым входом элемента ИЛИ-НЕ, выходы элементов ИЛИ, ИПИ-НЕ, НЕ и выходы с первого по тре тий дешифратора кода управления явля ются выходами блока. На фиг. 1 представл ена функциональная схема предложенного устройст ва; на фиг. 2 и фиг. 3 - соответственно функциональные схемы наиболее предпочтительных вариантов выполнения преобразователя кода ошибки и блока местного управления; на фиг.4 и фиг. 5 - примеры матрииьг предложен ного модифицированного кода Хемминга, применяемого для работы устройства; на фиг. 6 - схема объединения двух устройств. Устройство (фиг. 1) содержит блок 1 ввода и вывода информации, регистр 2, первый формирователь 3 контрольных сигналов, первый 4 и второй 5 формирователи сигналов ошибки, блок 6 обнаружения ошибок, преобразователь 7 кода ошибки, дешифратор 8 адреса ошибки, корректирующий блок 9, второй формирователь 10 контрольных сигналов и блок 11 местного управления, предназначенный для управления расширением устройства при увеличении разрядности обрабатываемых информационных слов. На фиг. 1 обозначены вход 12 разрешения вьшода, информационные входы и выходы 13; вход 14 разрешения ввода, контрольные входы 15, вход 16 режима работы, управляющие входы 17 - 20, контрольные 21 и индикаторные 22, 23 выходы устройства. Преобразователь кода ошибки содержит (фиг. 2) мультиплексоры с первого по седьмой , сумматоры 25, 26, 27 по модулю два с первого по третий, первый 28 и второй 29 элементы ИЛИ. На фиг. 2 обозначены выходы 30 -ЗОл и управляющие входы ЗЦ-З преобразователя. Блок местного управления содержит (фиг., 3) дешифратор 32 кода управле-ния, элементы ИЛИ с третьего по восьмой 33-38, элемент ИЛИ-НЕ 39, первый 40 и второй 41 элементы НЕ. На фиг. 3 обозначены выходы , 43 и 44 блока местного управления. На фиг. 4 и фиг. 5 обозначены информационные разряды и приведены значения контрольных сигналов KQ-K в контрольных разрядах, соответствующие модифицированным кодам Хемминга, применяемым при работе с шестнадцатиразрядными-шестидесятичетырех разрядными информационньми словами соответственно. На фиг. 6 изображены первое 45 и второе 46 описываемые устройства, объединенные-для обработки, например, тридцатидвухразрядных информационных слов и внешний формирователь 47 со входами 48. Пёрвьй формирователь 3 контрольных сигналовсостоит из элементов.

реализующих функцию сложения по модулю два(в соответствии с фиг. 4 и фиг, 5) и двух мультиплексоров, управляемых от блока 11 местного управления. ,

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

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

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

Вход 16 задает два основных режима работы устройства: Генерация и Контроль. Эти режимы соответствуют циклам записи и считывания информации в контролируемом блоке памяти(ЗУ)

I В режиме Генерация происходит формирование контрольных сигналов из информационного слова. Информация записываемая в ЗУ,поступает через входы 13 в блок 1 и далее в формирователь 3, который формирует контрольные сигналы в соответствии с кодом .Хемминга (фиг. 4). Полученные контрольные сигналы без изменений проходят чере.з формирователь 4 в формирователь 5. В режиме без расширения разрядности контрольные сигналы без изменения поступают на формирователь 10, дгшее на выходы 21 и записываются в дополнительное ЗУ (на фиг. 1 не показано).

В режиме Контроль устройство производит обнаружение одиночных двоичных и некоторых многократных ошибок и исправление одиночных ошибок. Информационные сигналы, считанные из контролируемого ЗУ, через блок 1 поCTynajoT в формирователь 3, где формируются новые контрольные сигналы, которые в формирователе 4 сравниваются со старыми контрольными сигналами считанными из дополнительного ЗУ чепез регистр 2. В результате на выходе формирователя 4 формируется код ошибки. В режиме без расширения разрядности полученньй код ошибки без изменений проходит через формирователи 5 и 10 на выходы 21 и на входы блока 6, который формирует сигналы одиночной (на выходе 22) и многократный (на выходе 23) ошибок. С выхода формирователя 5 код ошибки поступает на преобразователь 7 и далее используется дешифратором 8 для идентификации ошибочного разряда. Адрес ошибочного разряда поступает в блок 9, в котором осуществляется его инвертирование, и далее исправленная информация через блок 1 выдается на выходы 13. Сигналы ошибок на выходах 22 и 23 и код ошибки используются центральным процессором (на фиг. 1 условно не показан) для организации прерывания и программных методов обработки статических данных по ошибкам.

Предложенное устройство предназначено для обработки восьмиразрядных и шестнадцатиразрядных информационных слов и позволяет организовать совместную работу нескольких таких устройств при необходимости увеличения разрядности информационного слова до шестидесятичетырех с сохранением минимальной избыточности, соответствующей модифицированному коду Хемминга. Устройство основано на применении предложенных модифицированных кодов Хемминга. Проверочная Н-матрица (фиг. 4) используется как базовая для построения Н-матриц большей разрядности при расширении. При совместной работе нескольких предложенных устройств для обработки информации большой разрядности необходимо использовать более длинные коды Хемминга. Для построения таких кодов на основе базового кода (22,16) используется метод сложения по модулю два одинаковых по размерности 16«k проверочных Н-матриц (где k - количество контрольных разрядов - разрядов кода ошибки), получаемых из исходной проверочной (базовой) матрицы 166 путем модификации. Например, для построения кодов (39,32), 456,48), (72,64) на базе исходного кода (22,16 имеем следующие Н-матрицы:

(16 7 )f2 +(i 6 -7)f 32 7 (фиг. 5) ; (1б-8)« +(l6.8)5e+(16.8)f 488; (1б-8) +(16-8)М-ь(16-8)((16-8)Ч4 где знак + обозначает суммировани по модулю два. На фиг. 5 приведен пример указан ных Н-иатриц для модифицированного кода Хемминга (39,32), (56 ,,48)5 (72,64). Модификация исходной Н-матрицы 16«6 для прлучения матриц 16-1 заклю чается во введении дополнительных строк и изменении одной строки (в приведенном примере пятой строки К) причем вводимые дополнительные строки содержат все единицы либо для первого байта информации, либо для второго, т.е. являются результа том взаимной инверсии относительно друг друга. Эффективность применени данного метода построения кодов Хем минга из базового кода (22,16) осно вьшается на минимальном изменении исходного кода Хемминга и, следовательно, минимальной аппаратурной из быточности, вносимой в формировател 3, 4, 5, преобразователь 7 при обес печении программируемости устройств на определенный код. Мультиплексоры в формирователе 3 позволяют осуществлять перестройку кода Хемминга под управлением блока 11 и выбрать один из четырех контрол ных разрядов для Kj- и один из двух контрольных разрядов для К и К-; в соответствии со следующими уравнения ми: До+Д,+Дз- -Д4+Д8+Д9-Д1оД-13 , Д2+Д5+Д +Д,--Д й+Дэ+Д о+Д.з 1 Дг+Д 5+Д ,+Д,.+Д ,/Д,5 К ( «8 3- -fllO+fll|fll2V n-fll5 « 1д,+Д,+Д2+Дз+Д4+Ду+Де+Д7 Элементы И формирователя Ъ позволяют либо пропускать неизменной информацию с блока 4 на выход блока 5 например, в режиме обработки шестнад цатиразрядных слов, либо вьшолнять сложение по модулю Два информации, поступающей с блока 4 и со входов 15 получая таким образом полные контрольные сигналы или полные сигналы ошибки (в зависимости от режима рабо ты) при совместной работе двух предложенных устройств в режиме с удвоенной разрядностью информационного слова. Мультиплексоры (фиг. 2) предназначены для того, чтобы пропус кать на вход дешифратора 8 либо код ошибки с формирователя 5, сформированный этим же устройством, либо код ошибки, полученный через входы 15 с другого такого же устройства, либо с внешних логических схем в режимах работы с расширенной разрядностью более 32 бит. С помощью сумматоров 25, 26, 27, управляемых от блока 11, преобраэователь 7 позволяет учесть все изменения в кодах ошибок, возникающие при переходе с одного кода Хемминга на другой в режимах работы с различным расширением разрядности слова, и тем не усложнять дешифратор 8. При подаче на входы 31 , 322 ™ 31 преобразователя 7 лог. О происходит пропускание контрольных сигналов, а при подаче лог. инвертирование. Элементы ИЛИ 28, 29 служат для маскирования лишних контрольных сигналов сигналом лог. 1 в режиме работы без расширения разрядности. Организация обработки информации разрядностью до шестидесятичетырех бит при совместной работе двух,трех и четырех предложенных устройств осуществляется с помощью входов 17, 18, 19 и блока 11. С помощью входов 17, 18, 19 задается режим обработки информационных слов каждым устройством - определяется общий р,1змер информационного слова, положение информационных разрядов, обрабатываемых данным устройством, в общем слове данных, выбирается соответствующий код Хемминга. Б зависимости от сигналов на входах 17, 18, 19 в устройстве под управлением блока 1i програм ируется работа формирователей 3,, 4, 5 и преобразователя 7. В таблице приведены возможные режимы обработки информационных слов длиной восемь, шестнадцать, тридцать два -сорок восемь и шестьдесят четыре бит для кода Хемми1 га (фиг. 4 и фиг. 5) в зависимости от управляющих сигналов на входах 17, 18 и 19. Технико-экономическое преимущество предложенного устройства заключается в расширении области его применения по сравнению с прототипом за счет нара,ивания разрядности информационных слов с сохранением минимальной избыточности путем объединения для совестной работы нескольких описываеых устройств.

11

о о (22,16) 1(8,16) 0-15

1 (39,32) 1(32) 0-15

О

1 О (39,32)2(32)16-31

/

1 156,48) .1(48)0-15

(72,64)1(64)

1100639

12

Продолжение таблицы

О )2(48) 16-31

(72,64)2(64)

.15М8)3(48) 32-47

(72,64)3(64)

О (72,64)4(64) 48-63

(Pvz. 1

15,

7

77r

l

5;

фиг. 6