Устройство для вычисления булевых производных Советский патент 1988 года по МПК G06F17/10 G06F7/00 

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

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

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

При устройство для вычисле™ ния булевых производных (фиг. 1) содержит входов 14 t 9 ° Ие образующих первую группу входов, вторую группу входов 2,,2,..o,2g (2 8) устройства, восьмиразрядный регистр 3, состоящий из 2 8D -триггеров 3,32,...Зэ, блок вычислений 4, состоящий изи 3 подблоков 44,42,4j,

И равна единице на тех в рах, на которых функция стает (убывает) с возрас ванием) переменной х;. У изводная определя . dx;

муле

3 f(x) /Q

-д--I .Х„ , . . . , ,и,Х

Эх.

.f(:

-п Ui

,1 5Xj,,..

и равна единице на тех в борах, на которых функци р астает (убывает) с убыв

арифметические ячейки 5, 2 8 выходов устройства и тактовый вход уст ройства обозначены соответственно через 6 ,6. ,... ,6g и 7.

Арифметическая ячейка 5 (фиг. .2) . 30 состоит из двух мультаплексоров 8, и 8j,, двух элементов И 9, и 9,, двух элементов ИЛИ 10( и Ю, элемента НЕРАВНОЗНАЧНОСТЬ 11, двух управляющих входов 12i и 12г , ,цвух информа- jg растанием) переменной х; ционных входов 13i и 13, двух выходов 14 , и 14 .

Управление устройством осуществляется подачей на входы 1, , 1 , .., l,s устройства управляю:щих сигналов li, , 40 hj,...,h;. Согласно кодовой комбинации h.,, f ,3) устройство выполняет следующие преобразования булевой функции по переменной 00 - булева функция не дифференцируется; -j- 01 - булева функция дифференцируется ориентировано на увеличение; 10 , булева функция дифференцируется ориентировано на уменьшение; 11 - булева функция дифференцируется неориен50

тировано.

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

Производной -5---- булевой функ- 55

ОХ;

ции f(x), где ,. .. ,х, 5 по переменной X; называется функция, определяемая по формуле

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

...v.V, , где . ®Ii,®...®

Причем ® - знак прямо дения, 1 (,п) - опер рый не меняет вектор бул ции. Например.

V, 1„®1„.,®...®12®л; .,®..)u®I, ;

,®...®1,®1, .

Оператор и можно изобраз щими сигнальными г рафами

а). f(O).-f(0);

fd)--fd),

если булева функция не д ется;

1 -f(x X. о

-g-- -I

S-(

,x.

@f(:

n

jXj+i 9 i-i :

Производная ----- характеризует Э xj

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

a fCx)

Возрастающая производная

УХ;

определяется по формуле

fM

Эх

f(x.

-f (,.l э , 5 . . . jX ,. «

(+ ) 1

И равна единице на тех входных наборах, на которых функция f(x) возрастает (убывает) с возрастанием (убыванием) переменной х;. Убывающая производная определяется по фор- . dx;

муле

3 f(x) /Q,

-д--I .Х„ , . . . , ,и,Х;, , . . ,х., Г

Эх.

.f(:

-п Ui

,1 5Xj,,.. jX, )

астанием) переменной х;

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

астанием) переменной х;

Вьиисление производных по всем или нескольким переменным булевой функции можно рассматривать как ее преобразование с помощью произведения п операторов:.

...v.V, , где . ..®1;,®й® ®Ii,®...®

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

V, 1„®1„.,®...®12®л; .,®..)u®I, ;

,®...®1,®1, .

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

а). f(O).-f(0);

fd)--fd),

если булева функция не дифференцируется;

(0)®f(); f(0)®f(l),

если дифференцирование неориентировано, где знаком © обозначено сумми- рование по модулю два;

в)f(0)(0)f(l); fd)-- f(0)f(l),

если дифференцирование ориентирова- но на увеличение, где через и 0 обозначены операции инвертирования и логического умножения;

г)f(0)(0)f(l)

f(l)X .f(0)f(l)

если дифференцирование ориентировано на уменьшение.

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

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

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

На первые информационньхе входы устройства подаются управляющие сигналы h, ,h,j,... ,hg. Величины h, ,h поступают на управляющие входы ариф

метических ячеек подблока 4 , ah

h и hj, h на управляющие входы 4 2. и 4 5 соответственно.

5

подблоков 4 2. и 4 5 соответственно. Пр ориентированном на увеличение дифференцировании булевой функции по переменной X управляющие сигналы принимают значения: h(l, . Величинам h,0, соответствует отсутствие дифференцирования по переменной Xj, Дифференцирование, ориентированное .на уменьшение по переменной X,, задается кодовой комбинацией , .

На вторую группу информационных входов устройства 2, 22..,,2g подаются сигналы f(0,0,0), f(0,0,l) f(0,l,0), f(0,l,l), f(l,0,0), f(l,0,. 1), f(l,0,l), f(l,l,0), f(l,l,l), определяющие данную булеву функцию. Эти сигналы поступают на входы 13, и 13 каждой арифметической ячейки 5 подблока 4,,Через выводы 12, и 12z на адресные входы мультиплексоров 8, и 8г подаются величины h, 1, .

Благодаря этому сигналы, сформированные на вторых информационных

и- 5

- ю

15

я .

фифк-м,

30 гф20

25

35

При еиинн40

входах мультиплексоров редаются на их выходы, на выходах 14) и . 14 ячеек 5 подблока

