Устройство для умножения целых чисел в р-кодах Фибоначчи Советский патент 1987 года по МПК G06F7/49 

113

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

Целью изобретения является повышение быстродействия устройства при поточной обработке информации.

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

Устройство (фиг. 1) содержит генератор 1 последовательности обобщенных чисел Фибоначчи, блок 2 управления, регистры 3. частичных произведений,сумматоры 4.1-4.4 промежуточных сумм, блок 5 коммутации, регистры 6.1-6.4 множителя,вход 7 множителя,вход 8 множимого,вход 9 запуска, вход 10 задания количества циклов умножения, выход 11.Блок 2 управления имеет выходы 12 - 15, Генератор 1 имеет выходы 16 (16.1-16.4).

Генератор 1 последовательности обобщенных чисел Фибоначчи (фиг. 2) содержит узел 17 коммутации, сумматоры 18о1-18.4, регистры 19.1-19.4; 20.1-20.4; 21.1-21.4.

Блок 2 управления (фиг. 3) содержит задающий генератор 22,первый суммирующий счетчик 23 элемент 24 задержки, первый тригге з 25,. вычитающий счетчик 26,, первый элемент И 27, второй триггер 28, второй элемент И 29 и второй суммирующий счетчик 30.

Работу устройства рассмотрим на примере умножения четырех пар чисел А, 25; Б, 5(00100100); Aj 21;

В 8(01001000); Аа 35; Вз (01000000); А 43; В 3(00010000) (в скобках указаны значения чисел в кодах Фибоначчи). Работа устройства проиллюстрирована на таблице.

По сигналу запуска, nocTynaioniero на вход 9 (фиг. 4а), триггеры 25, 28 и счетчики 23, 30 по R-входам устанавливаются в нулевое состояние.Б счетчик 26 по входу 10 устройства записывается число L определяющее количество циклов умножения.Это число определяется заранее по выражению п/2р где п - разрядность

5

1902

кода множителя). На выходе 12 триггера 25 присутствует сигнал логическая О , который,поступая на управляющий вход блока 5 коммутации устройства и управляющий вход узла 17 коммутации генератора 1, разрешает прием на вход генератора 1 кода множимого А , а на вход регистра 6.1 множителя - кода множителя В . По

5

0

первому тактовому сигналу (выход 14 блока 2) код множимого А принимается регистром 19.1, а код множителя В, - регистром множителя 6.1. На выходе 16.1 регистра 19.1 появляется первое число 2 ряда Фибоначчи, равное начальному условию А,- (см. таблицу такт 1,16.1). Это число по выходу 16.1 генератора 1 поступает Q на сумматор 4.1 промежуточных сумм, где происходит формирование первой промежуточной суммь. Так как младший разряд минимального кода множителя содержит нуль, то на сумматоре 4.1 под воздействием сигнала, поступающего- с младшего разряда регист- ра 6.1 на его стробирующга вход,суммирования не происходит и результат первой промеж гточной суммы первых операндов или результат первого частичного произведения равен нулю (см. таблицу такт 1,А .4.1). В этом же такте начинается процесс формирования второго члена 2 ряда Фибоначчи на сумматоре 18.1 генератора 1.Так как в исходном состоянии регистр 21.1 содержит нули, то на сумматоре 18.1 формируется второй член ряда, равный множимому А..,.

По второму тактовому сигналу с выхода 14 блока 2 управления (фиг.4в) результат суммирования на сумматоре

18.1заносится в регистр 19.2 (см. таблицу такт 2,16.2), а результат первой промежуточной суммы - в регистр 3 .2. В регистр 6 . 2 принимается (п-1) разрядов кода множителя.Одновременно в регистр 19.1 принимается код второго множимого А,,а в регистр 6.1 - код второго множителя Б2-На сумматоре 4.1 начинается процесс формирования первого частичного произведения вто- рьсх операндов, а на сумматоре 4.2 - второго частичного произведения первых операндов. На первый вход сумматора 4.2 поступает второй член 2 ряда Фибоначчи с вь.гхода регистра

