Устройство для ускоренного умножения

Устройство для ускоренного умножения

Иллюстрации

Показать все

Реферат

 

O n И Щ :-Й-" И-Е

ИЗОВРЕТЕН ИЯ

t !

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

Социалистических республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (63) Дополнительное к авт. свкд-ву (22) Заявлено 03.05.77 (2l ) 2483624/18 24 с присоединением заявки М (51)M. Кл.

6 06 Г 7/39 еееудератеевее комитет

С66р во йелек взабретекий к етерыпгв (23) Приоритет

Опубликовано 05.02.80. Бюллетень J%5 (53 у УДК 681.325..57(088.8) Дата опубликования описания 08.02.80

Ъ

А. К. Горшков, B. A. Лесников, Е. П. Петров и А. B. Частиков (72) Авторы изобретения

Кировский политехнический институт (71) Заявитель

I (54) УСТРОЙСТВО ДЛЯ УСКОРЕННОРЭ УМНОЖЕНИЯ

»

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

Известны устройства для умножения, используюшие алгоритмы уменьшения длины, анализа очередных )ег разрядов, количества единиц и нулей регистра множителя Щ2ЦЗ)

Наиболее близким по технической сушности аналогом является устройство для ускоренного умножения (41 ïîçâîëÿþшее наряду с устранением распространения переносов в каждом цикле умножать

l5 одновременно на четыре разряда множителя. Это достигается за счет применения в арифметическом устройстве одноразрядных сумматоров на семь входов, что позволяет складывать одновременно до семи слагаемых. Устройство содержит сумматор, регистр множимого, регистр множителя, регистры запоминания сумм и поразрядных переносов, причем выход суммьг 6 -го разряда сумматора через схемы совпадения и сборки подключен к (1 -1)-му и (1-4}-му разрядам ре- гистра запоминания поразрядных сумм, выход "перенос-двойка" j -го разряда сумматора через схемы совпал. .;ия и сборки подключен к г -му и (j -3)-му разрядам регистра запоминания поразрядных переносов-двоек, выход переносчетверка i -го разряда сумматора через схемы совпадения и сборки соединен с (1 +1)-м. и (j -2)-м разрядами регистра запомичания поразрядных переносов-четверок, дополнительный выход суммы j -го разряда сумматора через схему совпадения и сборки подключен ко входу i -го разряда регистра запоминания сумм, а дополнительный выход перенос-двойка 1 -ro разряда сумматора через схемы совпадения и сборки соединен с (3 +1)-м разрядом сумматора и (i +1)-м разрядом регистра запоминания поразрядных переносов-двоек, перпый вход i -го разряда каждого сумматора з соединен с выходом j -го разряда ре-- гистра запоминания сумм, второй его вход соединен с выходом . j -го разряда регистра запоминания поразрядных переносов-четверок и дополнительным выходом переноса (i -1)-го разряда сумматора, третий вход его соединен с выходом (a +1)-го разряда регистра запоми-нания поразрядных переносов-двоек, на четвертый, пятый, шестой и седьмой входы 1 --го разряда сумматора подключены соответственно выходы j -го, (g +1)го,. (1 +2) -го, (1 +3) -го разрядов регистра множимого.

Недостатком известного устройства является ограниченное быстродействие, вследствие неэффективного использования в нем одноразрядных сумматоров на семь входов., Целью предлагаемого изобретения является повышение быстродействия. Для достижения поставленной пели устройство для ускоренного умножения, содержащее сумматор, построенный на основе одноразрядных семивходовых сумматоров, ре, гистры множимого и множителя, регистры запоминания сумм и поразрядных переносов, двоек и четверок, причем выход суммы i -го разряда сумматора подклю- чен к (1 -1)-му разряду регистра запоминания сумм, выход "перенос-двойка"

1 -го разряда сумматора подключен к --му разряду per истра запоминания поразрядных переносов-двоек, выход перенос-четверка i -го разряда сумматора соединен с (i +1)-м разрядом регистра эапоминайия поразрядных переносов-чет- верок, дополнительный вйход суммы

3 -го разряда сумматора подключен ко входу 1 -го разряда регистра запоминания сумм, а дополнительный вйход перенос-двойка 1 -го разряда сумматора соединен с (1 +1)-м разрядом сумматора и (1 +1)-и разрядом регйстра запоминания поразрядных переносовдвоек, первый вход 1 -го разряда сумматора соединен с выходом 1 -го разряда регистра запоминания сумм, второй его вход соединен с выходом j -го разряда регистра запоминания поразрядных переносов-четверок и дополнительным выходом переноса (1 — 1)-го разряда сумматора, третий вход eie соединен с выходом i -го разряда регистра за- поминания поразрядных переносов-двоек, дополнительно содержит преобразователь кода, четыре узла сдвига, элемент задержки, регистр множителя содержит до4 395

4 полн" ьный разряд, прием выходы младших восьми разрядов и дополн ного разряда регистра множителя подключены ко входам преобразователя хода,. выход регистра множимого подключен к первым входам узлов сдвига, выходы каждых двух соседних разрядов преобразователя кода, начиная с младшего, подключены ко второму-и третьему входам соот10 ветствуюших узлов сдвига, выход старшего разряда преобразователя кода подключен через элемент задержки ко входу младшего разряда преобразователя кода, выходы 1 = X разрядов первого, четвертого

15 узлов сдвига подключены соответственно к четрертому,седьмому входам 1 -го разряда сумматора, выход суммы 1-го. разряда сумматора подключен ко входу (1 -8)- ж разряда регистра запоминания

20 сумм, выход "перенос-двойка" s -го разряда сумматора подключен ко входу (j -7)-го разряда регистра запоминания поразрядных переносов двоек, выход перенос-четверка 1 -го разряда сумматора соединен со входом (1 -6)-го разряда регистра запоминания поразрядных переносов-четверок.

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

Устройство включает в себя регистр запоминания сумм с разрядами 1-9 (соответственно 1 +8, j +7,.....;., j +1, 1 разряды регистра запоминания сумм); сумматор с разрядами 10-13 (соответственно 1+1, i, j -1, 1-2 разряды сумматора); регистр запоминания пораз40 рядных переносов-двоек с разрядами 14° 23 (соответственно 1+ 9, 4 +8, .... .1+1, 1 разряды регистра запоминаний поразрядных переносов-двоек), регистр запоминания поразрядных переносовчетверок с разрядами 24-34 (соответственно 1+10, 1+9,....., 1+1, 1 разряды регистра запоминания поразрядных переносов-четверок 35-37 — триттеры, элементы 38-41 ИЛИ;элементы 42-51 И; регистр 52 множителя; преобразователь

53 кода; элемент 54 задержки-; узлы

55 58 сдвига; регистр 59 множимого;

; шину 6О передачи множимого на сумматор; трехвходовые сумматоры 61-64;

55 q -ый одноразрядный семивходовой сумматор 65; входные шины 66-72, сумматора 65; выходы 73-82 трехвкодовых сумматоров сумматора 65; выходные

714395

5 шины 83-90 старших восьми разрядов регистра 52; выходную шину 91 регистра 52 (дополнительного разряда регистра 52); дополнительный выход 92 младшего разряда преобразователя 53; выходные шины 93-100 преобразователя 53; выходные шины 101-104 j ых разря-дов узлов 55-58 соответственно; управляющие шины 105-114, входные шины 1 15-1 1 7.

1 -ый одноразрядный семивходовой сумматор 65 (см. фиг. 2) состоит из четырех одноразрядных трехвходовых сумматоров 61-64 и имеет семь входных шин 66-72. Выход 73 "перенос сумматора 61 соединен с одним из трех входов сумматора 63 и имеет также свободный выход 77 — дополнительный выход

"перенос" сумматора б5. Выход 74

"сумма" сумматора соединен с одним из трех входов сумматора 64 и имеет сво. бодный выход 80 — дополнительный выход "сумма сумматора 65. Выход 75 перенос" сумматора 62 соединен со вторым входом сумматора 63, а выход 76 сумма сумматора 62 соединен со вторым входом сумматора 64. Выход 82, сумма сумматора 64 является выходом суммы сумматора 65. Выход 81 переНос сумматора 64соединен с третьим входом сумматора 63. Выход 79 сумма сумматора 63 является выходом перенос — двойка" сумматора 65. Выход 78 перенос сумматора 63 является выходом перенос — четверка" сумматора 65. З5

К триггеру 35 через элемент 38

ИЛИ и элементы 42-44 И подключены соответственно дополнительный выход 80

"сумма сумматора 65 ((-ый разряд " сумматора), выход 82 суммы сумматора

65 и выход 82 суммы (1 -8)-го разряда сумматора (вход 115). Каждый разряд регистра запоминания сумм имеет структуру j -го разряда регистра 9, поэтому подключение каждого из них ана15 логично описанному.

К триггеру 36 через элемент 40 ИЛИ и элементы 47-48 И подключены соот- ветственно выход 79 перенос-двойка (1 -1)-го разряда сумматора (выход

79 разряда сумматора 12), дополнительный выход 77 перенос" (1 -1)-го разряда сумматора (выход 77 разряда сумматора 12) и выход 79 перенос-двойка (i - 9)-го разряда сумматора (вход 116). Каждый разряд регистра запоминания переносов — двоек имеет структуру разряда 23 регистра запоминания

6 поразрядных переносов — двоек поэтому подключение каждого из них аналогично описано.

К триггеру 37 через элемент 41

ИЛИ и элементы 50-51 И подключены соответственно выход "перенос-четверка (-2)-го разряда сумматора (выход

78 разряда сумматора 13) и выход перенос — четверка (1 -10)-го разряда сумматора,(вход 117). Каждый разряд регистра запоминания переносовчетверок имеет структуру разряда 34 регистра запоминания поразрядных переносов-четверок поэтому подключение каждого из них аналогично описанному.

