Генератор последовательности @ -чисел Фибоначчи Советский патент 1986 года по МПК G06F1/02 

112739 Изобретение относится к автоматике и вычислительной технике и предназначено для генерирования последовательностей значений мощности с произвольными начальными условиями 5 фибоначчиевого оптимального, минимального и модифицированного р-кодов, а также массы .оптимального р-кода, задаваемых в виде позиционных кодов. Значение мощности с произвольны- 10 ми начальными условиями фибоначчиевого р-кода разрядностью п (р-числа Фибоначчи) определяют рекурентным соотношением: Опри п О Ngпри ЧрСп-О +(1) .%-ь(п-р-1)при где N - произвольное начальное ус6ловие; р - целое неотрицательное число, задающее номер двоично р-системы счисления. Значения мощности с произвольным начальными условиями оптимального р-кода Фибоначчи разрядностью п и минимального р-кода разрядностью п - 1 определяются рекуррентным соотношением:при п о при 5;;ii4p(n - р - j) при п р Значения мощности с произвольным начальньми условиями оптимального и модифицированного р-кодов определяются рекуррентным соотношением: / 0.при п 0 %(п) glcp(p.j),N, ,р„,,0 Другой важной характеристикой кода является его масса. Значения массы с произвольными начальными условиями оптимального р-кода, определяющие количество дво ичных единиц в множестве кодовых сл мощностью Ф (п), задаются рекуррент ным соотношением: Гопри Шр(п)., (n-p-j)-t- (4) p(n-p-j) при В табл.1 приведены значения функ ции (4) для п ОГ/ГО и р 1,4 при Таблица 1 О О 1 2 4 8 13 22 35 54 83 О О 0123 9 15 22 33 О О 0012 6 10 16 О О 0001 Цель изобретения - расширение класса решаемых задач путем генерирования последовательности значения массы оптимального р-кода и мощности оптимального и модифицированного р-кодов. На- чертеже показана схема предлагаемого генератора. Устройство содержит регистры первой группы 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 генератора подается код NJ, начального условия, который поступает на информационный вход регистра 1.1 через элемент ИЛИ 2 и на информационный вход регистра 7 непосредственно. В режиме моделирования последовательности значений мощности с произвольными начальными условиями фибоначчиевого р-кода по сигналу, поступающему с выхода блока 4 на вход синхронизации регистра t.1 производится запись кода N в регистр 1.1. в первом такте содержимое регистра 1.1 под воздействием сигнала с выхода блока синхронизации поступает на информационньй выход генератора 10, на информационный вход регистра 1.2 и на первый информационный вход сумматора 3, на второй информационный вход которого поступает содержимое регистра 1f(р + 1). По сигналу, поступающему Е этом же такте с вькода блока

3

