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

 

Изобретение относится к области вычислительной техники и может быть использовано для умножения многоразрядных чисел в р-кодах Фибоначчи. Цель изобретения - повьшение быстродействия устрЬйства.Поставленная цель достигается тем, чтомножимое умножается одновременно на два разряда множителя ,для чегов устрействовводится блок удвоения, коммутатор, второй сумматор и регистр. Устройство является неотъемлемой частью цифрового, вычислительного и измерительного оборудования , использующего коды с иррациональными основаниями. 2 нл., 3 табл.

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

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

РЕСПУБЛИК (19) (11) А1 (59 4 С 06 F 7/49

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 382664 1/24-24 (22) 18. 12.84 (46) 30.08.86. Бюл. М - 32 (72) А.П.Стахов, В.А.Лужецкий, А.И.Черняк и А.Е.Андреев (53) 681.325(088.8) (56) Авторское свидетельство СССР

1(1137459, кл. G 06 F 7/49, 1980.

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

В 662941, кл. G 06 F 7/52, 1976. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к области вычислительной техники и может быть использовано для умножения многоразрядных чисел в р-кодах Фибоначчи.

Цель изобретения — повышение быстродействия устройства.Поставленнаяцель достигается тем,чтомножимое умножается одновременнона дваразряда множителя,для чегов устройство вводится блок удвоения, коммутатор, второй сумматор и регистр. Устройство является неотъемлемой частью цифрового, вычислительного и измерительного оборудования, использующего коды с иррациональными основаниями. 2 ил., 3 табл.

1254469

Изобретение OTHOCHTCB K BbIMHCJIF тельной технике и может быть испопьзовано для умножения многоразрядных чисел в р-кодах Фибоначчи.

Цель изобретения — повышение быстродействия устройства.

Если множитель A представить в виде — аnЧ (и) + аь.,Я (и 1) + ° ° ° 10

+ a qр(0), то произведение множителя A на множимое Ь будет равно

А В = В а„ср (и) + В ° а„,(р (и-1)+ 15

+ ... + a a ср (0), о р где g (i) — обощенное число Фибоначр чи, которое определяется следующим образом:

20 ср (i)= 1 при i = 0 а е (0,11 (1)

P ср (i-1)+ср (д-р-1) при i > О

Частичное произведение В cPP(i) с учетом соотношения (1) определяется так

Вс р(1)В(f ð(11)+Встр(1 —, -1).

Отсюда вытекает следующий алго— ритм умножения целых чисел в р-кодах

Фибоначчи.

Образуют два столбца чисел, в левом из которых помещается последова-, тельность обобщенных чисел Фибоначчи с начальным условием, равным 1, в 35 ней вьделяют р-числа Фибоначчи, сос тавляющие минимальный р-код Фибоначчи множителя А . Во втором столбце помещается последовательность обобщенных чисел Фибоначчи с начальным 40 условием, равным множимому B. Результат умножения А 5 образуют путем сложения всех чисел второго столбца., соответствующих вьделенным р-числам

Фибоначчи первого столбца. При этом 45 контролируют, чтобы любое выделенное для сложения число второго столбца отстояло от предьдущего и следующего за ним выделенных для сложения чисел не менее, чем на р последовательно 50 расположенных чисел второго столбца.

Для р-чисел справедливо следующее соотношение: р

gp(i + p + 1) = 2с (1) +5 clap (i — у — j) (2)

При р = 1 формула (2) принимает вид ср (i + .2) =- ? ср,(1) + ср, (i — 1) . (3)

Исходя из выражения (3), и так как в минимальной форме представление чисел в двух соседних разрядах не могут быть две единицы, можно добиться быстродействия устройства для умножения целых чисел в 1-кодах

Фибоначчи за счет одновременного рассмотрения двух соседних разрядов множителя, из которых только один раз-. ряд может содержать единицу.

На фиг.1 показана функциональная схема устройства для умножения целых чисел; на фиг.2 — то же, блока микропрограммного управления, Устройство (фиг.1) содержит генератор 1 последовательности обобщенных чисел Фибоначчи, блок 2 удвоения, сумматор 3, регистр 4, сумматор 5, регистр 6 частичных произведений, коммутатор 7, регистр 8 множителя, блок 9 микропрограммного управления.

Блок 9 микропрограммного управле-, ния (фиг.2) содержит элемент ИЛИ 10, блок 11 памяти, регистр 12, дешифратор 13, i-й разряд блока удвоения реализует следующую логическую функцию: где А, — значение z.-го разряда числа;

В; — удвоенное значение i-го разряда числа.

Устройство для умножения работает следующим образом.

Рассмотрим работу устройства для умножения целых чисел на примере умножения в 1-кодах Фибоначчи числа 60. на число 37.

В исходном состоянии в регистре

8 записан код числа 37 в минимальной форме представления. Код числа 60 задает начальное условие (нулевое число) последовательности обобщенных чисел Фибоначчи, которая совместно формируется генератором 1 и блоком 2 удвоения вместе с вторым сумматором

3, .в регистре 8 частичных произведений записан код нуля.

По сигналу, поступающему иэ блока

9 микропрограммного управления, генератор 1 и блок 2 удвоения вместе с вторым сумматором 3 начинают формировать последовательность обобщенных чисел Фибоначчи. После .того, как сформированы два очередных числа, 1254469 блоком 9 микропрограммного управления анализируются аостояния двух младших разрядов регистра 8 множите-. ля. Если в этой группе разрядов в младшем разряде записана единица, то первый сумматор 5 производит сложение кода, поступающего с выхода генератора 1 через коммутатор 7 и кода, поступающего с выхода регистра

6 частичных произведений. Если же в 10 этой группе разрядов в старшем разряде записана единица, то первыи сумматор производит сложение кода, поступающего с выхода регистра 4 через коммутатор 7 и кода, поступающего с 15 выхода регистра 6 частичных произведений. Затем происходит сдвиг кода на два разряда в сторону младших разрядов в регистре 8 множителя и формирование очередной пары обобщенных 20 чисел Фибоначчи генератором 1 и блоком 2 удвоения совместно с вторым сумматором 3.

Если в группе младших разрядов регистра 8 записаны два нуля, то 25 блок 9 микропрограммного управления вырабатывает управляющие сигналы, по котерым происходит только лишь сдвиг кода на два разряда в регистре

8 и формирование очередной пары чие.. 30 сел в генераторе 1 и в блоке 2 удвоения совместно с вторым сумматором 3.

Процесс умножения оканчивается после того, как будут выдвинуты из регистра 8 все разряды кода множителя.

При этом результат умножения будет находиться в регистре 6, откуда он поступает на выход устройства умножения-.

Состояния генератора 1, блока 2 0 удвоения, регистра 4, коммутатора 7, регистра 8 множителя и регистра 6 частичных произведений, соответствующие каждому такту работы, приведены в табл. 1. 45

Блок 9 микропрограммного управления работает в соответствии с табл. 2.

Необходимые для функционирования устройства управляющие сигналы приведены в табл.3.

Формула изобретения

Устройство для умножения, содержащее регистр множителя, регистр частичных произведений, первый сумматор,55 генератор последовательности обобщенных чисел Фибоначчи и блок микропрограммного управления, выход регистра, частичных произведений соединен с выходом устройства и первым входом первого сумматора, выход которого подключен к информационному входу регистра частичных произведений, вход регистра множителя соединен с входом множителя устройства, вход множимого которого соединен с первым информационным входом генератора последовательности обобщенных чисел Фибаначчи, выходы регистра множителя соединены с входом начальной установки блока микропрограммного управления, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него дополнительно введены блок удвоения, коммутатор, второй сумматор, регистр, вход установки в "0" регистра множителя соединен с входами установки в "0" регистра частичных произведений и регистра и подключен к первому выходу блока микропрограммного управления, второй выход которо— го соединен с входом записи в регистр множителя, вход множимого устройства соединен с первым информационным входом блока удвоения, yrrpaBляющий вход которого подключен к управляющему входу генератора последовательности обобщенных чисел Фибоначчи и соединен с третьим выходом блока микропрограммного управления, четвертый выход которого соединен с входом записи регистра, выход которого подключен к вторым информационным входам генератора последовательности обобщенных чисел Фибоначчи, блока удвоения и к первому информационному входу коммутатора, выход блока удвоения соединен с первым входом второго сумматора, второй вход которого соединен с выходом генератора последовательности обобщенных чисел Фибоначчи и вторым информационным входом коммутатора, первый и второй управляющие входы которого соединены соответственно с пятым и шестым выходами блока микропрограммного управления, седьмой выход которого соединен с входом записи регистра частичных произведений, выход второго сумматора соединен с информационным входом регистра, выход коммутатора подключен к второму входу первого сумматора, вход управле.ния сдвигом регистра множителя соединен с восьмым выходом блока микро- программного управления.

1254469

Та блица 1

Регистр 8 вес разряда

34:2 1: 13:8:5 .3:2: 1

Регистр 6

Регистр 4

Коммутатор

Блок. 2 удвоения

ГенеУ такратор

1 та

120

1 0 0 00 t 00

120

180

18000100001

300

240

180

00001000

180

780

600

480

2220 О О 0 О О 0 1 0 2220

2040

1560

1260

Таблица 2

4 5 6

0000010 00010111000011011011100000

000001100010111001 011011011110000

0000100000101101001101110000ÎÎÎÎ

00001010001.0117011011011100010000

000011Î0001Î11110ÎÎ1101110010000Î

0000111000101111011011100110000

0001000001001111 100110 11101000000

000100100100111111011011101010000

000101000101000000000011101100000

000 101 1 001О 1 00000 1 0000.1 1 101 0000

000110000101000010000011110000000

1 11 1001 0000

1110000

0001101001010000110000

0001110001010001000011

0001 t 11 0010 1000 t 01 0011 1111011 0000

001000000111000110001111111000000

0010001 0011 1000111 001 1 11 11 101 0000 г г г г у «i г г г г, г г г г,у х х,, z4z z z„ z z z z y х х, г. г г г

1 254469

Продолжение табл. 2

ОO11 1ОО1ООО

1OO1i OO1i iOO1OOi OOOO 1111»1 0000

Î0 i Î i ÎÎ Îλ 1ОО1О1О ОООО

îîi0iîi îoi »0010» оооо

00101,10 0011 1001100 ОООО

ОО1О111 ОО11 1ОО1101 ОООО

Îλ0ÎÎ ÎiÎ0 iÎλ1О ОООО

ОО» OO1 O i OO 1OO1 i 11 OOOO

ОО11О1О О1ОО 1О1ОООО ОООО

OO» O» O i OO 1O1OOO1 OOOO

ОО, 11ОО О1ОО 101ОО1О ОООО ооя1101 îiîî iî i îî» оооо

ÎÎ i » i O О1ОО 1О1О1ОО ОООО

OO»» i Î1ОО 1О1О1О1 ОООО

îiîîîîî 1îîî iîiî » о оооо

îiîîîîi oiîi iîiî » 1 оооо

О1ООО Î Î » » Î » ООО ОООО

О1ООО11 Î i λ 011001 ОООО

OO i OO 1OOO 1О1

OO i O1 O1O» О» O11 OOOO

OO11O O i 1» О» 1OO OOOO

О1ОО111 О1О1 1О11101 ОООО

О1О1ООО О11О 1O i i i 1O OOOO

О1О1ОО1 λΠ1Îi 1»1 ОООО

01О1О1О О11О 11ООООО ОООО

Î i Î i λ О11О 1100001 ОООО

О1О11ОО О11О 11ООО1О ОООО

1254469.l0

Продолжение табл.2) г б

0110101100011010110000

Таблица 3

Номер Обозна- Наименование связи чения

Примечание

Обнуление Рг, РгМн, РгЧП

Запись множителя в РгМн

У2

Управление -работой ГПОЧФ и БУдв.

У4

Запись результата сдожения в Рг

При Y5 = 1 коммутируется выход ГПОЧФ

Коммутация Км

При Y6 = 1 коммутируется выход Pr

У6

Коммутация Км

Запись результата сложения в РгЧП

У7

У8

Сдвиг на два разряда содержимого РгМн

0101101 01 10 110001 1 0000

010 t 1 0110 1100101 0000

01 10001 1000 1 1001 1 1 0000

011.0010 1000 1101000 0000

01 10100 1000 1 101010 0000

1254469

Составитель А.Жижин

Техред Л, Сердюкова Корректор А. Зимокосов

Редактор Н.Слободяник

Заказ 4721/52 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4