Входная шина 66- 1 -го разряда сумматора {разряд сумматора 11) подключен к выходу триг1 ера 35. Аналогично под-. ключаются входные шины 66 всех разрядов сумматора к выходам триггеров регистра запоминания сумм.

Входная шина 67 -го разряда сумматора (разряд сумматора 11) через элемент 39 ИЛИ и элементы 45-46 И соединены соответственно с выходом триггера 37 и дополнительным выходом

77 перенос" сумматора 12 (1 -1)-ый разряд сумматора) . Аналогично подключаются BxogBble шины 67 всех разрядов сумматора.

Входная шина 68 1 -го разряда сумматора (разряд сумматора 11) подключена к выходу триггера 36. Аналогично подключаются входные шины 68 всех разрядов сумматора.

К входным шинам 69, 70, 71 и 72

1 -го разряда сумматора (разряд сумматора 11) соответственно подключены входы 1- ых разрядов узлов 55-58 сдвига. Аналогично подключаются входные шины 69-72 всех разрядов сумматора.

Выходы регистра 52 соединены с соответствукяпими входами преобразователя 53 кода. Выходы регистра 59 подключены к первым входам узлов 5558 сдвига. Выходы 93-100 соединены с вторым и третьим входами узлов 55-58 сдвига соответственно. Выход 92 преобразователя 53 кода подключен к входу элемента 54 задержки, выход которого соединен с входом старшего разряда прсобраэователя 53 кода.

