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

 

Изобретение относится к вычислительной технике и предназначено для получения как минимальной, так и других форм представления кодов Фибоначчи . Цель изобретения - расширение функциональных возможностей за счет получения промежуточных кодовых комбинаций и выполнения преобразования р-кодов Фибоначчи. Устройство содержит информационный вход 1, информационный выход 2, регистр 3 сдвига, блок 4 свертки, элементы ИЛИ 5-9, элементы И 10-13, элементы НЕ 14 и 15, триггеры 16 и 17, задающий генератор 18, регистр 19 сдвига, счетчики 20 и 21, вход 22 запуска и сигнальный РЫХОД 23 устройства. В исходный момент регистр 3 сдвига находится в режиме параллельной записи информации. По сигналу запуска с входа 22 п-разрядный код с вход, 5 1 записывается в регистр 3 сдвига. Дальнейшая работа устройства определяется сигналом с выхода блока 4 свертки и состоянием регистров 3 и 19 сдвига. Если после каждого такта работы устройства условие свертки для очередных (р+1)-х разрядов не выполняется, в счетчик 20 записывается единица, его переполнение по выходу 23 сигнализирует о получении на выходе 2 промежуточной формы представления исходного кода. Сигнал переполнения счетчика 20 увеличивает содержимое счетчика 21 на единицу . Переполнение счетчика 21 сигнализирует об окончании процесса приведения кода к минимальной форме, и устройство приводится в исходное состояние . 1 ил. Ю ф оо со 4ь СО О5

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

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

РЕСПУБЛИК

ÄÄSUÄÄ 1633496 А1 щ)5 " 03 М 7/30

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

К A BTOPCKOMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4698677/24 (22) 10.05.89 (46) 07.03.91. Бюл. Р 9

l,71) Научно-производственное объединение космических исследований (72) Я.А.Мамедов,.Ф.А,Мамедов и И.Ç.Животовский (53) 681,3(088.8) (56) Авторское свидетельство СССР

М 1092489, кл. H 03 M 7/30, 1982.

Авторское свидетельство СССР

