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

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

Цель изобретения - расширение функциональных возможностей за счет ориентированного и неориентированног дифференцирования булевой функции по k переменным (k 1, п, где п - количество переменных).

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

Устройство для вычисления булевых производных содержит группы 1 и 2 входов, коммутаторы 3 и 4, группу 5 элементов НЕРАВНОЗНАЧНОСТЬ, сдвиговые регистры 6 и 7, блок 8 вычислений, блок 9 памяти, счетчик 10 по модулю п, тактовый вход 11 устройства и вход 12 установки в исходное состояние.

Блок 9 памяти включает в себя 2

D-триггеров 9, 9, 9,, ... ,9,, -оединенных по входам синхронизации и

входам установки в нулевое состояние

Первый коммутатор 3 содержит 2

мультиплексоров 3 3,2 1°8 п 1

адресных входов которых подключены к шине 13 (С 1 - знак округления до ближайшего целого числа). Первые информационные входы мультиплексоров образуют , первую группу информационных входов 14,...,Ah коммутатора 3. Остальные информационные входы каждого мультиплексора, число которых составляет по меньшей мере п-1, подключены к соответствующему входу второй группы 15 , .. ., 1 5,h ин- формацнонных входов коммутатора 3. Выходы 16 ,,.., мультиплексоров 3 ,...,32П являются выходами коммутатора 3.

Группа 5 элементов НЕРАВНОЗНАЧНОСТЬ состоит из 2 сумматоров по

Блок 8 вычислений содержит 2 ментов НЕ 17 2

эле- злемен-

тов и 18|,.. ., . Каждый из входов 1 9 , .. ., 1 9,j 1 блока 8 вычислений подключен к входу соответствующего элемента И 18, (i 1, 2) и через элемент НЕ 17 j ко входу элемента И 18. (18,,), если i - нечетное (i - четное). Выходы п-1 нечетньГх

и выходы 21 ,...,21,2h-i четных элементов И 18 ,..., 18 , образуют соответственно первую и вторую группы выходов блока 8 вычислений.

Второй коммутатор 4 содержит 2 мультиплексоров 4 ,... ,4 , адресные входы которых соединены с управляющими входами 22 и 22 Q коммутатора 4. Выходами 23

0

5

1 о

, ..., 23 коммутатора 4 являются выходы соответствующих мультиплексоров

0

5

0

5

Управление устройством осуществляется с помощью двух сдвиговых регистров 6 и 7. По группе входов 2 на сдвиговые регистры подаются управляющие сигналы Ь„п,...,Ц. Четные Ь„ величины поступают на параллельные входы сдвигового регистра 6, нечетные на соответствующие входы регистра 7 (i 1, п). Согласно кодовой комбинации (h,, h . ), хранимой в i-M разряде регистров, устройство выполняет следующие преобразования булевой функции:

00- по переменной х (i I, п)

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

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

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

11- булева функция дифференцируется ориентщзованно на увеличение.

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

3f(x)

0

Производной

х

от булевой

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

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при построении систем тестового и аппаратурного контроля цифровых устройств. Цель изобретения состоит в расширении функциональных возможностей за счет ориентированного и неориентированного дифференцирования булевой функции по k переменным (k I, п, где п - число переменных). Устройство содержит две группы входов 1, 2, два коммутатора 3, 4, группу элементов НЕРАВНОЗНАЧНОСТЬ 5, два сдвиговых регистра 6, 7, блок вычислений 8, блок памяти 9. На группы входов подаются соответственно вектор истинности и двоичный код, записываемый в сдвиговые регистры, который определяет для каждой переменной необходимость дифференцирования, а также тип производной. Полный цикл функционирования устройства составляет п тактов (п - число переменных). Счетчик хранит номер текущего такта и управляет работой пер вого коммутатора, на выходах которого в первом такте имеет место вектор истинности, а в последующих тактах - преобразованный вектор с вькодов блока памяти. Преобразования осуществляются группой элементов НЕРАВНОЗНАЧНОСТЬ, если дифференцирование неориентированное, и блоком вычислений, если производная по данной переменной ориентирована. Выбор соответствующих сигналов с целью записи в блок памяти производится вторым коммутатором под управлением двоичного кода с выходов сдвиговых регистров. 3 з.п. ф-лы, 6 ил. с S (О

модулю два )

а X,

55

f(x

.х,,,.0,

определяемая по формуле: X,,,... ,х, )@ f (х, . . . ,х,,,,1 ,х,.,,. ..X, )

Производная

af(x)

характеризует

д X,изменение функции f(X) при изменении переменной х и равна единице на тех

входных наборах, на которых изменение переменной х приводит к изменению функции.

Ориентированные булевы производные д f(X) „ a f(X) . д х- характеризуют

