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

 

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

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

РЕСПУБЛИК (я)з G 06 F 11/08

ОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ЕДОМСТВО СССР

ОСПАТЕНТ СССР) - -:ь ЮЛА

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Ф - . .4 ;4. 1)

) 6 (1) 4880204/24 ((22) 12.07.90 (8) 30.08.93. Бюл. N 32 (1) Научно-исследовательский институт авоматических систем и Институт математии и механики АН КазССР

72) А.В.Бондаренко, А.В.Шершавов, .M,Àìåðáàåâ, Ю.А,Макеев, И.Т,Пак

Р, Н.Турмухамбетов

6) Авторское свидетельство СССР

960823, кл. G 06 F 11/08, 1980.

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

1134941, кл. G 06 F 11/08, 1983. б4) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И

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

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

Изобретение относится к вычислитель«(ой технике и может найти применение в

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

Целью изобретения является повыше«(ие быстродействия устройства, На чертеже представлена структурная

1 лектрическая схема устройства.

Устройство для обнаружения и исправения ошибок имеет входы 1,1 — 1.6 инфорационной части слова, первую группу входных регистров 2.1 — 2.6, входы 3.1 — 3.3 ()статков по контрольным основаниям, вто„„. Ж„„1837293 А1 основания, что дает возможность определить ошибку в два этапа. Во втором блоке памяти хранятся константы ранга, в третьем блоке памяти — величины возможных ошибок при значениях вычетов невязки по двум контрольным основаниям и признаки выбора подтаблицы по третьему основанию, à в чет/ вертом блоке памяти — пары величин возможных ошибок, соответствующих призн;гку выбора подтаблицы и значению третьего остатка невязки по третьему контрольному основанию. Это позволяет исключить вычисление возможных ошибок и тем самым достичь поставленной цели. Устройство для обнаружения и исправления ошибок также содержит две группы входных регистров, блоки сумматоров, группу элементов задержки, группы сумматоров, регистр, группы вспомогательных регистров, группу элементов сравнения, группы элементов

ИЛИ и И, группу сумматоров коррекции, первый блок памяти. 1 ил. рую группу входных регистров 4.1 — 4.3, четыре блока 5.1 — 5.4 сумматоров, необходимых для вычисления неточного ранга и остатков по контрольным основаниям, группу элементов задержки 6.1 — 6.3, второй блок 7.1 памяти, в котором хранятся константы ранга, третий блок 7,2 памяти, в котором хранятся величины возможных ошибок при значениях вычетов невязки по двум контрольным основаниям и признаки выбора подтаблицы по третьему основанию, четвертый блок 7.3 памяти, в котором хранятся пары величин возможных ошибок, соответствующих признаку выбора подтаблицы и

1837293 значению третьего остатка невязки по третьему контрольному основанию, первую группу сумматоров 8.1 — 8.3, вторую группу сумматоров 9.1-9.3, необходимых для определения невяэки по контрольным основаниям, регистр 10, первую группу вспомогательных регистров 11,1 — 11.6, группу элементов 12.1 — 12.12 сравнения, вторую группу вспомогательных регистров 13.1—

13.6, группу элементов ИЛИ 14.1 — 14.6, третью группу вспомогательных регистров

15.1 — 15.6, группу многовходовых элементов

И 16.1-16.6, группу сумматоров коррекции

17,1-17,6, первый блок 18 памяти. Причем на чертеже не показаны синхронизирующие и тактирующие цепи, необходимость и подключаемость которых общеизвестны и не требуют дополнительного раскрытия.

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

Элементы сравнения 12.1-12.12 представляют собой схемы, вырабатывающие логическую "1" при совпадении всех разрядов сравниваемых чисел, Сумматоры коррекции 17.1 — 17.6 могут быть как позиционными, так и модульными.

Кодировка блока 7.1 памяти должна быть выполнена в соответствии с принятой моделью арифметики. В данном случае константы для вычисления ранга имеют вид

a (1 = 1;п (и = 6), 22 ml (а + (Pl — 1))/2 t pl где а — остатки числа по информационным основаниям;

Pl — основания;

ml — мультипликативно обратные вели и чины к П Ps/Pl по модулю Pl, s=l

Ix I р — остаток по модулю Pl, d — параметр точности (d «)tog2 пр.

Константы для вычисления остатков по контрольным основаниям имеют вид

Ьц(= -пi (а) + (Р -1)/2) Pn/Pl I pk, где Рк — контрольные основания;

Рп — произведение информационных и оснований Pn = П Р,, в =!

Константы ранга имеют вид

Ь.+1, = I г P. +(P.-1)/2) Ip<, k=n+1, и+2, ... где Ич — рангчисла N.

В этом случае ранг вычисляется в соответствии с формулой щ= (g ai/1 ), 1=1 причем Ич — это старшие остатки а разрядов суммы (1); всего сумма требует 3d бит, т.е. все разряды суммы слева от запятой.

Остатки по контрольным основаниям вычисляются по формуле

N+ 1

I N l pa = I Ь ц(! рк, k = и+1, и+2, „, (2)

1=1

Из этих формул ясно, что четвертый

15 блок 5.4 сумматоров состоит из позиционных сумматоров разрядности <30, а первый, второй и третий блоки 5.1-5.3 сумматоров вычисления остатков по контрольным основаниям — из модульных сумматоров по контрольным основаниям. Здесь возможно использование и позиционных сумматоров, если выполняется приведение к остатку результата суммирования каким-либо способом перед входом в блоки 7.2, 7.3 памяти или, например, простым увеличением адресного пространства этих блоков 7.2, 7.3 памяти для хранения величин допустимых ошибок.

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

Рп+к > Рп, Рп+2 Рп+1 > 2Рп Рп-1 (Р1 < Р2 « „. Рп).

В этом случае объем требуемой памяти блока 18 постоянной памяти для определения ошибки по невязке должен составлять

2 слов, Использование трех контрольных

11 оснований позволяет определить ошибку в два этапа таблично, исключая вычисления.

Схема представлена для девяти разрядных оснований, из которых 6 — информационные, а 3 — контрольные.

Вэтом случае ошибку Л i no невязке (д11, д1з) находят из уравнения

Iml Ail pl Pn

9Рп) I11ëç=(А1, д1з), (3)

Р где принимает значения 0,1. Отсюда име55 ют

Л l = д И,n + rPPn) г- — (4) Pl Рп и Р

11,1з р

1837293

Два основания обеспечивают единств нно возможное решение (rp Ai) для данного I.

Полученное значение ц и невязка д17 с ужат входом в таблицу решений уравне- 5 ния.

Imi6Iр Рп

>/iPn 17= д17, (5)

1 .е. !Р 6 р 17 = !д 17+ ЧР) Р 17, (6) !