951291, кл ° Н 03 М 7/30, 1980. (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ КОДОВ

ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ (57) Изобретение относится к вычислительной технике и предназначено для получения как минимальной, так и других форм представления кодов Фибоначчи. Цель изобретения — расширение функциональных воэможностей за счет получения промежуточных кодовых комбинаций и выполнения преобразования р-кодов Фибоначчи. Устройство содержит информационный вход 1, информационный выход 2, регистр 3 сдвига, блок 4 свертки, элементы ИЛИ 5-9, 2 элементы И 10-13, элементы HE 14 и15, триггеры l6 и 17, задающий генератор 18, регистр 19 сдвига, счетчики 20 и 21, вход 22 запуска и сигнальный выход 23 устройства. В исходный момент регистр 3 сдвига находится в режиме параллельной записи информации.

По сигналу запуска с входа 22 и-разрядный код с вход 1 записывается в регистр 3 сдвига. Дальнейшая работа устройства определяется сигналом с выхода блока 4 свертки и состоянием регистров 3 и 19 сдвига. Если после каждого такта работы устройства условие свертки для очередных (р+1)-х разрядов не выполняется, в счетчик 20 записывается единица, его переполнение по выходу 23 сигнализирует о получении на выходе 2 промежуточной формы представления исходного кода. Сигнал переполнения счетчика 20 увеличивает содержимое счетчика 21 на единицу. Переполнение счетчика 21 сигнализирует об окончании процесса приведения кода к минимальной форме, н устройство приводится в исходное состояние. 1 ил.

1633496!

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

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

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

Устройство содержит информационный вход 1, информационный выход 2, 15 первый регистр 3 сдвига, блок 4 свертки, пятый элемент ИЛИ 5, с второго по четвертый элементы ИЛИ 6-8, первый элемент ИЛИ 9, с первого по четвертый элементы И 10-13, первый 14 1О и второй 15 элементы НЕ, первый 16 и второй 17 триггеры, задающий генератор 18, второй регистр 19 сдвига, второй 20 и первый 21 счетчики, вход 22 запуска, сигнальный выход 23. 25

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

В исходном состоянии регистры 3 и 19 сдвига, счетчики 20 и 21 содержат нули. Триггеры 16 и 17 находятся 30 в нулевом состоянии. Сигнал логического 0 с прямого выхода триггера 16 запрещает работу задающего генератора 18 ° Сигнал логической 1 с инверсного выхода триггера 16 через элемен- 35 ты ИЛИ 6 и 7 поступает на входы задания режима регистра 3 сдвига и определяет режим его работы. В исходном состоянии регистр 3 находится в режиме параллельной записи информации. По щ входу 1 подается и-разрядный код, подлежащий приведению к минимальной форме. Одновременно по входу 22 поступает сигнал запуска. По этому сигналу, поступающему через элемент ИЛИ 5 на синхровход регистра 3 сдвига, последний принимает входной код, причем этот код записывается в п старших разрядах регистра 3 сдвига, в младшие р разрядов заносится нуль, а в (Р+1)-й разряд дополнительно заносится содержимое младшего разряда кода, поступающего по входу 1. Одновременно сигнал запуска дополнительно обнуляет счетчики 20 и 21 и через элемент ИЛИ 8 второй триггер !7,и ре-

55 гистр 19 сдвига. Сигнал запуска пере-, водит триггер 6 в единичное состояние и разрешает работу задающего генератора 18, под воздействием синхросигналов которого осуществляется сдвиг информации в регистрах 3 и 19 сдвига и увеличение содержимого счетчика 20. Блок 4 свертки осуществляет проверку условия свертки для текущих (р+1)-х разрядов исходного кода.

Дальнейшая работа устройства определяется сигналом с выхода блока 4 свертки. Если после каждого такта работы условие свертки для очередных (р+1)-х разрядов не выполняется, то на его выходе присутствует нулевой сигнал, элемент И 10 закрыт и на его выходе присутствует нулевой сигнал.

Поэтому на выходе элемента НЕ 15 единичный сигнал, который разрешает работу счетчика 20 и через элемент

ИЛИ 7 поступает на первый вход задания режима регистра 3 сдвига, на втором входе задания режима которого присутствует нулевой сигнал с выхода элемента ИЛИ 6, поскольку триггер 16 находится в единичном состоянии. При этом регистр 3 сдвига находится в режиме сдвига информации в сторону старших разрядов (условно влево). Поскольку регистр 19 сдвига содержит. нули, то элемент И 12 открыт для прохождения информации. Содержимое старшего разряда регистра 3 сдвига через элементы И 12 и ИЛИ 9 поступает на вход сдвигаемого разряда регистра 3 сдвига. После поступления очередного синхросигнала содержимое этого регистра сдвигается влево, а в младший разряд заносится значение сдвигаемого разряда. Если же условие свертки выполняется, то на выходе блока 4 свертки появляется единичный сигнал, который через элемент НЕ 14 установит в единичное состояние триггер 17 уп0 равления. Одновременно единичный сигнал поступает на второй вход элемента

И 10, на выходе которого также присутствует единичный сигнал, и соответственно, на втором входе задания режима регистра 3 сдвига появится единичный сигнал, а на первом входе задания режима — нулевой. Перед поступлением очередного синхросигнала регистр 3 сдвига находится в режиме сдвига в сторону младших разрядов (сдвиг вправо) с занесением нуля в старший разряд. С поступлением очередного синхросигнала содержимое триггера 17 заносится в младший разряд регистра 19 сдвига; На прямом выходе младшего раз6 6 нимальной форме блок 4 свертки вьгполняется на одном элементе И.

Ф о р м у л а и з о б р е т е н и я

Устройство для приведения кодов

Фибоначчи к минимальной форме, содержащее первый регистр сдвига, блок свертки, первый и второй элементы ИЛИ, с первого по четвертый элементы И, первый и второй элементы НЕ, первый и второй триггеры, задающий генератор и первый счетчик, причем вход запуска устройства соединен с входом установки в 1 первого триггера, вход установки н О которого соединен с выходом переполнения первого счетчика, выход задающего генератора соединен с первым входом второго элемента И, выход старшего разряда первого регистра сдвиг . соединен с первым входом трет с1: .1лемента И, выход которого и в; хсд четвертого элемента П соединены соответственно с входами первого элемента ИЛ!1, выход которого соединен с входом разряда, вдвигаемого при сдвиге в сторону старших разрядов, первого регистра сдвига, входы с (р+2)-го по (п+1+р)-й (р — параметр кода, и - разрядность кода) разрядов информационного входа которого соединень. соответственно с входами разрядов информационного входа устройства, выход первого з-лемента НЕ соединен с входом установки в "1" второго триггера, выходы двух старших разрядов первого регистра сдвига соединены соответственно с первым и вторым входами блока свертки, выходы разрядов с (р+2)-го по (n+p+

+1)-й первого регистра сдвига являются выходами старших разрядов информационного выхода устройства, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей за счет получения промежуточных кодовых комбинаций и выполнения преобразования р-кодов Фибоначчи, оно содержит второй регистр сдвига, второй счетчик, с третьего по пятый элементы ИЛИ причем выход (р+1)-го разряда первого регистра сдвига является выходом младшего разряда инфор5 163349 ряда этого регистра появляется единичный сигнал, а на инверсном выходе младIIIего разряда — нулевой. Единичный сигнал с выхода младшего разряда регистра 19 сдвига через элементы И 13 и ИЛИ 9 поступает на вход сдвигаемого разряда регистра 3 сдвига и последний переводится в режим сдвига влево. После поступления очередного синхросигна-!О ла в младший разряд регистра 3 сдви-. га заносится единица и содержимое регистра 3 оказывается сдвинутым на разряд влево. В регистре !9 также происходит сдвиг информации и на инверсном выходе второго разряда регистра появляется нулевой сигнал . Этим сигналом элементы И 12 и !3 закрыты и на выходе элемента ИЛИ 9 присутствует нулевой сигнал, Таким образом, последую- 7,! щие р+1 тактов после очередного сдвига влево содержимого регистра 3 сдвига в младший его разряд заносятся нули независимо от результата свертки в блоке 4. После р+1 тактов на прямом выходе последнего (р+2)-го разряда регистра 19 сдвига появляется единичный сигнал, который поступает на второй вход элемента И 11 и после поступления очередного синхросигнала через элементы И 11и ИЛИ8, регистр 19 сдвига и триггер 17 устанавливается в нулевое состояние. Описанный II.Ime процесс повторяется до переполнения счетчика 20, модуль пересчета которого равен n+p+2. Сигнал переполнения этого счетчика по выходу 23 сигнализирует о получении на выходе 2 промежуточной кодовой модификации исходного кода, над которым производится операция приведения к минимальной форме. Таким образом, в устройстве возможно получение промежуточных форм, кодов Фибоначчи. Сигнал переполнения счетчика 20 увеличивает содержимое счетчика 21 на единицу. Иодуль пересчета счетчика 21 выбирается равным

n/p+1, поскольку большего количества сверток в и-разрядном коде Фибоначчи невозможно. Переполнение счетчика 21 сигнализирует о полном окончании процесса приведения кода к минимальной форме и переводит триггер 16 в исходное состояние °

Содержимое старших и+1 разрядов регистра 3 сдвига соответствует минимальной форме исходного числа. Для приведения 1-ro кода Фибоначчи к мимационного выхода устройства, выход (n+p-К)-го разряда первого регистра сдвига соединен с {К+2)-м входом блока свертки (К l...р-l),выход которого соединен с входом первого эле1633496

Составитель А, Клюев

Texpeд Л. Олийнык

Редактор Н.Лазаренко

Корректор В.Гирняк

Заказ 622

Тираж 455

Подписное

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

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

Производственно-издатель< кин комбинат "Патент", г.ужгород, ул. Гагарина,101 мента НЕ, вход запуска устройства соединен с первым входом пятого элемента ИЛИ, с входами установки в "0" первого и второго счетчиков, входы р-младших разрядов информационного входа первого регистра сдвига соединены с входом нулевого потенциала устройства,вход младшего разряда информационного входа устройства соединен с входом (р+1)-го разряда информационного входа первого регистра сдвига, вход разряда, вдвигаемого при сдвиге в сторону младших разрядов, которого соединен с входом нулевого потенциала устройства, выход второго элемента И соединен с первым входом четвертого элемента ИЛИ, второй вход которого соединен с входом запуска устройства, выход четвертого элемента 2О

ИЛИ соединен с входами установки в

"0" второго триггера и второго регистра сдвига, синхровход которого соединен с вторым входом пятого элемента ИЛИ, синхровходом второго счетчика 25 и выходом задающего гЕнератора, прямой выход первого триггера соединен с входом запуска задающего генератора, инверсный выход первого триггера соединен с первыми входами третьего и второго элементов ИЛИ, выходы которых соответственно соединены с первым и вторым входами задания режима первого регистра сдвига, синхровход первого регистра сдвига соединен с выходом пятого элемента ИЛИ, выход первого элемента И соединен с вторым входом второго элемента ИЛИ и входом второго элемента VE, выход которого соединен с вторым входом третьего элемента ИЛИ и входом разрешения счета второго счетчика, выход переполнения которого является сигнальным выходом устройства и соединен с синхровходом первого счетчика, выход второго триггера соединен с информационным входом третьего регистра сдвига, инверсный выход первого разряда которого и выход блока свертки соединены соответственно с первым и вторым входами первого элемента И, прямые выходы первого и (р+2)-го разрядов второго регистра сдвига соединены соответственно с первым входом четвертого элемента И и вторым входом второго элемента И, инверсный выход М-го (М

= 2...р+2) разряда второго регистра сдвига соединен с М-ми входами третьего и четвертого элементов И.