не только изменение, но и направление 5

„i fM f(,.0,Х, ,,..,Х,) f(,,,1, Х,,,....Х,)

Эх.

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

JI IM f,

д X.

Чх,...,х,,0,

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

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

v , ... v V,

где V дифференцирует f(X) только п меременной х.

При п 1 оператор v представим единичной матрицей:

если булева функция соответственно не дифференцируется или дифференци- если булева функция не дифференциру- 35 РУется неориентированно (остальными ется, а также матрицей:элементами этих матриц являются нули).

если дифференцирование неориентированно.

В случае ориентированного дифференцирования оператор q , являясь нелинейным, может быть представлен сигнальными графами вида:

f(0)-t.-o-f(0) f(l)

Ч

N,

f(0) f(l)

O

--f(O) f(,l) f(O) f(I)

изменения функции f(X) при изменении

переменной х.Э°(Х)

ВозрастаиЛцая производная - j-- определяется по формуле:

a f(X) Убьшающая производная оп-

Зх

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

,хр f4x,...,x,l,x,,,..,x)

где через v и О обозначены операции инвертирования и логического умножения.

Эти сигнальные гра реализуются при вычислении возрастающей и убывающей производных соответственно, При п 2 оператор v (i 2)

представим матрицами:

25

30

Вычисление возрастающей и убываю- 40 щей производной по переменной х j (i 1, 2) задается сигнальными графами:

f(0,0) f(0,I) f(l,0) f(l,l) f(0,0) f(0, 1) f(l,0) f(l,l)

(3)

(1)

f(l.l)

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

(4)

При n - 3 матрицы

10

10

101

10

01

01

lOl

101

задается отсутствие дифференцирования и неориентированное дифференцирование 20 по переменной х (i 1 3) (остальными элементами этих матриц являются нули).

.(0,0,0)(0,0,1)

f(0,l,0)f(0,l,l)

,(1,0,0)(1,0,1)

(1,1,0)(1,1,1) (6)

(0,0,0)(0,0,1)

(0,1,0)f(0,1,1)

(1,0,0) (,0,1)

(1,1,0) (1,1,1)

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

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

(0,0) (0,1) (1,0). (1,1) (0,0) (0,1) (1,0) (1,1)

По группе входов 2 на сдвиговые регистры 6 и 7 подаются управляющие

Вь1числение возрастающей и убыва- производных по переменной х- (i 1, 3) задается следующими сигнальными графами:

f(0,0,0)(0,0,0) f(0,0,l)

f(0,0,l)

f (О, 1,0 ),.

