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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСтИЧЕСНИХ

РЕСПУБЛИН

4(51) С 11 С 29/00

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3643564/24 — 24 (22) 27.07.83 (46) 07 02 85. Бюл. № 5 (72) Е.Я.Белалов, И.А.Дичка;

Н.Н.Журавский, А.Г.Забуранный, . В.И.Корнейчук, M.Н.Орлова и Э.В.Рудаков (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (53) 681.327.6 (088.8) (56) 1. Авторское свидетельство СССР № 433542, кл. С 11 С 29/00, 1975.

2. Авторское свидетельство СССР № 443413, кл. С 11 С 29/00, 1975.

3. Хетагуров Я.А., Руднев Ю.П.

Повышение надежности цифровых устройств методами избыточного кодирования. М., 1974, с. 54 (прототип) . (54)(57) 1. ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

С ОБНАРУЖЕНИЕМ И КОРРЕКЦИЕЙ ОШИБОК, содержащее накопитель, блок декодиро вания, блок коррекции, первый и второй элементы ИЛИ, первый дешифратор, причем выход накопителя подключен к первому входу блока коррекции и входу блока декодирования, первый выход которого соединен с входом первого элемента ИЛИ и входом первого дешифратора, первый выход которого подключен к второму входу блока коррекции, о т л и ч а ю щ е е с я тем, что, с целью повышения надежнос ти в работе устройства, в него введены второй дешифратор, блок управления, блоки элементов И и блок контроля, причем выход первого эле,мента ИЛИ и второй выход блока декодирования соединены с входами второ- SU, 1138836 А го дешифратора, один вход блока управления соединен с выходом второго элемента ИЛИ, вход которого подключен к второму выходу первого дешифратора, другие входы блока управ- ления подключены к выходам второго дешифратора, выход блока коррекции соединен с первым входом первого блока элементов И, вход накопителя соединен с первым входом второго блока элементов И, первый выход блока декодирования соЕдинен: с первым входом третьего блока элементов И, выход первого блока элементов И является информационным выходом устройства, выходы второго и третьего блоков элементов И соединены соответственно с первым и вторым входами блока контроля, выход которого является контрольным выходом устройства, первый и второй выходы блока управления подключены соответственно к вторым входам первого и второго блоков элементов И, третий выход блока управления соединен с вторым входом третьего блока элементов" И и третьим входом блока контроля, четвертый вход которого подключен к четвертому выходу блока управления.

2. Устройство по тР. 1, о т л ич а ю щ е е с я тем, что блок управления содержит элементы ИЛИ и элемент И, причем второй вход первого элемента ИЛИ соединен с первыми входами второго и третьего элементов ИЛИ, третий вход первого элемента ИЛИ подключен к вторым входам второго и третьего элементов ИЛИ и к выходу элемента И, второй вход которого сбединен с вторым входом четвертого элемента ИЛИ, выход кото1138836

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

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

r средней степенью интеграции.

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

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

Наиболее близким техническим решением к изобретению явпяется устройство декодирования, содержащее блок 20 декодирования, дешифратор, корректор, элементы ИЛИ и И, причем к входам схемы декодирования и корректора подключен выход накопителя, выход схемы декодирования, связан с входами деши- 25 фратора и первого элемента ИЛИ, выход дешифратора подключен к вторым входам корректора и входам второго элемента ИЛИ, причем выход первого элемента ИЛИ соединен с прямым вхо- 3О дом двухвходового элемента И, а выход второго элемента ИЛИ вЂ” с его инверсным входом f3 ).

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

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

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

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

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

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

На фиг. 1 представлена функциональная схема предлагаемого запоминающего устройства; на фиг. 2 — схема блока управления; на фиг. 3 — один из возможных вариантов блока декодирования.

Запоминающее устройство с обнару- 2д жением и коррекцией ошибок содержит накопитель 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 — к управляющему входу блоIKa 21,.выход 28 — к управляющему

