Устройство для вычисления суммы квадратов к @ -разрядных чисел

Устройство для вычисления суммы квадратов к @ -разрядных чисел

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советския

Социалистическик

Республик

gi)993256 ф (61) Дополнительное к авт. сеид-ву(22} Заявлено 090281 (21)3245246/18-24 с присоединением заявки ¹ р,ц g+ з

G 06 Р 7/544

Государственный комитет

СССР по делам изобретений и открытий (23} Приоритет(ЩУДК 681.3 (088.8) Опубликовано 3001,83. Бюллетень ¹4

Дата опубликования описания 3001,83

М

t»

Г.Е.Пухов, А.И.Стасюк, Ф.E. Ëèñíèê и A.È Üóýåíêî (72) Авторы изобретения

Киевский ордена Трудового Красного Знамени=--институт инженеров гражданской авиации (73 ) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СУММЫ

КВАДРАТОВ К и -РАЗРЯДНЫХ ЧИСЕЛ

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

Известно устройство для вычисления сумвы парных произведений, содержащее регистр множимого,.регистр множителя, узел сдвига, сумматор, узел управления, группы элементов И, элементы И, ИЛИ, группу элементов ИЛИ(1).

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

Наиболее близким к предлагаемому является устройство для вычисления сумьаа квадратов К и-разрядных чисел, содержащее счетчик основания, разрядные выходы которого через элементы И группы соединены с выходами соответствующих разрядов накопителя, формирователи строб-импульсов, К-звейная линия задержки, К-ключей и элемен. ты ИЛИ, выход первого из которых соединен со входом второго разряда счетчика основания и К-звенной линии задержки P2)

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

Цель изобретения — увеличение быст родействия и надежности вычислений суммы квадратов К и-разрядных чисел.

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

И, схему сравнения, сумматор, полусумматор и одноразрядные вычитатели, причем. группы элементов И образуют Ia матрицу,.каждый 1-й столбец которой (где 1=1,2,...,n-1) содержит 1 групп элементов H и сдвинут относительно (1-Ц-го элемента И на один разряд вниз,.(2 g --1)-е информационные входы (где(, =1,2, К) групп элементов И ,i-ro столбца матрицы объединены,и

993256 подключены к (1+1) -му разряду -й входной информационной шины, к 1-му разряду которой подключены 2 j -e информационные входы i-й группы элеентов И всех столбцов, информационые выходы групп элементов И каждой

Я -й (где Яв1,2,..., 2n-3) строки матрицы соединены с информационным входом (S+1)-го разряда сумматора, информационный выход каждого 2 i-ro разряда сумматора подключен к первым информационным входам i-го полусумматора и 1-го одноразрядного вычитателя, второй информационный вход i-го одноразрядного вычитателя подключен к информационному выходу i-го полусумматора и соответствующего 2 1-му разряду информационной выходной шины, информационный выход i-ro одноразрядного вычитателя соединен с первым информационным входом i-го разряда схемы сравнения, второй вход которой подключен к второму информационному входу i-ro полусумматора и

i-му разряду первой информационной входной шины,.информационный выход каждого (2 i-1) -го разряда (где 1=2, З,...,n-l) сумматора соединен с вхо- дом (2 1-1)-го разряда информационной выходной шины, старший разряд которой соединен с информационным выходом элемента ИЛИ, к первому и второму информационным входам которого подключены выходы переносов соответственно сумматора и полусумматора предыдущего разряда, выход переноса каж дого (i+1) -ro полусумматора соединен с входом переноса сумматора последующего разря,;а, а выходы (1+1)-х разрядов каждой (j +1)-9k входной информационной шины подключены к информационному входу 2 i-ro разряда сумматора, информационный выход схемы сравнения соединен с управляющим выходом устройства.

Причем каждая группа элементов И содержит К двухвходовых элементов И, причем первый. информационный вход каждого ) --го элемента И (где ) 1,2.

К) соединен с (2 ф -1) ым информационным входом группы элементов И, второй информационный вход ) -го элемента И соединен с 2 7-ым информационньм: входом группы элементов И.

