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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 163349 А 09 1)5 Н 03 М 7/30 ПИСАНИЕ ИЗОБРЕТЕНИЯ слид оначе маустрои тояние ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР А В ГОРСКОМУ СВИДЕТЕЛЬСТВ(46) 07.03.91. Бюл. 11 9171) Научно-производственное объединение космических исследований (72) Я.А.МамедовФ.А,Мамедови И.3.1 Кивотовский(56) Авторское свидетельство СССР Мф 1092489, кл. Н 03 М 7/30, 1982.Авторское свидетельство СССР Мф 951291, кл. Н 03 М 7/30, 1980.(54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ (57) Изобретение относится к выч тельной технике и предназначено получения как минимальной, так гих форм представления кодов Фи чи. Цель изобретения - расширен функциональных воэможностей за получения промежуточных кодовых бинаций и выполнения преобразов р-кодов Фибоначчи. Устройство с жит информационный вход 1, инфо ционный выход 2, регистр 3 сдви блок 4 свертки, элементы ИЛИ 5 элементы И 10-13, элементы НЕ 14 и 15, триггеры6 и 17, задающий генератор 18, регистр 19 сдвига, счетчики 20 и 21, вход 22 запуска и сигналь ный выход 23 устройства. В исходный момент регистр 3 сдвига находится в режиме параллельной записи информации По сигналу запуска с входа 22 и-разрядный код с вход; 1 записывается в регистр 3 сдвига. Дальнейшая работа устройства определяется сигналом с выхода блока 4 свертки и состоянием регистров 3 и 19 сдвига. Если после каждого такта работы устройства условие свертки для очередных (р+1)-х разрядов не выполняется, в счетчик 20 записывается единица, его переполнение по выходу 23 сигнализирует о получении на выходе 2 промежуточной фор мы представления исходного кода. Сигнал переполнения счетчика 20 увеличивает содержимое счетчика 21 на единицу. Переполнение счетчика 21 сигнализирует об окончании процесса приведения кода к минимальной форме, нство приводится в исходное сос10 Изобретение относится к вычислительной технике и предназначено для приведения кодов Фибоначчи к минимальнойформе.Целью изобретения является расширение функциональных возможностей за счетполучения промежуточных кодовых комбинаций и выполнения преобразованияр-кодов Фибоначчи.На чертеже приведена схема устройства для приведения кодов Фибоначчи к минимальной форме.Устройство содержит информационный вход 1, информационный выход 2, 15первый регистр 3 сдвига, блок 4 сверт.ки, пятый элемент ИЛИ 5, с второгопо четвертый элементы ИЛИ 6-8, первый элемент ИЛИ 9, с первого по четвертый элементы И 10-13, первый 14 10и второй 15 элементы НЕ, первый 16и второй 17 триггеры, задающий генератор 18, второй регистр 19 сдвига,второй 20 и первый 21 счетчики,вход 22 запуска, сигнальный выход 23, 25Устройство работает следующим образом,В исходном состоянии регистры 3и 19 сдвига, счетчики 20 и 21 содержат нули, Триггеры 16 и 17 находятся 30в нулевом состоянии. Сигнал логического 0 с прямого выхода триггера 16запрещает работу задающего генератора 18. Сигнал логической 1 с инверсного выхода триггера 16 через элементы ИЛИ 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 упО равления. Одновременно единичный сигнал поступает на второй вход элемента И 10, на выходе которого также присутствует единичный сигнал, и соответственно, на втором входе задания режима регистра 3 сдвига появится единичный сигнал, а на первом входе задания режима - нулевой. Перед поступлением очередного синхросигнала регистр 3 сдвига находится в режиме сдвига в сторону младших разрядов (сдвиг вправо) с занесением нуля в старший разряд. С поступлением очередного синхросигнала содержимое триггера 17 заносится в младший разряд регистра 19 сдвига; На прямом выходе младшего раз6 6нимальной форме блок 4 свертки вьг. полняется на одном элементе И. Формула изобретения Устройство для приведения кодов Фибоначчи к минимальной форме, содержащее первый регистр сдвига, блок свертки, первый и второй элементы ИЛИ, с первого по четвертый элементы И, первый и второй элементы НЕ, первый и второй триггеры, задающий генератор и первый счетчик, причем вход запуска устройства соединен с входом установки в "1" первого триггера, вход установки н 0" которого соединен с выходом переполнения первого счетчика, выход задающего генератора соединен с первым входом второго элемента И, выход старшего разряда первого регистра сдвига соединен с первым входом трето элемента И, выход которого и в.ход четвертого элемента П соединены соответственно с входами первого элемента ИЛИ, выход которого соединен с входом разряда, вдвигаемого при сдвиге в сторону старших разрядов, первого регистра сдвига, входы с (р+2)-го по (и+1+р)-й(р - параметр кода, и - разрядностькода) разрядов информационного входакоторого соединень. соответственно свходами разрядов информационноговхода устройства, выход первого элемента НЕ соединен с входом установкив в 1" второго триггера, выходы двухстарших разрядов первого регистрасдвига соединены соответственно с первым и вторым входами блока свертки,выходы разрядов с (р+2)-го по (и+р++)-й первого регистра сдвига являются выходами старших разрядов информационного выхода устройства, о т -л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей за счет получения промежуточных кодовых комбинаций и выполненияпреобразования р-кодов Фибоначчи, оносодержит второй регистр сдвига, второй счетчик, с третьего по пятыйэлементы ИЛИ причем выход (р+1)-горазряда первого регистра сдвига является выходом младшего разряда инфор 5 163349 ряда этого регистра появляется единичный сигнал, а на инверсном выходе младшего разряда - нулевой. Единичный сигнал с выхода младшего разряда регистра 19 сдвига через элементы И 13 и ИЛИ 9 поступает на вход сдвигаемого разряда регистра 3 сдвига и последний переводится в режим сдвига влево. После поступления очередного синхросигна-О ла в младший разряд регистра 3 сдвига заносится единица и содержимое регистра 3 оказывается сдвинутым на разряд влево. В регистре 19 также происходит сдвиг информации и на инверсном выходе второго разряда регистра появляется нулевой сигнал . Этим сигналом элементы И 12 и 3 закрыты и на выходе элемента ИЛИ 9 присутствует нулевой сигнал, Таким образом, последую щие р+1 тактов после очередного сдвига влево содержимого регистра 3 сдвига в младший его разряд заносятся нули независимо от результата свертки в блоке 4. После р+1 тактов на прямом выходе последнего (р+2)-го разряда регистра 9 сдвига появляется единичный сигнал, который поступает на второй вход элемента И 11 и после поступления очередного синхросигнала через элементы И 11 и ИЛИ 8, регистр 19 сдвига и триггер 17 устанавливается в нулевое состояние. Описанный .крыше процесс повторяется до переполнения счетчика 20, модуль пересчета которого равен и+р+2, Сигнал переполнения этого счетчика по выходу 23 сигнализирует о получении на выходе 2 промежуточной кодовой модификации исходного кода, над которым производится операция приведения к минимальной форме. Таким образом, в устройстве возможно получение промежуточных форм, кодов Фибоначчи. Сигнал переполнения счетчика 20 увеличивает содержимое счетчика 21 на единицу. Иодуль пересчета счетчика 21 выбирается равным и/р+1, поскольку большего количества сверток в и-разрядном коде Фибоначчи невозможно. Переполнение счетчика 21 сигнализирует о полном окончании процесса приведения кода к минимальной форме и переводит триггер 16 в исходное состояние55 Содержимое старших п+1 разрядов регистра 3 сдвига соответствует минимальной форме исходного числа. Для приведения 1-го кода Фибоначчи к мимационного выхода устройства, выход(и+р-К)-го разряда первого регистра сдвига соединен с (К+2)-м входом блока свертки (К 1 р),выход которого соединен с входом первого элеРедактор Н,Лазаренко Корректор В,Гирняк Заказ 622 Тираж 455 Подписное ВНИИПИ Государственного комитет но изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д, 4/5Производственно-издательскин комбинат "Патент", г,ужгород, ул. Гагарина,10 мента НЕ, вход запуска устройства соединен с первым входом пятого элемента ИЛИ, с входами установки в "О" первого и второго счетчиков, входыр-младших разрядов информационноговхода первого регистра сдвига соединены с входом нулевого потенциала устройства,вход младшего разряда информационного входа устройства соединен свходом (р+1)-го разряда информационного входа первого регистра сдвига,вход разряда, вдвигаемого при сдвигев сторонумладших разрядов, которого соединен с входом нулевого потенциала устройства, выход второго элемента И соединен с первым входом четвертого элемента ИЛИ, второй входкоторого соединен с входом запускаустройства, выход четвертого элемента 20ИЛИ соединен с входами установки в"О" второго триггера и второго регистра сдвига, синхровход которого соединен с вторым входом пятого элемента ИЛИ, синхровходом второго счетчика 25и выходом задающего гЕнератора, прямойвыход первого триггера соединен свходом запуска задающего генератора,инверсный выход первого триггера соединен с первыми входами третьего и второго элементов ИЛИ, выходы которыхсоответственно соединены с первым ивторым входами задания режима первогОрегистра сдвига, синхровход первогорегистра сдвига соединен с выходомпятого элемента ИЛИ, выход первогоэлемента И соединен с вторым входомвторого элемента ИЛИ и входом второго элемента НЕ, выход которого соединен с вторым входом третьего элемента ИЛИ и входом разрешения счетавторого счетчика, выход переполнениякоторого является сигнальным выходомустройства и соединен с синхровходомпервого счетчика, выход второго триггера соединен с информационным входом третьего регистра сдвига, инверсный выход первого разряда которогои выход блока свертки соединены соответственно с первым и вторым входамипервого элемента И, прямые выходы первого и (р+2)-го разрядов второго регистра сдвига соединены соответственно с первым входом четвертого элемента И и вторым входом второго элемента И, инверсный выход М-го (М= 2 р+2) разряда второго регистрасдвига соединен с М-ми входами третьего и четвертого элементов И.