Это дает не более двух значений возм жного Лi при заданных q и д17.

Таким образом, объем требуемой памят составляет в данном случае 11х13 2 с ов для блока 7.2 памяти подтаблиц 2х17х2 с ов 6х2 х2 слов = Зх2 для подтаблиц.

О щий объем 2 + Зх2 = 2 слов.

В В 1О

Устройство работает следующим образ м.

Вычеты представления числа по информ ционным и контрольным основаниям пос упают соответственно на входы 1.1 — 1,6 и в оды 3.1 — 3.3 устройства. Значения остатк в по информационным основаниям с вых дов входных регистров 2.1 — 2.6 являются а ресами, по которым из блока 18 постоянн и памяти извлекаются константы для выч сления ранга и константы для р сширения на контрольные основания для к ждого из них, Константы для вычисления р нга поступают sчетвертый блок 5,,4 сумм торов для вычисления ранга, с выхода к торого значение ранга поступает на вход б ока 7,1 памяти. Эти константы вместе с к нстантами для расширения на контрольн ie основания суммируются с помощью сумматоров 8.1 — 8.3 первой группы, образуя о татки числа, представленного вычетами и информационным основаниям, по контр льным основаниям, На сумматорах 9,1—

9, второй группы они вычитаются из о татков, поступивших по контрольным вход м 3.1 — 3.3, через входные регистры 4.1 — 4.3

