Устройство для приведения р-кодов фибоначчи к минимальной форме Советский патент 1980 года по МПК H03M13/23 

тл выполнения устройством дополнительно операции сдвига р-кодов Фибоначчи и кодов обобщенной .золотой пропорции. Поставлегптя цель достигается тем, что усгройство для приведения р-кодов Фибоначчи к 1инимальной форме содержащее-, п однотипных блоков бвертки, причем первый выход t-ro блока -свертки соединен с первым входом ()-го и вторым входом (f-p-1)-блоков свертки, второй выход 1-го блока свертки является 1-м информационшлм выходом устройст ва и соединен с третьим вхопом 1-гр и четвертым входом (f+p+l)-го блоков свертки, управ ляющий вход устройства соединен с пятыми входами всех блоков свертки,- пятые входы каждого блока свертки, являются информацион ными входами устройст;за, третий выход 1-го блока свертки соединен с седьмым входом (-р)-го блока сЕертки, четвертый выход 1-го блока свёртки соединен с восьмым входом ,(-р)-го блока свертки, второй управляющий вход устройства соединен с девятыми входами всех блоков свертки и еще тем, что блок свертки содержит триггер, первый и второй элементы И, первый и второй элементы ИЛИ, причем выход первого, элемента И соединен с первым входом первого элемента ИЛИ и является первым выходом блока, единичный выход триггера соединен с первь1м входом второг элемента И и является вторым выходом блока выход второго элемента И является третьим выходом блока первый и второй входы блока соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которо го соединен с нулевым входом триггера, выход первого элемента ИЛИ, соединен с единичным входом триггера, нулевой выход триггера соеди нен с первым входом первого элемента И и является четвертым выходом блока, второй, . третий и четвертый. входы первого элемента И являются соответственно третьим, четвертым и пятым входами блока, второй и третий входы Первого элемента ИЛИ являются соответственно ; шестым и седьмым входами блока, второй и третий входы второго элемента И являются cpOTBeTCTBeifflo восьмым и девятым входами блока. На чертеже представлена функциональная схема устройства 1 для приведения кодов к минимальной форме, состоящего из шести (в общем случае из п однотипных блоков) 2 по числу разрядов р-кода Фибоначчи или кода обобщенной золотой пропорции (р-1), каждый из которых является одноразрядной функциональной ячейкой, соединяя которые определенным образом, можно получить устро ство 1 для приведения кодов к минимальной форме необходимой разрядности. Каждый из блоков 2 содержит триггер 3, выполняющий 74 функции элементов памяти, единичный выход . которого является информационным выходом 4 устройства 1 и вторым выходом блока 2. В состав блока 2 также входят первый элемент И 5, анализирующий вьшолнение условия свертки, и второй элемент И 6, анализирующий выполнение условия занесения единицы, причем нулевой выход триггера 3 связан с первым входом первого элемента И 5 и является четвертым выходом 7 блоков- Выход первого элемента И 5 является первым выходом 8 блока 2, а второй, третий и четвертый входы элемента И 5 являются соответственно третьим входом 9, четвертым входом 10 и пятьш входом 11 блока 2. Единичный выход триггера 3 соединен с первым входом элемента И 6, выхОд которого является третьим выходом 12 блока 2. Второй и третий входы .элемента И 6 являются соответственно восьмым входом 13 и девятым входом 14 блока 2. Каждый из блоков 2 содержит также первый элемент ИЛИ 15, выход которого соединен с единичным входом триггера 3, а первый вход элемента ИЛИ 15 соединен с выходом первого элемента И 5. Второй вход элемента ИЛИ 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-l)+...+aol/p (0), (1) где а. (-{0,1} р S 1, 2, 3.... Ур((М), . i/p(0) l. Существует шожество представлений числа N вида (1). Однако имеется единственная, так называемая, минимальная форма представления, характерным признаком которой является наличие не менее р нулей после каждой едишщы. Переход от любой не минимальной формы представления числа N к минимальной форме осуществляется на основе выполнения операции сверткн разрядов. Операютя свертки разрядов заключается в инвертировании i-ro, (i-I)-ro (i-p-l)-ro разрядов при условии, что , а , at-,,1 Предел отношения при п- Vpfn-f) равен постоянной величине Ор, которая, является действительным положительным корнем уравнения:: p4l, X X + 1 и назьтается обобщенной золотой пропорзолотойвдей. Используя степени обобщенной пропорции, можно представить любое действительное число D в виде: f Данное представле1ше назьтается кодом об общенной золотой пропор1щи действительног числа D . Для зтих кодов так же, как и для р-кодо 1ибоначчи сопутствует понятие максимальной формы, приведение к которой любой формы кода числа б осуществляется на основе операции Свертки. Все логические и арифметические операции выполняются над кодами, представленныли в минимальной форме. Обобщенная золотая пропорция обладает следующим свойством: в (Хр а% + что вытекает из уравнения (2) и является ана логичным соотнощению у р (п) Ур (п-1) +Ур (п-рдля р-кодов Фибоначчи. В силу общих свойств р-кодов Фибоначчи и кодов обобщенной золотой пропорции предложенное устройство может осуществлять операцию свертки над обеими кодами. 76 I Исходя из того, что операция свертки как бы перемещает единицу (-1)-го разряда в й разряд при наличии единицы в (рг1)-м разряде, операцию сдвига единицы 1-го разряда можно свести к занесению единицы в (-р-1)-й разряд и последующей свертке единиц зтих разрядов в единицу разряда. При наличии единицы-в (Е-1)-м разряде занесение еданицы в (р-1)-й разряд возможно только при наличии нуля в (й-р-1)-м разряде. Такое условие необходамо для исключения записи единицы в (2р-1)-й разряд после загаси единицы в (б-р-1)-й разряд. Таким образом сдвиг кода, осуществляется за два такта: занесение еди1сиц и свертка. Рассмотрим работу устройства 1. Первый такт. Если в (1)-м разряде записана единица, то, исходя из свойства минимальной формы представления кодов, в (&-р-1)-м и (f-p-l)-Mi разрядах будут нули. В силу этого на первом входе второго злемекта И 6 (f-l)-ro блока 2, подключенном к единичному выходу 4 триггера 3 зтого блока 2 и на втором входе этого же элемента подключенном к нулевому выходу 7 триггера 3 {f+p-l)-ro блока 2 будут присутствовать еданичные сигналы. Если теперь на второй управляющий вход 22 устройства 1 подать единичный сигнал, то на выходе второго элемента Мб (1 )-го блока 2 появится одаш1чный сигнал, который . , . пройдя через первый элемент МЛН 15 (p-l)-ro блока 2 установит триггер 3 этого блока в единичное состояние. На этом первый такт заканчивается. Во втором такте единичный сигнал подается на первый управляющий вход 21 устройства 1 и производится свертка кода известным образом. Пример сдвига кода в устройстве 1 при р-1 приведен в следующей таблице.

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

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

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

.Г. Устройство для приведения р-кодов Фибоначад к минимальной форме, содержащее п блоков свертки, причем первый Шход В-го блока свертки соединен с первым входом (2-))-го и вторым входом (-р-1)-го блоков свёртки, второй выход -го блока свертки является f-M информационным выходом устройства и соединен с третьим входом (В+1)-го и четвертым входом (Б+р+1)-го блоков свертки, управляющий вход устройства соединен-с roiTbiNm входами всех блоков свертки, шестые вхоДь каждого , блока свертки являются информаци6йн1 лт входами устройства, от ли чающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности выполнения операции сдвига, третий выход 2-го блока свертки соеди нен с седьмым входом (-р) -го блока свертки четвертый выход -го блока свертки соединен

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

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

Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР позаявке N 2386002/18-24, кл. G 06 F 5/00,02.08.76 (прототип).