Функциональный преобразователь
Изобретение относится к автоматике и вычислительной технике и предназначено для.проектирования логических схем.Цель изобретения - расширение функциональных возможностей за счет нахождения любого из 2 полиномиальных представлений булевой функции. Преобразователь содержит /Г информационные входы 1, выходы 2, счетчик 3, коммутатор 4, блок элементов НЕРАВНОЗНАЧНОСТЬ 5, блок триггеров 6, вход синхронизации 7, вход установки в локальное состояние 8, настроечные входы 9. Преобразователь вычисляет коэффициенты таких полиномиальных представлений булевой функции , в которых переменные входят не только непосредственно, но и со знаком инверсии. Б зависимости от выбранного способа инвертирования переменных , задаваемого кодом счетчика, коммутатор осуществляет перестанов из компонент в векторе истинности булевой функции, подаваемом на информационные входы. Блок элементов НЕРАВНОЗНАЧНОСТЬ формирует коэффициенты полинома выбранного вида, которые по завершении такта заносятся в блок триггеров, откуда снимается результат . 2 з.п. ф-лы, 3 ил. J (Л к 00 оо 00 со о
:«Ж .
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИН
А1
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТ ;=.НИЙ И ОТКРЫТИЙ
Г21) 4122426/24-24 (22) 18.09.86 (46) 15.04.88. Бил. ¹ 14 (71) Днепропетровский государственный университет им. 300-летия воссоединения Украины с Россией (72) Л.M,Ãîëoáîðîäüêo и B.À.Ïàùåèêo (53) 681.3(088,8) (56) Авторское свидетельство СССР
11 - 781822, кл, С 06 F 15/31, 1978, Авторское свидетельство СССР по заявке № 4059721/24, кл. G 06 F 15/31, 22.04.86, (54) ФУНКЦИОНАЛЬНЫЙ ПРЕОБРАЗОВАТЕЛЬ (57) Изобретение относится к автоматике и вычислительной технике и предназначено для проектирования логических схем. Цель изобретения — расширение функциональных возможностей за счет нахождения любого из 2 полиномиальных представлений булевой функции. Преобразователь содержит г.SU»1388890 инфармапионные входы 1, выходы 2, счетчик 3, коммутатор 4, блок элементов НЕРАВНОЗНАЧНОСТЬ 5, блок триг" геров 6, вход синхронизации 7, вход установки в локальное состояние 8, настроечные входы 9. Преобразователь вычисляет коэффициенты таких полиномиальных представлений булевой функции, в которых переменные входят не только непосредственно, но и со знаком инверсии. В зависимости от выбранного способа инвертирования переменных, задаваемого кодом счетчика, коммутатор осуществляет перестанов из компонент в векторе истинности булевой функции„ подаваемом на информационные входы. Блок элементов НЕРАВНОЗНАЧНОСТЬ формирует коэффициенты полинома выбранного вида, которые по завершении такта заносятся в блок триггеров, откуда снимается результат. 2 з.п. ф-лы, 3 ил.
1388890
< 4
f=(x„... х,)= ", . ° ° Q F(kn s ° ° ° »< )
« ÄÄ=o к,=о. к„,- <
<<Х o ° ° ° Õ< где . — знак суммы по модулю два; х, — или х;, или х (i=1 °,п); х", =1, если k; =0;
Величины F(kni }с<) могут быть или нулями, или единицами.
Чтобы получить вектор коэффициентов F(k„...,,k,), Håîáõîäèìo вектор
f умножить на и-кратное прямое (кронекеровское).произведение матрицы (r;<;) (2) 117 ?1 ?1<
h,h, }17 h, ?1, h2h, hp
h„
hsh2h
11 7}12
hsh, hs
h2h, }12
}1 <
?1 7h2h, h h, ?1, }1< h, 11 h, :!1 2
:i1 < !
}1 7 }"2 }1
h h
h,h
hy ?1 2?< <
?12
}1<
Р(0,0,0)
F(0,0,))
F(0, >,О)
F(O,1,>)
F(1,О, О)
F(1i,0,1)
Г(1,1,0)
F(1,1,1) 7 2
h h
h,}1<
}17
?12?1 < 1 1, 5Ä
h7hzhi
h h
h7h
h7
h2h, ?1, h, 1
h7h2h
h7h
h7h<
h7
}1, ?1, h
h<
h7h2h<
}1 7 }17.
}7?
?1
h2
h„
fî
f<
f, к
fg
fs
f<< т
Это соотношение можно представить как систему следующих равенств:
F(0»0) =hsh2h< 7<<®hsh2h< f<®h sh2h< f2®hsh2h< fs®hsh2h< Г4®}17}12}1< fsEbhsh25 f6
7 2 < 7 7
:, (0,0,1)=?,},ГВ?,}2Г Е?,?,ГВ?,? „ 7В?,?, Е? }1,Г,Е?,?,Г,а},?,Г,; .". (0 < 1 7 0 ) =hy h< Хо® hs h< Г <<}17 }1< 72О+?17 h< Г7Ю}17 }1< fs@hs h< fs+hs h ° 1 8}17}1< 7-7 7
"(0,1,1)-hs fßhs f,9?1 .f,И17170hsf7@hsfs&hsf60h7f,;
F(1,0,0)-h2h, f,Þ h2h, 1Я?12?1< f2eh2h, Г7®?12h, f,g)h h, f®+h2h, f,®h ?1< f,; (1 7 0 s 1 ) 2 о }1 2 < ® 11 2 f 2 + h s. f 7 ® }1 2 +Я )1 7 7<- }1 2 б< 7 ?1 2 7 s . (1,1,1)- Гв,аГ2ef аГ,Еf f,ef .
Для п=3 алгоритм функционирования определяется системой равенств (3).
Изобретение относится к автоматике и вычислительной гехнике H предназначено для механизации ручных методов синтеза логических схем в автоматизированных системах проектирования. . Цель изобретения -. расширение функциональных воэможностей преобразователя за счет нахождения любого !О
« иэ 2 полиномиальных представлений булевой функции.
На фиг. 1 показана функциональная схема преобразователя; на фиг. 2 и 3схемы блока элементов НЕРАВНОЗНАЧ- 15
НОСТЬ и коммутатора при n=3.
Функциональный преобразователь содержит информационные входы 1, выходы 2, счетчик 3, коммутатор 4, содержащий 2" мультиплексоров 4<-4., 20 блок 5 элементов НЕРАВНОЗНАЧНОСТЬ, содержащий n=3 групп по 2 =4 элемен-< тов НЕРАВНОЗНАЧНОСТЬ, блок триггеров б, вход 7 синхронизации, вход 8 установки B начальное состояние и настро- 25 ечные входы 9.
Рассмотрим реализуемый предлагаЕмым устройством алгоритм вычисления коэффициентов полинома Жегалкина, где каждая переменная входит или непо- 30 средственно, или с инверсией. Пусть
Задана булева функция своим вектором истинности f(f y...,1.. ), где f мо жет быть нли нулем, или единицей (1=< 0
О,,...,2 ). Произвольная булева
n-< 1 функция представлена полиномом Reran
Мина следующего вида: ! рассматриваемой при i-=1,...,n. Если переменная х; не инвертирована, то
h, =О, в противном случае h; =1
С целью нахождения и-кратного прямого произведения Н„ матрицы (2) можно воспользоваться следующим рекуррентным соотношением:
hnHn-< hnHn-<
Н„, Н„, 11 где Н„, — матрица размером 2 2 являющаяся (п-1)-кратным кронекеровским произведением матрицы (2).
При 11=3 умножение вектора значений функции f(xn х,) на матрицу Н„ записывается так:
Функциональный преобразователь содержит группу иэ 2" входов, причем
1388890 (5) (4) (011 100 101 110
000 000 001 010 011 100 101 110 111.
001 001 000 011 010 101 100 111 110
010 010 011 000 001 110 111 100 101
011 011 010 011 000 111 110 101 100
100 100 101 110 ill. 000 001 010 Oll !
01 101 100 ill 110 001 000 011 010
110 110 111 100 101 010 011 000 001
111 111 110 101 100 011 010 001 000
1) з h h»
Т, -, »,», Т4 1 11)L h<
Z,=h,h,h, порядок подключения входов N„(N, =0,2" -1) этой группы к информационным входам коммутатора описывается выражением вида
Здесь значения N(„„ (è Я," являются (<м компонентами двоичного представле(пп) (<) ния порядкового номера NÄ = (N Ä . . . N ) Предлагаемое устройство позволяет вычислять коэффициенты полинома Жегалкина за один такт функционирования путем умножения вектора значений функции f(x,,х,) на матрицу Н,„.
Требуемый вид полинома Жегалкина задается величинами h,... h,,хранимыми в счетчике 3. Величина h;(i=
=1,n) равна единице, если соответст- 40 вующая переменная х; инвертирована, и тождественна нулю в противном случае.
После занесения в счетчик 3 определенной комбинации величин h h 45 с входов 9 начинается подсчет синхроимпульсов и на выходах счетчика 3 последовательно появляются различные комбинации величин h„...h,. Это позволяет осуществить вычисление любых 50
»< из 2 полиномиальных представлений булевой функции, начиная с заданного,, f„eh h h < f, h )h h» f 6)h n-» (h) (<) N (»< + ° ° ° +2 N +N (« ° Получение двоичного представления номеров входов функционального преобразователя иэ двоичных представлений номеров мультиплексоров и номеров входов мультиплексоров при п=3 иллюстрируется таблицей. которое определяется заносимой комбинацией h„,...,h,. Полученные результаты сравниваются с целью выбора лучшего по заданным критериям (например, критерий минимального числа единиц в полиноме Жегалкина, обеспечивающий минимум аппаратных средств). Рассмотрим функционирование предлагаемого устройства для n=3, описываемое системой равенств (3). На входы 1, -1, функционального преобразователя соответственно подаются значения булевой функции. Комбинация величин h » h, h< с выхода счетчика 3 поступает через управляющие входы коммутатора 4 на адресные входы мультиплексоров 4,-4() Сигналы на выходах с мультиплексоров 4,-4 задаются следующими выражени" ями соответственно: h h z h (f 4GOh < h q h < f +h < hq h» f 4Bh q + h < 7 < hyh h» f»O+hy hgh< о®hyhgh< з®hyhgh» fg < 1 1388890 6 I,=h,h,h,f,еЯ,1,1:, f,eh,h,1, f4eh,1,h, г,е1i,h,1i, f,ю1,1,h, г,я1-„ь1,к, f.ак,h,h,f,; I<< 1 3Ь2Й< f 3 2 О 3 1 < 3 2 2 3 2 3 3 2 4 - 9 1- -б 3 2 1 б Э 2 7 )1 (h h 2 <7® h 3 h 2 f1 O+ h 3 h 2 2$ h 1 2 3O+ h 3 h 2 f 4O h 9 h 2 f & h 3 h 2 6<- 31 2 7 ); (h3h2h! 2С 1 3h2h! 3e3h3h2h! foeh3h2h< "<+h3h2h! fs+h3hzh< f<®h9hzh» f4&h3h2h< -5 ) (h > h 2 f 2O+ h 9 h 2 f 3 67h 3 h 2 5э 1 < 3 1 2 f <(B h 3 h 2 f4 ®h 3 h 2 f <® h 3 h z 47 31 3 h 2 3 ); (h3h2 h! 4@ 3 2" < "7 О1 31 21 < "6 3 211 f7@h 3h2h< о91 3 21 f<<- Это позволяет на выходах второй группы элементов НЕРАВНОЗНАЧНОСТЬ и ! на входах третьей группы элементов НЕРАВНОЗНАЧНОСТЬ получить соответственно значения: (h h2h fo®h h2h -1 6>h3h h f2&h9h>h 3®h3hzh f2Q+h3f3 ) ° На входы триггеров 6< -612 с выходов НОСТЬ поступают значения третьей группы элементов НЕРАВНОЗНАЧ-! ! (h 3 h2h! «® h3 h2h f 1 h3 h2h< f2(3h9 h2 h1 3®h3 h2h1 f4&h3 h2h< f3® hЭh 2h1 f<;&h3h2h! f7 ); (11 3 1 2 О@ 5 э 1 < 2. 1 87 h 3 h 2 f2O+ h 3 h2,-, i ? h 9 h2, 4< 3 h 3 h 2. 9 Qh 3 h 2 4 D+h 3 h . f 7 ) (h 3 h! о . h 3 h < f < O+ h 3 h < 2 ® h 3 h 3 3 1 1 f 4O h 3 h f 3 h 3 h < f6 e h 3 h < 7 ); (h2h! foÞh2} < f В результате по окончании такта на выходах 2, -2 преобразователя хранятся значения, определяемые системой равенств (3). 1, Функциональный преобразователь, содержащий счетчик, коммутатор, блок триггеров и блок элементов НЕРАВНО - где операция логического ИЛИ заменена суммой по модулю два благодаря следующему. В алгебре Жегалкина имеет место тождество хчу=хауЮху, которое превращается в хчу=хуу, если х и у предста- 10 вляют собой конъюнкции, содержащие Формула изобретения 55 прямое и инверсное значения некоторой переменной, например h, f,Nh, f, = =h,f vh f,. На выходах первой группы, а также на входах второй группы элементов НЕРАВНОЗНАЧНОСТЬ имеют место неличины: ЗНАЧНОСТЬ, причем информационные входы преобразователя соединены с информационными входами коммутатора, управляющие входы которого соединены с выходами счетчика, вход синхронизации которого соединен с входом синхронизации преобразователя и тактовьп. входом блока триггеров, выходы которого соединены с выходами преобразователя, вход установки в начальное состояние которого соединен с входом, 1388890 equi сброса блока триггеров, информационные входы которого соединены с выхо-, дом блока элементов НЕРАВНОЗНАЧНОСТЬ, входы которого соединены с выходами коммутатора, о т л и ч а ю щ и й— с я тем, что, с целью расширения функциональных возможностей за счет нахождения любого из 2 полиномиальных представлений булевой функции, 1{) настроечные входы преобразователя соединены с информационными входами счетчика, вход разрешения записи которого соединен с входом установки в начальное состояние преобразова- !5 теля. 2. Преобразователь по п. 1, о тл и ч а ю шийся тем, что блок элементов НЕРАВНОЗНАЧНОСТЬ содержит и групп по 2" элементов НЕРАВНОЗНАЧ- 20 НОСТЬ в каждой, причем входы )-го элемента НЕРАВНОЗНАЧНОСТЬ первой группы (=1,2 ) соединены с (2 -1)-м и 21-м входами блока, входы i-ro элемента К-й группы (К=2,n) соединены с соответствующими выходами элементов НЕРАВНОЗНАЧНОСТЬ (К-1)-й группы и-< и входами блока, с первого по 2 -й выходы блока соединены соответственно с первым входом блока, выходами элементов НЕРАВНОЗНАЧНОСТЬ с первой по (и-1)-ю группы, выходы элементов НЕРАВНОЗНАЧНОСТЬ и-й группы соедине-!!-! и ны с (2 +l)-ro по 2 -й выходами блока. 3. Преобразователь по п. 1, о тл и ч а ю шийся тем, что коммутатор содержит 2 мультиплексоров, причем управляющие входы коммутатора соединены с управляющими входами мультиплексоров, выходы которых соединены с выходами коммутатора, информационные входы которого соединены с соответствующими информационными входами мультиплексоров. Составитель О.Беоезикова Редактор А.Огар Техред M.Õoöàíè÷ Корректор М.Максимишинец Заказ 1582/51 Тираж 70ч Подписное ВНИИПИ Государственного комитета СССР по.делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. ч/5 Производственно-полиграфическое предприятие, г„ Ужгород, ул. Проектная, ч
