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

5"л 1 м"," "н,ы 1Е А Соеэ СоветскнкСфциалистическнкРеспублик оо 662930 К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(51)М. Кл.2 О 06 Р 5/00 с присоединением заявки ЙоГосударствеииыйкомитет СССР ио делам иэобретеиий и открытий(54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КОДОВ ФИБОНАЧЧИ КМИНИМАЛЬНОЙ ФОРМЕ 10 н. 1ИЗобретеиие. относится к области вычислительной, аналого-цифровой ицифроаналоГовой техники и может быть использовано для приведения р-кодов к минимальной форме,Под р-кодами Фибоначчи понимается представление любого натурального числа О в виде суммы где р - заданное натуральное число, , определянщее номер р-кода Фибоначчи; п =разность р-кода Фибоначчи;15 ат- двоичная цифра (О или 1) в 3 -ом разряде р-кода Фибоначчи;с(р ( Й) " вес 2-го раз ряда р-кода Фибоначчи (р-число Фибоначчи), задаваемый следующим рекуррентным соотношением:Одри 040 ,е)- .рис.о6-Ц+су 6-рири ОО,Подминимальной формой р-кода Фибоначчи понимается такой р-код Фибоначчи, в котором после каждого единичного разряда следует не менее 2р нулевых разрядов. При выполнениипреобразованйй информации в цйфровой(ЦАП) преобразователях над мнимальными формами р-кодов Фибоначчи всеинформацйонные операции приобретаютсвойство естественного самоконтроля,что ведет кповышению информационнойнадежности ЦВЙ, ЭЦП и ЦАП.Новой операцией над кодами в ЦВМ,АцП и цАП, работаюШих в р-кодах Фибоначчи являетси операция приведенияр-кодов Фибоначчи к минимальной форме.Устройства для приведения р-кодовФибоначчи к минимальной форме неизвестны,Целью изобретения является созданиеустройства для приведения р-кодов фибоначчи к минимальной форме.Это достигается тем, что устройство содержит в однотипных блоковсвертки, причем первый вход 0-го блока свертки соединен с первым входом3дом (2+р+1) блоков свертки, управляющий вход устройства соединен с пятйми входами всех блоков свертки, шестые входы кажДого блока свертки являются информационными входами устройства.Кроме того блок свертки содержит триггер, элемент И, первый и второй элемент ИЛИ, причем выход элемента И соединен с первым входом первого элемента ИЛИ и является первым выходом блока, единичный выход триггера является вторым выходом блока, первый и второй входы блока соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединен с нулевым входом тригге ра, нулевой выход триггера соединен с первым входом элемента И, второй, третий и четвертый входы которого являются соответственно третьим, чет-вертым и пятым входами блока, второй 20 вход первого элемента ИЛИ является шестымвходом блока, выход первого элемейта ИЛИ соединен с единичным входом триггера.На фиг.1 изображено устройство 25 для приведения 1-кодов Фибоначчи к минимальной формеУстройство содержит и однотипицх блоков 1 свертки, где и=5 и означает разрядность р-кода Фибоначчи. Первыйвыход 2 Р-го блока 1 соединен с пер вым входом 3 (Г) и вторым входом 4 (Г-1) блока 1. Второй выход 5 Р-го блока 1 (-3) является 0-ым информациониым выходом устройства и соедийен 38 с третьим входом б (.Х+1) и четвертым входом 7 (Р+1+1) блоков 1, Пятые входы 8 каждого блока 1 объединены и являются управляющим входом 9 устрой-" ства. Шестые входы 10 каждого блоха 1 являются информационными входами устройства.Блок 1. содержит триггер 11, эле- . меЮг 12 И, первый элемент 13 ЙЛИ ивторой элемент 14 ИЛИ. Выход элемен- та 12 И соединен с первым входом эле мента 13 ИЛИ и является первым выхо" дом 2 блока 1, Единичный выход триг- . гера 11 является вторым выходом 5 блока 1. Первый вход 3 и второй вход 4 блока 1 соединены соответственно50 с первым и вторым входами элемента 14 ИЛИ, выход кдторого соединен с нулев 1 ым входом триггера 11. Нулевой выход триггера 11 соединен с первым входом элемента 12 И, второй, третий и чет вертый входы которого являются соответственно входом 7, входом б и входом 8 устройства. Второйвход элемен.- та 13 ИЛИ является входом 10 блока 1, а выход элемента 13 ИЛИ соединен с единичным входом триггера 11. 662930 На фиг.2 изображено устройстводля приведения 2-кода Фибоначчи кминимальной форме. Устройство содержит п блоков 1свертки (п=5), Здесь каждый блок 1имеет также четвертый нулевой информационный выод 15, седьмой вход 16,пятый выход 17 (2-1) восьмых входов181 - 181, девятый вход 19,(2+1)десятых входов 201 - 202, (2+1)одинадцатых входов 211 - 21+, шестой выход 22. Девятые выходы 19 каждого блока 1 объединены и являютсявторым управляющим входом 23 устройства. Пятый выход 17 Р-го блока 1соединен со входом 21 (0-2-3+1)блока 1, Шестой выход 22 Е-го блока 1соединен со входом 18; (8-3.) блока 1.Четвертый выход 15 блока 1 соединенс седьмым входом 16 (,1-1) блока 1 исо входом 20 э (Р+2+з) блока 1, причем 3=в=1, 2 2+1, 1= 1, 2,..,2+1. Блок 1 в этом случае содержиттакже второй элемент 24 И и элемент25 НЕ, вход которого соединен с выходом элвмента 12 И, а выход являетсявыходом 22 блока 1 свертки. Нулевойвыход триггера.11 является четвертымвходом 15 блока 1; (р) входов элемента 12 И, начиная с пятого, являют"ся восьмыми входами 181-18 1 блока 1. Первый вход второго элемента24 И соединен с единичным выходомтриггера 11. Второй и третий входыэлемента 24 И являются входом 19и входом 16 соответственно блока 1,а оставшиеся (2+1) входов второгоэлемента 24 И являются десятыми входами 201 -20+, блока 1. Выход второго элемента 24 И соединен с треТьимвходом второго элемента 14 ИЛИ и является пятым выходом 17 блока 1.Устройство для приведения р-кодовФибоначчи к минимальной форме ра. ботает следующим образом.На фиг.1 представлена схема устройства для р 1 и п=5. Двоичнаяинформация поступает на входы 10 устройства и через элементы 13 ИЛИ записывается в триггеры 11 блоков 1свертки, находящиеся, до приходаинформации на входы 10, в нулевомсостоянии. При подаче единичногосИгнала на управляющий вход 9 устройства, этот сигнал поступает наодин из входов элемента 12 И всехблоков 1. Элемент 12 И, будучи связанным с триггерами 11 блоков 1 0-го,(М) и (Р-1) так,как описано выше,анализирует состояние триггеров 11этих блоков, На всех входах элемента 12 И будет присутствовать единичный сигнал, т.е. выполнится условиесвертки, если триггер 11 -го блока1 находится в нулевом состоянии, а б 0 триггера 11 (1 1) и (2-1-1) блоков 1находятся в единичном состоянии и науправляющий вход 9 поступает единичный сигнал. В этом случае на выходеэлемента 12 И 8-го блока 1 вырабатывается единичный сигнал, который поФормула изобретения 1. Устройство для приведенияр-кодов Фибоначчи к минимальной форме, о т л и ч а ю щ е. е с я тем, что оно содержит и однотипных блоков свертки, причем первый выход ;-го блока свертки соединен с первым входом (Ы) и . вторым входом (2"р) блоков свертки, второй выход 2-го блока свертки является 2-ым информационйым выходом устройства и соединен с третьим вхо" дом (2+1) и четвартым входом (Р+р+1) 5662ступает через элемент 13 ИЛИ на триггер 11 этой ячейки и устанавливаетего в единичное состояние. Одновременно этот же сигнал с выхода 2 8-гоблока 1 свертки подается на вход3 (2-1) и вход 4 ( Ь 1-1) блоков 1 ичерез элементы 14 ИЛИ записывает втриггеры 11.этих блоков нулевые сигналы, Например в устройство записаночисло 5, представленное в 1-коде Фибоначчи, отличном от нормальногоВес раври а ". 5 5 211 . 1 О1-код Фибоначчи 0 1 0 1 1Условие Свертки выполняется приподаче единичного сигнала,на управ"ляющий вход 9 устройства для блока 1с номером 8=3. Элемент 12 И этогоблока вырабатывает единичный сигнал,который записывает в триггер 11 блока 1 с номером 1 3 едйничный сигнал,а в триггеры 11 блоков 1 с номерами.Т=2 и 21 - нулевые сигналы. В результате число 0 1 0.1 1 принимает внл 201 1 0 О, вслелствне чего выполняется условие свертки для блока 1 с номером 2 5После проведения второйсвертки число 01011 принимает вйд10000, что соответствует минимальнойформе числа 5, в 1-коде Фибоначчи.Длительность управляющего сигнала,подаваемого на вход 9 устройства,должна быть заведомо больше времени,Необходимого для проведения всех воэможных сверток, По окончании управляющего сигнала свертки информация:считывается с информационных выходов 5устройства параллельно.Операция свертки для чисел в 2-коде. Фибоначчи осуществляется вышеописанным способом в устройстве, изобра"женном на фиг,2,На фиг.2 изображено устройство дляприведения 2-кода Фибоначчи к мини-мальной форме, реализующее также операцию развертки в тех случаях, когдапроведение всех возможных сверток необеспечивает получения минимальнойформы 2-кода фибоначчи. В этом случае 45устройство, изображенное на фиг,2,реализует поочередно операции свертоки разверток. Элемент 24.И блока 1 анализирует состояние триггеров 11 (2+1),Р и от (Р) до (Р-2) блоков 1.При наличии в триггерах 11 2+1 и от(Р) до (1-2-2) блоков 1 нулевых сигналов, а в триггере 11 1-го блока 1единичного сигнала, условие сверткивыполнено и при подаче на второй управляющий вход 23 единичного сигнала 55на выходе элемента 24 И вырабатывается сигнал совпаденияЭтот сигнал пе реводит триггеры 11 Р и от (0-2) до(Е-2) блоков 1 в инверсное состоянйе. После проведения всех возможных 60разверток проводятся все возможныесвертки. Во время проведения свертокэлемент 25 И каждой ячейки вырабатывает сигнал запрета свертки, которыйустраняет неоднозначность приведения 930 6числа к минимальной форме, Например, в устройство записано число 3, пред-ставленное в 2-коде.фибоначчи, отличном от нормального.Вес аз я а 3 2 112-код Фибоначчи О 1 1 О ОПри подаче единйчного" управляющего сигнала на вход 9 устройства условие свертки не выполняется ни для одного блока 1, хотя код представлен в форме, отличной от минимальной. Подается единичный сигнал на вход 23. Условие: развертки выполняется для блокасвертки с номером К=З, Элемент 24 И этого блока вырабатывает единичный сигнал, который записывает в триггер 11 блока 1 с номером 013 нулевой сигнал, а в триггеры с номерами от (8-2) до (М-2) - единичные сигналы. .В данном случае единичный сигнал запишется только в триггеры 11 блока 1 с номерами 8=1 и 1=2, так как остальные отсутствуют. В результате проведения развертки"код 0110 Д принимает вид 00111.Дальнейшие развертки невозможны. Подается опять единичный сигнал на вход 9 устройства. Условие свертки выполняется для блока 1 свертки с номером 1:О 3. Код 014 принимает вид 01010. Теперь условие свертки выполняется для блоков 1 с номерами 0=5 и 0=3. Но блок свертки вырабатывает сигнал запрета свертки, который подается на вход 184 блока 1 свертки с номером 2-"3 и свертка в него эапрецена. Код 1010 принимает вид 10000, что соотвес вует минимальной форме, числа в 2-коде Фибоначчи. Использование р-кодов Фибоначчи в цифровой вычислйтельной технике позволяет создавать самоконтролирующиеся узлы вычислительных машин.устройство для приведения р-кодов Фибоначчи к минимальной форме используется при проведенииоперации суммирования для приведения к минимальной форЪе промежуточной суммы,устройство можно использовать как многбвходовой счетчик импульсов в ркодах Фибоначчи, при этом входная информация подается на р младших разрядов/662930 8 блоков свертки, управляюций вход йервый и второй входы блока соединены устройства соединен с пятыми входами соответственно с первым и вторым вховсех блоков"свертки, шестые входы каж- дами второго элемента ИЛИ, выход кодого блока свертки являются инФорма- торого соединен с нулевым входом ционными входами устройства. " " "триггера, нулевой выход триггера сое 2, Устройство по п.1, о- т л и ч а- динен с первым входом элемента И, ю щ е е с я тем, что блок свертки 5 второй, третий и четвертый входы ко содержит триггер, элемент И, первый и торого являются соответственно тревторой элемент ИЛИ, причем выход эле- тьим, четвертым и пятым входами блока, мента И соединен с первым входом пер- второй вход первого элемента ИЛИ яввого элемента ИЛИ и является первым ляется шестым входом блока, выход первыходом блока, единичный выход триг вого элемента ИЛИ соединен с единичным гера является вторым выходом блокавходом триггера..Каменская Техред О,Андрейко Коррект Стец Реда одписноеСР 4/5 ивл ППП Патент, г.ужгород, ул.Проектная Заказ 2701/50 ЦНИИПИ по дел 113035, М