Устройство для обнаружения и исправления ошибок Советский патент 1993 года по МПК G06F11/08 

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

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

устройств.

Целью изобретения является повыше- |же быстродействия устройства, | На чертеже представлена структурная Электрическая схема устройства. ; Устройство для обнаружения и исправления ошибок имеет входы 1,1-1.6 информационной части слова, первую группу входных регистров 2,1-2.6, входы 3.1-3.3 бстатков по контрольным основаниям, вторую группу входных регистров 4.1-4.3, четыре блока 5.1-5.4 сумматоров, необходимых для вычисления неточного ранга и остатков по контрольным основаниям, группу элементов задержки 6.1-6.3, второй блок 7.1 памяти, в котором хранятся константы ранга, третий блок 7,2 памяти, в котором хранятся величины возможных ошибок при значениях вычетов невязки по двум контрольным основаниям и признаки выбора подтаблицы по третьему основанию, четвертый блок 7.3 памяти, в котором хранятся пары величин возможных ошибок, соответствующих признаку выбора подтаблицы и

00

со

3

w

значению третьего остатка невязки по третьему контрольному основанию, первую группу сумматоров 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 памяти должна быть выполнена в соответствии с принятой моделью арифметики. В данном случае константы для вычисления ранга имеют вид

и

-I

22d I mi(g|+(Pi-1))/2|p,

Pi

I 1,n(n 6),

где oi - остатки числа по информационным основаниям;

Pi - основания;

mi - мультипликативно обратные велип

чины к П PS/PI по модулю PI;

s

Ixi Р - остаток по модулю PI;

d - параметр точности (d nQ.

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

bi.k I -mi (сц + (Рг1)/2) Pn/Pi I Pk. где Pk - контрольные основания;

Рп - произведение информационных

п

оснований Рп П PS.

S 1

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

bn+u- I vn Рп + (Pn-1)/2) IPIC,

k n+1, n+2,... где VN - ранг числа N.

В этом случае ранг вычисляется в соответствии с формулой

а /2М I 1

(1)

причем VN - это старшие остатки а разря- дов суммы (1); всего сумма требует 3d бит, т.е. все разряды суммы слева от запятой.

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

0

5

0

5

0

5

0

5

N-H

. lN|Pk lЈbi,k Ipk, k n+1,n+2, ... (2) I 1

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

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

Pn+k Рп;

Рп+2 Рп-М 2Рп Рп-1 (Р1 Р2 ... Рп).

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

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

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

50

IfTIi Д|р,-Рп

Pi

) 111.13-(5n,3i3), (3)

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

Pi

ДНИ 11.13+ Рп)IIГП

i Два основания обеспечивают единственно возможное решение

I (T/I Л i) для данного I.

| Полученное значение r/i и невязка 6м служат входом в таблицу решений уравне-

нйя:

Это дает не более двух значений возможного Д| при заданных Г и 5i7.

Таким образом, объем требуемой памя- составляет в данном случае 11x13 28 ов для блока 7.2 памяти подтаблиц 2x17x2 ов 6х26х2 слов Зх28 для подтаблиц.

TV

с/ с/ О

зщий объем 2° + 3x2° 2|и слов. Устройство работает следующим обраю

за

м.

Вычеты представления числа по инфор- м&ционным и контрольным основаниям поступают соответственно на входы 1.1-1,6 и 3.1-3.3 устройства. Значения остатке в по информационным основаниям с вы- хсдов входных регистров 2.1-2.6 являются адресами, по которым из блока 18 постоянной памяти извлекаются константы для вы- числения ранга и константы для РЕ сширения на контрольные основания для каждого из них. Константы для вычисления PC нга поступают в четвертый блок 5.4 сум- моторов для вычисления ранга, с выхода которого значение ранга поступает на вход б/ока 7.1 памяти. Эти константы вместе с константами для расширения на контроль- нне основания суммируются с помощью сумматоров 8.1-8.3 первой группы, образуя остатки числа, представленного вычетами пс информационным основаниям, по контрольным основаниям. На сумматорах 9.1- 9.3 второй группы они вычитаются из остатков, поступивших по контрольным входам 3.1-3.3, через входные регистры 4.1-4.3 второй группы, образуя невязку. Величины невязки по двум наименьшим контрольным основаниям образуют адрес, по которому из второго блока 7.2 памяти извлекаются величины возможных ошибок Д| и бит выбора падтаблицы rf/i из третьего блока 7.3 памяти по третьему контрольному основанию, поступающему с выхода регистра 10. Бит выбора подтаблицы г и величина невязки по трэтьему основанию образуют адрес, по которому из соответствующей подтаблицы бл ока 7.3 памяти извлекаются два значения возможных ошибок А г и Дг по каждому из информационных оснований. На элемен

