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

 

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

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

СОИИАЛИСТИЧЕС 1ИХ

РЕСПУБЛИК

„„SU„, 1273909 А1 (51) 4 G 06 F 1/02

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

",3

ll

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3843388/24-24 (22) 09.01.85 (46) 30.11,86, Бюл. № 44 (72) В.И.Ключко, А,В,Ткаченко и В.И.Фрункер (53) 681.325(088 ° 8) (56) Авторское свидетельство СССР №- 662926, кл. G 06 F 1/02, 1976.

Авторское свидетельство СССР № 1196837, кл. С 06 F 1/02,12.11.84.

Авторское свидетельство СССР

¹ 1206766, кл. G 06 F 1/02, 1985.

t (54) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ р-ЧИСЕЛ ФИБОНАЧЧИ (57) Изобретение относится к области автоматики и вычислительной техники и предназначено для генерирования последовательностей значений мощностей с произвольными начальными условиями "фибоначчиевого" оптимального, минимального и модифицированного р-кодов, а также массы оптимального р-кода, задаваемых в виде позиционных кодов. Цель изобретения — расширение класса решаемых задач за счет воэможности генерирования последовательностей значений массы оптимального р-кода и мощности оптимального модифицированного р-кодов ° Генератор содержит регистры первой группы 1,1- 1.(2р + 1),элемент ИЛИ 2, сумматоры 3 — 5, блок 6 синхронизации, регистр 7 начальных условий, регистры второй группы

8.1-8.(2р + 1), информационные вход

9 и выходы 10 и 11, 1 ил. 4 табл.

1273909

Изобретение относится к автомати- ке и вычислительной технике и предназначено для генерирования последовательностей значений мощности с произвольными начальными условиями

"фибоначчиевого" оптимального, минимального и модифицированного р-кодов, а также массы .оптимального р-кода, задаваемых в виде позиционных кодов, Значение мощности с произвольными начальными условиями "фибоначчиевого" р-кода разрядностью и (р-числа Фибоначчи) определяют рекурентным соотношением: при п О при п=0 $n) = Х (п- 1 ) (1) 1+(и-р-1) при п>0

Р где N — произвольное начальное усб ловие; р — целое неотрицательное число, задающее номер двоичной р-системы счисления.

Значения мощности с произвольными начальными условиями оптимального р-кода Фибоначчи разрядностью и и минимального р-кода разрядностью

n — 1 определяются рекуррентным соотношением:

О о

p». p(n - р — j) при n> p

1=1 при п<О при 0<п<р ( (n) Значения мощности с произвольными начальными условиями оптимального и модифицированного р-кодов определяются рекуррентным соотношением:

1 (п) = е+ (3) ср (n-p-j)+N при и ) О =1

Другой важной характеристикой кода является его масса.

Значения массы с произвольными начальными условиями оптимального р-кода, определяющие количество двоичных единиц в множестве кодовых слов мощностью % (n), задаются рекуррентным соотношением:

О при п О

® (п). — Р,„(п-р-j)+ (4) )р+(и-р-j) при п О

В табл,1 приведены значения функции (4) для n = б,ТО и р = 1,4 при

N =1. о

Т а блица 1

012345678910

1 О О 1 2 4 8 13 22 35 5483

О О О 1 2 3 5 9 15 22 33

1О

О О О О 1 2 3 4 6 10 16

400000123457

Цель изобретения — расширение клас- са решаемых задач путем генерирования последовательности значения массы оптимального р-кода и мощности опти2О мального и модифицированного р-кодов.

На чертеже показана схема предлагаемого генератора °

Устройство содержит регистры пер.вой группы 1.1-1.(2р + 1), элемент

25 ИЛИ 2, сумматоры 3, 4 и 5, блок 6 синхронизации, регистр 7 начальных условий, регистры второй группы

8.1 — 8.(2р .+ 1),информационные вход

9 и.выходы 10 и 11, Генератор работает следующим образом.

B исходном состоянии в регистрах

