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

Изобретение относится к вычислительной технике и может быть использовано для кодирования слов-синонимо в информационно-поисковых системах. Известно устройство для приведени Р-кодов Фибоначчи к минимальной форме, позволяющее получать как минимальную, так и максимальную форг-гу лю бого натурального числа, представлен го в р-коде Фибоначчи, содержащее п функциональных ячеек, где п -число разрядов входного кода tl1. Недостатком известного устройств является невозможность получения . всех форм представления числа в р-ко де Фибоначчи. Наиболее близким к предлагаемому является устройство для приведения р-кодов Фибоначчи к минимальной форме, позволяющее получить как минимальную, так и максимальную форму числа, представленного в р-коде Фибоначчи, содержащее п ячеек, канодая из которых содержит триггер, блок коммутации, блок свертки, формирующий сигнал, воздействующий через блоки коммутации на триггеры -й, (Е-1)й и (Б-р-1)-й функциональных ячеек и осуществляющий переброс триг геров этих функциональных ячеек в ин версное состояние, блок развертки, формирующий сигнал, воздействующий через блоки коммутации на триггер t-й функциональной ячейки и на триггеры функциональных ячеек от (-р)-й до (1-2р)-й включительно и осуществляющий их переброс в инверсное состояние, причем блок свертки содержит логическую схему И свертки и инвертор, блок развертки содержит логическую схему И, информационные вхо ды и выходы .которых являются соответ ственно информационными входами и вы ходами устройства 2. Недостатком указанного устройства также является невозможность получения всех форм представления числа в р-коде Фибоначчи. Целью изобретения является расширение функциональных возможностей за счет обеспечения получения всех форм представления числа в р-кодах Фибоначчи, Поставленная цель достигается тем, что в устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее п ячеек свертки и развертки р -КОДОР; Фибоначчи (где П - число разрядов входного кода), информационные входы и выходы которых являются соответственно информационными входе1ми и выходами устройства, дополнительно введены первый сдвиговый регистр, содержащий n+p-i-2 . разряда, второй сдвиговый perTicTp,содержащий п+р+1 разряд, элемент РШИ и элемент задержки, выход которого соединен с входами начальной установки первого и второго сдвиговых регистров,, управляющие входы которых соединены с входом синхронизации устройства входы нуля и единицы которого соединены соответственно с входами переноса первого и второго сдвиговых регистров, единичный вькод (i )-го разряда первого сдвигового регистра () соединен с управляющим входом развертки i-й ячейки свертки и развертки р-кодов Фибоначчи, управляющий вход свертки которой соединен с единичным выходом i-ro разряда второго сдвигового регистра, а выход развертки i-й ячейки свертки и развертки р-кодов Фибоначчи соединен с i-M входом элемента ИЛИ, выход которого соединен с входом элемента задержки, (п+1)-й вход элемента ИЛИ соединен с единичным выходом первого разряда первого сдвигового регистра, а (п+2)-й вход элемента ИЛИ является входом начальной установки устройства. На чертеже приведена блок-схема предлагаемого устройства. В качестве примера рассмотрен случай, когда и . Устройство содержит ячейки 1 свертки и развертки р-кодов Фибоначчи, предназначенные для хранения исходной и промежуточной форм представления числа, а также для выполнения операций свертки и развертки над кодом, первый сдвиговый регистр 2, предназначенный для хранения управляющего сигнала развертки, второй сдвиговый регистр 3, предназначенный для хранения управляющих сигналов свертки, элемент 4 ИЛИ, предназначенный для выработки сигнала установки в исходное состояние первого сдвигового регистра 2 и второго сдвигового регистра 3 через элемент 5 задержки, предназначенный для временной задержки сигнала установки на время, необходимое для окончания переходных процессов в ячейке 1 для приведения -кодов Фибоначчи к минимальной форме. Устройство имоет мход 6 синхронизации, соедияеип1,11 .- лравляющими входами 7 и 8 соответственно первого сдвигового регистра 2 и второго сдвигового регистра 3, вход 9 начальной установки устройства(Соединенный с входом 10 элемента 4 ИЛИ, а также информационные входы 11 и информационные выходы 12 устройства. Единичные выходы 13 разрядов 2.42.10 первого сдвигового регистра 2 соединены соответственно с управляющими входами 14 развертки функциональных ячеек 1 устройства для приве дения Р-кодов Фибоначчи к минимальной форме, управляющие входы 15 свертки которых соединены соответственно с единичными выходами 16 раз рядов 3,1-3,7 второго сдвигового регистра 3, входы 17 элемента .4 ИЛИ соединены соответственно с выходами 18 развертки ячеек 1 устройства для приведения р-кодов Фибоначчи к мини мальной форме, вход 19 элемента 4 ШШ соединен с единичным выходом 13 разряда 2.1 первого сдвигового регистра 2, выход 20 элемента 4 ИЛИ соединен с входом 21 элемента 5-задержки, выход 22 которого соединен с входами 23 и 24 начальной установки соответс венно первого сдвигового регистра 2 и второго сдвигового регистра 3, пер вый управляющий вход 25 устройства сл жит для подачи потенциала О, второ управляющий вход 26 второго регистра 3 служит для подачи потенциала 1. Устройство работает следующим образом. Занесение исходной информации в устройство производится по информационным входам 1 Т. Пусть в исходном состоянии в ячейку занесен код 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 - в состояние 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 начальной установки соответственно первого

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

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

Продолжение таблицы

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

0111010000000000

0111001000000000

о 111001000000001

0111001000000011

0110111000000000

0110111000000001

0110111000000011

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

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