8, и 8j пе- В результате 2 арифметических 4( присутствуют

величины f(0,0,0). f(0,0,l); f(0,0,0) (0,0,l); f(,0)-f(0,l,l); f(0,l,0) f(0,l,l); f(l,0,0).f(l,0,i); f(l,0,0)-f(l,0,l); f(l,l,0)-f(l,l,l); f( 1 ,1 ,0) -f(l ,1,1). С выходов 14, и арифметических ячеек 5 подблока 4 , информация передается на входы подблока 4.

.Благодаря соединениям на входах 13, и арифметических ячеек 5 подблока 4 J присутствуют сигналы f(0,0,0).f(0,0,l); f(0,l,0).f(0,l,l); f(0,0,0).f(0,0,l); f(0,l,0),f(0,l,l); f(l,0,0)-f(l,p,l); f(l,I,0).f(l,l,l); (l,0,0)-f(l,6,l); f(l,l,0)«f(l,l,l)-, соответственно. Через выходы 12, и 122 адресные входы мультиплексоров 8 , и 8 , арифметических ячеек 5 подблока 4 2 поступает кодовая комбинация 00. В результате информация с первых информационных входов мультиплексоров передается на их выходы. Благодаря наличию перекрестных связей на выходах подблока 2 присутствуют величины f(0,0,0)f(0,0,1); f(0,0,0)-f(0,0,l); f(0,l,0).f(0,l,l); f(0,l,0)-f(0,l,l); f(1,0,0)-.f(1,0,1); f(l,0,0).f(l,0,l); f(l,l,0).f(l,l,l); f(l,l,0).f(l, l,l).

Благодаря соединениям на выходы 13; и 13 арифметических ячеек 5 подблока 4, поступают сигналы (0,0,0) (0,0,l); f(l,0,0).f(l,0,l); f(0,0,0)..f(0,0,l); f(l,0,0).f(l,0,l); f(0,l,0),f(0,l,l); f(l,l,0).f(l,l,l); f(0,l,0) f(0,l,l); f(l,l,0) f(l,l,l). Через выводы 12, и 12 на адресные

5

0

5

входы мультиплексоров 5

8, и 8 арифметических ячеек подблока 4, подаются

величины .

В результате

:игналы, сформированные на третьих информационных входах мультиплексоров

8 , и 8 2, передаются на их выходы. Благодаря наличию перекрестных связей на выходах подблока 4 при- сутствуют величины f(0,0,0)f(0,0,1) f(l,0,0)f(l OJ), f(0,0,0)f(0,0,l) f(l.O.Q) f 1.0,1); f(0,l,0)-f(0,l,l)« xr(i,i,o) f( 1,1.0; f(o,i,o).f(0,1,1)

ff(lJ.O) fCl,l,l);f(0,0,0).f(0,0,l)f(1,0,0) f(1,0,1);f(0,0,0)-f(0,0,l)

fV1,0,0) f(1,1,1);f(0,l,0) f(0,l,l)

r(1,1,0) f(1,1,1);f(0,l,0)-f(0,l,l) f(l,l,0) fri,,).

Сигналы с выходов подблока 4 пода-f ( 1 ,0,0)ft)f(1,1,0) ; f (0,0,1 )©f (0,1 ,1 );

ются на информационные входы регист-f(1,0,1 )®f( 1,1,1).

pa 3 и записываются в него по заднему На адресные входы мультиплексоров

фронту синхроимпульса с шины 7. В ре- 8, и В. через выводы 12, и IZj подазультате на выходах устройства 6,,ется кодовая комбинация 01. Следова- 6j,..,6g имеем сигналы тождественные величинам, полученным с помощью сигнального графа на фиг. 3.

