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

(51)М, Кд. Я 06 Г 7/39 ВоудеротоенеИ комитет иср ао делам изобретений к открыткиДата опубликования описания 08,02,80 А. К. Горппюв, В. А, Лесников, Е. П. Петров и А, В. Частиков(72) Авторыизобретения Кировский политехнический институт(54) УСТРОЙСТВО ДЛЯ УСКОРЕННОРЭ УМНОЖЕНИЯ ФИзобретение относится к области вычислительной техники и может найти при-,менение в арифметических устройствйсцифровых вычислительных машин и в цифровых фильтрах.Известны устройства для умножения,используюшие алгоритмы уменьшенйядлины, анализа очередных гп разрядов,количества едгпгиц и нулей регистра множителя Щ 2 Ц 31,Наиболее близким по технической сущности аналогом является устройство дляускоренного умножения 41,позволяющее наряду с устранением распространения переносов в каждом цикле умножать5одновременно на четыре разряда множителя. Это достигается за счет применения в арифметическом устройстве одноразрядных сумматоров на семь входов,что позволяет складывать одновременнодо семи слагаемых, Устройство содержитсумматор, регистр множимого, регистрмножителя, регистры запоминания сумми поразрядных переносов, причем выход суммьг 1 -го разряда сумматора черезсхемы совпаденияи сборки подключен к( 1 -1)-му и ( 1-4)-му разрядам ре-гистра запоминания поразрядных сумм,выход "перенос-двойка" 1 -го разрядасумматора через схемы совпат.;ия исборки подключен к г -му и ( т -3)-муразрядам регистра запоминания поразрядных переносов-двоек, выход переносчетверкв-го разряда сумматорачерез схемы совпадения и сборки соединенс ( 1 +1)-м и (1 -2)-м разрядами регистра запомичания поразрядных переносов-четверок, дополнительный выход суммы 1 -го разряда сумматора черезсхему совпадения и сборки подключен ковходу 1-го разряда регистра запоминания сумм, а дополнительный выход "перенос-двойка 1 -го разряда сумматорачерез схемы совпадения и сборки соединен с ( 1+1)-м разрядом сумматора и( 4 +1)-м разрядом регистра запоминания поразрядных переносов-дюек, первыйвход 1 -го разряда каждого сумматора714 395 3соединен с выходом 1 -го разряда ре-. гистра запоминания сумм, второй-его вход соединен с выходом 1-го разряда регистра запоминания поразрядных переносов-четверок и дополнительным выходом переноса ( 1 -1)-го разряда сумматора, третий вход его соединен с выходом (1+1)-го разряда регистра заломи. нания поразрядных переносов-двоек, на четвертый, пятый, шестой и седьмой входы 1-го разряда сумматора подключены соответственно выходы 1 -го, ( 1 +1)- го, ( 1+2)-го, (1+3)-го разрядов регистра множимого.Недостатком известного устройства являетсяограниченное быстродействие, вследствие неэффективного использования в нем одноразрядных сумматоров на семь входов., Целью предлагаемого изобретения является повышение быстродействия. Для достижения поставленной цели устройство для ускоренного умножения, содержащее сумматор, построенный на основе одноразрядных семивходовых сумматоров, ре, гистры множимого и множителя, регистры запоминания сумм и поразрядных пере носов, двоек и четверок, причем выход суммы 1 -го разряда сумматора подклю чен к ( 1 -1)-му разряду регистра запоминания сумм, выход "перенос-двойка"1 -го разряда сумматора подключен к1 -му разряду ре 1 истра запоминания поразрядных переносов-двоек, выход перенос-четверка 1 -го разряда сумматора соединен с (+1)-м разрядом регистра эапоминайия поразрядных переносов-четверок, дополнительный вйход суммы1 -го разряда сумматора подключен ко входу 1 -го разряда регистра запоминания сумм, а дополнительный вйход перенос-двойка 1 -го разрядасумматора соединен с ( 1 +1)-м разрядом сум матора и ( 1 +1)-и разрядом регйстразапоминания поразрядных переносов- двоек, первый вход 1-го разряда сумматора соединен с выходом 1 -го разряда регистра запоминания сумм, второй его вход соединен с выходом 1 -го разряда регистра запоминания поразрядных переносов-четверок и дополнительным выходом переноса ( 1 - 1)-го разряда сумматора, третий ъход ая соединен с выходом 1 -го разряда"регистра за- поминания поразрядных переносов-двоек, дополнительно содержит преобразователь кода, четыре узла сдвига, элемент задержки, регистр множителя содержит до 4нтепьный разряд, причем выходыл 1 ладших восьми разрядов и дополниного разряда регистра множителя подключены ко входам преобразователя хода,ыход регистра множимОГО подключенпервым входам узлов сдвига, выходы каждых двух соседних разрядов преобразователя кода, начиная с младшего, подключены ко второму.и третьему входам соот 1 О ветствующих узлов сдвига, выход старшего разряда преобразователя кода подключен через элемент задержки ко входумладшего разряда преобразователя кода,выходы 1 =Х разрядов первого, четвертого15 узлов сдвига подключены соответственнок четрертому,седьмому входам 1 -горазряда сумматора, выход суммы 1-го.разряда сумматора подключен ко входу(1 -8)чо разряда регистра запоминания20 сумм, выход "перенос-двойка" 4 -горазряда сумматора подключен ко входу( 1 -7)-го разряда регистра запоминанияпоразрядных переносов двоек, выходЮперенос-четверка 1 -го разряда сум 25 матора соединен со входом ( 1 -6)-горазряда регистра запоминания поразрядных переносов-четверок,На фиг, 1 приведена структурная схема устройства для ускоренного умноже 30 ния одновремепно на восемь разрядовмножителя, на фиг. 2 изображен одноразрядный семивходовой сумматор.Устройство включает в себя регистрзапоминания сумм с разрядами 1-9 (соЗ 5 ответственно 1 +8, 1 +7,;., 1 +1,1 разряды регистра запоминания сумм);сумматор с разрядами 10-13 (соответственно 1+1, 1, 1-1, 1-2 разрядысумматора); регистр запоминания пораз 40 рядных переносов-двоек с разрядами 14 23 ( соответственно 1 ь 9, 1+8,.1+1, 1 разряды регистра запоминаний поразрядных переносов-двоек), регистрзапоминания поразрядных переносовчетверок с разрядами 24-Г 4 (соответственно 1+10, 1+9 1+1, 1 разрядырегистра запоминания поразрядных переносов-четверок 35-37 - триттеры, эле менты 38-41 ИЛИ;элементы 42-51 И;регистр 52 множителя; преобразователь53 кода; элемент 54 задержки-; узлы55-58 сдвига; регистр 59 множимого;; шину 6 О передачи множимого на сумматор; трехвходовые сумматоры 61-64;55 1 ый одноразрядный семивходовой сумматор 65; входные шины 66-72, сумматора 65; выходы 73-82 трехвкодовыхсумматоров сумматора 65; выходные714395 описано,1 О элемента 54 задержки, выход которогосоединен с входом старшего разряда преобрвэоввтеля 53 кода,Зв исходное принимают такое состояние устройства, " когда нв регистры 59 множимого и 52 множителя приняты соответственно множимое и множитель. Умножение выполняется по алгоритму со 5шины 83-90 старших восьми разрядов регистра 52; выходную шину 91 регистра 52 (дополнительного разряда регистра 52); дополнительный выход 92 младшего разряда преобразователя 53; выходные шины 93-100 преобразователя 53;выходные шины 101-104 1- ых разрядов узлов 55-58 соответственно; управляющие шины 105-114, входные шины 115-117.1 -ый одноразрядный семивходовойсумматор 65 (см. фиг. 2) состоит изчетырех одноразрядных трехвходовых сумматоров 61-64 и имеет семь входныхшин 66-72, Выход 73 "перенос сумматора 61 соединен с одним из трех входов сумматора 63 и имеет также свободный выход 77 - дополнительный выход"сумма" сумматора соединен с одним изтрех входов сумматора 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 ( 1 -ый разрядсумматора), выход 82 суммы сумматора4065 и выход 82 суммы ( 1-8)-го разряда сумматора (вход 115). Каждый разряд регистра запоминания сумм имеет структуру-го разряда регистра 9, поэтому подключение каждого из них вна 5 логично описанному.К триггеру 36 через элемент 40 ИЛИ и элементы 47-48 И подключены соот- м ветственно выход 79 перенос-двойками ( 1 -1)-го разряда сумматора (выход56 79 разряда сумматора 12), дополнительный выход 77 перенос" ( 1 -1)-го разряда сумматора (выход 77 разряда сумматора 12) и выход 79 перенос-двойка ( 1 -9)-го разряда сумматора (вход 116). Каждый разряд регистра запоминания переносов - двоек имеет структуру разряда 23 регистра запоминания 6поразрядных переносов - двоек поэтому подключение каждого из них аналогично К триггеру 37 через элемент 41 ИЛИ и элементы 50-51 И подключены соответственно выход "пеоенос-четверка ( 1 -2)-го разряда сумматора (выход 78 разряда сумматора 13) и выход "перенос - четверка" ( 1 -10)-го разряда сумматора (вход 117). Каждый разряд регистра запоминания переносов- четверок имеет структуру разряда 34 регистра запоминания поразрядных переносов-четверок поэтому подключение квждого из них анвюгично описанному.Входная шина 66 1 -го разряда сумматора (разряд сумматора 11) подключен к выходу триг 1 ера 35. Аналогично под-. ключаются входные шины 66 всех разрядов сумматора к выходам триггеров регистра запоминания сумм.Входная шина 67 1-го разряда сумматора (разряд сумматора 11) через элемент 39 ИЛИ и элементы 45-46 И соединены соответственно с выходом триггера 37 и дополнительным выходом 77 перенос" сумматора 12 ( 1 -1)-ый разряд сумматора), Аналогично подключаются входные шины 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 кода подключен к входу714395 ь О п и- ьсдвигом регистра множителя и суммы частичных произведений в стогону старших разрядов, причем сдвиг суммы частичных произведений производится посредством определенным образом организованных связей между сумматором, каждый разряд которого построен на основе одноразрядного семивходового сумматора, регистром запоминания сумм и регистрами запоминания поразрядных переносов 1 О двоек и четверок. В каждом цикле умножения с регистра 52 множителя на преобразователь 53 кода поступают восемь разрядов множителя, Преобразователь 53 кода представляет собой схему, построенную по следующим правилам.3 Если данная цифра непреобразованного множителя не совпадает с соседней справа его цифрой, соседняя слева цифра есть 0 и предыдущая цифра преобразован- о ного множителя есть О, то данный разряд преобразованного множителя должен содержать +1.2, Если данная цифра непреобразованного множителя не совпадает с соседней справа его цифрой, соседняя слева цифра есть 1 и предыдущая цифра преобразован ного множителя есть О, то данный разряд преобразованного множителя должен содержать 1.зо3. Если данная цифра непреобразованного множителя совпадает с соседней справа его цифрой или если предыдущая цифра преобразованного множителя не является нулем, то данный разряд в преобразованном множителе есть О.По приведенным правилам можно записать следующие логические уравнения: Ъ40 ь Споп- С и СС+ и+:( д Ч ОО )С 1 П, С+ где И = 0,1, 7 Ъи иЪ соответственно заначения 1 и 1 в данном разряде преобразованного множителя;С и СП+ - значения О соответственно в данном и предыдущем разрядах преобразованного множителя 6 и+,4 и,йи, соответственно значения соседней слева, данной и соседней справа цифр непреобразованного множителя. По уравнениям (1) строится каждый разряд восьмиразрядного преобразователя кода 53, выходными сигналами которого являются значения Ф и Ъ, Младший разряд преобразователя кода имеет дополнителЬный выход, эначепием которого является Со=со О 1 М С, где СМ- значение старшего разряда следующей восьмирвзрядной группы непреобразованного множителя. Значение С, задержанное на один цикл работы устройства элементом 54 задержки, необходимо для формирования старшей цифры преобразованного множителя в очередном цикле работы устройства для ускоренного умножения. При этом в 1) значение Со предыдущего цикла является значением С и.+ =. СЕ текущего цикла, а значением ц:ц текущего цикла явйЕ 1 8ляется младшая из восьми цифр множителя, которые преобразовывались в предыдущем цикле, Для хранения С 1 :, О1 В введен дополнительный разряд в регистре множителя, Таким образом, путем введения дополнительного разряда в регистр множителя 52 и элемента задержки 54 в преобразователе кода 53 дости-, гается наличие всех необходимых значений, обеспечивающих работу преобразователя кода в каждом цикле умножения.П р и м" е р. Пусть множитель А= ,001101111100110101110011. В соответствии с приведенными правилами преобразования множителя получаем в :первом цикле старшие восемь разрядов преобразованного множителя 01001000. При этом Со = О. Аналогично во втором и третьем циклах получаем соответственно 010100 ХО, С,= 0 и 1001010 Х, Со = 1 фО. Таким образом, преобразованный множитель имеет вид 01001000010100101001010 Г.В результате преобразования множителя в соседних двух разрядах не могут появиться комбинации 11, 11, 11, 11. Поэтому в группе из восьми разрядов не может быть более четырех ненулевых разрядов, Следовательно, сумматор, позволяющий складывать одновременно семь слагаемых, может осуществлять умножение за один такт на восемь разрядов множителя. При этом множимое должно подаваться на сумматор в зависимости от значений преобразованного множителя, сгруппированных по два соседних разряда; со сдвигом в сторону старших разрядов, определяемым весом разрядов преобразованного множителя прямым кодом, если в данном разряде преобразованного множителя 1, или дополнительным кодом, если в данном разряде преобразованного множителя 1.Все перечисленные функции выполняют узлы 55-58 сдвига, работающие в соответствии со следукяцим алгоритмом; узел сдвига 55 передает множимое на сумматор без сдвига или со сдвигом на5 один разряд в сторону старших прямым или дополнительным кодами; узел 56 сдвига передает множимое на сумматор со сдвигом на два или три разряда в сторону старших прямым или дополни тельным кодами; узел 57 сдвига передает множимое на сумматор со сдвигом на четыре или пять разрядов в сторону старших прямым или дополнительным кодами; узел 56 сдвига передает множимое 15 на сумматор со сдвигом на шесть или семь разрядов в сторону старших прямым или дополнительными кодами.За один цикл умножения происходит умножение одновременно на восемь раэря дов множителя. Все циклы, за исключением последнего, выполняются одинаково, После выполнения каждого цикла происходит сдвиг числа в регистре множителя на восемь разрядов в сторону старших. 25В каждом цикле умножения на каждый разряд устройства поступают разрешаЮщие потенциалы на управляющие шины 105, 108, 110, 113 и шину 60 передачи множимого на сумматор, при этом на1 -ый разряд сумматора 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 регистра запоминания пораз/рядных переносов двоек поразрядных переносов-четверок, которые записываются сосдвигом на десять разрядов в сторонустарших в регистр запоминания поразрядных переносов-четверок (для д -горазряда сумматора с выхода 78 сумматора 65 в разряд 24 регистра запоминания поразрядных переносов - четверок,Описанный цикл работы устройстваповторяется до последнего цикла умножения,В последнем цикле умножения разрешающие потенциалы с шин 105, 110 и113 снимаются (на указанные шины по-ступают запрещающие потенциалы), ана шины 106, 112, 114 поступают разрешающие потенциалы, при этом поразрядные суммы записываются в тот же разряд регистра запоминания сумм (для 1 го разряда сумматора с выхода 82 навход элемента 43 И разряда 9 регистразапоминания сумм, поразрядные переносыдвойки записываются со сдвигом на одинразряд в сторону старших (для 1 -горазряда сумматоре с выхода 79 сумматора 65 в разряд 22 регистра запоминания поразрядных переносов двоек, поразрядные переносы-четверки записываютсясо сдвигом на два разряда в сторонустарших в регистр запоминания. поразрядных переносов-четверок (для-го разряда сумматора с выхода 78 сумматора65 в разряд 32 регистра запоминания поразрядных переносов - четверок, В результате выполнения последнего цикла умножения получен трехрядный результат,состоящий из поразрядных сумм, поразрядных переносов-двоек и поразрядныхпереносов-четверок, поэтол 1 у необходимополучить однорядный результат, Это осуществляется в устройстве путем получения вначале двухрядного результата, состоящегоиз поразрядных сумм и пораз-.рядных переносов-двоек, а затем однорядного, представляющего собой произведение, следующим образом,С шин 106, 60, 112 и 114 разрешающие потенциалы снимаются и на нихпоступает запрещающий потенциал, а нашины 111 и 107 подается разрешающийпотенциал. В результат регистр заполи714395 11нания поразрядных переносов-четверок нвходные. шины 69-72 каждого разрядасумматора от приема информации отключаются, при этом поразрядные суммы записываются в тот же разряд регистра за 5поминания сумм (для1 -го разрядасумматора с выхода 80 сумматора 65,поразрядные переносы - двойки записываются со сдвигом на один разряд в сторону старших в ре истр запомйнания по- оразряднъж переносов - двоек) для , т -1) -горазряда сумматора с выхода 77 разряда регистра 12 в разряд 23 регистраи трехрядный результат переходит в двухрядный. Далее разрешающие потенциалы 35с шин 108 и 111 снимаются (на указан-ные шины поступает запрещающий потенциал), а на шину 109 подается разрешаю 1ший потенциал. В результате разрешается распространение переносов но цепи 20распространения переносов (для т - горазряда сумматора с выхода 77 ( 1 -1)- го разряда сумматора через элемент 46И и элемент 39 ИЛИ на вход 67 сумматора 65), а в регистр запоминания сумм 5записываются поразрядные суммы (длял -го разряда сумматора с выхода 80сумматора 65) . Таким образом двухрядный результат перешел в однорядный,представляющий собой произведение, пос-, 50.ле чего разрешаЕйме пдтещжадйс шин107 и 109 снимаются и на этом процесс"умножения заканчйвается. й регистре запоминания сумм получено произведе ние.55Этим достигается повьппение быстродейств,а устройства для ускоренного умножения.Использование восьмиразрядного преобразователя кода, четырех узлов сдвига, 4 фэлемента задержки и дополнительногоразряда ирегистра множителя делаетвозможным создание устройства для ускореншГо умножения, позволщощего нарядуСустранением распространения переносов 45в каждом цикле умножать одновременнона восемь разрядов множителя, что повышает быстродействие устро йства. 50Формула изобретении Устройство для ускоренного умножения, содержащее сумматор, построенный на основе одноразрядных семивходовых ,55 сумматоров, регистры множимого и множителя; регистры запоминании сумм и поразрядных переносов-двоек и четверок,причем выход суммы т -го разряда сумматора ( т -1 и, где и -разрядность операндов) подключен к ( 1 -1) му разряду регистра запоминания сумм, выход перенос - двойка 1 -го разряда сумматора подключен к 1 -му разряду регистра запоминания поразрядных переносов - двоек, выход "перенос - четВерка 1 -го разряда сумматора соединен с ( 1 +1)-м разрядом регистра запоминания поразрядных переносов-четверок, дополнительный выход суммы (-го разряда сумматора подключен ко входу-го разряда регистра запоминания сумм, а дополнительный выход " перенос- двойка"-го разряда сумматора соединен с ( 1 +1)-м разрядом сумматора и (1 +1)-м разрядом регистра запоминания поразрядных переносов -двоек, первый вход 1 -го разряда сумматора соединен с выходом 1- го разряда регистра запоминания сумм, второй его вход соединен с выходом 1 - го разряда регистра запоминания поразрядных переносов - четверок и дополнительным выходом переноса ( т -1-)-го разряда сумматора, третий вход его соединен с выходом 1 -го разряда регистра, запоминания поразрядных переносов - двоек, о т л и ч а ю ш е е с я тем, что, с целью повышения быстродействия, устройство содержит преобразователь кода, четыре узла сдвига, элемент задержки регистр множителя содержит дополнительный разряд, причем выходы младших вось ми разрядов и дополнительного разряда регистра множителя подключены ко входам преобразователя кода, выход регистра множимого подключен к первым входам узлов сдвига, выходы каждых двух соседних разрядов преобразователя кода, начиная с младшего, подключены ко второму и третьему входам соответствующих узлов сдвига, выход старшего разряда преобразователя кода подключен через элемент задержки ко входу младшего разряда преобразователя кода, выходы1 -х разрядов первого - четвертого узлов сдвига подключены соответственно к четвертому - седьмому входам 1 -го разряда сумматора, выход суммы м-го разряда сумматора подключен ко входу ( 1 - 8)-го разряда регистра залошнания сумм, выход перенос-двойка 1 -го разряда сумматора подключен ко входу ( 1 -7)-го разряда регистра запоминания поразрядных переносов-двоек, выхоп "перенос-четверка 1 -го разряда суфл714395 14 77 1 1 ИПИ Заказ 9289/46 Тираж 751нзл ППрод одписно ул, Проектная ф П "Патент", г. Ужго е матора соединен со входом (-6)-го разряда регистра запоминания поразрядных переносов-четверок.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР269607, кл. 9 06 Г 7/52, 1968. 2, Авторское482740, кл. 3. Авторское255648, кл. 4, Авторское281004, кл.