Устройство для вычисления булевых производных

 

Изобретение относится к области средств разработки тестового и аппаратурного контроля цифровых |з ройств. Цель изобретения - повышение быстродействия. Устройство содержит две группы входов 1, 2, регистр 3, блок вычислений 4, содержащий п групп арифметических ячеек 5, выходы 6. Оно позволяет за один такт осуществить вычисление вектора значений булевой производной. Код, подаваемый на первую группу входов, определяет характер дифференцирования (ориентированное , неориентированное или отказ от дифференцирования) по каждой переменной. Под управлением кода блок вычислений преобразует вектор значений булевой функции, nocTjmaro- щий на вторую группу входов, а вектор истинности булевой производной. По окончании такта значения булевой производной записываются в триггеры регистра и снимаются с его выходов. 1 3.п. ф-лы, 4 ил. S (Л со 00 00 00 4 00 lit, iff -. Фи.г.{

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (д1) 1 С 06 F 7/00, 15/31

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2 1 ) 41 22427/24-24 (22) 18;09.86 (46) 15.04.88. Бюл. Р 14 (71) Днепропетровский государственный университет им. 300-летия воссоединения Украины с Россией (72) В.А.Пащенко и А.Г.Рябченко (53) 68 1.3(088.8) (56) Авторское свидетельство СССР

М 940166, кл. G 06 F 15/31, 1980. . Авторское свидетельство СССР, вьданное по заявке М 3884705/24, кл. G 06 F 7/00, 1985.

Авторское свидетельство СССР

N 1128263, кл. G 06 F 15/31, 1982. (54) УСТРОИСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ПРОИЗВОДНЫХ (57) Изобретение относится к области средств разработки тестового и аппаратурного контроля цифровых устЛК 1388843 А1 ройств. Цель изобретения — повыщение быстродействия. Устройство содержит две группы входов 1, 2, регистр 3, блок вычислений 4, содержащий и групп арифметических ячеек 5, выходы 6.

Оно позволяет за один такт осуществить вычисление вектора значений булевой производной. Код, подаваемый на первую группу входов, определяет характер дифференцирования (ориентированное, неориентированное или отказ от дифференцирования) по каждой переменной. Под управлением кода блок вычислений преобразует вектор значений булевой функции, поступающий на вторую группу входов, а вектор истинности булевой производной.

По окончании такта значения булевой производной записываются в триггеры регистра и снимаются с его выходов.

1 з.п. ф-лы, 4 ил.

43 муле

v, =X„e}X„p...Sl,N} д;

v =Õ„(}(}Õ„,® .. а}дВХ„;

° ° ° ° ° ° ° ° 0 ° ° ° ° 4 ° ° ° Ф Ь „=д®Х„ ®. ° .ВХ,®Х, .

a} !(о} — !(о}!

f(1) — — (1), 1 13888

Изобретение отно< ится к автоматике и вычислительной технике и может быть использовано при построении систем тестового и аппаратурного контроля цифровых устройств.

Целью изобретения является повышение .быстродействия.

На фиг. 1 приведена блок-схема предлагаемого устройства для.вычисления булевых производных при н =3, на фиг. 2 — структура. арифметической ячейки; на фиг. 3 и 4 — сигнальные графы, соответствующие различным примерам дифференцирования булевых функций.

При п=3 устройство для вычисления булевых производных (фиг. 1) содержит 2п=б входов 1,,1,...,1, образующих первую группу входов, вторую группу входов 2!,2,...,28 (2 =

=8) устройства, восьмиразрядный реп гистр 3, состоящий из 2 =8D -триггеров 3!,Зо,...,3, блок вычислений 4, состоящий из}! =3 подблоков 4,,4,4,, 2! арифметические ячейки 5, 2 =8 выходов устройства и тактовый вход устройства обозначены соответственно через 6„,6,...,68 и 7 °

Арифметическая ячейка 5 (фиг. 2) ЗО состоит из двух мультиплексоров 8, и

8, двух элементов И 9, и 9, двух элементов ИЛИ 10! и 10, элемента

