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

рого, подключен к третьему входу вто входы четвертого элемента ИЛИ являрого элемента ИЛИ, первьм и второй ются входами блока управления, выховходы первого элемента ИЛИ, первый дами которого являются выходы элеменвход элемента И, первый и второй тов ИЛИ,

1138836

1. ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С ОБНАРУЖЕНИЕМ И КОРРЕКЦИЕЙ ОИШБОК, содержащее накопитель, блок декодирования, блок коррекции,; первый и второй элементы ИЛИ, первьм дешифратор, причем выход накопителя подключен к первому входу блока коррекции и входу блока декодирования, первый выход которого соединен с входом первого элемента РШИ и входом первого дешифратора, первый выход которого подключен к второму входу блока коррекции, отличающееся тем, что, с целью повьшения надежности в работе устройства, в него введены второй дешифратор, блок управления, блоки элементов И и блок контроля, причем выход первого эле,мента ИЛИ и второй выход блока декодирования соединены с входами второго дешифратора, один вход блока управления соединен с выходом второго элемента ИЛИ, вход которого подключен к втopo fy выходу первого дешифратора, другие входы блока управления подключены к выходам второго дешифратора, выход блока коррекции соединен с первым входом первого блока элементов И, вход накопителя соединен с первым входом второго блока элементов И, первый выход блока декодирования соединен с первым входом третьего блока элементов И, выход первого блока элементов И является информационным выходом устройi ства, выходы второго и третьего блоков элементов И соединены соотW ветственно с первым и вторым входами блока контроля, выход которого является контрольным выходом устройства, первый и второй выходы блока :управления подключены соответственно к вторым входам первого и второго блоков элементов И, третий выход блока управления соединен с вторым 00 00 00 САЭ О) входом третьего блока элемёнтовИ и третьим входом блока контроля, четвертый вход которого подключен к четвертому выходу блока управления. 2. Устройство по iP. 1, о т л ичающееся тем, что блок управления содержит элементы ИЛИ и элемент И, причем второй вход первого элемента ИЛИ соединен с первыми вхо дами второго и третьего элементов ИЛИ, третий вход первого элемента ИЛИ подключен к вторым входам второго и третьего элементов ИЛИ и к выходу элемента И, второй вход которого сбединен с вторым входом четвертого элемента ИЛИ, выход кото

1

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

Известны запоминающие устройства, содержащие накопитель, блоки кодирования и декодирования, дешифратор номера откававщего разряда, блоки элементов И и ИЛИ l3 и L2.

Недостатками этих устройств являются большая избыточность и неправильна коррекция при появлении ошибок, кратность которых превышает кор ректирующую способность применяемого кода о

Наиболее близким техническим решением к изобретению является устройство декодирования, содержащее блок декодирования, дешифратор, корректор элементы ИЛИ и И, причем к входам схемы декодирования и корректора подключен выход накопителя, выход схемы декодирования 1 связан с входами дешифратора и первого элемента ИЛИ, выход дешифратора подключен к вторым входам корректора и входам второго элемента ИЛИ, причем выход первого элемента ИЛИ соединен с прямым входом двуквходового элемента И, а выход второго элемента ИЛИ - с его инверсным входом L3J«

Недостатком известного устройства является .то, что при возникновении ошибок, кратность которых превышает корректирующую способность применяемого помехоустойчивого кода, они исправляются неверно.

Цель изобретения - повьшение надежности в работе устройства«

