Устройство для приведения р-кодов Фибоначчи к минимальной форме Советский патент 1983 года по МПК H03M13/23 

дом первого элемента И, восьмой, девятый, десятый, одиннадцатый, двенадцатый и тринадцатый входы блока свёртки соединены соответственно с четвертым и пятым входами третьего элемента ИЛИ, с первым входом третьего элемента И, с третьим входом второго элемента И, с вторым входом третьего элемента И и с первым входом четвертого элемента, И выход kOToporo соединен с вторым входо первого элемента ИЛИ, выход первого элемента И соединен с вторым входом четвертого элемента И и с шестым входом третьего элемента ИЛИ, вглход которого соединение третьим

входом .третьего элемента И, первый и второй входы блока свертки соединены с первыми входами пятого и шестого элементов И, соответственно, выходы которых соединены с вторым и третьим входами второго элемента ИЛИ, соответственно, тринадцатый вход блока свертки соединен с вторыми входами пятого и шестого элементов И, единичный нулевой выходы триггера соединены соответственно с четвертым входом второго элемента И и информационным входом триггера, выход третьего элемента И соединен с входом синхронизации тригге ра.

«

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

Известно устройство для приведения р-кодов Фибоначчи к минимальной форме с повышенными надежностными характеристиками попумаемыми за сче устранения неоднозначм с: «1 срабатывания устройства из-за последовательного выполнения адерации свертки tl 3

Известно устройство для приведения р-кодов Фибоначчи .к минимальной форме повышенного быстродействия, достигаемого за счет введения допол нительной шины сквозного переноса условия свертки и операция приведения кода выполняется одновременно над всеми разрядами С 23Известно также устройство приведения р-кодов Фибоначчи к минимальной форме, позволяющее получать максимальную форму р-кода Фибоначчи, из-за наличия схем переключения и развертки f3 J

Наиболее близким техническим решением н предлагаемому изобретению является устройство для приведения р-ЕСОДов Фибоначчи к минимальной форме, которое содержит п однотипных блоков свертки, причем первый выход 1-го блока свертки соединен с вторьм входом {1-р-1)-го блока свертки, второй выход 1-го блока свертки является информационным

Д1ХОДОМ устройства и соединен с третьим входом блока свертки и четвертым входом (l-p-l)-ro блока свертки, управлякпций вход устройства соединен с пятыми входами блоков свертки, шестые входы каждого блока свертки являются информационными входами устрой ства Т«1

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

.

Цель изобретения - расширение функциональных возможностей путем пoлyчeн 1я промежуточных форм представления заданного числа при переходе от его минимальной формы представления к максимальной и обратно.

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

с пятыми входами всех блоков сверт3

ки, шестые и седьмые входы каждого блока свертки являются информационными входами устройства, а каждый блок свертки содержит триггер, первый элемент И, первый и второй элементы ИЛИ, причем пятый, шестой и седьмой входы каждого блока свертки соединены соответственно с первыми входами первого элемента И, первого и второго элементов ИЛИ, выходы которых соединены соответственно с певым входом блока свертки с нулевым и единичным входами триггера, единичный и нулевой выходы которого соединены соответственно с вторым выходом блока свертки и с вторым входом первого элемента И, выход 1-го блока свертки соединен с восьмым входом (|з:1)-го и девятым входом (l-p-l)-ro блоков свертки, второй, третий, четвертый и пятый управляющие входы устройства соединены соответственно с десятым, одиннадцатым, двенадцатым и тринадцатым входами каждого блока свертки, а в каждый блок свертки введены второй , третий, четвертый, пятый и шестой элементы И, третий элемент ИЛИ и два элемента НЕ, причем первый и второй входы каждого блока свертки соединены соответственно с первым и вторым входами третьего элемента ИД третий вход блока свертки соединен с третьим входом первого элемента И и через первый элемент НЕ с первы входом второго элемента И, выход которого соединен с третьим входом третьего элемента ИЛИ и является третьим выходом блока свертки, четвертый вход блока свертки соединен через второй элемент НЕ с вторым входом второго элемента И и с четвертым входом первого элемента И, восьмой, девятый, десятый, одиннадцатый , двенадцатый и тринадцатый входы блока свертки соединены соответственно с четвертым и пятым входами третьего элемента ИЛИ, с первым входом третьего элемента И, с третьим входом второго элемента И, с BTopbiM входом третьего элемента Ни с первым входом четвертого элемента И, выход которого соединен с вторым входом первого элемента И/М, выход первого элемента И соединен с вторым входом четвертого элемента И и с шестым входом третьего элемента ИЛИ, выход которого соединен с третьим входом третьего элемента