тельно, величины, сформированные на вторых информационных входах мультиплексоров, передаются на выходы 14( П р и м е р 2, Булева функция пе 10 ,и 14 , а затем посредством перекрест- дифференцируется по переменной X,, ных связей - на выходы подблока 4. дифференцируется неориентированно в результате на информационные входы по переменной х и дифференцируется D-триггеров регистра 3 поступают сиг- ориентировано на увеличение по пере- налы гТо,0,0)©Г(О,1ТоД Cf(1,0,0)© менной X,. В этом случае вектор ис- 5 ®f(l.l.O); : f(0,0,l )®f(0,l ,1)11 тинности f(x, ,х,х,) преобразуется (.J,0,,l )fflf ( , j 01 , fTO,0,0)® согласно сигнальному графу, приведен- ®f (07170)3 f ( 1 ,0,0)®f( 1 ,1 ,0); ному на фиг. 4.ff(0,0,1 ©ТГоТГТТ) f (1 ,0,1 )®f (1 ,1 ,

Л; Cf(0,0,OJ®fToTl,0) f(1,0,0)®

На управляющие входы устройства

поступают сигналы: h,0; 20 ®f(l,1,0)1; f (О ,0,1 )ef (О ,Т7Т) h,l; h., l; .x f (l ,0,1 )ЙГ ( 1 ,1 ,1) ; f-f (0,0,0)©

@f(0,l,0)- f(l,0,0)®f( 1 ,1 ,0)3 ;

Через вторую группу информационных входов устройства 2,,2,„..,2д на входы 13, и 13/2 арифметических

f(0,О,l)©f(0,,) f(l,0,l)®f(l, 1,1).

ячеек 5 подблока 4, подаются величи- 25 По заднему фронту синхроимпульса, поны f(0,0,0), f(0,0,l), f(0,l,0), f(0,l,l), f(l,0,0), .f(,0,l), f(l, 1,0), f(1,1 ,1 ) соответственно. Ha адресные входы мультиплексоров Bf и 82 арифметических ячеек 5 подблока 4, поступает кодовая комбинация 00. В результате сигналы с первых информационных входов мультиплексоров передаются на выходы 14, и 14...

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

f(o,a, 1), f(uo,o), f( 1,1,0),

f(l,0,l), f (1,1,1).

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

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

35

1. Устройство для вычисления булевых производных, содержащее регистр и блок вычислений, причем тактовый вход устройства соединен с тактовым 40 входом регистра, выход) которого яв- I- ляются выходами устройства, первая

На управляющих входах арифметичес- которого соединена с ких ячеек присутствуют величины h,- оцо:л первой группы блока вычисле- -1, h,-l. Следовательно сигналы, . выходы, которого соединены с ин.. .f, ДЗ Формационными входами регистра,

отличающееся тем, что, с целью повышения быстродействия, блок вычислений содержит п групп из арифметических ячеек (п - количество переменных), причем вторая группа входов устройства соединена. с информационными входами арифметических ячеек первой группы блока вычислений, информационные входы j-й арифметической ячейки (1,) i-й группы (,п) соединены с соответствующими выходами арифметичес- id)f(l,l,l)); f (0,0,1 )®f (о , 1 ,1 );ких ячеек (1-1)-й группы, выходы

f ( 1 ,0,1 X9f(1,151 ); f(0,0,0)©f(0,1,0); арифметических ячеек последней групционных входах мультиплексоров 8, и 8i, передаются на их выходы 14, и 14. Соединения обеспечивают присутствие на выходах подблока 4 величин f(0,Q,0)®f(0,l,0); f(0.,0,l)©f(0,1,1); f(0,0,0)d)f(0,l,0); f(0,0,l)©f(0,l,l); 50 f(l,0,0)®f(l,l,0); f(l,0,l)®f(1,1,1); f(l,0,0)®f(1,1,0); f(1,0,1 )@f(1,1,1).

С входов подблока 4 посредством перекрестных связе.й на входы арифметических ячеек 5 подблока 4 поступают 55 сигналы f(0,0,0)®f((,l ,0); Г(1,0,0)Ф

f(0,О,l)©f(0,,) f(l,0,l)®f(l, 1,1).

о заднему фронту синхроимпульса, по

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

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

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

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

Sfl

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

7

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

f

2

12i

9l

fOi

L

(fdi

3z

Юг

Г

jr/5 Фие2

то,9}

f{HO.Jf f (0,1,0)

Mi,i)

f(lO,Of f (1.0,1)

jUioj

ya/,/;

. ,-fr-.|pg(, J) X .жа0;/л«/;

Ч..( в }.ОЩ(111}

о .w tmii) .Qmo.i)

.., о, 1) o- -jjst--а /Г/, io)u IJ) f JIi.},o}MJ,J}

.o) , (o.o,i)

)

)

jd.o.o)

,1)

i(i,W

-wfuj;

imo)®Mi.o) ,moij} j(o,i.i)

(0,0,0) фМго) Mo.i) ®j-(o,ii) ЩО) ®ЛШ)

f(i,o.}) ®flm} f(i,uo) ej{j.w

J{lOJ)Qf{n,J) Фия.

mo,o} Jo-jJ i.o.oU(w.i) jio.o,owaoj) шоМ)Ши1} mip) a.i,i)f(i,w)fiw}

jpta. },o) т I

толМиО, 1)(10,0)M0.1)

то.оШо, nJd.o.OJMQ.i) T(Q. WjflQ. I /Ш r. OUd 1.1)

(o-vmw)f(i. i,i)

&(o.o,o ®Mi.oi)Cf{lo,Q).OjJ LfCo.o.i) .Ш Cf(m.j) f(ii.i) LiM MUlilm) ®fni,ffff ®f(O.V) .t) uf(ofifl) .1,) ®MW)J Шо.1 ®flaii,i)Cfllo,l) f,iff CKW) ®JiuW).W.O.O)®f{lW)

®mi.io&ii.o.i}®(wQ