Поставленная цель достигается тем что в запоминающее устройство с обнаружением и коррекцией ошибок, содержащее накопитель, блок декодирования блок коррекции, первьй и второй элементы ИЛИ, первьш дешифратор, причем выход накопителя подключен к первому входу блока коррекции и входу блока декодирования, первый которого соединен с входом первого элемента ИЛИ и входом первого дешифратора, первьй выход которого подключен к второму входу блока коррекции, введены второй дешифратор, блок управления, блоки элементов И и блок контроля, причем выход первого элемента ИЛИ и второй выход блока декодирования соединены с входами второго дешифратора, один вход блока управления соединен с выходом второго элемента ИЛИ, вход которого подключен к второму выходу первого дешифратора, другие входы блока управления подключены к выходам второго дешифратора, выход блока коррекции соединен с первым входом первого блока элементов И, вход накопителя соединен с первым входом второго блока элементов И, первьй выход блока декодирования соединен с первым входом третьего блока элементов И, въгход первого блока элементов И является информационным выходом устройства, выходы второго и третьего блоков элементов И соединены соответственно с первым и вторым входами блока контроля,выход которого является контрольным выходом устройства, первый и второй выходы блока управления подключены соответственно к в.торым входам первого и второго блоков элементов И, третий выход блока управления соединен с вторым входом третьего блока элементов И и третьим входом блока контроля четвертьй вход которого подключен к четвертому выходу блока управления. При этом блок управления содержит элементы ИЛИ и элемент И причем второй вход первого элемента ИЛИ соединен с первыми входами второго и третьего элементов ИЛИ, третий вход первого элемента ИЛИ подключен к вто рым входам второго и третьего элемен тов ИЛИ и к выходу элемента И, liTopo вход которого соединен и вторым входом четвертого элемента ИЛИ. выход которого подключен к третьему входу второго элемента ИПИ, первый и второй входы первого элемента ИЛИ, первый вход элемента И, первый и второй входы четвертого элемента ИЛИ являют ся входами блока управления, выходами которого являются выходы элементов ИЛИ. На фиг. 1 представлена функциональная схема предлагаемого запоминающего устройства; на фиг. 2 - схем блока управления; на фиг. 3 - один из возможных вариантов блока декодирования . , Запоминающее устройство с обнаружением и коррекцией ошибок содержит накопитель 1 с адресным входом 2, выход которого подключен к входу бло ка 3 декодирования и первому входу блока 4 коррекции. Первый выход 5 блока 3 подключен к входу-первого элемента ИЛИ 6 и входу первого дешифратора 7. Первая часть выходов 8 дешифратора 7 подключена к второму входу блока 4, а вторая часть выходов 9 - к входу второго элемента ИЛИ 10. Выход 11 элемента ИЛЖ 6 подключен к первому входу второго дешифратора 12, а второй выход 13 блока 3 - к второму входу дешифратора 12. Первый 14, второй 15, третий 16 и четвертый 17 выходы дешифра тора 12 подключены к входам блока 18 управления. Выход 19 элемента Ш1И 10 соединен с пятым входом блока 18. К информационному входу первого блока 20 элементов И подключен выход блока 4, к информационному входу вто рого 21 блока элементов И подключен адресньй вход 2 накопителя 1, к -информационному входу третьего блока 2 элементов И - выход 5 блока 3. Выход блЬка 21 подключен к первому входу блока 23 контроля, выход 24 которого является контрольным выходом устройства, выход блока 22 подключен к вто рому входу блока 23, Выход блока 20 соединен с информационной магистралью 25, Выход 26 блока 18 подключен к управляющему: входу блока 20,. выход 27 - к управляющему входу 21,. выход 28 к управляющему входу блока 22 h третьему входу блока 23 контроля, выход 29 - к четвертому входу блока 23. Блок 23 контроля представляет собой регистр, условно разбитый на четьфе части. В первой части 30 записывается адрес ячейки накопителя 1, при чтении информации из которой имеет место ошибка, в разряды 31 записывается значение синдрома, определяемое блоком 3, B разряд 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 подключен к третьему входу элемента , второму входу элемента ИЛИ 37 и второму входу элемента ИЛИ 38. Выход 29 элемента ИЛИ 35 соединен с третьим входом элемента ИЛИ 37. На фиг. 3 приведен один из возможных вариантов построения БДЗ при разрядам ( п- длина слов, хранимых в накопителе 1). Блок состоит из двухвходоБых сумматоров 39 - 53 по модулю два, к входам которых подключены соответствующие разряды слова, удовлетворяющие правилу образования контрольных разрядов Хэмминга, исправляющего одну и обнаруживающего две ошибки. Блок 4 коррекции ожет быть легко выполнен на п элементах ИСКЛЮЧАЮЩЕЕ ИЛИ, первые входы которьк связаны с выходами накопителя 1, а вто-- . рые -СП первыми выходами 8 первого депшфратора 7. Дешифратор 12 представляет собой обычньш дешифратор на два входа. Дешифратор 7 имеет Ч входов, определяемых из соотношения k JPog2n, где at - ближайшее целое число, не меньше чем и, Элемент ИЛИ 6 имеет 1 входов, эле мент ИЛИ 10 (2 -п) входов. Блок 20 состоит из двухвходовых элементов И, к первым входам которых подключены соответствующие выходы блока 4 коррекции s а к вторым - выход 26 блока 18 управления. Аналогично построены блоки 21 и 22. В накопителе 1 хранится информация, представленная в коде Хэмм1-шга, исправляющем одну и обнаруживающем две ошибки. Такой код имеет основные контрольные разряды (ОКР), каждый из которых контролирует по четности свою группу разрядов, и один дополнительный контрольньй разряд (ДКР)s осуп;ествляющий проверку на четность всего слова. Блок 3 определяет з-наче ния ОКР, поступающие с выхода 5 на элемент ИЛИ 6,и значение дополнительного контрольного разряда на вы де 13. Сигналы с выхода элемента ИЛИ 6 и выхода 13 блока пост на дешифратор 12. Результаты де рования и работа дешифратора 12 сываются в таблице. Ошибок нет Однократна ошибка, в нулевом разряде Ошибка чет ной кратностиОшибка нечетнойкратности При чтении информации устрой работает следующим.образом. Слово, считанное из некоторо ячейки накопителя 1, поступает в