I входу блока 22 h третьему входу бло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 имеет k входов, определяемых из соотношения k=jPog n( где ) а (— ближайшее целое число, не меньше чем d.

1138836 г г

Со е жание

ОКР д р Номер

ДКР (выход 13) (выход 11) выхо-30 да блока 12

Ошибок нет 14

Однократная 15 ошибка

0 в нулевом разряде

Ошибка чет†16 ной кратности

Ошибка нечетной кратности

При чтении информации устройство работает следующим. образом.

Слово, считанное из некоторой ячейки накопителя 1, поступает в бло-55 ки 3 и 4. Блок 3 вычисляет значения

0КР (выход 5) и значение ДКР (выход 13). Дешифратор 12 выдает сигнал.

Элемент ИЛИ 6 имеет 1 входов, элемент ИЛИ 10 (2 -и) входов. Блок 20 состоит из двухвходовых элементов И, к первым входам которых подключены соответствующие выходы блока 4 кор- 5 рекции, а к вторым — выход 26 блока 18 управления. Аналогично построены блоки 21 и 22.

В накопителе 1 хранится информация, представленная в коде Хэмминга, 1О исправляющем одну и обнаруживающем две ошибки. Такой код имеет основные контрольные разряды (ОКР), каждый из которых контролирует по четности свою группу разрядов, и один дополнительный контрольный разряд (ДКР), осуществляющий проверку на четность всего слова. Блок 3 определяет значения ОКР, поступающие с выхода 5 на элемент ИЛИ б,и значение дополнитель- 20 ного контрольного разряда на выходе 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, значения QKP (синдром), которые в данном случае равны нулю, через блок 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 поступает в информационную

1138836 магистраль 25, код адреса заносится в разряды 30 регистра 23, синдром— в разряды 31, а в разряд 32 — признак однократной ошибки. Если же возбуждается один из выходов 9 дешифра- 5 тора 7, то имеет место ошибка кратности 3, 5, ..., на выходе 29 элемента ИЛИ 35 блока 18 появляется сигнал "Ошибка" °

Таким образом, при наличии одно- 10 кратной ошибки в регистр 23 записывается адрес ячейки накопителя 1,код синдрома и признак однократной ошибки. В случае ошибки четной кратности либо обнаруживаемой ошибки нечетной 15 кратности, превышающей единицу, в регистр 23 записывается адрес ячейки и признак многократной ошибки.

Синдром в данном случае не фиксируется, так как 20 место неисправности. Блок 23 используется для хранения информации о неисправностях и их характере. Этот блок может быть выполнен и в виде стека, накапливающего информацию о неисправностях. Содержимое блока 23 ,выводится на выход 24.

Пример. Пусть первоначально записываемая информация в ячейку с адресом 10010110 имела вид 30

1 1 1 1 0 0 1 1 1 1

Ао — А

А

А 35

3 — -- 
4 где Ар — дополнительный контрольный разряд;

А -А — основные контрольные разря4 ды. 40

Каждый из контрольных разрядов контролирует по четности свою группу разрядов (эти разряды подчеркнуты).

Пусть при обращении к данной ячейке на выходе накопителя 1 получено сло- 45 во, поступающее в блоки 3 и 4, 0 1 2 3 4 5 6 7-8 9

1 1 1 1 0 0 1 0 1 1, и содержащее однократную ошибку в седьмом разряде. В блоке 3 вычисляются значения ОКР и ДКР. На выходе 5.1 сумматора 51 получает единичный сигнал — соотношение для А„ не выполнено, на выходах 5.2 и 5.3 сумматоров 48 и 49 тоже получаем едини- 5 цы — соотношения для А и А не вы2 3 полнены, на выходе 5.4 сумматора 45 сигнал равен нулю — соотношение для

А4 выполнено, на выходе 13 сумматора 53 имеем единичный сигнал. Таким образом, значение синдрома равно

$=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 заносится единица — признак однократной ошибки.

Рассмотрим случай трехкратной ошибки. Пусть при чтении получено слово

2. 3 4 5 6 7 8 9

1 0 0 0 1 0 1 О, Обнаружение ошибок кратности 3, 5, ... в предлагаемом устройстве основано на том, что длина h слова, хранимого в накопителе 1, меньше количества ненулевых дешифрируемых комбинаций, т.е. и (2" ., Тогда оставшаяся часть 2 -n выходов пешифратора 7 может быть использова" содержащее ошибки в 3, 7 и 9 разрядах. Значение синдрома, вычисленное ! в блоке 3, равно S=1101, он указывает, что имеет место ошибка в разряде 13, т.е. код синдрома превышает разрядность слова, хранимого в накопителе. В этом случае выход 19 элемента ИЛИ 10 равен единице, так как к блоку 4 подключены только первые десять выходов дешифратора 7, а к входам элемента ИЛИ 10 (для данного примера) подключены остальные

21 -10=6 выходов (с 11 по 16) . Срабатывает элемент ИЛИ 35 и на его выходе 29 появляется сигнал "Ошибка". Таким образом, трехкратная ошибка в слове обнаружена. В разряды 30 регистра 23 записывается адрес ячейки, а в разряд 33 — единица (признак многократной ошибки) .

1138836

lO на для обнаружения части ошибок кратности 3, 5,...

В известном устройстве исправляются однократные ошибки и обнаруживаются ошибки четной кратности. B предлагаемом устройстве, кроме того, обнаруживается часть ошибок нечетной кратности 3, 5, .... Так при п =10 обнаруживается 40 трехкратных оши5 бок, а при n=18 21,5Х.

1138836

Фиг. 2

1138836

Составитель О.Кулаков

Редактор А.Шишкина Техред О.Неце Корректор И.Эрдейи, Заказ 10695/39 . Тираж 584 Подписное

МНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент" r.Óæãoðoä, ул.Проектная, 4