Устройство для обнаружения и исправления ошибок в непозиционном коде

 

УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНА ОШИБОК В НЕПОЗИЦИОННОМ КОДЕ, содержащее К +2 входнык регистров , где Х- число информационных .оснований, и две группы сумматоров коррекции, при этом входы входных регистров являются информационными входами устройства, первые входы сумматоров коррекции первой и второй групп соответственно объединены, вторые входы сумматоров коррекции первой группы объединены, вторые входы сумматоров коррекции второй группы объединены, отличающееся тем, что, с целью повышения быстродействия , в устройство введены дешифратор , К +2 элементов задержки , два блока суммирования вычетов, первая и вторая группы вспомогательных регистров , трехразрядньй регистр, К элементов И, группы мультиплексоров, К +2 выходных регистров и элемент И,причем выходы К+2 входных регистров подключены к входам К+2 элементов задержки соответственно и к соответствующим входам первогои второго блоков суммирования вычетов, первые выходы И +2 элементов задержки подключены соответственно к первым входам сумматоров коррекции первой и второй групп, к вторым входам которых подключены выходы соответственно второго и первого блоков суммирования вычетов, подключенные также к входам дешифратора, первый, второй и третий выходы которого через трехразрядньй регистр соединены соответственно с первыми входами мультиплексоров (К+1)-й и (К+2)-и групп и (К+1)-м входам элемента И, группа входов которого подключена к выходам К элементов И и к первым входам мультиплексоров К групп, вторые входы которых соединены с первыми входами К элементов И и с выходами К вспомогательных регистров второй группы, а третьи входы - с вторыми входами К элементов задержки, вторые выходы (К+1)-го и (К+2)-го элементов задержки соединены с вторыми входами мультиплексоров (К+1)-й и (К+2)-и групп, СО 4 СО 4ii третьи входы которых соединены с выходами (К+1)-го и (К+2)-го регистров первой группы, выход / -го (i 1-К) iвспомогательного регистра первой группы подключен к второму входу -i-ro элемента И, выходы мультиплексоров К+2 групп подключены соответственно к входам К+2 выходных регис тров, выходы которых являются информационными выходами устройства, выход элемента И является выходом отказа от декодирования устройства, выходы сумматоров коррекции первой и второй групп подключены.соответственно к входам вспомогательных регистров первой и второй групп.

СОЮЗ СоаЕТСНИХ

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

РЕСПУБЛИК (19) (11) 4(51) G,06 F 11/08

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ » »>. :;:,.,»

{21) 3627737/24-24

{22) 27.07.83 (46) 15,01 85. Бюл. Р 2 (72) А.А.Коляда

171) Научно-исследовательский инстиЕут прикладных физических проблем им.акад.А.Н.Севченко

{53) 681.3(088.8)

{56) 1. Авторское свидетельство СССР ф» 714399, кл. G 06 F 11/08, 1980.

2. Журавлев Н:.П., Котелюк Л.А. надежность и контроль ЭВМ. M., "Сов. радио", 1978, с. 137 (прототип).

154)(57) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ

К ИСПРАВЛЕНИЯ ОШИБОК В НЕПОЗИЦИОННОМ

КОДЕ, содержащее V +2 входных регистрОв, где .К- число информационных .оснований, и две группы сумматоров коррекции, при этом входы входных регистров являются информационными

