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

 

УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КОДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ, содержащее п ячеек свертки и развертки р-кодов Фибоначчи, (где п - разрядов входного кода), информационные входы и выходы которых являются соответственно информационными входами и выходами устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения получения всех форм представления числа в р-кодах Фибоначчи, в него введены первый сдвиговый регистр, содержащий П+Р+2 разряда, второй сдвиговый регистр , содержащийп+Р+1 разряд, элемент ИЛИ и элемент задержки, выход которого соединен с входами начальной установки первого и второго сдвиговых регистров, управляющие входы которых соединены с входом синхронизации устройства , первый и второй управляющие входы которого соединены соответственно с входами переноса первого и второго сдвиговых регистров, единичный выход (i+p+2)-rp разряда первого сдвигового регистра () соединен с управляющим входом развертки i-й ячейки свертки и развертки р -кодов Фибоначчи, управляющий вход свертки которой соединен с единичным выходом -го разряда второго сдвигового реW гистра, а выход развертки i-и ячейки свертки и развертки р-кодов Фибоначчи соединен с i -м входом элемента ИЛИ, выход которого соединен с входом элемента задержки, (п+1)-й вход элемента ИЛИ соединен с единичным выходом первого разряда первого сдвигового регистра, а (п+2)-й вход элемента ИЛИ является входом начальной установки устройства.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (111

З(5ц G 06 F 5/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3517156/18-24 (22) 01. 12. 82 (46) 15.05.84. Бюл. № 18 (72) А.П.Стахов, Н.А.Соляниченко, В.В.Замчевский и А.И.Оникиенко (71) Винницкий политехнический институт (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР № 842786, кл. G 06 F 5/02, 1981.

2. Патент США ¹ 4187500, кл. 349-347, опублик. 1977 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ

Р-КОДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ, содержащее и ячеек свертки и развертки р -кодов Фибоначчи, (где и — чис;ло разрядов входного кода), информационные входы и выходы которых являются соответственно информационными входами и выходами устройства, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения получения всех форм представления числа в р-кодах Фибоначчи, в него введены первый сдвиговый регистр, содержащий п+р+2 разряда, второй сдвиговый регистр, содержащий и +р+1 разряд, элемент ИЛИ и элемент задержки, выход которого соединен с входами начальной установки первого и второго сдвиговых регистров, управляющие входы которых соединены с входом синхронизации устройства, первый и второй управляющие входы которого соединены соответственно с входами переноса первого и второго сдвиговых регистров, единичный выход (1+р+2)-го разряда первого сдвиговогo pe H (i =1 n) соединен с управляющим входом развертки -й ячейки свертки и развертки р -кодов

Фибоначчи, управляющий вход свертки которой соединен с единичным выходом

j-го разряда второго сдвигового регистра, а выход развертки -й ячейки свертки и развертки р-кодов Фибоначчи соединен с 1 -м входом элемента ИЛИ, выход которого соединен с входом элемента задержки, (n+1) é вход элемента ИЛИ соединен с единичным выходом первого разряда первого сдвигового регистра, а (и+2)-й вход элемента ИЛИ является входом начальной установки устройства.

1,10924

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

Известно устройство для приведения

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

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

Наиболее близким к предлагаемому является устройство для приведения р-кодов Фибоначчи к минимальной форме, позволяющее получить как минимальную, так и максимальную форму числа, представленного в р-коде Фибоначчи, содержащее и ячеек, каждая из которых содержит триггер, блок коммутации, блок свертки, формирующий сигнал, воздействующий через блоки коммутации на триггеры 1-й, (7-1) -й и (%†p-1) -й функциональных ячеек и осуществляющий переброс триггеров этих функциональных ячеек в инверсное состояние, блок развертки, формирующий сигнал, воздействующий через блоки коммутации на триггер

7.-й функциональной ячейки и на триггеры функциональных ячеек от (I-p)-й

35 до (1-2р)-й включительно и осуществляющий их переброс в инверсное состояние, причем блок свертки содержит логическую схему И свертки и инвертор, блок развертки содержит логическую схему И, информационные входы и выходы .которых являются соответственно информационными входами и выходами устройства (2 ).

Недостатком указанного устройства

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

Целью изобретения является расщирение функциональных возможностей

50 за счет обеспечения получения всех форм представления числа в р -êîäàõ

Фибоначчи.

Поставленная цель достигается тем, что в устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее и ячеек свертки и развертки р -кодов Фибоначчи (где

П вЂ” число разрядов входного кода), 89 2 информационные входы и выходы которых являются соответственно информационными входами и выходами устройства, дополнительно введены первый сдвиговый регистр, содержащий и+р+2 разряда, второй сдвиговый регистр,содержащий и+р+1 разряд, элемент ИЛИ и элемент задержки, выход которого соединен с входами начальной установки первого и второго сдвиговых регистров„ управляющие входы которых соединены с входом синхронизации устройства, входы нуля и единицы которого соединены соответственно с входами переноса первого и второго сдвиговых регистров, единичный выход (i +p+2)-ãî разряда первого сдвигового регистра (i †" 1 — и) соединен с управляющим входом развертки i é ячейки свертки и развертки р -кодов Фибоначчи, управляющий вход свертки которой соединен с единичным выходом 1-го разряда второго сдвигового регистра, а выход развертки 1-й ячейки свертки и развертки р -кодов Фибоначчи соединен с 1-м входом элемента ИЛИ, выход которого соединен с входом элемента задержки, (и+1)-й вход элемента ИЛИ соединен с единичным выходом первого разряда первого сдвигового регистра, а (n +2)-й вход элемента ИЛИ является входом начальной установки устройства.

На чертеже приведена блок-схема предлагаемого устройства. В качестве примера рассмотрен случай, когда р=1 и р=7.

Устройство содержит ячейки 1 свертки и развертки р -кодов Фибоначчи, предназначенные для хранения ис-. ходной и промежуточной форм представления числа, а также для выполнения операций свертки и развертки над кодом, первый сдвиговый регистр 2, предназначенный для хранения управляющего сигнала развертки, второй сдвиговый регистр 3, предназначенный для хранения управляющих сигналов свертки, элемент 4 ИЛИ, предназначенный для выработки сигнала установки в исходное состояние первого сдвигового регистра 2 и второго сдвигового регистра 3 через элемент 5 задержки, предназначенный для временной задержки сигнала установки на время, необходимое для окончания переходных процессов в ячейке 1 для приведения р -êîäîí Фибоначчи к минимальной форме. Устройство имеет «х.д б синхронизации, соединенlll,Ill, равляющими

1092489 4 входами 7 и 8 соответственно первого сдвигового регистра 2 и второго сдвигового регистра 3, вход 9 начальной установки устройства, соединенный с входом 10 элемента 4 ИЛИ, а также ин- формационные входы 11 и информационные выходы 12 устройства.

Единичные выходы 13 разрядов 2.42.10 первого сдвигового регистра 2 соединены соответственно с управляю- 10 щими входами 14 развертки функциональных ячеек 1 устройства для приведения P †код Фибоначчи к минимальI ной форме, управляющие входы 15 свертки которых соединены соответственно с единичными выходами 16 разрядов 3, 1-3,7 второго сдвигового регистра 3, входы 17 элемента .4 ИЛИ соединены соответственно с выходами

18 развертки ячеек 1 устройства для gp приведения р -кодов Фибоначчи к минимальной форме, вход 19 элемента 4 ИЛИ соединен с единичным выходом 13 разряда 2.1 первого сдвигового регистра

2, выход 20 элемента 4 ИЛИ соединен 25 с входом 21 элемента 5. задержки, выход 22 которого соединен с входами

23 и 24 начальной установки соответственно первого сдвигового регистра 2 и второго сдвигового регистра 3, пер-у вый управляющий вход 25 устройства служит для подачи потенциала "0", второй управляющий вход 26 второго регистра

3 служит для подачи потенциала "1".

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

Занесение исходной информации в устройство производится по информационным входам 11. Пусть в исходном состоянии в ячейку занесен код

1001010, в разряде 2.10 первого сдвигового регистра 2 записана единица, а в остальных разрядах 2.1-2.9— нули, во всех разрядах 3.1-3.9 второго сдвигового регистра 3 записаны ну- ли.

При подаче единичного сигнала на вход 6 синхронизации устройства первый сдвиговый регистр 2 устанавливается в состояние 0000000010, .второй сдвиговый регистр 3 устанавливается в состояние 000000001. Единичный сигнал с единичного выхода 13 разряда 2.9 первого сдвигового регистра 2 поступает на управляющий вход 14 развертки ячейки 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 — в состояние 0000001 il. Происходит развертка единичного состояния ячейки 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 для приведения ркодов Фибоначчи к минимальной форме

2 О

\

Единичный сигнал на входе 9 начальной установки, пройдя через элемент 4 ИЛИ и элемент 5 задержки, устанавливает первый и второй сдвиговые регистры 2,3 в исходное состояние °

Считывание информации производится по информационным выходам 12.

Таким образом, предложенное уст1 роиство позволяет путем определенного распределения управляющих сигналов свертки и развертки по разрядам кода получить все формы представления числа в р-кодах Фибоначчи, что и опрецеляет положительный эффект.

000000000

000000001

00000001 i

000000001

000000011 и второго сдвиговых регистров 2 и 3.

Первый сдвиговый регистр устанавливается в исходное состояние 0000000001, второй сдвиговый регистр 3 устанавливается в исходное состояние 000000000.5

Дальнейшая работа устройства иллюстрируется в приведенной таблице.

0000000001 0111010

000000000! 0 111001

0000000010 0111001

0000000100 0111001

0000000001 0110111

0000000010 0110111

0000000100 0110111

0000001000 01 1011 1 ,0000010000 0110111

0000100000 0110111

000 i 000000 01 1 10 i 0

0010000000 0111010

0100000000 0111010

0000000001 1001010

000000111

00000 1111

000011111

000111111 .

001111111

011111111

000000000

1092489

Составитель М.Аршавский

Редактор М.Петрова ТехредЖ.Кастелевич Корректор C.meKMaP

Заказ 3255/32 Тираж 699 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП "Патент", r.Óæãoðoä, ул.Проектная, 4