За исходное принимают такое состояние устройства,: когда на регистры 59 множимого и 52 множителя приняты соответственно множимое и множитель. Умножение выполняется по алгоритму со

714395 с п=с пс»п < сдвигом регистра множителя и суммы частичных произведений в стогону старших разрядов, причем сдвиг суммы частичных произведений производится посредством определенным образом организованных связей между сумматором, каждый разряд которого построен на основе одноразрядного семивходового сумматора, регистром запоминания сумм и регистрами запоминания поразрядных переносов двоек и четверок. В каждом цикле умножения с регистра 52 множителя на преобразователь 53 кода поступают восемь разрядов множителя. Преобразователь 53 кода представляет собой схему, построенную по следующим правилам.

1. Если данная цифра непреобразованного множителя не совпадает с соседней справа его цифрой, соседняя слева цифра есть О и предыдущая цифра преобразован- 0 ного множителя есть О, то данный разряд преобразованного множителя должен содержать +1.

2. Если данная цифра непреобразованного множителя не совпадает с соседней справа его цифрой, соседняя слева цифра есть 1 и предыдущая цифра преобразован ного множителя есть О, то денный разряд преобразованного множителя должен содержать i. зо

3. Если данная цифра непреобразованного множителя совпадает с соседней справа его цифрой или если предыдущая цифра преобразованного множителя не является нулем, то данный разряд в преобразованном множителе есть 0. !