2) 1,1 — 1. (2р + 1), 8.1 — 8 ° (2р + 1) и регистре 6 содержатся нулевые коды. В нулевом такте на информационный вход 9 генератора подается код

N начального условия, который поступает на информационный вход регистра 1. 1 через элемент ИЛИ 2 и

40 на информационный вход регистра 7 непосредственно.

В режиме моделирования последовательности значений мощности с произвольными начальными условиями

"фибоначчиевого" р-кода по сигналу, поступающему с выхода блока 4 на вход синхронизации регистра 1.1 производится запись кода N в регистр 1.1. В первом такте содержимое регистра 1.1 под воздействием

50 сигнала с выхода блока синхронизации поступает на информационный выход генератора 10, на информационный вход регистра 1.2 и на первый информационный вход сумматора 3, на второй информационный вход которого поступает содержимое регистра

1,(р + 1). По сигналу, поступающему в этом же такте с выхода блока

909

Примером функционирования данного генератора может служить формирование последовательности значений функции (1) при р = 2, N, = 2, по15 казанное с помощью табл,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

На выходе

2 2 2 4 6 8 12 18 26 38 з 1273

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

ro р-кода формируются повторением операции сложения содержимого реги стров 1,1 и 1,(р + 1) и перезаписи содержимого регистров 1. 1 — 1.(р + 1) .

В первом режиме работы генератора

В режиме моделирования последовательности значений мощности с произвольными начальными условиями фи- 40 боначчиевого"оптимального р-кода по сигналу, поступающему с выхода блока 6 на управляющий вход регистра

1.1, производится занесение кода Nz в регистр 1.1. В первол такте по сигналу с выхода блока 6 синхронизации содержимое регистра 1.1 постулат на информационный выход генераора 10, информационный вход региста 1.2 и второй информационный вход сумматора 3, на первый информационный вход которого поступает содержимое

1.(р + 1)-ro регистра. Одновременно по сигналу с выхода блока 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.и поступит на выход генератора во втором такте. Последующие (р-1) значений функции 9 (и) мос делируются аналогичным образом путем повторения операций сложения содержимого регистров 1.1 и 1,(р + 1) и перезаписи содержимого регистров

1.1 — 1 ° (р + 1).

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

7 8 9 10

2 2 2 4. 6 6 8 12 16 20

2 2 2 2 4 6 6 .8 12 16

6 8 12

0 2 2 2 2 4 6

0 0 2 2 2 2 4 6 6 8

0 0 0 2 2 2 2 4 6 6

На вы2 2 2 4 6 6 8 12 16 ходе генератора 2

5 1273 матора 4, Перед (р + 1)-м тактом в регистрах 1.1 — 1.(р + 1) записан код начального состояния N регистрах 1.(р + 2) — 1.(2р + 1) — нулевой код. В (р + I)-м такте по сигналу с выхода блока 6 из регистра 1.1 происходит выдача на информационный выход генератора 10 р-ro значения мощности с начальным условием М оптимального "фибоначчиевого" кода 10 и перезапись содержимого регистров

1.1 — 1. (2р + 1), Одновременно на информационные входы сумматора 4 поступает содержимое регистров 1.(р +

+ 1) — 1е(2p + 1), По сигналу с вы- 15 хода блока сумматор 4 производит сложение поступающих из регистров

1. (р + 1) — 1. (2р + 1) кодов чисел. Полу- ченный в результате сложения код суммы с информационного выхода суммато- 20 ра 4 через элемент ИЛИ 2 записыва1

В режиме моделирования последовательности значений мощности и массы с произвольными начальными условиями оптимального р-кода по сигна" лу, поступающему с выхода блока 6 синхронизации на управляющий вход регистра 1.1, производится занесение кода N в регистр 1.1, а по сигналу, поступающему на управляющий вход.регистра с выхода блока 6 синхрониза909 6 ется в регистр 1.1, Таким образом, в (р + 1)-м такте сформирован код (р + 1)-ro значения мощности иэ последовательности значений мощности с начальным условием N оптимального а

