Генератор последовательности обобщенных чисел фибоначчи с произвольными начальными условиями

Генератор последовательности обобщенных чисел фибоначчи с произвольными начальными условиями

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

„„SU„„1345181 А1 (51)4 С 06 Р 1 02

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

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

«Р

Ql

1 «а

1р

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4084758/24-24 (22) 30.06.86 (46) 15. 10. 87. Бюл. К 38 (71) Научно-производственное объединение космических исследований АН АЗССР (72) Ф.А.Мамедов и И.З.Животовский (53) 681 ° 325(088.8) (56) Авторское свидетельство СССР

В 1167598,кл. G 06 F 1/02, 1985.

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

Я 662926, кл. G 06 F 1/02, 1970. (54) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ

ОБОБЩЕННЫХ ЧИСЕЛ ФИБОНАЧЧИ С ПРОИЗВОЛЬЩИМИ НАЧАЛЬНЫМИ УСЛОВИЯМИ (57) Изобретение относится к вычислительной технике и предназначено для, формирования последовательностей обобщенных р-чисел Фибоначчи при

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

Цель изобретения вЂ,повышение быстродействия устройства. Устройство содержит коммутатор 5, блок 6 управления и 2р однотипных блоков промежуточных вычислений, каждый из которых состоит из сумматора 1 и регистров 2

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

5181 2

1 134

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

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

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

Генератор обобщенных чисел Фибо-наччи (фиг. 1) содержит сумматоры

1.1-1.4, регистры 2.1-2.4, 3.1-3.4, 4.1-4.4, коммутатор 5, блок 6 управления, вход 7 запуска, вход 8 начальной установки, вход 9 начальных условий и информационные выходы 10.110.4.

Блок 6 управления (фиг. 2) содержит задающий генератор 11, первый счетчик 12, элемент 13 задержки, первый триггер 14, вычитающий счетчик

15, первый элемент И 16, второй триггер 17, второй элемент И 18 и второй счетчик 19.

Сумматоры 1.1-1.4 устройства могут быть выполнены по известной схеме при представлении чисел в "фибоначчиевой системе счисления.

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

Известно, что обобщенные числа Фибоначчи определяются на основании следующего рекуррентного соотношения:

q (n) = N q (п — 1)+ q (и — 1 — р)(1

) P P где п — число членов заданного ряда, N. — начальные условия (j =1,...„m)

1 ш — количество рядов.

При р = 2 соотношение (1) перепишется в виде (n) = N .4 (n-1) + q (n — 3). (2)

1 3 2 т

Приведенная функциональная схема генератора последовательности обобщенных чисел Фибоначчи с произвольными начальными условиями (фиг. 1) со5

ЗО

) 45

55 ответствует рекуррентному соотношению (2).

По сигналу запуска (фиг. 3 q ), поступающему на вход 7 устройства, являющийся первым входом блока 6 управления, счетчики 12 и 19 и триггеры 14 и 17 устанавливаются в состояние "0". По входу 8 устройства в вычитающий счетчик 15 записывается число 1, определяющее количество членов ряда чисел Фибоначчи, подлежащих генерации. Сигнал "1" с инверсного выхода триггера 14, выхода 2 блока

6 управления поступает на второй вход коммутатора 5.. Устройство при этом готово к приему начальных условий для формирования ряда 2-чисел

Фибоначчи. Одновременно по сигналу запуска (фиг. 3 а ) задающий генератор 11 вырабатывает тактирующие импульсы (фиг. 3 ь). поступающие с выхода 1 блока 6 управления на тактирующие входы регистров 2, 3 и 4, и начинается процесс приема в устройство через коммутатор 5 первых 2р групп начальных условий N поступающих на вход 9 устройства (первый вход коммутатора 5). По первому тактовому сигналу в регистр 2.1 с выхода коммутатора 5 принимается код первого начального условия N„ . На выходе 10.1 устройства появляется код первого члена у (1) первого ряда. Так как в

1 исходном состоянии регистры 3.1 и

4.1 содержат нули, то на сумматоре

