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

112544

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

Цель изобретения - повышение быс- 5 тродействия устройства. -Если множитель Д представить в виде

А a cfpCn) + a,.cfp(n - 1)

+ a,q-p(0),

то произведение множителя жимое & будет равно

А на мноА ч

В В- (n) + В- а.,Срр(п-1)+ ... + В . a ifpCO),

где tfpCi) - обощенное число Фибоначчи, которое определяется следующим образом:

0при i 0

1при 1 0

Cfр (i-1) +(fp (i-p-1) при i О Частичное произведение В- Срр (i) с учетом соотношения (1) определяется так

В срр (i) В- Cf р (i-1)+B Cfp(i - Р - О..

срр(1)

а,е 0,l(1)

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

1 Образуют два столбца чисел, в левом из которых помещается последовательность обобщенных чисел Фибоначчи с начальным условием, равным 1, в ней выделяют р-числа Фибоначчи, coc тавляющие минимальный р-код Фибоначчи множителя Д. Во втором столбце помещается последовательность обобщенных чисел Фибоначчи с начальным условием, равным множимому В. Результат умножения А & i образуют путем сложения всех чисел второго столбца соответствующих выделенным р-числам Фибоначчи первого столбца. При этом контролируют, чтобы любое выделенное для сложения число второго столбца отстояло от предыдущего и следующего за ним выделенных для сложения чисел не менее, чем на р последовательно расположенных чисел второго столбца. Для р-чисел справедливо следующее

соотношение:

р

CfpCi + р -f 1) 2cf (i) + L Cfp(i - - j),J (2)

При p 1 формула (2) принимает

вид

5

0

20

15

25

30

5

40

55

45

50

692

Cf,(i + .2) - 2cp,(i) 4 cp (i - 1) .

(3)

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

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

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

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

,,A;,+A;.,A;,;A;,,-fA,.,A;,A.4- Ч,,-л/А,.,А5,А;„1.,

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

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

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

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

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

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

9микропрограммного управления, генератор 1 и блок 2 удвоения вместе с вторым сумматором 3 начинают формировать последовательность обобщенных чисел Фибоначчи. После .того, как сформированы два очередных числа.

3

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

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

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

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

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

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

Устройство для умножения, содержащее регистр множителя, регистр чатичных произведений, первый суммато генератор последовательности обобщеных чисел Фибоначчи и блок микропрораммного управления, выход регистра

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

Q 5

25

30

5

0

5

лью повышения быстродействия, в него дополнительно введены блок удвоения, коммутатор, второй сумматор, регистр, вход установки в О регистра множителя соединен с входами установки в О регистра частичных произведений и регистра и подключен к первому выходу блока микропрограммного управления,второй выход которого соединен с входом записи в регистр множителя, вход множимого устройства соединен с первым информационным входом блока удвоения, управляющий вход которого подключен к управляющему входу генератора последовательности обобщенных чисел Фибоначчи и соединен с третьим выходом блока микропрограммного управления, четвертый выход которого соединен с входом записи регистра, выход которого подключен к вторым информационным входам генератора последователь- ности обобщенных нисел Фибоначчи, блока удвоения и к первому информа- ционному входу коммутатора, выход блока удвоения соединен с первым входом второго сумматора, в 5орой вход которого соединен с выходом генератора последовательности обобщенных чисел Фибоначчи и вторым информационным входом коммутатора, первый и второй управляющие входы которого соединены соответственно с пя-тым и щестым выходами блока микропрограммного управления, седьмой выход которого соединен с входом записи регистра частичных произведений, выход второго сумма;тора соединен с информационным входом регистра, выход коммутатора подключен к второму входу первого сумматора, вход управления сдвигом регистра множителя сое- динен с восьмым выходом блока микро-т программного управления.

Таблица 1

Таблица 2

0010010 00111001000 О О 00 ItrilTO 0000

001,0 011 00111001001 0000 1 1 1 1 1 I I 2 2 2 20010100001110010100000

0010101 00111001011 0000

00101,10001110011000000

0010111 00111 о .0 1 1 о 1 0-0 о о

0011000010010011100000

001100101001 О о 1 1 1 1 0000

011 011 011

0.4 1 011 011 100 100 100 100 100 100 100 100 101

1о 1

101 101 101

о 1 о

01 1

1о о

1 о 1 1 1 о

111

000

о о 1 о 1 о

01 1

1 00 1 о 1 1 1 о

11 1

000

о о 1 о 1 о о 1 1

10 о

0100 0100 0100 010 о 0100 0100 1000 0101 0111 0101 1000 0101 01 1 1 о 1 01 0110 0110 0110 0110 0110

1010 1010 1010 1010 1010 1010 1010 1010 1011 1011 1011 1011 1011 1011 1011 1011 1100 1 1 о о 1100

0000 0000 0000 о 000 0000 0000 0000 0000 0000 0000 00 00 0000 0000 0000 0000 0000 0000 0000 0000

1011010110 11000110000

1011100110 1100100 0000

1011110110 11001010000 1 100 0010001100110 0000 1 100011000 1 1001 1 10000 11. 00101000 1101000 0000 11001110001101001 0000

110100loop 1101010 0000

1101011000 11010110000

Обозначения

Наимено вание

YT Обнуление Рг, РгМн, РгЧП Y2 Запись множителя в РгМн

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

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

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

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

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

Таблица 3

Примечание

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

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

Фиг. г

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