По приведенным правилам можно записать следующие логическйе уравнения: I

40 и И- » И И-1»»+ 1 >+"

=(5, „ с»,„» „,,)с»„,„с „+.» где ll = 0,1,........, 7; Ъп и Ъ » соответственно заначения 1 и 1 в данном разряде преобразованного множителя;

С> и С и+ „— значения О соответственно в данном и предыдущем разрядах преобразованного множителя;Ql и+, ц и,с ° соответственно значения соседней слева, данной и соседней справа цифр непреобразованного множителя. По уравнениям (1) строится каждый разряд восьмиразрядного преобразователя кода 53, выходными сигналами которого являются значения Ф » и Ъ ». Младший разряд преобразователя кода имеет дополнителЬный выход, энечепием которого является

Со= с» с» м с ., где чение старшего разряда следующей восьмирезрядной группы непреобрезованного множителя. Значение с, задержанное на один цикл работы устройства элементом 54 задержки, необходимо для формирования стершей цифры преобразованного множителя в очередном цикле работы устройства для ускоренного умножения. При этом в (1) значение C.ä предыдущего цикла является значением

С и.+» =. С текущего цикле, а значением ц = с» текущего цикла яви+»" 8 ляется младшая из восьми цифр множителя, которые преобразовывались в предыдущем цикле. Для хранения g =,с»

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

Пример. Пусть множитель А= .001101111100110101110011. B соответствии с приведенными правилами преобразования множителя получаем в

:первом цикле старшие восемь разрядов преобразованного множителя 01001000.

При этом C> = О. Аналогично во втором и третьем циклах получаем соответственно 010100 ХО, Сс,= 0 и 10010101, С© = Т фО. Таким образом, преобразованный множитель имеет вид

01001000010100101001010Г.

В результате преобразования множителя в соседних двух разрядах не могут появиться комбинации 11, li, 11, 11.

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

10

Все перечисленные функции выполняют узлы 55-58 сдвига, работакяцие в соответствии со следукяцим алгоритмом: узел сдвига 55 передает множимое на сумматор без сдвига или со сдвигом на

5 один разряд в c ãîðîíó старших прямым или дополнительным кодами; узел 56 сдвига передает множимое на сумматор со сдвигом на два или три разряда в сторону старших прямым или дополни- 1о тельным кодами; узел 57 сдвига передает множимое на сумматор со сдвигом на четыре или пять разрядов в сторону старших прямым или дополнительным кодами; узел 56 сдвига передает множимое 1s на сумматор со сдвигом на шесть или семь разрядов в сторону старших прямым или дополнительными кодами.

За один цикл умножения происходит умножение одновременно на восемь раэря- 30 дов множителя. Все циклы, за исключением последнего, выполняются одинаково, После выполнения каждого цикла происходит сдвиг числа в регистре множителя на восемь разрядов в сторону старших. 25

