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

Номер патента: 1273909

Авторы: Ключко, Ткаченко, Фрункер

ZIP архив

Текст

)4 С 06 Р 1/О ЕНИЯ ЕЛЬСТВ о СССР1976.СССР1211.СССР1985. Е 1 ОС к обл ои тех ерироГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ИСАНИЕ ИЭОБ К АВТОРСКОМУ СВИ(57) Изобретение относитсяти автоматики и вычислительники и предназначено для г 8012739 ания последовательностей значен мощностеи с произвольными начальными условиями "фибоначчиевого" оптимального, минимального и модифицированного р-кодов, а также массы оптимального р-кода, задаваемых в виде позиционных кодов. Цель изобретения - расширение класса решаемыхзадач за счет воэможности генерирования последовательностей значениймассы оптимального р-кода и мощности оптимального модифицированногор-кодовГенератор содержит регистры первой группы 1,1- 1.(2 р + 1),элемент ИЛИ 2, сумматоры 3 - 5, блок 6синхронизации, регистр 7 начальныхусловий, регистры второй группы8.1-8.(2 р + 1), информационные вход9 и выходы 10 и 11, 1 ил. 4 табл.-р-д) при иО 4) о (и) 55 Изобретение относится к автомати-ке и вычислительной технике и предназначено для генерирования последовательностей значений мощности с произвольными начальными условиями "фибоначчиевого" оптимального, минимального и модифицированного р-кодов, а также массы .оптимального р-кода, задаваемых в виде позиционных кодов,Значение мощности с произвольными начальными условиями "фибоначчиевого" р-кода разрядностью и (р"числа Фибоначчи) определяют рекурентным соотношением: ловие;р - целое неотрицательное число, задающее номер двоичной р-системы счисления.Значения мощности с произвольными начальными условиями оптимального р-кода Фибоначчи разрядностью и и минимального р-кода разрядностью и - 1 определяются рекуррентным соотношением; Значения мощности сначальными условиями омодифицированного р-кодются рекуррентным соот-1 Другой важной характеристикой кода является его масса.Значения массы с произвольными начальными условиями оптимального р-кода, определяющие количество двоичных единиц в множестве кодовых слов мощностью % (и), задаются рекуррентным соотношением: В табл,1 приведены значения функции (4) для и = 5, 10 и р = 1,4 при Х 1 1 0 0 1248 13 2 Цель изобретения - расширение клас са решаемых задач путем генерирования последовательности значения массы оптимального р-кода и мощности оптимального и модифицированного р-кодов.На чертеже показана схема предлагаемого генератора,Устройство содержит регистры пер.вой группы 1.1-1.(2 р + 1), элемент ИЛИ 2, сумматоры 3, 4 и 5, блок 6 синхронизации, регистр 7 начальных условий, регистры второй группы 8.1 - 8.(2 р .+ 1),информационные вход 9 и выходы 10 и 11.Генератор работает следующим образом. В исходном состоянии в регистрах 1,1 - 1,(2 р + 1), 8.1 - 8(2 р + 1) и регистре 6 содержатся нулевые коды. В нулевом такте на информационный вход 9 генератора подается код М начального условия, который поступает на информационный вход регистра 1. 1 через элемент ИЛИ 2 и на информационный вход регистра 7 непосредственно.В режиме моделирования последовательности значений мощности с произвольными начальными условиями "фибоначчиевого" р-кода по сигналу, поступающему с выхода блока 4 на вход синхронизации регистра 1.1 производится запись кода М в регистр 1.1. В первом такте содержимое регистра 1.1 под воздействием сигнала с выхода блока синхронизации поступает на информационный выход генератора 10, на информационный вход регистра 1,2 и на первый информационный вход сумматора 3, на второй информационныйвход которого поступает содержимое регистр1,(р + 1). По сигналу, поступающему в этом же такте с выхода блока909 Примером функционирования данного генератора может служить формирование последовательности значенийфункции (1) при р = 2, И, = 2, по казанное с помощью табл,2,Таблица 2 2 3 4 5 6 7 8 9 10 2 2 4 6 8 12 18 26 38 56 2 2 2 4 6 8 12 18 26 38 0 2 2 . 2 4 6 8 12 18 26 1.2 1.3 На выходе10 2 2 2 4 6 8 12 18 26 38 з 1273 6, происходит сложение поступивших из регистров 1,1 и 1,(р + 1) на сумматор 3 кодовых комбинаций чисел, Одновременно результат сложения за.писывается в регистр 1,1 через элемент ИЛИ 2, Таким образом, в первом такте получено первое значение функции (1), Последующие значения последовательности значений мощности с начальным условием "фибоначчиево О го р-кода формируются повторением операции сложения содержимого реги стров 1,1 и 1,(р + 1) и перезаписи содержимого ъпегистров 1.1 - 1.(р + 1 Э . В первом режиме работы генератора В режиме моделирования последовательности значений мощности с произвольными начальными условиями фи О боначчиевого оптимального р-кода по сигналу, поступающему с выхода блока 6 на управляющий вход регистра 1.1, производится занесение кода И в регистр 1.1. В первол такте по сигналу с выхода блока 6 синхронизации содержимое регистра 1.1 постулат на информационный выход генераора 10, информационный вход региста 1,2 и второй информационный вход сумматора 3, на первый информационный вход которого поступает содержимое 1.(р + 1)-го регистра. Одновременно по сигналу с выхода блока 6 синхронизации,поступающему на управляющий . 5 вход сумматора 3, происходит сложение содержимого регистров 1.1 и 1.(р + 1). В этом же такте результат сложение содержимого регистров1,(р + 1) - 1.(2 р + 1) и регистра 7на сумматоре 4 и содержимого регистров 1.(р + 1) - 1.(2 р + 1),8.(р ++ 1) - 8,(2 р + 1) на сумматоре 5 непроисходит, таМ как на входах синхронизации сумматоров 4 и 5 отсутствуют синхроимпульсы выходов и блока 6 синхронизации. сложения через элемент ИЛИ 2 записывается в регистр 1,1. Таким образом, в первом такте получено первое значение функции (2) и сформировано первое значение из последовательности значений мощности с начальным условием Х , код которого содержится в регистре 1.1.и поступит на выход генератора во втором такте. Последующие (р) значений функции 9 (и) моделируются аналогичным образом путем повторения операций сложения содержимого регистров 1.1 и 1,(р + 1) и перезаписи содержимого регистров 1.1 - 1(р + 1).Начиная с (р + 1)-го такта работы генератора, формирование синхроимпульсов на выходе блока 6 синхронизации прекращается, а сигналы управления начинают поступать с выхода блока 6 на управляющий вход сум6 7 8 9 4 5 10 6 2 2 2 6 8 6 6 выо генератора 2 12 ия последоваости и масальными услода по сигнада,блока 6 яющий входтся занесение а по сигналу, ющий вход ре- синхрониза 5 1273 матора 4, Перед (р + 1)-м тактом в регистрах 1.1 - 1.(р + 1) записан код начального состояния Х , а в регистрах 1.(р + 2) - 1.(2 р + 1) - нулевой код. В (р + 1)-м такте по сигналу с выхода блока 6 из регистра 1.1 происходит выдача на информационный выход генератора 10 р-го значения мощности с начальным условием Моптимального "фибоначчиевого" кода 10 и перезапись содержимого регистров 1.1 - 1,(2 р + 1), Одновременно на информационные входы сумматора 4 поступает содержимое регистров 1.(р + + 1) - 1 е(2 р + 1), По сигналу с Вы хода блока сумматор 4 производит сложение поступающих из регистров 1. (р + 1) - 1. (2 р + 1) кодов чисел. Полу-ченный в результате сложения код суммы с информационного выхода суммато ра 4 через элемент ИЛИ 2 записываВ режиме моделирован тельности значений мощи сы с произвольными нач виями оптимального р-ко лу, поступающему с выхо синхронизации на управл регистра 1.1, производи кода К в регистр 1.1, поступающему на управля гистра с выхода блока 6 909 6ется в регистр 1.1, Таким образом, в (р + 1)-м такте сформирован код (р + 1)-го значения мощности иэ последовательности значений мощности сначальным условием И оптимальногоа"фибоначчиевого" р-кода, который поступает на выход генератора 10 в след ющем (р + 2)-м такте. Последующие значения мощности с начальным условием М оптимального р-кода Фибоначчи моделируются повторением операций сложения содержимого регистров 1.(р + 1) - 1.(2 р + 1) и перезаписи содержимого регистров 1.1 - 1.(2 р + 1). Примером функционирования данного генератора может служить моделирование последовательности функций (2), как показано в табл,3, при р = 2, И = 2,Таблица 3 ции, код начального условия И заносится в регистр 7. В первом тактепо сигналу с выхода блока 6 синхронизации содержимое регистра 1,1 поступает на информационный выход 10генератора и информационный входрегистра 1.2; содержимое регистров1.(р + 1) - 1.(2 р + 1) поступает насоответствующие информационные входы 1 - (р + 1) сумматора 4, на (р+2)-й12 3 4 7 8 9 10 2 2 4 5 8 10 14 20 26 34 2 2 2 4 6 8 10 14 20 26 1,2 информационный вход которого поступает содержимое регистра 7 по сигналу с выхода блока 6 синхронизации,Одновременно по сигналу с выхода блока 6 синхронизации, поступающему науправляющий вход сумматора 4, происходит сложение содержимого регистров1.(р + 1) - 1,(2 р +. 1) и регистра 7,В этом же такте результат сложениячерез элемент ИЛИ 2 записывается врегистр 1.1. Таким образом, в первомтакте получено первое значение функции (3). Последующие значения функцииР (п) моделируются аналогичнымобразом путем повторения операцийсложения содержимого регистров 1,(р++ 1) - 1.(2 р + 1) и регистра 7 иперезаписи содержимого регистров1.1-1.(2 р + 1). В третьем режиме работы сложение содержимого регистров1.1 и 1.(р + 1) не происходит, таккак на управляющем входе сумматора3 отсутствует сигнал с выхода блока 6 синхронизации. Рассмотрим работу схемы в моделировании массы оптимального р-кода с произвольными начальными условиями, Вьппе указано,что содержимое регистров 1,(р + 1) - 1.(2 р + 1) поступает на соответствующие информационные входы 1 - (р + 1) сумматора 4, Параллельно содержимое регистров 1.(р + 1) - 1,(2 р + 1) поступает на соответствующие входы 1 - (р+ .1) сумматора 5, на (р + 2) - (2 р + 2) информационные входы которого поступает содержимое регистров 8.(р + 1) 8,(2 р + 1) по сигналу с выхода блока 6 синхронизации. Одновременно по сигналу с выхода блока 6 синхронизации, поступающему на информационный вход сумматора 5, происходит сложение содержимого регистров 1.(р + 1) 1,(2 р + 1) и регистров 8.(р + 1) 73909 8- 8,(2 р + 1). В этом же такте результат сложения записывается в регистр8.1.В первом такте по сигналу с выхода блока 6 синхронизации содержимоерегистра 81 поступает на информационный выход 11 генератора и на информационный вход регистра 8,2, содержимое регистров 1.(р + 1) - 1,(2 р + 1 О + 1) и 8.(р + 1) - 8.(2 р + 1) поступает на соответствующие информационные входы 1 - (2 р + 2) сумматора 5.Одновременно по сигналу с выхода блока 6 синхронизации, поступающему науправляющий вход сумматора 5, происходит сложение содержимого регистров 1.( р + 1) - 1,(2 р + 1) и8.(р + 1) - 8.(2 р + 1). В этом жетакте результат сложения записывается в регистр 8. 1. Таким образом, впервом такте получено первое значение функции (4) и сформировано следующее значение из последовательности значений массы оптимальногор-кода.Последующие значения последовательности значений функции (4) формируются аналогичным образом путемповторения операций сложения содержимого регистров 1.(р + 1) - 1.(2 р ++ 1), 8.(р + 1) - 8.(2 р + 1) и перезаписи содержимого регистров 8,18.(2 р + 1). При этом первое значениемассы оптимального р-кода формируется при (р+1)-м такте работы генератора и генерируется на (р+2)-м такте работы генератора.Примером функционирования данногогенератора может служить генерация 40последовательностей значений функций(3) и (4) при р= 2, И = 2, как показано в табл,4,В табл.2 - 4 содержимое регистровприведено на момент окончания соответствующего такта.Таблица 410 1273909 Продолжение табл.4 4 1 2 3 5 6 7 8 9 10 10 14 20 8 10 14 6 8 10 2 4 6 2 2 4 0 0 На выходе10 6 8 10 14 2 10 18 30 44 6 10 30 8.2 0 18 30 6 10 18 0 0 00 0 0 4 6 10 0 0 0 а выоде1 18 30 4 0 0 Ф Генератор последовательности рчисел Фнбоначчи, содержащий блок синхронизации, три сумматора, элемент ИЛИ, две группы по (2 р + 1) последо- фО вательно соединенных регистров,причем вход заданий начальных условий генератора подключен к первому входу элемента ИЛИ, второй и третий входы которого подключены соответственно к ,45 выходам первого и второго сумматоров, выход элемента ИЛИ подключен к информационному входу первого регистрапервой группы, входы синхронизации всех регистров обеих групп объединены и 50 подключены к первому выходу блока синхронизации, второй, третий и четвертый выходы которого подключены к входам стробирования первого, второго и третьего сумматоров соответ ственно, выход первого регистра первой группы подключен к выходу значений мощности генератора и первому инизобретения 3 5 формационному входу первого сумматора, второй информационный вход которого подключен к выходу (р + 1)-горегистра первой группы, выходы регистров с (р + 1)-го по (2 р + 1)-йпервой группы подключены к информационным входам второго сумматора,выходы регистров с (р + 1)-го по (2 р ++ 1)-й второй группы подключены кпервой группе информационных входовтретьего сумматора, выход первого регистра второй группы подключен квыходу значений массы генератора,выход третьего сумматора подключен кинформационному входу первого регистра второй группы, о т л и ч а ю -щ и й с я тем, что, с целью расширения класса решаемых задач путем генерирования функции мощности оптимального и модифицированного Р-кодов ифункции массы оптимального Р -кода,в него введен регистр начальных условий, причем информационный входрегистра начальных условий подклюСоставитель О.ОтрадновТехред Л. Серцюкова Корректор Е.Сирохман Редактор М,Дылын Тираж 671 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д.4/5Заказ 6477/46 Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная,4 1чен к входу задани 4 начальных условий генератора, вход синхронизации регистра начальных условий фподключен к пятому выходу блока синхрониз ции, выход регистра начальных усло 1273909 12вий подключен к входу константы второго сумматора, выходы регистров с (р + 1)-го по (2 р + 1)-й первой груп- а- пы подключены к второй грппе информационных входов третьего сумматора.

Смотреть

Заявка

3843388, 09.01.1985

КРАСНОДАРСКОЕ ВЫСШЕЕ ВОЕННОЕ КОМАНДНО-ИНЖЕНЕРНОЕ УЧИЛИЩЕ РАКЕТНЫХ ВОЙСК

КЛЮЧКО ВЛАДИМИР ИГНАТЬЕВИЧ, ТКАЧЕНКО АЛЕКСАНДР ВАСИЛЬЕВИЧ, ФРУНКЕР ВЛАДИМИР ИСААКОВИЧ

МПК / Метки

МПК: G06F 1/02

Метки: генератор, последовательности, фибоначчи, чисел

Опубликовано: 30.11.1986

Код ссылки

<a href="https://patents.su/7-1273909-generator-posledovatelnosti-chisel-fibonachchi.html" target="_blank" rel="follow" title="База патентов СССР">Генератор последовательности -чисел фибоначчи</a>

Похожие патенты