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

(50 4 С 06 Р 7/49 ИЗОБРЕТЕНИЯ ПИСА ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТ 21) 382664 1/24-2422) 18. 12,8446) 30.08.86, Бюл. В 3272) А.П.Стахов, В.А.Лужецкий,(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ(57) Изобретение относится к областивычислительной техники и может бытьиспользовано для умножения многоразрядных чисел в р-кодах фибоначчи.Цель изобретения - повышение быстродействия устройства.Поставленнаяцельдостигается тем,чтомножимое умножается одновременнона дваразряда множителя,для чегов устройствовводится блокудвоения, коммутатор, второй сумматор и регистр. Устройство являетсянеотъемлемой частью цифрового, вычислительного и измерительного оборудования, использующего коды с иррациональными основаниями. 2 ил., 3 табл.Изобретение относится к вычислительной технике и может быть испопь- зовано для умножения многоразрядных чисел в р-кодах Фибоначчи.Цель изобретения - повышение быс тродействия устройства.Если множитель А представить в виде А = асРР(п) + аь. срр(п - 1) +10 + асР (О) э то произведение множителя А на множимое Ь будет равно А В = В аср (и) + Ва,(р (и)+ 15 ++ В а,ср (О),О р где с (д) - обощенное число ФибоначР чи, которое определяется следующим образом:20 ср (1)= 1 приз.=О 1фа е Г 0,1 (1) РсРР (1-1)+сРР (д-р) при 10 Частичное произведение В срр с учетом соотношения (1) определяется так В сРР (1) В ср (1 1)+В срр(1р - 1),Отсюда вытекает следующий алгоритм умножения целых чисел в р-кодах Фибоначчи.Образуют два столбца чисел, в левом из которых помещается последова-, тельность обобщенных чисел Фибоначчи с начальным условием, равным 1, в 35 ней вьделяют р-числа Фибоначчи, сос тавляющие минимальный р-код фибоначчи множителя А . Во втором столбце помещается последовательность обобщенных чисел фибоначчи с начальным 40 условием, равным множимому В. Результат умножения А Вобразуют путем сложения всех чисел второго столбца, соответствующих вьделенным р-числам фибоначчи первого столбца. При этом 45 контролируют, чтобы любое выделенное для сложения число второго столбца отстояло от предьдущего и следующего за ним выделенных для сложения чисел не менее, чем на р последовательно 50 расположенных чисел второго столбца.Для р-чисел справедливо следующее соотношение:Р ср(2. + р + 1) = 2 сур +2 срр (д- з) (2)При р = 1 формула (2) принимаетВид сР ( д + . 2 ) =. 2 сР, ( 1 ) + сР, ( д - 1 ) .(3)Исходя из выражения (3), и таккак в минимальной форме представление чисел в двух соседних разрядахне могут быть две единицы, можно добиться быстродействия устройствадля умножения целых чисел в 1-кодахФибоначчи за счет одновременного рассмотрения двух соседних разрядов множителя, из которых только один раз-.ряд может содержать единицу.На фиг.1 показана функциональнаясхема устройства для умножения целыхчисел; на фиг.2 - то же, блока микропрограммного управления,Устройство (фиг.1) содержит генератор 1 последовательности обобщенныхчисел Фибоначчи, блок 2 удвоения,сумматор 3, регистр 4, сумматор 5,регистр 6 частичных произведений,коммутатор 7, регистр 8 множителя,блок 9 микропрограммного управления.Блок 9 микропрограммного управле-,ния (фиг.2) содержит элемент ИЛИ 10,блок 11 памяти, регистр 12, дешифратор 13, -й разряд блока удвоенияреализует следующую логическую функцию:где А; - значение -го разряда числа;В; - удвоенное значение д-го разряда числа.Устройство для умножения работает следующим образом,Рассмотрим работу устройства для умножения целых чисел на примере умножения в 1-кодах Фибоначчи числа 60:на число 37.В исходном состоянии в регистре8 записан код числа 37 в минимальнойформе представления. Код числа 60задает начальное условие (нулевоечисло) последовательности обобщенныхчисел Фибоначчи, которая совместноформируется генератором 1 и блоком 2удвоения вместе с вторым сумматором3, в регистре 8 частичных произведений записан код нуля.По сигналу, поступающему иэ блока 9 микропрограммного управления, генератор 1 и блок 2 удвоения вместе с вторым сумматором 3 начинают формировать последовательность обобщенных чисел Фибоначчи. После .того, как сформированы два очередных числа, 1254469блоком 9 микропрограммного управления анализируются аостояния двухмладших разрядов регистра 8 множите-.ля, Если в этой группе разрядов вмладшем разряде записана единица,то первый сумматор 5 производит сложение кода, поступающего с выходагенератора 1 через коммутатор 7 икода, поступающего с выхода регистра6 частичных произведений. Если же в 1 Оэтой группе разрядов в старшем разряде записана единица, то первыи сумматор производит сложение кода, поступающего с выхода регистра 4 черезкоммутатор 7 и кода, поступающего с 5выхода регистра 6 частичных произведений. Затем происходит сдвиг кодана два разряда в сторону младших разрядов в регистре 8 множителя и формирование очередной пары обобщенных 20чисел Фибоначчи генератором 1 и блоком 2 удвоения совместно с вторымсумматором 3.Если в группе младших разрядоврегистра 8 записаны два нуля, то 25блок 9 микропрограммного управлениявырабатывает управляющие сигналы,по котерым происходит только лишьсдвиг кода на два разряда в регистре8 и формирование очередной пары чие. ЗОсел в генераторе 1 и в блоке 2 удвоения совместно с вторым сумматором 3.Процесс умножения оканчивается послетого, как будут выдвинуты из регистра 8 все разряды кода множителя.При этом результат умножения будетнаходиться в регистре 6, откуда онпоступает на выход устройства умноженияСостояния генератора 1, блока 2удвоения, регистра 4, коммутатора 7,регистра 8 множителя и регистра 6частичных произведений, соответствующие каждому такту работы, приведеныв табл.1, 45Блок 9 микропрограммного управления работает в соответствии с табл, 2,Необходимые для функционированияустройства управляющие сигналы приведены в табл.3,Формула изобретения Устройство для умножения, содержащее регистр множителя, регистр частичных произведений, первый сумматор,55 генератор последовательности обобщенных чисел фибоначчи и блок микропрограммного управления, выход регистра,частичных произведений соединен с выходом устройства и первым входом первого сумматора, выход которого подключен к информационному входу регистра частичных произведений, вход регистра множителя соединен с входоммножителя устройства, вход множимогокоторого соединен с первым информационным входом генератора последовательности обобщенных чисел Фибаначчи,выходы регистра множителя соединены свходом начальной установки блокамикропрограммного управления, о тл и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него дополнительно введены блок удвоения, коммутатор, второй сумматор,регистр, вход установки в "О" регистра множителя соединен с входамиустановки в "О" регистра частичныхпроизведений и регистра и подключенк первому выходу блока микропрограммного управления, второй выход которого соединен с входом записи в регистр множителя, вход множимого устройства соединен с первым информационным входом блока удвоения, управляющий вход которого подключен куправляющему входу генератора последовательности обобщенных чисел Фибоначчи и соединен с третьим выходомблока микропрограммного управления,четвертый выход которого соединен свходом записи регистра, выход которого подключен к вторым информационным входам генератора последовательности обобщенных чисел Фибоначчи,блока удвоения и к первому информационному входу коммутатора, выходблока удвоения соединен с первымвходом второго сумматора, второйвход которого соединен с выходом генератора последовательности обобщенных чисел Фибоначчи и вторым информационным входом коммутатора, первыйи второй управляющие входы которогосоединены соответственно с пятыми шестым выходами блока микропрограммного управления, седьмой выходкоторого соединен с входом записи регистра частичных произведений, выходвторого сумматора соединен с информационным входом регистра, выходкоммутатора подключен к второму входу первого сумматора, вход управле.ния сдвигом регистра множителя соединен с восьмым выходом блока микро.программного управления..Номер Обозна- Наименованиесвязи чения Примечание Обнуление Рг, РгМн, РгЧП Запись множителя в РгМн Управление работой ГПОЧФи БУдв. 4 Запись результата сдоженияв Рг При Т 5 = 1 коммутируется выход ГПОЧФ Коммутация Км При Тб = 1 коммутируется выход Рг Коммутация Км Запись результата сложения в РгЧП Сдвиг на два разряда содержимого РгМн 0101101 0110 1100011 0000 0101110 0110 1100100 0000 0101111 0110 1100101 0000 0110000 1000 1100110 0000 0110001 1000 1100111 0000 011.0010 1000 1101000 0000 011001 1000 1101001 0000 0110100 1000 1101010 00001254469 Составитель А.Жижи Техред Л,Сердюков Корректор А. Зимокосо р Н.Слободя 1 5 ое Под тета СССка осу лам крыти я наб Производственно-полиграфическое предприятие, г.ужгород, ул,Проектная, 4 НИИП по 3035