45 вт рой группы, образуя невязку, Величины н вязки по двум наименьшим контрольным основаниям образуют адрес, по которому из втррого блока 7.2 памяти извлекаются вели-! чины возможных ошибок Лг и бит выбора (1) подтаблицы a i из третьего блока 7.3 памяти и третьему контрольному основанию, пост пающему с выхода регистра 10, Бит выбо!ра подтаблицы g и величина невязки по третьему основанию образуют адрес, по которому из соответствующей подтаблицы блока 7.3 памяти извлекаются ва значения возможных ошибок Лi! и Ьi по каждому из!информационных оснований, На элемен-! тах 12.1 — 12.12 эти значения сравниваются с ранее полученными значениями h,i . B слу 1 чае совпадения это возможно только для одной пары 4, Л г 1 значение ошибки ! ко через соответствующие элементы ИЛИ

14.1 — 14.6 и элементы И 16.1 — 16.6 поступает на сумматоры коррекции 17.1 — 17.6, где величина ошибки складывается с соответствующим неверным остатком, благодаря чему на выходе устройства формируется исправленныйй результат.

Первый, второй и третий блоки 5.1 — 5.3 сумматоров вместе с элементами задержки

6.1 — 6.3 служат для расширения на контрольные основания, причем элементы задержки

6.1 — 6,3 обеспечивают задержку промежуточной суммы констант расширения.

Входные регистры 4.1 — 4,3 второй группы, входы которых соединены с входами

3.1 — 3.3 устройства, обеспечивают хранение остатков по контрольным основаниям и подачу их на вторые входы сумматоров 9.1 — 9.3 второй группы, При этом входы 1.1 — 1.6 остатков по информационным основаниям соединены с вспомогательными регистрами

15.1 — 15,6 третьей группы, необходимыми для синхронной работы всего устройства.

Для этой же цели служат и вспомогательные регистры 11.1 — 11,6 и 13.1 — 13.6 первой и второй групп, Для лучшего понимания работы устройства может быть рассмотрен один числовой пример.

Пусть число N 35963 представлено своими остатками по основаниям 31, 29, 27, 25, 23, 19:(3, 2, 26, 13, 14, 15). Для этой системы оснований имеют

Р 31 29 27 25 23 19

IPn/Pi р 11 3 1 1 5 12 щ 17 10 1 1 14 8

Остатки числа N по контрольным основаниям 17, 13, 11 есть (8, 5, 4).

Пусть произошла ошибка по третьему основанию N = 21 и получилось число

N(3,30,20,13,14,15,8,,4) .

Вычисляют ранг числа N I Pn (3, 3, 20, 13, 14, 15):

Р 31 29 27 25 23 19 г4 3 3 20 13 14 15

Р -1 /2 15 14 13 12 11 9

18 17 6 0 2 5

mi 17 10 1 1 14 8

1mi(di+ ) !р 27 25 6 0 5 2

d = 3 и константы для вычисления ранга блока 2 будут а 55 55 14 0 13 6

Ич =(Zа /2 )=(2,23)=2.

1837293

В ы числя ют константы расширения на контрольные основания:

