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

 

ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ Р-ЧИСЕЛ ФИБОНАЧЧИ, содержащий р+1 последовательно соединенных регистров с первого по (p-f 1)-й, первый сумматор и блок синхронизации, причем первый информационный вход первого регистра является входом начальных условий генератора , а выход первого регистра является выходом генератора и подключен к первому информационному входу первого сумматора , второй информационный вход которого подключен к выходу (p-fl)-ro регистра , первый и второй выходы блока синхронизации подключены к синхронизирующим входам регистров и первого сумматора соответственно, отличающийся тем, что, с целью расширения класса решаемых задач за счет возможности генерирования последовательностей значений мощности, оптимального «фибоначчиевого и минимального кодов, он содержит донолнительно р последовательно соединенных регистров с (р + 2)го по

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

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

РЕСПУБЛИК з ц G 06 F 1/02

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

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

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3542198/18-24 (22) 24.01.83 (46) 07.05.84. Бюл. № 17 (72) В И. Ключко, А. В. Ткаченко, С. В. Шпа гин, А. В. Руксов и А. Н. Нефедов (53) 681. 3 (088.8) (56) 1. Авторское свидетельство СССР № 824200, кл. G 06 F 7/49, 1979.

2, Авторское свидетельство СССР № 662926, кл. G 06 F1/02, 1976 (прототип). (54) (57) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ P-ЧИСЕЛ ФИБОНАЧЧИ, содержащий р+1 последовательно соединенных регистров с первого по (р+1)-й, первый сумматор и блок синхронизации, причем первый информационный вход первого регистра является входом начальных условий генератора, а выход первого регистра является выходом генератора и подключен к первому информационному входу первого сумматора, второй информационный вход ко„.SU„„1091146 А торого подключен к выходу (р+1)-го регистра, первый и второй выходы блока синхронизации подключены к синхронизирующим входам регистров и первого сумматоры соответственно, отличающийся тем, что, с целью расширения класса решаемых задач за счет возможности генерирования последовательностей значений мощности, оптимального «фибоначчиевого» и минимального кодов, он содержит дополнительно р последовательно соединенных регистров с (р+2)ro по (2р+1)-й, второй сумматор и элемент ИЛИ, причем выход (р+1) -го регистра подключен к информационному входу (р+2) -го регистра, выходы регистров с (р+1)-го по (2р+1) -й подключены к информационным входам второго сумматора, выходы первого и второго сумматоров через элемент ИЛИ подключены к второму информационному входу первого регистра, третий выход блока синхронизации подключен к синхронизирующему входу второго сумматора.

1091146

50

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

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

Данный генератор позволяет, в частности, получать последовательность чисел Фибоначчи, но не обеспечивает получения последовательности значений Molll,ности оптимального «фибоначчиевого» р-кода.

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

Фибоначчи (2).

Недостатком известного генератора является невозможность получения последовательности значений мощности оптимального «фибоначчиевого» и минимального кодов.

Цель изобретения — расширение класса решаемых задач генератора последовательности р-чисел Фибоначчи за счет возможности генерирования последовательностей значений мощности оптимального «фибоначчиевого» и минимального кодов.

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

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

На чертеже представлена функциональная схема генератора последовательности р-чисел Фибоначчи.

Генератор содержит регистры 1,—

1(RP+ 1), элемент ИЛИ 2, сумматор 3, блок 4 с и их рон из а ци и, сум м атор 5. р-числа Фибоначчи го (п) с произвольными начальными условиями при заданном целом р>0 определяются рекуррентным соотношением

Опри и< р р(п) = N>при,= 0 (1) р (и- 1) + л р(п- р-1) n pv n > p где М, -произвольное начальное условие; — разрядность р-кода Фибоначчи.

При Np — — 1 р-числа Фибоначчи <р (и) определяют мощность «фибоначчиевого» р-кода. Мощность оптимального «фибоначчи евого» р-кода определяется рекуррентным соотношением

Опри п<0 (, (и) 1при O(Ксp р

1 р(п р-,))при п>р (2)

Генератор обеспечивает формирование последовательности р-чисел Фибоначчи с произвольными начальными условиями в первом режиме работы и последовательности значений мощности оптимального «фибоначчиевого» р-кода во втором режиме работы.

В исходном состоянии во всех регистрах записаны нулевые коды.

При формировании последовательности р-чисел Фибоначчи с произвольными начальными условиями принимают участие регистры 1 — 11p 0, элемент ИЛИ 2, сумматор 3 и блок 4 синхронизации. Информационный вход генератора служит для подачи кодовой комбинации начального условия в регистр 1>.

В регистрах 1» — 1 р+ 1 хранятся предыдущие р+1 р-числа Фибоначчи.

Формирование каждого последующего р-числа Фибоначчи осуществляется с помощью сумматора 3 согласно соотношению (1). Блок 4 синхронизации формирует синхроимпульсы, управляющие перезаписью содержимого каждого предыдущего регистра в каждый последующий регистр и сложением в сумматоре 3 содержимых регистра 1 и регистра 1п<1, Г1ри моделировании последовательности значений мощности оптимального «фибоначчиевого» р-кода участвуют все структурные элементы схемы. При этом информаци он ны и вход генератора служит для подачи кода единицы в регистр 1,. В регистрах 1 — 1(pyg) хранятся значения мощ1091146

Составитель В. Байков

Техред И. Верее Корректор Г. Решетник

Тираж 699 Подписное

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

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

Филиал ППП «Патент», r. Ужгород, ул. Проектная, 4

Редактор В. Петраш

Заказ 2826/44 ности оптимального р-кода Фибоначчи для предыдущих 2р+1 величин разрядности этого кода. Согласно соотношению (2) сумматор 3 формирует р-первых значений мощности оптимального «фибоначчиевого» ркода, а сумматор 5 — все последующие зна5 чения мощности кода. Блок 4 управляет работой сумматоров 3 и 5 таким образом, что в течение р тактов работы генератора, начиная со второго, синхроимпульсы поступают на синхронизирующий вход сумматора 3, а во всех последующих тактах синхроимпульсы подаются на сумматор 5. Элемент ИЛИ 2 предназначен для объединения выходов сумматоров 3 и 5.

Предлагаемый генератор позволяет также моделировать последовательные значения мощности с произвольными начальными условиями минимального р-кода. Это следует из того, что в двоичной минимальной р-системе счисления (р>0) для любых натуральных С и S существует представление С в виде с= к"= с,р,(s), гд.е С„,=1, C5<$0,1,3 длЯ всех 1(< П.

Таким образом, предлагаемый генератор обладает более высокой технико-экономической эффективностью по сравнению с известным за счет дополнительного моделирования последовательности значений мощности оптимального «фибоначчиевого» и минимального р-кодов, использование которых значительно повышает достоверность контроля устройств хранения информации.