Цифровое параллельное устройство для возведения в куб

 

ЦИФРОВОЕ ПАРАЛЛЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В КУБ, содержащее два сумматора, отличающ е ее я тем, что, с целью увеличения быстродействия, в него введены п-2 сумматора, п-1 сумматоров-вычитателей , п-1 коммутатор и ключ (п разрядность устройства), причем выходы каждого i-ro сумматора (i 1,2,...,п-1) соединение входами первой группы (i+1)-ro сумматора, выходы каждого i-ro сумматора-вычитателя подключены к входам второй группы i-ro сумматора и со сдвигом .на один разряд в сторону младших разрядов к входам первой группы (i+t)-ro сумматора-вычитателя,-входы первой группы п-го сумматора соединены с информационными входами первых групп коммутаторов с второго по (п-1)-и информационными входами первого коммутатора и подключены к входной шине устройства, которая соединена с входами второй группы п-го сумматора со сдвигом на один разряд в сторону старших разрядов, выходы п-го сумматора соединены с информационными входами вторьк групп коммутаторов с второго по i ( п-1)-и и с информационными входами первой группы первого коммутатора, (Л входы первой группы первого сумматора-вычитателя подключены со сдвигом на два разряда в сторону мпадших разрядов к входной шине устройства , (i+1)-й разряд которой соединен с управляющими входами i-ro сумматора , (i+1)-ro .сумматора-вычитасо теля и (i+1)-ro коммутатора, старО ) ший разряд входной шины соединен с 00 управлякяцими входами ключа, первоСП го сумматора-вычитателя и первого со коммутатора, выходы (n-l)-ro сумматора соединены с выходной шиной устройства.

(}9) (1})

У}1 4 G 06 F 7/552

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

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

РЕСПУБЛИК

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA

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

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

3CEC053HA%

,3,.;,",„, 13

ЬЧБ Лй 0 ТЕНА (2 1) 3782592/24-24 (22) 28.06.84 (46) 07.12.85. Бюл. № 45 (7 1) Институт проблем моделирования в энергетике АН УССР и Киевский . ордена Трудового Красного Знамени .институт инженеров гражданской авиации (72) В.И. Купреев, С.Е. Проз оров, А.И.Стасюк, Г.А.Трощенко, А.Б.Бабич и К.И.Рогозин (53) 681. 325 (088. 8) (56) Авторское свидетельство СССР № 924704, кл. G 06 F 7/552, 1982.

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

¹- 868755, кл. С 06 F 7/552, 1981.

{54) (57) ЦИФРОВОЕ ПАРАЛЛЕЛЬНОЕ УСТ. РОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В КУБ, содержащее два сумматора, о т л и ч а ющ е е с я тем, что, с целью увеличения быстродействия, в него введены и-2 сумматора, и-1 сумматоров-вычитателей, и-1 коммутатор и ключ (празрядность устройства), причем выходы каждого i-ro сумматора (i

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

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

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

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

Цель изобретения — увеличение быстродействия. .На чертеже показана схема цифроaofo параллельного устройства для

x.(g) х хч() ) 10

