Устройство для коррекции ошибок в блоке памяти

пментчс теикилм-натечь .1 нтиав ф ДОП ИСАНИЕИЗЬЬРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоциалистическикРеспублик и 765886(51) М. Кл,а Ст 11 С 2900 Гооударстееиимй комитет Опубликовано 23.09,80. Бюллетень,% 35Дата опубликования описания 28.09.80(53) УДК 681,327 (088.8) до делам иэооретеиий и открытий(54) УСТРОИСТВО ДЛЯ КОРРЕКЦИИ ОШИБОК В БЛОКЕ ПАМЯТИ1Изобретение относится к запоминающим устройствам.Известно устройство для коррекции ошибок в блоке памяти содержащее регистры, схему сравнения, логические элементы 11.Недостатком этого устройства являются большие аппаратурные затраты и малая скорость работы.Из известных устройств наиболее близким техническим решением к предлагаемому изобретению является устройство для коррекции ошибок в блоке памяти, содержащее информационный регистр, регистр инверсного кода, элементы И, НЕ и ИЛИ, сумматор по модулю два, схему сравнения и блок управления, причем выходы информационного регистра подключены к первым входам одних из элементов И, входам элементов НЕ, сумматоров по модулю два и первому входу схемы сравнения, второй вход которой соединен с выходом регистра инверсного кода, выходы элементов НЕ подключены к первым входам других элементов И, вторые входы элементов И соединены с одними из выходов блока управления, а выходы - со входами элементов ИЛИ, выходы которых подключены к одним из выходов устройства,2выходы сумматоров по модулю два соединены с одними из входов информационного регистра, другие входы которого и входы регистра инверсного кода соединены со входами устройства 12.Недостатком этого устройства является,во-первых, невысокое быстродействие, вызванное тем, что для кодирования информации, записываемой в память, кроме основного цикла записи, необходимо дополнительно произвести циклы чтения и записи. Во-вто рых, малая вероятность многократных ошибок делает неоправданным трехкратное увеличение цикла записи запоминающей системы (цикл записи принят равным циклу чтения).Если ошибки преимущественно вызваныотказами типа генератор О и генератор 1, то коррекция ошибок может быть осуществлена с меньшей временной избыточностью,Цель изобретения - повысить быстродействие устройства.Это достигается тем, что устройство содержит блок анализа отказов, вход которого подилючен к выходу схемы сравнения, и логический блок, входы которого соединены соответственно с выходами. блока анализаотказов, схемы сравнения, сумматоров по модулю два, информационного регистра и элементов НЕ.При этом блок анализа отказов целесообразно выполнить так, чтобы он содержал группы элементов И и элементы ИЛИ, входы которых подключены к выходам элементов И соответствующих групп, входы элементов И и выходы элементов ИЛИ соединены соответственно со входами и выходами блока анализа отказов. Предпочтительным вариантом выполнения логического блока является такой блок, который содержит группы элементов И, элементы ИЛИ и блоки инверсии, причем выходы элементов И первой . группы подключены ко входам элементов ИЛИ, выходы которых соединены с одними из входов элементов И второй группы, одни из входов блоков инверсии подключены к выходам элементов НЕ второй группы, а выходы - к выходам логического блока, входы которого соединены со входами элементов И первой группы и другими входами элементов И второй группы и блоков инверсии.Целесообразным вариантом выполненияблока инверсии является блок, содержащийэлементы НЕ, И и ИЛИ, причем первые входы первого и второго элементов И подключены соответственно ко входу и выходу элемента НЕ, а выходы - ко входам элементаИЛИ, выход которого подключен к выходублока инверсии, вторые входы элементов Ии вход элемента НЕ соединены соответственно со входами блока инверсии.На фиг. 1 изображена структурная схема предлагаемого устройства; на фиг. 2 -часть блока анализа отказов, называемаясхемой анализа отказов и соответствующаяодному контрольному разряду в информационном слове; на фиг. 3 - схема логического блока; на фиг. 4 - схема блока инверсии.Устройство содержит (см. фиг. 1) информационный регистр 1, регистр 2 инверсногокода, элементы НЕ 3, элементы И 4 и 5,элементы ИЛИ 6, сумматоры 7 по модулюдва, схему сравнения 8, блок 9 анализа отказов, логический блок 10. Элементы ИЛИ би блок 10 имеют соответственно выходы11 и 12, регистры 1 и 2 - соответственно входы 13 и 14,В состав устройства также входит блокуправления 15.Вход блока 9 подключен к выходу схемысравнения 8. Входы блока 10 соединены соответственно с выходами блока 9, схемы сравнения 8, сумматоров по модулю два, регистра 1 и элементов НЕ 3,Блок 9 анализа отказов (см. фиг. 2) состоит из К схем анализа отказов, где К - количество контрольных разрядов в информационном слове, записываемом в запоминающую ячейку. На фиг, 2 приводится примервыполнения 1-ой (1 с;,1(1) схемы анализаотказов. 4Схема анализа отказов состоит иэ 1-вхо.довых элементов И 16, входы которых связаны с соответствующими выходами схемы сравнения 8, а выходы соединены со входами элемента ИЛИ 17, своим выходом связанным с блоком 10 (1 - количество разрядов в анализируемой группе разрядов информационного слова, считываемого яз запоминающей ячейки).Схема анализа отказов реализует логи-ческую функцию у; = х хах зх Ч х х х зо хЧх 1 хгхзхЧххгхз.,х, гдех ьх - сигнаЛы на выходах соответствующих разрядов схемы сравнения 8, у = 1, если количество отказавших разрядов в анализируемой группе разрядов равно единице.В противном случае у; = О,Таким образом, на выходах блока 9 анализа отказов формируется код у у у зу,Причем у соответствует группе разрядов,контролируемых по четности 1:м контрольным разрядом, что дает воэможность опредео лить - равняется ли единице количество дефектных разрядов в данной группе,Блок 10 (см, фиг. 3) состоит из первойгруппы элементов И 18, входы которых.связаны с соответствующими выходами сумматоров 7 по модулю два и блока 9 анализа И отказов, а выходы подключень через элементы ИЛИ 19 к первым входам элементов И 20 второй группы. Ко вторым входам элементов И 20 подключены выходы схемы срав. нения 8. Выходы элементов И 20 соединеныс первыми входами блоков инверсии 21, вторые и третьи входы которых связаны соответственно с прямыми и инверсными выходами информационного регистра 1.На фиг. 3 принятые следующие обозначения для сигналови А АА - на выходах блока по модулюдва;у ну.у - на выходах блока 9 анализаотказов;х ьх х - на выходах схемы сравнения 8;Я Я а"Я - на прямых выходах информационного регистра 1;Я ,ЯЯп - на инверсных выходах информационного регистра 1;где п - количество разрядов дополненногоинформационного слова,43Блок инверсии 21 содержит элементыНЕ 22, первый 23 и второй 24 элементы Ии элемент ИЛИ 25, причем первые входы элементов И 23 и 24 подключены соответственно ко входу и выходу элемента НЕ 22, афф выходы - ко входу элемента ИЛИ 25, выход которого подключен к выходу блока 21.Вторые входы элементов И 23 и 24 и входэлемента НЕ 22 соединены соответственно совходами блока 21,ЦРабота устройства происходит следующим образом,В цикле записи информационное словопо входу 13 поступает в информационный регистр 1, кодируется в соответствии с алго6Пусть ячейка имеет четыре дефектных разряда, например, 1-й является генерато. ром 1, 2-й - генератором О, 4-й - генератором , 8-ой генератором 0, 10010001110АААзАПосле цикла чтения в информационный регистр 1 поступает искаженный код х. = = 0111100111 О.В результате декодирования этого кода сумматорами 7 получим:Группа, контролируемая А и О1 О1 ошибка А=1 Группа, контролируемая А1О О 1ошибка А г= Группа, контролируемая А з, 1 1 О О О ошибка А з=Группа, контролируемая А 4, 1 1 1О ошибка А 4=Наличие ошибок по контрольным разрядам свидетельствует о необходимости коррекции считанной информации.После циклов повторной записи и чтения в регистр 2 поступает код х з = 01010111000На выходе схемы сравнения 8 в результате сравнения кодов ха = 11010000000. Разряды этого кода, имеющие значение 1, соответствуют позициям отказавших разрядов. С выхода схемы сравнения 8 код ха поступает на блок 9 анализа отказов, на выходе которого формируется 4-разрядный код ууаузу 4. =111, так как в каждой иэ контрольных групп находится только один дефектный разряд. Так, в группе, контролируемой А дефектным является 1-й разряд, в группе контролируемой Аг - 2-й разряд, в группе, контролируемой Аз - 4-й разряд, а в группе, контролируемой А - 8-й разряд. В то же время каждый контролируемый разряд дает ошибку, Поэтому коррекция считанной информа. ции осуществляется блоком 10 путем инверсии отказавших разрядов. Скорректированное информационное слово поступает на выход 2.Таким образом, предлагаемое устройство, используя кодирование информационного слова, например, кодом Хэмминга, предназначенным для исправления одной ошибки, позволяет исправлять к-кратную ошибку (где к - количество контрольных разрядов в коде Хэмминга) при условии, что количество отказавших разрядов в группах разрядов информационного слова, контролируемых соответствчющими контрольными разрядами, не ьолее одного. При этом необхо. димо выполнить дополнительные циклы чтения и записи только при обнаружении ошиб. ки, в то время как в известном устройстве каждая операция занесения информации в запоминающую ячеику сопровождается двумя циклами записи и одним циклом чтения. формула изобретения 1. Устройство для коррекции ошибок вблоке памяти, содержащее информационный 765886ритмом образования кода Хэмминга, черезэлементы И 4 и ИЛИ 6 в прямом коде поступает на выход 11 и заносится в выбранную ячейку запоминающей системы (нафиг. 1 не показана). В цикле чтения считанное информационное слово поступает в информационный регистр 1, а с его выхода -на сумматоры 7. В случае отсутствия ошибок по всем контрольным разрядам информационное слово с выхода информационного регистра 1 через блок 10 поступает навыход 12. Если искажающие информацию от бказы имеют место, то по сигналам блокауправления 15 осуществляется коррекциясчитанной информации. Для этого содержимое информационного регистра 1 черезэлементы НЕ 3, И 5 и ИЛИ 6 в инверсномкоде поступает на выход 11 и заносится всоответствующую ячейку запоминающей системы, Затем выполняется цикл чтения с занесением считанной информации по входу: 14 в регистр 2.Содержимое регистров 1 и 2 сравнивается между собой на схеме сравнения 8. Навыходах схемы сравнения 8 сигнал 1 появляется в тех разрядах, в которых совпадают кодырегистров 1 и 2. Эти разряды запоминающей ячейки являются отказавшими и представляют собой генераторы конс- птаит (генератор 0 или генератор 1). Свыхода схемы сравнения 8 результат сравнения поступает на блок 9 анализа отказов,на выходах которого, формируются сигналыанализа отказов, на выходах которого формируются сигналы у ну а,у. Коррекция счиэотаиной информации осуществляется в блоке 1 О путем инверсии тех разрядов считанного информационного слова, в которых имеют место отказы (т. е. логические уровни сигналов на выходах схемы сравнения 8 поэтим разрядам равны 1) и для которых выполняются следующие условия:отказавший разряд принадлежит 1-й (1С (к) группе разрядов, а 1-й контрольныйразряд, контролирующий по четности этугруппу, равен 1;количество отказавших разрядов в 1-й(1 . .к) группе равно единице, т, е. 1-ясхема анализа отказов блока 9 формируетсигнал у, = 1. Если эти условия не выполняются, то инвертирование отказавших разрядов в блоке 10 не производится,Работа устройства иллюстрируется следующим примером.Допустим, необходимо записать в ячейку восьмиразрядное информационное словох 1 = 11001110. В соответствии с принципом впостроения кодов Хэмминга информационноеслово хдополняется четырьмя контрольными разрядами Ап А 2, Аз, А и на вход11 для записи в выбранную ячейку поступает код: на= А АаАз 100 А,1110. КонтрольЛные разряды А и А 4 формируются сумматорами 7 по модулюдва, В рассматриваемом примере А, = 1, А а = О, А з = О, А 4 =О.Следовательно, х а = 011010011110.Хрегистр, регистр инверсного кода, элементы И, НЕ и ИЛИ, сумматор по модулю два, схему сравнения и блок управления, причем выходы информационного регистра подключены к первым входам одних из элементов И, входам элементов НЕ, сумматоров по моду. лю два и первому входу схемы сравнения, второй вход которой соединен,с выходом регистра инверсного кода, выходы элементов НЕ подключены к первым входам других элементов И, вторые входы элементов И соединены с одними из выходов блока управления, а выходы - со входами элементов ИЛИ, выходы которых подключены к одним из выходов устройства, выходы сумматоров по модулю два соединены с одними из входов информационного регистра, другие входы кото-. рого и, входы регистра инверсного кода сое диненц со входами устройства, отличающе-. еся тем, что, с целью повышения быстродействия устройства, оно содержит блок авализа отказов, вход которого подключен к выходу схемы сравнения, и логический блок; входы которого соединены соответственно с вц 20 ходами блока анализа отказов, схемы сравнения, сумматоров по модулю два, информационного регистра и элементов НЕ.2. Устройство по и. 1, отличающееся тем, что блок анализа отказов содержит груп пу элементов И и элементы ИЛИ, входы которых подключены к выходам элементов И соответствующих групп, входы элементов И и выходы элементов ИЛИ соединены соот 68ветственно со входамн и выходами блокаанализа отказов,3. Устройство по пп. 1 и 2, отличающеесятем, что логический блок содержит группыэлементов И, элементы ИЛИ и блоки инверсии, причем выходы элементов И первойгруппы йодключены ко входам элементовИЛИ, выходы которых соединены с одниминз входов элементов И второй группы, одни из входов блоков инверсии подключенык выходам элементов НЕ второй группы,а выходы - к выходам логического блока,входы которого соединены со входами элементов И первой группы и другими входамиэлементов И второй группы и блоков инверсии.4. Устройство по п. 3, отличающеесятем, что каждый блок инверсии содержитэлементы НЕ, И и ИЛИ, причем первые входы первого и второго элементов И подключены соответственно ко входу и выходу элемента НЕ, а выходы - ко входам элемента ИЛИ, выход которого подключен к выходу блока инверсии, вторые входы элементовИ и вход элемента НЕ соединены соответственно со входами блока инверсии.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР402870, кл. б 06 Г 1/00, 1972.2. Авторское свидетельство СССР622086, кл. б 11 С 29/00, 1976 (прототип).7 б 5886 ю уз Составитель В а Техред К, Шуфр Тираж 662 ВНИИПИ Государственного ко по делам изобретений . и 13035, Москва, Ж - 35, Раушск илнал ППП сПатентэ, т. Ужгород, Рудач х, лр Мр Ха х Хр х ху Редактор О. Стенин Заказ 66 8/48 и Корректор Ю. МакаренкоПодписноеитета СССРоткрытийи на 6 д. 4/5ул. Проектная, 4