Устройство для ускоренного умножения Советский патент 1980 года по МПК G06F7/39 

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

VI

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

Известны устройства для ут шожеяия, использующие алгоритмы уменьшений длины, анализа очередных ni разрядов, количества единиц и нулей регистра множителя 1,23,3.

Наиболее близким по технической сущности аналогом является устройство для ускоренного умножения 43, позволяющее наряду с устранением распространения переносов в каждом цикле умножать одновременно на четьфе разряда множителя. Это достигается за счет применения в арифметическом устройстве одноразрядных сумматоров на семь входов, что позволяет складывать одновременно до семи слагаемых. Устройство содержит сумматор, регистр множимого, регистр множителя, регистры запоминания сумм и поразрядных переносов, причем выход

суммы i -го разряда сумматора через схемы срвдаденйя И сборки подключен к ( i -1)-му и ( -1 -4)-му разрядам регистра айпоминания поразрядных сумм, выход перенос-двойка i -го разряда сумматора через схемы совпо.дп:ия и сборки подключен к i -му и ( i -3) разрядам репюТра запоминания пора ядных пёрёнОсов-двоек, выход переносчетверка 1 -го разряда сумматора через схемы совпадения и сборки соединен с ( 1 +1)-м и ( i -2)-м разрядами регистра запоминания поразрядных переносов-четверок, дополнительный выход суммы i -го разряда сумматора через

