Запоминающее устройство с коррекцией ошибок Советский патент 1985 года по МПК G11C29/00 

11 Изобретение относится к пьмислителыюй технике и может быть использовано в качестве основного и вспомогательного запоминаюпщх устройств в вычислительных системах. Известны запоминающие устройства содержащие накопитель, регистр адреса, блоки кодирования и декодирования, связанные с накопителем, входной и выходной регистры, блок поразрядного сравнения, блоки элементов И и ШШ О и 2. Недостатки этих устройств - избыточность, а также неправильная коррекция при появлении ошибок, кратность которых, превышает корректирующую способность применяемого кода. Известно также запоминающее устройство с коррекцией ошибок, содержа щее накопитель, выход которого подключей к входам регистров прямого и обратного кода, блок обнаружения отказавших разрядов, входы которого соединены с прямыми выходами регистров прямого и обратного кода, корректирующее устройство, вход которог соединен с выходом регистра прямого кода, схему равенства кодов, к входа которых подключены вьгходы блока обнаружения отказавших разрядов и корректирующего устройства, блок управления, входы которого связаны с выходами корректирующего устройства и схемы равенства кодов, а выходы с входами регистров прямого и обратного кодов и блока элементов И, к вторым входам которого подключен выход корректирующего устройства. Выход регистра прямого кода соединен с входом накопителя З. Наиболее близким к изобретению является запоминающее устройство с коррекцией ошибок, содержащее накопитель, выход которого соединен с одним входом блока коррек1щи и входом блока декодирования, один выход которого соединен с входами первого дешифратора и первого элемента ИЛИ, выход которого и другой выход блока декодирования соединены с входами второго дешифратора, выходы которого соединены с блоком управления, выход первого дешифратора - с другим входом блока коррек1дии, выход которого соединен с одним входом элемента И, другой вход которого соединен с выходом блока управления, первые входы других элементов И - соответственно с входом накопителя и выхо22дом блока декодирования, вторые входы - с выходами блока управления, выходы других элементов - с входами регистра прямого кода С . Недостатком известных устройств является ограниченная корректирующая способность при появлении ошибок, вызванных сбоями, а также совместным действием отказов и сбоев. Целью изобретения является повьшение надежности устройства. Поставленная цель достигается тем, что в запоминающее устройство с коррекцией ошибок, содержащее накопитель, блок декодирования, блок коррекции, первый дешифратор, первый элемент ИЛИ, второй дешифратор, первый блок элементов И, регистр прямого кода, блок управления, причем первый выход блока декодирования соединен с входами первого элемента ИЛИ и первого дешифратора, выход которого подключен к одному входу блока коррекции, выход которого соедине-н с одним входом первого блока элементов И, второй выход блока декодирования и выход первого элемента ИЛИ подключены к входам второго дешифратора, одни выходы которого соединены с первым и вторым входами блока управления, третий вход которого является управляющим входом устройства, введены второй блок элементов И, блок инверторов, второй элемент ИЛИ, первый и второй блоки элементов ИЛИ, регистр инверсного кода, причем выход накопителя соединен с одними входами второго блока элементов И и блока инверторов, выходы которых подключены к входам первого блока элементов ИЛИ,выход которого соединен с входом блока декодирования, другим входом блока коррекции и одним входом регистра инверсного кода, выход которого подключен к входу накопителя, выход блока коррекции соединен с одним входом регистра прямого кода, вькод которого и выход первого блока элементов И подключены к входам второго блока элементов ИЛИ, выход которого является информационным выходом устройства, другие выходы второго дешифратора соединены с входами вторО1о элемента ИЛИ, выход которог-о подключен к четвертому входу блока управления, первый и шестой выходы которого соединены с друг-ими РХОдами регистра инверсн(лч) каля, пругие входы регистра прямого кода подключены к третьему и шестому выходам блока управления, первый четвертый и седьмой выходы которого соединены соответственно с другими входами второго блока элементов И, первого блока элементов И и блока инверторов, второй и пятый выходы блока управления являются индикаторными выходами устройства. На фиг. 1 приведена блок-схема устройства; на фиг. 2 - схема блока управления; на фиг.З - один из вари антов блока декодирования. Устройство содержит накопитель 1 вькод которого подключен к первым входам второго блока 2 элементов И и блока 3 инверторов, выходы блоков 2 и 3 соединены е входами первого блока 4 элементов ИЛИ, выход которо подключен к входу блока 5 декодирования одним входом, блока 6 коррекции и регистра 7 инверсного кода, выход которого соединен с входом на копителя 1. Выход блока 6 коррекции связан с одними входами первого бло ка 8 элементов И и регистра 9 прямо го кода, выходы которых через второ блок 10 элементов ИЛИ соединены с ч ловой магистралью 1t. Информационные выходы 12 блбка 5 подключены к входам первого элемента ИЛИ 13 и пе вого дешифратора 14, выход которого соединен с другим входом блока 6 коррекции. К первому входу второго дешифратора 15 подключен выход первого элемента ИЛИ 13, к второму управляющий выход 16 блока 5. Первый и второй выходы блока 15 соединены с входами второго элемента ИЛИ 17, выход 18 которого подключен к одному из входов блока 19 управления. Третий выход 20 и четвертый выход 21 блока 15 подключены к входам блока 19. На вход 22 блока 1.9 поступает сигнал Чтение с центрального устройства управления. Выход 23 блока 19 управления подклю чен к первому управлякяцему входу блока 7 и к управляющему входу блока 2, с выхода 24 блока 19 вьщается сигнал Ошибка, выходы 25 и 26 блока 19 управления подключены соответственно к первому управляющему входу блока 9 и управляющему входу блока 8, с выхода 27 блока 19 управления снимается сигнал Готовность вькоды 28 и 29 блока 19 управления 24 соединены соответственно с вторыми управляюп ими входами блоков 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 . К первому входу элемента И 41 подключен выход триггера 35, к второму - выход элемента И 31. Первый вход элемента И 42 соединен с выходом триггера 35, второй - с выходом элемента И 33, первый вход элемента И 42 - с выходом триггера 34, второй - с выходом элемента И 33. К входам трехвходового элемента ИЛИ 44 подключены выход элемента И 42, выход элемента И 43 и выход 18 элемента ИЛИ 17. К первому входу элемента ИЛИ 43 подключен выход элемента И 41, к второму - выход элемента ИЛИ 44. На фиг. 3 приведен один из возможных вариантов построения блока 5 декодирования при м 8 разрядов ( г - длина слов, храни «1х в накопителе 1) . Блок 5 состоит из двухвходовьк сумматоров 45 и 46 по модулю два, к входам которых подключены соответствующие разряды слова с выхода блока 4, удовлетворяющие правилу образова контрольных разрядов для кода Хемминга, исправляющего одну и обнаруживающего две ошибки. Блок 6 коррекции выполнить на двухвходовых сумматорах по модулю два (элементы ИСКЛКНАКЯЦЕЕ ИЛИ) , , к первым входам которых подключены выходы блока 4, а к вторым - выходы первого дешифратора 14. в накопителе 1 хранится информация, представленная в коде Хемминга исправляющем одну и обнаруживающем две ошибки. Такой код имеет основные контрольные разряды (ОКР), кажд из которых контролирует по четности свою группу разрядов (группы формируются так, чтобы опрос ОКР указал место ошибки), и один дополнительны контрольный разрез (ДКР), осуществляющий проверку на четность всего слова. Блок 5 декодирования определ ет значение ОКР, поступающее с выхода 12 на элемент ИЛИ 1., и значение ДКР на выходе 16. Сигналы с выхода элемен -а ИЛИ 13 и выхода 16 блока 5 декодирования поступают на 15. Результат декодирования и работа дешифратора 15 описываются таблицей. Если ДКР О, ОКР О, то это оз начает, что декодированное слово не содержит ошибок. Комбинация ДКР 1 ОКР О свидетельствует о наличии однократной ошибки в дополнительном (нулевом) контрольном разряде слова либо ошибки нечетной кратности (3,5.. татсой, что сумма номеров ошибочных разрядов по модулю два равна нулю. Более вероятен первый случай,поэтом ,с выхода 18 элемента ИЛИ 17 поступае управляющий сигнал О, как сигнал отсутствия ошибок в слове. В предло- SO

женном устройстве при комбинации ДКР 1 и ОКР О значение дополнительного контрольного разряда не исправляется, так как предполагается, что он в дальнейших операцй ях участвовать не будет. Если его необходимо использовать, то второй выход блока 15jкроме того, необходимо подется в триггере 34.

Как в первом так и во втором случае с выхода 28 элемента ИЖ 36 выдается сигнал, по которому содержимое регистра 7 с его инверсного выхода записывается в ту же ячейку накопителя, по сигналу с рькода 28 информация с блока 6 KoppeKij iH зано26ключить к нулевому разряду блока 6 коррекции. При ДКР О и ОКР 1 на выходе 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 элемента ИЛИ 17 появляется сигнал О, поступаюпщй на третий вход элемента ИЛИ 44 блока 19 управления, с выхода 26 которого вьщается сигнал в блок 8 элементов И, разрешаюш;ий прохождение информации с блока 6 коррекции через блок 10 элементов ИЛИ в числовую магистраль 1 1 .С выхода 27 элемента ИЛИ 45 блока 19 вьщается сигнал Готовность. При появлении на выходе 21 дешифратора 15 управляющего сигнала 1 срабатывает элемент И 32, на второй вход которого в это время поступает сигнал с выхода элемента 37 задержки, и сигнал 1 запоминается в триггере 35.Аналогичным образом управляющий сигнал 2, если имеет место такой исход декодирования,запоминасится в регистр 9 прямого кода, и, кроме того, он подается на вход эле мента 38 задержки. Затем производит ся повторное чтение информации.Сигнал с выхода 29 элемента 38 задержк разрешает прохождение информации че рез блок 3 инверторов. Вновь считан ное слово через блок 4 поступает на входы блоков 5 и 6. В блоках 5,6,13 t4,15 и 17 производятся те же дей1ствия, что и при первом чтении.Если считанное слово ошибок не содержит, то сигнал с выхода 26 элемента ИЛИ 44 блока 19 разрешает прохождение информации с блока 6 коррекции через первый блок 8 элементов И, бл 10 элементов HJHi в числовую магистраль 11, ас выхода 27 элемента ШШ 45 блока 19 вьщается сигнал Го товность, свидетельствующий об око чании операции чтения. Если на выход 20 дешифратора 15 появится управляющий сигнал 2, то сработает элемент И 31,, на второй вход которого в этот момент поступает сигнал с выхода элемента 39 задержки. Если в первом цикле чтения исходом декодирования был сигнал 2, хранимый в триггере 34, что сработает элемент И 40, и на выходе 24 появится сигнал Ошибка, если же в первом цикле результатом декодирования был сигнал 1, то сработает элемент И 41, с выхода 25 которого информация с регистра 9 через второй блок 10 элементов ИЛИ поступает в числовую магистраль 11, а с выхода 27 элемен та Ида45 поступает сигнал Готовность При появлении сигнала 1 на выходе 21 деашфратрра 15 срабатывает элемент И 33 и либо элемент И 42 блока 19 либо элемент И 43 (в зависимости от исхода декодирования в первом цикле чтения), и по сигналу с выхода 26 элемента ИЛИ 44 информация с выхода блока 6 через первьй блок 8 элементов И, второй блок 10 элементов ИЛИ поступает в числовую магистраль 11, при этом на выходе 27 элемента ИЛИ 45 появляется сигнал Готовность. Пример. Пусть первоначально записьшаемая в некоторую ячейку накопителя 1 информация имела вид 01011010, 42 Ад - дополнительней контрольный разряд; основные контрольные разряды. Каждый из контрольных разрядов контролирует по четности свою группу разрядов (эти разряды подчеркнуты) . Пусть при обращении к данной ячейки на выходе блока элементов ИЛИ 4 получено слово содержащее две ошибки. Допустим, что в 5-м разряде ошибка вызвана отказом, а в 6-м разряде - сбоем. Считанное слово записывается в регистр 7, поступает в блоки 5 и 6. Первое контрольное соотношение не выполняется (на выходе 12.1 суммато ра 52 по модулю два (фиг. 3) блока 5 сигнал равен единице), второе контрольное соотношение не выполняется (на выходе 12.2 сумматора 53 сигнал равен единице), третье конт- рольное соотношение вьтолняется (на выходе 12.3 сигнал равен нулю), т.е. на дешифратор 14 поступает код 011, и в блоке 6 коррекции инвертируется третий разряд считанного слова. Дополнительное контрольное соотношение выполняется (сигнал на выходе 16 сумматора 56 равен нулю) , на выходе элемента ИЛИ 17 сигнал равен единице, т.е. на дешифратор 15 поступает код 01 (см. таблицу). На выходе 20 дешифратора 15 появляется управляющий сигнал 2, срабатывает элемент И 30 блока 19 , и триггер 34 устанавливается в единичное состояние. На выходе элемента ИЛИ 36 появляется единичньй сигнал, в соответствии с которым с выхода 28 вьщаются сигналы управления, содержимое регистра 7 с инверсного выхода записывается в ту же ячейку накопителя 1 и имеет вид 10100011, а информация с блока 6 заносится в регистр 9. Затем производится повторное читывание слова. Сигнал с выхода 29 лока 19 разрешает прохождение инормации через блок 3 инверторов. читанная информация имеет вид 10100|1 1,а после прохождения ерез блок 3-01011000. та информация поступает в блоки 5

. 9 i1

и 6. На выходах 12.3 - 12.1 блока 5 появляется код 110, который поступает на дешифратор 14, в блоке 6 инвертируется шестой разряд слова. Сигнал на выходе 16 блока 5 равен единице, на вход дешифратора 15- поступает код 11 и с выхода 21 вьщает ся управляющий сигнал 1. Срабатывает элемент И 33 блока 19, элемент И 43, с выхода 26 элемента ИЛИ 44 поступает управляющий сигнал, и содержимое блока 6-0101 101 через блоки 8 и 10 поступает в числовую магистраль 11. С выхода 27 элемента ИЛИ 45 блока 19 поступает сигнал Готовность, свидетельствую

210

щий об окончании операции чтения.

Ошибка кратности два исправлена.

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

действии отказов и сбоев устройство всегда исправляет двукратную ошибку (одна ошибка вызвана отказом, одна сбоем).

ЗАПОМИНАВДЕЕ УСТРОЙСТВО С КОРРЕШЩЕЙ ШИБОК, содержащее накопитель, блок декодирования, блок коррекции, первый дешифратор, первый элемент ИЛИ, второй дешифратор, первый блок элементов. И, регистр прямого кода, блок управления, причем первый выход блока декодирования соединен с входами первого элемента ИЛИ и первого дешифратора,выход которого подключен к одному входу блока коррекции, выход которого соединен с одним входом первого блока элементов И, второй выход блока декодирования и выход первого элемента .ИЛИ подключены к входам второго дешифратора, одни выходы которого соединены с первым и вторым входами блока управления, третий вход котороГо является управляющим входом устройства, отличающееся тем, что, с целью повышения надежности устройства, в него введены второй блок элементов И, блок инверторов, второй элемент ИЛИ, первый и второй блоки элементов ИЛИ, регистр инверсного кода, причем выход накопителя соединен с одними входами второго блока элементов И и блока инверторов, выходы которых подключены к входам первого блока элементов ИЛИ, выход которого соединен с входом блока декодирования, другим входом блока коррекции и одним входом регистра инверсного кода, выход которого подключен к входу накопителя, выход блока коррекции соединен с одним входом регистра прямого Л кода, выход которого и выход первого С блока элементов И подключены к входам второго блока элементов ИЛИ, выход которого является информационным выходом устройства, другие выходы второго дешифратора соединены с входами второго элемента ИЛИ, выход которого подключен к четвертому входу блока управления, первый и шестой выходы которого соединены с другими входами регистра инверсного кода, другие входы регистра прямого кода подключены к третьему и шестому выходам блока управления, первый, четвертый и седьмой выходы которого соединены соответственно с другими входами второго блока элментов И, первого блока элементов И и блока инверторов, второй и пятый выходы блока управления являются индикаторными выходами устройства.

( 1 I

i

Фиг. г