ки 3 и 4. Блок 3 вычисляет значения ОКР (выход 5) и значение ДКР (выход 13). Дешифратор 12 вьщает сигнал.

блока 4 через первый блок 20 элементов И по сигналу с выхода 26 элемента ИЛИ 36 поступает в информационную на одном из выходов 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 записываются в разряды 3.1 регистра 23, а в разряд 32 заносится признак однократной ошибки. При появлении сигнала на выходе 16 дешифратора 12 в слове имеется ошибка четной кратности. На выходе 29 элемента ИЛИ 35 появляется сигнал Ошибка, код адреса при этом записывается в разряды 30 регистра 23, а в разряд 33 записывается признак многократной ошибки. Если на выходе 17 дешифратора 12 появляется сигнал, то это свидетельствует о наличии в слове ошибки нечетной кратности. Код ОКР с выхода 5 поступает на вход дешифратора 7 (дешифрирование производится при любом исходе декодирования; дешифратор 7 не дешифрирует нулевой код ОКР). Если при этом возбуждается один из выходов 8, то имеет место однократная ошибка, срабатывает элемент И 34 блока 18, бло-55 скорректированное слово с выхода магистраль 25, код адреса заносится в разряды 30 регистра 23, синдром в разряды 31, а в разряд 32 - признак однократной ошибки. Если же возбуждается один из выходов 9 дешифратора 7, то имеет место ошибка кратности 3, 5, ..., на выходе 29 элемен та ИЛИ 35 блока 18 появляется сигнал Ошибка. Таким образом, при наличии однократной ошибки в регистр 23 записыва ется адрес ячейки накопителя 1,код синдрома и признак однократной ошибки. В случае ошибки четной кратности либо обнаруживаемой ошибки нечетной кратности,превышающей единицу, в регистр 23 записывается адрес ячейки и признак многократной ошибки. Синдром в данном случае не фиксируется, так как невозможно определить, место неисправности. Блок 23 используется для хранения информации о неисправностях и их характере. Этот блок может быть выполнен и в виде стека, накапливающего информацию о неисправностях. Содержимое блока 23 ,выводится на выход 24. Пример. Пусть первоначально записываемая информация в ячейку с адресом 10010110 имела,вид 11110011-11 А, где Ад - дополнительный контрольный разряд; - основные контрольные разряды. Каждьш из контрольных разрядов контролирует по четности свою группу разрядов (эти разряды подчеркнуты). Пусть при обращении к данной ячейке на выходе накопителя 1 получено ело во, поступающее в блоки 3 и 4, 0123456789 1 1 1 10 01 О 1 .1, и содержащее однократную ошибку в седьмом разряде. В блоке 3 вычисляются значения ОКР и ДКР. На выходе 5.1.сумматора 51 получает единич ный сигнал - соотношение для А не выполнено, на выходах 5.2 и 5.3 сум маторов 48 и 49 получаем едини- 55 цы - соотношения для А„ и А, не выполнены, на выходе 5.4 сумматора 45 сигнал равен нулю - соотношение для 68 А выполнено, на выходе 13 сумматора 53 имеем единичный сигнал. Таким образом, значение синдрома равно и . Синдром поступает на элемент ИЛИ 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 заносится единица - признак однократной ошибки. Рассмотрим случай трехкратной ошибки. Пусть при чтении получено слово 012.3456789 1 1 1 О О О 1 д 1 О, содержащее ошибки в 3, 7 и 9 разрядах Значение синдрома, вычисленное B блоке 3, равно , он указывает, что имеет место ошибка в разряде 13, т.е. код синдрома превышает разрядность слова, хранимого в накопителе. В этом случае выход 19 элемента ИЛИ 10 равен единице, так как к блоку 4 подключены только первые десять выходов дешифратора7, а к входам элемента ИЛИ 10 (для данного примера) подключены остальные 2-10 6 выходов (с 11 по 16). Срабатывает элемент ИЛИ 35 и на его выходе 29 появляется сигнал Ошибка. Таким образом, трехкратная ошибка в слове обнаружена. В разряды 30 регистра 23 записывается адрес ячейки, а в разряд 33. - единица (признак многократной ошибки). Обнарзпкение ошибок кратности 3, 5, ... в предлагаемом устройстве основано на том, что длина h слова, хранимого в накопителе 1, меньше количества ненулевых дешифрируемых комбинаций, т.е. и 2. Тогда оставшаяся часть 2 -h выходов дешифратора 7 может быть йспользована для обнаружения части ошибок кратности 3, 5,... .

В известном -устройстве исправляются однократные ошибки и обнаруживаются ошибки четной кратности. Б предлагаемом устройстве, кроме того, обнаруживается часть ошибок нечетной кратности 3, 5, .... Так при п 10 обнаруживается А0% трехкратных ошибок, а при 27,5%.

Фиг. 2