Генератор последовательности @ -чисел фибоначчи
ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ Iр-ЧИСЕЛ ФИБОНАЧЧИ по апт.сп. СССР № 1091146, о т л и ч а ю щ и и с я тем, что, с целью расширения класса решаем1,1х задач путем обеспечег{ия возможности генерирования последовательностей значении мощности оптимального и модифицированного р-кодов , введены регистр началыгых условий , информационный вход которого подключен к входу начальных условий генератора, выход регистра начальных УСЛОВИЙ подк.чючен к соответствуюuteNty входу второго сумматора, а синхронизирующий вход регистра начальных условий - к четвертому выходу блока синхронизации.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИК (19) (11) (51) С 06 F 1/02
ОПИСАНИЕ ИЗОБРЕТЕНИЯ / "
К ABTOPCHOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (61) 1091146 (21) 3569035/18 — 24
C22) 29.03.83 (46) 07.09.84. Бюл. И 33 (72) А.Г.Андрущенко, В.И.Ключко, В.И.Глушков и A.В.Ткаченко (53) 681.3(088.8) (56) I. Авторское свидетельство СССР
II - 1091146, кл. С 06 F 1/02, 24.01.83 (прототип). (543 (57) ГЕНЕ РАТОР ПОСЛЕДОВАТЕЛЬНОСТИ . P-ЧИСЕЛ ФИБОНАЧЧИ по авт. с«. СССР
) 1091146, отличающийся тем, что, с целью расширения класса решаемых задач путем обеспечения воэможности генерирования последовательностей значений мощности оптимальнос го и модифицированного р -кодов, введены регистр начальных усло. вий, информационный «ход которого подключен к входу начапьных условий генератора, выход регистра начальных условий подключен к соответствующему входу второго сумматора, а синхронизирующий вход регистра начальных условий — к четвертому выходу блока синхронизации.
1112356
Изобретение относится к автомати- ке и вычислительной технике и предназначено для генерирования последовательностей значений мощностей с произвольными начальными условиями фибоначчиевого, оптимального фибоначчиевого, оптимального, максимального и модифицированного Р -кодов, что может быть использовано при моделировании данных кодов и для анализа фибоначчиевого, оптимального фибоначчиевого и оптимального Р -кодов, задаваеи. х в виде позиционных кодов.
По основному авт.св. Ф 1091146 известен генератор последовательности р -чисел Фибоначчи, содержащий
2)+I последовательно соединенных регистров, два сумматора, элемент
ИЛИ и блок синхронизации, причем вход начальных условий генератора 20 последовательности Р -чисел Фибоначчи, а также выходы первого и второго сумматоров через элемент ИЛИ подключены к информационному входу первого регистра, выход которого 25 является выходом генератора последовательности Р -чисел Фибоначчи и подключен к первому информационному входу первого сумматора, выход(Р +1)го регистра подключен к второму информационному входу первого сумматора, выходы регистров с (p +1)-го по (2р+1) -й подключен к соответствующим информационным входам второго сумматора, первый выход блока синхронизации подключен к синхрони35 зирующим входам всех регистров, второй и третий выходы блока синхронизации подключены к синхронизирующим входам первого и второго сумматоров. соответственно (1, 7, 40
Известный генератор формирует последовательности р -чисел Фибоначчи, а также последовательности значений мощности оптимального фибоначчиевого и минимального Р -ко45 дов, однако не позволяет получить последовательности значений мощности оптимального и модифицированного
Р-кодов.
Цель изобретения — расширение класса решаемых задач путем обеспечения возможности генерирования последовательностей значений мощности оптимапьного и модифицированного р --кодов.
Поставленная цель достигается тем, что генератор последовательности Р -чисел Фибоначчи содержит! регистр начальных условий, информационный вход которого подключен к входу начальных условий генератора последовательностей Р -чисел Сибоначчи, выход регистра начальных условий подключен к соответствующему входу второго сумматора, а синхронизирующий вход регистра начальных условий — к четвертому выходу блока синхронизации.
На чертеже представлена функциональная схема генератора последовательности Р -чисел Фибоначчи.
Генератор содержит регистры
1.1 — I(2P+Ij элемент ИЛИ 2, сумматор 3, блок 4 синхронизации, сумматор 5, регистр 6 начальных условий. Значения мощности с произвольными начальными условиями фибоначчиевого р -кода разрядностью ll определяются рекуррентным соотношением
0 при псО;
pj(n ) - 11О при п=О; (1)
Щр(n-1)+QI,(n-ð-l) при п)0, где No — произвольное начальное успо. вие;
Р— заданное натуральное число, задающее номер фибоначчиевой двоичной Р -системы счисления.
О при n(0; (q (n) N при Осп61; р+1 (n-p-j) при п р
P (2) Значения мощности с произвольными начальными условиями оптимального
Р-кода определяются рекуррентным соотношением
Значения мощности с произволь,ными начальными условиями одновременно являются весами двоичных разрядов чисел в фибоначчиевой двоичной ю
Р --системе счисления. При этом число р является обобщенным числом Фибоначчи с произвольными начальными условиями.
Значения мощности с произвольными начальными условиями оптимального фибоначчиевого р -кода определяется рекуррентным соотношением
l l 12 356
О при паО; ф (п) = р+1
Р (3) ф (и-р-j)+N при и > О. р О
Предлагаемый генератор обеспечивает моделирование последовательности значений мощности с произвольными начальными условиями фибоначчиевого p †ко в первом режиме рабо- 1О
"гы, последовательности значений мощности с произвольными начальными условиями оптимального фибоначчиеного р -кода во втором режиме работы и последовательности значений мощности с произвольными начальными условиями оптимального р --кода в третьем режиме работы.
В моделировании последовательности значений мощности с произвольными начальными условиями фибоначчиевого Р -кода участвуют регистры
1. 1 — 1.(p+ I), элемент ИЛИ 2, сумматор 3 и блок 4 синхронизации. Информационный вход генератора служит для подачи кодовой комбинации начального условия через элемент
ИЛИ в регистр I. 1 в нулевом такте работы генератора. В регистрах !. I—
1(р+ I ) хранятся предыдущие (р+1 )
30 значений мощности с произвольными начальными условиями фибоначчиевого Р -кода. Формирование каждого последующего значения мощности с произвольными начальными услониями Обес-M печивается сумматором 3 согласно соотношению (I). Блок 4 синхронизации формирует синхроимпульсы, управляющие перезаписью содержимого каждого предыдущего регистра в каждый после- 40 дующий регистр, управляющие сложением в сумматоре 3 содержимого регистров I. I и 1.(p+I) . Элемент ИЛИ 2 предназначен для объединения выходов сумматоров 3 и 5.
В моделировании последовательности значений мощности с произвольными начальными условиями оптимального фибоначчиевого р -кода принимают учас. тие все структурные элементы схемы за исключением регистра б. В регистрах 1.1-1..(2р+1) хранятся значения мощности с произвольными начальными условиями оптимального р -кода
Фибоначчи для предыдущих (2 +I) величин разрядностей этого кода. Моделирование последующих значений мощности обеспечивается с помощью сумматоров 3 и 5 согласно Выражению (2).
Сумматор 3 формирует р первых значений мощности, а суммауор 5 — все последующие значения. Блок 4 упранляет работой сумматоров 3 и 5 таким образом, что в течение р тактов работы генератора, начиная с первого, синхроимпульсы поступают на сумматор 3, а во всех последующих тактах на сумматор 5.
B моделировании последовательности значений мощности с произвольными начальными условиями оптимального р-кода участвуют все структурные элементы схемы за исключением r óMMëтора 3. Регистр 6 служит для хранения и выдачи (П+1) раз кодовой комбинации начального условия и может быть выполнен как регистр с обратными связями. В регистрах . .1-1. (2p+ I) хранятся предыдущие (2р+1) значений мощности, а последующие значения реализуются на сумматоре 5 соглас но соотношению (3). Блок 4 формирует синхроимнульсы для регистров 1 и 6 и сумматора 5.
Кроме указанных последовательнос,тей, предлагаемый генератор позволяет также моделировать последовательности мощностей с произвольными начальными условиями модифицированного и минимального Р -кодов. г дВОичнОЙ мОдифицированнОй ) сис теме счисления для заданного целого р> О и любого натурального D при не котором целом п1 > О сущестнует предстal" ение D В виде и-1 О и р() где d„=1, Й 6(0,1) илн вrex
О Значения мощности с произвольными начальными условиями Р (n) эаP дают cR ре куррент ным соотношением (3) и формируются в третьем режиме работы генератора на г1 -м такте и генерируются на (и+1! -м такте. В двоичной минимальной Р -системе счисления для заданного целого р> О и любых натуральных С и Q существует представление в виде 1р (Б) где С„ 1, С с(0, 1) для всех I 6 S (n. Значение мощности с произвольными начальными условиями равно (р (n+I), где Qp (5 ) определяется рекуррент12356 Составитель В. Байков Техред А. Кикемеэей Корректор В. Синицкая Редактор Е.Папп Заказ 6459/33 Тираж 698 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий I1,3035, Москва, Ж-35, Раушская наб., д. 4/5 Филиал ППП "Патент", r.Óçòîðîä, ул.Проектная,4 S ll ным соотношением (2), формируется во втором режиме работы генератора на (И+1) "м такте н генерируется на (n+2)-ì такте. Таким образом, наряду с последовательностями генерируемыми известным генератором, предпагаемый генератор позволяет также получать последовательности значений мошлости оптимального и модифицированного р-ко5 дов, что расширяет его функциональные возможности.
