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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ.с присоединением заявки Ко 6 Об Р 5/00 Государственный комитет СССР по делам изобретений и открытий(088.8) Дата опубликования описания 150383 РОИСТВО ДИЯ ПРИВЕДЕНИЯ 1-К ИБОНАЧЧИ К ИИНИМАЛЬНОЙ ФОРИ эким ксущносведени жно,и ес разря 0 . 1 Исходный Изобретение относится к автомати ке и вычислительной технике и преимущественно может быть использовано в процессах специализированных отказоустойчивых вычислительных машин.Известно устройство для приведения кодов Фибоначчи к минимальной Фор ме, содержащее набор блоков свертки по числу разрядов минимизируемого кода, построенное на основе алгоритма минимизации, заключающегося в последовательном применении операций свертки двоичных разрядов 1.Недостатком такого устройства является необходимость больших временных затрат для приведения кодов Фибоначчи к минимальной Форме, что снижает производительность вычисли-. тельных машин.Наиболее бли предлагаемому по технической ти является устройство для при я р-кодов Фибоначчи к минимальной Форме, содержащее п однотипных блоков свертки, при.чем первый выход-го блока .свертки соединен с первым входом Я) "го и вторым входом 8 -2)-го блоков свер 5ки, второй выход с -го блока свертки является т -м информационным выходом устройства и соединен с тре тьим входом (9+0 -го и четвертым входом ф+2)-го блоков свертки, управляющий вход устройства соединен с пятыми входами всех блоков свертки, шестые входы каждого блока свертки являются информационными входами устройства 2.Недостатком известного устройства 15 является необходимость больших временных затрат для приведения 1-кодов Фибоначчи к минимальной Форме, которые возникают при поступлении на вход устройства кодов, требующих 20 выполнения смежных сверток, которыевыполняются строго последовательно. Работу устройства-прояснитьследующим приме1005024 Работа устройства 1 0 0 0 1 0 0 0 11 0 0 1 О. Минимизированныйкод 1 0 0 1 Вес разряда 21 13 8 5 3 2 1 5 О 1 О О 1 О 1 Исходный код Минимизированный код 0 1 0 0 0 О 1 В рассмотренном примере для минимизации исходного кода необходимо выполнить три операции свертки, из которых две - смежные, так как выполняются последовательно. В общем случае время минимизации Т исходного кода можно определить следующим образом: Тм = т "сэ фгде е - число смежных сверток;время выполнения однойоперации свертки. 20Цель изобретения - повышение быст-,родействия, уменьшение временныхзатрат для приведения 1-кодов Фибоначчи к минимальной форме.Поставленная цель достигается тем, 25что в устройство для приведения 1-кодов Фибоначчи к минимальной Форме,содержащее и блоков свертки, причем первый выход 1 -го блока свертки (0 = 1,2 и) соединен с первым входом (1 -1)-го и вторым входом (Р)-го блоков свертки, второй выход Р-го блока свертки является 9 -м информационным выходомустройства и соединен с третьим выходом Я+1) -го и четвертым входом(3 +2)-го блоков свертки, управляющий вход устройства соединен с пятыми входами Г -х блоков свертки,. шестые входы которых соединены с информационными входами устройства 4 О соответственно, третий выход. 0 -гоблока свертки соединен с седьмым входом ф +1)-го и восьмым входом (1 +2)-го блоков свертки, а девятый и десятый входы 1-го блока свертки соединены с четвертым выходом (1+2)-го и вторым выходом В+1)-го блоков .свертки соответственно.Кроме того, блок свертки содержит элементы И, ИЛИ, НЕ и, триггер, при- щ чем первый и второй входы блока подключены к первому и второму входам первого элемента ИЛИ соответственно, выход которого подключен к нулевому входу триггера, нулевой выход кото, рого подключен к первому входу первого элемента И, второй, третий и чет.вертый входы которого подключены к третьему, четвертому и пятому входам ,блока соответственно, выход первого элемента И подключен к первому выходу блока и к первому входу второго элемента ИЛИ, единичный выход триггера подключен к второму выходу блока, третий выход которого подключен к выходу второго элемента И, первый вход которого подключен к выходу второго элемента ИЛИ и к первому входу третьего элемента И, второй вхоц которого подключен к выходу элемента НЕ, вход которого подключен к второму входу второго элемента И и к выходу четвертого элемента И, нулевой выход триггера к четвертому выходу блока, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ,. второй вход которого подключен к шестому входу блока, а выход подключен к единичному входу триггера, седьмой вход блока подключен к третьему вхо-. ду первого элемента ИЛИ, восьмой вход блока подключен к второму входу второго элемента ИЛИ, девятый и десятый входы блока подключены к входам четвертого элемента И соответственно,.Введение дополнительных входов и выходов в каждом блоке свертки позволяет сократить время минимизации таких исходных кодов, которые требуют выполнения смежных сверток. При этом используется следующий метод минимизации. Если в 0 -м блоке выполняется усло вие свертки (6-й разряд кода равен"0", а И -1) -й и (И)- й разряды равны "1" ), -1 )-й и (О) -й разрядыкода обнуляются, однако запись еди-ницы в 3 -й разряд минимизируемогокода происходит только в том случае,если после этого не выполняется условие свертки для (0+2) -го разряда,Если условие свертки для Я+2)-горазряда выполняется, происходит обнуление +1) -го разряда, после чегоопределяется возможность записи единицы уже в (0+2)-й разряд и т,д.Рассматриваемый метод минимизации кодов можно пояснить следующимпримером,Формула изобретения В этом примере условие свертки выполняется для третьего разряда (т.е, :3). При этом необходимо произвести обнуление второго и первого разрядов, однако запись единицы в третий разряд производить не нужно. так как после этого выполняется условие свертки для пятого разряда, В этом случае необходимо обнулить четвертый разряд кода, а пятый разряд установить в единичное значение, так как для седьмого разряда условие свертки после этого не выполняется.В устройстве-прототипе для минимизации данного входного кода необ ходимо выполнить две смежные опеРации свертки 01001 Я 1 в010 Д 100- - 101010000).Метод, используемый в данном устройстве, позволяет выполнить только одну операцию свертки (010101 - ф 01010000 ), что и сокращает вре= мя минимизации кода.Структурная схема устройства для приведения 1-кодов Фибоначчи к мини мальной форме представлена на чертеже.Устройство содержит блок 1 свертки элементы И 2, ИЛИ 3, И 4, НЕ 5, И 6, ИЛИ 7 и 8, триггер 9 и элементы И 10, входы 11-14 свертки, выход 15 свертки, входы 16-19 свертки, выход 20 свертки, входы 21-24.свертки, выход 25 свертки.Устройство работает следующим образом.35Двоичная информация поступает на входы 11 устройства и через элементы ИЛИ 7 записывается в триггеры 9 блоков 1 свертки, находящиеся до прихода информации на входы 11 40 в нулевом состоянии. При подаче единичного сигнала на управляющий вход 23 устройства этот сигнал поступает на один из входов элемента И 10 всех блоков 1. Элемент И 10 анализи рует состояние триггеров 9-1) -го и -2 )-го блоков 1. На всех входах элемента И 10 присутствует единичный сигнал,.т.е. выполняться,условие свертки, если триггеры 9 О -1) -го 50 и Я)-го блоков 1 нахОдятся в единичном состоянии, а триггер 9 3 -го блока 1 - в нулевом и на управляющий вход.23 поступает единичный сигнал. В зХом случае на хде элемента И 10-го блока 1 вырабатывается единичный сигнал, который с выхода 20 1 -го блока 1 свертки подается на вход 13 ф -Ц-го и вход 14 ф -2) -го блоков 1 и через элементы ИЛИ 8 записывает в триггеры 9 этих блоков нулевые сигналы.Если триггер 9+2) -го блока 1 установлен в нулевое состояние, а триггер 9 Я +1) -го блока 1 - в единичное, на выходе 25 Ц +2) -го бло ка 1 и выходе 20 И+ 1)-го блока 1 присутствуют единичные сигналы, которые поступают на входы 18 и 19 1 -го блока 1. В результате на выходе элемента И 4-го блока 1 устанавливается единичный сигнал, подготавливающий к открытию элемент И 2. В этом случае управляющий сигнал с выхода . элемента И 10 Р -го блока 1 через элемент ИЛИ 3 и элемент И 2 поступает на вход 16(+1)-го блока 1 и через элемент ИЛИ 8 устанавливает триггер 9 этого блока в нулевое состояние. Одновременно этот же сигнал поступает на вход 17 Я+2)-го блока 1.Если при этом триггер 9 ф+4)-го блока 1 находится в нулевом, а триггер 99+3)-го блока 1 - в единичном состояниито все перечисленные действия повторяются.Если триггер 9 ф+2)-го и 0+1) -го, блоков 1 установлены в состояния, отличные от упомянутых. на выходе элемента И 4 присутствует нулевой сигнал, который через элемент НЕ готовит к открытию элемент И 6. Управляющий сигнал с выхода элемента И 10 0 -го блока 1 в этом случае через элемеьты ИЛИ 3, И 6 и ИЛИ 7 устанавливает триггер 9 1 -го блока 1 в единичное состояние.По окончании управляющего сигнала свертки информация считывается с информационных выходов 20 устройства параллельно.Временные затраты на миними.зацию 6-разрядного кода, требующего выполнения смежных сверток, уменьшаются в данном устройстве в 2 раза по сравнению с устройством- прототипом. Выигрыш во времени минимизации возрастает с увеличением раэ" рядности кода, поступающего на вход устройства. 1. Устройство для приведения 1-кодов Фибоначчи к минимальной форме, содержащее и блоков свертки, причем первый выход 6 -го блока свертки ф,2, н ) соединен с первым входом Р)-го и вторым входом (В -2)-го блоков свертки, второй выход-го ,блока свертки является 2 -м информационным выходом устройства.и соединен с третьим входом ф+1) -го и четвертым входом И+2)-го блоков свертки, управляющий вход устройства соединен с пятыми входами-х блоков свертки, шестые входы которых соединены с информационными входами устройства соответственно, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, третий выход 0 -го блока свертки соединен с седьмым входом Я +1) -го и вось 1005024мым входом 8+2)-го блоков свертки, а девятый и десятый входы 6 -го бло- ка свертки соединены с четвертым выходом 0 +2)"го и вторым выходом И +1)-го блоков свертки соответственно.2. Устройство по п.1, о т л ич а ю .щ е е с я тем, что блок сверт ки содержит элементы И, ИЛИ, НЕ и триггер, причем первый и второй вхо ды блока подключены к первому и второму входам первого элемента ИЛИ соответственно, выход которого подключен к нулевому входу триггера, нулевой выход которого подключен к первому входу первого .элемента И, второй, третий и четвертый входы которого подключены к третьему, чет вертому и пятому входам блока соответственно, выход первого элемента И подключен к первому выходу блока и к первому входу второго элемента ИЛИ, единичный выход триггера подключен к второму выходу блока, .третий выход которого подключен к выходу второго элемента И, первый вход которого подключен к выходу второго элемента ИЛИ и к первому входу третьего элемента И, второй вход которого подключен к выходу элемента НЕ, вход которого подключен к второму входувторого элемента И и .к выходу четвертого элемента И, нулевой выходтриггера подключен к четвертому выходу блока, выход третьего элемента Иподключен к первому входу третьегоэлемента ИЛИ, второй вход которого 10 подключен к шестому входу блока,а выход подключен к единичному входутриггера, седьмой вход блока подключен к третьему входу первого элемента ИЛИ, восьмой вход блока подключен )5 к второму входу второго элемента ИЛИ,девятый и десятый входы блока подключенык входам четвертого элемента И.соответственно. 20Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР1005024 аж 704 Подписи Филиал ППП "Патентф,г,Уаг ВНИИПИ Заказ 1899/б