Устройство для умножения чисел в @ -кодах фибоначчи

 

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ В р-КОДАХ ФИБОНАЧЧИ, содержащее регистр множимого, регистр множителя , сумматор, регистр частичных произведений и блок управления, входы регистров множимого и множителя являются соответствующими входами устройства, выход сумматора соединен с информационным входом регист-г ра частичных произведений, выход которого является выходом устройства и соединен с первым информационным входом сумматора, о т л и ч а ю щ ье с я тем, что, с целью повышения его быстродействия, в него введены блоки поразрядных произведений, блоки суммирования, регистры поразрядных произведений, образующие п/(р-ь1) групп (п - разрядность множимого ), блоки коммутации, выходы которых подключают к второму информащюнному входу сумматора, выходы блоков по разрядных произведений каждой группы и соответствующего регистра поразрядных произведений подключены к информационным входам соответствующего блока суммирования, выход кото .рого соединен с информационным вхо- . . дом соответствующего регистра по .разрядных произведений, блок управления содержит узел анализа, кольцевой сдвиговый регистр, ключевой элемент и узел выработки управляющих сигналов, узел анализа содержит элемент ШШ-НЕ, дешифратор, элемент И, элемент и элемент ШШ, узел выработки управлякщих сигналов содержит генератор импульсов, два элемента запрета, .шесть элементов И, четыре элемента ИЛИ, три кольцевых сдвиговых регистра, причем выходы разрядов регистра множителя подключены к входам элемента ИЛИ-НЕ узла анализа, выходы двух старших разря .дов регистра множителя подключены к входам дешифратора узла анализа, выход-элемента 1ШИ-НЕ узла анализа подключен к первому входу элемента И и информационному входу элемента запрета узла анализа, выход элемента запрета узла анализа соединен с управляющим входом первого элемента запрета н с первьм входом первого элемента И узла выработки управСО ляющих сигналов, первый выход дешиф sl ратора узла анализа подключен к 4аь СП управляющим входам второго элемента запрета и шестого элемента И узла :0 выработки управляющих сигналов информационные входы которых соединены с выходом первого элемента запрета узла выработки управляющих сигнгшов , второй и третий выходы дешиф ратора узла анализа соединены с входами элемента ИШ узла анализа, выход которого подключен к управлякнцему входу ключевого элемента блока управления , информационные входы которого соединены с выходами всех разрядов, . кроме старшего, кольцевого сдвигового регистра блока управления, выход стар

09) (И) СОЮЗ COBETCHHX

О ИЛ П

РЕСПУБЛИН

4(51) 606 Р 7/49

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

H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЦТИЙ (2!) 3225313/24-24 (22) 24.11.80 (46) 30.01.85. Бюл. У 4 (72). В;В.Роздобара, И,А.Баранов, Г.В.Кремез, И.И.Захарчуки В.П.Лачугин (53) 681.325(088.8) (56) 1. Патент Японии В 52-22218,, кл. G 06 Р 7/38, опублик. 1977.

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

Ф 662941, кл. С 06 F 7/49, 1976

