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

 

Изобретение относится к вычислительной технике и может быть использовано при построении высокопроизводительных процессов,оперирзпощих в фибоначчиевой системе исчисления. Цель изобретения - повьшение быстродействия устройства при поточной обработке информации.Устройство состоит из генератора 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 П

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

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

РЕСПУБЛИК (504 G06 F 7 4

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К А BTOPGHOMY СВИДЕТЕЛЬСТВУ (21) 4085818/24-24 (22) 30.06.86 (46) 15.10.87. Бюл. N - 38 (7i) Научно-производственное объединение космических исследований AH АЗССР (72) Я.А.Мамедов, Ф.А.Мамедов и И.З.Животовский (53) 681.325(088.8) (56) Авторское свидетельство СССР

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

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

У 662941, кл. G 06 Р 7/49, 1976. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЦЕЛЫХ

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

Цель изобретения — повышение быстродействия устройства при поточной обработке информации. Устройство сос„„SU„„ I 345 ll 90 А 1 тоит из генератора 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 134

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

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

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

Устройство (фиг. 1) содержит генератор 1 последовательности обобщенных чисел Фибоначчи, блок 2 управления, регистры 3.1-3.4 частичных произведений,сумматоры 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); А = 21;

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

По сигналу запуска, поступающето на вход 9 (фиг. 4а), триггеры 25, 28 и счетчики 23, 30 по R-входам устанавливаются в нулевое состояние.E счетчик 26 по входу 10 устройства записывается число L,îïðåäåëÿþùåå количество циклов умножения.Это число определяется заранее по выражению n/2р где п — разрядность

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

25 операндов или результат первого часЗО тичного произведения равен нулю (см. таблицу такт 1,А 4.1). В этом же такте начинается процесс формирования второго члена 2 ряда Фибоначчи

35 на сумматоре 18.1 генератора 1.Так как в исходном состоянии регистр

21. 1 содержит нули, то на сумматоре

18.1 формируется второй член ряда, равный множимому А„.

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

18. 1 заносится в регистр 19.2 (см. таблицу такт 2,16.2), а результат

45 первой промежуточной суммы — в регистр 3.2.В регистр 6.2 принимается (n-1) разрядов кода множителя.Одновременно в регистр 19. 1 принимается код второгомножимого А,a в регистр 6.1

50 код второго множителя В .На сумматоре

4.1 начинается процесс формирования первого частичного произведения вторых операндов, а на суммагоре 4.2 второго частичного произведения первых операндов. На первый вход сум55 матора 4.2 поступает второй член 2 ряда Фибоначчи с выхода регистра

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

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

1 первому тактовому сигналу (выход 14 блока 2) код множимого А„ принимается регистром 19.1, а код множителя

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

50

V (4) = Ч (3) + V (1) 3 13451

В содержит нуль (см. таблн . такт

2.С 6.2), то этот сигнал с выхода младшего разряда регистра 6.2 стробирует сумматор 4.2, и результат второго частичного произведения окажется равным нулю (см. таблицу такт

2,А 4.2).Аналогично первое частичное произведение вторых операндов тоже равно нулю (см. таблицу такт 2,А

4.1) из-за наличия нуля в младшем разряде кода множителя второго операнда В (см. таблицу такт 2.С 6).

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

Фибоначчи,численно равного первому множимому А,так как содержимое регистра 21.2 равно нулю.Во втором такте, также как и в первом, тактовый сигнал задающего генератора 22,пос- 25 тупая на счетный вход счетчика 23, увеличивает его содержимое на еди— ницу. Состояния остальных элементов блока 2 управления не изменяются.

В этом же такте содержимое регистра

19. 1 заносится в регистр 20.3. На сумматоре 18.2 начинается процесс формирования третьего члена первого

2 ряда Фибоначчи, численно равного коду множимого первого операнда

А4, так как регистр 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 — третий член ряда, численно равного коду множимого, т.е. выполняется рекуррентное соотношение

С выхода регистра 19. 3 по вь|ходу

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

3.3, равного нулю. Так как младший разряд кода множителя в регистре 6.3 содержит единицу (см. таблицу такт

3.С 6.3),то разрешается суммирование на сумматоре 4.3 и результат суммирования окажется равным третьему члену первого ряда (см. таблицу такт

3,А 4.3), так как в регистре 3.3 частичных произведений содержится нуль.

В этом такте также происходит формирование частичных произведений вторых операндов А и В>,а на регистр

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

Таким образом, в третьем такте формируются третье частичное произведение первой пары на сумматоре 4.3 (см. таблицу такт З,А 4.3), второе частичное произведение второй пары ,на сумматоре 4.2 (см. таблицу такт

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

З,А 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 принимаются соответственно коды множителя и множимого четвертой пары операндов А и В .

5 13451

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

19 и сумматора 4: на выходе сумматора 4.1 — первое частичное произведение четвертых

5 операндов (см. таблицу такт 4, А

4.1), а на выходе регистра 19.1 значение первого члена четвертого ряда, численно равное множимому А (см. таблицу такт 4,16.1); на выходе сумматора 4.2 — второе частичное произведение третьей пары операндов А> и В» а на выходе регистра 19.2 — значение второго члена третье"о ряда (см. таблицу такт

4, 16.2); на выходе сумматора 4.3 — значение третьего частичного произведения второй пары операндов А и В (см. таблицу такт 4,А 4.3),а на выходе регистра 19.3 — третий член второго ряда (см. таблицу, такт 4, 16. 3); на выходе сумматора 4.4 — результат умножения А, и В„ (см. таблицу такт 4,А 4.4), если код множителя содержит 2р разрядов. В.противном случае, если код множителя больше, чем 2р, и содержит и разрядов, . L=n/2р разрядов (где Ь вЂ” целое число), то по сигналу блока 2 управления с выхода 13 разрешается дальнейшее умножение.