НЕРАВНОЗНАЧНОСТЬ 11, двух управляющих входов 12! и 12,, двух информационных входов 13! и 13, двух выходов 14, и 14

Управление устройством осуществляется подачей на вхоцы 1(,1,...,1,s устройства управляющих сигналов h, Согласно кодовой комбинации 1!.h . Ь 1,3) устроиство выпол няет следующие преобразования булевой функции по переменной х : 00— булева функция не,цифференцируется; 45

01 - булева функция дифференцируется ориентировано на увеличение; 10— булева функция дифференцируется ориентировано на уменьшение; 11 — буле-ва функция дифференцируется неориентировано.

Рассмотрим алгоритм вычисления бу" левых производных, реализуемый устройством.

af(x)

Производной -- — — от булевой функ- 5$ ах; ции f (x), где Х=(х „,...,х, 1 по переменной х; называется функция, определяемая по формуле

Bf(x) х, !0!x )е е е ох<)О дх. !!! >

Ф

8f(X о а e ° ох о ох! !о ° " ° !)

1, . х а (х)

Производная --- — характеризует ах; изменение функции f(x) при изменении переменной х; и равна единице на тех входных наборах, на которых изменение переменной х приводит к изменению функции. а (х)

Возрастающая производная —--ах,. определяется по формуле а (х) -г

=Г(х,ее ох оО Х °, Х )!! !

1 ! 1(хоэ ° oохо1охо ° еа ох!) !! 1+! 1 1 и равна единице на тех входных наборах, на которых функция f(x) возрастает (убывает) с возрастанием (убыванием) переменной х;. Убывающая проа (х) изводная -- †-- определяется по форах, () г

--- — — =г(х ...,>-,О,х ...,х ) дх !

+! — I

»Р(х„,...,х.„,,1,х;,,...,х, ) и равна единице на тех входных наборах, на которых функции f(x) возрастает {убывает) с убыванием (возрастанием) переменной х;.

Вычисление произво,цных по всем или нескольким переменным булевой функции можно рассматривать как ее преобразование с помощью произведения и операторов:. где V,=Х„Ж.. ЯХ;„®дОх

Причем (3 — знак прямого произведения, I, (1=1,n) — оператор, который не меняет вектор булевой функции. Например.

Оператор д можно изобразить следующими сигнальными графами: если булева функция не дифференцируется, 1388843

) () О f(o)þf(1), (<) f(o)of(1), если дифференцирование неориентировано, где знаком Я обозначено суммирование по модулю два; в) r(0) O —. f(O) r(1); (1) - (о) (1), если дифференцирование ориентировано на увеличение, где через и О обозначены операции инвертирования и логического умножения; г) r(0) О r(0)r(1) r(1). . (о) (l) 15 если дифференцирование ориентировано на уменьшение.

Рассмотрим работу устройства для вычисления булевых производных напримерах для случая п =3 переменных.

1I р и м е р 1. Булева функция дифференцируется ориентированно на увеличение по переменной х <, не дифференцируется по переменной х и диф. ференцируется ориентированно на уменьшение по переменной х .

В этом случае преобразование вектора, истинности описывается< графом, показанным на фиг. 3.

На первые информационные входы 30 устройства подаются управляющие сигналы h h h . Величины h< h поступают на управляющие входы арифметических ячеек подблока 4,, à h>, и 4 и 115 h<; на управляющие входы 35 подблоков 4 и 4 з соответственно. При ориентированном на увеличение дифференцировании булевой функции по переменной х, управляющие сигналы при- нимают значения: h,=l, hz=0. Величи- 4р нам 1< =О, h„=o соответствует отсут" ствие дифференцирования по переменной х . Дифференцирование, ориентированное на уменьшение по переменной х,, задается кодовой комбинаци- 45 ей 1i =о, h6=1.

На вторую группу информационных входов устройства 2<, 2,...,2я подаются сигналы f(0,0,0), 1(0,0,1)

