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

Минимизированный код В рассмотренном примере для мини миэации исходного кода необходимо выполнить три операции свертки, из которых две - смежные, так как выполняются последовательно. В общем случае время минимизации Т исходного кода можно определить следующим образом: где m - число смежных сверток; сь время выполнения одной операции свертки. Цель изобретения - повышение быс родействия, уменьшение временных затрат для приведения 1-кодов Фибо наччи к минимальной форме. Поставленная цель достигается те что в устройство для приведения 1-к дов Фибоначчи к минимальной форме, содержащее п блоков свертки, причем первый выход 2-го блока свертки (Р 1,2,...,п} соединен с первым входом (2 -1)-го и вторым входом (В-2)-го блоков свертки, второй выход ё-го блока свертки является К-м информационным выходом устройства.и соединен с третьим выходом (.Р+1) -го и четвертым входом (,Е+2/-го блоков свертки, управляющий вход устройства соединен с пяты ми входами -X блоков свертки,. шестые входы которых соединены с информационными входами устройства соответственно, третий выход. 8-го блока свертки соединен с седьмым входом (Р+1}-го и восьмым входом (2+2)-го блокрв свертки, а девятый и десятый входы -го блока свертку соединены с четвертым выходом JCP+2 и вторым выходом )-го блоков .свертки соответственно. Кроме того, блок свертки содержи элементы И, ИЛИ, НЕ и, триггер, причем первый и второй входы блока под ключены к первому и второму входам первого элемента ИЛИ соответственно выход которого подключен к нулевому входу триггера, нулевой выход которого подключен к первому входу перв го элемента И, второй, третий и чет .вертый входы которого подключены к третьему, четвертому и пятому входам .блока соответственно, выход первого элемента И подключен к первому выходу блока и к первому входу второго элемента ИЛИ, единичный выход триггера подключен к второму выходу блока, третий выход которого подключен к выходу второго элемента И, первый вход которого подключен к ВЕЛходу второго элемента ИЛИ и к первому входу третьего элемента И, второй вход которого подключен к выходу элемента НЕ .вход которого подключен к второму входу второго элемента Инк выходу четвертого элемента И, нулевой выход триггера к четвертому выходу блока, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого подключен к шестому входу блока, а выход подключен к единичному входу триггера, седьмой вход блока подключен к третьему вхо-. ду первого элемента ИЛИ, восьмой вход блока подключен к второму входу второго элемента ИЛИ, девятый и десятый входы блока подключены к входам четвертого элемента И соответственно. Введение дополнительных входов и выходов в каждом блоке свертки позволяет сократить время минимизации таких исходных кодов, которые требуют выполнения смежных сверток, При этом используется следующий метод минимизации. Если в -м блоке выполняется условие свертки (С-и разряд кода равен О, а (-1)-й и (-2)й разряды равны 1), (&-1)-й и(г-2;-й разряды кода обнуляются, однако запись единицы в 8-и разрйд минимизируемого кода происходит только в том случае, если после этого не выполняется условие свертки для (Р+2)-го разряда. Если условие свертки для(.2 + 2)-го разряда выполняется происходит обнуление U+1) -го разряда, после чего определяется возможность записи единицы уже в (2+2)-й разряд и т.д. Рассматриваемый метод миншлизаlyiH кодов можно пояснить следующим примером.

