Генератор последовательности -чисел фибоначчи

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК за) б 06 Р 1/02 ОПИСАНИЕ ИЗОБРЕТК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) 1. Авторское свидетельство СССР824200, кл. б 06 Г 7/49, 1979.2, Авторское свидетельство СССР662926, кл. б 06 Г 1/02, 1976 (прототип). (54) (57) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ Р-ЧИСЕЛ ФИБОНАЧЧИ, содержащий р+1 последовательно соединенных регистров с первого по (р+1)-й, первый сумматор и блок синхронизации, причем первый информационный вход первого регистра является входом начальных условий генератора, а выход первого регистра является выходом генератора и подключен к первому информационному входу первого сумматора, второй информационный вход ко,ЯО 1091146 А торого подключен к выходу (р+1)-го регистра, первый и второй выходы блока синхронизации подключены к синхронизирующим входам регистров и первого сумматора соответственно, отличающийся тем, что, с целью расширения класса решаемых задач за счет возможности генерирования последовательностей значений мощности, оптимального фибоначчиевого и минимального кодов, он содержит дополнительно р последовательно соединенных регистров с (р+2)- го по (2 р+1) -й, второй сумматор и элемент ИЛИ, причем выход (р+1) -го регистра подключен к информационному входу (р+2) -го регистра, выходы регистров с (р+1)-го по (2 р+1)-й подключены к информационным входам второго сумматора, выходы первого и второго сумматоров че рез элемент ИЛИ подключены к второму информационному входу первого регистра, третий выход блока синхронизации подключен к синхронизирующему входу второго сумматора.Изобретение относится к автоматике ивычислительной технике и предназначенодля генерирования последовательности рчисел Фибоначчи с произвольными начальными условиями и последовательности значений мощности оптимального фибоначчиевого р-кода, что может быть использованодля анализа р-кодов Фибоначчи и оптимальных р-кодов Фибоначчи.Известен генератор последовательностейобобщенных чисел, содержащий регистры, 1 Осумматор, блоки контроля и нормализации 1Данный генератор позволяет, в частности,полу чать последовательность чисел Фибоначчи, но не обеспечивает получения последовательности значений мощности оптимального фибоначчиевого р-кода.Наиболее близким по технической сущности к предлагаемому является генераторпоследовательности р-чисел Фибоначчи,содержащий р+1 последовательно соединенных регистров, сумматор и блок синхронизации, выходы первого и (р+1) -го регистров подключены к входам сумматора,выход сумматора подключен к входу первого регистра, на выходе первого регистраформируется последовательность р-чиселФибоначчи 2,Недостатком известного генератора является невозможность получения последовательности значений мощности оптимального фибоначчиевого и минимального З 0кодов.Цель изобретения - расширение классарешаемых задач генератора последовательности р-чисел Фибоначчи за счет возможности генерирования последовательностейзначений моцности оптимального фибоначчиевого и минимального кодов.Поставленная цель достигается тем, чтогенератор последовательности р-чисел Фибоначчи, содержащий р+1 последовательно соединенных регистров с первого по 40(р+1) -й, первый сумматор и блок синхронизации, причем первый информационный вход первого регистра является входом начальных условий генератора, а выход первого регистра является выходомгенератора и подключен к первому информационному входу первого сумматора, второй информационный вход которого подключен к выходу (р+1)-го регистра, первый и второй выходы блока синхронизацииподключены к синхронизирующим входамрегистров и первого сумматора соответ 50ственно, содержит дополнительно р последовательно соеди ненных регистров с(р+2) -го по (2 р+1) -й, второй сумматори элемент ИЛИ, причем выход (р+1) -горегистра подключен к информационному 55входу (р+2) -го регистра, выходы регистров с р+1)-го по (2 р+1)-й подключенык информационным входам второго сумматора, выходы первого и второго суммато. ров через элемент ИЛИ подключены к второму информационному входу первого регистра, третий выход блока синхронизации подключен к синхронизирующему входу второго сумматора.На чертеже представлена функциональная схема генератора последовательности р-чисел Фибоначчи.Генератор содержит регистры 1, - ЯР+ 1), элемент ИЛИ 2, сумматор 3, блок 4 синхронизации, сумматор 5,р-числа Фибоначчи го (п) с произвольными начальными условиями при заданном целом р)0 определяются рекуррентным соотношениемОпри п О Ур(п) = Иопря= 0 (1)Рр(п- )+ р(п-р) при п)0, где М, -произвольное начальное условие;11 - разрядность р-кода Фибоначчи.При Мо -- 1 р-числа Фибоначчи Рр (и) определяют мощность фибоначчиевого р-кода, Мощность оптимального фибоначчи евого р-кода определяется рекуррентным соотношениемОпри п 0 ,у, (и)дРи о( 1(рр(п-Р,при н)р (2)Генератор обеспечивает формирование последовательности р.чисел Фибоначчи с произвольными начальными условиями в первом режиме работы и последовательности значений мощности оптимального фибоначчиевого р-кода во втором режиме работы.В исходном состоянии во всех регистрах записаны нулевые коды,При формировании последовательности р-чисел Фибоначчи с произвольными начальными условиями принимают участие регистры 1, - 1(р 11, элемент ИЛИ 2, сумматор 3 и блок 4 синхронизации, Информационный вход генератора служит для подачи кодовой комбинации начального условия в регистр 1,. В регистрах 1 - 1 рн 1 хранятся предыдущие р+1 р-числа Фибоначчи.Формирование каждого последующего р-числа Фибоначчи осуществляется с помощью сумматора 3 согласно соотношению (1). Блок 4 синхронизации формирует синхроимпульсы, управляющие перезаписью содержимого каждого предыдущего регистра в каждый последующий регистр и сложением в сумматоре 3 содержимых регистра 1 и регистра 1(р.1),Г 1 ри моделировании последовательности значений мощности оптимального фибоначчиевого р-кода участвуют все структурные элементы схемы. При этом информаци он ны й вход генератора служит для подачи кода единицы в регистр 1,. В регистрах 1 - 11 р) хранятся значения мощ1091146 Составитель В, Байков Техред И. Верее Корректор Г. Решетник Тираж 699 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж - 35, Раушская наб., д. 4/5 филиал ППП Патент, г. Ужгород, ул. Проектная, 4Редактор В. ПетрашЗаказ 2826/44 ности оптимального р-кода фибоначчи для предыдущих 2 р+1 величин разрядности этого кода. Согласно соотношению (2) сумматор 3 формирует р-первых значений мощности оптимального фибоначчиевого ркода, а сумматор 5 - все последующие зна 5 чения мощности кода, Блок 4 управляет работой сумматоров 3 и 5 таким образом, что в течение р тактов работы генератора, начиная со второго, синхроимпульсы поступают на синхронизирующий вход суммато ра 3, а во всех последующих тактах синхроимпульсы подаются на сумматор 5. Элемент ИЛИ 2 предназначен для объединения выходов сумматоров 3 и 5.Предлагаемый генератор позволяет также моделировать последовательные значения мощности с произвольными начальными условиями минимального р-кода. Это следует из того, что в двоичной минимальной р-системе счисления (рзО) для любых натуральных С и 5 существует представление С в видеС 1 й),где С=1, С 5 Е 0,1 длЯ всех 143 ПТаким образом, предлагаемый генератор обладает более высокой технико-экономической эффективностью по сравнению с известным за счет дополнительного моделирования последовательности значений мощности оптимального фибоначчиевого и минимального р-кодов, использование которых значительно повышает достоверность контроля устройств хранения информации.