1.1 начинается процесс формирования второго члена,(1) первого ряда, т.е. ц„(1) + О. Одновременно с этим тактовый сигнал задающего генератора

11 увеличит содержимое первого счетчика 12 блока 6 управления на единицу. Так как второй триггер 17 находится в нулевом состоянии, то сигнал

"О" с его выхода блокирует по первому входу элемент И 18 и тактовый сигнал задающего генератора 11 состояние второго счетчика 19 не изменяет.

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

1.1 — в регистр 2.2. На выходе 10.2 устройства появится код второго члена ц (1) первого ряда. Одновременно с этим в регистр 2.1 принимается код второго начального условия N и на выходе 10.1 устройства появится код первого члена ц,,(2) второго ряда.

1345181

Так как в регистрах 3. 2 и 4 .." здержались нули, то во втором такте на суммаре 1.2 начинается процесс формирования третьего q (1) члена перво3 го ряда, а на сумматоре 1.1 — второго члена ср,(2) второго ряда. В блоке

6 управления при этом содержимое счетчика 12 увеличивается на единицу.

В третьем такте содержимое регистра 3.3 заносится в регистр 4.3, а содержимое регистра 2.2 — в регистр

3.4. В регистр 2.3 принимается результат суммирования с сумматора 1.2.

На выходе 10.3 появится код третьего члена (1) первого ряда, на втором выходе 10.2 — код второго члена у (2)

2 второго ряда. На регистр 2. 1 принимается код третьего начального условия

N и на выходе 10.1 появляется код первого члена cp„(3) третьего ряда.