f(0,1,0), f(0,1,1), f(1,0,0), f(1,0, 1), r(l,o,l), Г(1,1,o) r(1,1,1), определяющие данную булеву функцию.

Эти сигналы поступают на входы 13, и 13 каждой арифметической ячейки

5 подблока 4,.Через выводы 12, и 12 на адресные входы мультиплексоров 8, и 8 подаются величины h,=l, h =О.

Благодаря этому сигналы, сформированные на вторых информационных входах мультиплексоров 8, и 8 передаются на их выходы. В результате на выходах 14< и 14 арифметических ячеек 5 подблока 4< присутствуют величины r(O,O,0) r(0,0,1); f(O,Î,O)" (о,о,1); (о,l,о) ° (0,1,1);

Р(0,1,о) (о,l,l); r(l,o,o) r(l,o,l);

f(1,О,О) f(1,О,1); Г(1,1,О) ° f(1,1,1);

7(1,1,0) ° f(1,1,1). С выходов 14(и

14 арифметических ячеек 5 подблока

4, информация передается на входы подблока 4 .

Благодаря соединениям на вуодах

l3, и 13 арифметических ячеек 5 подблока 4 присутствуют сигналы

« (о,о,о). (о,о,1); (о,l,о) ° (0,1,1); (о,о,о). f(o,о,l); (о,l,о). f(о,l,l);

f(1,О,О) f(1,О,1); f(1„1,О) f(l,l,l);

7(1,0,o) ° 1(1,0,1); У(l,l,o) r(1,1,1). соответственно. Через выходы 12, и

12z на адресные входы мультиплексоров 8, и 8 арифметических ячеек 5 подблока 4 поступает кодовая комбинация 00. В результате информация с первых информационных входов мультиплексоров передается на их выходы.

Благодаря наличию перекрестных связей на выходах подблока 4z присутствуют величины f(O,Î,O) r(O 0,1); (о,о,о) :(о,о,l); f(0,1,0) if(0,1,1);

r(î,1,о).r(0,1 1); r(1 о,о): f(1,0 1);

f(1,Q,0) f(1,0,1); f(1,1,Î) f(1,1,1);

1(1,1,O) (1, 1,1).

Благодаря соединениям на выходы

13; и 13 арифметических ячеек 5 подблока 4, поступают сигналы f(0,0,0)"

r(o,о,l); r(l,î,o)«r(l,o,l); (0,0,О). (О,О,1); f(1,0,0) f(1,0,1); (о,l,о) r(o,1,1); (1,1,0) (i,1,1);

f(0,1,О) ° (0,1,1); f(1,1,О) f(1,1,1).

Через выводы 12, и 12 на адресные. входы мультиплексоров 8, и 8 арифметических ячеек 5 подблока 4, подаются величины h = О, h =1. В результате игналы, сформированные на третьих информационных входах мультиплексоров

8 < и 8, передаются на их выходы. Благодаря наличию перекрестных связей на выходах подблока 4 присутствуют величины Т(О,O,Î) ° (О,O,1) (1 о о) (1 о 1) 7(о о о) (о о 1)

f 1 O Î 2. 1 Î 1); (0,1,О)- (0,1,1)

«т 1 1 0 f 1 1 1); f(0 1 0) (0,1,1) r l,1,o f » l ; (о,о,о) (о,о,l).

ff 1 î î f 1 î 1); f(o,о,о) ° (о,о,l) ь 1 о о ; 1,1,1); r(o,l,о) r(o,l,l) l 1,0 f I l,l; f(0,1,0) fIo,l,i)

«Р 1,1,0

1388843

Сигналы с выходон подблока 4 подаются на информационные входи регистра 3 и записываются в него по заднему фронту синхроимпульса с шины 7. В результате на выходах устройства 6,, 6». ..68 имеем сигналы, тождественные величинам, полученным с помощью сигнального графа на фиг. 3.

Пример 2. Булева функция не >О дифференцируется по переменной Х<, дифференцируется неориентированно по переменной х и дифференцируется ориентировано на увеличение по переменной х<. В зтом сл учае вектор истинности Г(х,х»,х,) преобразуется согласно сигнальному графу, приведенному на фиг. 4.

