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

)4 С 06 Р 1 ПИСАНИЕ ИЗОБРЕТЕНИ селво 27 льство СССР 1/02, 1974, ство СССР 1/02, 1985. ВАТЕЛЬНОСТИ ится к автомаехнике и свяявляется расения за счет ОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(57) Изобретение отнотике, вычислительнойзи. Целью изобретенияширение области приме возможности представления чи птимальном р-коде Фибоначчи. В генератор последовательности р-чисел Фибоначчи, содержащий регистры 11-12сумматор 3, регистр 4 начального условия н блок 6 элементов ИЛИ, введеныблоки 7, 7 элементов ИЛИ, элементИ 8, блок 10 элементов И, суммирующийсчетчик 12, группа блоков 13 1-13 +,элементов И, блоки 1414 элементовзапрета, дешифратор 15, шифратор 16унитарного кода в оптимальный Г-код,блок 17 элементов, ИСКЛЮЧАЮЩЕЕ ИЛИ иэлемент ИЛИ 20 с соответствующимисвязями. 2 ил.Получать изображения оптимального р-кода фибоначчи удобно посредством изображений оптимальной С-системы счисления (С р), для которых характерно наличие после каждой единицы не менее С и не более 2 С нулей,55 Изобретение относится к автомати: ке, вычислительной технике и связи.Цель .изобретения - расширение области применения за счет возможностипредставления чисел в оптимальном р 5коде Фибоначчи,На фиг. 1.представлена схема генератора последовательности р-чисел Фибоначчи; на фиг. 2 - схема шифратораунитарного кода в оптимальнь 5 й Г-код1(для и=8, Г=1).1Генератор содержит регистры 1, -5.1 , первый тактовый вход 2 генератора, сумматор 3, регистр 4 начального условия, вход 5 запуска генератора, блок 6 элементов ИЛИ, блоки 7, и, 7 элементов ИЛИ, элемент И 8, второйтактовый вход 9 генератора, блок 10элементов И, третий тактовый вход 11генератора, суммирующий счетчик 12,1 группу блоков 13, -13 +1 элементов И,блоки 14 и 14 элементов запрета,1 дешифратор 15, шифратор 16 унитарно: :го кода в оптимальный Г-код, блок 17 25элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход 18числа генератора, первый установоч, ный вход 19 генератора,. элемент ИЛИ20, выход 21 номера числа генератора,, второй установочный вход 22 генера:, тора,Шифратор 16 унитарного кода в оп тимальный 1-код (фиг, 2) содержитформирователь 23 логического нуля игруппу элементов ИЛИ 24-24 , выходыкоторых являются выходами шйфратора16, соответствующий вход (Б)-гоэлемента ИЛИ соединен с входом С шифратора 16 при Ф(Б- )О Ск40Для всех изображений оптимальногор-кода Фибоначчи характерно наличие после каждой единицы не менеер и не более 2 р нулей и, кроме того,не более р нулей в старших разрядахдо первой единицы. Такое представление определяет основную отличительнуюособенность оптимального р-кода Фибоначчи: число В может быть представлено в оптимальном р-коде Фибоначчиразличными комбинациями для различныхдлин и кода, Число В, представляемое в оптимальном р-коде Фибоначчи, и число С, представляемое в оптимальном С-коде, связаны зависимостью С(и)=В(и)+ ф (и-р),В двоичной оптимальной С-системесчисления для заданного целого С , Ои любого натурального С существуетпредставление С в виде: С=С, У (Б),С,при Ф(Б 1) С сф (Б)С 5 гО при ф (Б)С З Ф(Б); О1( се 1 -Значения фи) определяют мощность и-разрядного оптимального р-кода Фибоначчи, а значения ф(и) - мощность и-разрядного оптимального С-кода,Вес оптимального С-кода, определяющий количество двоичных единиц в множестве ф(и), равен". епри получении блока оптимального р-кода Фибоначчи последовательно фориируатся значения В=О, Гп 5-1, при необходимости получать отдельные кодовые комбинации оптимального р-кода Фибоначчи, соответствующие значения В заносятся в генератор избирательно,находится значение С согласно выражению (1;( ) Опри и 0, 1ы (и-С-,+Ф (и)- 1 при и ЪО.Сущность изобретения заключаетая в реализации следующего алгоритма:задается значение разрядности кода и;формируется значение ф(и-р) согласно рекуррентному соотношению. Генератор работает в двух режимах,В первом режиме на входе 19 устананливается код числа(и)-1 и фор 5 мируется весь блок оптимального р-кода Фибоначчи. Во втором режиме, когда формируются кодовые комбинации оп-с тимального р-кода Фибоначчи избира 1 О тельно, на входы 19 и 22 подаются соответствующие номера кодовых комбинаций.В исходном состоянии все регистры и счетчик обнулены. В первом режиме работы на входе 19 устанавливается число ц (п)-1, Работа начинается с подачи на вход 5 числа "1" в первом такте работы, Далее значения выражения (3) формируются в регистре 1 в каждом такте работы путем сложения содержимого регистров 1 Р+, у+, 4 на сумматоре 3 и перезаписи содержимого регистров 1-1 1. Через и-рРтактов на входе 2 генератора устанав ливается нулевой потенциал. В регист- . ре 1 фиксируется значение фР(п-р), Одновременно нулевой потенциал с входа 2 генератора переключает входы сумматора 3 к выходам регистра 1 и счетчика 12, на вход 11 генератора подаются импульсы. В это время на выходе сумматора 3 образуется число ф(п-р)+О, которое в виде кода оптимальной формы поступает через генератор 15 и шифратор 16, на выход 18,35 что соответствует числу "О" (установленному на выходе 21) в оптимальном р-коде Фибоначчи.В каждом последующем такте происходит сложение на сумматоре 3 числа фР(п-р) с числом в счетчике 12, Последним значением суммы является Ф(п-р - 1)+l(п) - 1; после чего на выходе блока 17 элементов ИСКЛОЧАЮЩЕЕ 45 ИЛИ образуется нулевой потенциал, который через элемент ИЛИ 20 запрещает прохождение тактовых импульсов через элемент И 8 на счетный вход счетчика 12, Таким образом, на выходе 18 получают все комбинации оптимального р-кода Фибоначчи разрядности п.При необходимости кодирования одного или нескольких конкретных значений В последние поочередно подаются одновременно на входы 19 и 22. На выходе 18 образуется оптимальная форма суммы В+фР(п-р), что соответствует числу В в оптимальном р-коде Фибоначчи,Формула изобретенияГенератор последовательности р-чисел Фибоначчи, содержащий (2 р+1) регистрон, сумматор, регистр начального услония и первый блок элементов ИЛИ, причем вход запуска генератора соединен с входом регистра начального условия и с первым входом первого блока элементов ИЛИ, выход которого соединен с информационным входом первого регистра, выход предыдущего регистра соединен с информационным входом последующего регистра, первый тактовый вход генератора соединен с входами разрешения приема регистров, второй тактовый вход генератора соединен с входом разрешения сумматора, выход сумматора соединен с вторым входом первого блока элементов ИЛИ, о т л и ч а ю щ и й с я тем, что, с целью расширения области применения за счет воэможности представления, чисел в оптимальном р-коде фибоначчи, он содержит элемент И, группу из р+1 блоков элементов И,.второй и третий блоки элементов ИЛИ, суммирующий счетчик, два блока элементов запрета, дешифратор, шифратор унитарного кода в оптимальный Г-код, блок элементов ИСКЛН)ЧАЮЩЕЕ ИЛИ, элемент ИЛИ и блок элементов И, причем первый тактовый вход генератора соединен с первыми входами блоков элементов И группы, блока элементов И и с управляющими входами первого и второго блоков элементов запрета, выходы которых соединены с первыми нходами соответственно второго и третьего блоков элементов ИЛИ, вторые входы которых соединены с выходами первого и второго блоков элементов И группы соответстненно, выход блока элементов И, выходы второго и третьего блоков элементов ИЛИ и выходы блоков элементов И с третьего по (р+1)-й группы соединены соответственно с входами слагаемых сумматора, выход которого соединен с входом дешифратора, выход которого соединен с входом шифратора. унитарного кода в оптимальный -код, выход которого является выходом числа генератора, первый установочный вход которого соединен с первым входом1411725 6тора и с выходом элемента.ИЛИ, входы которого соединены соответственно с выходами разрядов блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход первого регистра соединен с информационным входом первого блока элементов запрета, выходы регистров с (р+1)-го по (2 р+1)-й соединены с вторыми входами блоков элементов И с (р+1)-го по первый группы соответственно, второй вход блока элементов И соединен с выходом регистра начального условия. ель А.Клюев.Олийнык Тираз 704Государственного к ам изобретений и ква, Ж, Раушск Подпис митета С ткрытий я наб аказ 365 Н по дел13035, Мос 4/5 ктная, 4 Ужгород, у графическое предпрняти эводственно 5бароха элементов ИСКЛЮЧАМ 61 ЕЕ ИЛИ, вто-рой вход которых соединен с выходом суммирувз 1 его счетчика, с информационным входом второго блока элементов5 запрета и является выходом номера чИсла генератора, второй установочвход которого соединен с установ чиым входом суммирующего счетчика, фетный вход которого соединен с выхЬдом эленента И, первый и второй вхокоторого соединены соответственс третьим тактовым входом генераСоставиРедактор В.петраш Техред орректор М,Васильева