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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ Союз Советскик Соцниалистнческнх Республик(61) Дополнительное к авт. свид-ву 1) М. 2) Заявлено 280присоединением 79 (21) 27аявки М 032/18-2 06 Г 5 00 дарственный комнтСССРделам изобретенийи открытий 23) Приоритет 3006,81, Бюллетень Мо 2ания описания 300681 Опубликова71) Заявите инницкий политехнический институт 54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ Р - КОДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕазанном устрайст Изаб тельной зовано наччи ктение относитс ехнике и может я приведения р минимальной фар к вычи слиыть испольадов Фиба-. уде авналСВ,Ъдеаотвериггеия ка ченийЛИ иприверавно с а 10 Таким аб мя приведен форме равно и Тра - 2 ( "и+ "или+ тР 15 учитывая со /Ъ п и = или= где "ии и,едиовблока ми вх г ия О повышение приведени нимальной с р Недостато значительное дов Фибоначч Это определя приведения к таит из ряда наяемых опериз трех разр и ного устройвр приведения рк минимальной фортся тем, что працеминимальной формепоследовательно выций свертки над грдов. Время одной с ства-костигаетс иведения ьной фор блоков 8- го бл ым входа м (0 - ртем,р-каме.сс сос- полрт а пп ертИзвестно устройство для прния р-кодов Фибоначчи к минимформе, которое содержит и аднблоков свертки, причем первыйР-го блока свертки соединенрым входом (В-,р).-го блокавторой выход 1-го блока сверляется информационным выходомройства и соедииен с третьим(6+1) го блока свертки и четвходом (В+р+1)-го блока сверуправляющий вход устройстванен с пятыми входами всех блевертки, шестые входы каждогсвертки являются информациондами устройства 1) . иведеальнай атипны выход о втовертки ки яв- уствходом ертым л= ц + ИЛЧ +вили то - время переклственно элементов И,а. Максимальное времяда к минимальной форме отношения л"инв"сР-и емя переключе инвертора. Цель изабретения -родействия устройства р-кодов Фибоначчи к ми ме. Поставленная цель до что в устройство для пр дов Фибоначчи к минимал содержащее и однотипных ки, причем первый выход свертки соединен с первблоков свертки, второй выход В-го флока свертки является 1-м информационным выходом устройства и соединен с третьим входом(В+1)-го и четвертым входом (.В+р+1)-го блоков свертки,управляющий вход устройства соединен с пятым входом всех блоков свертки, шестые входы каждого блока свертки являются информационными входами устройства, введена дополнительная связь, первый выход Ю-го блока свертки сое 1 О динен с седььим входом ( В+р+1) - го блока свертки, Кроме того, блок свертки содержит триггер, первый, второй, третий и четвертый элементы И, первый, второй и третий элементы ИЛИ, первый и второй элементы НЕ, причем выход первого элемента НЕ соединен с первым входом первого элемента И, ин - версный выход триггера соединен с первым входом первого элемента ИЛИ, выход которого соединен с первым вхо дом второго элемента И, выход второго элемента ИЛИ соединен с вторым входом второго элемента И, выход ко - торого соединен с первым входом третьего элемента И, входом первого 25 элемента НЕ и первым выходом блока, первый вход блока соединен с первым входом четвертого элемента И, выходы первого, третьего и четвертого элементов И соединены соответственно30 с первым, вторым и третьим входами третьего элемента ИЛИ, выход которого соединен со счетным входом триггера, прямой выход которого является вторым выходом блока, второй вход блока сое - динен со входом второго элемента НЕ, со вторым входом первого элемента И и со вторым входом первого элемента ИЛИ, третий вход второго элемента И и первый вход второго элемента ИЛИ являются соответственно третьим и 40 четвертым входами блока, пятый вход блока соединен с третьим входом пер - вого элемента И и вторыми входами третьего и четвертого элементов И, шестой вход блока соединен со вторыми входами третьего и четвертого эле - ментов И соответственно, седьмой вход блока соединен с установочным входом триггера, выход второго элемента НЕ соединен с третьим входом третьего элемента И.На фиг. 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. Выход второго элемента И 11 является первым выходом блока 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,управляющим входом б блока 1 свертки и первым выходом блока 1 свертки .Входы четВертого элемен - та И 13 соединены соответственно с управляющим входом 6 блока 1 свертки и с установочным входом 2 блока 1 свертки. Выходы первого элемента И 10, третьего элемента И 12 и четвертого элемента И 13 соединены через третий элемент ИЛИ 16 со счетным входом триггера 9, Появление единичного сигнала на выходе третьего элемента ИЛИ 16 приводит к инвертированию состояния триггера 9, Кроме того, установочный вход 3 блока 1 свертки соединен со входом второго элемента НЕ 18. Установочный вход в единицу триггера 9 соединен с информационным входом 7 блока 1 свертки. Устройство работает следующим образом.Перед началом работы все триггеры находятся в нулевом состоянии. Сигналы, поступающие на установочные входы 7 блоков 1 свертки всех разрядов, устанавливают триггеры 9 в состояния, соответствующие поданному кодуПредположим, что необходимо привести к минимальной форме 1-код Фибоначчи числа 8, представляемого следующим образом:Вес разряда 8 5 3 2 1 1 Номер блокасвертки 1,6 1 Р 5 1,4 13 12 111 1-код фибоначчичисла ,0 1 0 1 0 1 В предлагаемом устройстве это происходит в два этапа.На первом этапе - этапе подготовки-осуществляется формирование сигналов выделения ситуаций для выполнения операций свертки, Эти сигналы формируются по цепям сквозного переноса, но при этом свертка не производитсяНа втором этапе, при поступлении единичного сигнала на управляющие входы 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 свертки,на первый вход четвертого элемента И 13 блока 1,1 свертки и через второй элемент ЙЛИ 15 блока 1,4 свертки на второй вход второго элемента И 11 40 блока 1,4 свертки, на третий вход которого поступает единичный сигнал со второго выхода блока 1,3 свертки, а на первый вход поступает через элемент ИЛИ 14, блока 1,4 свертки 45 единичный сигнал с инверсного выхода триггера 9 блока 1,4 свертки, Нулевой сигнал с выхода первого элемента НЕ 17 блока 1,2 свертки поступает на первый вход первого элемента И 10 блока 1,2 свертки, запрещая появление единичного сигнала на выходе этого элемента, На выходе второго элемента И 11 блока 1,4 свертки появляется единичный сигнал, который поступает на вход первого элемента НЕ 17 блока 1,4 свертки, на первый вход третьего элемента И 12 блока 1,4 свертки, на первый вход четвертого элемента И 13 блока 1,3 свертки, на второй вход первого элемента И 10 блока 1,2 свертки, на вход второго элемента НЕ 18 блока 1,2 свертки и через второй элемент ИЛИ 15 блока 1,6 свертки на второй вход второго элемента И 11 блока 1,6 свертки, на третий вход 65 которого поступает единичный сигнал со второго выхода блока 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 свертки, на первый вход четвертого элемента И 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 свертки,на первых входах четвертых элементов И 13 блоков 1,2 и 1,4, запрещая появление единичных сигналов на выходах первого элемента И 10 третьего элемента И 12 блока 1,1 свертки; первого элемента И 10, третьего элемента И 12, четвертого элемента И 13 блока 1,2 свертки; первого элемента И 10, третьего элемен 842782Ниже приводятся значения сигналов С для каждого разряда, а также окончательный результат свертки при приведении к минимальной форме 1-кода Фибоначчи числа 11Вес разряда 8 5 3 2 1 Номер блокасвертки 1-код Фибоначчи числа 0 1 1 1 0 1 Результатсвертки 1 0 1 0 0 0 Результат свертки1 0 1 О 1 0 65 та И 12 блока 1,3 свертки; первогоэлемента И 10, третьего элемента И 12,четвертого элемента И 13 блока 1,4свертки; первого элемента И 10, третьего элемента И 12 блока 1,5 свертки;третьего элемента И 12,четвертогоэлемента И 13 блока 1,6 свертки.При поступлении единичного сигналана Управляющие входы 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.Для пояснения работы устройствапри приведении к минимальной форме 20других кодов введены следующие обоз -начения:СЕ - сигнал с перного выхода блока1 свертки Е-го разряда;БЕ - сигнал с выхода третьего элемента ИЛИ 16 блока 1 сверткиЕ,-го разряда;ТЕ - сигнал с прямого выхода триггера 9 блока 1 свертки Е-го раз -ряда;ЗОТЕ - сигнал с инверсного выхода триггера 9 блока 1 свертки Е-горазряда;- сигнал , поступающий на пятыевходы всех блоков 1 свертки,Б соответствии с принятыми обозначениями формирование сигналов Си Б происходит по следующим уравнениям:се: (те + се+) те-(те+ се- ), (1)л = (се се се+1+ се+ се) ч, (2) 40Уравнение (1) соответствует первому этапу работы устройства, а навтором этапе происходит формированиеинвертирующих сигналов в соответствии с уравнениям (2), 45Примеры, иллюстрирующие работуустройства, приведены ниже. При необходимости к минимальной форме 1-кодФибоначчи числа 12 значения сигналовС и. П, вычисляемые для каждого блокасвертки в соответствии с приведеннымивыше уравнениями, а также окончательный результат свертки, будут следующи ми:Вес разряда 8 5 3 2 1 155Номер блокасверки 1 6 1,5 1,4 1,3 1,:, 1,11-код Фибоначчичисла 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1,6 ,5 1,4 1,3 1,2 1,) 1 О 1 О 1 0 1 1 0 1 0 1 Предлагаемое устройство позволяет получать минимальную формулу исходного р-кода Фибоначчи за один такт управляющего сигнала У . Максимальное время приведения кода к минимальной форме равноТ , = Т 1 + Т 2,.где т 1 о - максимальное время осу -ществления первого этапаработы устройства;Т 2 - максимальное время осуществления второго этапаработы устройства; Т 1 зависит от количества разрядов и равнои, л, 3ос 2 ( Илии ивов) в ИНВ2 Т 2, не зависит от количества раэ - рядов и равно,м /фгбч= о + или = 2 "иНВЗначение максимального времени Т, приведения кода к минимальной11 Дформе ванно2 иняДля двадцатиразрядного 1-кода Фибонначи в известном устройстве Тс,-50 инв, тогда как при том же количестве разрядов в предлагаемом - Тп - 32 ин 8.Таким образом, предлагаемое устройство обладает более высоким быстродействием, что и определяет положительный эффект, Кроме того, устройство может осуществлять контроль за формированием сигналов С, основывающийся на том, что при правильной работе невозможно появление сигналов СЕ в двух соседних блоках 1 свертки, что янляется дополнительным преимуществом устройства Формула изобретения1. Устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее п блоков свертки, причем первый выход 3-го блока свертки соединен с первым входом ( 3-1) -го и вторым входом (3-р)-го блоков свертки, второй выход В-го блока свертки явля 842782 10ется Ю -м информационным выходом устройства и соединен с третьим входом( 6+1) -го и четвертым входом (+р+1)-гоблоков свертки, управляющий входустройства соединен с пятыми входамивсех блоков свертки, шестые входыкаждого блока свертки являются информационными входами устройства, о тл и ч а ю щ е е с я тем, что, с целью повышения быстродействия, первыйвыход В-го блока свертки соединен сседьмым входом ( В+р+1)-го блока свертки,2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что блок свертки содержит триггер, первый, второй,третий и четвертый элементы И, первый,5второй и третий элементы ИЛИ, первыйи второй элементы НЕ, причем выходпервого элемента НЕ соединен с первым входом первого элемента И, инверсный выход триггера соединен с первым Овходом первого элемента ИЛИ, выходкоторого соединен с первым входом второго элемента И, выход второго элемента ИЛИ соединен со вторым входомвторого элемента И, выход которого,соединен с первым входом третьегоэлемента И; входом первого элеменТаНЕ и первым выходом блока, первый входблока соединен с первым входом четвертогЬ элемента И, выходы первого,третьего и четвертого элементов Исоединены с первым, вторым и третьимвходом третьего элемента ИЛИ, выходкоторого соединен со счетным входомтриггера, прямой выход которого является вторым выходом блока, второйвход блока соединен со входом втордгоэлемента НЕ, со вторым входом первого элемента И и со вторым входом .первого элемента ИЛИ, третий входвторого элемента И и первый вход второго элемента ИЛИ являются соответственно третьим и четвертым входамиблока, пятый вход блока соединен стретьим входом первого элемента И ивторыми входами третьего и четвертого элементов И, шестой вход блокасоединен со вторыми входами третьегои четвертого элементов И соответственно, седьмой вход блока соединен сустановочным входом триггера, выходвторого элемента НЕ соединен с третьим входом третьего элемента И,Источники информации, принятые во внимание при экспертизе1, Авторское свидетельство СССР 9 662926 по заявке Р 2386002/18-24, кл. С 06 Р 5/00, от 01.08.76 (прототип)842782Составитель И.Сигалов Редактор И,Ковальчук Техред 3. Фанта Корректор Г.Решетник Заказ 5101/59 Тираж 745 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5 Филиал ППП Патент, г. Ужгород, ул. Проектная, 4