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

(19) ИИ 6 Р 5/О ОПИСАНИЕ ИЗОБРЕТЕН ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ К АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) 1. Авторское свидетельство СССР У 842786, кл. С 06 Р 5/02, 1981.2. Патент США У 4187500, кл, 349-347, опублик. 1977 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р КОДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ, содержащее п ячеек свертки и развертки р -кодов Фибоначчи, (где и - чис;ло разрядов входного кода), информационные входы и выходы которых являются соответственно информационными входами и выходами устройства, о т - л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения получения всех форм представления числа в р-кодах фибоначчи, в него введены первый сдвиговый регистр, содержащий и+р+2 разряда, второй сдвиговый регистр, содержащий и +р+1 разряд, элемент ИЛИ и элемент задержки, выходкоторого соединен с входами начальнойустановки первого и второго сдвиговыхрегистров, управляющие входы которыхсоединены с входом синхронизации устройства, первый и второй управляющиевходы которого соединены соответственно с входами переноса первого ивторого сдвиговых регистров, единичный выход (1+р+2)-го разряда первогосдвигового регистра (1 =1-п) соединенс управляющим входом развертки -йячейки свертки и развертки р -кодовФибоначчи, управляющий вход сверткикоторой соединен с единичным выходом-го разряда второго сдвигового регистра, а выход развертки -й ячейкисвертки и развертки р-кодов Фибоначчисоединен с 1 -м входом элемента ИЛИ,выход которого соединен с входомэлемента задержки, (и+1)-й вход элемента ИЛИ соединен с единичным выходом первого разряда первого сдвигового регистра, а (и+2)-й вход элемента ИЛИ является входом начальной установки устройства.1 ,10924Изобретение относится к вычислительной технике и может быть использовано для кодирования слов-синонимов в информационно-поисковых системах,Известно устройство для приведения Р-кодов фибоначчи к минимальной форме, позволяющее получать как минимальную, так и максимальную форму любого натурального числа, представленго в-коде Фибоначчи, содержащее и функциональпых ячек, где П -число разрядов входного кода 111.Недостатком известного устройства является невозможность получения всех форм представления числа в Р -ко де Фибоначчи.Наиболее близким к предлагаемому является устройство для приведения р-кодов Фибоначчи к минимальной форме, позволяющее получить как минимальную, так и максимальную форму числа, представленного в р-коде Фибоначчи, содержащее и ячеек, каждая из которых содержит триггер, блок коммутации, блок свертки, формирующий сигнал, воздействующий через блоки коммутации на триггеры 1-й, ( 7-1) -й и ( %в -1) -й функциональных ячеек и осуществляющий переброс триггеров этих функциональных ячеек в инверсное состояние, блок развертки, формирующий сигнал, воздействующий через блоки коммутации на триггер 2-й функциональной ячейки и на триггеры функциональных ячеек от ( -р)-й35 до (1-2 р)-й включительно и осуществляющий их переброс в инверсное состояние, причем блок свертки содержит логическую схему И свертки и инвертор, блок развертки содержит логическую схему И, информационные входы и выходы .которых являются соответственно информационными входами и выходами устройства 1 2 3.Недостатком указанного устройства45 также является невозможность получения всех форм представления числа в р-коде Фибоначчи.Целью изобретения является расщирение функциональных возможностей50 за счет обеспечения получения всех форм представления числа в Р -кодах Фибоначчи.Поставленная цель достигается тем, что в устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее и ячеек свертки и развертки р -кодов Фибоначчи (где П - число разрядов входного кода),89 2информационные входы и выходы которых являются соответственно информационными входами и выходами устройства, дополнительно введены первый сдвиговый регистр, содержащий и+р+2 разряда, второй сдвиговый регистр,содержащий и+Р+1 разряд, элемент ИЛИ и элемент задержки, выход которого соединен с входами начальной установки первого и второго сдвиговых регистров управляющие входы которых соединены с входом синхронизации устройства, входы нуля и единицы которого соединены соответственно свходами переноса первого и второгосдвиговых регистров, единичный выход(1 +Р+2)-го разряда первого сдвигового регистра (1-"1 - и) соединен с управляющим входом развертки 1-й ячейкисвертки и развертки р -кодов Фибоначчи, управляющий вход свертки которойсоединен с единичным выходом 1-горазряда второго сдвигового регистра,а выход развертки 1-й ячейки сверткии развертки р -кодов Фибоначчи соединен с 1-м входом элемента ИЛИ, выходкоторого соединен с входом элементазадержки, (о+1)-й вход элемента ИЛИсоединен с единичным выходом первогоразряда первого сдвигового регистра,а (и +2)-й вход элемента ИЛИ являетсявходом начальной установки устройства.На чертеже приведена блок-схемапредлагаемого устройства, В качестве примера рассмотрен случай, когдар=1 и о=7,Устройство содержит ячейки 1свертки и развертки Р -кодов Фибоначчи, предназначенные для хранения ис-.ходной и промежуточной форм представления числа, а также для выполнения операций свертки и развертки над кодом, первый сдвиговый регистр 2, предназначенный для хранения управляющего сигнала развертки, второй сдвиговый регистр 3, предназначенный для хранения управляющих сигналов свертки, элемент 4 ИЛИ, предназначенный для выработки сигнала установки в исходное состояние первого сдвигового регистра 2 и второго сдвигового регистра 3 через элемент 5 задержки, предназначенный для временной задержки сигнала установки на время, необходимое для окончания переходных процессов в ячейке 1 для приведения р -кодов Фибоначчи к минимальной форме. Устройство имеет их.д б синхронизации, соединени,и 1 и, равляющими1092489 4 входами 7 и 8 соответственно первого сдвигового регистра 2 и второго сдвигового регистра 3, вход 9 начальной установки устройства, соединенный с входом 10 элемента 4 ИЛИ, а также ин-формационные входы 11 и информационные выходы 12 устройства.Единичные выходы 13 разрядов 2.4- 2.10 первого сдвигового регистра 2 соединены соответственно с управляю О щими входами 14 развертки функциональных ячеек 1 устройства для приведения Р -кодов Фибоначчи к минимальной форме, управляющие входы 15 свертки которых соединены соответ ственно с единичными выходами 16 разрядов 3, 1-3,7 второго сдвигового регистра 3, входы 17 элемента .4 ИЛИ соединены соответственно с выходами 18 развертки ячеек 1 устройства для 2 О приведения р -кодов Фибоначчи к минимальной форме, вход 19 элемента 4 ИЛИ соединен с единичным выходом 13 разряда 2.1 первого сдвигового регистра 2, выход 20 элемента 4 ИЛИ соединен 25 с входом 21 элемента 5. задержки, выход 22 которого соединен с входами 23 и 24 начальной установки соответственно первого сдвигового регистра 2 и второго сдвигового регистра 3, пер-у вый управляющий вход 25 устройства служит для подачи потенциала 0, второй управляющий вход 26 второго регистра 3 служит для подачи потенциала "1".Устройство работает следующим об- З 5 разом.Занесение исходной информации в устройство производится по информационным входам 11. Пусть в исходном состоянии в ячейку занесен код40 1001010, в разряде 2.10 первого сдвигового регистра 2 записана единица, а в остальных разрядах 2.1-2.9 - нули, во всех разрядах 3.1-3.9 второго сдвигового регистра 3 записаны нули. При подаче единичного сигнала на вход 6 синхронизации устройства первый сдвиговый регистр 2 устанавливается в состояние 0000000010, .второй сдвиговый регистр 3 устанавливается в состояние 000000001, Единичный сигнал с единичного выхода 13 разряда 2.9 первого сдвигового регистра 2 поступает на управляющий вход 14 развертки 55 ячейки 1.6 свертки и развертки р-кодов Фибоначчи. Единичный сигнал с .выхода 18 развертки ячейки 1.6 через вход 17 элемента 4 ИЛИ поступает на вход элемента 5 задержки. Происходит развертка, единичного состояния ячейки 1.6 свертки и развертки р -кодов Фибоначчи. Устройство для приведения р-кодов Фибоначчи к минимальной форме устанавливается в состояние 1001001. Нулевой сигнал с выхода 18 развертки ячейки 1.6 через вход 17 элемента 4 ИЛИ поступает на вход 21 элемента 5 задержки. Единичный сигнал с выхода 22 элемента 5 задержки поступает на входы 23 и 24 начальной установки соответственно первого и второго сдвиговых регистров 2 и 3. Первый сдвиговый регистр 2 устанавливается в исходное состояние 0000000001, второй сдвиговый регистр 3 устанавливается в исходное состо-, яние 000000000.При подаче следующих трех единичных сигналов на вход 6 синхронизации устройства первый сдвиговый регистр 2 установится в состояние 0000001000, второй сдвиговый регистр 3 - в состояние 000000111. Происходит развертка единичного состояния ячейки 1.4 свертки и развертки р-кодов Фибоначчи, Устройство для приведения р-кодов фибоначчи к минимальной форме установится в состояние 1000111. Первый сдвиговый регистр 2 устанавливается в исходное состояние 000000000.При подаче следующих единичных сигналов на вход 6 синхронизации устройства первый сдвиговый регистр 2 установится в состояние 0001000000,второй сдвиговый регистр 3 установится в состояние 000111111. Происходит развертка единичного состояния ячейки 1. 1 свертки и развертки р-кодов Фибоначчи, Единичный сигнал с единичного выхода 16 разряда 3.4 второго сдвигового регистра 3 поступает на управляющий вход 15 свертки ячейки 1.4 свертки и развертки р -ходов Фибоначчи. Происходит свертка в ячейке 1.4. Единичный сигнал с единичного выхода 16 разряда 3.6 второго сдвигового регистра 3 поступает на управляющий вход 15 свертки ячейки 1.6 свертки и развертки р -кодов Фибоначчи. Устройство для приведения рукодов Фибоиаччи к минимальной форме устанавливается в состояние 0111010. Единичный сигнал с выхода 22 элемента 5 задержки поступает на входы 23 и 24 начальной установки соответственно первого1092489 Продолжение таблицы Код второго сдвигавого регистра 3 Код первого сдвигового регистра 2 Код ячейки 1 для приведения ркодов Фибоначчи к минимальной форме 5 2 ОЕ ВИ)Единичный сигнал на входе 9 начальной установки, пройдя через элемент 4 ИЛИ и элемент 5 задержки, устанавливает первый и второй сдвиговые регистры 2,3 в исходное состояниеСчитывание информации производится по информационным выходам 12,Таким образом, предложенное устроиство позволяет путем определенного распределения управляющих сигналов свертки и развертки по разрядам кода получить все формы представления числа в р-кодах Фибоначчи, что и опрецеляет положительный эффект. 000000000 000000000 000000001 000000011 000000000 000000001 000000011 и второго сдвиговых регистров 2 и 3. Первый сдвиговый регистр устанавливается в исходное состояние 0000000001, второй сдвиговый регистр 3 устанавливается в исходное состояние 000000000,5Дальнейшая работа устройства иллюстрируется в приведенной таблице, 3 0000000001 0111010 000000000 0 111001 0000000010 0111001 0000000100 0111001 0000000001 0110111 0000000010 01.10111 0000000100 0110111 0000001000 0110111 ,0000010000 0110111 0000100000 0110111 0001000000 0111010 0010000000 0111010 0100000000 0111010 0000000001 1001010 000000111 00000 1111 000011111 000111111 001111111 011111111 0000000001092489Составитель М.Аршавский едактор М.Петрова ТехредЖ.Кастелевич Корректор С Шекм аказ 3255/32 Тираж 699 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д.4/5ал ППП "Патент", г.ужгород, ул.Проектная,