6, происходит сложение поступивших из регистров 1.1 и 1.(р + 1) на сумматор 3 кодовых комбинаций чисел. Одновременно результат сложения за«писывается в регистр 1.1 через элемент ИЛИ 2, Таким образом, в первом такте получено первое значение функции (1). Последующие значения последовательности значений мощности с начальным условием фибоначчиевого р-кода формируются повторением операции сложения содержимого регистров 1.1 и 1.(р + 1) и перезаписи содержимого 2егистров 1.1 - 1 . (р + О . В первом режиме работы генератора

739094

сложение содержимого регистров 1.(р + 1) - 1.(2р + 1) и регистра 7 на сумматоре 4 и содержимого регистров 1.(р + 1) - 1.(2р + 1),8.(р + 5 + 1) - 8.(2р + 1) на сумматоре 5 не происходит, та как на входах синхронизации сумматоров 4 и 5 отсутствуют синхроимпульсы выходов и блока 6 синхронизации.

Примером функционирования данного генератора может служить формирование последовательности значений функции (1) при р 2, Ng 2, показанное с помощью табл.2.

Таблица 2

Изобретение относится к области автоматики и вычислительной техники и предназначено для генерироf-A/h- гги ri вания последовательностей значений мощностей с произвольными начальными условиями фибоначчиевого оптимального, минимального и модифицированного р-кодов, а также массы оптимального р-кода, задаваемых в виде позиционных кодов. Цель изобретения - расширение класса решаемых задач за счет возможности генерирования последовательностей значений массы оптимального р-кода и мощности оптимального модифицированного р-кодов. Генератор содержит регист. ры первой группы 1.1-1.

В режиме моделирования последовательности значений мощности с произвольными начальными условиями фибоначчиевого оптимального р-кода по сигналу, поступающему с выхода блока 6 на управляющий вход регистра 1.1, производится занесение кода N в регистр 1.1. В первом такте по сигналу с выхода блока 6 синхронизации содержимое регистра 1.1 поступаЕт на информационный выход генераора 10, информационный вход региста 1,2 и второй информационный вход сумматора 3, на первый информационны вход которого поступает содержимое 1(р + 1)-го регистра. Одновременно по сигналу с выхода блока 6 синхронизации, поступающему на управляющий вход сумматора 3, происходит сложение содержимого регистров 1.1 и 1.(р + 1). В этом же такте результат сложения через элемент ИЛИ 2 записывается в регистр 1.1. Таким образом, в первом такте получено первое значение функции (2) и сформировано первое значение из последовательности значений мощности с начальным условием N, код которого содержится в регистре 1.1.и поступит на выход генератора во втором такте. Последующие (р-1) значений функции Ч (п) моделируются аналогичным образом путем повторения операций сложения содержимого регистров 1,1 и 1,(р+ 1) и перезаписи содержимого регистров 1.1 - 1.(р + 1). Начиная с (р + 1)-го такта работы генератора, формирование синхроимпульсов на выходе блока 6 синхронизации прекращается, а сигналы управления начинают поступать с выхода блока 6 на управляющий вход сумматора 4, Перед (р + 1)-м тактом в регистрах 1,1 - 1.(р + 1) записан код начального состояния N, а в регистрах 1.(р + 2) - 1. (2р 1) - нулевой код. В (р + 1)-м такте по сигналу с выхода блока 6 из регистра 1.1 происходит выдача на информационный выход генератора 10 р-го значения мощности с начальным условием N, оптимального фибоначчиевого кода и перезапись содержимого регистров 1.1 - 1.(2р+ 1). Одновременно на информационные входы сумматора 4 поступает содержимое |)егистров 1. (р + 1) - 1.(2р « 1), По сигналу с выхода блока сумматор 4 производит сложение, поступающих, из регистров 1 . (р + 1) - 1 . (2р + i) кодов чисел.Полученный в результате сложения код сум мы с информационного выхода сумматора 4 через элемент ИПИ 2 записьшаТакт

2 2 О О О

24

2 2 2 О О

22

22

22

О2

На выходегенератораВ режиме моделирования последовательности значений мощности и массы с произвольными начгшьными условиями оптимального р-кода по сигналу, поступающему с вьисода-.блока 6 синхронизации на управляющий вход регистра 1.1, производится занесение кода Ng в регистр 1.1, а по сигналу, поступающему на управляющий вход регистра с выхода блока 6 синхрониза10

6

1216

20

6

6 6 4 2

16

.812

4

68

12

66

2

8

2

46

6

4 6

8 12 16 ется в регистр 1.1. Таким образом, в (р + 1)-м такте сформирован код (р + 1)-го значения мощности из последовательности значений мощности с начальным условием N оптимального фибоначчиевого р-кода, который поступает на выход генератора 10 в след.ющем (р + 2)-м такте. Последующие иначе ния мощности с начальным условием N оптимального р-кода Фибоначчи моделируются повторением операций сложения содержимого регистров 1.(р + 1) - 1.(2р + 1) и перезаписи содержимого регистров 1.1 - 1.(2р + 1). Примером функционирования данного генератора может служить моделирование последовательности функций (2), как показано в табл.3, при р - 2, N 2. ТаблицаЗ ции, код начального условия N заносится в регистр 7. В первом такте по сигналу с выхода блока 6 синхронизации содержимое регистра 1.1 поступает на информационный выход 10 генератора и информационный вход регистра 1.2; содержимое регистров 1.(р + 1) 1.(2р + 1) поступает на соответствую15ие информационные входы 1 - (р + 1) сумматора 4, на (р+2)-й

