Устройство для приведения р-кодов фибоначчи к минимальной форме

 

ОП ИСАНИЕ

ИЗОБРЕТЕН Ия

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

Союз Советских

Соцмалмстическнх

Реслублкк ii>779997 (61) Дополнительное к авт. свид-ву (5I)M. Кл.

3 (22) Заявлено 26.12.78 (21) 2701498/18-24 с присоединением заявки М (23) П риоритет

G 06 F 5 00

1ееударстеенный комитет

СССР по делам изобретений и открытий

Опубликовано 15.11.80 Бюллетень Ле 42 (53) УДК 681,327 (088.8) Дата опубликования описания 15,11.80

А. П. Стахов, В. А. Лужецкий, А. Д. Азаров и Ю, Н. Ужвак (72) Авторы изобретения (71) Заявитель

Винницкий политехнический институт (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КОДОВ

ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ

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

Проведенные патентные исследования по научно-технической и патентной. литературЕ показали, что не существует аналогов устройства для приведения кодов к минимальной форме.

Это связано с тем, что теории р-кодов Фибоначчи и кодов обобщенной "золотой" пропорции начала развиваться в последнее время.

Поэтому наиболее близким по технической сущности является устройство для приведения ркодов Фибоначчи к минимальной форме, состоящее из и однотипных блоков свертки, причем первый выход 1-ro блока свертки соединен с первым входом (1-1)-ro и вторым входом (2-р-1)-го блоков свертки, второй выход g -го блока свертки является P-м информационным

20 выходом устройства и соединен с третьим входом (Р-!)-го и четвертым входом (E+p+1)-ro . блоков свертки, управляющий вход устройства соединен с пятыми входами всех блоков свертim, шестые входы каждого блока свертки являются информационными входами устройства, кроме того, каждый блок содержит триггер, элемент И, первый и второй элементы ИЛИ, причем выход элемента И соединен с первым входом первого элемента ИЛИ и является первым выходом блока, единичный выход триггера является вторым выходом блока, первый и второй входы блока соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединен с нулевым входом триггера, нулевой выход триггера соединен с первым входом элемента И, второй, третий и четвертый входы которого являются соответственно третьим, четвертым и пятым входами блока, второй вход первого элемента ИЛИ, является шестым входом блока, выход первого элемента ИЛИ соединен с единичным входом: триггера (11.

Недостатком такого устройства является невозможность выполнения операции сдвига кода.

Цель изобретения — расширение функциональных возможносте заключаю|цееся в возможнос3 7

TH выполнения устройством дополнительно операции сдвига р-кодов Фибоначчи и кодов обобщенной, золотой пропорции.

Поставле пгая цель достигается тем, что устройство для приведения р-кодов Фибоначчи к минимальной форме содержащее и однотипных блоков свертки, причем первый выход

Вго блока свертки соединен с первым входом (11)-го и вторым входом (Е-р-1)-блоков свертки, второй выход 1-ro блока свертки является 1-м информационным выходом устройства и соединен с тоетьим входом 1-го и четвертым входом (8+р+1)-rо блоков свертки, управляющий вход устройства соединен с пятыми входами всех блоков свертки, пятые входы каждого блока свертки, являются информационными входами устройстаа, третий выход 1-го блока свертки соединен с седьмым входом (E-p)-ro блока свертки, четвертый выход 1-го блока свертки соединен с восьмым входом (E-p)-ro блока свертки, второй управляющий вход устройства соединен с девятыми входами всех блоков свертки и еще тем, что блок свертки содержит триггер, первый и второй элементы И, первый и второй элементы ИЛИ, причем выход первого. элемента И соединен с первым входом первого элемента ИЛИ и является первым выходом блока, единичный выход триггера соединен с первым входом второго элемента И и является вторым выходом блока, выход второго элемента И является третьим выходом блока первый и второй входы блока соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединен с нулевым входом триггера, выход первого элемента HJIH, соединен с единичным входом триггера, нулевой выход триггера соеди .-. нен с первым входом первого элемента И и является четвертым выходом блока, второй, . третий и четвертый. входы первого элемента И являются соответственно третьим, четвертым и пятым входами блока, второй и третий входы первого элемента ИЛИ являются соответственно. шестым и седьмым входами блока, второй и третий входы второго элемента И являются соответственно восьмым и девятым входами блока.

79997 4

30

5S

На чертеже представлена функциональная схема устройства 1 для приведения кодов к минимальной форме, состоящего иэ шести (в общем случае из и однотипных блоков) 2 по числу разрядов р-кода Фибоначчи или кода обобщенной "золотой" пропорции (р-1), каждый из которых является одноразрядной функциональной ячейкой, соединяя которые определенным образом, можно получить устройство 1 для приведения кодов к минимальной форме необходимой разрядности. Каждый из блоков 2 содержит триггер 3, выполняющий функции элементов памяти, единичный выход которого является информационным выходом

4 устройства 1 и вторым выходом блока 2.

В состав блока 2 также входят первый элемент И 5, анализирующий выполнение условия свертки, и второй элемент И 6, анализирующий выполнение условия занесения единицы, причем нулевой выход триггера 3 связан с первым входом первого элемента И S и является четвертым выходом 7 блоков. Выход первого элемента И 5 является первым выходом 8 блока 2, а второй, третий и четвертый входы weмента И 5 являются соответственно третьим входом 9, четвертым входом 10 и пятым входом 11 блока 2. Единичный выход триггера 3 соединен с первым входом эЛемента И 6, выход которого является третьим выходом 12 блока 2. Второй и третий входы элемента И 6 являются соответственно восьмым входом 13

20 и девятым входом 14 блока 2. Каждый из блоков 2 содержит также первый элемент ИЛИ

15, выход которого соединен с единичным входом триггера 3, а первый вход элемента ИЛИ

15 соединен с выходом первого элемента И 5, 25

Второй вход элемента ИЛИ 15 является информационным входом 16 устройства 1 и шестым входом блока 2. Третий вход первого элемента ИЛИ 15 является седьмым входом 17 блока 2. В состав блока 2 входит также второй элемент ИЛИ 18, выход которого соединен с нулевым входом. триггера 3. Первый и второй входы второго элемента ИЛИ 18 являются соответственно первым входом 19 и вторым входом 20 блока 2. Первый управляющий вход

21 устройства 1 соединен с пятыми входами

11 блоков 2, а второй управляющий вход 22 устройства 1 соединен с девятыми входами 14 блоков 2. На входы блока 2 с первого по пятый поступают сигналы, обеспечивающие выполнение операции свертки, а на входы седьмого по девятый — занесение единиц. На первом и втором выходах формируются сигналы необходимые при выполнении свертки, а на третьем и четвертом — при занесении единиц.

Операция сдвига выполняется на основе свойств р-кодов Фибоначчи и койов обобщенной "золотой"пронорции.

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

N=a г Цр(n)+a„ / р(n-1)+...+а,Яр (О), (1) где а, ((0,1 р 1, 2, 3,...

У,()= У„(-1)+Ур(-р-1)

g, (0) =1.

Существует множество представлений числа и вида (1). .Однако имеется единственная, так называемая, минимальная форма представления, харак5 7 терным признаком которой является наличие не менее р нУлей после каждой единицы. Переход от любой не минимальной формы представления числа М к минимальной форме осуществляется на основе выполнения операции свертки разрядов.

Операция свертки разрядов заключается в инвертировании i-го, (i-1)-го (i-p-1)-го разрядов при условии, что а;=О, а а, = а,, =1

Предел отношения " "1 при и -+ ""

Vp(n--?) равен постоянной величине й?, которая является действительным положительным корнем уравнения:: р ? х =х +1 и называется обобщенной "золотой" . пропорцией. Используя степени обобщенной "золотой" пропорции, можно представить любое действительное число 0 в виде: ф

0= Z ае а„ еаао

) . Во втором такте единичный сигнал подается на первый управляющий вход 21 устройства 1 и производится свертка кода известным образом.

Пример сдвига кода в устройстве 1 при р-1 приведен в следующей таблице.

0 (исходи. код) 0 1 0 1 0 0

0 1 1 1 1 0

0 1 1 1 1 0

1 1 0

0 0 0

1 0 0

1 0 1

Данное представление называется кодом обобщенной "золотой" пропорции децствительного числа О.

Для этих кодов так же, как и для р-кодов

Фибоначчи сопутствует понятие максимальной формы, приведение к которой любой формы кода числа 5 осуществляется на основе операции свертки.

Все логические и арифметические операции выполняются над кодами, представленными в минимальной форме.

Обобщенная "золотая" пропорция обладает следующим свойством:

6 е ? ф-?Ф - ?

0. p= Qp t сг„ что вытекает из уравнения (2) и является аналогичным соотношению Ц„(n) =, (n-1) + „(n-p-1 для р-кодов Фибоначчи.

- В силу общих свойств р-кодов Фибоначчи и кодов обобщенной "золотой" пропорции предложенное устройство может осуществлять операцию свертки над обеими кодами.

79997 б

Исходя из того, что операция свертки как бы перемещает единицу (?.-1)-го разряда в

6й разряд при наличии единицы в (??-р-l)-м разряде, операцию сдвига единицы 1-го разряда можно свести к занесению единицы в (E.ð-1)-й разряд и последующей свертке единиц этих разрядов в единицу 1 го разряда.

При наличии единицы ъ (1?-1)-м разряде занесение единицы в (Бр-1)-й разряд возмож10 но только при наличии нуля в (К+р-1)-м разряде.

Такое условие необходимо для исключения записи единицы в (В-2р-!)-й разряд после записи единицы в (6p-1)-й разряд.

Таким образом сдвиг кода. осугцествляется за два такта: занесение единиц и свертка.

Рассмотрим работу устройства 1.

Первый такт. Если в (8-1)-м разряде записана единица, то, исходя из свойства минимальной формы представления кодов, в (f+p-1)-м и (У-р-1)-xi разрядах будут нули.

В силу этого на первом входе второго элемента И 6 (8-1)-го блока 2, подключенном к единичному выходу 4 триггера 3 этого блока 2 и на втором входе этого же элемента подключенном к нулевому выходу 7 триггера

3 (Й+р-1)-ro блока 2 будут присутствовать единичные сигналы, Если теперь на второй управляю?ций вход 22 устройства 1 подать единичный сигнал, то на выходе второго элемента И 6 (6-1)-го блока 2 появится одиничный сигнал, который пройдя через первый элемент ?ЛЛИ 15 (6р-1) -го блока 2 установит триггер 3 этого блока в единичное состояние. На этом первый такт эаканчива35

2$

7 77999

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

Это позволяет сократить затраты оборудования при использовании предложенного устройства в различных операционных устройствах.

Так как, в тех случаях, когда над кодом необходимо осуществлять операции приведе ния к минимальной форме сдвига (например, в устройствах для уменьшения), отпадает необходимость в регистре сдвига.

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

1 . Устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее и блоков свертки, причем первый выход ь-ro блока свертки соединен с первым входом (2-1)-ro и вторым входом (2-р-1)-ro блоков свертки, второй выход т.-ro блока свертки asляется 3-м информационным выходом устройства и соединен с третьим входом (т .+1)-ro u четвертым входом (2+р+1)-ro блоков свертки, ут равляющий вход устройства соединен. с пятыми входами всех блоков свертки, шестые входы каждого, блока свертки являются информацйонными входами устройства, о т л N ч а ю щ е е с я тем; что, с целью расширения функциональных возможностей за счет обеспечения возможности выполнения операции сдвига, третий выход его блока свертки смдинен с седьмым входом (2-р)-ro блока свертки, четвертый выход 2-ro блока свертки соединен

7 8 с восьмым входом (1-р)-ro блока свертки, второй управляющий вход устройства соединен, . с девятыми входами вмх блоков свертки.

2. Устройство по п. 1, о т л и ч а ю щ е ее я тем, что блок свертки содержит триггер, первый и второй элементы И, первый и второй элементы ИЛИ, причем выход первого элемента

И соединен с первым входом первого элемента

ИЛИ и является первым выходом блока, единичный выход триггера соединен с первым входом первого элемента ИЛИ и является первым выходом блока, единичный выход триггера соединен с первым входом второго элемента И и является вторым выходом блока, выход второго элемента

И является третьим выходом блока, первый и второй входы блока соединены соответственно с первым и вторым входами второго элемента

ИЛИ, выход которого соединен с нулевым входом триггера, выход первого элемента ИЛИ соединен с единичным входом триггера, нулевой выход триггера соединен с первым входом первого элемента И и является четвертым выходом блока, второй, третий и четвертый входы первого элемента И являются соответственно третьим, четвертым и пятым входами блока, вто.рой и третий входы первого элемента ИЛИ явля. ются соответственно шестым и седьмым входамИ блока, второй и третий входы второго элементa И являются соответственно восьмым и девятым входами блока.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР по заявке

Ю 2386002/18-24, кл. 6 06 F 5/ОО, 02.08.76 (прототип).