5 схему совпадения и сборки подключен ко входу i -го разряда регистра запомтгания сумм, а дополнительный выход перенос-двойка 1 -го разряда сумматора через схемы совпадения и сборки соединен с ( -J +1)-м разрядом сумматора и ( -i +1)-м разрядом регистра запоминания поразрядных перепосов-днэоск, nopnt.iA вход i -го разряда каждого сумматора соединен с выходом -j -го рафяда ре-- гистра запоминатта сумм, вторО11 ег6 вход соединен с выходом i-го разряда регистра запоминани5Г поразрядных переносов-четверок и дополнительным выходом переноса ( i -1)-го разряда сумматора, третий вход его соединен с выходом (i 4-1)-го разряда регистра запоминания поразрядных переносов-двоек, на четвертый, пятый, шестой и седьмой входы 1-го разряда сумматора подключены соответственно выходы i -го, ( i +1)го,- ( i +2)-го, {i +3)-го разрядов ре- , гистра множимого. Недостатком известного устройства является ограниченное быстродействие, вследствие неэффективного использования в нем одноразрядных сумматоров на семь входов. Целью предлагаемого изобретения является повышение быстродействия. Для достижения поставленной цели устройство для ускоренного умножения, содержаш:ее сумматор, построенный на основе одноразрядных семивходовьйс сумматоров, регистры множимого и множителя, регистры запоминания сумм и поразрядных пере носов, двоек и четвёрок, причем выход суммы 1 -го разряда сумматора подключен к ( 1 -1)-му разряду регистра запоминания сумм, выход перенос-двойка i -го разряда сумматора подключен к i -му разряду рехистра запоминания поР.,®Р °Я° ° ® Ь1ход переноЪ-чётверка i-го разряда сумматора соединен с ( i+1)-м разрядом регистра запоминания поразрядных переносов-четвёрок, дополнительный выход суммы -го разряда сумматора подключен ко входу i -го разряда регистра запоминания сумм, а дополнительный выход перенос-двойка i-гчэ разряда сумматора соединен с ( i +1)-м разрядом сум матора и ( i +1)-м раёрядб рёгйстра за помйнания . поразрядных переносов- двоек, первый вход i -го разряда сумматора соединен с выходом i -го разряда регистра запоминания сумм, второй его вход соединен с выходом -j -го разряда регистра запоминания поразрядных переносов-четверок и дополнительным выходом переноса ( 1 -1)-го разряда сумматЬра, третийВХ :)д Ш Ш еДИИен с выходом i -го раэряйа регистра запоминания поразрядных переносов-двоек, дополнительно содержит преобразователь кода, четьфе узла сдвига, элемент задержки, регистр множителя содержит до714395полнительный разряд, причем выходы младших восьми разрядов и дополнительного разряда регистра множителя подключены ко входам преобра:зователя кода, выход регистра множимого подключен к первым входам узлов сдвига, выходы каждых двух соседних разрядов преобразователя кода, начиная с младшего, подключены ко второмучи третьему входам соответствующих узлов сдвига, выход старшего разряда преобразователя кода подключен через элемент задержки ко входу младшего разряда преобразователя кода, выходы разрядов первого,четвертого узлов сдвига подключены соответственно к четвертому,седьмому входам 1-го разряда сумматора, выход суммы i -го разряда сумматора подключен ко входу ( i -8}-го разряда регистра запоминания сумм, выход перенос-двойка i -го разряда cyiviMaTOpa подключен ко входу { i -7)-го разряда регистра запоминания поразрядных переносов двоек, выход iiepeHOc- eTBepKa 1 -го,разряда сумматора соединен со входом ( i 6} го разряда регистра запоминания поразрядных переносов-четверок, На фиг. i приведенаструктурная схема устройства для ускоренного умножения одновременно на восемь разрядов множителя, на фиг. 2 изображен одноразрядный семивходовой сумматор. Устройство включает в себя регистр запоминания сумм с разрядами 1-9 (соответственно i -fS, i+7.., t+1, -f разряды регистра запоминания сумм); сумматор с разрядами 10-13 (соответственно i 4-1, i , -j l, i-2 разряды 1J. --сумматора); регистр запоминания поразрядных переносов-двоек с разрядами 1423 ( соответственно , -t +8, .....1+1 , 1 разряды регистра запоминаний поразрядных пероносов-двоек), регистр г запоминания поразрядных . переносовчетверок с разрядами 24-5 (соответственно 1+10, 1+9 1+1, 1 разряды регистра запоминания поразрядных переяо,сов-четверок 35-37 - триггеры, эле менты 38-4j ИЛИ ,элементы 42-51 И; регистр 52 множителя; преобразователь 53 кода; элемент 54 задержки-; узлы 55-58 сдвига; регистр 59 множимого; шину 60 передачи множимого на сумматор; трехвходовые сумматоры 61-64; -ый одноразрядный семивходо во и сумматор. 65; входные шины 66-72, сумматора 65; выходы 73-82 трехвходовых сумматоров сумматора 65; выходные шины 83-90 старших восьми разрядов регистра 52; выходную шину 91 регистра 52 (дополнительного разряда регистра 52); дополнительный выход 92 младшего разряда преобразователя 53; выходные шины 93-1ОО преобразователя 53 выходные шины 1О1-1О4 i-ых разрядов узлов 55-58 соответственно; управляющие шины 105-114 входные шины 115-117. i -ый одноразрядный семивходовой сумматор 65 (см, фиг, 2) состоит из четырех одноразрядных трехвходовых сум маторов 61-64 и имеет семь входных шин 66-72. Выход 73 перенос сумматора 61 соединен с одним из трех входов сумматора 63 и имеет также свобод ный выход 77 - дополнительный выход перенос сумматора 65. Выход 74 сумма сумматора соединен с одним из трех входов сумматора 64 и имеет свободный выход 8О - дополнительный выход сумма сумкттора 65. Выход 75 перенос сумматора 62 соединен со вто рым .входом сумматора 63, а выход 76 сумма сумматора 62 соединен со вторым входом сумматора 64. Выход 82 сумма сумматора 64 является выходом суммы сумматора 65. Выход 81 перенос сумматора 6 4 соединен с третьим входом сумматора 63. Выход 79 сумма сумматора 63 является выходом пере- нос - двойка сумматора 65. Выход 78 перенос сумматора 63 является выходом перенос - четверка сумматора 65. К триггеру 35 элемент 38 ИЛИ и элементы 42-44 И подключены соответственно дополнительный выход ВО сумма сумматора 65 ( i -ый разряд сумматора), выход 82 суммы сумматора 65 и выход 82 суммы ( i -8)-го разряда суммаггора (вход 115). Каждый разряд регистра запоминания сумм имеет структуру i -го разряда регистра 9, поэтому подключение каждогю из них аналогично описанному. К триггеру 36 через элемент 40 ИЛИ и элементы 47-48 И подклтрчены соответственно выход 79 перенос-двойка ( i -1)-го разряда сумматора (выход 79 разряда сумматора 12), дополнительный выход 77 перенос ( i -1)-го разряда сумматора (выход 77 разряда сумматора 12) и выход 79 переш с-двойка ( i -9)-го разряда сумматора (вход 116), Каждый разряд регистра запоминания переносов - двоек имеет ст1зук туру разряда 23 регистра запоминайся ,.

714395 поразрядных переносов - двоек поэтому подключение каждого из них аналогично описано. К триггеру 37 через элемент 41 ИЛИ и элементы 50-51 И подключены соответственно выход пеоенос-четверка {i -2}-го разряда сумматора (выход 78 разряда сумматора 13) и выход перенос - четверка ( i -10)-го разряда сумматора (вход 117), Каждый разряд регистра запоминания переносовчетверок имеет структуру разряда 34 регистра запоминания поразрядных переносов-четверок поэтому подключение каждого из них аналогично описанному. Входная шина 66 i -го разряда сумматора (разряд сумматора 11) подключен к выходу триггёра 35. Аналогично подключаются входньге шниы 66 всех разрядов сумматора к выходам триггеров регистра запоминания сумм, Входная шина 67 i -го разряда сумматора (разряд сумматора 11) через элемент 39 ИЛИ и элементы 45-46 И соединены соответственно с выходом триггера 37 и дополнительным выходом 77 перенос сумматора 12 ( i -1)-ый разряд cyMJvfaTOpa). Аналогично подключаются входные шины 67 всех разрядов сумматора. Входная шина 68 i -го разряда сумматора (разряд сумматора 11) подключена к выходу триггера 36. Аналогично подключаются входные шины 68 всех разрядов сумматора. К входным шинам 69, 70, 71 и 72 1 -го разряда сумматора (разряд сумматора 11) соответственно подключены входы 1-ых разрядов узлов 55-58 сдвига. Аналогично подключаются входные глины 69-72 всех разрядов сумматора. Выходы регистра 52 соединены с соответствующими входами преобразователя 53 кода. Выходы регистра 59 подключены к первым входам узлов 5558 сдвига. Выходы 93-1ОО соединены с вторым и третьим входами узлов 55-58 сдвига соответственно., Выход 92 преобразователя 53 кода подключен к входу элемента 54 задержки, выход которого оединен с входом старшего разряда пребразователя 53 кода. За исходное принимают такое состояние устройства, когда на регистры 59 ножимого и 52 множителя приняты .сответственно множ1смое и множитель. Умножение вьтолняется по алгоритму со сдвигом регистра множителя и суммы частичных произведений в сторону старших разрядов, причем Сдвиг сумыы частичных произведений производится посред ством определенным образом организованных связей между сумматором, каждый разряд которого построен на основе одноразрядного семивходового сумматора регистром запоминания сумм и регистрами запоминания поразрядных переносов двоек и четверок. В канодом цикле умножения с регистра 52 множителя на преобразователь 53 кода поступают восемь разрядов множителя. Преобразователь 53 кода представляет собой схему, построенную по следующим правилам. 1.Если данная цифра непреобразованноп множителя не совпадает с соседней справа его цифрой, соседняя рлева цифра есть О и предыдущая цифра преобразованного множителя есть О, то данный разряд преобразованного множителя должен содержать +1., . . 2.Если данная цифра непреобразованного множителя не совпадает с соседней справа его цифрой, соседняя слева пифра есть 1 и предыдущая цифра преобразованп ного множителя есть О, то данный разряд преобразованного множйтёлядолжён содержать 1. 3.Если данная цифра непреобразованного множителя совпадает с соседней справа его цифрой или. если предыдущая цифра преобразованного множзятеля не является нулем, то данный разряд в преобразованном мнонштеле есть О, По приведенным правилам можно записать следующие . лопгчёскйё уравнения Са„а„., «v, «vi-i v i v.-H h- n n- Vl°и-t il Vl п-а,а„,с VI О,1 7; th и tJ ветственно заначения 1 и 1 в данном разряде преобразованного множителя; С и Cji-n значения О соответственно в да1шом и предыдущем разрядах преобразованного множителя;0| И4{7 соответственно значения соседней слева, данной и соседней справа цифр непреобра зованного множителя. По уравнениям (1) строится каждый разряд восьмиразрядного преобразователя кода 53, выходными слгнапами которохч) являются значе ния t h Ьи- Младщий разряд преобразователя кода имеет дополнительный выход, значением которого является где о( чение старшего разряда следующей восьмиразрядной группы нспреобразоваиного 1иножителя. .чение Сд задержанное на один цикл работы устройства элементом 54 задержки, НеЬбходимо для формирования старшей цифры преобразованного множителя в очередном цикле работы устройства для ускоренного у иножения. При этом в (1) значение С предыдущего цикла является значением текущего цикла, а значением q текущего цикла является младшая из восьми цифр множителя, которые преобразовьгоались в предыдушем цикле. Для хранения а а. введен дополнительный разряд в регистре множителя. Таким образом, путем введения дополнительного разряда в регистр множителя 52 и элемента задержюи 54 в преобразователе кода 53 достигается наличие всех необходш ых значений, обеспечивающих работу преобразователя кода в каждом цикле умножения. П РИМ ер. Пусть множитель А OOllOlllllOOllOlOlllOOll. в соответствии с приведенными правилами преобразования множителя получаем в первом цикле старшксе восемь разрядов - преобразованного множителя О1001ООО.. При этом Ср О. Аналогично во втором и третьем циклах получаем соответственмо О1О10О 10,05-, О и1ОО1О101, CQ - 7f О. Таким образом, преобразованный множитель имеет вид 01оо1ооор1рГроГоГорГо1оГ. в результате преобразования множителя в соседних двух разрял х не могут появиться комбинации 11, 11, 11, 11. Поэтому в группе из восьми разрядов не может быть более четырех ненулевых разрядов. Следовательно, сумматор, позволяющий складывать одновременно семь слагаемых, может осуществлять умножение за один такт на восемь разрядов множителя. При этом множимое должно подаваться на сумматор в завксикюсти от значений преобра ванного множителя, сгруппированных по два соседних разряда; со сдвигом в сторону старших разрядов, определяемьгм весом разрядов преобразованного мнр.житёля прямым кодом, если в данном разряде преобразованного множителя 1, или дополнительным кодом, если в данном разряде преобразованного множителя 1. 97 Все перечисленные функции вьтолняют узлы 55-58 сдвига, работакщие в соответствии со следующим алгоритмом: узел сдвига 55 передает множимое на сумматор без сдвига или со сдвигом на один разряд в сторону старших прямым или дополнительным кодами; узел 56 сдвига передает множимое на суммато со сдвигом на два или три разряда в сторону старших прямым или дополнительным кодами; узел 57 сдвига передаёт множимое на сумматор со сдвигом на четыре или пять разрядов в сторону старш,их прямым или дополнительным кодами; узел 56 сдвига передает множимо на сумматор со сдвигом на шесть или семь разрядов в сторону старших прямым или дополнительными кодами, За один цикл умножения происходит умножение одновременно на восемь разр дов множителя. Все циклы, за исключением последнего, выполняются одинаково После вьшолнения каждого цикла происходит сдвиг числа в регистре множителя на восемь разрядов в сторону старших. В каждом цикле умножения на каждый разряд устройства поступают разрешающи потенциалы на управляющие шины 1О5, 1О8, НО, 113 и шину 6О передачи множимого на сумматор, при этом на: i -ый разряд сумматора 11 подаются поразрядная сумма с разряда 9 регистра запоминания сумм (входная шина б6 сумматора 65), поразрядный перенос двойка с разряда 23 регистра запомн- Ч нания поразрядных переносов (входная шина 68 сумматора 65), порязрядный перенос четверка с разряда 34 регистра запоминания поразрядных переносов-четверок через элемент 45 и элемент 39 ИЛИ (входная шина 67 сумматора 65), а на входные шины 69-72 сумматора 65 подаются значения с i -ых выходов узлов 55-58 сдвига соответственно ал- |Горитму их паботы. После суммирования семи слов: слова записанного в регистре запоминания сумм; слова, записанного в регистре запоминания поразрядных переносов - двоек слова, записанного в регистре запомйнания поразрядных переносов-четверок; четьфех слов, переданных узлами 55-58 сдвига соответственно,. получаем трехрядный результат, состоящий из поразряд ных сукол, которые записываются со сдвИ гом на восемь разрядов в сторону старших в регистр запоминания сумм (для i -го разряда сумматора с выхода 82 i5 сух-гматора 65 в разряд 1 регистра запоминания сумм, поразрядных переносовдвоек, которые записываются со сдвигом на девять разрядов в сторону старших в регистр запоминания поразрядных переносов - двоек (для 1-го разряда сумматора с выхода 79 сумматора 65 в разряд 14 регистра запоминания поразрядных переносов двоек поразрядных переносов-четверок, которые записываются со сдвигом на десять разрядов в сторону старших в регистр запоминания поразрядных переносов-четверок (для Ц -го разряда сумматора с выхода 78 сумматора 65 в разряд 24 регистра запоминаНИЯ поразрядных переносов - четверок. Описанный цикл работы устройства повторяется до последнего цикла умножения, В последнем цшсле умножения разрешающие потенциалы с шин 105, 110 и 113 снимаются (на указанные шины по- f ступают : запрещающие потенциалы), а на шины 106, 112, 114 поступают разрешающие потенциалы, при этом поразрядные суммы записываются в тот же разряд регистра запоминания сумм (для iго разряда сумматора с выхода 82 на вход элемента 43 И разряда 9 регистра запоминания сумм, поразрядные переносыдвойки записываются со сдвигом на один разряд в сторону старших (для i -го разряда сумматора с выхода 79 сумматора 65 в разряд 22 регистра запоминания поразрядных переносов двоек, поразрядные переносы-четверки записываются со сдвигом на два разряда в сторону Старших в регистр запоминания поразрядных переносов-четверок (для i -го разряда сумматора с выхода 78 cy tмaтopa 65 в разряд 32 регистра запоминания поразрядных переносов - четверок. В результате вьшолнения последнего цикла умножения получен трехрядный результат, состоящий из поразрядных сумм, поразрядных переноров-двоек и поразрядных переносов-четверок, поэтому необходимо получить однорядный результат. Это осуществляется в устройстве путем получения вначале двухрядного результата, состоящего из поразрядных сумм и порао-. рядных переносов-двоек, а затем однорядного, представляющего собой произведение, следующим образом. С шин 106, 60, 112 и 114 разрешающие потенциалы ск л счются и нп }1их поступает запрещающий потенциал, а на ишны 111 и 1О7 подастся разрешающий потенциал. В результате регистр 3anoN(H-

11 яания поразрядных переносо з-чётверок и входные.шины 69-7S каждого разряда сумматора от прк&лв информации отклк чаются, при этом поразрядные суммы записываются в тот же разряд регистра запоминания сумм (для i что разряда сумматора с вьиаэда 8О сумматора 65, порагзрядные перенос - двойки записы ваются со сдвигом ни один разряд в сторону старших в регистр запоминания поразрйдньгапереносов - двоек) для ( i -1) го разряда сумматора с выхода 77 разряда -регистра 12 в разряд 23 регистра и трехрадный резуттътатпереходит в двух рядный. Далее разрешающие потенциалы 1 с шш 1О8 и 111 снимаются (на указан ные шины поступает запрещающий потенцийл), а.на шину 1О9 подается разрешаю П1ИЙ потенциал. В результате |)ai3peniaeTся распространение переносов по цепи распространения переносов (для 1-го разряда сумматора с выхода 77 ( i -1)го разряда сумматора через„ элетлент 46 И и элемент 39 ИЛИ на в±од 67 сумматора 65), а в регистр запоминания сумм еапнсйгваются поразрядные суммы (для t1 -ГО разряда сумматора с выхода 8О „сумматора 65). Таким образом двухряднь1Й резутштат перещея в однорёд ный, представляющий произведение, пос; ле тогоразре1а Ь1Шё:ШтеШнаш Г 107 и 1О9 снимаются и на этом процесс ЙШ шйязаканчивается. В р йстре запоминаний сумм получено произведе; вне. Этшл достигается пговышениё бысэродействйй устройства для ycEOpeHi 5ro умножения.J Испрльзованйё восьмщэазряднрго нреобразователя кода, четьфех узлов сдвига элемвйта задержки и дополнительного разряда и регистра множителя делает воэулЬжным создание устройства для уско ренного умножения, позволякйдего наряду с устранением раснространшия переносов в каждом цикле умножать одновременно на восемь разрядов множителя, что повы шает быстродействие устройства. - ; . Фор мула изобр е т е н и я Устройство дляусгаэренного умноження, содержащее сумматор, построенный на основе одноразрядных соугивходовых сумматоров, регистры М1н жимого н мж жителя; регистры запоминания сумм и по разрядных переносов-двоек н четвёрок.

714395

12 причем выход сук-гмы i -го разряда сумматора ( -i -1,..,, ц, где и -разрядность операндов) подключен к ( -i -l) му разряду регистра запоминания сумм, выход перенос - двойка i -го разряда сумматора подключен к 1-му разряду регистра запоминания поразрядных переносов - двоек, выход перенос - четверка i -гю разряда сумматора соединен с ( -i ч-1)-м разрядом регистра запоминания поразрядных переносов-четверок, дополнительный выход суммы -го разряда сумматора подключен ко входу 4 -го разряда регистра запоминания сумм, а дополнительный выход переносдвойка i -го разряда сумматора соединен с ( i -1-1)-м разрядом сумматора и ( i -5-1) -м разрядом регистра запоминания поразрядных переносов-двоек, первый вход i -го разряда сумматора соединен с выходом -1 - го разряда регистра запоминания сумм, второй его вход соединен с вьцходом 1-го разряда регж;тра запоминания поразрядных переносов - четверок и дополнительным выходом переноса ( i -1-)-го разряда сумматора, третий вход его соединен с выходсял i -го разряда регистра, запоминания поразрядных переносов - двоек, о Тл и ч а ю щ е е с я тем, что, с «елью повышения быстродействия, устройство содержит преобразователь кода, чеTbipe узла сдвига, элемент задержки регистр множителя содержит дополнительный разряд, причем выходы младших восьми разрядов и дополнительного регистра множителя подключены ко входам преобразователя кода, выход регистра множимого подключен к первым входам узлов сдвига, выходы каждых двух соседних разрядов преофазователя кода, начиная с младшего, подключены ко второму и третьему входам соответствующих узлов сдвига, выход старшехх разряда преобразователя кода подключен через элемент задержки ко входу младшего разряда преобразователя кода выходы t -X разрядов первого - четвертого узлов сдвига подключены соответственно к четвертому - седьмому входам i -го разряда сумматора, выход суммы lr.ro разряда сумматора подключен ко входу ( i - 8)-го разряда регистра запо.инания сумм, выход перенос-двойка i -тхэ разряда сумматора подключен ко входу ( 1 -7)-го разряда регистра запомина,ния поразрядных перекосов-двоек, пыхол перегюс-четверка i -го разрядо сум13714395матора соединен со входом ( { -6)-го разряда регистра запоминания поразрядных переносов-четверок. Источники информации, принятые во внимание при экёпертизе 1. Авторское свидетельство СССР NO 269607, кл. Q 06 F 7/52, 1968. № № № (пр 2.Авторское свидетельство СССР 482740, кл. G 06 F 7/52, 1973. 3.Авторское свидетельство СССР 255648, кл. Q 06 F 7/54, 1967. 4.Авторское свидетельство СССР 281ОО4, кл. G Об F 7/39, 1968 ототип).