В каждом цикле умножения на каждый разряд устройства поступают разрешаКяцие потенциалы на управляюшие шины 105, 108, 110, 113 и шину 60 передачи множимого на сумматор, при этом на j -ый разряд сумматора 11 подаются поразрядная сумма с разряда 9 регистра запоминания сумм (входная шина 66 сумматора 65), поразрядный переносдвойка с разряда 23 регистра запоминания поразрядных переносов (входная шина 68 сумматора 65), порязрядный перенос четверка с разряда 34 регистра запоминания поразрядных переносов-четверок через элемент 45 . и элемент 39 4О

ИЛИ (входнея шина 67 сумматора 65), а на входные шины 69-72 сумматора 65 подаются значения с 1 -ых выходов узлов 55-58 сдвига соответственно ал-

;горитму их паботы.

После суммирования семи слов: сл ва, записанного в регистре запоминания сумм; слова, записанного в регистре запоминания поразрядных переносов — двоек; слова, записанного в регистре запоминания поразрядных переносов-четверок; четырех слов, переданных узлами 55-58 сдвига соответственно,.получаем трехрядиый результат, состояший из поразрядных сумм, которые записываются со сдви-

55 гом на восемь разрядов в сторону стар( шпх в регистр запоминания сумм (для

1 -го разряда сумматора с выхода 82 сумматора 65 в разряд 1 регистра запоминания сумм, поразрядных переносовдвоек, которые записываются со сдвигом на девять разрядов в сторону старших в регистр запоминания поразрядных переносов — двоек (для 1 — го разряда сумматора с выхода 79 сумматора 65 в разряд 14 регистра запоминания поразI рядных переносов двоек поразрядных пере.носов-четверок, которые записываются со сдвигом на десять разрядов в сторону старших в регистр запоминания поразрядных переносов-четверок (для я -го разряда сумматора с выхода 78 сумматора 65 в разряд 24 регистра запоминания поразрядных переносов — четверок.

Описанный цикл работы устройства повторяется до последнего цикла умножения, В последнем цикле умножения разрешающие потенциалы с шин 105, 110 и

113 снимаются (на указанные шины по- ступают . запрешаюшие потенциалы), а на шины 106, 112, 114- поступают разрешающие потенциалы, при этом поразрядные суммы записываются в тот же разряд регистра запоминания сумм (для 1го разряда сумматора с выхода 82 на вход элемента 43 И разряда 9 регистра запоминания сумм, поразрядные переносыдвойки записываются со сдвигом на один разряд В сторону ст&рших (для 1 -Го разряда сумматоре с выхода 79 сумматора 65 в разряд 22 регистра запоминания поразрядных переносов двоек, поразрядные переносы-четверки записываются со сдвигом на два разряда в сторону старших в регистр запоминания поразрядных переносов-четверок (для i -го разряда сумматора с выхода 78 сумматора

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

С шин 106, 60, 112 и 114 разрешаюшие потенциалы снимаются и на них поступает запрешаюший потенциал, а на шины 111 и 107 подается разрещаняпий потенциал. В результат» регистр запоми714395

11

HsHHH поразрядных переносов-четверок входные. шины 69-7ф каждого разряда сумматора от приема информации отклю чатотса при этОм ПОраэрядньте суммы за» писываются в тот же разряд регистра за5 поминания сумм (для т -го разряда сумматора с выхода В0 сумматора 65, поразрядные переносы - двойки записываются со сдвигом на один разряд в сторону старших в регистр эапомйнания по- î разрадньтхпереносов двоек) для т р 1) го .разряда сумматора с выхода 77 разряда -регистра 12 в разряд 2З регистра и трехрядный результат переходит в двухрядный. Далее разрешаюптие потенциалы È ! с шин 108 и 111 снимаются (на указан-" ные шины поступает запрещающий потенциал), а на шину 109 подается разрешаю, ший потенциал. В результате раэрешаетса распространение переносов но цепи 20 распространения переносов (дла :т - го разряда сумматора с выхода 77 (j -1)го разряда сумматора через элемент 46

И и элемент 39 ттЛИ на вход 67 сумматора 65), s a регистр запоминании сумм?5 записываются поразрядные суммы (дла т -го разряда сумматора с выхода ЗО ,. сумматора 65) . Таким образом двухрадньтй результат перешел в однорадный, представляющий собой произведение, пос-; >0 ле чего разрешатфттие пдтей»пиалы с шии

107 и 109 снимаются и на этом процесс Ф4тХожениа заканчйвается. В регистре запоминания сумм получено произведение. -: З5

Этим достигаетса повьппение быс

ТРО действиа устройства дла ускоренного умнОж ения.

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

-» ъ =.=

И

Формула изобретении причем выход суммы j -го разряда сумматора (i -1, тт, где и -разрядность операндов) подключен к (1 -l) му разряду регистра запоминания сумм, выход "перенос — двойка" -го разряда сумматора подключен к т -му разряду регистра запоминания поразрядных переносов — двоек, выход "перенос — четВерка j -го разряда сумматора соединен с (1 +1)-м разрядом регистра запоминания поразрядных переносов-четверок, дополнительный выход суммы g-го разряда сумматора подключен ко входу

i -го разряда регистра запоминания сумм, а дополнительный выход " переносдвойка" i -го разряда сумматора соединен с (т +1)-м разрядом сумматора и (1 +1)-м разрядом регистра запоминания поразрядных переносов двоек, первый вход т -го разряда сумматора соединен с выходом т- го разряда регистра запоминания сумм, второй его вход соединен с выходом > - го разряда регистра запоминания поразрядных переносов - четверОк и дополнительным выходом переноса (т -1-)-го разряда сумматора, третий вход его соединен с выходом i -го разряда регистра, запоминания поразрядных переносов — двоек, о т л и ч а то m е е с я тем, что, с целью повышения быстродействия, устройство содержит преобразователь кода, четыре узла сдвига, элемент задержки регистр множителя содержит дополнительный разряд, причем выходы младших вось» ми разрядов и дополнительного разряда регистра множителя подключены ко входам преобразователя кода, выход регистра множимого подключен к первым входам узлов сдвига, выходы каждых двух соседних разрядов преобразователя кода, начиная с младшего, подключены ко второму и третьему входам соответствующих узлов сдвига, выход старшего разряда преобразователя кода подключен через элемент задержки ко входу младшего разряда преобразователя кода, выходы

j --х разрядов первого — четвертого узлов сдвига подключены соответственно к четвертому — седьмому входам 1 -го разряда сумматора, выход суммы т- го

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

as основе одноразрядных семивходовых,5З сумматоров, регистры множимого и множителя; регистры запоминании сумм и по- . разрядных переносов-двоек и четверок, разряда сумматора подключен ко входу (< — 8)-го разряда регистра зало ..шнания сумм, выход перенос-двойка 1 -го разряда сумматора подключен ко входу (1 -7)-го разряда регистра запоминания пораэряднъrx переносов-двоек, выхоп перенос-четверка» 1 -го разряд» су.л714395

77 73 79 И рог 7

IIHHHllH Заказ 9289/46 Тираж 751

Г! одп ясно е

Филиал ППП "Патент", г. Ужгород, ул. ЛГюектная, 4 е матора соединен со входом (j -6)-го разряда регистра запоминания поразрядных переносов-четверок.

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

1. Авторское свидетельство СССР № 269607, кл. G 06 F 7/52, 1968.

2. Авторское № 482740, кл.

3. Авторское № 255648, кл.

4. Авторское

¹ 281004, кл. (прототип) . свидетельство СССР

G 06 F 7/52, 1973. свидетельство СССР

5 06 F 7/54, 1967. свидетельство СССР

G 06 Р 7/39, 1968