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

 

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

СОЮЗ СО8ЕТСНИХ

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

РЕСПУБЛИК

4(5!1 С 11 С 29/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К AST0PCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3659434/24-24 (22) 05.11.83 (46) 23.04.85. Вюл. И- 15 (72) И.А. Дичка, В.И. Корнейчук, Ю.Б. Рычагов, В.В. Садовский и А.А. Юрасов (53) 681.327(088.8) (56) 1. Авторское свидетельство СССР

У 433542, кл. G 11 С 29/00, 1974.

2. Авторское свидетельство СССР

У 443413, кл. С 11 С 29/00, 1974.

3. Авторское свидетельство СССР

9 855730, кл. G 11 С 11/00, 1984.

4. Авторское свидетельство СССР по эаявке У 3643564, кл. С 11 С 29/00, 05.11.83 (прототип). (54)(57) ЗАПОИИНАЮП1ЕЕ УСТРОЙСТВО С

КОРРЕКЦИЕЙ ОШИБОК, содержащее накопитель, блок декодирования, блок коррекции, первый дешифратор, первый элемент ИЛИ, второй дешифратор, первый блок элементов. И, регистр прямого кода, блок управления, причем первый выход блока декодирования соединен с входами первого элемен.Ъ та ИЛИ и первого дешифратора,выход которого. подключен к одному входу блока коррекции, выход которого соединен с одним входом первого блока элементов И, второй выход блока декодирования и выход первого элемента, ИЛИ подключены к входам второго дешифратора, одни выходы которого соединены с первым и вторым входами блока управления, третий вход кото рого является управляющим входом устройства, о т л и ч а ю щ е е с я

ÄÄSUÄÄ 1152042 A тем, что, с целью повьппения надежйости устройства, в него введены второй блок элементов И, блок инверторов, второй элемент ИЛИ, первый и второй блоки элементов ИЛИ, регистр инверсного кода, причем выход накопителя соединен с одними входами второго блока элементов И и блока инверторов, выходы которых подключены к входам первого блока элементов ИЛИ, выход которого соединен с входом блока декодирования, другим входом блока коррекции и одним входом регистра инверсного кода, выход которого подключен к входу накопителя, выход блока коррекции соеди- Б нен с одним входом регистра прямого кода, выход которого и выход первого блока элементов И подключены к входам второго блока элементов ИЛИ, выход которого является информационным выходом устройства, другие выходы второго дешифратора соединены с входами второго элемента ИЛИ, выход которого подключен к четвертому входу блока управления, первый и шестой выходы которого соединены с други ми входами регистра инверсного кода, t

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

115204

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

Известны запоминающие устройства, содержащие накопитель, регистр адреса, блоки кодирования и декодирования, связанные с накопителем, входной и выходной регистры, блок пораз- 1ð рядного сравнения, блоки элс.ментов И и HJIH (11 и (21.

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

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

Выход регистра прямого кода соединен с входом накопителя (3f.

Наиболее близким к изобретению является запоминающее устройство с коррекцией ошибок, содержащее накопитель, выход которого соединен с одним входом блока коррекции и вхо- 4 дом блока декодирования, один выход которого соединен с входами первого дешифратора и первого элемента ИЛИ, выход которого и другой выход блока декодирования соединены с входами второго дешифратора, выходы которого соединены с блоком управления, выход первого цешифратора — с другим входом блока коррекции, выход которого соединен с одним входом элемен55 та И, другой вход которого соединен с выходом блока управления, первые входы других элементов И вЂ” с оответственно с входом накопителя и выхо2 2 дом блока декодирования, вторые входы — с выходами блока управления, выхоцы других элементов — с входами регистра прямого кода 4 ).

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

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

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

ИЛИ и первого дешифратора, выход которого подключен к одному входу блока коррекции, выход которого соединен с одним входом первого блока элементов И, второй выход блока декодирования и выход первого элемента ИЛИ подключены к входам второго дешифратора, одни выходы которого соединены с первым и вторым входами блока управления, третий вход которого является управляющим входом устройства, введены второй блок элементов И, блок инверторов, второй элемент ИЛИ, первый и второй блоки эле— ментов ИЛИ, регистр инверсного кода, причем выход накопителя соединен с одними входами второго блока элементов И и блока инверторов, выходы которых подключены к входам первого блока элементов ИЛИ,выход которого соединен с входом блока декодирования, другим входом блока коррекции и одним входом регистра инверсного кода, выход которого подключен к входу накопителя, выход блока коррекции соединен с одним входом регистра прямого кода, выход которого и выход первого блока элементов И подключены к входам второго блока элементов ИЛИ, выход которого является информационным вь ходом устройства, другие выходы второго дешифратора соединены с входами второго элемента HJIH, выход которого подключен к четвертому входу блока управления, первый и шестой выходы которого соединены с другими гходами регистра инверсного код», дру1152042

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

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

Устройство содержит накопитель 1, 15 выход которого подключен к первым входам второго блока 2 элементов И

Г и блока 3 инверторов, выходы блоков

2 и 3 соединены с входами первого блока 4 элементов ИЛИ, выход которого20 подключен к входу блока 5 декодирования одним входом, блока 6 коррекции и регистра 7 инверсного кода, выход которого соединен с входом накопителя 1. Выход блока 6 коррекции 25 связан с одними входами первого блока 8 элементов И и регистра 9 прямого кода, выходы которых через второй блок 10 элементов ИЛИ соединены с числовой магистралью 11. Информацион- 30 ные выходы 12 блока 5 подключены к входам первого элемента ИЛИ 13 и первого дешифратора 14, выход которого соединен с другим входом блока 6 коррекции. К первому входу второго дешифратора 15 подключен выход первого элемента ИЛИ 13, к второму— управляющий выход 16 блока 5. Первый и второй выходы блока 15 соединены с входами второго элемента ИЛИ 4О

17, выход 18 которого подключен к одному из входов блока 19 управления. Третий выход 20 и четвертый выход 21 блока 15 подключены„к входам блока 19. На вход 22 блока 19 45 поступает сигнал "Чтение" с центрального устройства управления.

Выход 23 блока 19 управления подключен к первому управляющему входу блока 7 и к управляющему входу блока gg

2, с выхода 24 блока 19 выдается сигнал "Ошибка", выходы 25 и 26 блока 19 управления подключены соответственно к первому управляющему входу блока 9 и управляющему входу 55 блока 8, с выхода 27 блока 19 управления снимается сигнал "Готовность"

i выходы 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 приведен один из sosMoaных вариантов построения блока 5 декодирования при n = 8 разрядов (идлина слов, хранимых в накопителе 1) .

Блок 5 состоит из двухвходовых сумматоров 45 и 46 по модулю два, к входам которых подключены соответствующие разряды слова с выхода блока

4, удовлетворяющие правилу образования контрольных разрядов для кода

Хемминга, исправляющего одну и обнаруживающего две ошибки.

Блок 6 коррекции легко выполнить на двухвходовых сумматорах по модулю два (элементы ИСКЛЮЧАЮЩЕЕ ИЛИ), к первым входам которых подключены выходы блока 4, а к вторым — выходы первого дешифратора 14.

1152042

В накопителе 1 хранится информация, представленная в коде Хемминга, исправляющем одну и обнаруживающем две ошибки. Такой код имеет основные контрольные разряды (ОКР), каждый 5 из которых контролирует по четности свою группу разрядов (группы формируются так, чтобы опрос OKP указал место ошибки), и один дополнительный контрольный разрез (ДКР), осуществляющий проверку на четность всего слова. Блок 5 декодирования определяет значение ОКР, поступающее с выхода 12 на элемент ИЛИ 13, и значение ДКР на выходе 16. Сигналы с выхода элемента ИЛИ 13 и выхода 16 блока 5 декодирования поступают на дешифратор 15 ° Результат декодирования и работа дешифратора 15 описываются таблицей.

ДКР (вы» ОКР (выход ход 16) элемента

ИЛИ 13) Значения управляющих сигналов на выходах дешифратора 15

"О" (выход 18 элемента ИЛИ 17)

"2" (выход 20)

"1" (выход 21)

О

Если ДКР, О, ОКР = О, то это означает, что декодированное слово не содержит ошибок. Комбинация ДКР = 1, 40

ОКР = О свидетельствует о наличии однократной ошибки в дополнительном (нулевом) контрольном разряде слова либо ошибки нечетной кратности (3,5 .. ° ), такой, что сумма номеров ошибочных 45 разрядов по модулю два равна нулю.

Более вероятен первый случай, поэтому ,с выхода 18 элемента. ИЛИ 17 поступает управляющий сигнал "О", как сигнал отсутствия ошибок в слове. В предло- SO женном устройстве при комбинации

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

6 коррекции. При ДКР = О и ОКР на выходе 20 дешифратора 15 появится управляющий сигнал "2", свидетельствующий о том, что слово содержит не корректируемую, но обнаруживаемую ошибку четной кратности (2,4,6...).

Значение ДКР = 1 и OKP = 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, на второй вход которого в это время поступает снг1 нал с выхода элемента 37 задержки, и сигнал 1" запоминается в тригге:ре 35.Аналогичным образом управляющий сигнал "2", если имеет место такой исход декодирования, запоминается в триггере 34.

Как в первом так и во втором случае с выхода 28 элемента ИЛИ 36 выдается сигнал, по которому содержимое регистра 7 с его инверсного выхода записывается в ту же ячейку накопителя, по сигналу с выхода 28 информация с блока 6 коррекции зано7 1152042 8 сится в регистр 9 прямого кода, и, где А — дополнительный контрольный кроме того, он подается на вход эле- разряд;

f мента 38 задержки. Затем производит- А -А — основные контрольные разся повторное чтение информации.Сиг- ряды. нал с выхода 29 элемента 38 задержки 5 Каждый из контрольных .Разрядов разрешает прохождение информации че- контролирует по четности свою групрез блок 3 инверторов. Вновь считан- пу разрядов (эти разряды подчеркнуное слово через блок 4 поступает на ты). Пусть при обращении к даннойвходы блоков 5 и 6. В блоках 5,6,13, ячейки на выходе блока элементов

14,15 и 17 производятся те же дей- 10 ИЛИ 4 получено слово ствия, что и при первом чтении. Если считанное слово ошибок не содержит, 01011100 то сигнал с выхода 26 элемента

01234567

ИЛИ 44 блока 19 разрешает прохождение информации с блока 6 коррекции через первый блок 8 элементов H блок x e OIHG H ° Допустим, содержащее две ошибки.

i0 элементов КПН в числовую маги- о в 5-м Разряде ошибка вызвана страль 11, а с выхода 27 элемента

HJIH 45 блока 19 выдается сигнал "Го- Считанное слово записываетсЯ в Petl гистр 7; поступает в локи товность, свидетельствующий об окон-рр чании операции чтения. Если на выходе выполняется (на выходе 12.1 суммато ра 52 по модулю два (фиг. 3) блока элемент И 31, на второй вход кото5 сигнал авен е и контрольное соотношение не выполняется (на вь оде 12. 2 сумматора 53 сигв первом кле чтения исходом деко- нал равен единице), третье контдирования бып сигнал "2", хранимый рольное соотношение выполняется (на в триггере 34, что сработает эле-. выходе 12.3 сигнал равен нулю), т.е-. мент И 40 и на выходе 24 появится

У 30 на дешифратор 14 поступает код 011

Э сигнал "Ошибка", если же в первом и в блоке 6 коррекции инвертируетцикле результатом декодирования был сЯ третий РазРЯд считанного слова. сигнал "1", то сработает элемент ДополнитеЛьное контрольное соотИ 4 1 Ib0I oдa 25 Ko1 opoг о HHфopMа ношение вь олняе ся (си нал на в9 чepea aтopои gлок ходе 16 с ма ора 56 равеi нулю), 10 элементов ИЛИ поступает в числовую Э5 на выходе элемента ИЛИ 17 сигнал ги р 11, а с выхода 27 элемен- Равен единице, т.е. Hà дешифратор та HJ5f45 поступает сигнал "1"отовность". 15 постУпает коц 01 (см. таблицУ).

При появлении сигнала "1" на На выходе 20 дешифратора 15 появлявыходе 21 деш,фратора 15 срабаты- ется управляющий сигнал "2, срабавает элемент И 33 и либо элемент

40 тывает элемент И 30 блока 19, и

И 42 блока 19 либо элемент И 43 (в триггер 34 устанавливается в единичзависимости от исхода декодирования ное состояние. На выходе элемента в первом цикле чтения), и по сиг- ИЛИ 36 появляется единичный сигнал, налу с выхода 26 элемента ИЛИ 44 в соответствии с которым с выхода информация с выхода блока 6 через

45 28

8 выдаются сигналы управления, сопервый блок 8 элементов И, второй держимое регистра 7 с инверсного блок 10 элементов ИЛИ поступает в выхода записывается в ту же ячеику числовую магистраль 11, при этом накопителя 1 и имеет вид 1 О 1 0 О 0 1 1, на выходе 27 элемента ИЛИ 45 появ- «нфоРмациЯ с блока 6 заноситсЯ ляется сигнал I oTQBHocTb в регистр 9.

Пример. Пусть первоначально Затем производится повторное

3aBHcb aeMaH в HeKoTopylo ячейку На- считывание слова. Сигнал с вьжода 29 лока 19 разрешает прохождение ин01011010

A формации через блок 3 инверторов. о . 55 Считанная информация имеет вид

-А, . 1 О 1 0 0 1 1 1, а после прохождения

1 черезблок3-01011000. з Эта информация поступает в блоки 5

1152042

9 и 6. Яа выходах 12.3 — 12.1 блока 5 появляется код 110, который посту-. пает на дешифратор 14, .в блоке 6 инвертируется шестой разряд слова.

Сигнал на выходе 16 блока 5 равен единице, на вход дешифратора 15 поступает код 11 и с выхода 21 выдается управляющий сигнал "1". Срабатывает элемент И 33 блока 19, элемент

И 43, с выхода 26.элемента ИЛИ 44

10 поступает управляющий сигнал, и содержимое блока 6 — 0 1 0 1 1 0 1 0 через блоки 8 и 10 поступает в числовую магистраль 11. С выхода 27 элемента ИЛИ 45. блока 19 поступает сигнал "Готовность", свидетельствующии об окончании операции чтения.

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

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

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

1152042

<Риг. Р!

152042

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

Техред С.Мигунова Корректор М.Самборская

Редактор В. Данко филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

Заказ 2333/41 Тираж 584 Подписное

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

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