Функциональный преобразователь

(51) ОПИСАНИЕ ИЗОБРЕТЕНК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Днепропетровский ордена ТрудовогоКрасного Знамени государственный университет им. 300-летия воссоединения Украиныс Россией(53) 681.32 (088.8) 6) 1. Авторское свидетельство СССР 781822, кл. 6 06 Е 15/31, 1979. вторскос свидетельство СССР Р 100110706 Г 15/332, 982 (прототип).(54) (57) ФУНКЦИОНАЛЬНЫЙ ПРЕОБРАЗОВАи ТЕЛЬ, содержащий первую группу из п (2 - размер преобразования) элементов задержки, и арифметических блоков, причем 1-й (1=1,п) арифметический блок содержит первый элемент И и сумматор по модулю два, первый вход которого подключен к выходу первого элемента И, первый вход которого подклю. чен к выходу -го элемента задержки первой группы, блок управления, содержаший счет. чик, прямой выход .го (1=1,п) разряда которого подключен к второму входу первого элемента И -го арифметического блока, о тличающийся тем,что,сцелью расширения функциональных возможностей за счет реализации полинома Жегалкина заданного вида, в который каждая переменная входит непосредственно или с инверсией, в преобразователь введены вторая группа нэ и элементов задержки, в 1-й арифметический блок - второй и третий элементы И, а в блок управления - и элементов И, и элементов И - НЕ и и триггеров, причем в 1-м арифметическом блоке второй и третий входы сумматора чо модулю два подключены к вы. ходам соответственно второго и третьего элементов И, первые входы которых подключены к выходам соответственно 1-го элемента И - НЕ и -го элемента И блока управления, первые входы которых подключены к выходу -го триггера блока управления, прямой, и инверсный выходы 1-го разряда счетчика блока управления подключены к вторым входам соответственно 1-го элемента И - НЕ .и 1-го элемента И блока управления, выход сумматора по 3 модулю два 1-го (1= 1,и - 1) арифметического блока подключен к второму входу третьего элемента И (1+1)-го арифметического блока и входу (1+1)-го элемента задержки. второй группы, выход которого подключен к второму входу второго элемента И (1+1)-го арифметического блока и входу (1+1)-го элемента задержки первой группы, выход сумматора по модулю два и-го арифметического блока является информационным выходом преобразователя, второй вход второго элемента И первого арифметического блока соединен. с входом первого элемента задержки первой группы и подключен к выходу первого элемента задержки второй группы, вход кото. рого соединен с вторым входом третьего элемента И первого арифметического блока и является информационным входом преобразователя.1401Изобретение относится к автоматике и вычислительной технике и предназначено длямеханизации ручных методов синтеза логических схем в автоматизированных системах про.екти ров ания. 5Известен функциональный преобразователь,содержащий счетчик, коммутатор, шифратор,элементы И и счетные триггеры 11).Несмотря на значительные аппаратурныезатраты это устройство позволяет найти дляданной булевой функции ее полипом Жегалкина, если в последнем все переменные не инвертированы,Наиболее близким по технической сущностик изобретению является анализатор спектра,состоящий из счетчика и последовательно соединенных каналов, каждый из которых содер.жит блок задержки и арифметический блок,который содержит последовательно соединенныеэлемент И и сумматор по модулю два 2.Это устройство реализуется с меньшимиаппаратурными затратами, однако также позволяет найти для данной булевой функции толькотакой ее полином Жегалкина, в котором всепеременные не инвертированы. 25Наиболее близким по технической сущностик изобретению является анализатор спектра,состоящий из счетчика и последовательно сое.диненных каналов, каждый иэ которых содержит блок задержки и арифметический блоккоторый содержит последовательно соединенныеэлемент И и сумматор по модулю два 2.Это устройство реализуется с меньшимиаппаратурными затратами, однако также позволяет найти для данной булевой функции .только такой ее полипом Жегалкина, в котором все переменные не инвертированы,Цель изобретения - расширение функциональных возможностей за счет реализации поли- нома Жегалкина заданного вида, в который каждая переменная входит или непосредственно, или с инверсией,Поставленная цель достигается тем, что функциональный преобразователь, содержащий. первую группу из п (2 -размер преобразовачния) элементов задержки, и арифметических блоков, причем -й(=1,п) арифметический блок содержит первый элемент И и сумматор по модулю два, первый вход которого подключен к выходу элемента И, первый вход кото рого подключен к выходу -го элемента задержки первой группы, блок управления, содержащий счетчйк, прямой выход -го(=1,и) разряда которого подключен к второму входу первого элемента И 1-го арифметического 55 блока, введены вторая группа из п элементов задержки, в -й арифметический блок - второй и третий элементы И, а в блок управле 30 1ния - и элементов И, п элементов И-Е и и триггеров, причем в -м арифметическом блоке второй и третий входы сумматора по модулю два подключены к выходам соответ. ственно второго и третьего элементов И, первые входы которых подключены к выхо.дам соответственно -го элемента ИНЕ и -го элемент И блока управления, первые входы которых подключены к выходу -го триггера блока управления, прямой и ин.версный выходы -го разряда счетчика блока управления подключены к вторым входам соответственно -го элемента И - НЕ и .го элемента И блока управления, выход сумматора по модулю два -го ( = 1,и - 1) арифметического блока подключен к второму входу третьего элемента И (+1)-го арифметического блока и входу (1+1) -го элемента задержки второй группы, выход которого подключен ко второму входу второго элемента И (1 )- го арифметического блока и входу (+1)-го элемента задержки первой группы, выход сумматора по модулю два о-го арифметичес.кого блока является информационным выходом преобразователя, второй вход второго элемента И первого арифметического блока соединен с входом первого элемента задержки первой группы и подключен к выходу первого элемента задержки второй группы, вход которого соединен с вторым входом третьего элемента И первого арифметического блока и является информационным входом преобразователя.На фиг. 1 показана структура функцио.нального преобразователя; на фиг. 2 и 3 - блок-схемы арифметического блока и блока управления соответственно.Функциональный преобразователь состоитиз блока управления 1, элементов задержки21 2, и 3, 3 арифметических блоков 41, 4 п, каждый из которых содержитэлементы И 5, 6 и 7 и сумматор 8 по моду.лю два, блок управления 1 состоит из и-разрядного счетчика 9, триггеров 10, . 10элементов И - НЕ 11,11 и элементовИ 1212, Выходы 13 13,14,.14, 1 515,блока управления 1 подключены соответственно к входам элементов5, 6 и 7 арифметических блоков 41,4,.Элементы. задержки 2 и 3 первого канала задерживают входную двоичную последовательность на один такт каждый. Элементызадержки в каждом последующем каналеосуществляют задержку в два раза большую,чем в предыдущем канале,Рассмотрим аглоритм вычисления коэффици.ентов полинома Жегалкина, реализуемогоустройством,30 4Для п = 2 алгоритм функционирования данного устройства определяется системой равенств (3).Данное устройство позволяет вычислять коэф.фициенты полинома Жегалкина булевых функцийдаже тогда, когда их векторыистинности длины2 подаются на вход непосредственно друг эадругом. Последовательность их 2" нулей и .единиц - коэффициентов полинома ЖегалкинаИвырабатывается с задержкои на 2 - 1 тактовпо отношению к спектору истинности, т, е. коэффициент формируется в том же такте, вкотором на вход поступает последнее значениебулевой функции,Требуемый вид полинома Жегалкнна задаетсявеличинами Ь 1 Ьп, хранимыми соответственно в триггерах 10,1 Оп и равными единице,1если соответствуюшие переменные х,1 х,инвертированы и тождественными нулю в про)тивном случае.Рассмотрим функционирование данного уст.ройства для п = 2, что описывается системойравенств (3).В первом такте счетчик 9 блока управления1. находится в нулевом состоянии (00), на вхо.де устройства присутствует последнее значение Ф булевой функции двух переменных,элементы задержки 2 и 31 хранят сост.,ветственно 1 г и 1 а элемент задержки 2содержит 1 О+ Ь, 1 в первом своем разрядеи 1 О Ь,1 во втором. В первом и второмразрядах элемента задержки 3 имеем результаты обработки вектора истинности предыдушей булевой функции 1 9 Ь 13 и Ф 9 ЬФ.соответственно,Нулевой потенциал с выхода 13 блокауправления 1 подается через вход элементаИ 5 на вход сумматора 8 по модулю арифметического блока 4 . Нуль в младшем раз.ряде счетчика 9 обеспечивает единичный потекциал на выходе 14 блока управления 1 и,следовательно, на входе элемента И 6 арифметического блока 4. Благодаря этому величина Ф через вход элемента И 6 поступаетна вход сумматора 8 по модулю два. Сигналс инверсного выхода первого разряда счетчика 9 обеспечивает прохождение величины Ьс выхода триггера 1 О через вход элементаИ 12,выход 15 блока управления 1 навход элемента И 7 арифметического блока 419вследствие чего 1 со входа функциональногопреобразователя умножается на Ь и поступаетна вход сумматора 8 по модулю два арифметического блока 4, Следовательно, на выходеарифметического блока 4 имеем величинуТг е Ь 4 Т 3 3 140Пусть задана булева функция своим векто.ром истинности т = (11 1 л. ) гдеможет быть или нулем, или единицей (1= О,12"), 1 роиэвольная булева функция представима полиномом Жегэлкина следующего видах , х, =Е, ф Г1 , ,) х "хс,:ОЛгде- знак суммы по модулю два, х,это или х; или х (=1,п), а хь 1,если К =О. Величины Е(К К,) могут быть10или нулями, или единицами,Поскольку каждая переменная хвходит в(1) или непосредственно, или со знаком инвер-сии,то всего существует 2 различных полиномоввида (1), причем если все переменные нс кивер.тированы, то имеем традиционный полипом Же.галкина, коэффициенты которого могут бытьвычислены с помощью устройства. прототипа.Например, при и = 2 и х - хг, х, - химеем полином 201(хг,х)=Е(00)ЙЕ(0,1) . х Е(1,0) х ЮЕ(1,1)х,х.Чтобы получить вектор коэффициентов Е(с,К), необходимо вектор 1 умножить на и-кратное прямое (кронекерово) произведение матрицы(2)при=1,п. Если переменная х, не инвертиро.вана, то Ь =О, в противном. случае Ь = 1С целью нахождс гия и-кратного прямого про-, .изведения Н матриц (2) можно воспользоватьсяследуюшим рекурсивным соотношением-1 "и Нп-Нв:Ь Н35 и-где Н, - матрица размером 2 х 2 являющаяся (и - 1) -кратным кронекеровым произведением матриц (2), рассматриваемых при =1, и - 1.40При и = 2 умножение вектора значений функции 1 (хх) на матрицу Н записываетсяитак 45 Е (0,0) Е (0,1) Е (1,0) Е (1,1) 1 Ь,Ь, 1 Ь Ь 7 1 ЬЬг 1 Ь, Ь Ьг г Ь Ь Ь,Б,Ь,Ь,0(3)г Это соотношение можно представить как систему 50из четырех следующих равенств, записанных вскобочной форме Е(0 0) (Фр Э 0 О+ Ь Ф)0 В Ь (1 гЮОЮЬ 1 Е(0,1) - (Ь, тОО)0 ЗЬ,(Ь, 1,+г 0), (3) Е(1,0)= Ьг (тг ЭОЫ Ь т,)9(т 80 6 Ь )90, Е(1,1)=Ь,(Ь ,Е 1:, ЕО)а(БаУО)ао Эта величина умножается элементом И 7арифметического блока 4 на Ь и подаетсяна вход сумматора по модулю два 8, Ь 2 пос.тупает на вход элемента И 7 с выхода триггера 10( через вход элемента И 122 ивыход 15 блока управления 1 благодаряналичию единичного потенциала на инверсном выходе второго разряда счетчика 9. Логический нуль с выхода 132 блока управле.ния 1 подается через вход элемента И 5 навход сумматора 8 по модулю два арифмети.ческого блока 4(. Благодаря потенциалу логического нуля на прямом выходе второго 10разряда счетчика 9 имеем единицу на выходе 14, блока управления 1, что обеспечиваетфпрохождение на вход сумматора 8 по модулю два через вход элемента И б арифметического блока 42 величины 1 о Я Ь, 1 с 15выхода второго разряда элемента задержки2,. На выходе устройства имеем (1 8 ЬфФ и (Ь ).По окончанию такта элементы задержки 2и 31 хранят 1 и г соответственно. В пер Овом ивтором разрядах элемента задержки 2( - (имеем 1 Ж Ь 1 1 э и;10+ 11 1, а такжефО Ь 2 и т 29 Ь 1 13 в первом и второмразрядах элемента задержки 3,Во втором такте первое значение 1 о новой 25булевой функции поступает на вход функционального преобразователя,Благодаря наличию единицы в младшеуразряде счетчика 9 на выходе элементаИ - НЕ 11 имеем величину Ь котораячерез выход 14 блока управления 1 посту.пает на вход элемента И б, где умножаетсяна величину 1 с выхода элемента задержки21 Полученный результат подается на вход .сумматора по модулю два 8 арифметического35блока 4. На другой вход сумматора 8 помодулю два через вход элемента И 5 с выхода элемента задержки 3 поступает величина 1 . На соответствующем входесумматора28 по модулю два арифметического блока 44имеем нуль, поступающий с инверсного вы.хода первого разряда счетчика 9 через входэлемента И 12(выход 15 блока управле ния 1 и вход элемента И 7. В результатена выходе арифметического блока 4 получаем величину 1 З Ь 1Поскольку во втором такте, также как ив первом, второй разряд счетчика 9 содержит нуль, то на входы сумматора 8 по модулю .два арифметического блока 4 поступают соответствснно нуль, сигнал с выхода элемента-задержки 22 -Ь 1и величина с выхода первого канала - 1 8 Ь 1 13 умножае.2мая элементом И 7 на величину Ь 2, которая подается с выхода триггера 10 через вход эп.емета 12 и выход 15 чблокауп- .равпения 1, На выходе устройства во второмтакте имеем ( 1 оЬЬ, ,)Ь 2(2 8 Ь3)По окончании второго такта величины и 1 засыпаются в элементы задержки 2,яи Зг соответственно. Элемент задержки 2-содержит 12 9 Ь1 в первом своем разряде и 1 О Ь 1 во втором. В первом и втором разряде элемента задержки 3 имеем Х,ЮЬ 1 и 1 о ЫЬ,( 1 соответственно.В третьем такте содержимое счетчика 9 составляет (10). Поэтому на выходах 13 14, 153 и 132, 14 , 152 устройства управления 1 имеем 0,1 Ь ( и 1, Ь 2 О, соответственно. Сумматор 8 по модулю два арифметического блока 4, осуществляет сло. жение величины 1 О с выхода элемента задержки 2 с величиной , подаваемой на вход функционального преобразователя, которая предварительно умножается на Ь посредством элемента И 7, В результате на выходе арифметического блока 4 имеем 1 О Ь 11. Сумматор по модулю два 8 арифметического бпо ка 42 выполняет сложение величин 1 ЙЬ 1 1 и(2 фЬ 1с вьходов элементов задср1и 22, соответственно, причем величина 1 9 Ь 1 предварительно умножается на Ь 2 с помощью элемента И б арифметического блока 4. Следовательно, в третьем такте на выходе функ,Г ционапьного преобразователя имеем (1 я Ь фО+ ЯЪ (1,ОЬ,т).При переходе к четвертому такту в элементы( задержки 21 и 3 засыпаются величины 1 и соответственно. В первом разряде элемента за(держки 22 имеем9 Ь 11, а во втором разряде 129 Ь Ф. В первом и втором разрядах элемен та задержки 3 содержатся величины 1 ЫЬ 1( 2 и 1 ЗЬ 1 соответственно.В четвертом такте на входе функционального преобразователя присутствует значение Цновой булевой функции, а счетчик 9 содержит (11). Единичные потенциалы с прямых выходов счетчика 9 поступают через выходы 131 и 132 устройства управления 1 на входы элемента И 5 арифметических блоков 4 и 4 .г Благодаря этому на входы сумматоров 8 по модулю два арифметических блоков 4и 4( -подаются величины 1 и 1 9 Ь 1 с выходов элементов задержки 3 и 22 соответственно. На выходах 14 и 142 блока управ. пения 1 имеем величины Ьи Ь 2 соответ,ственно, которые поступают на входы элементов И б арифметических блоков 4 и 4 .иВ результате 1, и 129 Ь 1 1 э в выходов элементов задержки 2 и И 22 умножаются соответственно на Ь и Ь посредством элементов И б и поступают на входы сумма. торов 8 по модулю два арифметических блоков 4и 42, Сигналы логического нуля с инверсных выходов счетчика 9 через входы7 114 О 1 ЗО 8 элементов И 12 и 12 поступают на входы Технико. экономический эффект от использова и 15 блока управления 1, а затем ния функционального преобразователя состоит в через входы элементов И 7 - на вход сумма. возможностиавтоматизироватьнроцссснахождетора 8 по модулю два арифметических блоков ниядляданной булевойфункцииипеременныхне 4 и 4. Таким образом в четвертом такте 5 только единственного полинома Жегалкина, в ко3на выходах арифметических блоков 4 и 4. тором всепеременные не инвертированы, но и любо- имеем величины 1 Ю Ь, Ф, и (Фо 6 Ь ) О+ го из 2" возможных полиномов,отличающихся друг С+) Ь (1 96 1 ) соответственно.Р гот друта способом инвертирования переменных.,ЯТираж 710 Подписное ПИ Заказ 265/ Фили ПП "Патент", г, Ужгород, ул. Проектная, 4