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

Изобретение относится к вычислительной технике и может быть использовано для приведения р-кодов Фибог наччи к минимальной форме. Известно устройство для приведения р-кбдов Фибоначчи к минимальной форме, которое содержит п однотипных блоков свертки, причем первый выход Е-ГО блока свертки соединен со вторым входом {В-р-1)-го блока свертки второй выход 1-го блока свертки является информационным выходом устройства и соединен с третьим входом (1+1) то блока свертки и четвертым входом (Е+р+1)-го блока свертки, управляющий вход устройства соедиHeti с пятыми входами всех блоков све1(тки, шестые входы каждого блока являются информационными вх дами устройства 1. Недостаток известного устройства значительное время приведения р-кодов Фибоначчи к минимальной форме. Это определяется тем, что процесс приведения к минимальной форме состоит из ряда последовательно выполнаяемых операций свертки над группо из трех разрядов. Время одной сверт , указанном устройстве будет равно + илм /V /Х . ... где C, , -ТР время переключений соответственно элементов И, ИЛИ и триггера. Максимальное время приведения кода к минимальной форме равно Т В. -К may 2 С.6 Таким образом, максимальное время приведения кода к минимальной форме равно |( ) 1 + тр) V-uHBт тек- +ил л учитывая соотношения , -ТР- -И 1 где,,- время переключения одного инвертора. Цель изобретения - повышение быстродействия устройства приведения р-кодов Фибоначчи к минимальной форме. Поставленная цель достигается тем, что в устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее п однотипных блоков свертки, причем первый выход Е-го блока свертки соединен с первым входом (-1)-го и вторым входом (В-р-1)-го

блоков свертки, второй выход 1.-го $лока свертки является 1-м информационным выходом устройства и соединен .с третьим входом(Е+1)-го и четвертым входом (..+р+1)-го блоков свертки,управляющий вход устройства соединен с пятым входом всех блоков свертки, шестые входы каждого блока свертки являются информационными входами устройства, введена дополнительная связ первый выход Е-го блока свертки соединен с седьмлм входом (В+р+1)-го блока свертки. Кроме того, блок сверки содержит триггер, первый, второй, третий и четвертый элементы И, первый, второй и третий элементы ИЛИ, первый и второй элементы НЕ, причем выход первого элемента НЕ соединен с первым входом первого элемента И, инверсный выход триггера соединен с певым входом первого элемента ИЛИ, выход которого соединен с первым входом второго элемента И, выход второго элемента ИЛИ соединен с вторым входом второго элемента И, выход которого соединен с первым входом третьего элемента И, входом первого элемента НЕ и первым выходом блока, первый вход блока соединен с первым входом четвертого элемента И, выходы первого, третьего и четвертого элементов И соединены соответственно с первым, вторым и третьим входами третьего элемента ИЛИ, выход которог соединен со счетным входом триггера, прямой выход которого является вторы выходом блока, второй вход блока соединен со входом второго элемента НЕ, со вторым входом первого элемента И и со вторым входом первого элемента ИЛИ, третий вход второго элемента И и первый вход второго элемента ИЛИ являются соответственно третьим и четвертым входами блока, пятый вход блока соединен с третьим входом первого элемента И и вторыми входами третьего и четвертого элементов И, шестой вход блока соединен со вторйми входами третьего и четвертого элементов И соответственно, седьмой вход блока соединен с установочным входом триггера, выход второго элемента НЕ соединен с третьим входом третьего элемента И.

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

