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

:яМ хр: .: 4 Ф В Пав "ЙЙУФВниййВМию. ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик 1 п 779997(23) П риоритет 6 06 Е 5/00 Веударстееииый комитет СССР по делам изобретеиий и открытий(088.8) Дата опубликования описания 15,11,80 А. П. Стахов, В. А. Лужецкий, А, Д. Азаров и Ю, Н. Ужвак(71) Заявитель Винницкий политехнический институт(54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р.КОДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ 3г1,с Изобретение относится к области вычислительной техники и может быль использовано в цифровых устройствах, работающих в р-ко.дах Фибоначчи и кодах обобщенной "золотой" пропорции.Проведенные патентные исследования по научно-технической и патентной. литературЕ показали, что не существует аналогов устройства для приведения кодов к минимальной форме. Это связано с тем, что теории р-кодов Фибоначчи и кодов обобщенной "золотой" пропор- те ции начала развиваться в последнее время.Поэтому наиболее близким по технической сущ. ности является устройство для приведения ркодов Фибоначчи к минимальной форме, сос.тоящее из и однотипных блоков свертки, при. чем первый выход 1 го блока свертки соеди. нен с первым входом (1-1)-го и вторым входом (2-р)-го блоков свертки, второй выходго блока свертки является Р м информационным26 выходом устройства и соединен с третьим вхо. дом (Р.) го и четвертым входом(с+р+1)-го . блоков свертки, управляющий вход устройства соединен с пятыми входами всех блоков свертки, шестые входы каждого блока свертки являются информационными входами устройства, кроме того, каждый блок содержит триггер, элемент И, первый и второй элементы ИЛИ, причем выход элемента И соединен с первым входом первого элемента ИЛИ и является первым выходом блока, единичный выход тригге. ра является вторым выходом блока, первый и второй входы блока соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединен с нулевым входом триггера, нулевой выход триггера соединен с первым входом элемента И, второй, третий и четвертый входы которого являются соответственно третьим, четвертым и пятым входами блока, второй вход первого элемента ИЛИ, является шестым входом блока, выход первого элемента ИЛИ соединен с единичным входом: триггера 11.Недостатком такого устройства является невозможность выполнения операции сдвига кода.Цель изобретения - расширение функциональных возможностеК заключаюцееся в возможнос.3 7ти выполнения устройством дополнительнооперации сдвига р.кодов Фибоначчи и кодовобобщенной, золотойпропорции,Поставлепгая цель достигается тем, чтоустройство для приведения р-кодов Фибоначчик минимальной форме содержащее и однотип.ных блоков свертки, причем первый выходВго блока свертки соединен с первым входомф 1).го и вторым входом фр.1).блоковсвертки, второй выход 1-го блока свертки является 1-м информационным выходом устройства и соединен с тоетьим вхопом 1-го и четвертым входом (бр+1).го блоков свертки, управляющий вход устройства соединен с пятымивходами всех блоков свертки, пятые входыкаждого блока свертки, являются информационными входами устройстаа, третий выход 1-гоблока свертки соединен с седьмым входомр)-го блока свертки, четвертый выход 1-гоблока свертки соединен с восьмым входом(Й-р)-го блока свертки, второй управляющийвход устройства соединен с девятыми входамивсех блоков свертки и еще тем, что блоксвертки содержит триггер, первый и второйэлементы И, первый и второй элементы ИЛИ,причем выход первого. элемента И соединенс первым входом первого элемента ИЛИ и является первым выходом блока, единичный вы.ход триггера соединен с первым входом второгоэлемента И и является вторым выходом блока,выход второго элемента И является третьимвыходом блока первый и второй входы блокасоединены соответственно с первым и вторымвходами второго элемента ИЛИ, выход которого соединен с нулевым входом тригге 1)а, выходпервого элемента ИЛИ, соединен с единичнымвходом триггера, нулевой выход триггера соеди.нен с первым входом первого элемента И иявляется четвертым выходом блока, второй, .третий и четвертый. входы первого элемента Иявляются соответственно третьим, четвертым ипятым входами блока, второй и третий входыпервого элемента ИЛИ являются соответственно.шестым и седьмым входами блока, второй итретий входы второго элемента И являютсясоответственно восьмым и девятым входамиблока. 79997 4 510 15 ЗО 35 40 45 50 На чертеже представлена функциональная схема устройства 1 для приведения кодов к минимальной форме, состоящего иэ шести (в общем случае из и однотипных блоков) 2 по числу разрядов р-кода Фибоначчи или кода обобщенной "золотой" пропорции (р.1), каждый из которых является одноразрядной функциональной ячейкой, соединяя которые определенным образом, можно получить устройство 1 для приведения кодов к минимальной форме необходимой разрядности. Каждый из блоков 2 содержит триггер 3, выполняющий функции элементов памяти, единичный выходкоторого является информационным выходом4 устройства 1 и вторым выходом блока 2.В состав блока 2 также входят первый эле.мент И 5, анализирующий выполнение условиясвертки, и второй элемент И 6, анализирующийвыполнение условия занесения единицы, причем нулевой выход триггера 3 связан с первымвходом первого элемента И 5 и является четвертым выходом 7 блоков. Выход первогоэлемента И 5 является первым выходом 8 блока 2, а второй, третий и четвертый входы элемента И 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 с первого по пя. тый поступают сигналы, обеспечивающие выполнение операции свертки, а на входы седьмого по девятый - занесение единиц. На первом и втором выходах формируются сигналы необходи. мые при выполнении свертки, а на третьем и четвертом - при занесении единиц.Операция сдвига выполняется на основе свойств р.кодов Фибоначчи и койов обобщен. ной "золотой"процорции.Любое натуральное число М может оыть представлено в р-коде Фибоначчи следующим образомВ=а аЯр (и)+а Я р (п.1)а,Яр (О), (1) где а, Я 0,1 р - 1, 2, 3,.У, = У(-1)+ Ур( -р.1), (0) =1.Существует множество представлений числай вида (1).Однако имеется единственная, так называе.мая, минимальная форма представления, харак.5 7 терным признаком которой является наличие не менее р нУлей после каждой единицы. Пе. реход от любой не минимальной формы представления числа М к миимальной форме осу. ществляется на основе выполнения операциг свертки разрядов.Операция свертки разрядов заключается в инвертированииго, (-1)-го (-р)-го разря дов при условии, что а;=О, а ас, = а, , =Предел отношения " " при и-+ Мр(ч-)равен постоянной величине а, которая является действительным положительным корнем уравнения.":р.Пх =х +1и называется обобщенной "золотой" . пропорцией, Используя степени обобщенной "золотой" пропорции, можно представить любое действительное число О в виде:О= Е ас.), Во втором такте единичный сигнал подаетсяна первый управляющий вход 21 устройства 1 и производится свертка кода известным образом.Пример сдвига кода в устройстве 1 прирприведен в следующей таблице.О О О Данное представление называется кодом об.общенной "золотой" пропорции децствительногочисла О.Для этих кодов так же, как и для р-кодовФибоначчи сопутствует понятие максимальнойформы, приведение к которой любой формыкода числа О осуществляется на основе опера.ции свертки,Все логические и арифметические операциивыполняются над кодами, представленными вминимальной форме,Обобщенная "золотая" пропорция обладаетследующим свойством:6 с Ф-Рар= ар + арчто вытекает из уравнения (2) и является ана.логичным соотношению Ц(п) =У (и)+У (и-Рдля р.кодов Фибоначчи.В силу общих свойств р кодов Фибоначчии кодов обобщенной "золотой" пропорциипредложенное устройство может осуществлятьоперацию свертки над обеими кодами,79997 бИсходя из того, что операция сверткикакбы перемещает единицу (8-1).го разряда в6 й разряд при наличии единицы в (-р).мразряде, операцию сдвига единицы 1-го раз.ряла можно свести к занесению единицы в(Яр.)-й разряд и последующей свертке еди.ниц этих разрядов в единицу фго разряда.При наличии единицы ъ (2.1).м разрядезанесение единицы в (Бр.) й разряд возможО но только при наличии нуля в ф+р)-м разряде.Такое условие необходимо для исключения записи единицы в ф 2 р-)-й разряд послезаписи единицы в (6 р)-й разряд.з Таким образом сдвиг кола, осугцествляетсяза два такта: занесение единиц и свертка,Рассмотрим работу устройства 1.Первый такт. Если в (8-1) м разряде запи.сана единица, то, исходя из свойства минималь.ной формы представления кодов, в (8+р).ми (У-р)-м 1 разрядах будут нули,В силу этого на первом входе второгоэлемента И б (8.1)-го блока 2, подключенномк единичному выходу 4 триггера 3 этогод блока 2 и на втором входе этого же элементаподключенном к нулевому выходу 7 триггера3 (Й+р.)-го блока 2 будут присутствоватьединичные сигналы, Если теперь на второй управляющий вход 22 устройстваподать единичныйсигнал, то на выходе второго элемента И 6 (6. )-гоблока 2 появится олиничный сигнал, которыйпройдя через первый элементЛЛИ 15 (с.р.1) гоблока 2 установит триггер 3 этого блока в единичное состояние. На этом первый такт эаканчива.3530 7 77999Введение новых элементов и связей обеспечивает расширение функциональных возможное.тей, заключающееся в том, что устройство приведения кода к минимальной форме может выполнять дополнительно функцию сдвига кода. Это позволяет сократить затраты оборудованияпри использовании предложенного устройства в различных операционных устройствах.Так как, в тех случаях, когданад кодом необходимо осуществлять операции приведе"ния к минимальной форме сдвига (например, в устройствах для уменьшения), отпадает не.обходимость в регистре сдвига. Формула изобретения 1, Устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее и блоков свертки, причем первый выход 2.го блока свертки соединен с первым входом (2.1)-го и вторым входом (2-р)-го блоков свертки, второй выход т.-гоблока свертки яв. ляется т.м информационным выходом устройства и соединен с третьим входом (8+1)-го и четвертым входом (2+р+1) -го блоков свертки, уКравляющий вход устройства соединен с пятыми входами всех блоков свертки, шестыевходы каждого, блока свертки являются информацйонными входами устройства, о т л и ч а ю щ е е с я тем; что, с целью расширения функциональных возможностей за счет обеспечения возможности выполнения операции сдвига, третий выход Й-го блока свертки соеди нен с седьмым входом (2-р) -го блока свертки, четвертый выход 2-го блока свертки соединен 7 8с восьмым входом (1-р).го блока свертки, второй управляющий входустройства соединен, . с девятыми входами всех блоков свертки.2, Устройство по п, 1, о т л и ч а ю щ е ее я тем, что блок свертки содержит триггер, первый и второй элементы И, первый и второй элементы ИЛИ, причем выход первого элемента И соединен с первым входом первого элемента ИЛИ и является первым выходом блока, единич. ный выход триггера соединен с первым входом первого элемента ИЛИ и является первым выхо. дом блока, единичный выход триггера соединен с первым входом второго элемента И и является вторым выходом блока, выход второго элемента И является третьим выходом блока, первый и второй входы блока соединены соответственно с первым и вторым входами второгоэлемента ИЛИ, выход которого соединен с нулевым входом триггера, выход первого элемента ИЛИ соединен с единичным входом триггера, нулевой выход триггера соединен с первым входом первого элемента И и является четвертым выходом блока, второй, третий и четвертый вхо. ды первого элемента И являются соответственно третьим, четвертым и пятым входами блока, вто рой и третий входы первого элемента ИЛИ явля.ются соответственно шестым и седьмым входа- мИ блока, второй и третий входы второго элемента И являются соответственно восьмым и девятым входами блока. Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР позаявке У 2386002/18-24, кл, 6 06 Р 5/ОО, 02.08.76 (про. тоти п),