19.2(см. таблицу такт 2,16.1.Так как второй разряд кода множителя

5

0

5

0

5

3

B-f содержит нуль (см. таблн ; такт 2.С 6.2), то этот сигнал с выхода младшего разряда регистра 6.2 стробирует сумматор .2, и результат

второго частичного произведения окажется равным нулю (см. таблицу такт 2,А 4.2).Аналогично первое частичное произведение вторых операндов тоже равно нулю (см. таблицу такт 2,А 4.1) из-за наличия нуля в младшем разряде кода множителя второго операнда Bj (см. таблицу такт 2.С 6). В дальнейшем значения частичных произведений можно проследить по табли- це, где также указаны значения членов, формируемых генератором 1 четы- рех 2 рядов Фибоначчи.Во втором такте начинается процесс формирования третьего члена первого ряда Фибоначчи,численно равного первому множимому А,так как содержимое регистра 21.2 равно нулю.Во втором такте, также как и в первом,тактовый сигнал задающего генератора 22,пос- тупая на счетный вход счетчика 23, увеличивает его содержимое на единицу. Состояния остальных элементов блока 2 управления не изменяются В этом же такте содержимое регистра

19.1заносится в регистр 20.3. На сумматоре 18.2 начинается процесс формирования третьего члена первого 2 ряда Фибоначчи, численно- равного коду множимого первого операнда А, так как регистр 21.2 содержит нуль перед выполнением третьего такта.

По третьему тактовому сигналу результат суммирования на сумматоре 4.2 заносится в регистр 3.3, а содержимое регистра 6.2 - в регистр 6.3. Результат суммирования на сумматоре 18.2 заносится в регистр 19.3, а содержимое регистра 20.3 - в регистр 21.3.Содержимое регистра

19.2заносится в регистр 20.4. На сумматоре 18.3 начинается процесс формирования четвертого члена первого ряда ,числено равного сумме третьего и первого членов ряда,так

как в регистре 21.3 содержится значение первого члена первого ряда, а в регистре 19.3 - третий член

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

соотношение

(f.(3) + (/1).

5 0 5 о

Q

Ь

5

904

С выхода регистра 19.3 по выходу

16.3третий член ряда поступает на вход сумматора 4.3 (см. таблицу такт 3,16.3),на другой вход которого поступает значение второго частичного произведения с выхода регистра

3.3,равного нулю. Так как младший разряд кода множителя в регистре 6.3 содержит единицу (см. таблицу такт З.С 6.3),то разрешается суммирование на сумматоре 4.3 и результат суммирования окажется равным третьему члену первого ряда (см. таблицу такт 3,А 4.3),так как в регистре 3.3 частичных произведений содержится нуль. В этом такте также происходит формирование частичных произведений вторых операндов Aj и на -регистр 6.1 и регистр 19.1 принимаются соответствен FIO коды множителя и множимого третьей пары операндов Aj и В„. Таким образом, в третьем такте формируются третье частичное произведение первой пары на сумматоре 4.3 (см. таблицу такт 3,А 4.3), второе частичное произведение второй пары

;На сумматоре 4.2 (см. таблицу такт 3, А 4.2), и первое частичное про- (изведение третьей пары операндов на сумматоре 4.1 (см. таблицу такт 3,А 4.1).

В четвертом такте результат суммирования на сумматоре 18.3 заносится в регистр 19.4,содержимое регистра

20.4- в регистр 21.4, содержимое регистра 19.3 - в регистр 20.1, а

на сумматоре 18.4 начинается процесс формирования четвертого члена первого ряда. Результат суммирования на сумматоре 4.3 заносится в регистр

3.4.Значение четвертого члена первого ряда с выхода регистра 19.4 по выходу 16.4 (см. таблицу такт 4, 16.4) поступает на вход сумматора 4.4, на другой вход которого с выхода регистра 3.4 поступает результат третьего частичного произведения первых операндов. Так как младший разряд кода множителя в регистре 6.4, поступившего с выхода регистра 6.3, равен нулю (см. таблицу такт 4,С 6.4), то результат четвертого частичного произведения первой пары окажется равным предьздущему значению. В этом

же такте в регистр 6.1 ив регистр 19.1 принимаются соответственно коды множителя и множимого четвертой пары операндов А 4 и В 45 .

В четвертом такте имеются следующие значения на выходах регистров 19 и сумматора 4:

на выходе сумматора 4.1 - первое частичное произведение четвертых операндов (см. таблицу такт 4, А 4.1), а на выходе регистра 19.1 - значение первого члена четвертого ряда, численно равное множимому А4 (см. таблицу такт 4,16,1);

на выходе сумматора 4,2 - второе частичное произведение третьей пары операндов А иВз,а на выходе регистра 19.2 - значение второго чле- на третьего ряда (см. таблицу такт 4,16.2);

на выходе сумматора 4.3 - значение третьего частичного прои зведе- ния второй пары операндов Aj и В2 (см. таблицу такт 4,А 4.3),а на выходе регистра 19.3 - третий член второго ряда (см. таблицу,такт 4, 16.3);

на выходе сумматора 4.4 - резул тат умножения А, и В (см. таблицу такт 4,А 4.4), еслИ код множителя содержит 2р разрядов. В.противном случае, если код множителя больше, чем 2р, и содержит п разрядов, . разрядов (где L - целое число) , то по сигналу блока 2 управления с выхода 13 разрешается дальнейшее умножение.

Это происходит следующим образо По четвертому тактовому сигналу задающего генератора 22 счетчик 23, модуль пересчета которого равен 2р переполняется и сигнал переполнения после задержки на элементе задержк 24 на время,равное времени приема последнего кода в регистр 19.1, устанавливает триггер 25 по S-входу в единичное состояние, и сигнал логического О с его выхода 13 пос- тупает на управляющий вход блока 5 коммутации и разрешает прохождение оставшихся (п-2р) разрядов множителя на вход регистра 6.1.Аналогично этот же сигнал по входу 13 разреша- ет прохождение суммы с выхода сумматора 18.4 на вход регистра 19.1. Одновременно сигнал переполнения счетчика 23 уменьшает содержимое вычитающего счетчика 26 на единицу, ко эффициент пересчета которого заранее программируется по входу 10 и выбирается из соотношения (фиг. 4 c,d,e). В проводимом приме

5 Q

Q Q g

5

906

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

По пятому тактовому сигналу результат суммирования на сумматоре 18.4 через узел 17 коммутации принимается регистром 19.1 (см. таблицу, такт 5,16.1), (п-2р) разряды кода множителя через блок 5 коммутации принимаются регистром 6.1, а результат суммирования на сумматоре 4.4 принимается регистром 3.1. На вход сумматора 4.1 с выхода 16.1 поступает значение пятого члена первого ряда (см. таблицу такт 5,16.1). В этом такте младший разряд кода множителя содержит нуль (см. таблицу такт 5.Д 6.1), поэтому результат суммирования на сумматоре 4.1 численно будет равен предыдущему значению частичного произведения (см. таблицу такт 5.В 4.1). В пятом такте также начинается процесс формирования шестого члена первого ряда на сумматоре 18.1, так как содержимое регистра 20.1, равное третьему члену первого ряда, перепишется в регистр 21.1.В этом же такте содержимое регистра 19.4 принимается регистром 20.2.

В последующих тактах работа устройства аналогична предьщущим тактам и продолжается до появления значения восьмого члена первого ряда на выходе 16.1 регистра 19.4 (см. таблицу такт 8, 16.4). На выходах остальных элементов устройства присутствуют соответствующие члены остальных четырех рядов и частичные произведения оставшихся трех пар операндов (см. таблицу такт 8,16.3, такт 16.2, 16.1).

По восьмому тактовому сигналу на выходе сумматора 4.4 появится результат умножения А х В (см. таблицу такт 8,В 4.4).Счетчик 23 .блока 2 уп- равл ения переполняется,сигнал переполнения уменьшает содержимое вычитающего счетчика 26 на единицу. Одновременно этот же сигнал через элемент 24 задержки подтверждает состояние триггера 25.Так как модуль пересчета вычитающего счетчика 26 равен двум,то после прихода восьмого тактового сигнала по переполнению счётчика 23 он переполняется, а сиг71345

нал переполнения через элемент И 27 устанавливает триггер 28 в единичное состояние по его S-входу, так как триггер 25 находился в единичном состоянии и разрешал прохождение сигналов через элемент И 27. Одновременно сигнал переполнения вычитающего счетчика 26 по счетному входу триггера 25 сбрасывает его в исходное ю состояние. Сигнал логической 1 с выхода 15 триггера 28 поступает на сбросовые входы регистров 20.1,20,2, 21.1, 21,2 и 3.1 и в течение р тактов в эти регистры информация не при- is ной обработке информации, в устройнимается. Это необходимо для обеспечения приема новой информации в устройство умножения. Неообходимсе количество р тактов отсчитывается счетчиком 30, на счетный вход которого тактовые сигналы с задающего генератора 22 поступают через открытый сигналом логической 1 триггера 28 элемент И 29. По истечении р тактов счетчика 30 переполняется и сигнал переполнения устанавливает триггер 28 в исходное состояние по его счетному входу (фиг. 4 f, g, h). В восьмом такте в устройство умножения могут быть введены следующие 2р групп операндов для умножения. В последующие 2р-1 тактов из устройства считываются результаты умножения предыдущих 2р-1 пар операндов по выходу 11 (см. таблицу такт 9,В 4.4, такт В, 4.4,такт 11, В4.4). Одновременно с этим в устройство могут быть введены следующие группы операндов для умножения.

Таким образом, ройство позволяет

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

20

35

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

25 промежуточных сумм (,...,2p) соединен с J-M выходом генератора последовательности обобщенных чисел Фибоначчи,выход j-ro регистра частичных произведений подключен к второму

30 информационному входу j-ro сумматора промежуточных сумм, выход -го сумматора промежуточных сумм ( 1,..., 2р-1) подключен к информационному входу (+1)-го регистра частичных произведений, апход 2р-го сумматора промежуточных сумм соединен с выходом устройства и с информационным входом первого регистра частичных произведений,выход блока

предлагаемое уст- о коммутации подключен к информацион- одновременно умно- ному входу первого регистра множителя, выходы (п-) старших разрядов -го регистра множителя соединены с информационными входами соответст-.

g вующих разрядов (.+ 1)-го регистра множителя, выход младшего разряда i-ro регистра множителя (i 1,..., 2р) соединен со стробирующим входом соответствующего сумматора промежуgQ точных сумм, информационные входы

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

55

8

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

20

35

30

55

циклов умножения блока управления подключены соответственно к одноименным входам устройства, в генераторе последовательности обобщенных чисел Фибоначчи выход узла коммутации соединен с информационным входом первого регистра первой группы, выход i- го регистра первой группы соединен с первым вхс)дом i-ro сумматора и является i-M выходом генератора последовательности обобщенных чисел Фибоначчи, выход В-го сумматора соединен с информационным входом (+1)-го регистра первой группы, выход i-ro регистра ш-й группы (,..., р) сое динен с информацйонньм входом i-ro регистра (т+1)-й группы, выход i-ro регистра (р+1)-й группы соединен с вторым входом i-ro сумматора,входы синхронизации всех регистров всех групп соединены с входом синхронизации генератора последовательности обобщенных чисел Фибоначчи,информационные входы узла коммутации соединены с выходом 2р-го сумматора и информационным входом генератора последовательности обобщенных чисел- Фибоначчи,управляющие входы узла коммутации соединены с первым и вторым управляющим входами генератора последовательности обобщенных чисел Фибоначчи,которые соединены соответственно с первым и вторым выходами блока управления, выход q-ro регистра первой группы (,,..2p- 2), соединен с информационным входом (q+p)-ro регистра второй группы, информационные входы первого и второго регистров второй группы соединены соответственно с выходами (2р- 1)-го и (2р)-го регистров первой группы, входы сброса регистров с первого по k-й (,..., р) групп и с второй по (р+1)-го соединены с входом сброса генератора последовательности обобщенных чисел Фибоначчи,который подключен к четвертому выходу блока управления.

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

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

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

с прямым и инверсным выходами первого триггера, четвертый выход блока управления соединен с прямым выходом второго триггера, вторые вхо45

ды первого и второго элементов И соединены соответственно с выходом переполнения вычитающего счетчика и выходом задающего генератора.

12

-и

е JlJlJTJnJ lJlJlJnJlJ T rLn

Составитель В.Березкин Редактор М.Келемеш Техред М.Двдьт

Заказ 4920/47 Тираж 670Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

фи&Л

Корректор С.Черни

Изобретение относится к вычислительной технике и может быть использовано при построении высокопроизводительных процессов,оперирзпощих в фибоначчиевой системе исчисления. Цель изобретения - повьшение быстродействия устройства при поточной обработке информации.Устройство состоит из генератора 1 последовательности обобщенных чисел Фибоначчи, блока 2 управления, регистров 3.1 - 3.4 частичных произведений,сумматоров 4.1-4.4 промежуточных сумм,блока 5 коммутации, регистров 6.1-6.4 множителя,входов 7,8 множителя и множимого.Внешний сигнал, поступающий на вход 9 запуска,сбрасывает триггеры и счетчики блока 2 управления в нулевое состояние. По входу 10 устройства в блок 2 управления записывается число L, определяющее количество циклов умножения. По так- тов ым сигналам и сигналам управления с выхода блока 2 управления обеспечивается умножение 2р пар операндов, причем на умножение первой пары затрачивается п тактов,после чего в каждом такте из устройства считываются результаты умножения последующих операндов. 1 з.п. ф-лы, 4 ил., 1 табл. 7, i (Л со .4 СЛ со iftue.t П