:(прототип). (54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

ЧИСЕЛ В р -КОДАХ ФИБОНАЧЧИ, содержащее регистр множимого, регистр множителя, сумматор, регистр частичных произведений и блок управления, входы регистров множимого и множителя являются соответствующими входами устройства, выход сумматора соединен с информационным входом регист-. ра частичных произведений, выход которого является выходом устройства и соединен с первым информационным входом сумматора, о т л и ч а ю щ е.е с я тем, что, с целью повышения его быстродействия, в него введены блоки поразрядных произведений, блоки суммирования, регистры .поразрядных произведений, образующие n/(р+1) групп (n — разрядность.множимого J, блоки коммутации, выходы которых

:подключают к второму информационному входу сумматора, выходы блоков поразрядных произведений каждой группы и соответствующего регистра поразрядных произведений подключены к информационным входам соответствующего блока суммирования, выход кото..рого:соединен с информационным вхо-, дом соответствующего регистра по= .разрядных произведений, блок управления содержит узел анализа, кольцевой сдвиговый регистр, ключевой элемент и узел выработки управляющих сигналов, узел анализа содержит элемент ИЛИ-НЕ, дешифратор, элемент

И, элемент запрета и элемент ИЛИ, узел выработки управляющих сигналов содержит генератор импульсов, два элемента запрета, .шесть элементов И, четыре элемента ИЛИ, три кольцевых сдвиговых регистра, причем выходы разрядов регистра множителя подключены к входам элемента ИЛИ-НЕ узла анализа, выходы двух старших разря.дов регистра множителя подключены к входам дешифратора узла анализа, выход .элемента ИЛИ-НЕ узла-анализа подключен к первому входу элемента

И и информационному входу элемента запрета узла анапиза, выход элемента запрета узла анализа соединен с управляющим входом первого элемента запрета и с первым входом первого элемента И узла выработки управляющих сигналов, первый выход дешифратора узла анализа подключен к управляющим входам второго элемента запрета и шестого элемента И узла выработки управляющих сигналов, информационные входы которых соедине" ны с выходом первого элемента запрета узла выработки управляющих сигналов, второй и третий выходы дешифратора узла анализа соединены с вхо-дами элемента ИЛИ узла анализа, выход которого подключен к управляющему входу ключевого элемента блока управ ления, информационные входы которого соединены с выходами всех разрядов, кроме старшего, кольцевого сдвигового регистра блока управления, выход стар1137459 шего разряда которого соединен с вторым входом элемента И и с управляющим входом элемента запрета узла анализа, выход ключевого элемента блока управления подключен к вторым входам блоков поразрядных произведений,. второй выход дешифратора узла анализа подключен к первому входу второго элемента И узла выработки управляющих сигналов, выход которого соединен с первым входом первого элемента ИЛИ узла выработки управляющих сигналов, второй вход которого соединен с выходом шестого элемента

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

И узла выработки управляющих сигналов, выход первого разряда первого кольцевого сдвигового регистра узла выработки управляющих сигналов соединен с вторыми входами второго и третьего элементов И узла выработки управляющих сигналов, выходы второго и третьего разрядов первого кольцевого сдвигового регистра узла выработки управляющих сигналов соединены с управляющими входами блоков суммирования и регистров поразрядных произведений соответственно, выходы третьего и четвертого элементов И узла выработки управляющих сигналов соединены с входами второго элемента ИЛИ узла выработки управляющих сигналов, выход шестого элемента И узла выработки управляющих сигналов „ подключен к первому входу третьего элемента ИЛИ узла выработки управляющих сигналов, выход которого соединен с управляющим входом регистра множителя, выход четвертого разряда первого кольцевого сдвигового регистра узла выработки управляющих . сигналов соединен с вторыми входами

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

Известно устройство для умножения, содержащее регистры множителя, множимого, частичных произведений, сумматоры,и блок управления, позволяющее умножать коды, представленные в классичесиой двоичной системе счисления (I).

3 11374

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

Известно устройство для умножения целых чисел, содержащее регистр множителя, регистр частичных произведений, сумматор, блок управления и генератор последовательности обобщенных чисел Фибоначчи, вход которого ,является-вторым входом устройства, .а выход соединен с вторым входом сумматора, выход и первый вход которого соединены соответственно с входом и выходом регистра частичных произведений, выход которого также является выходом устройства, вход регистра множителя является первым входом устройства, а выход соединен с входом блока управления, выход которого соединен с управляющими входами регистра частичных произведений, регистра множителя, сумматора и генератора последовательности обобщенных чисел Фибоначчи. В .этом устройстве контроль вычислений осуществляется за счет того, что перемножаемые числа представпяются в р-кодах Фибоначчи, обладающих вьгсокой ошибкообнару30 живающей способностью 1.2 "1.

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

Целью изобретения является повышение быстродействия работы устрой- 4О ства, заключающееся в одновременном умножении множимого на (p+l) разрядов множителя в случае, если множимое и множитель представлены в р-кодах Фибоначчи. 45

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

59 4 входом сумматора, введены блоки поразрядных произведений, блоки суммирования, регистры поразрядных произведений, образующие n/(р+!) групп (и — разрядность множимого), блоки коммутации, выходы которых подключают к второму информационному входу сумматора, выходы блоков поразрядных произведений каждой группы и соответствующего регистра поразрядных произведений подключены к информационным входам соответствующего блока суммирования, выход которого соединен с информационным входом соответствующего регистра поразрядных произведений, блок управления содержит узел анализа, кольцевой сдвиговый регистр, ключевой элемент и узел выработки управляющих сигналов, узел анализа содержит элемент ИЛИ-НЕ, дешифратор, элемент И, элемент запрета и элемент ,ИЛИ, узел выработки управляющих сиг= налов содержит генератор импульсов, два элемента запрета, шесть элементов И, четыре элемента ИЛИ, три кольцевык сдвиговых регистра, причем выходы разрядов регистра множителя подключены к входам элемента ИЛИ вЂ  узла анализа, выходы двух старших pasрядов регистра множителя подключены к входам дешифратора узла анализа, выход элемента ИЛИ-НЕ узла анализа, подключен к первому входу элемента

И и информационному входу элемента запрета узла анализа, выход элемента запрета узла анализа соединен с управляющим входом первого элемента запрета и с первым входом первого элемента .И узла выработки управляющих сигналов, первый выход дешифратора узла анализа подключен к управляющим входам второго элемента запрета и шестого элемента И узла выработки управляющих сигналов, информационные входы которьгх соединены с выходом первого элемента запрета узла выработки управляющих сигналов, второй и третий выходы дешифратора узла анализа соединены с входами элемента ИЛИ узла анализа, выход которого подключен к управляющему входу ключевого элемента блока управления, информационные входы которого соединены с выходами всех разрядов, кроме старшего, кольцевого сдвигового регистра блока управления, выход старшего разряда которого соединен с вторым входом элемента И и с управляющим входом элемента запре1137459 ла выработки управляющих сигналов, выходы первого и второго элементов

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

so та узла анализа, выход ключевого элемента блока управления подключен, к вторым входам блоков поразрядных произведений, второй выход дешифратора узла анализа подключен к перФому входу второго элемента И узла выработки управляющих сигналов, выход которого соединен с первым входом первого элемента ИЛИ узла выработки управляющих сигналов, второй 10 вход которого соединен с выходом шестого элемента И узла выработки управляющих сигналов, третий выход дешифратора узла анализа соединен с первыми входами третьего и четвертого элементов И узла выработки управ ляющих сигналов, выход первого разряда первого кольцевого сдвигового регистра узла выработки управляющих сигналов соединен с вторыми входами второго и третьего элементов И узла выработки управляющих сигналов, выходы второго и третьего разрядов первого кольцевого сдвигового регистра узла выработки управляющих сигналов соединены c óíðàâëÿþùèìè входами блоков суммирования и регистров поразрядных произведений соответственно, выходы третьего и четвертого элементов И узла выработки управляющих сигналов соединены с входами второго элемента ИЛИ узла выработки управляющих сигналов, выход шестого элемента И узла выработки управляющих сигналов подключен к пер вому входу третьего элемента ИЛИ уз- Зла выработки управляющих сигналов, выход которого соединен с управляющим входом регистра множителя, выход четвертого разряда первого кольцевого сдвигового регистра узла выра—

40 ботки управляющих сигналов соединен с вторыми входами четвертого элемента И и третьего элемента ИЛИ узЧ (Е+й) пРи 1 =0

9 (0+k)-9 (H)Y (М-1) при р=1

1 1 1

q (е )-ч (е-1) Е (%-р)—

Р - P P

- (k-4) У (Е-р) при p>i2

Ч (П (Ц= где чр(1.) — вес i-го РазРЯда Р-кода Фибоначчи, k 7 g.

В частности, для p=l произведение

g (I) ч (1 .) представляется в виде следующей суммы

V„(e>V„(a)-V „ (Å. К- Ц.Ч„ (Е. 1 -S).V„(Е 1 -Э)+... ... + 4 (Е+ %-1-4 (1п-1)) +У (1с-2т), (2) рого, кроме последнего, подключены к управляющим входам соответствующих блоков коммутации, выходы второго и третьего разрядов второго кольцевого сдвигового регистра,узла выработки управляющих сигналов подключены соответственно к управляющим входам сумматора и регистра частичных произведений, выход четвертого разряда второго кольцевого сдвигового регистра узла выработки управляющих сигналов подключен к первому входу пятого элемента И узла выработки управляющих сигналов, второй вход которого соединен с выходом предпоследнего разряда третьего кольцевого сдвиГового регистра узла выработки управляющих сигнаЛов, входы четвертого элемента ИЛИ узла выработки управляющих сигналов подключены к выходу пятого элемента И .узла выработки управляющих сигналов и выходу элемента И узла анализа, а выход подключен к выхо-ду признака. окончания работы устройства, вход запуска которого соединен с входом запуска генератора импульсов узла выработки управляющих сигналов.

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

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

11 37459

k=4 3=3

2=! Е 3! с=4 !1= l

k-1 2-1

Сложение: ) 1000100

+ 1000

1 001 1 00

1 01 0000

1 0 l 0 000

+ 10000

2) 1100100

10000 l 1 0

1 0001000 где м — частное от деления E на 2.

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

Пример. Умножить в двоичной

1-системе счисления число 6=10010 и число 4=1010.

I) 10000 1000 = 1OOOIDO;

3) 1 0000 х 1 0 = 0000; .10000100

10000100.

3) + 1 0

Результат: 6 х 4 = 24 = 10 00 1 0 00.

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

8.

Схема устройства для умножения чисел в р — кодах Фибоначчи содержит регистр множимого l, регистр 2 множителя, сумматор 3, регистр 4 частичных произведений, блок 5 управления, блоки 6 поразрядных произведений, блоки 7 суммирования, регистры 8 поразрядньгл произведений, блоки 9 коммутации, входы 0 — 12 !

О устройства, выход 13 устройства.

Блок 5 управления содержит вход

12, выходы 14-21, кольцевой сдвиговый регистр 22, ключевой элемент 23 узел 24 анализа, содержащий дешифратор 25, элемент ИЛИ 26, элемент

ИЛИ-НЕ 27, элемент И 28, элемент 29 запрета. Блок 5 управления содержит также узел 30 выработки управляющих сигналов, содержащий входы 31-35 ро выходы 36 и 37, генератор 38 импульсов, кольцевые сдвиговые регистры

39-41, элементы И 42-47, элементы за,прета 48 и 49, элементы ИЛИ 50-53.

Регистр множимого 1 и регистр множителя 2 предназначены для хранения

1 соответственно р-кодов Фибоначчи множимого и множителя.

В сумматоре 3 осуществляется сложение частичных произведений по правилам "фибоначчиевой" арифметики.

В регистре 4 частичных произведений хранится текущая сумма частичных произведений.

Блок 5 управления предназначен для выдачи сигналов управления блоками

;устройства в соответствии с алгоритмом работы устройства.

В блоках 6 поразрядных произведе- ний формируются произведения соот4О ветствующих разрядов множителя и множимого по формуле (ll .

Блоки 7 суммирования осуществляют сложение поразрядных произведений соответствующей группы из (р+1) разрядов множимого на группы из (р+1!

45 разрядов множителя.

Регистры 8 поразрядных произведений используются для хранения текущих сумм поразрядных произведений.

Блоки 9 коммутации предназначены для подключения соответствующих регистров поразрядных произведений к сумматору.

Входы 10 и ll являются информационными входами .устройства, вход

12 — входом запуска, выход 13 является информационным выходом устройства, выход 14 — выходом признака окончания работы устройства.

9 11374

Работу устройства для умножения р-кодов Фибоначчи опишем для случая

pm1, Предлагаемое устройство работает следующим образом. 5

В начальный момент все регистры устройства обнулены, в старших разрядах кольцевых сдвиговых регистров

22, 39, 40 и 4! находятся единицы.

Множимое и множитель, представ- !О ленные в 1-кодах Фибоначчи, поступают в регистры 1 и 2.

По сигналу запуска на входе 12 устройства включается генератор им,пульсов 38. 15

Алгоритм работы устройства опре- . деляется содержимым регистра множителя 2, анализ которого выполняется блоком 5 управления.

Наличие единичного сигнала на входе 34 узла анализа 24 означает, что содержимое регистра множителя в начальный момент равно "0", и результат умножения тоже равен нулю. В этом случае на выходе 14 устройства форми-д руется признак окончания работы устройства, по которому оно завершает работу. В противном случае дальнейшая работа устройства определяется содержимым двух (в,общем случае

30 (р+1)) старших разрядов регистра множителя.

Если содержимое старших разрядов регистра множителя равно "0" (единица на выходе 33 узла анализа 24), то в данном такте умножения формиро35 вать частичные произведения не требуется. Поэтому в блоке управления вырабатываются сигналы сдвига "1" в кольцевом сдвиговом регистре 22 и

40 и сдвига регистра множителя 2 на 2 разряда в сторону старших разрядов (сигналы на выходах 36 и 21 блока управления).

Если содержимое старших разрядов

45 регистра множителя равно 01 (единица на выходе 32 узла анализа.), то блок управления вначале также вырабатывает на выходе 36 сигнал сдвига "1" в регистре 22 на 2 разряда. Это означает, что "1" в регистре 22 будет находиться в том же разряде, что и значащая цифра в регистре множителя, и через открытый ключевой элемент 23 единичный сигнал с выхода 15 поступит в блоки поразрядных произведений 5"

6 для формирования частичных произведений 6 для формирования частичных произведений по формуле (2), (в об59 10. щем случае по формуле (1)). Так как множимое представлено в нормальной форме I êîäà Фибоначчи, то ненулевое частичное произведение может сформироваться лишь в одном из двух из (р+1)) соседних блоков поразрядных произведений. Поэтому выходы, двух блоков 6, а в общем случае (р+1! таких блоков, соединены с входами одно

ro блока 7 суммирования.

По следующему сигналу на выходе 16 блока управления полученные поразрядные произведения складываются в блоках суммирования 7 с текущей суммой поразрядных произведений из регистров 8, после чего новая сумма по сигналу на выходе 17 блока управления запишется в зти же регистры.

В конце такта выполняется сдвиг регистра множителя,на 2 разряда и переход к следующему такту умножения, Если содержимое двух старших разрядов регистра множителя равно 10 (единица на выходе 31 узла анализа), то вначале выполняется сдвиг "l" в регистре 22 на 1 разряд, после чего образуется новая сумма .поразрядных произведений. В конце такта одно. временно со сдвигом регистра множителя на 2 разряда выполняется еще один сдвиг регистра 22 на 1 разряд..

I . В общем случае, если значащая цифра множителя находится в группе (р+1) разрядов на к-том месте, начиная со старших разрядов, то вначале выполняется сдвиг регистра 22 на к разрядов, а в конце такта умножения — на (р+1-к) разрядов.

Умножение выполняется по перечисленным алгоритмам до тех пор, пока содержимое регистра множителя не станет равно нулю (единица на выходе 35 узла анализа). В этом случае в регистрах поразрядных произведений 8 находятся произведения множителя на соответствующие 2, а в об щем случае на (р+1! разряда множимого.

Дальнейшая работа устройства заключается в последовательном сложе- . нии полученных кратных множителя на сумматоре 3.

В. узле выработки управляющих сигналов 30 импульсы от генератора 38 управляют сдвигом "1" в регистре

40 на 1 разряд, При нахождении "1"

s первом разряде регистра 40 происходит сдвиг "1" в регистре 41 íà I разряд, за счет чего каждый иэ регистров

7459

11 11З поразрядных произведений 8 по сигналу на соответствующем выходе шины 18 блока управления через блоки коммута-. ции 9 подключается к сумматору 3, где происходит сложение соответствующего кратного множителя с суммой частичных произведений, находящейся в. регистре 4, и запись новой суммы в тот же регистр.

После того, как все кратные множи теля будут суммированы и в регистМножимое

Содержимое Р 22

Разряды множителя

Такты умножения

10

100010010 0

000000000

000000

1000000

100010010

100000

100

100000

0001000

100100 0

100010010

01

100110110

ШШ

100100

101001000

101001000

2) !01001000

+ 000000000

Тформ

4S где Т вЂ” время формирования частично1

ro произведения, к — число значащих разрядов s множителе, причем

101001000

3) 101001000

+ 100100

k c m/(ð+1) 101101100

ШШ

110010000

1000010000

Сложение кратных множителя:

1) 000000000

+ 101001000

Результат: 6 х 10 60 = 1000010000 (55+5) .. ре частичных произведений 4 образо-,: вано полное произведение множимого на множитель, в блоке управления на выходе 14 сформируется признак окончания работы устройства.

Пример. Умножить число

А=6=010010 на число B=)0=100100 в двоичной фибоначчиевой 1-системе счисления.

