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

/00, 1978.ельство СССР ГОО 1 ЩФРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И.ОТКРЫТИЙ ОПИСАНИЕ И(56) 1, Авторское свид11 РЮ 880, кл. 6 Об Г 72. Авторское свидетМ 842783, ко, 6 Об Р.5/ОО, 1979.3, Авторское свидетельство СССР11 842786, кл, О Об Г 5/00, 1978,4, Авторское свидетельство СССРУ 662930 кл. 6 6 Р 5/00, 1976(й - разрядность приводимого числа),причем первый выход 1-го блока свер-.тки (1 1+и) соединен с первым входом (0-1)"го и вторым входом (1"р).блоков свертки, второй выход 1-гоблока свертки является 1-и информационным выходом устройства и соединен с третьим (1+1)-го и четвертымвходами(1 Фр+1) блоков свертки, первый управляющий вход устройства соединен с. пятыми входами всех блоковсвертки, шестые и седьмые входы каждого блока свертки являются инфор"мационными входами устройства, а каждый блок свертки содержит триггер,первый элемент И, первый и второйэлементы ИЛИ, причем пятый, шестойи седьмой входы каждого блока сверткисоединены соответственно с первыми входами первого элемента И, первого и второго элементов ИЛИ, выходы которых соединены соответственно с первым выходом блока сверт-. ки, с нулевым и единичными входами триггера, единичный и нулевой выходы которого соединены соответственно с вторым выходом блока свертки и с вторым входом первого элемента И, о т л и чающее с я тем, что, с целью расширения функциональных возможностей путем получения промежуточных форм представления заданного числа при переходе от его минимальной формы представления в . максимальной и обратно, выход 1-го а блока свертки соединен с восьмым входом (1-1)-го и девятым входом (1-р)-го блоков свертки, второй, тратий, четвертый и пятый управляв- С щие входы устройства соединенысоответственно с десятым, одиннад.цатым, двенадцатым и тринадцатым , входами каждого блока свертки, а в каждый. блок свертки введены второй, третий, четвертый, пятый и шестой элементы И,. третий элемент ИЛИ и два элемента НЕ, причем первый, второй входы каждого блока свертки соедине-. р ны соответственно с первым и вторым входами третьего элемента ИЛИ, тре. тий вход блока свертки соединен с третьим входом первого элемента И и через первый элемент НЕ с первым входом второго элемента И, выход ко- Вф торого соединен с третьим входом третьего элемента ИЛИ и является третьим выходом блока свертки, четвертый вход блока свертки соединен через второй элемент НЕ с вторым входом второго элемента И и с четвертым вхо"1019434 дом первого элемента И, восьмой,девятый, десятый, одиннадцатый, двенадцатый и тринадцатый входы блокасвертки соединены соответственно счетвертым и пятым входами третьегоэлемента ИЛИ, с первым входом тре"тьего элемента И, с третьим входомвторого элемента И, с вторым вхо"дом третьего элемента И и с первымвходом четвертого элемента, И выход которого соединен с вторым входомпервого элемента ИЛИ, выход первого элемента И соединен с вторым входом четвертого элемента И и с шес"тым входом третьего элемента ИЛИ,выход которого соединен с третьимИзобретение относится к вычислительной технике и может быть использовано для получения развернутойформы р-кода Фибоначчи и приведенияее к минимальной Форме,Известно устройство для приведе"ния р-кодов фибоначчи к минимальнойформе с повышенным надежностнымихарактеристиками получаемыми за счетустранения неоднозначности срабаты"вания устройства из-за последовательного выполнения операции свертки 1 1,Известно устройство для приведе"ния р-кодов фибоначчи к минимальнойформе повышенного быстродействия,достигаемого за счет введения дойол.нительной шины сквозного переносаусловия свертки и операция при"ведения кода выполняется одновре"менно над всеми разрядами 2.Известно также устройство при"ведения р-кодов Фибоначчи к мини"мальной Форме, позволяющее получатьмаксимальную форму р-кода фибоначчи,.из-за наличия схем переключения иразвертки 1"3;1.. Наиболее близким техническим решением н предлагаемому изобретениюявляется устройство для приведенияр-цодов Фибоначчи к минимальнойформе, которое содержит и однотипных блоков свертки, причем первыйвыход 1-го блока свертки соединенс вторым входом (1-р)-го блокасвертки, второй выход 1-го блокасвертки является информационным входом, третьего элемента И, первыйи второй входы блока свертки соединены с первыми входами пятого и шестого элементов И, соответственно,выходы которых соединены с вторыми третьим входами второго элементаИЛИ, соответственно, тринадцатыйвход блока свертки соединен с вто"рыми входами пятого и шестого эле"ментов И, единичный нулевой выходытриггера соединены соответственнос четвертым входом второго элемента И и информационным входом триггера, выход третьего элемента И соединен с входом синхронизации триггера. 3выходом устройства и соединен с третьим входом (1"1)."го блока сверткии четвертым входом (1-р"1)-го бло"ка свертки, управляющий вход устрой ства соединен с пятыми входами блоков свертки, шестые входы каждогоблока свертки являются информацион- .ными входами устройства 1 М (Недостатком указанных устройств 10 является невозможность полученияпромежуточных Форм представлениязаданного числа при переходе от егоминимальной Формы представления кмаксимальной и обратно.15Цель изобретения - расширениефункциональных воэможностей путемполучения. промежуточных форм представления заданного числа при пе реходе от его минимальной Формы представления к максимальной и обратно,Поставленная цель достигаетсятем, что в устройство для приведенияр"кодов фибоначчи к минимальной фор ме, содержащее и-блоков свертки (иразрядность приводимого числа), причем первый выход 1-го блока свертки(1-1)-го и вторым входом (1-р) блозо ков свертки, второй выход 1-го блокасвертки является м информационнымвыходом устройства и соединен с тре"тьим входом (1-1)-го и четвертым входами (1-р) блоков свертки, первый 35управляющий вход устройства соединенс пятыми входами всех блоков свертки, шестые и седьмые входы каждогоблока свертки являются информационными входами устройства, а каждыйблок свертки содержит триггер, первый элемент И, первый и второй эле"менты ИЛИ, причем пятый, шестой иседьмой входы каждого блока сверткисоединены соответственно с первымивходами первого элемента И, первогои второго элементов ИЛИ, выходы ко 10194 2025304550 торых соединены соответственно с первым входом блока свертки с нулевым и единичным входами триггера, единичный и нулевой выходы которого соединены соответственно с вторым выходом блока свертки и с вторым входом первого элемента И, выход 1-го блока свертки соединен с восьмым входом (1=1)-го и девятым входом (1-р)-.го блоков свертки, второй, третий, четвертый и пятый управляоцие входы устройства соединены соответственно с десятым, одиннадцатым, двенадцатым и тринадцатым входами каждого блока свертки,а в каждый блок свертки введены второй, третий, четвертый, пятый и шестой элементы И, третий элемент ИЛИ и два элемента НЕ, причем первый и второй входы каждого блока свертки соединены соответственно с первым ивторым входами третьего элемента ИЛИтретий вход блока свертки соединенс третьим входом первого элементаИ и через первый элемент НЕ с первымвходом второго элемента И, выход которого соединен с третьим входом третьего элемента ИЛИ и является третьим выходом блока свертки, четвертый вход блока свертки соединен через второй элемент НЕ с вторым входом второго элемента И и с четвертым входом первого элемента И, восьмой, девятый, десятый, одиннад" цатый, двенадцатый и трина,цатый входы блока свертки соединены соответственно с четвертым и пятым входами третьего элемента ИЛИ, с первым входом третьего элемента И, с третьим входом второго элемента И, с вторым входом третьего элемента И и с первым входом четвертого эле" мента И, выход которого соединен с вторым входом первого элемента ИЛИ, выход первогоэлемента И соединен с вторым входом четвертого элемента И и с шестым входом третьего эле" мента ИЛИ, выход которого соединен с третьим входом третьего элемента 34 ЮИ, первый и второй выходы блокасвертки соединены с первыми входамипятого и шестого элементов И, соответственно, выходы которых соединены с вторым и третьим входами второго элемента ИЛИ, соответственно,тринадцатый вход блока свертки сое"динен с вторыми входами пятого ишестого элементов И, единичный и ну"левой выходы триггера соединены со"ответственно с четвертым входом второго элемента И и информационнымвходом триггера, выход третьего элемента И соединен с входом синхронизации триггера,На фиг, 1 приведена функциональная схема устройства для р и п=6на фиг, 2 приведена функциональнаясхема блока свертки,Устройство содержит шесть блоков1 свертки, каждый блок 1 сверткиимеет установочные входы 2 и 3, инФормационные входы 4 и 5, управляющий вход 6, информационные входы7 и 8, для занесения исходной ин-.формации, Кроме того, каждый блок1 свертки имеет дополнительные установочные входы 9 и 10, дополнительные управляоцие входы 11-14,В состав блока 1 свертки (фиг.2)входит триггер 15, первый элемент16 И, второй элемент 17 И, третийэлемент 18 И, четвертый элемент19 И, пятый элемент 20 И, шестойэлемент 21 И, первый элемент 22 ИЛИ,второй элемент 23 ИЛИ, третий элемент 23 ИЛИ, четвертый элемент24 ИЛИ, первый элемент 25 НЕ, второйэлемент 26 НЕ, Выход первого элемен-та 16 И является первым выходом бло"ка 1 свертки, появление единичногосигнала на выходе которого свидетельствует овыполнении условия сверткидля данного блока 1,свертки, Единичный выход триггера 15 являе ся вторым выходом блока 1 свертки, Выходвторого элемента 17 И является третьим выходом блока 1 свертки, появле"ние единичного .сигнала на выходекоторого свидетельствует о выполне"нии условия развертки для данногоблока 1 свертки, Входы первого элемента 16 И соединены с инверснымвыходом и вторым входом триггера 15,входом первого элемента 25 НЕ и информационным вхдодом 5 и непосред.ственно с управляющим входом 6 бдока 1 свертки, Первый выход блока 1свертки соединен с первым входом5 10194 первого элемента 22 ИЛИ и вторым входом четвертого элемента 19 И.Входы второго элемента 17 И сое" динены е прямым выходом триггера 15 и вторым выходом блока 1 свертки, у выходом дервого элемента 25 НЕ выходом второго элемента 26 НЕ и непосредственно с управляющим вхо" дом 12 блока 1 свертки, Кроме того, третий выход блока 1 свертки соеди- е нен с шестым входом первого эле" мента 22 ИЛИ, Второй вход первого элемента 22 ИЛИ соединен с вторым входом пятого элемента 20 И и с установочным входом 2 блока 1 сверт з ки, Третий вход первого элемента 22 ИЛИ соединены с вторым входом шестого элемента 21 И и с установочным входом 3 блока 1 свертки, Четвертый и пятый входы первого эле" ф мента 22 ИЛИ соответственно соединены с дополнительными установочными входами 9 и 10 блока 1 свертки,Дополнительные управляющие 13 и 11 входы блока 1 свертки соединены и соответственно с первым и вторым входами третьего элемента Ц Я, третий вход которого соединен с выходом первого элемента 22 ИЛИ, Выход третьего элемента 18 И соединен стретьим входом триггера 15. Дополнительный управляющий 14 вход поступает на первые входы четверто-го 19, пятого 20 .и аестоуфо 21 элемента И, Выходы пятого 20 и шестого 21 элемента И поступают на вто- ээ рой и третий входы третьего злемен" та 24 ИЛИ, первый вход которого соединенс информационным входом 8 блока 1 свертки, Выход третьего элемента 24 ИЛИ соединен с первым входом ф триггера 15, четвертый вход которого соединен,с выходом второго эле-.мента 23 ИЛИ, Информационный вход 7 блока 1 свертки соединен с вторым входом второго злеиента 23 ИЛИ, 4 э первый вход которого соединен с выходом четвертого элемента 19 И. С установлением триггеров 15 в соответствующие состояния на инверсйом выходе триггера 15 блока 1.2 свертки возникает единичный сигнал, который поступает на первый вход первого элемента 6:Й блока 1,2 свертки, на второй вход которого поступает единичный сигнал с второго выхода блока 1,1 свертки, третий вход неэадействован, так как должен быть соединен с вторым выходом блока- свертки предшествующего блоку 1.1 свертки, а на четвертом входе на" ходится управляющий единичный сигнал, На выходе первого элемента 16 И блока 1.2 свертки появляется единичный сигнал, который поступает на первый вход первого элемента 22 ИЛИ и второй вход четвертого элемента 19 И блока 1,2 свертки, на второй вход первого элементе 22 ИЛИ и второй вход пятого злемен" та 20 И блока 1,1 свертки, Нулевой сигнал на входах 13 всех блоков 1 свертки в асинхронном режиме блокирует поступление единичных сигналов с выхода первого элемента 22 ИЛИ блоков 1,1 и 1,2 свертки, Единичный сигнал с входов 14 всех блоков 1 свертки поступает на первые входы четвертого 19, пятого 20, шестого 21 элементов И всех блоков 1 гверт- ки, На выходе четвертого элемента; - 19 И блока 1,2 свертки появится единичный сигнал, поступающий на пер. вый вход второго элемента 23 ИЛИ, выход которого соединен с четвертым входои триггера 15 блока 1.2 свертки, Единиц" ный сигнал с выхода пятогс элемента 20 И блока 1.1 свертки поступит на второй вход третьего элемента 24 ИЛИ с выхода которого подается на первый вход триггера 15 блока 1,1 свертки, Устройство иэ состояния 00 1 0 1 перейдет в состояние 0 1 0 1 1 О, Единичный сигнал с инверсного выхода триггера 15 блока 1,4 свертки поступает на первый вход первого блока 16 И, на второй и третий входы которого поступают единичные сигналы с вторых выходов блоков 1,2 и 1.3 В асинхронном режиме устройство работает следующим образом.Перед началом работы все триггеры 15 находятся в нулевом состоянии. Сигналы, поступающие на входы 7 и 8 блоков 1 свертки всех разрядов, устанавливают триггеры 15 в состояние, соответствующее поданному коду, Пред- ложим, что необходимо привести к минимальной форме первый код фибоначЗ 4 6чи числа 8, представленного следующим образомВес разряда 8 5 3 2 1 1Номер блока свертки 1,6 1,5 1,4 1,3 1,2 1Первый кодФибоначчичисла 0 1 0 1 0 10 1 0 1 0 7 10194 свертки, управляющий единичный сиг- нал поступает на четвертый вход первого блока 16 И, единичный сигнал с выхода первого элемента 16 И бло" ка 1,4 свертки поступает на первый элемент 22 ИЛИ и четвертый элемент 19 И блока 1.4 свертки, на первый элемент 22 ИЛИ и на пятый элемент 20 И блока 1.3 свертки, на первый элемент 22 ИЛИ и шестой элемент 1 Е 21 И блока 1.2 свертки.На выходе четвертого элемента 19 И появляется единичный сигнал, который через второй элемент 23 ИЛИ поступает на четвертый вход тригге ра 15 блока 14 свертки, Единичные сигналы с выхода пятого элемента 20 И блока 1.6 свертки и выхода шестого элемента 21 И блока 1,2 свертки через соответствующие третьи эле- Зе мейты.24 ИЛИ поступают на первые входы триггеров 15 блоков 1,3 и 1.2 свертки. Устройство из состояния 0 1 О 1 1 0 перейдет в состояние 0 1 1 0 0 О, Аналогичные условия а возникнут для следуецей триады блоков 1,4:1,5:1,6 свертки и устройство из состояния 01 О 0 0 перейдет в состояние 1 0 0 0 О О.В синхронном режиме устройство . зв производит свертку и развертку кода и работает следующим образом.Перед началом работы все триг" геры 13 находятся .в нулевом состоянии, Сигналы, поступающие на входы 7 и 8 блока 1 свертки всех разрядов,33 устанавливают триггеры 15 в состояния, соответствующие поданному коду, Предположим, необходимо привести к минимальной Форме первый код Фибонач"40 чи числа 8, представленного следую" щим образом:Вес разряда 8 5 3 2Номер блокасвертки 1,6 15 1,4 1,3 1,2 1 1Первый кодФибоначчичисла 1 Приведение к минимальной формепроисходит потактно е два этапа.На первом этапе - этапе подготтовки осуществляется формированиесигналов всех блоков 1 сверткж.йопри этом свертка не производится,На втором этапе при поступленииединичного сигнала на управляющиевходы 11 всех блоков 1 свертки,при наличии единичного сигнала науправляющих входах 13 всех блоков 34 81 свертки, происходит формирование сигналов, поступающих на счетные входы 3 триггеров 13 блоков 1 свертки, разрядов, подлежащих ввертке. С уста" новлением триггеров 15 в соответству" ющие состояния на инверсном выходе триггера 15 блока 1.2 свертки возникает единичный сигнал, который поступает на первый вход первого элемента 16 И блока 1.2 свертки, на второй вход которого поступает еди" ничный сигнал с второго выхода блока 1,1 свертки, а на .четвертом входе .находится управляющий единичный сигнал. На выходе первого элемента 16 И бло" ка 1.2 свертки появляется единичныйсигнал, который поступает на первыйвход первого элемента 22 ИЛИ и второй вход четвертого элемента 19 И блока 12 свертки появляется единичный сигнал,который поступает на первый входпервого элемента 22 ИЛИ и второй вход ,четвертого элемента 19 И блока 1.2свертки, на второй вход первого эле"мента 22 ИЛИ и второй вход пятогоэлемента 20 И блока 1.1 свертки,Нулевой сигнал на управляющих входах 14 всех блоковсвертки в синхронном режиме блокирует поступление .сигналов на установочные первый ичетвертый входы всех триггеров 15блоков 1 свертки, В синхронном режи"ме единичный сигнал поступает. на 13входы всех блоков 1 свертки, С выходов первого элемента 22 ИЛИ блоков1,1 и 1,2 свертки единичный сигналпоступает на третий вход третьегоэлемента 8 И,. Поступление единич"ного сигнала на управляющий вход 11всех блоков 1 свертки вызывает появление единичных сигналов на выходах третьих элементов 18 И и блоков 1, 1 и 1,2 свертки, которые поступают на третьи входы триггеров 15 блоков 1 и 1,2 свертки, Устройство из состояния О 1 0 1 0 1 переходит в состояние О 1 91 О, На ин" версном выходе триггера 15 блока 1,4 . свертки возникает единичный сипнал, который поступает иа первый вход первого элементе 16 И блока 1,4 свертки, на второй и третий входы которых поступают единичные сигнеь соответственно с второго выхода блока 1.3 свертки и второго выхода блока 1,2 свертки, На четвертый вход первого элемента 16 И блока 1,4 свертки по",ступает единичный управляющий сигнал, который поступает на первыйЭ 1019вход первого элемента 22 И и второйвход четвертого элемента 19 И блока1.4 свертки, на вторые входы первогоэлемента 22 И и пятого элемента 20 Иблока 1,3 свертки, третий вход перво-го элемента 22 И и второй вход шесто"го элемента 21 И блока 1.2 свертки,Нулевой сигнал на управляющих входах14 всех блоков 1 свертки блокируетпоступление сигналов на установоч- фные входыи 4 всех триггеров 15,На входы 13 всех блоков 1 сверткипоступает управляющий единичный сигнал. С выходов первого элемента22 ИВИ блоков 1,2, 1,3 и 1,4 сверткиединичный сигнал поступает на третийвход третьего элемента 18 И блоков1,2, 1,3 и 1,4 свертки, Поступлениеединичного сигнала на управляющийвход 11 в сех блоков 1 свертки вызы- уфвает появление единичных сигналов навыходах третьих элементов 18 И блоков 1.2, 1.3 и1,4 свертки, которыепоступают на .третьи входы триггеров15 блоков 1,2, 1.3 и 1,4 свертки. ИУстройство из состояния 0 1 0 1 1 0перейдет в состояние 0 1 1 0 О О,В следующем такте работы условиесвертки будет выполняться для триадыблоков 1,4, 15 и 1,6 свертки м уст- З 11ройство из состояния 0 1 1 1 0 0 0перейдет в состояние 1 0 0 0 0 О.Процесс потактного приведения первого кода фибоначчи числак минимальной форме следующий:35Вес разряда 8 5 3 2Номер блока 1,б 1,5 1,4 1,3 1,2 1,Первый кодчисла Фибоначчи 0 1 0 1 0 1 46Такт Мф0 10 0 О2 0 1 1 0 0 .03 1 0 0 .0 О ОПосле третьего такта первый .кодФибоначчи числа 8 примет минимальнуюформу 1 0 О 0 О,Для приведения к максимальной форме первого кода фибоначчи устройствоработает следующим образом,В исходном состоянии все триггеры15 находятся в нулевом состоянии.Сигналы, поступающие на входы 7 и 8блоков свертки всех разрядов, устанавливают триггеры 15 в состояния, соот"%ветствующие поданному коду. Предположим, необходимо привести к максимальной форме минимальный первый код10000.0 434 10Вес разряда 8 5 3 ; 1 1Номер блокасвертки 1,6 1,5 1,4 1,3 1,2 1,1Первый кодфибоначчичисла 1 0 0 0 О 0Приведение к максимальной форме происходит потактно, С установлением триггера 15 в соответствующие состояния на прямом выходе триггера 15 бло" ка 1.6 свертки возникает единичный сигнал, который поступает на первый вход второго элемента 17 И блока 1,6 сверткина второй и третий входы которого поступают соответственно выходы первого 25 и второ" го 26 элементов НЕ, на четвертый вход второго элемента 17 И блока 1.6 свертки поступает единичный сигнал с управляющего входа 12 блока 1.6 свертки, На выходе второго элемента 17 И блока 1,6 свертки появляется единичный сигнал, который поступает на шестой вход первого элемента 22 ИЛИ блока 1,6 свертки, на девятый вход блока 1,5 свертки и десятый вход блока 1.4 свертки, На входы 13 всех блоков 1 свертки в синхронном режиме подан единичный разреаающий сигнал, а на входы 11 всех блоков свертки подается единичный управляющий сигнал, который приходит на первый и второй входы третьего элемента 18 И всех блоков 1 свертки. На третий вход третьих элементов 18 И блоков 1,4, 1.5 и 1.6 свертки поступают единичные сигналы с выходов пер" вых элементов 22 ИЛИ блоков 1.4, 1,5 и 1,6 свертки.1Единичные сигналы с выходов третьих элементов 18 И блоков 1.4, 1.5 и 1.6 свертки поступают на третьи входы триггеров 15 блоков 1,4, 1.51,6,свертки, Устройство из состояния 1 0 0 0 О 0 переходит в состояние 0 1О 0 О. В следующих двух тактах условно развертки будет выполняться для триады 1,2, 1.3 и 1.4 блоков свертки, а потом для 11 и 1.2 блоков свертки. Процесс потактного приведения минимального первого кода фибоначчи числа 8 к минимальной Форме следующий:Вес разряда 8 5 3 2 1 1Номер блокасвертки 1,6 1,5 1,4 1,3 1,2 1,1Первый кодчисла Фибо"наччиаз 3 ого комит открыская н ал ППП "Патент", г, Ужгород, ул,3 Ти ВНИИПИ Госу ло делам 113035, Москаж 706 арстве зобрет а, Же ее Подлисноета СССРтийнаб д. М 5е е еаеее а аектная, 4