f(0,I,l

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

15 f(I,0,0) Г(0,0,0) f(0,0,l)

f(i,o,ir

f(0,,0) f(0,1,1)

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

f(l,l,l)

fd.l.O) f(l,l,l) (5)

х и ориентированно на уменьшение по переменной х„.

5 в этом случае преобразование вектора истинности (х , X ) описывается следующим графом:

(0,0) (0,1) (0,0) (1,1)

(0,0) (0,1) (1,0) (1,1)

(7)

(0,0) (0,1) (1,0) (1,1)

(0,0) (0,1) (1,0) (1,1)

I

сигналы h , hj, h,, h, . Величины h , h-, поступают на параллельные входы

сдвигового регистра 6, ah , h, - иа соответствующие входы сдвигового регистра 7, На выходах регистров 6 и 7 в первом такте присутствуют сигналы h., hj, а во втором такте h,j, h соответственно. Для того, чтобы булеву функцию дифференцировать ориентированно на увеличение по переменно X, и ориентированно на уменьшение по переменной х-, на группу входов подается кодовая комбинация h 1, hj I, h 1, h, О.

По входу 12 .поступает сигнал, который устанавливает счетчик 10 и блок 9 памяти в нулевое состояние, а также разрешает запись в сдвиговы регистры 6 и 7 кодовой комбинации, присутствующей на группе входов 2.

С группы входов 1 на первые ин- формационные входы 14.,, 14 , 14, 14 коммутатора 3 подаются сигналы f(0,0), f(0,l), f(l,0), f(l,l), определяющие заданную булеву функцию.

В первом такте с выходов счетчи- ка 10 по шине 13 на адресные входы мультиплексоров 3 , 3., 3 , 3, поступает кодовая комбинация 00, В результате величины f(0,0), f(0,I), f(l,0), f(l,l) передаются на выходы 16, Ь, 16J, 16. коммутатора 3.

Сигналы с выходов 16, 16, 16, 16, поступают на группу входов 19 блока 8 вычислений, который формирует на выходах 21,2 величины (0,0) f(0,I) и f(l,0) f(l,l) соответственно.

Сигналы с выходов 21 и 21 блока И вычислений подаются на входы 27 и 27 „ коммутатора 4. С выходов сдвиговых регистров 6 и 7 через входы 22 и 222 на адресные входы мультиплексоров 4, 4, 4j, 4 поступают сигналы h 1, h 1. Благодаря этому информация с четвертых информа ционньос входов мультиплексоров 4 , 0. 3 передается на их выходы. В результате на выходах 23,, 23, 23э , 23, коммутатора 4 присутствуют соответственно сигналы f(0,0) f(0,l f(l,0) f(l,l), f(0,0) f(0,l), f(l,0) f(l,l), описываемые выражением (3).

Информация с выходов 23, 232,, 23о, 23 коммутатора 4 подается на информационные входы блока 9 памяти и записывается в него по окончании первого такта.

Q

5

20

25 30

д .г °

5

В результате на выходах устройства , а следовательно, и на входах 15,, 15,2 , 5., 5 проявляются сигналы f(0,0) f(0,l), f(I,0) f(l, I), f (0,0) f(0,1), f(l,0) . f(l,l) соответственно, описываемые результирующим вектором из (3).

По заднему фронту синхроимпульса с входа II счетчик 10 переводится в состояние 01, а в сдвиговых регистрах 6 и 7 происходит сдвиг содержимого в сторону младших разрядов.

Во втором такте коммутатора 3 по шине 13 передается кодовая комбинация 01. Благодаря этому сигналы F(0,0)- f(0,l), fil,0) f(l,l), f(0,0) f(0,l), f(l,0) f(l,l), присутствующие на входах 15 , 15 , 15 , 15, , поступают на группу выходов 16 коммутатора 3.

С выходов 16, 16-, 16-, 16 сигналы поступают на группу входов 19 блока 8 вычислений. В результате преобразований на выходах 20 и 20 при- сутствует величина f(0,0) f(0, 1), «f(l,0) f(l,l).

Сигналы с выходов 20, и 202 блока 8 вычислений передаются на входы 26 и 26 ,, коммутатора 4, с выходов сдвиговых регистров 6 и 7 через входы 22 и 22 на адресные входы мультиплексоров 4, 4-, 4,, 4 поступают сигналы h 2 I, h, 0.J3 результанте

величина f (0,0)-f (0,1). ГоТоУТоТО с входов 26i и 26 передается на выходы мультиплексоров 4f, 4 выходах 23, 23, 23., 23 коммутатора 4 присутствует одна и величина f(0,0) f(0, 1)« « f(l,0) -(1,1), сформированная в соответствии с выражением (7).

Информация, переданная с группы выходов 23 коммутатора 4, присутствует на информационных входах блока 9 памяти и записывается в него по заднему фронту синхроимпульса с входа 11. Следовательно, сигналы, присутствующие на выходе устройства, тождественны величинам, получаемым согласно выражению (7).

Пример 2. Булева функция дифференцируется неориентированно по переменной х и не дифференцируется по переменной х„.

В процессе неориентированного дифференцирования по переменной х вектор истинности f(х , х ) преобразуется следующим образом:

1 I

I 11

итсутствию дифференцирования по X г, соответствует следующее преобра-

10

01

f(0,0) ® f(0,l) f(l,0) ® f(l,l) f(0,0) © f(0,1) f(l,0) @ f(l,l)

Выполнение преобразования вектора истинности f(Xn, х) с помощью предлагаемого устройства для вычисления булевых производных.

По входу 12 поступает сигнал, который устанавливает счетчик 10 и блок 9 памяти в нулевое состояние, а также разрешает запись в сдвиговые регистры 6 и 7 кодовой комбинации h 1, Ьз О, hg О, h, О На первые информационные входы коммутатора 3 через группу входов 14 подаются сигналы f(0,0), f(0,l), f(l,0),

f(l,l).

В первом такте с выходов счетчика 10 по шине 13 на адресные входы ль типлексоров 3, 3 , 3 , 3 поступает кодовая комбинация 00. В результате информация с первых информацион ных входов подается на выходы 16., 16,, 16,.

С выходов 10,, iDj налы f(0,0), f(0,l), f(1,0), f(l,l) поступают на входы группы элементов НЕРАВНОЗНАЧНОСТЬ 5.

В результате преобразований на выходе:этой группы присутствуют величины f (0,0)@f(0, 1), f(l,0) Of (1, 1), KOTOptje поступают на группу входов 24 коммутатора 4.

С выходов сдвиговых регистров 6 и 7 через входы 22 и 22. на адресные входы мультиплексоров 4,, 4, 4., 4 поступают сигналы h 1, h. 0,

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

16 коммутатора 3.

16,, 16„, 16, 1б4 сиг

2

S.

передается

На выходах 23., 23„

f(0,0) 0 f(0,l)

f(l,0) 0 f(l,l)

(8) f(0,0) ©f(0,l)

f(i,o) © fd.i)