Устройство содержит шесть блоков 1 . Каждый из которых имеет устанЪйочные входы 2 и 3, информационные входы 4 и 5, управляющий вход б, кроме того, каждый блок 1 свертки имеет информационный вход 7 для занесения исходной информации и установочный вход 8 сквозного переноса. По установочным входам 2 и 3 и по установочному входу 8 сквозного переноса в соответствующие блоки свертки поступает единичный сигнал, свидетельствующий о выполнении условия свертки. Блок 1 свертки (фиг. 2) содержит триггер 9 со счетным входом, первый элемент И 10, второй элемент И 11, третий элемент И 12, четвертый элемент И 13, первый элемента ИЛИ 4, втрой элемент ИЛИ 15, третий элемент ИЛИ 16, первый элемент НЕ 17, второй элемент НЕ 18. Выход второго элемента И 1 1 является первым выходом блока 1 свертки, появление единичного сигнала на выходе которого свидетельствует о выполнении условия свертки для данного блока 1 свертки. Единичный выход триггера 9 является вторым выходом блока 1 свертки. Входы второго элемента И 11 соединены через первый элемент ИЛИ 14 с установочным входом 3 блока 1 свертки и инверсным выходом триггера 9, через второй элемент ИЛИ 15 с установочным входом 8 сквозного переноса блока 1 свертки и информационным входом 5 блока 1 свертки и непосредственно с информационным входом 4 блока 1 свертки,Кроме того, первый выход блока 1 свертк соединен со входом первого элемента НЕ 17 и первым входом третьего элемента И 12, Входы первого элемента И 10 соединены соответственно с выхО дом первого элемента НЕ 17,управляющим входом б блока 1 свертки и установочным входом 3 блока 1 свертки. Входы третьего элемента И 12 соединены соответственно с выходом второго элемента НЕ 18,управляющим входом 6 блока 1 свертки и первым выходом блока 1 свертки.Входы четвертого элемента И 13 соединены соответственно с управляющим входом б блока 1 свертки и с установочным входом 2 блока 1 свертки,Выходы первого элемента И 10 третьего элемента И 12-и четвертого элемента И 13 соединены через третий элемент ИЛИ 16 со счетным входом триггера 9, Появление единичного сигнала на выходе третьего элемента ИЛИ 16 приводит к инвертированию состояния.триггера 9, Кроме того, установочный вход 3 блока 1 свертки соединен со входом второго элемента НЕ 18 Установочный вход в единицу триггера 9 соединен с информационным входом 7 блока 1 свертки.

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

Перед началом работы все триггеры находятся в нулевом состоянии. Сигналы, поступающие на установочные входы 7 блоков 1 свертки всех разрядов, устанавливают триггеры 9 в состояния, соответствующие поданному коду.

