Генератор последовательности обобщенных чисел фибоначчи с произвольными начальными условиями — SU 1345181 (original) (raw)

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК ЯО 13451 А(51)4 С 0 ИСАНИЕ ИЗОБРЕТЕНИ ГОСУДАРСТВЕННЫЙ НОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ А ВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Научно-производственное объединение космических исследований АН АЗССР (72) ф.А.Мамедов и И.З.Животовский (53) 681325(088.8)(56) Авторское свидетельство СССР В 1167598,кл. С 06 Р 1/02, 1985,Авторское свидетельство СССР У 662926, кл. С 06 Р 1/02, 1970. (54) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ ОБОБЩЕННЫХ ЧИСЕЛ ФИБОНАЧЧИ С ПРОИЗВОЛЬНКИ НАЧАЛЬНЫМИ УСЛОВИЯМИ (57) Изобретение относится к вычислительной технике и предназначено для, формирования последовательностей обобщенных р-чисел фибоначчи при построении высокопроизводительных вычислительных систем, оперирующихв "фибоначчиевой" системе счисления.Цель изобретения в ,повышение быстродействия устройства, Устройство содержит коммутатор 5, блок 6 управления и 2 р однотипных блоков промежуточных вычислений, каждый из которыхсостоит из сумматора 1 и регистров 2Поставленная цель достигается за счетвведения 2 рблоков промежуточныхвычислений. Одновременное формирование 2 р числовых последовательностейобеспечивается сигналами управленияблока 6 управления так,что в каждомтакте из устройства считываютсязначения 2 р членов формируемых числовых последовательностей, 3 ил,где и - число членов заданного ряда,Ы, - начальные условия ( =1,ш)ш - количество рядов.При р = 2 соотношение (1) перепишется в виде 1 134Изобретение относится к вычислительной технике и предназначено для генерирования последовательности р-чисел Фибоначчи с произвольными начальными условиями., Цель изобретения - повышение быстродействия устройства.На фиг, 1 приведена функциональная схема предложенного устройства (р=2) на фиг, 2 - функциональная схема блока управления; на фиг3 - временная диаграмма работы блока управления.В генераторе последовательности обобщенных чисел Фибоначчи с произвольными начальными условиями 2 р однотипных блоков промежуточных вычислений, каждый из которых состоит из сумматора и (р + 1) регистров (в приведенном примере р = 2).Генератор обобщенных чисел Фибо-. наччи (фиг, 1) содержит сумматорь 1 1.1-1.4, регистры 2.1-2.4, 3.1-3.4, 4.1-4,4, коммутатор 5, блок 6 управления, вход 7 запуска, нход 8 начальной установки, вход 9 начальных условий и информационные выходы 10.1- 10.4.Блок 6 управления (фиг. 2) содержит задающий генератор 11, первый счетчик 12, элемент 13 задержки, первый триггер 14, вычитающий счетчик 15, первый элемент И 16, второй триггер 17, второй элемент И 18 и второй счетчик 19.Сумматоры 1.1-1.4 устройства могут быть выполнены по известной схеме при представлении чисел в "фибоначчиевойсистеме счисления.Устройство работает следующим образом.Известно, что обобщенные числа Фибоначчи определяются на оснОвании следующего рекуррентного соотношения:(и) = И у (и - 1)+(и - 1 - р),(1Р 1 Р Р(и) = И 4 (и - 1) +(и - 3) . (2)1 1 2 2 Приведенная функциональная схема генератора последовательности обобщенных чисел Фибоначчи с произвольными начальными условиями (фиг. 1) со 5181 2 ответствует рекуррентному соотношению (2).По сигналу запуска (фиг. 3 а ), поступающему на вход 7 устройства, являющийся первым нходом блока 6 управления, счетчики 12 и 19 и триггеры 14 и 17 устанавливаются в состояние "0", По входу 8 устройства в вычитающий счетчик 15 записывается число 1, определяющее количество членов ряда чисел Фибоначчи, подлежащих генерации. Сигнал "1" с инверсного выхода триггера 14, выхода 2 блока б управления поступает на второй вход коммутатора 5, Устройство при этом готово к приему начальных условий для формирования ряда 2-чисел Фибоначчи, Одновременно по сигналу запуска (фиг. 3 д ) задающий генератор 11 вырабатывает тактирующие импульсы (фиг. 3 ). поступающие с выхода 1 блока 6 управления на тактирующие входы регистров 2, 3 и 4, и начинается процесс приема в устройство через коммутатор 5 первых 2 р групп начальных условий И , поступающих на вход 9 устройства (первый вход коммутатора 5). По первому тактоному сигналу в регистр 2,1 с выхода коммутатора 5 принимается код первого начального условия И, На выходе 10. 1 устройства появляется код первого члена у (1) первого ряда, Так как н исходном состоянии регистры 3,1 и 4.1 содержат нули, то на сумматоре 1.1 начинается процесс формирования второго члена ,(1) первого ряда, т.е. ц (1) + О. Одновременно с этим тактовый сигнал задающего генератора 11 увеличит содержимое первого счетчика 12 блока 6 управления на единицу. Так как второй триггер 17 находится в нулевом состоянии, то сигнал "0" с его выхода блокирует по первому входу элемент И 18 и тактовый сигнал задающего генератора 11 состояние второго счетчика 19 не изменяет.Во втором такте содержимое регистра 2.1 заносится в регистр 3.3, а результат суммирования на сумматоре 1.1 - в регистр 2.2. На выходе 10.2 устройства появится код второго члена ц (1) первого ряда. Одновременно с этим в регистр 2,1 принимается код второго начального условия И и на выходе 10.1 устройства появится код первого члена ц(2) второго ряда,5 10 15 20 25 30 35 40 ) 4550 55Так как в регистрах 3. 2 и 4, 2 здержались нули, то во втором такте на суммаре 1,2 начинается процесс формирования третьего(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 принимается код третьего начального условия И и на выходе 10.1 появляется код первого члена (3) третьего ряда, Так как в регистре 4.3 содержится код (1), то на сумматоре 1.3 начинается процесс формирования четвертого члена (р (1) первого ряда, так как ,(1) = ср (1) + ,(1). На сум - маторах 1.1 и 1,2 - соответствующие члены второго и третьего рядов. В блоке 6 управления содержимое счетчика 12 увеличивается еще на единицу.По четвертому тактовому сигналу в регистр 2.1 принимается код четвертого начального условия И и на первом выходе 10.1 устройства появится код первого члена у (4) четвертого1ряда. В этом такте содержимое регистра 3.4 принимается регистром 4.4, ре 1 зультат суммирования сумматора 1.3 поступает в регистр 2.4. На выходе 10.4 появляется код четвертого члена Ч (1) первого ряда. Так как в регистре 3.4 содержался код второго члена (1) первого ряда, то на сумматоре 1,1 начинается процесс формирования пятого члена (1) первого ряда, так как Ц (1) = Ц (1) + р(1) . В этом же такте счетчик 12 блока 6 управления, коэффициент пересчета которого выбирается равным 2 р, переполняется (фиг, 3 ж ) и сигнал переполнения после задержки на элементе 13 (фиг. 3 О), поступая на единичный вход триггера 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)4 (1) + ср (1), На выходе 10.1 уст ройства появляется код пятого члена(1) пеРвого ряда. Содержимое регистра 2.4 заносится в регистр 3.2.В последующих тактах работа устройства аналогична описанному.25 Информация на выходах устройстваприведена в таблице.В восьмом такте счетчик 12 блока 6управления переполняется (фиг, 3 с ),а сигнал переполнения через элемент13 задержки (фиг. 3 д) поступает насчетный вход вычитающего счетчика 15,который заранее запрограммирован навырабатывание устройством определенного количества членов, кратных 351 2 р (1 =- 1, 2,), Если, например,1 = 2, то в восьмом такте сигнал переполнения вычитающего счетчика 15через открытый элемент И 16 поступает на единичный вход триггера 17 и 4 О устанавливает его в состояние 1(фиг. 3 Ъ, 1,). Сигнал "1" триггера17 разрешает прохождение тактовыхсигналов задающего генератора 11 через элемент И 18 на счетный входсчетчика 19, коэффициент переполнения которого равен числу р (в описываемом примере р = 2). Сигнал "1"триггера 1 также блокирует регистры3,1, 3.2 и 4.1, 4.2, устанавливаяих в состояние "0", В течение следующих двух тактов (в общем случае ртактов) после восьмого обратные связи с выходов регистров 2.4 и 2.3оказываются блокированными сигналом"1" с триггера 17, Одновременносигналом переполнения вычитающегосчетчика 15 триггер 14 по счетномувходу устанавливается в исходное состояние 0 и сигналом 0 с его пря 1345181мого выхода (выхода 3 блока 6 управления) блокируется третий вход коммутатора 5, и устройство готово для приема следующих ( р + 2)-х групп начальных условий.В последующие три ( р + 1) такта после восьмого из устройства считываются старшие члены последующих рядов из первбй группы,Формула изобретенияГенератор последовательности обобщенных чисел Фибоначчи с произвольными начальными условиямир содержа 15 щий блок управления и блок промежуточных вычислений, содержащий сумматоры и (р + 1) регистров, причем выход первого регистра блока подключен к первому выходу генератора, выходы а-х регистров блока промежуточных вычислений, начиная с второго, подключены к входу (ш + 1)-го регистра, выход (р + 1)-го регистра блока промежуточных вычислений подключен к 25 первому входу сумматора, второй вход которого подключен к выходу первого регистра блока промежуточных вычислений, первый выход блока .управления подключен к управляющим входам (р + 1) Во регистров блока промежуточных вычислений, о т л и ч а ю щ и й с я тем, что, с целью повьппения быстродействия в него введены (2 р - 1) блоков предварительных вычислений и коммутатор,35 а блок управления содержит задающий генератор, два счетчика, вычитающий счетчик, два триггера, два элемента И и элемент задержки, причем первый информационный вход коммутатора подключен к информационному входу генератора, вход запуска которого под 4ключен к входу задающего генератора, вхоц начальной установки которого подключен к входу данных вычитающего45 счетчика, выход сумматора 1-го12 р - 1) блока промежуточных вычислений подключен к входу первого регистра ( + 1)-го блока промежуточных вычислений выход сумматоУ 50 ра 2 р-го блока промежуточных вычислений подключен к второму информационному входу коммутатора, первый ивторой управляющие входы которогоподключены соответственно к прямомуи инверсному выходам первого триггера, выход задающего генератора подключен к первому выходу блока управ-,ления и к управляющим входам всехрегистров (2 р - 1) блоков промежуточных вычислений, выход коммутатораподключен к входу первого регистрапервого блока промежуточных вычислений, выходы первых регистров блоковпромежуточных вычислений с второгопо 2 р-й подключены к соответствующимвыходам генератора прямой выход второго триггера подключен к входам"броса всех регистров, начиная с второго каждого г-го (г = 1,р) блока промежуточных вычислений, выходыпервых регистров г-х блоков промежуточных вычислений подключены к входам вторых регистров (г + р) - х блоков промежуточных вычислений, выходыпервых регистров которых подключенык входам вторых регистров г-х блоков,причем выход задающего генератораподключен к счетному входу первогосчетчика и первому входу первого элемента И, второй вход которого подключен к выходу второго триггера, входустановки которого подключен к выходу второго элемента И, первый входкоторого подключен к прямому выходупервого триггера, счетный вход которого и второй вход второго элемента Иподключены к выходу переполнения вычитающего счетчика, установочный входкоторого, входы сброса первого и второго триггеров первого и второгосчетчиков подключены к входу задающего генератора, выход переполненийпервого счетчика через элемент задержки подключен к установочному входу первого триггера и счетному входувычитающего счетчика, выход первогоэлемента И подключен к счетному входу второго счетчика, выход переполнений которого подключен к счетномувходу второго триггера.1345181Составитель С.Курош Редактор М,Келемеш Техред М,Дидык Корректор СЧерни Заказ 4920/47 Тираж 670 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д, 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Смотреть

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