зование вектора, полученного в (8): f(0,0) @ f(0,l)

(9)

f(0,0) ® f(0,l) f(l,0) & f(l,l) f(l,0) @ f(l,1)

5

0

5

Q

5

0

23 , 23, коммутатора 4 присутствуют сигналы соответственно f (0,0) ® f (О, 1 ) f(l,0)©f(l,l), f(0,0)@f(0,l), f(l,0)©f(l,l), которые формируются согласно выражению (8).

Сигналы с группы выходов 23 мультиплексоров 4 , 4 , 4,, 4, подаются на информационные входы блока 9 па- мя . По заднему фронту синхроимпульса сигналы с информационных входов блока памяти 9 записываются в триггеры 9, 9, 9oj, 9,. В результате на выходе устройства и на группе входов 15 коммутатора 3 имеются соответственно сигналы f (0,0) @f (О, 1), f(I,0)@ Glf(l,l), f(0,0)©f (0,1), f(l,0)® ©f(l,l).

По Окончании такта счетчик 10 переводится в состояние 01, а в сдвиговых регистрах 6 и 7 происходит сдвиг содержимого влево на I разряд.

Во втором такте с выходов счетчика 10 на управляющие входы коммутатора 3 по шине 13 передается кодовая комбинация 01. Следовательно, сигналы (0,0)0 f(0, 1), f (l,0)®f (1, 1), f (0,0)©f (0,1), f (l,0)®f (1,1), присутствующие на группе входов 15, через вторую группу информационных входов коммутатора 3 передаются на его

выходы 16, 16п /1

С группы выходов 16 сигналы f(0,0) 0f(0,l), f(l,0)©f(l,l), f(0,0)@f(0,l), f(l,0)®f (1,1) поступают на входы 25, 25 , 25 , 25, коммутатора 4.

С выходов сдвиговых регистров 6 и 7 через входы 22, и 22 на управляющие входы коммутатора 4 поступают сигналы , h, 0. В результате информация с первых информационных входов передается на выходы муль типлексоров 4

Ч S.

V 23,

На выхо- коммутатора 4

1

дах 23, 23,, 23 присутствуют соответственно сигналы f(0,0)@f(0,l), f(0,0)@f(0,l), f(l,0)©f(l,l), f(l,0)©f(l, I), которые тождественны величинам, полученным ..согласно выражению (9).

Информация, переданная с группы выходов 23 коммутатора 4, присутствует на информационных входах блока памяти 9 и записывается в триггеры

q 9

Ч 3

с приходом синхроимпульса по входу 11.

15 второй группы устройства, выходы первого и второго сдвиговых регистров соединены с управляющими входами второго коммутатора.

Сигналы, поступающие на выход уст-2о чающееся тем, что первый коммутатор содержит 2 мультиплексоров, причем первьш информационный вход i-ro мультиплексора (i I, 2) соединен с i-M информационным входом первой группы первого коммутатора, с второго по (п-1)-й информационные входы i-ro мультиплексора объединены и соединены с i-м информационным входом второй группы коммутатора, уп-

ройства, тождественны величинам, полученным согласно выражению (9).

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

25

НЕРАВНОЗНАЧНОСТЬ и блок вычислений, зо равляющие входы которого соединены причем первая группа входов устройст- с управляющими входами мультиплек35

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

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

k переменным (k 1, п, где п - количество переменных), в него введены блок памяти и счетчик, причем выходы первого коммутатора соединены попарно с входами элементов НЕРАВНОЗНАЧ,-50

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

,-50

НОСТЬ группы и информационными входа- ми второго коммутатора, ми второй группы второго коммутатора, информационные входы третьей и четвертой групп которого соединены с вы ходами первой и второй групп блока вычислений соответственно выходы второго коммутатора соединены с информационными входами блока памяти, выходы которого соединены с выходами

55

устройства и информационными входами второй группы первого коммутатора, управляющие входы которого соединены

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

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

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

35

+ 1 )-го по 2 -й мультиплексоров сое- динены с нечетньми и четньми инфор- мационными входами второй группы вто- д рого коммутатора, информационные вхосоров, выходы которых явдяются выходами первого коммутатора.

0

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

ми второго коммутатора,

ми второго коммутатора,

55

та И, выход 2т-го элемента НЕ соеди-первой группы блока, j-й выход втонен с вторым входом (2т-1)-то эле-рой группы которого соединен с выхомента И, выход (2in-l)-ro элемента Идом 2т-го элемента И.

.л J .П J

О -5.

Е

Fif

П J

- .

ш

О -5.

Г

ду

..d

Фиг. 2.

О Ооб

20, 202 202П-1

П /

Фиг.

22r, 22,

фиг. 6