Генератор последовательности обобщенных чисел Фибоначчи с произвольными начальными условиями Советский патент 1987 года по МПК G06F1/02 

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

, Цель изобретения - повышение быстродействия устройства.

На фиг. 1 приведена функциональная схема предложенного устройства ()j на фиг. 2 - функциональная схема блока управленияi на фиг. 3 - временная диаграмма работы блока управления. В генераторе последовательности

обобщенных чисел Фибоначчи с произ- 15 управления поступает на второй

20

30

вход коммутатора 5. Устройство при этом готово к приему начальных условий для формирования ряда 2-чисел Фибоначчи. Одновременно по сигналу запуска (фиг. За) задающий генератор 11 вырабатывает тактирующие импульсы (фиг. 3 б),| поступающие с выхода 1 блока 6 управления на тактирующие входы регистров 2, 3 и 4д и ления, вход 7 запуска, вход 8 началь- 25 начинается процесс приема в устройст- ной установки, вход 9 начальных ус- во через коммутатор 5 первьрс 2р групп

начальных условий , поступающих на вход 9 устройства (первый вход коммутатора 5). По первому тактовому сигналу в регистр 2.1 с выхода коммутатора 5 принимается код первого начального условия N, . На выходе 10.1 устройства появляется код первого члена If (1) первого ряда. Так как в исходном состоянии регистры 3.1 и

Of- ,

4.1 содержат нули, то на сумматоре 1.1 начинается процесс формирования второго члена Ч , (1) первого ряда, т.е. Ч(1) + 0. Одновременно с этим тактовый сигнал задающего генератора 11 увеличит содержимое первого счетчика 12 блока 6 управления на единицу. Так как второй триггер 17 находится в нулевом состоянии, то сигнал О с его выхода блокирует по перво1/ (п) (п - 1)+ Ц|р (п - 1 - р),(1 ) му входу элемент И 18 и тактовый

сигнал задающего генератора 11 сосгде п - число членов заданного ряда тояние второго счетчика 19 не изменя- N. - начальные условия ( , . . . ,,т); ет.

- количество рядов.

50

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

Генератор обобщенных чисел Фибоначчи (фиг. 1) содержит сумматоры 1.1-1.4, регистры 2.1-2.4, 3.1-3.4, 4.1-4.4, коммутатор 5, блок 6 управловий и информационные вьпсоды 10.1- 10.4.

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

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

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

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

40

.45

га - количество рядов. При р 2 соотношение (1) перепишется в виде

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