И, первый и второй выходы блока свертки соединены с первыми входами пятого и шестого элементов И, соответственно, выходы которых соединены с вторым и третьим входами второго элемента ИЛИ, соответственно, тринадцатый вход блока свертки соединен с вторыми входами пятого и шестого элементов И, единичный и нулевой выходы триггера соединены соответственно с четвертым входом второго элемента И и информационным входом триггера, выход третьего элемента И соединен с входом синхронизации триггера.

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

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

7 и 8, для занесения исходной информации. Кроме того, каждый блок 1 свертки имеет дополнительные установочные входы 9 и 10, дополнительные управляющие .входы ll-l.

В состав блока 1 саертки (фиг.2) входит триггер 15, первь1й элемент 16 И, второй элемент 1 И, третий элемент 18 И, четвертый элемент 19 И, пятый элемент 20 И, шестой

элемент 21 И, первыйэлемент 22 ИЛИ,

второй элемент 23 ИЛИ, третий элемент 23 ИЛИ, четвертый элемент 2Ц ИЛИ, первый элемент 25 НЕ, второй элемент 26 НЕ. Выход первого элемента 16 И является Первым выходом блока 1 свертки, появление единичного сигнала на выходе которого свидетельствует о выполнении условия свертки для данного блока 1,свертки. Единичный выход триггера 15 являе ся вторым выходом блока 1 свертки. Выход второго элемента 17 И является третьим выходом блока 1 свертки, появление единичного сигнала на выходе которого свидетельствует о выполнении условия развертки для данного блока 1 свертки. Входы первого элемента 16 И соединены с инверсным выходом и входом триггера 15 входом первого элeмeнta 25 НЕ и информамионным вхдодом 5 и непосредственно с управляющим входом 6 блока 1 свертки. Первый выход блока 1 свертки соединен с первым входом 5 первого элемента 2 ИЛИ и вторым входом четвертого элемента 19 И. Входы Bte0oro элемента 17 И соединены с прямым выходом триггера 15 и вторым выходом блока 1 свертк выходом первого элемента 25 НЕ, выходом второго элемента 2б НЕ и непосредственно с управляющим входом 12 блока 1 свертки. Кроме того третий выход блока 1 свертки соеди нен с шестым входом первого элемента 22 ИЛИ. Вторые вход первого элемента 22 ИЛИ соединен с вторым входом пятого элемента 20 И и с ус тановочным входом 2 блока 1 свертки. Третий вход первого элемента 22 ИЛИ соединены с вторым входом ш стого элемента 21 И и с установоч ным входом 3 блока 1 свертки. Четвертый и пятый входы первого элемента 22 ИЛИ соответственно соединены с дополнительными установочными входами 9 и 10 блока 1 свертк Дополнительные управляюи е 13 и 1J входы блока 1 свертки соединены соответственно с первым и вторым входами третьего элемента lS tl, тр тий вход которого соединен с «лходом первого элемента 22 ИЛИ. Выход третьего элемента 18 И соединен с .третьим входом триггера 15. Дополнительный управляющий k вход поступает на первые входы четвертого 19, пятого 20 и шестого 21 элемента И, Ьыходы пятого 20 и шестого 21 элемента И поступают на второй и третий входы третьего элемента 2 ИЛИ, первый вход -которого сое динена информационным входом 8 блока 1 свертки Выход третьего элемен та 2 ИЛИ соединен с первым входом триггера 15 четвертый вход которого соединен с выходом второго элемента 23 ИЛ1. Информационный вход 7 блока 1 свертки соединен с вторым входом второго элемента 23 ИЛИ, первый вход которого соединен с выходом четвертого элемента 19 И. В асинхронном режиме устройство работает следующим образом. Перед началом работы все триггеры 15 находятся в кулевом состоянии Сигналы, поступающие на входы 7 и 8 блоков 1 свертки всех разрядов, уст навливают триггер 15 в состояние, соответствующее поданному коду. Пре ложим, что необходимо привести к минимальной форме первый код фибпна 4,6 чи числа 8, представленного следующим образом Вес разряда 8 53 2 11 Номер блока свертки 1,6 1,5 1, 1,3 1,2 1 Первый код Фибоначчи числа О 1 О 1 01 с установлением триггеров 15 в соответствующие состояния на инверсйом выходе триггера 15 блока 1.2 свертки возникает единичный сигнал, который поступает на первый вход первого элемента 1б И блока свертки, на второй вход которого поступает единичный сигнал с второго выхода блока 1.1 свертки, третий вход незадействован, так как должен быть соединен с вторым выходом блокасвертки предшествующего блоку 1.1 свертки, а на четвертом входе находится управляюи й единичный сигнал. На выходе первого элемента 1б И блока 1.2 свертки появляется единичный сигнал, который поступает на первый вход первого элемента 22 ИЛИ и второй вход четвертого элемента 19 И блока 1.2 свертки, на второй вход первого элемента 22 ИЛИ и второй вход пятого .элемента 20 И блока 1.1 свертки. Нулевой сигнал на входах 13 всех блоков 1 свертки в асинхронном режиме блокирует поступление единичных -сигналов с выхода первого элемента 22 ИЛИ блоков 1.1 и 1.2 свертки.- Единичный сигнал с входов 1 и всех блоков 1 свертки поступает на первые входы четвертого 19, пятого 20, шестого 21 элементов И всех блоков 1 гверт- ки. На выходе четвертого элементах 19И блока 1.2 евepTKii появится единичный сигнал, поступаюир й на первый вход второго элемента 23 ИЛИ,выход которого соединен с четвертым входом триггера 15 блока 1.2 свертки. Единичный сигнал с выхода пятого элемента 20И блока 1.1 свертки поступит на второй вход третьего элемента , с выхода которого подается на первый вход триггера 15 блока 1.1 свертки Устройство из состояния 010101 перейдет в состояние Ь1 О 1 1 О, Единичный сигнал с инверсного выхода триггера 15 блока 1,-свертки поступает на первый вход первого блока 16 И, на второй и третий входы которого поступают единичные сигналы с вторых выходов блоков 1.2 и 1.3 свертки, управляющий единичный сигнал поступает на четвертый вход первого блока 16 И. Единичный сигна с выхода первого элемента 16 И блока I, свертки поступает на первый элемент 22 ИЛИ и четвертый элемент 19И блока 1.4 свертки, на первый элемент 22 ИЛИ и на пятый элемент 20И блока 1.3 сяертки, на первый элемент 22 ИЛИ и шестой элемент 21И блока 1.2 свертки. На выходе четвертого элемента 19И появляется единичный сигнал, который через второй элемент 23 ИШ поступает на четвертый вход триггера 15 блока l.t свертки. Единичные сигналы с выхода пятого элемента 20И блока 1.6 свертки и выхода шестого элемента 21 И блока 1,2 сверт ки через соответствующие третьи эле мейты. 24 ИЛИ поступают на первые входы триггеров 15 бтжов 1.3 и 1С2 свертки. Устройство из состояния 010110 перейдет в состояние 01 1000. Аналогичные условия возникнут для следущей триады блоков 1.4:1.5:1.6 свертки и устройств из состояния 011000 перейдет в состояние 100000. В синхронном режиме устройство производит свертку и развертку кода и работает следующим образом. Перед работы все триггеры 13 находятся в нулевом состоянии. Сигналы, пдступающие на входы 7 и 8 блока 1 свертки всех разрядов устанавливают триггеры 15 в состояния, соответствующие поданному коду Предположим, необходимо привести к минимальной форме первый код Фибоиз ми числа 8, представленного след чвщим образом: Вес разряда 853 2 Номер блока свертки1,6 V,5 Ь ПЗ 1,2 Первый код Фибоначчи числа01 в 10 Приведение к минимальной фор«(е происходит потактно 8 два этапа tia первом этапе - этапе тюдгот товки осуществляется формирование сигналов всех блоков 1 сверткц.Но при этом свертка не производится. На втором этапе при поступлении единичного сигнала на управляющие входы 11 всех блоков 1 свертки, при наличии единичного сигнала на управляющих входах 13 всех блоков 1 свертки, происходит формирование сигналов, поступающих на с штные входы 3 триггеров 13 блоков 1 свертки, разрядов, подлежащих евертке. С установлением триггеров 15 в соответствующие состояния на инверсном выходе триггера 15 блока 1.2 свертки возникает единичный сигнал, который поступает на первый вход первого элемента 16 И блока 1.2 свертки, на второй вход которого поступает единичный сигнал с второго выхода блока 1.1 свертки, а на четвертом входе находится управляющий единичньЛ сиг- v нал. На выходе первого элемента 16 И блока 1.2 свертки появляется единичный сигнал, который поступает на лервый вход первого элемента 22 ИЛИ и второй вход четвертого элемента 19 И блока 1,2 свертки гюявляется единичный сигнал, который поступает на первый вход первого элемента 22 ИШ и второй вход , четвертого элемента 19 И блока 1.2 свертки, на втoJX5Й вход первого элемента 22 ИШ и второй вход пятого элемента 20 И блока 1.1 свертю1. Нулевой сигнал на управляющих входах 14 всех блоков 1 свертки в синхронном режиме блокирует поступление сигналов на установочные первый и четвертый входы всех триггеров 15 блоков 1 свертки, В синхронном режиг ме единичный сигнал поступает на 13 входы всех блоков 1 свертки. С выходов первого элемента 22 ИЛИ блоков 1.1 и 1.2 свертки единичный сигнал поступает на третий вход третьего элемента 18 И. Поступление единичного сигнала на управляющий вход 11 всех блоков 1 свертки вызывает появление единичных сигналов на выходах третьих элементов 18 И и блоков 1.1 и 1.2 свертки, которые поступают на третьи входы триггеров 15 блоков 1.1 и 1,2 свертки. Устройство из состояния 0101 О 1 переходит в состояние О 1 О 11 0. На инвер сном выходе триггера 15 блока 1. t свертки возникает единичный сипнал, который поступает иа первый вход первого элемента 16 И блока 1.4 свертки, на второй и третий входы которых поступают едегничные сигналы соответственно с второго выхода блока 1,3 свертки и второго выхода блока 1.2 свертки. На четвертый вход первого элемента 1б И блока 1.4 свертки по- Iступает единичный управляющий сигнал, который поступает на первый у1 вход первого элемента 22 И и второй вход четвертого элемента 19 И блока .k свертки, на вторые входы первого элемента 22 И и пятого элемента 20 И блока 1,3 свертки, третий вход перво го элемента 22 И и второй вход шесто го элемента 21 И блока 1,2 свертки. Нулевой сигнал на управляющих входах I всех блоков 1 свертки блокирует поступление сигналов на установочные входы 1 и Ц всех триггеров 15. На входы 13 всех блоков 1 свертки поступает управляющий единичный сигнал, С выходов первого элемента 22 ИЛИ блоков 1.2, 1,3 и 1 ,Л свертки единичный сигнал поступает на третий вход третьего элемента 18 И блоков 1,2, 1.3и 1 свертки. Поступление единичного сигнала на управляющий вход 11 в сех -блоков 1 свертки вызывает появление единичных сигналов на выводах третьих элементов 18 И блоков 1,2, 1,3 и-1,1 свертки, которые поступают на третьи входы триггеров 15 блоков 1,2, 1.3 и l.i саертки. Устройство из состояния О 1 01 10 перейдет в состояние 01 1 000. В следующем такте работы условие свертки будет выполняться для триады блоков I., 1,5 и 1,6 свертки и устройство из состояния 01 11000 перейдет в состояние 100000, Процесс потактного приведения первого кода Фибоначчи числа 8 к минимальной форме следующий: Вес разряда 853 2 11 Номер блока 1,6 1,5 Ь 1,3 , Первый код числа ФибоначчиТакт N 1 После третьего такта первый :код Фибонамчи числа 8 примет минимальную форму 10000. Для приведения к максимальной форме первого кода Фибоначчи устройство работает следующим образом. В исходном состоянии все триггеры 15 находятся в нулевом состоянии. Сигналы, поступающие на входы 7 и 8 блоков свертки всех разрядов, устанав ливают триггеры 15 в состояния, соответствующие поданному коду. Предположим, необходимо привести к максимальной форме минимальный первый код .Фибоначчи числа 3 3« Вес разряда 8 5 Номер блока свертки 1,6 1,5 I, 1,3 1 ,2 1,1 Первый код Фибоначчи числа 1 Приведение к максимальной форме происходит потактно. С установлением триггера 15 в соответствующие состояния на прямом выходе триггера 15 блока 1.6 свертки возникает единичный сигнал, который поступает на первый вход второго элемента 17 И блока 1,6 свертки, на второй и третий входы которого поступают соответственно выходы первого 25 и второго 26 элементов НЕ, на че7:вертый вход второго элемента 17 И блока 1.6 свертки поступает единичный сигнал с управляющего входа 12 блока 1.6 свертки. На выходе второго элемента 17 И блока 1,6 свертки появляется единичный сигнал, который поступает на шестой вход первого элемента 22 ИЛИ блока 1,6 свертки, на девятый вход блока 1,5 свертки и десятый вход блока 1, свертки. На входы 13 всех блоков 1 свертки в синхронном режиме подан единичный разрешающий сигнал, а на входы 11 всех блоков 1 свертки подается единичный управляющий сигнал, который приходит на первый и второй входы третьего элемента 18 И всех блоков 1 свертки. На третий вход третьих элементов 18 И блоков I,, 1.5 и 1,6 свертки поступают единичные сигналы с выходов первых элементов 22 ИЛИ блоков 1,, 1.5 и 1.6 свертки. Единичные сигналы с выходов третьих элг-ментов 18 И блоков l.i, 1,5 и 1,6 свертки поступают на третьи входы триггеров 15 блоков 1.А, 1.5 1.6,свертки. Устройство из состояния 1 00000 переходит в состояние О 1 1 000, В-следующих двух тактах условно развертки будет выполняться для триады 1,2, 1.3 и I. блоков свертки, а потом для 1,1 и 1.2 блоков свертки. Процесс потактного приведения минимального первого кода Фибоначчи числа 8 к минимальной форме следующий: Вес разряда 8532 Номер блока 1.6 1,5 1,4 1,3 1,2 1,1 свертки Первый код числа Фибоначчи1l Такт ff Г01100 201011 301010 Для пояснения работы устройства при работе с других кодами введем следующие обозначения: -сигнал с первого выхода бло 1 свертки 1-го разряда; -сигнал с выхода третьего элемента 18 И блока 1 сверт кки 1-го разряда; Rg - сигнал с третьего выхода бл ка 1 свертки 1-го разряда; Tg - сигнал с прямого выхода три гера 15 блока 1 свертки 1-г iразряда; сигнал с инверсного выхода триггера 15 блока 1 CBeptKM 1-го разряда; сигнал, поступающий на шестые входы всех блоков свертки; сигнал, поступающий на двенадцатые шсоды всех блоков 1 свертки; сигнал, поступающий на один надцатые входа всех блоков 1 свертки; сигнал, поступающий на тринадцатые входы всех блоков 1; свертки; сигнал, поступающий на четы надцатые входы всех блоков 1 свертки; установочный сигнал, поступающий на вход блеж 1 свертки 1-го разряда; . установочный сигнал, поступающий на восьмой вход блока 1 свертки 1-го разряда; сигнал с выхода второго эле мента 23 ИЛИ блока 1 свертк 1-го разряда; A сигнал с выхода третьего эле мента 24 ИЛИ блока 1 свертки 1-го разряда, В соответствии с принятыми обозначениями формирование сигналов S, R, и, М и N происходит по следующим уравнениям: 5„ Т., t; -Т -Y, Ч е -i -S«..(3) I Уравнения (1 ) и (2) соответствуют первому этапу работы устройства этапу формирования условий, как в синхронном, так и асинхронном режимах, Уравнение (3 ) соответствует BTOpotity этапу работы устройства в синхронном режиме, когда происходит формирование инвертирующих сигналов, Уравне ние (4 ) и (5 ) соответствуют второму этапу работы устройства в асинхроннo 4 рен(име, когдапроисходит формирование установочных сигналов. Таким образом, предложенное устройство обладает более широкими функциональные возможностями, что и определяет положительный эффект. Кроме того устройство обладает возможностью осуществления контроля формирования сигналов S и Rg основывающегося на том, что при правильной работе устройства, во-первых, невозможно одновременно появление сигналов So и R g в одном блоке свертки, во-вторых, невозможно появление сигналов Sg в двух блоках 1 свертки, .в-третьих, невозможно появление сигналов Rg в двух соседних блоках, что является дополнительным преимуществом устройства.