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

 

Изобретение относится к автоматике , вычислительной технике и связи . Целью изобретения является расширение области применения за счет возможности представления чисел в оптимальном р-коде Фибоначчи. В генератор последовательности р-чисел Фибоначчи , содержащий регистры сумматор 3, регистр 4 начального условия и блок 6 элементов ИЛИ, введены блоки 7, 7 J элементов ИЛИ, элемент И 8, блок 10 элементов И, суммирующий счетчик 12, группа блоков , элементов И, блоки 14, 14 элементов запрета, дешифратор 15, шифратор 16 унитарного кода в оптимальный f-код, блок 17 элементов,ИСКЛЮЧАЮЩЕЕ ИЛИ и элемент ИЛИ 20 с соответствующими связями. 2 ил.

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

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

РЕСПУБЛИН

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

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

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 4183456/24-24 (22) 23.01.87 (46) 23.07.88. Бюл. У 27 (72) А.В.Ткаченко (53) 681,3(088.8) (56) Авторское свидетельство СССР

У 1206766, кл, G 06 F l/02, 1974.

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

У 1273909, кл. G 06 F 1/02, 1985. (54) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ р-ЧИСЕЛ ФИБОНАЧЧИ (57) Изобретение относится к автоматике, вычислительной технике и связи. Целью изобретения является расширение области применения за счет возможности представления чисел в оптимальном р-коде Фибоначчи. В генератор последовательности р-чисел Фибоначчи, содержащий регистры 1 -1 +„, сумматор 3, регистр 4 начального условия н блок 6 элементов ИЛИ, введены блоки 7, 7 элементов ИЛИ, элемент

И 8, блок 10 элементов И, суммирующий счетчик 12, группа блоков 13 1-13 +, элементов И, блоки 14 „ 14 элементов запрета, дешифратор 15, шифратор 16 унитарного кода в оптималыый f-код, блок 17 элементов,ИСКЛ1ОЧАКЩЕЕ ИЛИ и элемент ИЛИ 20 с соответствующими связями. 2 ил.

1411725

Получать изображения оптимального р-кода Фибоначчи удобно посредством изображений оптимальной t-системы счисления (t p), для которых характерно наличие после каждой единицы не менее и не более 21 нулей, 55

Изобретение относится к автомати:, ке, вычислительной технике и связи.

Цель .изобретения — расширение об ласти применения за счет возможности представления чисел в оптимальном р5 коде Фибоначчи.

На фиг. l.представлена схема генератора последовательности р-чисел Фибоначчи; на фиг. 2 — схема шифратора, унитарного кода в оптимальный f-код

1(для n=8, f=l).

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

-1 „ первый тактовый вход 2 генератора, сумматор 3, регистр 4 начально- 15 го условия, вход 5 запуска генератора, блок 6 элементов ИЛИ, блоки 7, и, 7 элементов ИЛИ, элемент И 8, второй тактовый вход 9 генератора, блок 10 элементов И, третий тактовый вход 11 генератора, суммирующий счетчик 12, 1 группу блоков 13, — 13 +1 элементов И, блоки 14„ 14 элементов запрета, ; дешифратор 15, шифратор 16 унитарно: :го кода в оптимальный f-код, блок 17 25 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход 18 числа генератора, первый установоч, ный вход 19 генератора,. элемент ИЛИ

20, выход 21 номера числа генератора,, второй установочный вход 22 генера- 30

; тора. !

Шифратор 16 унитарного кода в оп тимальный f-код (фиг. 2) содержит

1 формирователь 23 логического нуля и группу элементов ИЛИ 24„-24, выходы которых являются выходами шйфратора 16, соответствующий вход (S-1)-го элемента ИЛИ соединен с входом С шифратора 16 при Ф„(Б-!) < 0 Ск

Для всех изображений оптимального р-кода Фибоначчи характерно наличие после каждой единицы не менее

- р и не более 2р нулей и, кроме того, не более р нулей в старших разрядах до первой единицы. Такое представление определяет основную отличительную особенность оптимального р-кода Фибоначчи: число В может быть представлено в оптимальном р-коде Фибоначчи различными комбинациями для различных длин и кода.

Число В, представляемое в оптимальном р-коде Фибоначчи, и число С, представляемое в оптимальном t-коде, связаны зависимостью

В двоичной оптимальной t-системе счисления для заданного целого ty 0 и любого натурального С существует представление С в виде:

-,(s); Ф(Б );

1 при <О при 0<Б р, 0

1+1, / (Ь -j — l ) при Б ) р;

1и1

11 (Б )=

0 при S <О, 1+1 (3) ф (Б-,j-l)+1 при Б 0 °

)1 ф (с 1—

Значения ф и) определяют мощность и-разрядного оптимального р-кода Фибоначчи, а значения Ф (п) - мощность и-разрядного оптимального t-кода.

Вес оптимального t-кода, определяющий количество двоичных единиц в множестве ф (п), равен: () 0

IIpH n О, 1

> 1„> (n-t-,j)+ф (и) — 1 при и ъ О.