/(п) Nj-L| (n- 1) + (f(n - 3)

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

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

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

.45

50

55

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

313

Так как э регистрах 3.2 и 4,2 эдер- жались нули, то во втором такте на суммаре 1.2 начинается процесс формирования третьего t/,(1) члена первого ряда, а На сумматоре 1.1 - второго члена / (2) второго ряда. В блоке 6 управления при этом содержимое счетчика 12 увеличивается на единицу.

В третьем такте содержимое регист-чд держимое регистра 2.4 заносится в

ра 3.3 заносится в регистр 4.3, а содержимое регистра 2.2 - в регистр 3.4. В регистр 2.3 принимается результат суммирования с сумматора 1.2. На выходе 10.3 появится код третьего члена (/.(1) первого ряда, на втором выходе 10.2 - код второго члена „(2) второго ряда. На регистр 2.1 принимается код третьего начального условия N. и на выходе 10.1 появляется код первого члена (д (3) третьего ряда. Так как в регистре 4.3 содержится код i,(1)j то на сумматоре 1.3 начинается процесс формирования четвертого члена (1) первого ряда, так как М 4(1) %(1) + )- На сумматорах 1.1 и 1.2 - соответствующие члены второго и третьего рядов. В блоке 6 управления содержимое счетчика 12 увеличивается еще на единицу. По четвертому тактовому сигналу в регистр 2.1 принимается код четвертого начального условия N и на первом выходе 10.1 устройства появится код первого члена L (4) четвертого ряда. В этом такте содержимое регистра 3.4 принимается регистром 4.4, ре- зультат суммирования сумматора 1 .3 поступает в регистр 2.4. На выходе ;10.4 появляется код четвертого члена

Ч (.(1) первого ряда. Так как в регистре 3.4 содержался код второго члена tf. первого ряда, то на сумматоре 1.1 начинается процесс формирования пятого члена 4(1) первого ряда, так как cfjCD Ч ф) + fiCD- В этом же такте счетчик 12 блока 6 управления, коэффициент пересчета которого выбирается равным 2р, переполняется (фиг. Зф) и сигнал переполнения после задержки на элементе 13 (фиг. 3 о), поступая на единичный вход триггера 14, устанавливает его в состояние 1. Одновременно сигнал с элемента 13 задержки уменьшает содержимое вычитающего счетчика 15 на единицу. Сигнал 1 с прямого выхода триггера 14 по выходу 3 блока 6 управления разрешает прохождение ре25

30

регистр 3.2, содержимое регистра 3 в регистр 4.1, а результат суммиро вания с сумматора 1.4 - в регистр 2.1. Так как в регистре 4.1 содерж

15 ся информация о третьем члене ел ( первого ряда, то на сумматоре 1.1 начинается процесс формирования ше того члена первого ряда (/ (1) (1) + УЗ (1) На выходе 10.1 ус

2Q ройства появляется код пятого член (/ (1) первого ряда. Содержимое ре гистра 2.4 заносится в регистр 3.2 В последующих тактах работа устрой ства аналогична описанному.

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

В восьмом такте счетчик 12 блок управления переполняется (фиг, 3с а сигнал переполнения через элемен 13 задержки (фиг. 3d) поступает н счетный вход вычитающего счетчика который заранее запрограммирован н вырабатывание устройством определе ного количества членов, кратных 1«2р (1 1, 2,,..). Если5 наприме 1 2, то в восьмом такте сигнал п реполнения вычитающего счетчика 15 через открытый элемент И 16 поступ ет на единичный вход триггера 17 и устанавливает его в состояние 1 (фиг. ЗЪ, к). Сигнал 1 триггера 17 разрешает прохождение тактовых сигналов задающего генератора 11 ч рез элемент И 18 на счетный вход счетчика 19, коэффициент переполне ния которого равен числу р (в опис ваемом примере р 2). Сигнал 1 триггера 17 также блокирует регист 3.1, 3.2 и 4.1, 4.2, устанавливая их в состояние О. В течение след щих двух тактов (в общем случае р тактов) после восьмого обратные св зи с выходов регистров 2.4 и 2.3 оказываются блокированными сигнало 1 с триггера 17. Одновременно сигналом переполнения вычитающего счетчика 15 триггер 14 по счетном входу устанавливается в исходное с тояние О и сигналом О с его пр

35

40

45

50

55

зультата суммирования с выхода сумматора 14 через коммутатор 5 на вход регистра 2.1. В четвертом такте также происходит продвижение информации по цепям регистров в порядке, описанном в предыдущих тактах. Содержимое регистра 2.3 заносится в регистр 3.1. По пятому тактовому сигналу со

регистр 3.2, содержимое регистра 3.1 - в регистр 4.1, а результат суммирования с сумматора 1.4 - в регистр 2.1. Так как в регистре 4.1 содержится информация о третьем члене ел (1) первого ряда, то на сумматоре 1.1 начинается процесс формирования шестого члена первого ряда (/ (1) (1) + УЗ (1) На выходе 10.1 устройства появляется код пятого члена (/ (1) первого ряда. Содержимое регистра 2.4 заносится в регистр 3.2. В последующих тактах работа устройства аналогична описанному.

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

В восьмом такте счетчик 12 блока 6 управления переполняется (фиг, 3с), а сигнал переполнения через элемент 13 задержки (фиг. 3d) поступает на счетный вход вычитающего счетчика 15, который заранее запрограммирован на вырабатывание устройством определенного количества членов, кратных 1«2р (1 1, 2,,..). Если5 например, 1 2, то в восьмом такте сигнал переполнения вычитающего счетчика 15 через открытый элемент И 16 поступает на единичный вход триггера 17 и устанавливает его в состояние 1 (фиг. ЗЪ, к). Сигнал 1 триггера 17 разрешает прохождение тактовых сигналов задающего генератора 11 че- рез элемент И 18 на счетный вход счетчика 19, коэффициент переполнения которого равен числу р (в описываемом примере р 2). Сигнал 1 триггера 17 также блокирует регистры 3.1, 3.2 и 4.1, 4.2, устанавливая их в состояние О. В течение следующих двух тактов (в общем случае р тактов) после восьмого обратные свя - зи с выходов регистров 2.4 и 2.3 оказываются блокированными сигналом 1 с триггера 17. Одновременно сигналом переполнения вычитающего счетчика 15 триггер 14 по счетному входу устанавливается в исходное состояние О и сигналом О с его пря

5

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

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

Формула изобретения Генератор последовательности обобщенных чисел Фибоначчи с произвольными начальными условиямиj содержа- щий блок управления и блок промежуточных вычислений, содержащий сумматоры и (р + 1) регистров, причем выход первого регистра блока подключен к первому выходу генератора выходы т-х регистров блока промежуточных вычисленийJ начиная с второго$ подключены к входу (т + 1)-го регистра, выход (р + 1)го регистра блока промежуточных вычислений подключен к первому входу сумматора, второй вход которого подключен к выходу первого регистра блока промежуточных вычислений, первый выход блока управления подключен к управляющим входам (р+ 1 регистров блока промежуточных вычислений, отличающийся тем, 4TOj, с целью повьш1ения быстродействи в него введены (2р - 1) блоков предварительных вычислений и коммутатор, а блок управления содержит задающий генератор, два счетчика,, вычитающий счетчик, два триггера, два элемента И и элемент задержки, причем первый информационный вход коммутатора под- ключен к информационному входу генератора, вход запуска которого подключен к входу задающего генератора, вход начальной установки которого подключен к входу данных вычитающего счетчика, выход сумматора i-ro (i 1,...,2р - 1) блока промежуточных вычислений подключен к входу первого регистра (i + 1)-го блока проме- жуточных вычислений, выход сумматора 2р-го блока промежуточных вычисле

5 о Q

5

181б

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

nj--

nJ jnJbTTJTTlJ

с- и -JJ.JJ-.

иLJ

е /

и

фигЗ

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