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

ГО

ел

Изобретение относится к aвтo 5aти- ке, вычислительной технике и связи.

Цель .изобретения - расширение области применения за счет возможности

j представления чисел в оптимальном р;коде Фибоначчи.

: На фиг. 1. представлена схема гене ратора последовательности р-чисел Фи: боначчи; на фиг. 2 - схема шифратора

j унитарного кода в оптимальный f-код

i (для , ).

j Генератор содержит регистры ЦMj ,j первый тактовый вход 2 генератора, сумматор 3, регистр 4 начального условия, вход 5 запуска генератора, блок 6 элементов ИЛИ, блоки 7 и

I 7 элементов ИЛИ, элемент И 8, второй тактовый вход 9 генератора, блок 10 элементов И, третий тактовый вход 11 генератора, суммирующий счетчик 12, группу блоков 13,-13р.1 элементов И, блоки 14 и 14 элементов запрета, дешифратор 15, шифратор 16 унитарного кода в оптимальный f-код, блок 17 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход 18 числа генератора, первый установочный вход 19 генератора,, элемент ИЛИ 20, выход 21 номера числа генератора, второй установочный вход 22 генератора.

Шифратор 16 унитарного кода в оптимальный f-код (фиг. 2) содержит формирователь 23 логического нуля и группу элементов ИЛИ выходы которых являются выходами шифратора 16, соответствующий вход (S-l)-ro элемента ИЛИ соединен с входом С шифратора 16 при Ф,(3-1 ) oil Ск

Кг 6+1

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

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

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

С(п)В(п)+фр(п-р-1). (1)

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

0.5(3),

где Сдг1 при ф.(3-1)С- Л С Ц(К

Пг5+

(s);

(2)

20

С рО при ф,(Й-1) УС- 2Ic.,it i(K)7

.Ф/.Б );

V,(SV

О

1 i

при при О р,

51 Vx(-J-l) при-5 р; )1

0

5

, ,,,1 Опри g ГО,

f(S,-j,,(3)

XI ф (S-j-l) + l при sS.O.

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

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

, ч 1 Опри п О,

(U.i

5

0

5

,Z(xJ,(n-t-,l) + 4(n)- 1 ,

i t

Сущность изобретения заключаетея в реализации следующего алгоритма:

задается значение разрядности кода п;

формируется значение фр(п-р-1) согласно рекуррентному соотношению

(3);

при получении блока оптимального

р-кода Фибоначчи последовательно формируются значения , ЧЧп)-1 , при необходимости получать отдельные кодовые комбинации оптимального р-кода Фибоначчи, соответствующие значения В заносятся в генератор избирательно находится значение С согласно выражению (1);

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

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

В исходном состоянии все регистры и счетчик обнулены. В первом режиме работы на входе 19 устанавливается число (т1}-. Работа начинается с подачи на вход 5 числа 1 в первом такте работы. Далее значения выражения (З) формируются в регистре 1 в каждом такте работы путем сложения содержимого регистров 1 р. , 2р-и на сумматоре 3 и перезаписи содержимого регистров . Через п-р . тактов на входе 2 генератора устанав- ливается нулевой потенциал. В- регистре 1 фиксируется значение фр(п-р-1). Одновременно нулевой потенциал с входа 2 генератора переключает входы сумматора 3 к выходам регистра 1. и счетчика 12, на вход 11 генератора подаются импульсы, В это время на выходе сумматора 3 образуется число фр(п-р-1)+0, которое в виде кода оп

тимальной формы поступает через генератор 15 и шифратор 16, на выход 18, что соответствует числу О (установленному на выходе 21) в оптимальном р-коде Фибоначчи.

В каждом последующем такте происходит сложение на сумматоре 3 числа фр(п-р-1) с числом в счетчике 12. Последним значением суммы является фр(п-р-1) + Ур(п)-1, после чего на

35

40

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

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

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

50

55

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

0

5

5 JQ

0

35

40

числу в в оптимальном р-коде Фибоначчи.

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

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

0

5

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

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

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

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