Предположим, что необходимо привети к минимальной форме 1-код Фибоначчи числа 8, представляемого следующим образом: Вес разряда Номер блока 1,6 1,5 1,4 1,3 1,2 1, свертки 1-код Фибоначчичисла 8предлагаемом устройстве это происходит в два этапа. На первом этапе - этапе подготовки - осуществляет ся формирование сигна лов выделения ситуаций для выполнения операций свертки. Эти сигналы формируются по цепям сквозного пере .носа, но при этом свертка не производится.. На втором этапе, при поступлении единичного сигнала на управляющие входы 6 всех блоков 1 свертки, происходит формирование сигналов, поступающих на счетные входы триггеров 9блоков 1 свертки разрядов, подлежащих свертке. С установлением триггеров 9 в соответствующие состояния на инверсном выходе триггера 9 блока 1,2; свертки возникает единичный сигнал, который через первый эле мент ИЛИ 14 блока 1,2 свертки поступает на первый вход второго элемента И 11 блока 1,2 свертки, на второй вход которого поступает единичный сигнал со второго выхода блока 1,1 свертки, а на третьем входе находится постоянно единичный сигнал На выходе второго элемента И 11 блока 1,2 ,свертки появляется единичный сигнал, который поступает на вход первого элемента НЕ 17, блока 1,2 свертки, на первый вход третьего элемента И 12 блока 1,2 свертки,на первый вход четвертого элемента И 1 блока 1,1свертки и через второй элемент ИЛИ 15 блока 1,4 свертки - на второй вход второго элемента И 1 блока 1,4 свертки, на третий вход которого поступает единичный сигнал со второго выхода блока 1,3 свертки а на первый вход поступает через элемент ИЛИ 14, блока 1,4 свертки единичный сигнал с инверсного выхода триггера 9 блока 1,4 свертки. Нулевой сигнал с выхода первого элемента НЕ 17 блока 1,2 свертки поступает на первый вход первого элементаИ 10 блока 1,2 свертки, запрещая появлени единичного сигнала на выходе этого элемента. На выходе второго И 11 блока 1,4 свертки появляется единичный сигнал, который поступает на вход первого ,элемента НЕ 17блока 1,4 свертки, на первый вход третьего элемента И 12 бло.ка 1,4 свертки, на первый вход четвертого элемента И 1 блока 1,3 свертки, на второй вхОд первого элемента И 10 блока 1,2 свер ки, на вход второго элемента НЕ 18 блока 1,2 свертки и через второй элемент ИЛИ 15 блока 1,6 свертки на второй вход второго элемента И 11 блока 1,6 двертки, на третий вход которого поступает единичный сигнал со второго выхода блока 1,5 свертки, а на первый вход поступает черезэлемент ИЛИ 14 блока 1,6 свертки единичный сигнал с инверсного выхода триггера 9 блока 1,6 свертки. Нулевой сигнал с выхода первого элемента НЕ 17 блока 1,4 свертки поступает на первый вход первого элемента И 10 1,4 свертки,запрещая появления единичного сигнала на выходе этого элемента. Нулевой сигнал с выхода второго элемента НЕ 18 блока 1,2 свертки поступает на третий вход третьего элемента И 12 блока 1,2 свертки, запрещая появление единичного сигнала на выходе этого элемента. На выходе второго элемента И 11 блока 1,6 свертки появляется единичный сигнал, который поступает на вход первого элемента НЕ 17 блока 1,6 свертки, на первый вход третьего элемента И 12 блока 1,6 свертки, на первый 1вход четвертого элемента И 13 блока 1,5 свертки, на третий вход первого элемента И 10 блока 1,2 свертки и на вход второго элемента НЕ 18 блока 1,2 свертки. Нулевой сигнал с выхода первого элемента НЕ 17 блока 1,6 свертки поступает на первый вход первого элемента И 10 блока 1,6 свертки, запрещая появление на его выходе единичного сигнала. Нулевой сигнсШ с выхода второго элемента НЕ 18 блока 1,4 свертки поступает на третий вход третьего элемента И12 блока 1,4 , запрещая появление единичного сигнгша на его выходе. Таким образом, единичные сигналы появляются на первых .выходах блоков 1, 2; 1,4; 1,6 свертки, на третьих входах первых элементов И 10 блоков 1,2; 1,4 свертки, на первых входах первых элементов И 10 блоков 1,1; 1,3; 1,5 свертки, на первых входах третьих элементов И 12 блоков 1,2; 1,4; 1,6 свертки, на третьих входах третьих элементов И 12 блоков 1,1; 1,3; 1,5; 1,6 свертки, на первых входах четвертых.элементов И 13 блоков 1,1; 1,3; 1,5 свертки. Нулевые сигналы появляются на первых выходах блоков 1,1; 1, 3; 1,5;на третьих входахпервых элементов И 10 блоков 1,1 1,3; 1,5 свертки, на первых входах первых элементов И 10 блоков. 1,2; 1,4; 1,6 свертки, на первых входах третьих элементов И 12 &локов 1,1; 1,3 свертки, на третьих входах третьих элементов И 12 блоков 1,2; 1,4; 1,6 свертки,на первых входах Ч1етвертых элементов И 13 блоков 1,2 и 1,4, запрещая появление единичных сигналов на выходах первого элемента И 10 третьего элемента И 12 блока 1,1 свертки; первого элемента И 10, третьего элемента И 12, четвертого элемента И 13 блока 1,2 свертки; первого элемента И 10, третьего элемента И 12 блока 1,3 свертки; первого элемента И 10, третьего элемента И четвертого элемента И 13 блока 1,4 свертки; первого элемента И 10, тре тьего элемента И 12 блока 1,5 сверт ки; третьего элемента И 12,четвертог элемента И 13 блока 1,6 свертки. ПРИ поступлении единичного сигна на управляющие входы б блоков 1,1; 1,2; 1,3; 1,4; 1,5; 1,6 свертки воз никают единичные сигналы на выходах четвертых элементов И 13 блоков 1,1 1,3; 1,5 свертки и на выходе третье элемента И 12 блока 1,6 свертки, ко торые через третьи элементы ИЛИ 16 соответствующих блоков свертки пост пают на счетные входы триггеров 9 блоков 1,1; 1,3; 1,5; 1,6 свертки. Устройство из состояния 010101 пере ходит в состояние 100000. Для пояснения работы устройства при приведении к минимальной форме других кодов введены следующие обоз начения: Св - сигнал с первого выхода блока 1 свертки Е-го разряда; ив - сигнал с выхода третьего элемента ИЛИ 16 блока 1 свертки г-го разряда; Т& - сигнал с прямого выхода тригге ра 9 блока 1 свертки Е-го раз ряда; ТЕ - сигнал с инверсного выхода три гера 9 блока 1 свертки е-го разряда; - сигнал , поступающий на пятые входы всех блоков 1 свертки. В соответствии с принятыми обозначениями формирование сигналов С и и происходит по следующим уравнениям:се (тк + се+а) (т8-2+ се-2) ( ив (ее-06+2+ )-у. ( Уравнение (1) соответствует первому этапу работы устройства, а на втором этапе происходит формировани инвертирующих сигналов в соответствии с уравнениям (2), Примеры, иллюстрирующие работу устройства, приведены ниже. При необходимости к минимальной форме 1-к Фибоначчи числа 12 значения сигнало С и. и, вычисляемые для каждого блок свертки в соответствии с приведенны выше уравнениями, а также окончател ный результат свертки, будут следую щими: Результат свертки Ниже приводятся значения сигналов и, С для каждого разряда, а также окончательный результат свертки при приведении к минимальной форме 1-кода Фибоначчи числа 11 Вес разряда 8 5 3 21 1 Номер блока свертки1,61,5 1,4 1,3 1,2 1,1 1-код Фибоначчи числа 011101 Результат свертки Предлагаемое устройство позволяет получать минимальную формулу исходного р-кода Фибоначчи за один такт управляющего сигнала Y . Максимальное время приведения кода к минимальной форме равно max - vnav -ii mdy, где Т1 максимальное время осуществления первого этапа работы устройства; максимальное щремя осуществления второго.этапа работы устройства; зависит от количества разрядов и равно - -If: -п - ииб fnoix 2 Или . не зависит от количества разрядов и равно mcis- Значение максимального времени Т приведения кода к минимальной форме равно п + 2t т -ГГ may 2 чне Для дваддатиразрядного 1-кода Фибонначи в известном устройстве , тогда как при том же количестве разрядов в предлагаемом - 32fKHg. Таким образом, предлагаемое устройство обладает более высоким быстродействием, что и определяет положительный эффект. Кроме того, устройство может осуществлять контроль за формированием сигналов С, основывающийся на том, Что при правильной работе невозможно появление сигналов се в двух соседних блоках 1 свертки, что является дополнительным преимуществом устройства, . Формула изобретения 1..Устройство для приведения р-кодов Фибона.ччи к минимальной форме, содержащее п -блоков свертки, причем первый выход В-го блока свертки соединен с первым входом (-1)-го и вторым входом (B-p-l)-ro блоков свертки, второй выход 1-го блока свертки является t -м информационным выходом устройства и соединен с третьим входом {t+l)-ro и четвертым входом (1.+р-И)блоков свертки, управляющий вход устройства соединен с пятыми входами всех блоков .свертки, шестые входы каждого блока свертки являются информационными входами устройства, отличающееся тем, что, с целью повышения быстродействия, первый выход Е-го блока.свертки соединен с седьмым входом (6+р+1)-го блока сверт ки. 2. Устройство по п. 1,отличающееся тем, что блок сверт ки содержит триггер, первый, второй, третий и четвертый элементы И, первый второй и третий элементы ИЛИ, первый и второй элементы НЕ, причем выход первого элемента НЕ соединен с первым входом первого элемента И, инвер ный выход триггера соединен с первым входом первого элемента ИЛИ, выход которого соединен с первым входом вто рого элемента И, выход второго элемента ИЛИ соединен со вторым входом второго элемента И, выход которого , соединен с первым входом третьего элемен.та ТЛ, входом первого элемента НЕ и первым выходом блока,первыйвход блока соединен с первым входом четвертого элемента И, выходы первого, третьего и четвертого элементов И соединены с первым, вторым и третьим входом третьего элемента ИЛИ, выход . которого соединен со счетным входом триггера, прямой выход которого является вторым выходом блока, BTOjJofl вход блока соединен со входом вторЬго элемента НЕ, со вторым входом первого элемента И и со вторым входом . первого элемента ИЛИ, третий вход второго элемента И и первый вход второго элемента ШШ являются соответственно третьим и четвертым входами блока, пятый вход блока соединен с третьим входом первого элемента И и вторыми входами третьего и четвертого элементов И, шестой вход блока соединен со вторыми входами третьего и четвертого элементов И соответственно, седьмой вход блока соединен с установочным входом триггера, выход второго элемента НЕ соединен с третьим входом третьего элемента И. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР №662926 по заявке 2386002/18-24, кл. G 06 F 5/00, от 01.08.76 (прототип) ,