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

Союз Советских Социалистических Республик,Г С 06 Р 7/00 с присоединением заявки Йо Государстаеиицй комитет СССР ио делан изобретеиий и открытийсА.П. Стахов, А.А. Козак и Н.А. Солянич нко 72) Авторы изобретенияВинницкий политехнический институт Министдрства высшего н среднего специального образованияУкраинской ССР(54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ Р-КОДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ Изобретение относится к вычисли- тельной технике и может быть использовано для приведения р-кодов Фибоначчи к минимальной формеИзвестно устройство для приведения р-кодов Фибоначчн к минимальной форме, содержащее и-блоков свертки, причем первый выход -го блока сверт.ки соединен с первым входом со (о-р) блока свертки, второй выход в-го блока свертки соединен со вторым входом (+1)-го и третьим входом (5+р +1)-го блоков свертки, второй выход каждого блока свертки является информационным выходом ус тройства, четвертый вход каждого блока свертки соединен с управляющим входом устройства, пятый вход каждого блока свертки является информационным входом устройства,(1.Недостатком известного устройства является возможность возникновения неоднозначности срабатывания (или гонокф) при приведении к минимальной форме некоторого р-кода Фибоначчи. Данная неоднозначность может возникнуть иэ-эа отклонения па,раметров элементов, входящих в каждый блок свертки. Йапример, при приведении к минимальной форме 1-код Фибоначчи числа 10 представлен в следующем видеВеса разрядов 13 8 5 3 2 1 1Номер блокасвертки 6543210Код 10 0011100,.при проведении свертки в пятый блоксвертки может возникнуть следующаяситуация. Предположим, что в результате отклонения параметров элементовчетвертого блока свертки, триггер,входящий в данный блок, сбросится внуль быстрее, чем триггер третьегоблока свертки. Тогда возникает ус ловие для свертки в четвертый блоксвертки. В результате получается слецующий код 0,110000. Затем возникаетусловие свертки для свертки в шестойблок свертки. Окончательно получится 20 код 1000000, т.е. приведенные к минимальной форме произошло неверно.В общем случае фгонки могут появиться во всех 2"- Мр(п) случаяхприведения,исходного кода.к минималь ному.Цель изобретения - повышение надежности устройства для приведенияр-кодов Фибоиаччи к минимальной форме.Поставленная цель достигается тем, ЗО что в устройстве для приведения р-ко 840880дон Фибоначчи к минимальной формевторой выход 6 -го блока свертки соединен с шестым нходом (6+1) -го блокасвертки.Кроме того,что блок свертки содержит триггер со счетным входом и элемент И, причем выход элемента И является первым выходом блока, единич"ный выход триггера является нторымвыходом блока, первый выход блокасвертки соединен с нулевым входомтриггера, нулевой выход которого сое"динен с первым входом элемента И,второй, третий и четвертый входыэлемента И являются соответственновторым, третьим и четвертым входамиблока, единичный вход триггера соединен с пятым входом блока, шестой входблока соединен со счетным входомтриггера,На фиг. 1 изображена функциональная схема устройства для р=1 и п=5; 20на фиг, 2 - функциональная схемаблока свертки.Устройство содержит пять блоков1.1-1,5 свертки. Каждый блок сверткиимеет установочные входы 2 и 3 снерт- р 5ки, информационные входы 4 и 5 свертки, упранляюций вход б свертки. Устройство имеет информационный вход7 для занесения информации о числе,Представленном и р-коде Фибоначчи.Информационные входы 4 и 5 сверткислужат для считынания информации синформационных выходов блоков 1,5 и1. Я -р) свертки, входы б всех блоков 1,1-1,5 свертки подключены к обшей шине, являющейся управляющимвходом устройства приведения р-кодов Фибоначчи к минимальной форме,на которой подается сигнал управления в случае необходимости приведения р-кода Фибоначчи к минимальной 40форме.В состав блока свертки (фиг. 2)входит триггер со счетным входом 8и элемент И 9. Единичный вход триггера 8 соединен с информационнымвходом 7, счетный вход триггера соединен с установочным входом.5 свертки,нулевой вход триггера 8 соединен сустановочным входом 3 свертки. Единичный выход триггера является информационным выходом блока свертки.Первый вход элемента И 9 соединенс нулевым выходом триггера 8, второйи третий входы .элемента И 9 соединены соответственно с информационнымивходами 4 и 5 свертки, четвертыйвход элемента И 9 соединен с управляюшим входом б свертки. Выход элемента И 9 является управляющим выходом блока свертки.Устройство работает следующим об Оразом.Предположим, что необходимо осуществить операцию принедения к минимальной форме, например, числа 5, которое представлено в 1-коде Фибоначчи отличном от минимального, следуюшим образомВес раз яда 5 3 2 1 11 код Фибоначчи 01011Двоичная информация параллельно поступает на информационные входы 7 волоков свертки и записываются в триггера 8, находящиеся до прихода информационного сигнала н нулевом состоянии. При подаче единичного управляющего сигнала на управляющий вход б этот сигнал поступает на четвертый вход элемента И 9 каждого блока сверткиОдновременно на первый, второй и третий входы элемента И 9 каждого блока свертки поступает информация о состоянии триггеров 8 1.6 - ого 1 (6-1)-ого и 1. (1-2)-ого блока свертки и производится анализ возможности проведения операции свертки. В данном случае условие свертки выполнено для 3-го разряда, На выходе элемента И 9 третьего блока свертки появится единичный сигнал, который поступает на нулевой вход 3 триггера 8 первого блока 1.1 свертки и переводит его н нулевое состояние. На единичном выходе данного триггера появится нулевой сигнал, который поступит на счетный вход 2 триггера 8 второго блока 1.2 свертки и так же переведет его в нулевое состояние. На единичномвыходе данного триггера появится нуленой сигнал, который поступит на счетный вход 2 триггера 8 третьего блока 1,3 свертки и переведет его в единичное состояние. Первая свертка окончена. В результате свертки число 01011 примет вид 01100, вследствие чего возникает условие для свертки н пятый блок 1,5 свертки, что осуществляется уже описанным образом. В результате исходная комбинация 01011 примет вид 10000, что соответствует минимальной форме представления числа 5 в 1-коде Фибоначчи. Длительность управляющего сигнала на управляющем входе б должна быть занедомо больше времени, необходимого для проведения всех нозможных сверток. По окончании управляющего сигнала свертки информацию о полученном р-коде Фибоначчи считывают с информационных выходов всех блоков 1.1-1.5 свертки. В предлагаемом устройстве для приведения р-кодов к минимальной форме неоднозначность срабатывания прй приведении любого р-кода Фибоначчи к минимальной форме не возникает . Устройство выполнено таким образом, что операция свертки производится последоватьно. При наличии условия свертки для 5-го (6-1)-го и (8-р)- го блоков свертки, вначале происходит сброс в нуль триггера (-р)-го блока свертки. На его информационном выходе появляется нулевой пот.нциал,который поступает на счетный вход триггера (-1)-го блока свертки и переводит его в нулевое состояние, что соответственно приводит к записи единицы в триггер 1-го блока свертки. Этим и достигается положительный эффект.формула изобретения1. Устройство для приведения р-ко,цов фибоначчи к минимальной Форме, содержащее и-блоков свертки, причем, первый выход С-го блока свертки сое, динен с первым входом (Й-р) блока свертки, второй выход 0-го блока свертки соединен со вторым входом (С+1)-го и третьим входом (+р+1)-го блоков свертки, второй выход каждого блока свертки является информационным выходом устройства, четвертый вход каждого блока свертки соединен с управляющим входом устройства, пятый вход каждого блока свертки является информационным входом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения надежности устройства, второй выхол -гоблока свертки соединен с шестымвходом (6+1)-го блока свертки.2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок сзертнисодержит триггер со счетным входоми элемент И, причем выход элементаИ является первым выходом блока,единичный выход триггера являетсявторым выходом блока, первый входблока свертки соединен ,с нулевымвходом триггера, нулевой выход которого соединен с первым входом элемента И, второй, третий и четвертыйвходы элемента И являются соответственно вторым, третьим и четвертым5 входами блока, единичный вход триггера соединен с пятым входом блока,шестой вход блока соединен со счетным входом триггера.Источники информации,70 принятые вовнимание при .экспертизе1. Авторское свидетельство СССРпо заявке Р 2386002/24,кл. С 06 Р 7/00, 2.08.76.840880 иг. Составитель И.заренко , Техред В, Бабур ов РедакторКорректор В. Бутяга Тираа 745 П ВНИИПИ Государственного комитета ССС ф по делам изобретениЯ и открытий 35, Москва, а, Раушская наб., д.