На управляющие входы устройства поступают сигналы: h< 0; 11»=0; Ь,,=1; 20

h,=l; h 1; ),-0.

Через вторую группу информационных входов устройства 2<,2»,...,2н на входы 13, и 13» арифметических ячеек 5 подблока 4, подаются величины f(0,0,0), f(0,0,1),:Г(0,1,0) (0,1,1), f(1,0,0), .;f(1,0,1), f(), 1,О), f(1,1,1) соответственно. На адресные входы мультиплексоров 8< и

8» арифметических ячеек 5 подблока

4, поступает кодовая комбинация 00.

В результате сигналы с первых информационных входов мультиплексоров передаются на выходы 14, и 14..

Благодаря наличию перекрестных связей на входы 13, и 13» арифметических ячеек 5 подблока 4 подаются сигналы 1(0,0,0), f(0,1,0), f(0,0,1)

f(0,:1,)), 1(1,0,0), f(1,1,0), f(1,О,1), Г (1,1,1). !

На управляющих входах арифметических ячеек присутствуют величины Ь :=

=1, h =1. Следовательно сигналы, сформированные на четвертых информа45 ционных входах мультиплексоров 8, и

80, передаются на их выходы 14< и

14,2, Соединения обеспечивают присутствие на выходах подблока 4» велич)лн

f (0,О,О)В (О,1,0); f(0,0,))В(О,1,));

f(0,0,0P f(0,1,0); f(0,0,))O (0,1,1); 50

f(1,0,0)O+f(),1,О); (1,0,1)Ю:(1,1,1);

f(1,0,0)Of(1,1,О); f (I,0,1)О+ (1,1,)), С входон подблока 4 посредством перекрестных связей на входы арифметических ячеек 5 подблока 4 поступают 55 сигналы f(0,0,0)<+)f((),1,0); f(1,0,0)B

В: (1, ), () ) f (0, 0, 1 )e? f (О, 1, 1 );

"(),0,) k7f(),1,1); (0,0,0)В"(0,1,0);

f(1 0 0)6)f() 1,0) (О О 1)ВГ(О 1,))

f(1,0,1)Of(), 1,1), На адресные входы мультиплексоров

8, и 8 через выводы 12< 12» подается кодовая комбинация 01, Следовательно, величины, сформированные на вторых информационных входах мультиплексоров, передаются на выходы )4( и 14<, а затем посредством перекрестных связей — на выходы подблока 4, В результате на информационные входы

D-тригге ов егистра 3 поступают сигналы (f 0,0,0)9f О ),ОН (f(),0,0)Ю