Кроме того, схема сравнения содержит и сумматоров по модулю.два и элемент. ИЛИ, причем первый информационный вход i-ro сумматора по модулю два соединен с первым выходом i-ro разряда схемы сравнения, второй информационный вход i-ro сумматора по модулю два соединен с вторым выходом. i-го разряда схемы сравнения, информационные выходы сумматоров по модулю два соединены с соответствующими входами элемента ИЛИ, информационный выход которого соединен с информационным выходом схе. мы сравнения.

На фиг. 1 представлена схема устройства для вычисления суммы квадратов К-и-разрядных; чисел для слу5 чая, когда информация представлена пятью двоичными -разрядами (n=5), а количество чисел равно трем (К=З)) на фиг. 2 — схема группы элементов И.

Устройство содержит матрицу 1, 1О сумматор 2, схему 3 сравнения, элемент ИЛИ 4,полусумматоры .5,одноразряд-, ные вычитатели 6,К входных шин7 (где = 1, 2 ..., К), выходную шину 8, (где i = 1, 2 ... n8=

l,2;.. 2 n) и управляющий выход 9 (регистрации конца переходного процес- . са в устройстве). Матрица 1 выполнена из групп элементов И 10„причем каждый

5.-й столбец (где i=1,2,..., n-l) содержит 1групп элементов И 10 и сдви20 нут относительно (i-1)-го на;один разряд вниз. Сумматор 2 выполнен из (2n-l) последовательно соединенных одноразрядных. сумматоров. Схема сравнения 3 выполнена из и сумматоров ll

25 по модулю два 12 и элемента ИЛИ 4, причем выход каждого i-ro сумматора. по модулю два 12 подключен к 1-му входу. элемента ИЛИ 4, выход которого, соединен с выходом 9 регистрации кон30 ца переходного процесса в устройстве. Каждая группа элементов И 10 матрицы l содержит К двухвходовых элементов И 13 причем первый вход каждого )-ro элемента И 13 (j. »1,2...,Кf

35 является Л $ -1) -ым входом группй элементов И 10 матрицы.1 и групп элементов И. Второй вход ) -ro элемента И 13 группы элементов И 10 матрицы 1 из элементов И является 2 -ым

