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

 

Союз Соеетскни

Социалистических

Республик

<11662941 (61) Дополнительное к авт. саид-ву(22) Заявлено 020876(21) 238б002/18-24 с присоединением заявки Мо(23) Приоритет

G 06 Р 7/52

Государственный. комитет

СССР по делам изобретений и открытиИ (53) УДК б81 3 (088.8) Опубликовано 150579, Бюллетень Мо 18

Дата опубликования описания 1505.79 (72) Авторы изобретения

A.Ï.CTàõoâ и В.A ° Ëóæåöêèé (71 ) Заявитель

Таганрогский радиотехнический институт им. В.,Ц. Калмыкова. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЦЕЛЫХ

ЧИСЕЛ I

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

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

Это достигается тем, что устрой,ство дополнительно содержит генера1тор последовательности обобщенных чисел Фибоначчи, выход которого сое« динен со вторым входом сумматора, а выход блока управйения соединен с управляющим входом генератора последовательности обобщенных чисел Фибоначчи, вход которого является вторым входом устройства °

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

Устройство содержит генератор, последовательности обобщенных чисел

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

Если множитель A представить В виде, Аа„q (и) а„1(ур(П-Ц+ - + а„qp)O)j

662941

1 О О 1 О О 0 О О . О

О 1 О О 1 О О О О О

О 0 1 О 0 1 О О О О

О 0 О. 1 О О 1 О О О

0 80

1 80

2 80

3 160

4 240

5 320

6 480

8 1040

О О О О 1 0 О 1 О

О

О О 1 О О 1

О О О 1 0 О

0 О 0

0 О О

480

0 О О О О О О 1 О О

480

0 О О О О 0 0 0 1

480

9 1520 0 О О О О О 0 0 0

2000 rO произведение множителя А на множимое В будет равно

4 Ь =Во„ Р(п) В и-1„Р „1)+ - ° + Э а0 р(о) где g (i ) — обобщенное число Фи бон ачР чи, которое определяется следующим образом:

0 при (0 ш ()= 3. нр =0 (j)

Р

<р (j g)+y (i -р-1) яри j >О

Р Р 30 а а О;,1) Частичное произведение В q (iIс учетоМ соотношения (1) определяется как

> АР() =3 (РР((-1)» V (i-Р-<)

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

Образуют два столбца чисел, в левом иэ которых помещается последовательность обобщенных чисел Фибоначчи с начальным условием, равным f., в ней выделяют р-числа Фибоначчи, составляющие: минимальный р-код Фибоначчи множителя A. Во второМ столбце помещаетбя последовательность обобщенных чисел Фибоначчи с начальным условием, равным множимому В. Результат умножения А В образуют путем сложения" всех чисел вторбго столбца, соответ твуюк(йх- выделенным р-числам Фибоначчи первого столбца. При этоМ контрбяи руют, чтобы любое выделениое-для Сложения число второго столбца от -4 стояло от предыдущего и следующего 35

:.,за ним выделенных для сложения чисел

he менее,-чем на -р посредовательно

gàáïîëoæåííûõ чйсел второго столбца.

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

80 на число 25.

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

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

3. Затем происходит сдвиг кода на один разряд в сторону младших разрядов s регистре 4 и фЬрмирование очередного обобщенного числа Фибоначчи генератором 1.

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

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

Состояния генератоРа 1, регистра множителя 4 и регистра частичных произ-. ведений 3, соответствующие каждому такту работы, приведены в таблице.

662941

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

Составитель И.Сигалов

Техред M. Петко Корректор С.Патрушева

Редактор И.Каменская

Тираж 779 Подписное

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

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

Заказ 2701/50

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

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

Источники информации, принятые во внимание при экспертизе

1. Карцев 34.À . Арифметика цифровых машин, М, Наука, 1969, с.350.