Устройство для приведения р-кодов фибоначчиК МиНиМАльНОй фОРМЕ Советский патент 1981 года по МПК G06F7/00 

1

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

Известно устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее п-блоков свертки, причем первый выЗсод С-го блока сверки соединен с первым входом со (в-р-1) блока свертки, второй выход 6-го блока свертки соединен со вторьа-1 входом (8+1)-го и третьим входом (+р +1)-го блоков свертки, второй выход каждого блока свертки является информационным выходом устройства, четвертый вход каждого блока свертки соединен с управляющим входом устройства, пятый вход каждого блока свертки является информационным входом устройства 1J.

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

10 представлен в слеФибоначчи числа дующем виде

3211 13 В 5

Веса разрядов

Номер блока

3210

свертки 6 54 1100,

Код 10 001 при проведении свертки -в пятый блок свертки может возникнуть следующая ситуация. Предположим, что в резуль0тате отклонения параметров элементов четвертого блока свертки, триггер, входящий в данный блок, сбросится в нуль быстрее, чем триггер третьего блока свертки. Тогда возникает ус5ловие для свертки в четвертый блок свертки. В результате получается следующий код ОД 10000, Затем возникает условие свертки для свертки в шестой блок свертки. Окончательно получится

0 код 1000000, т.е. приведенные к минимальной форме произошло неверно. В общем случае гонки могут появиться во всех .(n) случаях приведения 1исходного кода к минималь5. иому,«

Цель изобретения - повышение надежности устройства для приведения р-кодов Фибоначчи к минимальной форме.

Поставленная цель достигается тем, 0 что в устройстве для приведения р-колов Фибоначчи к минимальной форме второй выход в-го блока свертки соединен с шестым входом (€+1)-го блока свертки. Кроме того,что блок свертки содержит триггер со счетным входом и элемент И, причем выход элемента И является первым выходом блока, единичный выход триггера является вторым выходом блока, первый выход блока свертки соединен с нулевым входом триггера, нулевой выход которого соединен с первым входом элемента И, вторюй, третий и четвертый входы элемента И являются соответственно вторым, третьим и четвертым входами блока, единичный вход Тригге{)а соединен с пятым входом блока, шестой вход блока соединен со счетным входом триггера.

На фиг. 1 изображена функциональная схема устройства для и на фиг. 2 - функциональная схема блока свертки.

Устройство содержит пять блоков 1.1-1.5 свертки. Каждый блок свертки имеет установочные входы 2 и 3 свертки, информационные входы 4 и 5 свертки, управляющий вход б свертки. Устройство имеет информационный вход 7 для занесения информации о числе, представленном в р-коде Фибоначчи. Информационные входы 4 и 5 свертки служат для считывания информации с информационных выходов блоков 1.8 и 1. (6-р-1) свертки,входы б всех блоков 1.1-1.5 свертки подключены к общей шине, являющейся управляющим входом устройства приведения р-кодов Фибоначчи к минимальной форме, на которой подается сигнал управления в случае необходимости приведения р-кода Фибоначчи к минимальной форме.

В состав блока свертки (фиг. 2) входит триггер со счетным входом 8 и элемент И 9. Единичный вход триггера 8 соединен с информационным входом 7, счетный вход триггера соединен с установочным входом.5 свертк нулевой вход триггера 8 соединен с установочным входом 3 свертки. Единичный выход триггера является информационным выходсял блока свертки. Первый вход элемента И 9 соединен с нулевым выходом триггера 8, второй и третий входы элемента И 9 соединены соответственно с информационными входами 4 и 5 свертки, четвертый вход элемента И 9 соединен с управляющим входом б свертки. Выход элемента И 9 является управляющим выходом блока свертки.

Устройство работает следующим образом.

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

отличном от минимального, следующим образом

Вес разряда53211

1 код Фибоначчи 01011 Двоичная информация параллельно поступает на информационные входы 7 Элоков свертки и записываются в триггера 8, находящиеся до прихода информационного сигнала в нулевом состоянии. При подаче единичного управляющего сигнала на управляющий вход б этот сигнал поступает на четвертый вход элемента И 9 каждого блка свертки. Одновременно на первый, второй и третий входы элемента И 9 каждого блока свертки поступает информация о состоянии триггеров 8 1.б ого 1 (g-l)-oro и 1. (С-2)-ого блока свертки и производится анализ возможности проведения операции свертки В данном случае условие свертки выполнено для 3-го разряда. На выходе элемента И 9 третьего блока свертки появится единичный сигнал, который поступает на нулевой вход 3 триггера 8 первого блока 1.1 свертки и переводит его в нулевое состояние. На единичном выходе данного триггера появится нулевой сигнал, который поступит на счетный вход 2 триггера 8 второго блока 1.2 свертки и так же переведет его в нулевое состояние. На единичном выхЬде данного триггера появится нулевой сигнал, который поступит на счетный вход 2 триггера 8 третьего блока 1.3 свертки и переведет его в единичное состояние. Первая свертка окончена. В результате свертки число 01011 примет вид 01100 вс 1едствие чего возникает условие для свертки в пятый блок 1.5 свертки, что осуществляется уже описанным образом. В результате исходная комбинация 01011 примет вид 10000, что соответствует минимальной форме представления числа 5 в 1-коде Фибоначчи Длительность управляющего сигнала на управляющем входе 6 должна быть заведомо больше времени, необходимого для проведения всех возможных сверток По окончании управляющего сигнала свертки информацию о полученном р-коде Фибоначчи считывают с информационных выходов всех блоков 1.1-1.5 свертки.

в предлагаемом устройстве для приведения р-кодов к минимальной форме неоднозначность срабатывания при приведении любого р-кода Фибоначчи к минимальной форме не возникает . Устройство выполнено таким образом, что операция свертки производится последовательно. При наличии условия свертки для-го (6-1)-го и {1-р-1)го блоков свертки, вначале происходит сброс в нуль триггера (t-p-l)-ro блока свертки. На его информационном выходе появляется нулевой .

который поступает насчетный вход триггера (g-l)-ro блока свертки и переводит его в нулевое состояние, что соответственно приводит к записи единицы в триггер -го блока свертки. Этим и достигается положительный эффект.

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

i. Устройство для приведения р-коДов Фибоначчи к минимальной форме, содержащее п-блок6в свертки, причем первый выход t-ro блока свертки соединен с первым входом (-р-1) блока свертки, второй выход Р-го блока свертки соединен со вторым входом

(t+l)-ro и третьим входом (С+р+1)-го блоков свертки, второй выход каждого блока свертки является информационным выходом устройства, четвертый вход каждого блока свертки соединен с управляющим входом устройства, пятый вход каждого блока свертки является информационным входом устройства, отличающееся Гем, что, с целью повышения надежности устройства, второй выход f-ro блока свертки соединен с шестым входом ()-ro блока свертки.

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

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

5 входами блока, единичный вход триггера соединен с пятым входом блока, шестой вход блока соединен со счетным входом триггера.

Источники информации,

0 принятые во, вниманиеПри экспертизе

1. Авторское свидетельство СССР по заявке № 2386002/24, кл. G 06 F 7/00, 2.08.76.

7 k Г rik