4р входом группы элементов И 10. Все (2 4 -1(7-ые входы групп, элементов

И 10 каждого i-го столбца матрицы 1 из элементов И объединены и подключены к выходу .(1+1)"ro разряда -oN входной шины 7), к выходу i-ro разряда которой подключены 2 j -е входы i-ой группы элементов И 10 всех столбцов матрицы 1 из элементов И.

Выходы групп элементов И 10 каждой

В=.,ой (где,.81,2,...,2п-3)строки матрицы; 1 из элементов И соединены со входом одноразрядного суьщатора

11 (S+1)-го разряда сумматора 2, выход каждого 2 i-ro разряда которого .подключен к первому входу i-ro

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

gp первому входу сумматора по модулю два 12 1-гб разряда схемы 3 сравнения, Второй вход сумматора по модулю два

12 i-ro разряда схемы 3 сравнения

/йодключен ко второму входу i-го полусумматора 5 и i-xy разряду пер" -- 993256 вой входной шины ),-(К.1) . Выход одноразрядного сумматора.ll (2i -l)-го разрядного сумматора (где 1.-.2,3, и-1) соединен со входом (2i-l)-го

:разряда выходной шины 8,вход старше-! го разряда .которой-соединен с выходом элемента ИЛИ 4,к входам которого подключены выходы переносов одноразрядного сумматора 11, сумматора 2 и полусумматора.5 предыдущего .разряда.

Выход переноса каждого (i+1)-го (1=1,2,...,,п-1) полусумматора 5 соединен с входом одноразрядного сув матора 11,.сумматора 2..последующего разряда..Выходы (i+1)-ых разрядов каждой (3. +1)-ой входной,шины 7, то есть ф 7 ..., 7 "(1„-1,2, ° ° °,п-1) .подключены к входу 2 1-ro разряда ,сумматора 2. Басод схема 3 сравнения подключен к выходу 9 регистрации конца переходного процесса в устройстве, а каждый одноразрядный вычитатель б выполнен в виде сумматора по модулю два.

Работу устройства для вычисления суввй квадратов K n-разрядных чисел

20 нли соответственно

Для увеличения надежности вычисления в устройстве путем реализации парал45 лельного контроля вычислительного

Выражение (3) положено в основу алгоритма параллельного функционирования предлагаемого устройства. поясним на примере реализации зыра.жения к к

:3 ххФ xх)х, 3=1 )=i 1 3 . предварительно представленногб в раэ5 . рядной форме s виде =.1 )(р;, 3 где

С

v 1 ф В1 ч i 2. Oll

1О х. х х.."х.; s<чз -.у (() разрядные векторы, представляющие собой разрядное изображение Xj, У у

9 — разрядная матх= рица, представ-лякицая собой разрядное изображение Х. при и 3.

Выражение (1) в развернутой фор25 ме при n=5 и К=З представляется в виде.

993256 третьего ч х,-х x ...х

4 значения

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

И 10 матрицы 1 из групп элементов И.

При этом значения разрядов Х - первого вектора Х поступают параллельно на вторые входы сумматоров по модулю два 12 схемы 3 сравнения соответствующих 1-х разрядов и на

2 вторые входы полусумматоров 5 также соответствующих 1-х разрядов ° После окончания переходного процесса в устройстве на выходах каждой строки групп элементов И 10 матрицы 1

ЗО из элементов И образуются в соответствии с выражением (3) частичные произведения, которые суммируются соответствующим одноразрядным суммато- ром 11 сумматора 2.После суммирования . 35 на выходах второго, четвертого, шестого, восьмого и десятого разрядов сумматора 2 образуются по выражению (4 и 5 соответственно.значения Б,84,Б,Б,Б

:поступающие на первые входы соответ4() стнующих разрядов полусумматорон 5 и первые входы соответствующих одноразрядных вычитателей 6. На выходах полусумматоров 5 по выражению (ф образуются зна ения разрядов Г, у, 45 у, у искомого вектора у, поступающие соответственно на вторые входы одно- разрядных нычитателей б,в которых по ,выражению (6) реализуется нычисление соответственно разрядов Х Х,,>,фХ

О первого вектора Х,,и поступают на первые входы соответствующих разрядоэ схемы 3 сравнения. В схеме 3 сраннения реализуется сравнение заданного вектора Х с вычисленным в процессе решения вектора Х,(поступающего с выходов однозарядных вычитателей 6).Если векторы равны,то сумма квадратов и-разрядных чисел выполнена правиль о и на выходе элемента ИЛИ 4 схемы 3 авыения и,соответственно, выходе 9 о регистрации конца переходного процес са в устройстве вырабатывается сигнал, оповещающий,что операция выполнена правильно и переходной процесс в схеме закончен, а с выходной рины 8 можно

65 считывать искомый вектор у и на вход-

Таким образом, реализовав выражение (5), получаем сумму кнадратон, К и-разрядных чисел, а реализовав выражетйе вида

Х =398

)(„4 99 з" e

Х„=У 95 (6

x,-- УЮ Б где Я вЂ” знак, обозначающий сложение по модулю два .получаем век-, ( тор Х (обозначим его Х % — вычисленный), сравнивая который с заданным вектором Х„, определяем правильность. выполненйя операции, а в момент их равенства фиксируется момент ее окончания (т.е.момент конца переходного процесса в схеме1. При,этом знар pt 89& У ения раэрядон У,У,У У,У и разрядов, Г, Б, S Б определяются в процессе вычисления суммы квадратов К чисел, а Определение x„= „s соответствии с (6) (т.е. контроль вычислительного процесса) реализуется параллель но с вычислителем вектора у по вйражению (5) ° процесса (т.е. осуществления параллельной проверки ° правильности выполнения операции) и увеличения производительности путем фиксации момента конца выполнения операции суммы квадратов К и-разрядных чисел (т,е. переходного процесса в схеме) разрешаем выр вкение (3)„относительно значений Х вектора Х, а. л 1 а 4 1 1 х„у-(x,+ х,+ х„х,+х,х,+х,х,) = У-s

10 х,=У (4 +x )=3-7, (4) а 4 В где S Б, S Б Б — значения соответствующих булевых сумм в выражении

1 (4) с учетом значений переноса иэ мпадших разрядов н старшие.

B соответствии с выражением (4) выражение (3) может быть записано

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

На первую, вторую и третью входные шины T — 7 (1=1,2. ..п устройства, фиг. 1) подаются соответственно значения первого разрядного вектора. зС 1 1 и х„=х,x ...x„

1 1 1" 1 у второго . и

Х1 Х2 Х2 Х2

993256

10 ные шины 71,.можно подавать следующие

К чисел.

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

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

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

1. Устройство для вычисления сум- мы квадратов К и-разрядных чисел, содержащее группу элементов И и элемент ИЛИ, о т л к ч à ю щ е е с я тем, что, .с целью увеличения быстродействия и надежности вычислений, оио содержит группы элементов И, схему сравнения, сумматор, полусумматор и одноразрядные вычитатели, причем группы элементов И Образуют матрицу, каждый i-й столбец которой (где i=1 2,...,n-l) содержит i групп элементов И и сдвинут относительно (1-1)-го элемента И на один разряд вниз, (2) -1)-ые информационные входы (где =1, 2,...,X). групп элементов И i-ro.столбца матрицы объе динены и подключены к (1+1)-му разряду ) -й входной информационной шины, к i-му разряду которой подключены 2 )-е информацконные входы l.-й группы элементов И всех столбцов, информационные выходы групп элементов

И каждой S-й (где S=l,2,... 2n-3) строки матрицы соединены с информационным входом (8+1)-го разряда

Сумматора, информационный выход каждого 2 i-го разряда сумматора ,подключей "к первым,информационным входам i-го полусумматора и 1-го одноразрядного вычитателя, второй инФормационный вход i-го одноразрядного вычитателя подключен к информационному выходу i-ro полусумматора и соответствующего 2 i-му разряду информационной выходной шины, информационный выход 1-ro одноразрядного вычитателя соединен с первым информационным входом i-го разряда схе10 мы сравнения, второй вход которой подключен * второму информационному входу i-ro полусумматора к i-му разряду первой информационной входной шины, информационный выход каждого (5 (2 i-l) разряда (где 1=2,3,...п-l) сумматора соединен с входом (2i-1)го разряда информационной выходной шины старший разряд которой соединен с информационным. выходом эле2О мента ИЛИ, к первому и второму информационным входам которого подключены выходы переносов соответственно сумматора и полусумматора предыдущего разряда, выход переноса каждого (i+1)го полусумматора соединен с входом переноса сумматора последующего разряда, а выходы (1+1)-х разрядов каждой (y +1)-й входной информационной шины подключены к информационнОму входу 2 i-ro разряда сумматора,информационный выход схемы сравнения соединен с управляющим выходом устройства.

2. Устройство .по п. 1, о т л и.ч а ю щ е е с я тем, что каждая груп. па элементов И содержит К двухвходовых элементов И, причем первый информационный вход каждого -ro элемента И (где $ =1,2,...,К) соединен с (2 -1)-ым икформационнык входом

40 группы элементов И, второй информационный вход j-ro элемента И соединен с 2 3 -ым информационным входом .группы элементов И.

3. Устройство по п. 1, о т л и45 ч а ю щ е е с я тем, что схема сравнения содержит и сумматоров по модулю два и элемент ИЛИ, причем первый информационный вход 1-го сумматора по модулю два соединен с первым вы5().ходом i-го разряда схемы сравнения,. второй информационный вход i-ro сумматора по модулю два.соединен с вторым выходом i-ro разряда схемы сравнения, информационные выходы

55 сумматоров по модулю два соединены с соответствующими входами элемента.

ИЛИ, информационный выход которого соединен с выходом схемы сравнения.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР 9 717765 кл. G 06 F7/50 1980.

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

У 717759 кл. G 06 F 7/38,1980 (прототип) .

993256

Fg

7J

Составитель Венцель

Редактор С.Юско Техред Т.Фанта Корректор 8,, Шухта

Закаэ 429/65 Тираж 704 Подписное

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

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

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