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

(9) 4(5)у С 11 С 29 ГОСУДАРСТВЕН 10 ДЕЛАМ ИЗО НОМИТЕТ СССР ТЕНИИ И ОТНРЫТИИ(54) (57) ЗАПОИИНАЮЩЕЕ УСТРОЙСТВО СКОРРЕКЦИЕЙ ОШИБОК, содержащее накопитель, блок декодирования, блоккоррекции, первый дешифратор, первый элемент ИЛИ, второй дешифратор,первый блок элементов. И, регистрпрямого кода, блок управления, причем первый выход блока декодированиясоединен с входами первого элемента ИЛИ и первого дешифратора,выходкоторого. подключен к одному входублока коррекции, выход которого соединен с одним входом первого блокаэлементов И, второй выход блока декодирования и выход первого элемента,ИЛИ подключены к входам второго дешифратора, одни выходы которого соединены с первым и вторым входамиблока управления, третий вход которого является управляющим входом устройства, о т л и ч а ю щ е е с я д(56) 1. Авторское свидеУ 433542, кл. 6 11 С 292. Авторское свидетелУ 443413, кл. С 11 С 293. Авторское свидетелВ 855730, кл. С 11 С 114. Авторское свидетелпо эаявке У 3643564, кл05.11.83 (прототип). тем, что, с целью повьппения надежйости устройства, в него введены второй блок элементов И, блок кивер" торов, второй элемент ИЛИ, первый н второй блоки элементов ИЛИ, регистр инверсного кода, причем выход накопителя соединен с одними входа- Р ми второго блока элементов И и бло" ка инверторов, выходы которых подключены к входам первого блока элементов ИЛИ, выход которого соединен с входом блока декодирования, другим входом блока коррекции и одним входом регистра инверсного кода, выход которого подключен к входу накопителя, выход блока коррекции соеди- Б нен с одним входом регистра прямого кода, выход которого и выход первого блока элементов И подключены к входам второго блока элементов ИЛИ, выход которого является информационным выходом устройства, другие выходы второго дешифратора соединены с вхоами второго элемента ИЛИ, вьпсод которого подключен к четвертому входу блока управления, первый и шестой выходы которого соединены с други ми входами регистра инверсного кода, : другие входы регистра прямого кода подключены к третьему и шестому выходам блока управления, первый, четвертый и седьмой выходы которого соединены соответственно с другими входами второго блока элментов И, первого блока элементов И и блока инверторов, второй и пятый выходы блока управления являются индикаторными выходами устройства.11 5201Изобретение относится к вычислительной технике и может быть использовацо в качестве основного и вспомогательного запоминающих устройствв вычислительных системах,Известны запоминающие устройства,содержащие накопитель, регистр адреса, блоки кодирования и декодирования, связанные с накопителем, входной и выходной регистры, блок поразрядного сравнения, блоки элементов Ии ИЛИ 11 и Г 21.Недостатки этих устройств - избыточность, а также неправильная коррекция при появлении ошибок, кратностьь которых. превышает корректирующую способность применяемого кода.Известно также запоминающее устройство с коррекцией ошибок, содержащее накопитель, выход которого подключен к входам регистров прямого иобратного кода, блок обнаруженияотказавших разрядов, входы которогосоединены с прямыми выходами регистров прямого и обратного кода, корректирующее устройство, вход которогосоединен с выходом регистра прямогокода, схему равенства кодов, к входамкоторых подключены выходы блока обнаружения отказавших разрядов и кор- Зоректирующего устройства, блок управления, входы которого связаны с выходами корректирующего устройстваи схемы равенства кодов, а выходы -с входами регистров прямого и обратного кодов и блока элементов И, квторым входам которого подключенвыход корректирующего устройства.Выход регистра прямого кода соединенс входом накопителя 33.Наиболее близким к изобретениюявляется запоминающее устройство скоррекцией ошибок, содержащее накопитель, выход которого соединен содним входом блока коррекции и входом блока декодирования, один выходкоторого соединен с входами первогодешифратора и первого элемента ИЛИ,выход которого и другой выход блокадекодирования соединены с входамивторого дешифратора, выходы которогосоединены с блоком управления,выход первого цешифратора - с другимвходом блока коррекции, выход которого соединен с одним входом элемен 55та И, другой вход которого соединенс выходом блока управления, первыевходы других элементов И - соответственна с входом накопителя ц выхо 2 2дом блока декодирования, вторые входы - с выходами блока управления, выхоцы других элементов - с входами регистра прямого кодаНедостатком известных устройств является ограниченная корректирующая способность при появлении ошибок, вызванных сбоями, а также совместным действием отказов и сбоев.Целью изобретения является повышение надежности устроцства.Поставленная цель достигается тем, что в запоминающее устройство с коррекцией ошибок, содержащее накопитель, блок декодирования, блок коррекции, первый дешифратор, первый элемент ИЛИ, второй дешифратор, первый блок элементов И, регистр прямого кода, блок управления, причем первый выход блока декодирования соединен с входами первого элемента ИЛИ и первого дешифратора, выход которого подключен к одному входу блока коррекции, выход которого соединен с одним входом первого блока элементов И, второй выход блока декодирования и выход первого элемента ИЛИ подключены к входам второго дешифратора, одни выходы которого соединены с первым и вторым входами блока управления, третий вход которого является управляющим входом устройства, введены второй блок элементов И, блок инверторов, второй элемент ИЛИ, первый и второй блоки элементов ИЛИ, регистр инверсного кода, причем выход накопителя соединен с одними входами второго блока элементов И и блока инверторов, выходы которых подключены к входам первого блока элементов ИЛИ,выход которого соединен с входом блока декодирования, другим входом блока коррекции и одним входом регистра инверсного кода, выход которого подключен к входу накопителя, выход блока коррекции соединен с одним входом регистра прямого кода, выход которого и выход первого блока элементов И подключены к входам второго блока элементов ИЛИ, выход которого является информационным выходом устройства, другие выходы второго дешифратора соединены с входами второго элемента ИЛИ, выход которого подключен к четвертому входу блока управления, первый и шестой выходыкоторого соединены с другими входами регистра инверсного код, дру35 гие входы регистра прямого кода подключены к третьему и шестому выходам блока управления, первый, четвертый и седьмой выходы которого соединены соответственно с другими 5 входами второго блока элементов И, первого блока элементов И и блока инверторов, второй н пятый выходы блока управления являются индикаторными выходами устройства.На фиг. 1 приведена блок-схема устройства; на фиг. 2 - схема блока управления; на фиг.3 - один из вариантов блока декодирования.Устройство содержит накопитель 1, 15 выход которого подключен к первым входам второго блока 2 элементов И и блока 3 инверторов, выходы блоков 2 и 3 соединены с входами первого блока 4 элементов ИЛИ, выход которого 20 подключен к входу блока 5 декодирования одним входом, блока 6 коррек" ции и регистра 7 инверсного кода, выход которого соединен с входом накопителя 1. Выход блока 6 коррекции 25 связан с одними входами первого блока 8 элементов И и регистра 9 прямого кода, выходы которых через второй блок 10 элементов ИЛИ соединены с числовой магистралью 11. Информацион ные выходы 12 блока 5 подключены к входам первого элемента ИЛИ 13 и первого дешифратора 14, выход которого соединен с другим входом блока 6 коррекции. К первому входу второго дешифратора 15 подключен выход первого элемента ИЛИ 13, к второму - управляющий выход 16 блока 5. Первый и второй выходы блока 15 соединены с входами второго элемента ИЛИ 4 О 17, выход 18 которого подключен к одному из входов блока 19 управления. Третий выход 20 и четвертый выход 21 блока 15 подключенык входам блока 19. На вход 22 блока 19 45 поступает сигнал "Чтение" с центрального устройства управления.Выход 23 блока 19 управления подключен к первому управляющему входу блока 7 и к управляющему входу блока 5 О 2, с выхода 24 блока 19 выдается сигнал "Ошибка", выходы 25 и 26блока 19 управления подключены соответственно к первому управляющему входу блока 9 и управляющему входу 55 блока 8, с выхода 27 блока 19 управления снимается сигнал "Готовность" выходы 28 и 29 блока 19 управления соединены соответственно с вторыми управляющими входами блоков 7 и 9 и управляющим входом блока 3.Блок 19 управления (фиг. 2) содержит двухвходовые элементы И 30 и 31, первые входы которых связаны с выходом 20 второго дешифратора 15, элементы И 32 и 33, к первым входам которых подключен выход 21 второго дешифратора 15, первый триггер 34, вход которого связан с выходом элемента И 30, второй триггер 35, вход которого связан с выходом элемента И 32, элемент ИЛИ 36,.к входам которого подключены выходы элементов И 30 и 32. Вход 22 подключен к элементу 37 задержки, выход которого соединен с вторыми входами элементов И 30 и 32. Выход элемента ИЛИ 36 соединен с входом элемента 38 задержки, выход 29 которого через элемент 39 задержки подключен к вторым входам элементов И 31 и 33. К первому входу элемента И 40 подключен выход триггера 34, к второму - вькод элемента И 31. К первому входу элемента И 4 1 подключен выход триггера 35, к второму . - выход элемента И 31Первый вход элемента И 42 соединен с выходом триггера 35, второй - с выходом элемента И 33, первый вход элемента И 42 в . с выходом триггера 34, второй - с выходом элемента И 33. К входам трехвходового элемента ИПИ 44 подключены выход элемента И 42, выход элемента И 43 и выход 18 элемента ИЛИ 17. К первому входу эле мента ИЛИ 45 подключен выход эле,мента И 4 1, к второму - выход элемента ИЛИ 44.На фиг. 3 приведен один из возможных вариантов построения блока 5 декодирования при и= 8 разрядов (и- длина слов, хранимых в накопителе 1). Блок 5 состоит из двухвходовых сумматоров 45 и 46 по модулю два, к входам которых подключены соответствующие разряды слова с выхода блока 4, удовлетворяющие правилу образования контрольных разрядов для кода Хемминга, исправляющего одну и обнаруживающего две ошибки.Блок 6 коррекции легко выполнить на двухвходовых сумматорах по модулю два (элементы ИСКЛЮЧАЮЩЕЕ ИЛИ), к первым входам которых подключены выходы блока 4, а к вторым - выходы первого дешифратора 14.В накопителе 1 хранится информация, представленная в коде Хемминга, исправляющем одну и обнаруживающем две ошибки. Такой код имеет основные контрольные разряды (ОКР), каждый 5 из которых контролирует по четности свою группу разрядов (группы формируются так, чтобы опрос ОКР указал место ошибки), и один дополнительный контрольный разрез (ДКР), осуществляющий проверку на четность всего слова. Блок 5 декодирования определяет значение ОКР, поступающее свыхода 12 на элемент ИЛИ 13, и значение ДКР на выходе 16. Сигналы с выхода элемента ИЛИ 13 и выхода 16 блока 5 декодирования поступают на дешифратор 15Результат декодирования и работа дешифратора 15 описываются таблицей. ДКР (вы ОКР (выходход 16) элементаИЛИ 13) Значения управляющих сигналов на выходах де- д шифратора 15"2" (выход 20) "1" (выход 21)Э 5 О Если ДКР, О, ОКР = О, то это означает, что декодированное слово не содержит ошибок. Комбинация ДКР = 1, 40 ОКР = О свидетельствует о наличии однократной ошибки в дополнительном (нулевом) контрольном разряде слова либо ошибки нечетной кратности (3,5), таКой, что сумма номеров ошибочных 45 разрядов по модулю два равна нулю.Более вероятен первый случай, поэтому ,с выхода 18 элемента ИЛИ 17 поступает управляющий сигнал "О", как сигнал отсутствия ошибок в слове. В предло женном устройстве при комбинации ДКР = 1 и ОКР = О значение дополнительного контрольного разряда не исправляется, так как предполагается, что он в дальнейших операциях 55 участвовать не будет. Если его необходимо использовать, то второй выход блока 15 кроме того, необходимо подключить к нулевому разряду блока6 коррекции, При ДКР = О и ОКР =на выходе 20 дешифратора 15 появитсяуправляющий сигнал "2", свидетельствующий о том, что слово содержит некорректируемую, но обнаруживаемуюошибку четной кратности (2,4,6).Значение ДКР = 1 и ОКР = 1 означает,что в слове имеется ошибка нечетнойкратности (1,3), и на выходе 21дешифратора 15 появится управляющийсигнал "1",Операция чтения инициируется сигналом "Чтение", поступающим на вход22 блока 19 управления. Информацияс выхода накопителя 1 по сигналу свыхода 23 блока 19 проходит черезблоки 2 и 4, поступает в блок 5декодирования и блок 6 и по сигналус выхода 23 блока 19 записываетсяв регистр 7, Значения основныхконтрольных разрядов, вычисленныев блоке 5 декодирования с выхода12, поступают на дешифратор 14,который в соответствии с принятымкодом инвертирует один иэ разрядовслова (1 - и) в блоке 6 коррекции,если с выхода 12 поступает ненулевойкод. При отсутствии ошибок либопри наличии однократной ошибки в дополнительном контрольном разряде навыходе 18 элемента ИЛИ 1 появляетсясигнал "О", поступающий на третийвход элемента ИЛИ 44 блока 19 управления, с выхода 26 которого выдаетсясигнал в блок 8 элементов И, разрешающий прохождение информации с блока 6 коррекции через блок 10 элементов ИЛИ в числовую магистраль 1 1.Свыхода 27 элемента ИЛИ 45 блока 19выдается сигнал "Готовность". Припоявлении на выходе 21 дешифратора15 управляющего сигнала "1" срабатывает элемент И 32, на второй входкоторого в это время поступает снгнал с выхода элемента 37 задержки,и сигнал1" запоминается в триггере 35.Аналогичным образом управляющий сигнал "2", если имеет местотакой исход декодирования, запоминается в триггере 34.Как в первом так и во втором случае с выхода 28 элемента ИЛИ 36 выдается сигнал, по которому содержимое регистра 7 с его инверсного выхода записывается в ту же ячейкунакопителя, по сигналу с выхода 28информация с блока 6 коррекции зано 7 1152042 8сится в регистр 9 прямого кода, и, где А - дополнительный контрольныйкроме того, он подается на вход эле- раэряд;мента 38 задержки. Затем производит- А -А - основные контрольные разся повторное чтение информации.Сиг- ряды.нал с выхода 29 элемента 38 задержки 5 Каждый из контрольных .разрядовразрешает прохождение информации че- контролирует по четности свою групрез блок 3 инверторов. Вновь считан- пу разрядов (эти разряды подчеркнуное слово через блок 4 поступает на ты). Пусть при обращении к данной .входы блоков 5 и 6. В блоках 5,6,13, ячейки на выходе блока элементов14,15 и 17 производятся те же дей ИЛИ 4 получено словоствия, что и при первом чтении. Еслисчитанное слово ошибок не содержит, 01011100то сигнал с выхода 26 элемента01234567ИЛИ 44 блока 19 разрешает прохождение информации с блока 6 коррекциичерез первый блок 8 элементов И, блок щ д е ошибки Д"пУстимэсодержащее две ошибки,10 элементов ИЛИ в числовую маги- . что в 5-м разряде ошибка вызванастраль 11, а с выхода 27 элемента отказо, а в 6-м разряде - сбоемИЛИ 45 блока 19 выдается сигнал иГо- Считанное слово записывается в репгистр 7; поступает в докиступат в боки 5 и 6чании операции чтения. Если на выходе Первое контРольное соотношение не20 дешифратора 15 появится управ- . выполняется (на выходе 12.1 сумматоляющнй сигнал "2", то сработает Ра 52 по модулю два (фиг. 3) блокаэлемент И 31 на второй вход кото-л равен единице), второе5 сигнал авен е ирого в этот момент поступает сигнал 25 контрольное соотношение не выполняет.с выхода элемента 39 задержки. Если ся на выходе 2.2 сумматора 53 сигв первом цикле чтения исходом деко- нал равен единице),третье контдирования бып сигнал "2", хранимый рольное соотношение выполняется (нав триггере 34, что сработает эле- выходе 12,3 сигнал равен нулю), т.емент И 40 и на вьжоде 24 появитсяУ 30на дешифратор 14 поступает код 011Эсигнал "Ошибка", если же в первоми в блоке 6 коррекции инвертируетцикле результатом дЕкодирования был ся третин РазРяд считанного слова.сигнал "1", то сработает элемент ДополнитеЛьное контрольное соотИ 41 с выхода 25 которого информа- ношение выполняется (сигнал на выция с регистра 9 через второй блок ходе 16 сумматора 56 равен нулю),1 О элементов ИЛИ поступаетв числовую 5 на выходе элемента ИЛИ 17 сигналмагистраль 11, а с выхода 27 элемен- равен единице, т.е. на дешифраторта ИЛИ 45 поступает сигнал готовность". 15 поступает код 01 (см. таблицу).При появлении сигнала "1" на На выходе 20 дешифратора 15 появлявыходе 21 дешифратора 15 срабаты- ется управляющий сигнал "2, срабавает элемент И 33 и либо элемент40тывает элемент И 30 блока 19 , иИ 42 блока 19 либо элемент И 43 (в триггер 34 устанавливается в единичвнсимости от исхода декодирования ное состояние. На выходе элементав первом цикле чтения), и по сиг- ИЛИ 36 появляется единичный сигнал,налу с выхода 26 элемента ИЛИ 44 в соответствии с которым с выходаинформация с выхода блока 6 через45 288 выдаются сигналы управления, сопервый блок 8 элементов И, второй держимое регистра 7 с инверсногоблок 10 элементов ИЛИ поступает в выхода записывается в ту же ячейкучисловую магистраль 11, при этом накопителя 1 и имеет вид 1 О 1 0 0 0 1 1,на выходе 27 элемента ИЛИ 45 появ- а инфоРмация с блока 6 заноситсяляется сигнал готовность". 50 в регистр 9.П р и м е р, Пусть первоначально Затем производится повторноезаписываемая в некоторую ячейку на- читывание слова. Сигнал с выхода 29копителя 1 информация имела вид блока 19 разрешает прохождение ин 01011010Аформации через блок 3 инверторов.о . 55 Считанная информация имеет вид-А, 1 0 1 0 0 1 1 1, а после прохожденияХ через блок 3 - О 1 О 1О О О.з Эта информация поступает в блоки 51152042 10 9 и 6. Яа выходах 12.3 - 12.1 блока 5появляется код 110, который посту-. пает на дешифратор 14, .в блоке 6 инвертируется шестой разряд слова. Сигнал на выходе 16 блока 5 равен 5 единице, на вход дешифратора 15 поступает код 11 и с выхода 21 выдается управляющий сигнал "1". Срабатывает элемент И ЭЗ блока 19, элемент И 43, с выхода 26.элемента ИЛИ 441 О поступает управляющий сигнал, и содержимое блока 6 - О 1 О 1 1 О 1 О через блоки 8 и 10 поступает в числовую магистраль 11. С выхода 27 элемента ИЛИ 45. блока 19 поступает сигнал "Готовность", свидетельствующий об окончании операции чтения. Ошибка кратности два исправлена.Предлагаемое устройство позволяет исправлять ошибки, вызванные отказами, сбоями и их совместным действием. Если ошибки вызваны только отказами, то устройство исправляет 1-, 2- и 3-кратные ошибки.Если ошибки вызваны только сбоями, то устройство исправляет лищь одно,кратную ошибку и обнаруживает двукратную ошибку. При совместном действии отказов и сбоев устройство всегда исправляет двукратную ошибку (одна ошибка вызвана отказом, одна - сбоем) .152042 Составитель О. КулаРедактор В, Данко Техред С,Мигунова орректор М.Самборска Зак е ПППнт", г. Ужгород, ул. Проектная,ил 33/41 ВНИИПИ Госу по делам 113035, Москв