ef().).0Ä; (f О,О,) ef 0 ),IÄ (((1,0,1)Е1(l, l,<Д, (f O,Ñ,Î Â

Oaf(0 1 О),) ff(),0,0)Bf(),1,0)); ((0,0,1)®f 0 1 1))- ((1,0,1)аГ(),1, 1Д; (f(0,0,0 Bif 0. I 0Д (f(1,0,0)Е

В (1,1,0) J; (f (0,0,) е<ГВ 1 1Д (((10,1)0+f(1,1,<Д; ((0,0,0 В

ef(O ) ОД P(),o,с,e+f(),),0)j; ((0,0,1 Q+f 0,1,1 ) ((1,0,))Bf(), 1,))).

По заднему фронту синхроимпульса, поступающего по шине 7, эти сигналы записываются в D-триггеры 3,,3»,..., 3 « и присутствуют на выходах 6,, 6 . ..6 регистра 3. Следовательно, на выходах устройства присутствуют величины, сформированные согласно графа, приведенного на фиг, 4.

Формула изобретения

1. Устройство для вычисления булевых производных, содержащее регистр и блок вычислений, причем тактовый вход устройства соединен с тактовым входом регистра, выходы которого являются выходами устройства, первая группа входов которого соединена с входом первой группы блока вычислений, выходы. которого соединены с информационными входами регистра, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, блок вычислений содержит п групп из

2" арифметических ячеек (n — количество переменных), причем вторая группа входов устройства соединена. с информационными входами арифметических ячеек первой группы блока вычислений, информационные входы

j é арифметической ячейки (j =1,2" )

i-й группы (i=2,n) соединены с соответствующими выходами арифметических ячеек (i-1) -й группы, выходы арифметических ячеек последней груп1388843 пы соединены с выходами блока вычислений, входы первой группы которого соединены с настроечными входами арифметических ячеек.

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что арифметическая ячейка содержит два мультиплексора, два элемента И, два эле- 1р мента НЕ и элемент НЕРАВНОЗНАЧНОСТЬ, причем настроечные входы ячейки с управляющими входами первого и второго мультиплексоров, выходы которых соединены с выходами ячейки, первый информационный вход которой соединен с первым информационным входом первого мультиплексора, первыми входами первого элемента И и элемента НЕРАВНОЗНАЧНОСТЬ, входом первого элемента

НЕ, выход которого соединен с первым входом второго элемента И, второй вход которого соединен с вторым входом элемента НЕРАВНОЗНАЧНОСТЬ, вторым информационным входом ячейки, первым информационным входом второго мультиплексора и входом второго элемента НЕ, выход которого соединен с вторым входом первого элемента И, второй, третий и четвертый информационные входы первого и второго мультиплексоров соединены с выходами второго элемента И, первого элемента И и элемента НЕРАВНОЗНАЧНОСТЬ соответственно.

1388843 г(ао,о)

P(PO 1) р(0,1,0)

У(0. 1, 1)

y(r,O0)

Я,о,r) (1,0) (1,),)),.у(о а а), r(aa l)

)(цо)

«((о и!

)(гап) g(oo 0 (Оо, 1) p(a0,o) Дс(Д11

&(ООО)

Яоо1) @$00) Составитель О. Березикова

Редактор И. Середа Техред M.Äèäûê Корректор М. Максимишинец

Заказ 1580/49 Тираж 704 Подписно е

ВНИИПИ Государстве. нного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4

ЯО,О,О) м)

®и o)

par, r)

f(r.o.o)

У(1,0 1)

У(1,1,0)

У(1, 1, 1) ЯЦОЩФ 1)

ЮСОВ(И 1)

Я д ЦЦ1(я 1.1)

)О o)f(arr)

У(1,00) (10 1) (1,0(0)У(1 0 1)

«Д 10)Я1 1,1) ъу(цO)f(r.1. 1) ((((000)f(y0 1)

7(одаИ(И() д (()у(е(()

i(a r sera(()

a((aa) ((a»

7r(ap)A(ar) у(1, 1,0)Я1.11)

„7(1„ 0)/(1,) 1) .1(ОаО) р (О. 1,0)

f(f41) @+011) (ИО) Е,У(010) ,1(0,01) f&f(or.r) ,1(1,00) ЩЯ1,1.6

z(r,о.ц ®ffr,r,r)

f(r.аО) ЕЮ 1,0)

f(r.0D рЯ1.1.1) ЯОО,ОУ(оа1) ЮО,ОР(10 1) ООО) (ОО1) Шо,о)Ю а1/

ya ro) (0.1,Ц хааа)й1, 1,1) @1,ц) фцr)f(1 ЯЛ1 11) у(цОО)ЯО 1)Й100) (10 1) (ОДОР ОО, 1)Х(1О0)З(т1) < 1 0),.(а 1,1) (,10у(1, 1, ),-(010)f(0, 1)f(1r,1,0)Я!1.1/ У(Ц 1,О (Я0,0) В Я*ЯД

®gqr,r)) У(т1) ФЯ111» едцоЯ&(ял) оЮ 140

Щ У(01,1)/(Я1,0)1) ®Ю И1 ДНО)) (ЯОЯ Е (, 10))

eg/a1 1))сЯ101) 9х(1 иО

eg(gо, 10)ЦЯ1,0,0)Вф1, 1,0))

@g(y gJ(fl1l,о,1) еМШ3