Входами устройства, первые входы сумматоров коррекции первой и второй групп соответственно объединены, вторые входы сумматоров коррекции перВой группы объединены, вторые входы сумматоров коррекции второй группы объединены, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены дешифратор,»(+2 элементов задержки; два блока суммирования вычетов, первая и

Вторая группы вспомогательных регистров, трехразрядный регистр, К элементов И, группы мультиплексоров,,К +2 выходных регистров и элемент И,причем выходы К+2 входных регистров подключены к входам К+2 элементов задержки соответственно и к соответствующим входам первого и второго блоков суьс»ирования вьиетов, первые выходы К +2 элементов задержки подключены соответственно к первым входам сумматоров коррекции первой и второй групп, к вторым входам которых подключены выходы соответственно второго и первого блоков суммирования вычетов, подключенные также к входам дешифратора, первый, второй и третий выходы которого через трехразрядный регистр соединены соответственно с первыми входами мультиплексоров (К+1)-й и (К+2)-й групп и (К+1).-м входам элемента И, группа входов которого подключена к выходам

К элементов И и к первым входам мультиплексоров К групп, вторые входы которых соединены с первыми входами

К элементов И и с выходами К вспомогательных регистров второй группы, а третьи входы — с вторыми входами

К элементов задержки, вторые выходы (К+1)-го и (К+2)-го элементов задержt ки соединены с вторыми входами мультиплексоров (К+1)-й и (К+2)-й групп, третьи входы которых соединены с выходами (К+1)-го и (K+2)-ro регистров первой группы, выход » -ro (1=1-»() вспомогательного регистра первой груп пы подключен к второму входу w-ro элемента И, выходы мультиплексоров

К+2 групп подключены соответственно к входам »(+2 выходных регистров, вы. ходы которых являются информационными выходами устройства, выход элемен та И является выходом отказа от декодирования устройства, выходы сумма торов коррекции первой и второй групп подключены соответственно к входам вспомогательных регистров первой и второй групп.

1134941

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

Известно устройство для обнаружения и исправления ошибок в непозиционном коде, содержащее входной регистр, входы которого являются входа- 10 ми устройства, блок свертки по контрольным модулям, входь. которого подключены к первому выходу входного регистра, сумматоры по контрольным модулям, по входам подключенные к 15 второму и третьему выходам входнОго регистра и выходам блока модульной свертки по контрольным модулям, блок памяти ошибок, входы которого соединены с выходами сумматоров по конт- щ . Рольным основаниям, и блок сумматоров коррекции по модулям непозиционной системы счисления, первый вход которого подключен к выходу блока памяти ошибок, второй, третий и четвертый 25 входы — соответственно к первому, e""орому и третьему выходам входного ье гФстра, а выход является выходом

1 у стройства, которое при соответствующей структуре блока модульной сверткиз0 по контрольным основаниям осуществляет коррекцию однократных ошибок как по информационным, так и по контрольным модулям за 3+)log K(модульных операций, где К вЂ” количество информационных оснований, через ) Х(обозначается наименьшее целое число,не меньшее Х (Ц °

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

Наиболее близким по своей сущнос- 45 ти к изобретению является устройство для обнаружения и исправления ошибок в непозиционном коде, содержащее регистры информационных и контрольных разрядов кода, узел свертки по конт- 50 рольным основаниям, узел перевода остаточного кода в позиционный код, по входам подключенный к выходам регистра информационной части кода, а по выходам — к входам узла свертки по 55 контрольным основаниям, вычитатель, таблицу поправок и сумматор коррекции,-причем первые входы вычитателя соединены с выходами регистра контрольной части кода, вторые входы — к выходам узла свертки по контрольным основаниям, а выходы — к соответству. ющим входам таблицы поправок, первые входы сумматора коррекции соединены с выходами регистра информационной части кода, а вторые входы — с выходами вычитателя (2). устройство ориентировано на остаточное кодирование чисел рабочего диапазона по всем модулям системы в том числе и по контрольным, благода-. ря чему оно может использоваться для контроля ошибок как при передаче данных, так и при.выполнении арифметических операций. В рамках остаточного кодирования формирование контрольных признаков по информационным символам кода осуществляется с помощью операции расширения, которое в данном устройстве выполняется путем преобразования информационной части непозиционного кода в позиционный код.

Это приводит к низкому быстродействию устройства.

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

Поставленная цель достигается тем, что в устройство для обнаружения и исправления ошибок в напозиционном коде, содержащее К+2 входных регистров, где К вЂ” число информационных оснований, и две группы сумматоров коррекции, при этом входы входных регистров являются. информационными входами устройства, первые входы сумматоров коррекции первой и второй групп соответственно объединены, вторые входы сумматоров корекции первой группы объединены, вторые входы сумматоров коррекции второй группы объединены, введены дешифратор, К+2 элементов задержки, два блока суммирования вычетов, первая и втоРая гРУппы вспомогательных регистров, трехразрядный регистр, К элементов И, группы мультиплексоров, К+2 выходных регистров и элемент И, причем выходы К+2 входных регистров подключены ко входам К+2 элементов задержки соответственно и к соответствующим входам первого и второго блоков суммирования вычетов, первые выходы К+2 элементов задержки подключены соответственно к первым вхо дам сумматоров коррекции первой и

11349 второй групп, к вторым входам которых подключены выходы соответственно второго и первого блоков суммирования вычетов, подключенные также к входам дешифратора, первый, второй и третий выходы которого через трехразрядный регистр соединены соответственно с первыми входами мультиплексоров (К+1).-й и (К+2)-й групп и (К+1)-м входом элемента И, группа входов которого 10 подключена к выходам К элементов И и к первым входам мультиплексоров К групп, вторые входы которых соединены с первыми входами К элементов И и с выходами К вспомогательных регистров 15 второй группы, а третьи входы — с вторыми входами К элементов задержки, вторые выходы (К+1) и (K+2)-го элементов задержки соединены с вторыми входами мультиплексоров (К+1)-й и (К+2)-й групп, третьи входы которых соединены с выходами (К+1)-ro u (К+2)-ro регистров первой группы, выход i-го (i=1-К) вспомогательного регистра первой группы подключен к вто-25 рому входу i-го элемента И, выходы мультиплексоров К+2 групп подключены соответственно ко входам К+2 выходных регистров, выходы которых являются информационными выходами устройст- З0 ва, выход элемента И является выходом отказа от декодирования устройства, выходы сумматоров коррекции первой и

;второй групп подключены соответственно к входам вспомогательных регист35 ров первой и второй групп.

На фиг.1 и 2 приведена структурная схема предлагаемого устройства для обнаружения и исправления ошибок в непозиционном коде.

Устройство содержит информационные входы устройства 1.1, 1 ° 2,...,1 К+2 (К- количество информационных модулей), входные регистры 2.1, 2.2,..., 2К+2, элементы задержки 3.1, 3.2,... »45

ЗК+2, блоки суммирования вычетов 4К+1 и 4К+2 соответственно по первому и второму контрольным модулям системы, сумматоры коррекции первой группы

5.1, 5.2,...,5K+2, сумматоры коррек- 0 ции второй группы 6.1, 6.2,...,6К, дешифратор 7, вспомогательные регистры первой группы 8.1, 8.2,..., 8К+2, вспомогательные регистры второй груп-, пы 9.1, 9.2, ..., 9К, трехразрядный 55 регистр 10, элементы 11.1, 11.2,..., 11К, группы мультиплексоров 12.1, 12,2, ..., 12 К+2, выходные регистры

41 4

13. 1, 13.2, ..., 13 К+2, (К+1), входовый элемент И 14 информационные выходы устройства 15.1, 15.2, 15 К+2, выход 16 отказа от декодирования устройства.

Входные регистры устройствй =2..1, 2.2, ..., 2К+2 предназначены для приема соответствующих цифр исходного непозиционного кода о,1, 1,с К < к-1,к-, к-1, "к+2, "к„2 . Если слово(с(К 1, 2,к 1,„.,О к-1,к-1, к-, - к,2 не содержит ошибки, т.е. является кодовым, то его компоненты определяются следукнцими соотношениями

1 к-1 АМ, „(m х=1»2»... »

К I

A- X. И„,к „а1 К 1 т„„ик1» где M„ „„= — = — (i=1,2,...,К-1), И К-1 ш к-л

К )»"" » П12» ° » К

1--1 1 система информационных модулей; причем тк) 2р+К-2, р — некоторое фиксированное натуральное число, m „и

m.к+ — контрольные основания, выбираемые из условия: mÄ >m. (i=1,2, к+»

К; j = 1, 2) А — число рабочего диапазона системы, D= (-рИ „„,-рИ„ . +

+1,..., pN „-1, через Х1 „обозначается наименьший неотрицательный вычет, сравнимый с величиной Х по модулю m.

Элемент задержки 3i (i 1 2,...,K+

+2) представляет собой цепочку из

Т+1 последовательно соединенных регистров T=glog2(K+1)(вход первого из которых является входом элемента задержки, а выходы Т-го и (Т+1)-ro регистров -. первым и вторым выходами соответственно. Вход элемента задержки З.i (i=1 2, ..., +2К) подключен к выходу регистра 2.i, первый выход— к одноименным входам сумматоров коррекции 5.i и б.i (i/K+1 К+2, еслиjP2),а второй выход соединен с третьим входом группы мультиплексоров 12 ° i.

Блок суммирования .вычетов 4.K+j по !

-му контрольному модулю (j=1,2) имеет конвейерную структуру и служит для формирования за Т тактов j-й компоненты S синдрома S--(S 82) не позиционного кода, определяемой по

qiopMyae

К" 1

1134941

1, если S4 ФО и S 0 при этом r-й вход блока 4z+K+j (r=

=1,2,...,К) подключен к выходу регистра 2.r, (К+1)-й вход — к выходу . регистра 2. K+ j а выход подключен ко вторым входам сумматоров коррекцйи 5

j-й группы и j-му входу дешифратора 7., Дешифратор 7 предназначен для выделения значений синдрома $ ($„,S ) кода, соответствующих сигналам

1, если S 60, à S =-0 (3) 0 в остальных случаях

1, если Б 0, а $„=0 (4)

О в остальных случаях, 6

О в остальных случаях.

Элемент И 11.i ..вырабатывает сигнал

6„ поразрядного совпадения входных величин Х1 и У „@ 1 О, 1,...,m„. 1) в соответствии с формулой

25 б, —,ч (r, s у I! «)

0) (р где Х и У вЂ” j-e цифры двоичных

1, 1 представлений вычетов Х; и У„ соответственно r „=)log ш „.I i=1, 2,..., К, ;символом 8 обозначается операция сложения по модулю 2.

Элемент И 11.i (i=1,2,...,Ê) реа:лизуется на сумматорах по модулю 2 и

r - входовом элементе ИЛИ. 35,Первый вход элемента 11.i через вспомогательный регистр 8 соединен с выходом сумматора коррекции 5.i второй вход соединен с вторым входом 4о группы мультиплексоров 12.i и через вспомогательный регистр 9.1 с выходом сумматора коррекции б.i, выход

11.i подключен к первому входу группы мультиплексоров 12.i u i-му входу 45 элемента И14, (К+1)-й вход которого подключен к третьему выходу.трехраэрядного регистра 10 (i=1,2,...,К).

Второй вход группы мультиплексоров

12.K+j соединен с выходом вспомогательного регистра 8.K+j, а первый вход — с j-м выходом трехраэрядного регистра 10, входы которого подключены к соответствующим выходам дешифратора 7 (j=1,2). Выход группы мульти- 55 плексоров 12.i соединен со входом выходного регистра устройства 13.i для- всех i=1,2,..., К+2.

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

В соответствии с формулой (2) вычисляются компоненты Б„ и $< синдрома S-=(Б, Бу) кода. Если при этом

S„=$ =0, то декодируемое слово не искажено, т.е. является кодовым.

Если S P О, à S „,ð=Î (i=1,2), то (" .б1 ошибка произошла по j-му контрольному модулю. В этом случае истинное значение (K+j) и цифры кода совпадает с вьиетом

«-1

Х „ ) =! > I N,, « „< „, К-1 / m „+ l I g "

Случай S ФО и S ФО соответствует искажению одного из информационных символов; Для локализации и исправления такой ошибки достаточно . а) для каждого i=1 2,...,К в формуле (2) заменить i-ю цифру кода на неизвестное Z и затем найти его по контрольным модулям, используя (1) и (2). В результате получим вьиеты

-(„ Yi), К1 S„.) m

4 2 - «Ф!

Х = при i=1 2 К-1; (8)

|0 1) к- 1-er; ê I m „2 при 1.=1, 2 р... р К-1;:

j I„„+H" Б ш„, при 1=К, (9) б) если лля некоторого т t (1,2,..., K) выполняется Х =У1, то заключаем, что 3 -я цифра кода искажена. Исправленным ее значением является вычет

Х вЂ” У, в) случай, когда для всех i=1 2, ...,К выполняется неравенство Х У, указывает на то, что произошла ошибка, кратность которой больше едини- цы, и в рамках используемого корректирующего кода она не может быть исправлена.

Рассмотрим как работает предлагаемое устройство для обнаружения и исправления ошибок в непозиционном коде.

Непдзицион.ный код (g „„ о „„ е„З „рс„ р „ подлежащий койтролю, через входы 1.1, 1.2, ..., 1.К+2 устройства принимается на входные регистры 2.1, 2.2,..., 2.K+2, откуда он подается на элементы задержки 3.1, 3.2,е, 3. К+2 и в блоки суммирования вьиетов 4К+ 1 и 4.К+2, которые по

941 8

Д„ =О, то в регистре 13.i появится вычет Х; (в данном случае Х;=У„ для

1 К), если же 6„ =1, то в регистр

13.i поступит i-я цифра исходного кода. Перечень всех возможных ситуаций на выходах устройства представлен в табл.1. Нулевое значение сигнала Ч, вырабатываемого на выходе 16 отказа от декодирования устройства, свидетельствует о том, что исходный код либо бып правильным, либо .содержал ошибку по одному из модулей системы, которая исправлена, единичное значение сигнала ч соответствует ошибке, кратность которой больше единицы. В рамках используемого корректирующего кода такая ошибка не может быть исправлена.

Непозиционный код, сформированный в регистрах 13.1, 13.2, ..., 13.К+2 .устройства (исходный или исправленный), снимается с выходов 15. 1, 15.2, ..., 15.К+2 устройства, и на этом операция обнаружения и исправления ошибок в непозиционном коде заканчивается.

Быстродействие прототипа, главным образом, определяется скоростными характеристиками входящего в его состав блока преобразования остаточного кода в позиционный код. Теоретическая нижняя оценка времени работы прототипа составляет 2(2+)log К () модульных оп ер аций.

Перечень возможных ситуаций на выходах устройства

Ф Значения сигнало

Содержание ситуации

Ошибка отсутствует, на информационных выходах устройс гва формируется исходный код, М =О.

Ошибка ."ронзошла по первому контрольному модулю, на информационных выходах устройства формируется исправленный код, Y =О.

7 1134 истечении Т-ro такта в соответствии с (2) сформируют синдром S=-(S„» Sq ) непозиционного кода.

На (Т+1)-м такте компонента S> синдрома (j=1,2) с выхода блока суммирования вычетов 4.K+j подается на

j-й вход дешифратора 7 и вторые входы сумматора коррекции 5+j i на первый

I вход которого с одноименного выхода элемента задержки З.i поступает i-я tp цифра исходного непозиционного кода

4 К-1 Д К-4 ° - К-4,К-4 g-4 i Сф1, КЛ (i=1, 2, . ...К+2; j =1, 2, 1фК+1, К+2, если j =2), сумматоры коррекции 5. i (i=1 2,..., К+2) и 6.i (i.=1,2,...,К) получают соответственно вычеты Х, и

У< (см. формулы (7-9)), которые с

:вйходов сумматоров поступают в ре. гистры 8.i и 9.i соответственно, а дешифратор 7 в соответствии с форму лами (3-5) формирует сигналы 6 б, „ и d которые с первого, второго и третьего выходов дешифратора передаются в трехразрядный регистр

10.

На (Т+2)-м такте работы устройства элемент И 11.i (i=1 2,. ° .,К) производит анализ содержимых Х„. и У; соответственно регистров 8.i и 9.i вырабатывая сигнал д,, определяемый соотношением (6), который подается на первый вход группы мультиплексоров

12.i и х-й вход элемента И 14. Одновременно с этим на первый вход (K+j)-й группы мультиплексоров (j= . =1,2) и (К+1)-й вход элемента И 14 с выходов j-го и третьего разрядов регистра 10 подаются соответственно сигналы 6„ и d на вторые входы групп мультйплексоров 12.i и 12K+j

40 (i=1,2,...,К; j=1,2) подаются соответственно содержимые регистров 9.i и 8.K+j ò.å. вычеты У„ н Х„, а на третий вход группы муль иплексоров ,12.i (i=1,2,...,К+2) со второго выхода элемента задержки З.i поступает

i-я цифра контролируемого непозицион"ого кода 1 к- „ выходах группы мультиплексоров

12. 1, 12.2, ..., 12.К+2, а следовательно, и в выходных регистрах устройства 13.1, 13.2,..., 13.К+2 сформируется, искомый непозиционный код, а на выходе 16 элемента И 14 вырабатывается управляющий сигнал Ч =6,,6,," „д . Если для некоторого 3.6 I 1,2,..., K+2 j сигнал

1О

1134941

Значение сигналов

Содержание ситуации

Значение сигналов

Содержание ситуации

Произошла не однокр ат ная ошибк а, на информационных выходах устройства формируется исходный код, 4-=1 .

Фиг.1

11родолжение таблицы

Ошибка произошла по второму контрольному модулю, на информационных . выкодах устройст- 10 ва формируется исправленный код, Ч =О.

Ошибка произошла по му информя циочному модулю, на информационных выходах устройства формируется испРавленный код, 20

Ч =О.

11родолжение таблицы

Время выполнения одной операции контроля непозиционного кода в предлагаемом устройстве занимает

2+)log<(K+1) (тактов, что в два раза меньше указанной выше нижней оценки для прототипа.

1134941

Составитель И.Сафронова.

Редактор А.Долинич Техред И.Гергель Корректор Н.Король

Заказ 528 Тираж 710 Подписное

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

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

Филиал ППП "Патент", г.Ужгород, ул.Проектная, 4