Imi(ai+ )(,27 25 6 0 5 2 ! Р(7/Pi I 17 11 10 12,15 3 9

-Ь!17 8 12 4 0 1

0(11 9 5 13 О 2 16

Imi(ai+ )!,27 25 6 0 5 2

I Pn/Р(!17 2 12 10 3 1 6

- из

Ь!13 11 12 5 О 8 1 (т!(а!+ — )!,27 25 6 0 6 2

IP /P(!11 4, Е:5 1 3 10

-Ь(11 9 6 8 О 4 9

Ь(11 2 5 3 О 7 2

Константы ранга также легко вычислить:

17 13 1(1 :!0 3!

2:2 г !

Pn+k

I Pn l Pn+k

Вход в блок 7.2 памяти дает значение коррекции возможной ошибки и признак выбора подтаблицы.

По первому основанию

I m1 6zI = (8,8)х(х,3) + эу1 Р1 = !(4,2) +

+ т)! Р1! 11,13 = 134 + 7)(Р(! 14з = 22;

Л1") - 22 11 31 = 25, yi - 1, по второму основанию! m2 и P2 !(8,8)х(12,6) + tpPz !14з- I7O+ рР2!143, т.е. решений нет ни при r 7.- О, ни при r 1-1 (коррекция в этом случае может быть нулевая); !(11

Ьл+1,k 2,. 5, 7;"

Таким образом, расйирение на контрольные основания дает остатки

Р(17 13 1

9 11 2

5 12 5

-13 5 3

О 0 О

2 8 7

16 1 2

2 5 7

1II%,Б Ъ 5

Следовательно, значение невяэки на выходе сумматоров 9.1, 9.2 и 9.3 второй группы составляет

8 5 4

13 3 4

4 8 8 по третьему основанию

)п13 Л3| р3 l(8,8)x(4,9)+ rpP31 11 1з

= )(6,6)+ юузРз !14з= 6, 5 63 )= !6 1lp6=6, rp-О; по четвертому основанию ! m4 Л4 p4 = !(8,8)х(9,1) + 1 4Р4 I 1113 =

10 = l(7,8)+ y4P4I1113 = I85+ У4Р4 !143; т.е. решения нет;

4 по пятому основанию

15 Im5&l p5= !(8,8)х(1,4)+ 7р,-Р5!11.13=

l (8,10) + )5Р5 143 - 21, 6б = !21 14 !23 = 18, ь = О; по шестому основанию

Im6 ® I P6 = l(8,8)õ(11,10) + Ц6Р6!1113 =

= l(10,3)+ д6Р6! 143 =36, решения нет.

Обращение в блок 7,3 памяти дает по первому основанию yi -1

Im1 и IP1= l4 14!17+Ð1+! 17=

=5+ 31+ k 17, Im141 IP1 = 19, Im1 Л1() р1 = 2, Л1(2) - гз, Л1(з) = гг. по третьему основанию

Imk!k7I P3= 14 !0I !! +2 !7= 6+k !7, Im3ha2) <рз=6; ) =0, )m3 ДР Ip3=

=23, k = 1 24(3@ = 6, 3(з) = 23; по пятому основанию ! (п5Л5 jp5= !4 6 I17= 7+ k 17, Im5 5 !Р5=71 1С 6 Ь5 =12, 45

he ) не существует(N =О), На элементах 12.1-12.12 сравнения имеют для оснований 31, 27, 23;

25 Ф 23 25 22 6 w 6 18 Ф12, и эначеО ние.коррекции Аз 6 по третьему основа(1) нию поступает на соответствующий сумматор коррекции 17.1 — 17.6, на выходе

Ю которого образуется правильный результат, 55

Формула изобретения

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

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

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

, третий блок памяти, первый и вторесные входы которого соединены с 30 ми соответствующих сумматоров группы, информационный вход ресоединен с выходом третьего сумвторой группы, выход второго амяти соединен с вторыми входами 35 сумматоров первой группы, выходы которых соединены с вторыми входами соответствующих сумматоров второй группы, четвертый блок памяти, первый адресный вход которого соединен с выходом регистра, а второй адресный вход третьего блока памяти и информационные входы вспомогательных регистров первой и второй групп подключены к выходу третьего блока памяти, группу элементов сравнения, первые входы которых соединены с выходом четвертого блока памяти, а вторые входы 2i-го и (2I-1)-ro элементов сравнения группы соединены с выходом i-го вспомогательного регистра первой группы (I=1,6), группу элементов

ИЛИ, причем первый и второй входы I-го элемента ИЛИ группы соединены с выходами 2i-го и (2I-1)-го элементов сравнения группы, третью группу вспомогательных регистров. информационные входы которых соединены с информационными входами соответствующих входных регистров первой группы, выходы элементов ИЛИ группы соединены с первыми входами соответствующих многовходовых элементов группы И, другие входы которых соединены с выходами соответствующих вспомогательныхрегистров второй группы, входы многовходовых элементов И группы соединены с первыми входами соответствующих сумматоров коррекции, вторые входы которых соединены с выходами соответствующих вспомогательных регистров третьей группы, выходы сумматоров коррекции являются выходами устройства.

1837293

Составитель И. Ванюхин

Техред M. Моргентал Корректор П. Гереши

Редактор Т. Коляда

Производственно-издательский комбинат "Патент", r. Ужгород, ул,Гагарина, 101

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

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

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