Запоминающее устройство с обнаружением и коррекцией ошибок

СОЮЗ СОВЕТСКИХСОЦИАЛИСтИЧЕСНИХРЕСПУБЛИН 4(51) С 11 С 29/00 го дешифратора, один вход блокауправления соединен с выходом второго элемента ИЛИ, вход которого подключен к второму выходу первого дешифратора, другие входы блока управ-ления подклюЧены к выходам второгодешифратора, выход блока коррекциисоединен с первым входом первогоблока элементов И, вход накопителясоединен с первым входом второгоблока элементов И, первый выход блока декодирования соЕдинен с первым Р входомтретьего блока элементов И,выход первого блока элементов И является информационным выходом устрой.ства, выходы второго и третьегоблоков элементов И соединены соответственно с первым и вторым входами блока контроля, выход которогоявляется контрольным выходом устройства, первый и второй выходы блуправления подключены соответст ок вторым входам первого и второгоблоков элементов И, третий выходблока управления соединен с вторымвходом третьего блока элементов" Ии третьим входом блока контроля,четвертый вход которого подключенк четвертому выходу блока управления,2. Устройство по тР. 1, о т л ич а ю щ е е с я тем, что блок управления содержит элементы ИЛИ и элемент И, причем второй вход первогоэлемента ИЛИ соединен с первыми входами второго и третьего элементов ИЛИ, третий вход первого элемента ИЛИ подключен к вторым входамвторого и третьего элементов ИЛИи к выходу элемента И, второй входкоторого сЬединен с вторым входочетвертого элемента ИЛИ, выход к окавенн(54)(57) 1. ЗАПОМИНАЮЩЕЕ УСТРОЙСТВОС ОБНАРУЖЕНИЕМ И КОРРЕКЦИЕЙ ОШИБОК,содержащее накопитель, блок декодирования, блок коррекции, первый и второй элементы ИЛИ, первый дешифратор,причем выход накопителя подключенк первому входу блока коррекции ивходу блока декодирования, первыйвыход которого соединен с входомпервого элемента ИЛИ и входом первого дешифратора, первый выход которого подключен к второму входу блокакоррекции, о т л и ч а ю щ е е с ятем, что, с целью повышения надежнос.ти в работе устройства, в него введены второй дешифратор, блок управления, блоки элементов И и блокконтроля, причем выход первого эле,мента ИЛИ и второй выход блока декодирования соединены с входами второОб ОО мотоГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Киевский ордена Ленина политех нический институт им. 50-летия Вели кой Октябрьской социалистической революции(56) 1. Авторское свидетельство ССС У 433542, кл. С 11 С 29/00, 1975.2. Авторское свидетельство СССР У 443413, кл. С 11 С 29/00, 1975.3, Хетагуров Я.А., Руднев Ю.П. Повышение надежности цифровых устройств методами избыточного кодирования. М., 1974, с. 54 (прототип)ЯО 1138836 А1138836 1 О рого подключен к третьему входу второго элемента ИЛИ, первый и второйвходы первого элемента ИЛИ, первыйвход элемента И, первый и второй 1Изобретение относится к вычисли- тельной технике и может быть использовано в запоминающих системах повышенной надежности, выполненных на функциональных узлах с большой и 5 средней степенью интеграции.Известны запоминающие устройства, содержащие накопитель, блоки кодирования и декодирования, дешифратор номера отказавшего разряда, блоки элементов И и ИЛИ 11 и 1 2 .Недостатками этих устройств являются большая избыточность и неправильна коррекция при появлении оши. бок, кратность которых превышает кор - 15 ректирующую способность применяемого кода.Наиболее близким техническим решением к изобретению явпяется устройство декодирования, содержащее блок 20 декодирования, дешифратор, корректор, элементы ИЛИ и И, причем к входам схемы декодирования и корректора подключен выход накопителя, выход схемы декодирования, связан с входами деши фратора и первого элемента ИЛИ, выход дешифратора подключен к вторым входам корректора и входам второго элемента ИЛИ, причем выход первого элемента ИЛИ соединен с прямым вхо- ЗО дом двухвходового элемента И, а выход второго элемента ИЛИ - с его инверсным входом 1 3 1.Недостатком известного устройства является .то, что при возникновении ошибок, кратность которых превышает корректирующую способность применяемого помехоустойчивого кода, они исправляются неверно.Цель изобретения - повышение надежности в работе устройства.Поставленная цель достигается тем что в запоминающее устройство с обнаружением и коррекцией ошибок, содержащее накопитель, блок декодирования, блок коррекции, первый и второй элевходы четвертого элемента ИЛИ являются входами блока управления, выходами которого являются выходы элементов ИЛИ. 2менты ИЛИ, гервый дешифратор, причем выход накопителя подключен к первому входу блока коррекции и входу блока декодирования, первый выход которого соединен с входом первого элемента ИЛИ и входом первого дешифратора, первый выход которого подключен к второму входу блока коррекции, введены второй дешифратор, блок управления, блоки элементов И и блок контроля, причем выход первого элемента ИЛИ и второй выход блока декодирования соединены с входами второго дешифратора, один вход блока управления соединен с выходом второго элемента ИЛИ, вход которого подключен к второму выходу первого дешифратора, другие входы блока управления подключены к выходам второго дешифратора, выход блока коррекции соединен с первым входом первого блока элементов И, вход накопителя соединен с первым входом второго блока элементов И, первый выход блока декодирования соединен с первым входом третьего блока элементов И, выход первого блока элементов И является информационным выходом устройства, выходы второго и третьего блоков элементов И соединены соответственно с первым и вторым входами блока контроля,выход которого является контрольным выходом устройства, первый и второй выходы блока управления подключены соответственно к вторым входам первого и второго блоков элементов И, третий выход блока управления соединен с вторым входом третьего блока элементов И и третьим входом блока контроля, четвертый вход которого подключен к четвертому выходу блока управления,При этом блок управления содержит элементы ИЛИ и элемент И, причем второй вход первого элемента ИЛИ соединен с первыми входами второго и тре" тьего элементов ИЛИ, третий входз 1138первого элемента ИЛИ подключен к вторым входам второго и третьего элементов ИЛИ и к выходу элемента И, торойвход которого соединен с вторым входом четвертого элемента ИЛИ. выходкоторого подключен к третьему входувторого элемента ИЛИ, первый и второй входы первого элемента ИЛИ, первый вход элемента И, первый и второйвходы четвертого элемента ИЛИ являют Ося входами блока управления, выхода- .ми которого являются выходы элементов ИЛИ,На фиг. 1 представлена функциональная схема предлагаемого запоминающего устройства; на фиг, 2 - схемаблока управления; на фиг. 3 - одиниз возможных вариантов блока декодирования.Запоминающее устройство с обнаружением и коррекцией ошибок содержитнакопитель 1 с адресным входом 2,выход которого подключен к входу блока 3 декодирования и первому входублока 4 коррекции. Первый выход 5 25блока 3 подключен к входу. первогоэлемента ИЛИ 6 и входу первого дешифратора 7, Первая часть выходов 8дешифратора 7 подключена к второмувходу блока 4, а вторая часть выходов 9 - к входу второго элемента ИЛИ 10. Выход 11 элемента ИЛИ 6подключен к первому входу второгодешифратора 12, а второй выход 13блока 3 - к второму входу дешифрато 35ра 12. Первый 14, второй 15, третий 16 и четвертый 17 выходы дешифратора 12 подключены к входам блока 18управления. Выход 19 элемента ИЛИ 10соединен с пятым входом блока 18.К информационному входу первого блока 20 элементов И подключен выходблока 4, к информационному входу второго 21 блока элементов И подключенадресный вход 2 накопителя 1, к.информационному входу третьего блока 22элементов И - выход 5 блока 3. Выходблька 21 подключен к первому входублока 23 контроля, выход 24 которогоявляется контрольным выходом устройства, выход блока 22 подключен к второму входу блока 23. Выход блока 20соединен с информационной магистралью 25. Выход 26 блока 18 подключен к управляющему входу блока 20,55выход 27 - к управляющему входу блока 21,.выход 28 - к управляющемувходу блока 22 И третьему входу бло 836 4ка 23 контроля, выход 29 - к четвертому входу блока 23. Блок 23 контроля представляет собой регистр,условно разбитый на четыре части.В первой части 30 записывается адресячейки накопителя 1, при чтении информации из которой имеет место ошибка, в разряды 31 записывается значение синдрома; определяемое блоком 3,в разряд 32 - признак однократнойошибки, в разряд 33 - признак многократной ошибки.Блок 18 управления (фиг. 2) состоит из двухвходового элемента И 34,двухвходового элемента ИЛИ 35, двух-,трехвходовых элементов ИЛИ 36 и 37и двухвходового элемента ИЛИ 38.Выход 14 блока 12 подключен к первому входу элемента ИЛИ 36, выход 15 - к второму входу элемента ИЛИ 36, первому входу элемента ИЛИ 37 и первому входу элемента ИЛИ 38, выход 16 - к первому входу элемента ИЛИ 35, выход 17 - к первому входу элемента И 34. Выход 19элемента ИЛИ 10 соединен с вторымвходом элемента ИЛИ 35 и вторым инверсным входом элемента И 34. Выходэлемента И 34 подключен к третьемувходу элемента ИЛИ 36, второму входуэлемента ИЛИ 37 и второму входуэлемента ИЛИ 38. Выход 29 элемента ИЛИ 35 соединен с третьим входомэлемента ИЛИ 37.На фиг. 3 приведен один из возможных вариантов построения БДЗ при= 10 разрядам ( и - длина слов, хранимых в накопителе 1) . Блок состоитиз двухвходовых сумматоров 39 - 53по модулю два, к входам которых подключены соответствующие разряды слова, удовлетворяющие правилу образования контрольных разрядов дляокодаХэмминга, исправляющего одну и обна-.руживающего две ошибки. Блок 4 коррекции может быть легко выполнен на и элементах ИСКЛЮЧАЮЩЕЕ ИЛИ, первые входы которых связаны с выходами накопителя 1, а вто- рые - с и первыми выходами 8 первого дешифратора .Дешифратор 12 представляет собой обычный дешифратор на два входа.Дешифратор 7 имеет 1 входов, определяемых из соотношения 1=0 одп, гдеа- ближайшее целое число, неменьше чем б.(выход 11) выходаблока 12 Ошибок нет 14 0 Однократная 15ошибка в нулевомразряде Ошибка четной кратности Ошибка нечетной кратности При чтении информации устройство работает следующим. образом.Слово, считанное из некоторой ячейки накопителя 1, поступает в блоки 3 и 4. Блок 3 вычисляет значения ОКР (выход 5) и значение ДКР (выход 13), Дешифратор 12 выдает сигнал. Элемент ИЛИ 6 имеет В входов, элемент ИЛИ 10 (2 " -п) входов. Блок 20состоит из двухвходовых элементов И,к первым входам которых подключенысоответствующие выходы блока 4 коррекции, а к вторым - выход 26 блока 18 управления. Аналогично построены блоки 21 и 22.В накопителе 1 хранится информация, представленная в коде Хэмминга,1 Оисправляющем одну и обнаруживающемдве ошибки. Такой код имеет основныеконтрольные разряды (ОКР), каждыйиз которых контролирует по четностисвою группу разрядов, и один дополнительный контрольный разряд (ДКР),осуществляющий проверку на четностьвсего слова. Блок 3 определяет значения ОКР, поступающие с выхода 5 наэлемент ИЛИ б,и значение дополнительного контрольного разряда на выходе 13. Сигналы с выхода элемента ИЛИ 6 и выхода 13 блока поступаютна дешифратор 12. Результаты декодирования и работа дешифратора 12 опи-сываются в таблице,на одном из выходов 14-17. Если в считанном слове ошибки отсутствуют, то сигнал с выхода 14 поступает на вход элемента ИЛИ 36 блока 18 управления и с его выхода 26 выдается сигнал, информация с выхода блока 4 коррекции через первый блок 20 элементов И поступает в информационную магистраль 25. Появление сигнала на выходе 15 дешифратора 12 свидетельствует о том, чтоимеет место ошибка в нулевом разряде слова, информация с блока 4 по сигналу с выхода 26 блока 18 управления поступает в информационную магистраль 25. В данном случае значение нулевого разряда, в котором размещается ДКР, не исправляется, так как предполагается, что в дальнейшем он использоваться не будет, если же его необходимо сохранить, то выход 15 дешифратора 12, кроме того, необходимо подключить к нулевому разряду блока 4, что позволит осуществить коррекцию, при этом адрес, по которому производится обращение к накопителю, через блок 21 по сигналу с выхода 27 элемента ИЛИ 37 блока 18 записывается в старшие разряды 30 регистра 23, значения ОКР (синдром), которые в данном случае равны нулю, через блок 22 по сигналу с выхода 28 элемента ИЛИ 38 блока 18 записываются в разряды 31 регистра 23, а в разряд 32 заносится признак однократной ошибки.При появлении сигнала на выходе 16 дешифратора 12 в слове имеется ошибка четной кратности, На выходе 29 элемента ИЛИ 35 появляется сигнал "Ошибка", код адреса при этом записывается в разряды 30 регистра 23, а в разряд 33 записывается признак многократной ошибки. Если на выходе 17 дешифратора 12 появляется сигнал, то это свидетельствует о наличии в слове ошибки нечетной кратности. Код ОКР с выхода 5 поступает на вход дешифратора 7 (дешифрирование производится при любом исходе декодирования; дешифратор 7 не дешифрирует нулевой код ОКР). Если при этом возбуждается один из выходов 8, то имеет место однократная ошибка, срабатывает элемент И 34 блока 18, скорректированное слово с выхода блока 4 через первый блок 20 элементов И по сигналу с выхода 26 элемента ИЛИ 36 поступает в информационнуюмагистраль 25, код адреса заносится в разряды 30 регистра 23, синдром - в разряды 31, а в разряд 32 - признак однократной ошибки. Если же возбуждается один из выходов 9 дешифра тора 7, то имеет место ошибка кратности 3, 5, , на выходе 29 элемента ИЛИ 35 блока 18 появляется сигнал "Ошибка"Таким образом, при наличии одно кратной ошибки в регистр 23 записывается адрес ячейки накопителя 1,код синдрома и признак однократной ошибки. В случае ошибки четной кратности либо обнаруживаемой ошибки нечетной 15 кратности, превышающей единицу, в регистр 23 записывается адрес ячейки и признак многократной ошибки.Синдром в данном случае не фиксируется, так как невозможно определить, 20 место неисправности. Блок 23 используется для хранения информации о неисправностях и их характере. Этот блок может быть выполнен и в виде стека, накапливающего информацию о 25 неисправностях. Содержимое блока 23 ,выводится на выход 24.1П р и м е р, Пусть первоначально записываемая информация в ячейку с адресом 10010110 имела вид 301 1 1 1 0 0 1 1 1 1Ао- А1т АгА 353-Афгде Ар - дополнительный контрольныйразряд;А -А - основные контрольные разря 4ды. 40Каждый из контрольных разрядовконтролирует по четности свою группуразрядов (эти разряды подчеркнуты).Пусть при обращении к данной ячейкена выходе накопителя 1 получено слово, поступающее в блоки 3 и 4,0 1 2 3 4 5 6 7 8 91 1 1 1 0 0 1 0 1 1,и содержащее однократную ошибкув седьмом разряде. В блоке 3 вычисляются значения ОКР и ДКР. На выходе 5.1 сумматора 51 получает единичный сигнал - соотношение для А невыполнено, на выходах 5.2 и 5.3 сумматоров 48 и 49 тоже получаем единицы - соотношения для А и А не вы 2 3полнены, на выходе 5.4 сумматора 45сигнал равен нулю - соотношение дляА 1 выполнено, на выходе 13 сумматора 53 имеем единичный сигнал, Таким образом, значение синдрома равно 8=0111 и ДКР=1. Синдром поступает на элемент ИЛИ 6 и на вход дешифратора 7, в котором возбуждает выход за номером семь, в блоке 4 корректируется разряд номер семь, а на вход дешифратора 12 поступает код 11 (см. таблицу), на выходе 17 появляется сигнал, вызывающий срабатывание элемента И 34. По сигналу с выхода 26 блока 18 скорректированное содержимое блока 4 через блок 20 поступает в информационную магистраль 25, по сигналу с выхода 27 блока 18 адрес 10010110 через блок 21 поступает в старшие разряды 30 регистра 23, по сигналу с выхода 28 элементи ИЛИ 38 код синдрома 0111 через блока 22 записывается в разряды 31 регистра 23, а в разряд 32 заносится единица - признак однократной ошибки.Рассмотрим случай трехкратной ошибки. Пусть при чтении получено слово0 11 2. 3 4 5 6 7 8 91 0 0 0 1 0 1 О,Обнаружение ошибок кратности 3,5,в предлагаемом устройствеосновано на том, что длина Ь слова,хранимого в накопителе 1, меньшеколичества ненулевых дешифрируемыхкомбинаций, т.е, и ( 2",Тогда оставшаяся часть 2 -и выходовпешифратора 7 может быть использова" содержащее ошибки в 3, 7 и 9 разрядах. Значение синдрома, вычисленноев блоке 3, равно 8=1101 он указывает, что имеет место ошибка в разряде 13, т.е. код синдрома превышаетразрядность слова, хранимого в накопителе. В этом случае выход 19 элемента ИЛИ 10 равен единице, так какк блоку 4 подключены только первыедесять выходов дешифратора 7, ак входам элемента ИЛИ 10 (для данного примера) подключены остальные2 т=6 выходов (с 11 по 16) . Срабатывает элемент ИЛИ 35 и на его выходе 29 появляется сигнал "Ошибка". Таким образом, трехкратная ошибкав слове обнаружена, В разряды 30регистра 23 записывается адрес ячейки, а в разряд 33 - единица (признакмногократной ошибки).на для обнаружения части ошибок кратности 3, 5,В известном устройстве исправляются однократные ошибки и обнаруживаются ошибки четной кратности. В предлагаемом устройстве, кроме того,обнаруживается часть ошибок нечетнойкратности 3, 5,Так при=10обнаруживается 40% трехкратных оши 5 бок, а при п=18 27,5 Е."Патент" г.ужгород, ул.Проектная, 4 10695/39 . Тираж 584 ЯНИИПИ Государственного по делам изобрете 113035, Москва, Ж, Раушск