"фибоначчиевого" р-кода, который поступает на выход генератора 10 в след .ющем (р + 2)-м такте. Последующие значения мощности с начальным условием М оптимального р-кода

Фибоначчи моделируются повторением операций сложения содержимого регистров 1.(р + 1) — 1.(2р + 1) и перезаписи содержимого регистров

1.1 — 1.(2р + 1).

Примером функционирования данного генератора может служить моделирование последовательности функций (2), как показано в табл,3, при р = 2, N = 2, Таблица 3 ции, код начального условия N заносится в регистр 7. В первом такте по сигналу с выхода блока 6 синхронизации содержимое регистра 1,1 поступает на информационный выход 10 генератора и информационный вход регистра 1.2; содержимое регистров

1.(р + 1) — 1.(2р + 1) поступает на соответствующие информационные входы 1 - (р + 1} сумматора 4, на (р+2)-й

12,5 6

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). Последующие значения функции Р (n) моделируются аналогичным

P образом путем повторения операций сложения содержимого регистров 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) — i,(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 синхронизации содержимое регистра 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.(р + i) — 8.(2р + 1). В этом же такте результат сложения записывается в регистр 8. 1. Таким образом, в первом такте получено первое значение функции (4) и сформировано следующее значение из последовательности значений массы оптимального

25 Р кода °

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

+ 1), 8.(р + 1) — 8.(2р + 1) и перезаписи содержимого регистров 8,1

8.(2р + 1). При этом первое значение массы оптимального р-кода формируется при (р+1)-м такте работы генера35 тора и генерируется на (р+2)-м такте работы генератора.

Примером функционирования данного генератора может служить генерация

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

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

Таблица 4

1273909

Продолжение табл.4

1 2 3

5 6 7 8

9 10

0 2 2 2 4 6 8 10 14 20

0 0 2 2 2 4 6 8 10 14

0 0 0 2 2 2 4 6 8 10

1.3

1.4

1.5

На выходе

2 2 2 4 б 8 10 14 20 26

0 0 2 4 б 10 18 30 44 66

0 0 0 2 4 6 10 18 30 44

8.1

8.2

0 0 0

0 0 0

8.3

8.4

0 0 0 0 0 0 2 4 6 10

8.5

На выходе

0 0 0 2 4 6 10 18 30 44

Формула из обретения 35

Генератор последовательности рчисел Фнбоначчи, содержащий блок синхронизации, три сумматора, элемент

ИЛИ, две группы по (2р + 1) последо- 40 вательно соединенных регистров,причем вход заданий начальных условий генератора подключен к первому входу элемента ИЛИ, второй и третий входы которого подключены соответственно к выходам первого и второго сумматоров, выход элемента ИЛИ подключен к информационному входу первого регистра первой группы, входы синхронизации всех регистров обеих групп объединены и 50 подключены к первому выходу блока синхронизации, второй, третий и четвертый выходы которого подключены к входам стробирования первого, второго и третьего сумматоров соответ- 55 ственно, выход первого регистра первой группы подключен к выходу значений мощности генератора и первому ин0 2 .4 6 10 18 30

0 0 2 4 6 10 18 формационному входу первого сумматора, второй информационный вход которого подключен к выходу (р + 1)-ro регистра первой группы, выходы регистров с (р + 1}-ro по (2р + 1)-й первой группы подключены к информационным входам второго сумматора,выходы регистров с (р + 1)-ro по (2р +

+ 1)-й второй группы подключены к первой группе информационных входов третьего сумматора, выход первого регистра второй группы подключен к выходу значений массы генератора,выход третьего сумматора подключен к информационному входу первого регистра второй группы, о т л и ч а ю— шийся тем, что, с целью расширения класса решаемых задач путем генерирования функции мощности оптимального и модифицированного Р-кодов и функции массы оптимального р -кода, в него введен регистр начальных условий, причем информационный вход регистра начальных условий подклюСоставитель 0.0траднов

Техред Л. Серцюкова Корректор Е Сирохман

Редактор М,Дылын

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

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

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

Заказ 6477/46

Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная,4

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