Представляют выражение (1) с учетом выражения (2) как у = %хх = 2 х%(" + 2 хх +

2Ъ ч ч (3) п ц и ч и (3) хх + ...:+ У хх

15 равенство (3) следукщие

Вводят в обозначения

-2 ч ч(1)

2 -хх

2 2 хчх(2)

2ь Оч(ь) хх

2-(и+2) v(a) хх

21 ч(1)! х х

2 х() х

2-2 чР З х х

2 (и-") х (и) х у = x3, 20 происходит следующим образом.

Представим выражение (1) в разрядной форме как

Р ч у=ххх ч

Тогда значение у может быть вычислено по следующим рекуррентным

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

Ю х=О;

2 х=1

2-" х(2) 2 х

2 " х()+

2-1 ч,(1) »

3 21ч

3.2 х

2-2 х("+

2 2 чх(ь)

2- 2 v (2) 2-С ч при

2 х=О > (i-1) ч ((.1) -Я1 ч х + 3 2 х

1-1 х= 1 при .

1-1 х = Оразрядная матрица, представляющая собой разрядные иэображения х при п=4 количестве разрядов представления информации.

Записывают произведение матрицы

Ч ч х на вектор х в развернутом виде

-(1-)) Ч (1-1) 2; Ч х -2 х

Цифровое параллельное устройство для возведения в куб функционирует следующим образом.

В исходном состоянии на входную

50 шину устройства 6 подается значение и 1 х = х х ... х, которое поступает на информационный вход ключа 5, первый вход и-го сумматора 2, со

55 сдвигом на один разряд в сторону старших разрядов на второй вход и-го сумматора 2, со сдвигом на два разряда в сторону младших разрядов, на (2) возведения в куб.

Предлагаемое цифровое параллельное устройство содержит и-1 сумматоров 1, )1-й сумматор 2, и -2 сумматоров-вычитателей 3, )1 †.1 коммутаторов 4, ключ 5, входную 6 и выходную

7 шины устройства.

Цифровое устройство для возведения в куб произвольного числа х, т.е. — + 2 х(")х1, (4) где х() формируются как 2 " х )= 2 х;

1196859 первый вход первого сумматора-вычитателя 3, на первые входы всех ком- 1 мутаторов 4, начиная с второго и на второй вход первого коммутатора 4.

Кроме того, значение старшего

t ч разряда х исходного вектора х подается на управляющие входы ключа

5, первого сумматора-вычитателя 3 и первого коммутатора 4, а значение каждого (i+ 1)-го разряда х исходного вектора подается соответственно на управляющие входы i-го сумматора

1, (i+!)-го сумматора-вычитателя 3 и (i+1)-го коммутатора 4. После этого в схеме устройства протекает пере- 15 ходной процесс, после окончания которого на выходе и-го сумматора 2 образуется значение Зх,"которое подается на вторые входы коммутаторов

4, начиная с второго, и на первый вход первого коммутатора 4.

Если значение первого разряда х ч вектора х равно единице х=1, то

v значение х поступает через ключ 5 . 25 со сдвигом на два разряда в сторону младших разрядов на первый вход первого сумматора 1, первый сумматорвычитатель 3 настраивается на сложение, благодаря чему на выходе его 3g по выражению (5) вычисляется значение 2 х 1= 2 х + 2 х, которое подается на второй вход первого сумматора 1, а первый коммутатор 4 настраивается на передачу информации

35 с второго входа на выход, при этом

v значение х поступает на второй вход первого сумматора-вычитателя 3 со сдвигом на четыре разряда в сторону младших разрядов..Когда х=О, то ключ 5 закрыт, первый сумматор-вычитатель,З настраивается на вычитание, а коммутатор

4 — на передачу информации с первого входа на выход. Далее, если х = 1, 2 то первый сумматор 1 настраивается на сложение, второй сумматор-вычитатель — на сложение, второй коммутатор 4 — на передачу информации с а второго входа на выход. Когда х = О, то первый сумматор 1 настраивается на передачу информаций с первого входа на выход, второй сумматор-вычитатель 3 — на вычитание, а второй коммутатор — на передачу информации с первого входа на выход. При этом с выхода второго коммутатора 4 значения х или Зх подается со сдвигом на шесть разрядов в сторону младших разрядов на второй вход второго сумматора-вычитателя 3, на первый вход которого подается значение 2 z х <з1 иэ выхода первого сумматора-вычитателя 3.

Во втором сумматоре-вычитателе

3 по выражению (5) вычисляется значение 2 x, поступающее на второй

2, Y(31 вход второго сумматора 1. В первом сумматоре 1 по выражению (4) определяется значение у = у + 2 х х ч -1 ч(2! z к ч . которое поступает на первый вход .второго сумматора 1. Аналогично в зависимости от значения i-ro разряда

С. вектора х, равному х = 1 или х = 0, (i-1)-й сумматор 1 настраивается на сложение или передачу информации с первого входа на выход, i-й сумматор-вычитатель 3 настраи1вается на сложение или вычитание и i-й коммутатор 4 на передачу ин— формации с второго или первого входов на выход. Благодаря этому значение х или Зх поступает со сдвигом на 2(i+ 1) разряда в c îðîíó младших разрядов с выхода i-го коммутатора и на второй вход i-го.сумматора-вычитателя 3.

В i-м сумматоре-вычитателе 3 по выражению (6) вычисляется значение 2("1х, поступающее на второй вход i-го сумматора 1. В (i-I) ì сумматоре 1 по выражению (4) опредеv ляется очередное значение у, поступакицее на первый вход i-го сумматора 1. В зависимости от значения

Ь-1 . n-1 мпадшего разряда х = 1, х = О на выходе (n-1)-ro коммутатора 4 образуется значение х или Зх, поступающее на второй вход (и-1)-ro сумматора-вычитателя 3.

В (n-1)-м сумматоре по выражению (6) вычисляется значение 2 " " х ", поступающее на второй вход (n-1)-го сумматора 1. При х = 1 (n-1)-й сумматор 1 настраивается на сложение, когда х = Π— на величину информации из первого входа на выход. При этом в (n-1)-м сумматоре 1 по выражению (4) вычисляется искомое значение у = у = у„, + 2 х<"> х, которое поступает на выходную шину устройства 7.

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

Составитель Е.Максимова

Техред М.Надь Корректор М.Максимишинец

Редактор Н.Тупица

Подписное

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная, 4

Заказ 7564/47 . Тираж 709

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

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