информационный вход которого поступает содержимое регистра 7 по сигналу с выхода блока 6 синхронизации. Одновременно по сигналу с выхода блока 6 синхронизации, поступающему на управляющий вход сумматора 4, происходит сложение содержимого регистров 1 . (р 1) - 1.(2р + 1) и регистра 7, В этом же такте результат сложения через элемент ИЛИ 2 записывается в регистр 1.1. Таким образом, в первом такте получено первое значение функции (3). Последующие значения функцииР (п) моделируются аналогичным образом путем повторения операций сложения содержимого регистров 1.(р+ f 1) - V, (2р + 1) и регистра 7 и перезаписи содержимого регистров 1,1-1.(2р + 1). В третьем режиме работы сложение содержимого регистров 1.1 и 1.(р + 1) не происходит, так как на управляющем входе сумматора 3 отсутствует сигнал с выхода блока 6 синхронизации.

Рассмотрим работу схемы в моделировании массы оптимального р-кода с произвольными начальными условиями Bbmie указано,что содержимое регистров 1,(р + 1) - 1.(2р + 1) поступает на соответствующие информационные входы 1 - (р + 1) сумматора 4. Параллельно содержимое регистров 1.(р + 1) 1t(2р + 1) поступает на соответствующие входы 1 - (р+.1) сумматора 5, на (р + 2) - (2р + 2) информационные входы которого поступает содержимое регистров 8.(р + 1) 8,(2р + 1) по сигналу с выхода блока 6 си1нхронизации, Одновременно по сигналу с выхода блока 6 синхронизации, поступающему на информационный вход сумматора 5, происходит сложени содержимого регистров 1.(р + 1) 1,(2р + 1) и регистров 8,(р + 1) - 8.(2р + 1). В этом же такте результат сложения записьшается в регистр 8.1.

В первом такте по сигналу с выхода блока 6 синхронизации содержимое регистра 8.1 поступает на информационный выход 11 генератора и на информационный вход регистра 8.2, содержимое регистров 1,(р + 1) - 1.(2р + + 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,1 8.(2р + 1). При этом первое значение массы оптимального р-кода формируется при (р+1)-м такте работы генератора и генерируется на (р+2)-м такте работы генератора.

Примером функционирования данного генератора может служить генерация последовательностей значений функций (3) и (4) при р 2, N 2, как показано в табл.4.

В табл.2 - 4 содержимое регистров приведено на момент окончания соответствующего такта. . Таблица 4

О О 2 4 6 10 18 30 4466

О О О 2 4 6 10 18 3044

О О О О 2 .4 6 10 1830

О О О О О 2 46 1018

00000024610

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

6 10 18 30 44 формационному входу первого сумматора, второй информационный вход которого подключен к выходу (р + 1)-го регистра первой группы, выходы регистров с (р + 1)-го по (2р + 1)-й первой группы подключены к информационным входам второго сумматора,выходы регистров с (р + 1)-го по (2р + + 1)-й второй группы подключены к первой группе информационнБпс входов третьего сумматора, выход первого регистра второй группы подключен к выходу значений массы генератора,выход третьего сумматора подключен к информационному входу первого регистра второй группы, отличающийся тем, что, с целью расширения класса решаемых задач путем генерирования функции мощности оптимального и модифицированного Р-кодов и функции массы оптимального р -кода, в него введен регистр начальных условий, причем информационный вход регистра начальных условий подклю11127390912

чен к входу задани5 начальных уело- вий подключен к входу константы втовий генератора, вход синхронизации рого сумматора, выходы регистров с регистра начальньк условийподклю- (р + 1)-го по (2р + 1)-й первой групчен к пятому выходу блока синхрониза- пы подключены к второй rpvnne инфорции, выход регистра начальных уело- j мационных входов третьего сумматора.