0

5

0

5

0

5

0

5

тах 12.1-12.12 эти значения сравниваются с ранее полученными значениями Д| Ч В случае совпадения (это возможно только для одной пары Дг , Д i 0 значение ошибки через соответствующие элементы ИЛИ 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

lPn/Pi I pi 11 3 1 1 5 12 mi 17 10 1 1 14 8

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

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

N(3.30,20, 13, 14, 15,8,4) . Вычисляют ранг числа INI Рп (3, 3, 20, 13, 14, 15):

Pi31 29 27 25 23 19

3 20 13 14 15

)/2 15 14 13 12 11 9

d 3 и константы для вычисления ранга блока 2 будут

ai55 55 14 0 13 6

(/22d 2,23 2.

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

27 25 6 0 5 2

Im ai4-Јy-i)|p,.

iPn/Pih 2 12 10 3 1 6 Ю

15

|mi(ai+ ДГ-1 lPn/Pi In

)|P|27 25 6 0 5 2 4 . g 5...1. 3:.1Qi

-bin968049

bin253072

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

Pn+k 17 13 1120

I Pn 1 Pn+k 1 10 3 VM2 .2 .2

2 7

|(Pn-lV2|Pn+k 0 -ft- if9Ц

bn+U2 ; 5, 7Г.

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

9 11 2 5 12 5 -13 5 3 000 287 16 1 2

2 57

(di, $2, дз) 13 3 4 Следовательно, значение невязки на ыходе сумматоров 9.1, 9.2 и 9,3 второй руппы составляет 854

13 3 4

488

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

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

Imi ДгI (8.8)х(х,3) + ty Pi - |(4,2) + + т Pi 111,13 - 1134 + jflp, 1143 22; Aif1) 122-11131 25, /1 1;

по второму основанию

|m2Azlp2 l(8,8)x(12,6)+ rpWw

- I70+ 72P2ll43,

.е. решений нет ни при r)z 0, ни при r 1 (коррекция в этом случае может быть улевая);

30

35

40

45

,.

55

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

1тзДз1 РЗ l(8,8)x(4,9)+ зРз 11-13

|(6 6) + 73РЗ 1143 6,

Дз0) 16-1|рб 6, з 0; по четвертому основанию

|ГП4 A4IP4 l(8,8)x(9,1)+ 11-13 l(7,8)+ J/4P4I 11-13 185+ 7/4Р4 1143,т.е. решения нет;

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

ГтвДб Р5 l(8,8)x(1,4)+ 1Ш -1(8,10)+ Ч5Р5 И43-21, Ле 121-14(, /5 0;

по шестому основанию

1теДб рб I(8,8)х( 11.10) + jyePe 111-13 1(10,3)+ 7бРб1143 36,

решения нет.

Обращение в блок 7.3 памяти дает по первому основанию tyi 1

Imi Ai lpi |4-14li7 + Pi + k-17 5 + 31+k-17,

lmiAi(1)|pi 19, Imi Ai(3)lpr 2, Ai(2-23, Ai(3) 22;

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

1тзАз) РЗ 14-101 17 + k -17 6 + k -17, I тз Дз( I РЗ 6; k - О, I тз Аз(3) I рз 23, k 1, Аз(2) 6, Аз{3) 23;

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

ImsAsJps И-6 Ii7 7 + k- 17, lm5A5f2)|p5 7,k 6,A5(2)12,

Аб не существует (N 0).

На элементах 12.1-12.12 сравнения имеют для оснований 31, 27, 23:

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

Формула изобретения Устройство для обнаружения и исправления ошибок, содержащее первую группу входных регистров, информационные входы которых являются входами информационной части слова устройства, первый и второй блоки сумматоров, группу элементов задержки, первую группу вспомогательных регистров, группу многовходовых элементов И, вторую группу вспомогательных реги- строз, группу сумматоров коррекции, регистр, отличающееся тем, что, с повышения быстродействия, в устройство введены вторая группа входных регистров, информационные входы которых являются входами остатков по контрольным ОСНОЕЭНИЯМ устройства, первый блок памяти, гр/ппа адресных входов которого соединена с выходами входных регистров первой группы, третий и четвертый блоки сумматоров, Е рого

оды которых и входы первого и вто- блоков сумматоров соединены с

выходами первого блока памяти, второй

блок динен ров, входы

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

которых соединены с выходами, соотенно, первого, второго и третьего

сумматоров, вторая группа сумматорвые входы которых соединены с выл соответствующих регистров второй

.1, третий блок памяти, первый и втовходьветст блоко ров, п ходам групп

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

0

5

0

5

5

0

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

I

Nl

-

«M

Ъ

f