Это происходит следующим образом.

По четвертому тактовому сигналу задающего генератора 22 счетчик 23, модуль пересчета которого равен 2р, переполняется и сигнал переполнения после задержки на элементе задержки

24 на время, равное времени приема последнего кода в регистр 19.1, устанавливает триггер 25 по Б--входу в единичное состояние, и сигнал логического "0" с его выхода 13 поступает на управляющий вход блока 5 коммутации и разрешае прохождение оставшихся (и-2р) разрядов множителя на вход регистра 6.1.Аналогично этот же сигнал по входу 13 разрешает прохождение суммы с выхода сумматора 18.4 на вход регистра 19. 1. Оцновременно сигнал переполнения счетчика 23 уменьшает содержимое вычитающего счетчика 26 на единицу, коэффициент пересчета которого заранее программируется по входу 10 и выбирается из соотношения L=n/2ð (фиг. 4 с,d,е). В проводимом приме90

6 ре код множителя содержит 8 разрядов, следовательно, L=2. Четвертый тактовый сигнал состояния остальных элементов блока 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 появится результат умножения А1 х В (см. таблицу такт 8 В 4.4).Счетчик 23,блока 2 управления переполняется, сигнал переполнения уменьшает содержимое вычитающего счетчика 26 на единицу.

Одновременно этот же сигнал через элемент 24 задержки подтверждает состояние триггера 25.Так как модуль пересчета вычитающего счетчика 26 равен двум,то после прихода восьмого тактового сигнала по переполнению счетчика 23 он переполняется, а сиг7 134519 нал переполнения через элемент И 27 устанавливает триггер 28 в единичное состояние по его S-входу, так как триггер 25 находился в единичном сос5 тоянии и разрешал прохождение сигналов через элемент И 27. Одновременно сигнал переполнения вычитающего счетчика 26 по счетному входу триггера 25 сбрасывает его в исходное состояние. Сигнал логической "1" с выхода 15 триггера 28 поступает на сбросовые входы регистров 20.1,20,2, 21. 1, 2 1,2 и 3. 1 и в течение р тактов в эти регистры информация не при- 15 нимается. Это необходимо для обеспечения приема новой информации в устройство умножения. Неообходимое количество р тактов отсчитывается счетчиком 30, на счетный вход кото- zp рого тактовые сигналы с задающего генератора 22 поступают через открытый сигналом логической "1" триггера 28 элемент И 29. По истечении р тактов счетчика 30 переполняется и 25 сигнал переполнения устанавливает триггер 28 в исходное состояние по

его счетному входу (фиг. 4 f, g, h).

В восьмом такте в устройство умножения могут быть введены следующие 2р ЗО групп операндов для умножения. В последующие 2р-1 тактов из устройства считываются результаты умножения предыдущих 2р-1 пар операндов по выходу 11 (см. таблицу такт 9,В 4.4, такт В, 4.4,такт 1 t, В4.4). Одновременно с этим в устройство могут быть введены следующие группы операндов для умножения.

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

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

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

Фибоначчи,выход j-го регистра частичных произведений подключен к второму информационному входу j-го сумматора промежуточных сумм, выход 8-го сумматора промежуточных сумм (1

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

f-ro регистра множителя соединены с информационными входами соответст-. вующих разрядов (С+1)-го регистра множителя, выход младшего разряда

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

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

1345190

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

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

ro регистра первой группы соединен с первым ВхОдом i-ro сумматора и яв- 10 ляется -м выходом генератора последовательности обобщенных чисел Фибоначчи, выход 2-го сумматора соединен с информационным входом (1+1)-го регистра первой группы, выход i-rope- )5 гистра ю-й группы (m=2,..., р) соединен с информационным входом i-го регистра (m+1)-й группы, выход i-ro регистра (р+ 1)-й группы соединен с вторым входом х-го сумматора, входы 20 синхронизации всех регистров всех групп соединены с входом синхронизации генератора последовательности обобщенных чисел Фибоначчи,информационные входы узла коммутации соеди- 25 иены с выходом 2р-го сумматора и информационным входом генератора последовательности Обобщениых чисел Фибоначчи,управляющие входы узла коммутации соединены с первым 30 и вторым управляющим входами генератора последовательности обобщенных чисел Фибоначчи,которые соединены соответственно с первым и вторым выхОдами блОка упраВления ВыхОд q го регистра первой группы (q--1,...2р2), соединен с информационным входом iq+p)-го регистра второй группы, информационные входы первого и второго регистров второй группы соединены соответственно с выходами (2р1)-го и (2р)-го регистров первой группы, входы сброса регистров с первого по k-й (k= 1,..., р) групп и с второй по (p+l)-го соединены с вхо—

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

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

1345190

13451 10

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

Редактор M.Êåëåìåø ТехредМ.Дидье

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

Заказ 4920/47 Тираж б70

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

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

Подписное

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