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

1547074 а формирования кода, блоки свертки,Каждый иэ которых содержит элементыИЛИ, элементы И, триггер. Введениедополнительных связей и изменениефункциональной схемы блока сверткиобусловило изменение алгоритма рабоИзобретение относится к вычислиельной технике и может быть испольовано для приведения р-кодов Фибоаччи к минимальной форме.Целью изобретения является повыщенке быстродействия.На. фиг. 1 изображена схема устройства для приведения р-кодов Фибояаччи к минимальной форме; на фнг.2ок-схема блока свертки; на фиг.З - 20ременные диаграммы работы для конкретного примера.Устройство (фиг. 1) содержит груп 1 у информационных входов 1 устройстФа тактовый вход 2 устройства, и блоков 3 свертки, каждый из которых имеет шестой 4, пятый 5, третий б, четвертый 7, седьмой 8, первый 9 и торой 10 входы, второй 11, третий 12 и первый 13 выходы, группу ин формационных выходов 14 устройствавыход 15 признака конца формирования кода устройства.Блок 3 свертки (фиг, 2) содержит йервый и второй элементы ИЛИ 16 и 17, второй и первый элементы И 18 и 19:и триггер 20.Устройство (фиг. 1) работает слейуюшим образом.Перед началом работы все триггеры 40 20 блоков 3 свертки устанавливаются в нулевое состояние подачей сигнала по входу, объединяющему все входы установки в нули (не показаны).Сиг-, налы, поступающие по,информационным 45 входам 1 устройства, устанавливают. триггеры 20 в состояния, соответствующие поданным разрядам исходного кода,Рассмотрим случайр когда миними зируется 1-код Фибоначчи для п=.-б: Номер блока 3 свертки 654321 Вес разряда 853211 1-Код Фибоначчи 010101 Временные диаграммы работы устройства для этого случая приведены на фиг3.При подаче кода на установочныевходы триггеров 20 триггеры Т 1, ТЗ ты устройства таким образом, что длительность формирования минимальногокода стала зависеть от числа фактически выполняемых сверток, т.еувеличилось среднее быстродействие устройства. 1 з.п. ф-лы, 3 ил. и Т 5 устанавливаются в состояние "1",а триггеры Т 2, Т 4 и Тб - в состояние(1"1)-го и (1-2)-го разрядов, и фор"мирует а выходе признак свертки Х =0 й0 е-Ч е-гЕсли Х= 1, то над соответствующими разрядами кода Фибоначчи должна быть выполнена операция свертки.Для рассматриваемого случая признак сверт. - ки, равный 1, будет вырабатываться на выходе элемента И 19 второго блока 3 свертки.С выхода элемента И 19 признак . свертки через элемент ИЛИ 16 подается на первый вход элемента ИЛИ 17, который предназначен для выработки признака конца формирования разряда Е, Для 1-го блока 3 свертки признак конца Е формируется как объединение сигнала признака конца, поступившего с (1+1)-го блока 3 свертки, и признаков свертки 1-го (1+1)-го и (1+2)-го блоков 3: Одновременно с формированием приз нака конца сигнал свертки Х постуГ пает.на первый вход элемента И 18. Элемент И 18 каждого блока 3 свертки используется для синхронной, подачи сигнала 1) на счетные входы триггеров 20, что устраняет эффект гонок. Выработка сигнала 0 на выходе элемента И 18 осуществляется в момент подачи на второй вход этого элемента управляющего сигнала У по входу 2: и х(х чх чх ).В рассматриваемом примере единичный сигнал свертки Хподается на входы элементов ИЛИ 16 первого и второго блоков 3 свертки. Элементы ИЛИ 16 пропускают эти единичные сигналы на первые входы элементов И 18 и470746 10 15 20 четвертыми входами= Х (1р+2)блоков свертки.425 2. Устройство по п.1 о т л ич а ю щ е е с я тем, что блок свертки содержит первый и второй элементы 30 40 45 Формула изобретения1. Устройство для приведения р-кодов Фибоначчи к минимальной форме) содержащее и блоков свертки, причем первый выход 1-го блока свертки соединен с первым входом (1-1)го и вторым входом (1-р)-го блоков свертки, второй выход 1-го блока свертки сое 50 5 15и элементов ИЛИ 17, на выходе 15устройства появляется сигнал признака конца формирования кода, равныйединице. По входу 2 устройства подается управляющий сигнал У, приэтом на выходах элементов И 18 первого и второго блоков 3 свертки появляются единичные сигналы Б и БЯподаваемые на счетные входы триггеров Т 1 и Т 2, Триггеры Т 1 и Т 2, срабатывая по заднему фронту входногосигнала, изменяют состояние на противоположное; триггер Т 1 переключаетсяиз единичного состояния в нулевое,а триггер Т 2 - из нулевого в единичное,Устройство из исходного состояния010101 переходит в состояние 010110.После подачи по входу 2 устройстваеще двух управляющих сигналов У навыходе 15 устройства появляется сигнал признака конца формирования кода,равный нулю. При этом подача на вход2 серии управляющих сигналов У прекращается. На информационных выходахустройства получается результирующий минимальный код Фибоначчи 100000.Таким образом, длительность подачи серии сигналов У меняется в зависимости от количества сверток, фактически выполняемых при Формированииустройством минимального кода Фибоначчи. Самой длительной по времениявляется серия сигналов У для приведения "тяжелого" кода Фибоначчи типа10101010101010101011. Для приведения"легкого" кода Фибоначчи типа01001001001001001001 длительность серии сигналов У равна нулю. Кроме того,вустройстве каждый из блоков сверткисодержит меньшее количество логических Элементов при сохранении функциональных воэможностей прототипа. динен с 1-ым информационным выходомгруппы устройства, третьим входом(1+1)-го и четвертым входом (1+р+1)го блоков свертки, тактовый вход устройства соединен с пятыми входамивсех блоков свертки, информационныевходы группы устройства соединены сшестыми входами соответствующих блоков свертки, отличающеесятем, что, с целью повьпдения быстродействия, третий выход 1-го блокасвертки (при 11) соединен с седьмымвходом (1-1)-го блока свертки, третийвыход первого блока свертки являетсявыходом признака конца Формированиякода устройства, вторые входы 1=Х(1и-р) и первый и седьмой входы и-го блоков свертки соединены с входом логического нуля устройства,вход логической единицы которого соединен с третьим входом первого и ИЛИ, первый и второй элементы И и триггер, причем выход первого элемента И соединен с первым выходом блокасвертки и первым входом первого элемента ИЛИ, второй и третий входы которого соединены с первым и вторымвходами блока свертки соответственно,выход первого элемента ИЛИ соединенс первыми входами второго элемента И и второго элемента ИЛИ, второй вход второго элемента И соединен с пятымвходом блока свертки, выход второго элемента И соединен со счетным входом триггера, шестой вход блока свертки соединен с входом установки в"1." триггера, прямой выход которогосоединен с вторым выходом блока свеитки, а инверсный выход - с первым входом первого элемента И, второй итретий входы которого соединены стретьим и четвертым входами блокасвертки соответственно, второй входвторого элемента ИЛИ соединен с седьмым входом блока свертки, выход второго элемента ИЛИ соединен с третьимвыходом блока свертки.орректор В ня а 6 одписн и СССР етениямушская н ного комитета по 035, Москва, Жггиям при4/5 Производственно-издательский комбинат "Патент", г, Ужгород гарина Заказ 85ВНИИПИ Государст У(Х 83 Клюев