Минимизированный код В этом примере условие свертки выполняется для третьего разряда (т.е. ;ЗК При этом необходимо прои вести обнуление второго и первого разрядов, однако запись единихда в третий разряд производить не нужно, так как после этого выполняется условие свертки для пятого разряда. В этом случае необходимо обнулит,ь четвертый разряд кода, а пятый разряд установить в единичное значение, так как для седьмого разряда условие свертки после этого не выпол няется. И устройстве-прототипе для минимизации данного входного кода необходимо выполнить две смежные операции свертки(01001011 OlOgllOO- 01010000). - Метод, используемый в данном устройстве, позволяет выполнить тол ко одну операцию свертки (01001011 - -01010000), что и сокращает в ремя минимизации кода. Структурная схема устройства для приведения 1-кодов Фибоначчи к мини мальной форме представлена на черте же. Устройство содержит блок 1 сверт ки элементы И 2, ИЛИ 3, И 4, НЕ 5, И 6, ИЛИ 7 и 8, триггер 9 и элементы И 10, входы 11-14 свертки, выход 15 свертки, входы 16-19 свертки, выход 20 свертки, входы 21-24. сверт ки, выход 25 свертки. Устройство работает следующим об разом. Двоичная информация поступает на входы 11 устройства и через элементы ИЛИ 7 записывается в триггеры 9 блоков 1 свертки, находящиеся до прихода информации на входы 11 в нулевом состоянии. При подаче единичного сигнала на управляющий вход 23 устройства этот сигнал пост пает на один из входов элемента И 1 всех блоков 1. Элемент И 10 анализи рует состояние триггеров 9 (-1)-го и (Р-2)-го блоков 1. На всех входах элемента И 10 присутствует един ный сигнал, т.е. выполняться.условие свертки, если триггеры 9 (В-1)и(2-2)-го блоков 1 находятся в единичном состоянии, а триггер 9 В-го блока 1 - в нулевом и на управляющий вход.23 поступает единичный сиг нал. В эхом случае на выходе элемен та И 10 -го блока 1 вырабатывает ся единичный сигнал, который с выхо да 20 -го блока 1 свертки подается на вход 13 (В-ly-го и вход 14 (1-2) -го блоков 1 и через элементы ИЛИ 8 записывает в триггеры 9 зт блоков нулевые сигналы. Если триггер 9 S +2) -го блока 1 установлен в нулевое состояние, а триггер 9 {2 +1) -го блока 1 - в единичное, на выходе 25 (,Е +2)-го блока 1 и выходе 20(.6+ блока 1 присутствуют единичные сигналы, которые поступают на входы 18 и 19 -го блока 1. В результате .на выходе элемента И 4 1-го блока 1 устанавливается единичный сигнал подготавливающий к открытию элемент И 2. В эГом случае управляющий сигнал с выхода элемента И 10 Р-го блока 1 через элемент ИЛИ 3 и элемент И 2 поступает на вход 16(f+l)-ro блока 1 и через элемент ИЛИ 8 устанавливает триггер 9 этого блока в нулевое состояние. Одновременно этот же сигнал поступает на вход 17(И+2)-го блока 1. Если при этом триггер )-го блока 1 находится в нулевом, а триггер 9(,8+3)-го блока 1 - в единичном состоянии,.то все перечисленные действия повторяются. Если триггер 9 (t+2)-ro и (8+1)-го, блоков 1 установлены в состояния, отличные от упомянутых, на выходе элемента И 4 присутствует нулевой сигнал, который через элемент НЕ готовит к открытию элемент И б. Управляющий сигнал с выхода элемента И 10 Р -го блока 1 в этом случае через элементы ИЛИ 3. И б и ИЛИ 7 устанавливает триггер 9 -го блока 1 в единичное состояние. По окончании управляющего сигнала свертки информация считывается с информационных выходов 20 устройства параллельно. Временные затраты на минимизацию б-раэрядного кода, требующего выполнения смежных сверток, уменьшаются в данном устройстве в 2 раза по сравнению с устройствомпрототипом. Выигрьш во времени миними|зации возрастает с увеличением разфядности кода, поступающего на вход устройства. Формула изобретения 1. Устройство для приведения 1-кодов Фибоначчи к минимашьной форме, Ьодержащее п блоков свертки, причем первый выход С-го блока свертки (,6-1,2,.., п) соединен с первым входом )-го и вторым входом (В-2)-го блоков свертки, второй выход -го блока свертки является в-м информационным выходом устройства.и соединен с третьим входом (f+1J -го и четвертым входом (й+2)-го блоков свертки, управляющий вход устройства соединен с пятыли входами t-х блоков свертки, шестые входы которых соединена с информационньми входами устройства соответственно, от л ичающееся тем, что, с целью повышения быстродействия, третий выход Р-го блока свертки соединен с седьмым входом ХЕ+1}-го и весьмым входом 1К+2)-го блоков свертки а Девятый и десятый входы 6-го блока свертки соединены с четвертым выходом (В +2)-го и вторым выходом (. +1)-го блоков свертки соответственно. 2. Устройство по П.1, о т л ичаю щееся тем, что блок сверг ки содержит элементы И, ИЛИ, НЕ и триггер, причем первый и второй входы блока подключены к первому и второму входам первого элемента ИЛИ соответственно, выход которого подключен к нулевому входу триггера, нулевой выход которого подключен к первому входу первого элемента И, второй, третий и четвертый входы которого подключены к третьему, четвертому и пятому входам блока COQTветственно, выход первого элемента И подключен к первому выходу блока и к первому входу второго элемента ИЛИ, единичный выход триггера подключен к второму выходу блока, .третий выход которого подключен к выходу второго элемента И, первый вход которого подключен к выходу второго элемента ИЛИ и к первому входу третьего элемента И, второй вход которого подключен к выходу элемента НЕ, вход которого подключен к второму входу второго элемента И и .к выходу четвертого элемента И, нулевой выход триггера подключен к четвертому выходу блока, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого подключен к шестому входу блока, а выход подключен к единичнсжу входу триггера, седьмой вход блока подключен к третьему входу первого элемента ИЛИ, восьмой вход блока подключен к второму входу второго элемента ИЛИ, девятый и десятый входы блока подключены к входам четвертого элемента И .соответственно. Источники информации, принятые во внимание при экспертизе 1,Авторское свидетельство СССР . 732864, кл. G Об F 7/38, 1980. 2.Авторское свидетельство СССР 662930, кл. G 06F 5/00, 1976 (прототип) .