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

 

Союз Советских

Соцналистичесиих

Республик

ОПИСАНИЕ >84088

+ г .(д 4Ф

4» 5 г

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (63) Дополнительное к ввт. сеид-ву (22) Заявлено 310178 (21) 2576357/18-24 (51)М. КЛ. с присоединением заявки Но

G 06 F 7/00

Государстаеиимй комитет

ССС Р ио делан изобретеиий и открытий (23) Приоритет

Опубликовано 2306.816юллетень 89 23

Дата опубликования описания 230681 (ЗЗРДК 681.3 (088.8) с

А.П. Стахов, А.А. Козак и Н.A. Солянич нко

l (72) Авторы изобретения t

Винницкий политехнический институт Министдрства. - =-"высшего н среднего специального образования

Украинской CCP (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ Р-КОДОВ ФИБОНАЧЧИ

К МИНИМАЛЬНОЙ ФОРМЕ

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

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

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

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

Веса разрядов 13 8 5 3 2 1 1

Номер блока свертки 6 5 4 3 2 1 0

Код 10 0011100,. прн проведении свертки .в пятый блок свертки может возникнуть следующая ситуация. Предположим, что в реэульlaTe отклонения параметров элементов четвертого блока свертки, триггер, входящий в данный блок, сбросится в нуль быстрее, чем триггер третьего блока свертки. Тогда возникает условие для свертки в четвертый блок свертки. В результате получается сле» цующий код 0,110000. Затем возникает условие свертки для свертки в шестой блок свертки. Окончательно получится код 1000000, т.е. приведенные к минимальной форме произошло неверно.

В общем случае гонки могут появиться во всех 2"- Мр{п) случаях приведения, исходного кода-к минималь25 иомуе

Ф

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

Поставленная цель достигается тем, ЗО что в устройстве для приведения р-ко840880 дов Фибоначчи к минимальной форме второй выход С -ro блока свертки соединен с шестым входом (6+1)-ro блока свертки.

Кроме того,что блок свертки содер. жит триггер со счетным входом и эле- 5 мент И, причем выход элемента И является первым выходом блока, единичный выход триггера является вторым выходом блока, первый выход блока свертки соединен с нулевым входом триггера, нулевой выход которого сое" динен с первым входом элемента И, второй, третий и четвертый входы элемента И являются соответственно вторым, третьим и четвертым входами блока, единичный вход триггера соединен с пятым входом блока, шестой вход блока соединен со счетным входом триггера.

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

Устройство содержит пять блоков

1 .1-1.5 свертки. Каждый блок свертки имеет установочные входы 2 и 3 сверт- р5 ки, информационные входы 4 и 5 свертки, управляюций вход 6 свертки. Устройство имеет информационный вход

7 для занесения информации о числе, представленном в р-коде Фибоначчи.

Информационные входы 4 и 5 свертки служат для считывания информации с информационных выходов блоков 1.3 и

1. (6 -р-1) свертки, входы 6 всех блоков 1.1-1.5 свертки подключены к обшей шине, являющейся управляющим входом устройства приведения р-кодов Фибоначчи к минимальной форме, на которой подается сигнал управления в случае необходимости приведения р-кода Фибоначчи к минимальной 40 форме.

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

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

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

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

Вес раз яда 5 3 2 1 1

1 код Фибоначчи 0 1 0 1 1

Двоичная информация параллельно поступает на информационные входы 7 ,блоков свертки и записываются в триггера 8, находящиеся до прихода информационного сигнала в нулевом состоянии. При подаче единичного управляющего сигнала на управляющий вход 6 этот сигнал поступает на четвертый вход элемента И 9 каждого блока свертки. Одновременно на первый, второй и третий входы элемента И 9 каждого блока свертки поступает информация о состоянии триггеров 8 1. —

oro 1 (8-1)-oro и 1. (6-2)-oro блока свертки и производится анализ возможности проведения операции свертки.

В данном случае условие свертки выполнено для 3-го разряда. На выходе элемента И 9 третьего блока свертки появится единичный сигнал, который поступает на нулевой вход 3 триггера

8 первого блока 1.1 свертки и переводит его в нулевое состояние. На единичном выходе данного триггера появится нулевой сигнал, который поступит на счетный вход 2 триггера 8 второго блока 1.2 свертки и так же переведет его в нулевое состояние.

На единичном выходе данного триггера появится нулевой сигнал, который поступит на счетный вход 2 триггера 8 третьего блока 1.3 свертки и переведет его в единичное состояние. Первая свертка окончена. В результате свертки число 01011 примет вид 01100, вследствие чего возникает условие для свертки в пятый блок 1.5 свертки, что осуществляется уже описанным образом. В результате исходная комбинация 01011 примет вид 10000, что соответствует минимальной форме представления числа 5 в 1-коде Фибоначчи.

Длительность управляющего сигнала на управляющем входе 6 должна быть заведомо больше времени, необходимого для проведения всех возможных сверток.

По окончании управляющего сигнала свертки информацию о полученном р-коде Фибоначчи считывают с информационных выходов всех блоков 1.1-1.5 свертки.

В предлагаемом устройстве для пРиведения р-кодов к минимальной форме неоднозначность срабатывания прй

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

Этим и достигается положительный эффект.

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

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

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

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

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

Источники информации, Щ принятые во внимание при .экспертизе

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

840880

Фиг. 1

Составитель И. Сигалов

Техред В, Вабурка Корректор В. Бутяга

Редактор В. Лазаренко

Тирам 745 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретениЯ и открытий

113035, Москва, X-35, Раушская наб., д. 4/5

Заказ 4766/71

Филиал ПИП Патент, r. Уигород, ул. Проектная, 4