Сущность изобретения заключаетая в реализации следующего алгоритма . задается значение разрядности кода и; формируется значение ф (п-р-1) согласно рекуррентному соотношению (3);

1 е при получении блока оптимального р-кода Фибоначчи последовательно фориируются значения В=О, Гпту-1, при необходимости получать отдельные кодовые комбинации оптимального р-кода

Фибоначчи, соответствующие значения

В заносятся в генератор избирательно, находится значение С согласно выражевию (1, ;

С(п)=В(п)+ ф (п-р-l).

C= Z С, !i(Б), s=1 5 где С,=! при Ф (Б- l ) СС 0 при 9 (0-1) ) С Е. "" к (К)

1 и Ь1-1 (2) и .Е С, 1,(К) к=5м

1411725 шифруется значение С в оптимальном t-коДе согласно представлению (2). . Генератор работает в двух режимах.

В первом режиме на входе 19 устанавливается код числа tp (n)-1 и фор5 мируется весь блок оптимального р-кода Фибоначчи. Во втором режиме, когда формируются кодовые комбинации оп- тимального р-кода Фибоначчи иэбира10 тельно, на входы 19 и 22 подаются соответствующие номера кодовых комбинаций.

В исходном состоянии все регистры и счетчик обнулены. В первом режиме работы на входе 19 устанавливается число ц (п)-1. Работа начинается с подачи на вход 5 числа "1" в первом такте работы. Далее значения выражения (3) формируются в регистре 1 в каждом такте работы путем сложения содержимого регистров 1 +„, 1 +„ 4 на сумматоре 3 и перезаписи содержимого регистров 1 † 1. Через и-р

Р тактов на входе 2 генератора устанав- 25 ливается нулевой потенциал. В регист- . ре 1 фиксируется значение фР(п-р-l), Одновременно нулевой потенциал с входа 2 генератора переключает входы сумматора 3 к выходам регистра 11 и счетчика 12, на вход ll генератора подаются импульсы. В это время на выходе сумматора 3 образуется число ф (п-р-1)+О, которое в виде кода оптимальной формы поступает через генератор 15 и шифратор 16, на выход 18, 35 что соответствует числу "О" (установленному на выходе 21) в оптимальном р-коде Фибоначчи.

В каждом последующем такте происходит сложение на сумматоре 3 числа фР(п-p-1) с числом в счетчике 12, Последним значением суммы является ф,(п-р-1)+f<(n)-1; после чего на выходе блока 17 элементов ИСКЛЮЧА1ОЩЕЕ 45

ИЛИ образуется нулевой потенциал, который через элемент ИЛИ 20 запрещает прохождение тактовых импульсов через элемент И 8 на счетный вход счетчика

12. Таким образом, на выходе 18 получают все комбинации оптимального р-кода Фибоначчи разрядности п.

При необходимости кодирования одного или нескольких конкретных значений В последние поочередно подаются одновременно на входы 19 и 22. На выходе 18 образуется оптимальная форма суммы В+фР(п -р-1), что соответствует числу В в оптимальном р-коде Фибоначчи, Формула изобретения

Генератор последовательности р-чисел Фибоначчи, содержащий (2р+1) регистров, сумматор, регистр начального условия и первый блок элементов

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

ИСКЛН)ЧАЮЩЕЕ ИЛИ, элемент ИЛИ и блок элементов И, причем первый тактовьп вход генератора соединен с первыми входами блоков элементов И группы, блока элементов И и с управляющими входами первого и второго блоков элементов запрета, выходы которых соединены с первыми входами соответственно второго и третьего блоков элементов ИЛИ, вторые входы которых соединены с выходами первого и второго блоков элементов И группы соответственно, выход блока элементов И, выходы второго и третьего блоков элементов

ИЛИ и выходы блоков элементов И с третьего по (р+1)-й группы соединены соответственно с входами слагаемых сумматора, выход которого соединен с входом дешифратора, выход которого соединен с входом шифратора. унитарного кода в оптимальньп f-код, выход которого является выходом числа генератора, первый установочный вход которого соединен с первым входом

1411725

Корректор М.Васильева

Заказ 3654/43 Тирадк 704 Подписное

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

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

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

5 блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вто- рой вход которых соединен с выходом суммирува1его счетчика, с информационным входом второго блока элементов

5 запрета и является выходом номера числа генератора, второй установочвход которого соединен с установ чным входом суммирующего счетчика, c åòèûé вход которого соединен с выхЬдом эленента И, первый и второй вхокоторого соединены соответственс третьим тактовым входом генераСоставитель А. Клюев

Редактор В.петраш Техред Л.Олийнык

6 тора и с выходом элемента.ИЛИ, входы которого соединены соответственно с выходами разрядов блока элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ, выход первого регистра соединен с информационным входом первого блока элементов запрета, выходы регистров с (р+1)-го по (2р+1)-й соединены с вторыми входами блоков элементов И с (р+1)-ro по первый группы соответственно, второй вход блока элементов И соединен с выходом регистра начального условия.