10 В таблице показан процесс формирования кратных множителя.

В предлагаемом устройстве общее время умножения:.

jMH1 Форм счм

=.Т + Т

° где Тфор — время формирования кратных множителя;

Тсчм аре суммирования кратных множителя; где m — разрядность множителя. и

Т =. — — — ° Т счм р4.1 2 где и — разрядность множимого

Т2 — время сложения двух р-кодов.

Таким образом, при умножении и-разрядных р-кодов Фибоначчи т

-РАМН 1 равно:

1137459

13 ю и 1 1 р 1 2 причем k. — -, и р+1

В устройстве-прототипе время умножения h-разрядных р-кодов Фибоначчи равно ч Х ТЗ где T> - время формирования кратного множимого, определяемое в основном временем сложения двух предыдущих кратных множимого.

Можно считать, что Т и Т Т так как эти времена в основйом опрецеляются временем сложения двух р-кодов Фибоначчи.

Для оценки достигаемого эффекта введен коэффициент

Тgìí g

Тумм 1

Для различных оснований р-кодов

Фибоначчи этот коэффициент имеет следующие значения:

R=l-2 при р=l;

R=1,2-3 при.р=2;

R=1,3-4 при р=3 и т.д;

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

1! з я

1137459

12 Я я3

32 gf

Составитель В.Березкин

Техред. Т.Дубинчак. Корректор О.Билак

Редактор И.Недолуженко

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4

Заказ )0525/36 Тираж 710 Подписное

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

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