Устройство для приведения р-кодов фибоначчи к минимальной форме
Изобретение относится к вычислительной технике и может быть использовано для приведения P-кодов Фибоначчи к минимальной форме. Цель изобретения - повышение быстродействия. Устройство для приведения P-кодов Фибоначчи к минимальной форме содержит группу информационных входов, тактовый вход, группу информационных выходов, выход признака конца формирования кода, блокисвертки,каждый из которых содержит элементы ИЛИ, элементы И и триггер. Введение дополнительных связей и изменение функциональной схемы блока свертки обусловило изменение алгоритма работы устройства таким образом, что длительность формирования минимального кода стала зависеть от числа фактически выполняемых сверток, т.е. увеличилось среднее быстродействие устройства. 1 с.п.ф, 1 з.п.ф. 3 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (19) (11) А1 (51)5 Н 03 И 7/30
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И OTHPbfTHRM
ПРИ ВАНТ СССР (21) 4445768/24-24 (22) 21.06.88 (46) 28.02.90. Бнш. И - 8 (71) Пермский политехнический институт (72) Л.Ф. Викентьев, А.А. Клюкин, С.Ю. Погодина, О.Л. Лепихина и И.О. Синегубов (53) 681.3(088.8) (56) Авторское свидетельство СССР.
9 1392554, кл. Н 03 M 7/30, 1986. . Авторское свидетельство СССР
Ф 842782, кл. Н 03 И 7/30, 1979.
2 (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КО-
ДОВ ФИБОНАЧЧИ К ИИНИИАЛЬНОИ ФОРИЕ (57) Изобретение относится к вычислительной технике и может быть использовано для приведения р-кодов
Фибоначчи к минимальной форме. Цель изобретения — повьппение быстродейст.— вия. Устройство для приведения р-кодов Фибоначчи к минимальной форме содержит группу информационных входов, тактовый вход, группу информационных выходов и выход признака кон1547074 а формирования кода, блоки свертки, Каждый иэ которых содержит элементы
ИЛИ, элементы И, триггер. Введение дополнительных связей и изменение функциональной схемы блока свертки обусловило изменение алгоритма рабоИзобретение относится к вычислиельной технике и может быть испольовано для приведения р-кодов Фибоаччи к минимальной форме.
Целью изобретения является павы! щенке быстродействия.
На. фиг. 1 изображена схема устройства для приведения р-кодов Фибояаччи к минимальной форме; на фнг.2 ок-схема блока свертки; на фиг.3— ременные диаграммы работы для конкретного примера.
Устройство (фиг. 1) содержит груп 1у информационных входов 1 устройстФа тактовый вход 2 устройства, и блоков 3 свертки, каждый из которых имеет шестой 4, пятый 5, третий 6, четвертый 7, седьмой 8, первый 9 и торой 10 входы, второй 11, третий
12 и первый 13 выходы, группу ин- 30 формационных выходов 14 устройства
1 выход 15 признака конца формирования кода устройства.
Блок 3 свертки (фиг. 2) содержит йервый и второй элементы ИЛИ 16 и
17, второй и первый элементы И 18 и
19:и. триггер 20.
Устройство (фиг. 1) работает слеДуюшим образом.
Перед началом работы все триггеры 40 .20 блоков 3 свертки устанавливаются
s нулевое состояние подачей сигнала по входу объединяющему все входы установки в нули (не показаны).Сиг-. налы, поступающие по;информационным 45 входам 1 устройства, устанавливают. триггеры 20 в состояния, соответствующие поданным разрядам исходного кода. !
Рассмотрим случай, когда минимизируется 1-код Фибоначчи для п==б:
Иомер блока 3 свертки 654321 .Вес разряда 853211
1-Код Фибоначчи 010101
Временные диаграммы работы устройства для этого случая приведены на фиг ° 3.
При подаче кода на установочные входы триггеров 20 триггеры Т1, Т3 ты устройства таким образом, что длительность формирования минимального кода стала зависеть от числа фактически выполняемых сверток, т. ° е. увеличилось среднее быстродействие устройства. 1 з.п. ф-лы, 3 ил. и Т5 устанавливаются в состояние "1", а триггеры Т2, Т4 и Тб — в состояние
"0". Элемент И19 каждого блока 3 свертки анализирует состояние трех триггеров, хранящих значения 1-ro, (1"1)-ro и (1-2)-ro разрядов, и фор" мирует на выходе признак свертки Х =
0 e 0 е- i Ч е-гЕсли Х = 1, то над соответствующими разрядами кода Фибоначчи должна быть выполнена операция свертки.Для рассматриваемого случая признак сверт.— ки, равный 1, будет вырабатываться на выходе элемента И19 второго блока 3 свертки.
С выхода элемента И19 признак . свертки через элемент ИЛИ16 подается на первый вход элемента ИЛИ 17, который предназначен для выработки признака конца формирования разряда Zg.
Для 1-ro блока 3 свертки признак конца Z < формируется как объединение сигнала признака конца, поступившего с (1+1)-ro блока 3 свертки, и признаков свертки 1-го (1+1)-го и (1+2)-го блоков 3:
Одновременно с формированием приз нака конца сигнал свертки Х постуГ пает.на первый вход элемента И 18.
Элемент И18 каждого блока 3 свертки используется для синхронной;подачи сигнала U на счетные входы триггеров 20, что устраняет эффект гонок.
Выработка сигнала U< на выходе элемента И 18 осуцествляется в момент подачи на второй вход этого элемента управляющего сигнала У по входу 2:
U = х(х vх „чх, ).
В рассматриваемом примере единичный сигнал свертки Х подается на входы элементов ИЛИ16 первого и второго блоков 3 свертки. Элементы
ИЛИ 16 пропускают эти единичные сигналы на первые входы элементов И 18 и
47074
10
20 четвертыми входами k = Х (k < р+2) блоков свертки.
2. Устройство по п.1 о т л и
° ° 1 ч а ю щ е е с я тем, что блок свертки содержит первый и второй элементы
40
Формула изобретения
1. Устройство для приведения р-кодов Фибоначчи к минимальной форме
Ф содержащее и блоков свертки, причем первый выход 1-го блока свертки соединен с первым входом (1-1)го и вторым входом (1-р-1)-ro блоков свертки, второй выход 1-го блока свертки сое50
5 и элементов ИЛИ 17, на выходе 15 устройства появляется сигнал признака конца формирования кода, равный единице. По входу 2 устройства подается управляющий сигнал У, при этом на выходах элементов И 18 первого и второго блоков 3 свертки появляются единичные сигналы U u U
2 подаваемые на счетные входы триггеров 71 и Т2, Триггеры 71 и Т2, срабатывая по заднему фронту входного сигнала, изменяют состояние на противоположное; триггер Т1 переключается из единичного состояния в нулевое, а триггер Т2 — из нулевого в единичное.
Устройство из исходного состояния
010101 переходит в состояние 010110.
После подачи по входу 2 устройства еще двух управляющих сигналов У на выходе 15 устройства появляется сигнал признака конца формирования кода, равный нулю. При этом подача на вход
2 серии управляющих сигналов Y прекращается. На информационных выходах устройства получается результирующий минимальный код Фибоначчи 100000.
Таким образом, длительность подачи серии сигналов Y меняется в зависимости от количества сверток, фактически выполняемых при формировании устройством минимального кода Фибоначчи. Самой длительной по времени является серия сигналов Y для приведения "тяжелого" кода Фибоначчи типа
1010101010101 0101011. Для приведения
"легкого" кода Фибоначчи типа
01001001001001001001 длительность серии сигналов Y равна нулю. Кроме того,в устройстве каждый из блоков свертки содержит меньшее количество логических Элементов при сохранении функциональных воэможностей прототипа. динен с 1-ым информационным выходом группы устройства, третьим входом (1+1)-го и четвертым входом (1+р+1)ro блоков свертки, тактовый вход устройства соединен с пятыми входами всех блоков свертки, информационные входы группы устройства соединены с шестыми входами соответствующих блоков свертки, о т л и ч а ю щ е е с я тем, что, с целью повьпления быстродействия, третий выход 1-го блока свертки (при 1 > 1) соединен с седьмым входом (1-1)-ro блока свертки, третий выход первого блока свертки является выходом признака конца формирования кода устройства, вторые входы i=X (i v и-р-1) и первый и седьмой входы и-ro блоков свертки соединены с входом логического нуля устройства, вход логической единицы которого соединен с третьим входом первого и
ИЛИ, первый и второй элементы И и триггер, причем выход первого элемента И соединен с первым выходом блока свертки и первым входом первого элемента ИЛИ, второй и третий входы которого соединены с первым и вторым входами блока свертки соответственно, выход первого элемента ИЛИ соединен с первыми входами второго элемента
И и второго элемента ИЛИ, второй вход второго элемента И соединен с пятым входом блока свертки, выход второго элемента И соединен со счетным входом триггера, шестой вход блока свертки соединен с входом установки в
"1." триггера, прямой выход которого соединен с вторым выходом блока свеитки, а инв ер с ный выход — с первым входом первого элемента И, второй и третий входы которого соединены с третьим и четвертым входами блока свертки соответственно, второй вход второго элемента ИЛИ соединен с седьмым входом блока свертки, выход второго элемента ИЛИ соединен с третьим выходом блока свертки.
1547074
gg
Оу
9q
Ду
g) gg 2р 6g Х ,9 д g jY Zlj ,((Хз Ую Уу zg Ур М 2f /, ФизЗ Составитель А. Клюев Редактор А. Лежнина Техред Jl.Сердюкова Корректор В. Гирняк Заказ 85 - Тираж 659 Подписное ВНИИПИ Государственного комитета по изобретениям и открьггиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", r, Ужгород, ул. Гагарина, 101