Так как в регистре 4.3 содержится код „(1), то на сумматоре 1.3 начинается процесс формирования четвертого члена ((1) первого ряда, так как,(1) = ср (1) + (,(1). На сумматорах 1.1 и 1.2 — соответствующие члены второго и третьего рядов. В блоке 6 управления содержимое счетчика 12 увеличивается еще на единицу.

По четвертому тактовому сигналу в регистр 2.1 принимается код четвертого начального условия N< и на первом выходе 10.1 устройства появится код первого члена q (4) четвертого

1 ряда. В этом такте содержимое регистра 3.4 принимается регистром 4.4, ре1зультат суммирования сумматора 1.3 поступает в регистр 2.4. На выходе .10.4 появляется код четвертого члена

Ч (1) первого ряда. Так как в регистре 3.4 содержался код второго члена 2(1) первого ряда, то на сумматоре 1.1 начинается процесс формирования пятого члена (1) первого ряда, так как g (1) = g (1) + р2(1).

В этом же такте счетчик 12 блока 6 управления, коэффициент пересчета которого выбирается равным 2р, переполняется (фиг. 3 с) и сигнал переполнения после задержки на элементе t3 (фиг. 3 o), поступая на единичный вход триггера 14, устанавливает его в состояние "1". Одновременно сигнал с элемента 13 задержки уменьшает содержимое вычитающего счетчика 15 на единицу. Сигнал "1" с прямого выхода триггера 14 по выходу 3 блока 6 управления разрешает прохождение результата суммирования с выхода сумматора 14 через коммутатор 5 на вход регистра 2.1. В четвертом такте также происходит продвижение информации

5 по цепям регистров в порядке, описанном в предыдущих тактах. Содержимое регистра 2.3 заносится в регистр 3.1.

По пятому тактовому сигналу содержимое регистра 2.4 заносится в регистр 3.2, содержимое регистра 3.1— в регистр 4.1, а результат суммирования с сумматора 1.4 — в регистр

2.1. Так как в регистре 4.1 содержится информация о третьем члене у (1) первого ряда, то на сумматоре 1.1 начинается процесс формирования шестого члена первого ряда у (1)

1 — 4 (1) + ч (1). На выходе 10.1 уст о ройства появляется код пятого члена (1) первого ряда. Содержимое регистра 2.4 заносится в регистр 3.2.

В последующих тактах работа устройства аналогична описанному.

25 Информация на выходах устройства приведена в таблице.

В восьмом такте счетчик 12 блока 6 управления переполняется (фиг. 3 с ), а сигнал переполнения через элемент

ЗО 13 задержки (фиг. 3 d) поступает на счетный вход вычитающего счетчика 15 который заранее запрограммирован на вырабатывание устройством определенного количества членов, кратных

1 2р (1 =- 1, 2,...). Если, например, 1 = 2, то в восьмом такте сигнал переполнения вычитающего счетчика 15 через открытый элемент И 16 поступает на единичный вход триггера 17 и

40 устанавливает его в состояние 1 (фиг. 3 9, g ). Сигнал "1" триггера

17 разрешает прохождение тактовых сигналов задающего генератора 11 чеpcs элемент И 18 на счетный вход счетчика 19, коэффициент переполне45 ния которого равен числу р (в описываемом примере р = 2). Сигнал "1" триггера 17 также блокирует регистры

3.1, 3.2 и 4.1, 4.2, устанавливая их в состояние "0". В течение следую50 щих двух тактов (в общем случае р тактов) после восьмого обратные связи с выходов регистров 2.4 и 2.3 оказываются блокированными сигналом

"1" с триггера 17, Одновременно сигналом переполнения вычитающего счетчика 15 триггер 14 по счетному входу устанавливается в исходное состояние "0" и сигналом "0" с его пря1345181 мого выхода (выхода 3 блока 6 управления) блокируется третий вход коммутатора 5, и устройство готово для приема следующих (р + 2)-х групп начальных условий.

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

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

m-x регистров блока промежуточных вычислений, начиная с второго, подключены к входу (ш + 1)-го регистра, выход (р + 1)-го регистра блока промежуточных вычислений подключен к 25 первому входу сумматора, второй вход которого подключен к выходу первого регистра блока промежуточных вычислений, первый выход блока управления подключен к управляющим входам (р + 1) Вц регистров блока промежуточных вычислений, отличающийся тем, что, с целью повьппения быстродействия в него введены (2р — 1) блоков предварительных вычислений и коммутатор, 35 а блок управления содержит задающий генератор, два счетчика, вычитающий счетчик, два триггера, два элемента

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

45 счетчика, выход сумматора .i-го (i

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

"броса всех регистров, начиная с второго каждого х-го (r = 1,...,.р) блока промежуточных вычислений, выходы первых регистров r-х блоков промежуточных вычислений подключены к входам вторых регистров (г + р) — х блоков промежуточных вычислений, выходы первых регистров которых подключены к входам вторых регистров r-х блоков, причем выход задающего генератора подключен к счетному входу первого счетчика и первому входу первого элемента И, второй вход которого подключен к выходу второго триггера, вход установки которого подключен к выходу второго элемента И, первый вход которого подключен к прямому выходу первого триггера, счетный вход которого и второй вход второго элемента И подключены к выходу переполнения вы читающего счетчика, установочный вход которого, входы сброса первого и второго триггеров первого и второго счетчиков подключены к входу задающего генератора, выход переполнений первого счетчика через элемент задержки подключен к установочному входу первого триггера и счетному входу вычитающего счетчика, выход первого элемента И подключен к счетному входу второго счетчика, выход переполнений которого подключен к счетному входу второго триггера.

1 2 3 4 5 6 7 8 9 10 11

10. 1 ср„(1) ср (2) ср, (3) lg (4) (p (1) q (2) 4 (3) ср (4) ср,(1) (p,(2) q,(3) 10. 2 0 V,(1) сс (2) V (3) сР (4) W (1) ср (2) Ч (3) V (4) ср,(1) ср (2) 10.3 0

10.4 0

Выходы

1345181

Такт, № ь(1) y (2) с4(3) сиз(4) с6 (1) сс" (2) q (3) у (4) с э(0 ср (1) ср (2) p (3) 9 (4) ср (1) Q (2) p(3) Q (4) 1345181

Составитель С.Курош

Редактор И.Келемеш Техред И.яндык Корректор С,.Черни

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

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

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

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