Устройство для вычисления булевых дифференциалов

Устройство для вычисления булевых дифференциалов

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (ц С 06 F 7/00

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

H А BTGPCHGMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4412940/24 (22) 19.04.88 (46) 07.1il.91. Ьюл. №- 41 (72) В.М.Полищук и Н.Н.(Цубина (53) 681,3 (088.8) (56) Авторское свидетельство СССР №- 4315768/24, кл. С 06 F 7/00, 1987.

Авторское свидетельство СССР № 1587487ь кл. G 06 Р 7/00ь 1988 °

>5& 1689942 А1 (54) УСТРОЙСТВО ДДЯ ВЫЧИСЛЕНИЯ НУЛЕВЫХ ДИФФЕРЕНЦИАЛОВ (57) Изобретение относится к автоматике и вычислительной технике и предназначено для автоматизации процесса вычислений при проектировании средств тестового и аппаратного контроля комбинационных схем и для анализа структурной надежности дискретных уст1689942

10 ройств. Целью изобретения является расширение функциональных возможнос тей устройства за счет вычисления булевой разности функции, заданной в диэъюнктивной нормальной форме (ДНФ), определения "веса" булевой функции и "веса" булевой разности, а также преобразования булевой функции из ДНФ в совершенную ДНФ (СДНФ) °

Устройство для вычисления булевых дифференциалов содержит группу входов

1» -1» искомых переменных, вход 2 запуска устройства, группу 3К-триггеров, 3»-3, дешифратор 4, узел 5 идентификации, вычитающий счетчик 6, . суммирующий счетчик 7, УК-триггер 8, четыре группы элементов И 9» -9g

10» -101», 11»-1 111 и 12» -1» 1, семь

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

Цель изобретения - расширение функциональных возможностей устройства за счет вычисления булевой разнос. 35 ти функции, заданной в дизъюнктивной нормальной форме (ДНФ), определение

"веса" булевой функции и "веса" булевой разности, а также преобразования булевой функции из ДНФ в совершенную 0

ДНФ (СДНФ), На фиг.1 представлена структурная схема устройства для вычисления булевых дифференциалов; на фиг.2функциональная схема узла идентификации 4

Устройство (фиг.1) содержит груп-. пу входов 1» -1 { искомых переменных (N - максимальное число переменных булевых Функций) вход 2 запуска устройства, группу .IK-триггеров, 3» -Зщ, дешифратор 4, узел 5 идентификации, вычитающий счетчик 6, суммирующий счетчик 7, IK-триггер 8, четыре группы элементов И 9» -9 1, 10» -10ц, 11» -11 {, 121-12, семь элементов И

13-19, шесть элементов ИЛИ 20-25,, пять элементов 26-30 задержки, выход

31 узла 5 идентификации, выход 32 элементов И 13-19, шесть элементов

ИЛИ 20-25 и пять элементов задержки

26-30. Устройство в зависимости от кода настройки может работать в четырех режимах. На группу входов искомых переменных заносится код, определяющий, по какой переменной проводится вычисление булевого дифференциала. В вычитающий счетчик 6 заносится код, соответствующий максимальному числу наборов искомой функции, в узел идентификации заносится код элементарных конъюнкций. На выходе суммирующего счетчика 7 формируется значение "веса" искомой функции для заданного режима. 1 з.п. A-лы, 2 ил., 2 табл. признака окончания вычисления 32, группу выходов искомых наборов переменных 33» -33 {, выход 34 признака определения очередного набора переменных, вход 35 обнуления, выход 36

"веса" булевой .разности, N групп входов задания первого кода 37» -37,1 е узла идентификации (М вЂ” максимальное количество элементарных конъюнкций заданной функции), М групп входов второго кода 38»-38 », два настроечных

Я входа 39 и 40 устройства, группу входов задания наборов 41»-41 {, две группы входов 42»-42м и 43» -43» узла

5 идентификации.

Узел 5 идентификации (фиг.2) содержит два блока групп элементов

KIN 44»-44 и 45, -45, группу злемен{t{ тов ИЛИ 46»-46{ {, груйпу элементов И

47 -47 и элемент ИЛИ 48.

Элементарную конъюнкцию ранга гоп можно кодировать двумя двоичными и-разрядными кодами А (а{...а;...а {) н е (bt ... Ь; ... Ь ), гДе е<,b;f{0,11, причем для всех х;, содержащихся в элементарной конъюнкции, и только для них в i-х разрядах первого кода записывается "0", в остальных разряII tt дах 1, а для всех х — в i х разрядах второго кода 0, в остальных

Ii разр .дах - "1". При этом, если n(N, то в оставшиеся (N-п)старших разрядов групп кодов записываются единицы.

Незадействованные входы кодов групп

5

16899 (не содержащие элементарных конъюнкций) должны быть обнулены,, При таком способе кодирования определение факта поглощения элементарной конъюнкцией принятого набора nepeMeHHbIx х(х„ ° ..х,...х ), где х,=0 или

1 (i=1,N), осуществляется проверкой следующего условия:

n " а 10

P(ga;x;)=P (Q Ь;х; = 1 °

i=3 =4 =4

Устройство работает следующим образом.

В исходном состоянии в узел 5 идентификации поступают коды элементарных конъюнкций. В и младших разрядов вычитающего счетчика 6 записываются "1", в остальные — "0" (исходя из количества и переменных заданной 20

Функции), суммирующий счетчик 7 обнуляется сигналом с входа 35 обнуления.

Работа устройства начинается с приходом единичного сигнала на вход 2 запуска устройства. Устройство может 25 работать в четырех режимах.

Коды настроек для каждого из четырех режимов приведены в табл.1.

Режим 1. Вычисление неориентированных булевых дифференциалов (R,). 30

Булевым дифференциалом (разностью) логической функции Е(х,...,х 1) по переменной х; называется логическая функция R(xg ° ° ° хp)=Р(х() ° ° ° рх ) ° ° . ° p с / и) m г (х1 s ° ° ° ix) y ° . ° х ) ° 35

Определение наборов переменных, соответствующих функции R

Сигнал с входа 2 запуска устройства через элемент ИЛИ 20 обнуляет IKтриггеры 34 -3 g группы и I К-триггер

8, задерживается на элементе 26 задержки (время задержки определяется временем переходных процессов в вычитающем счетчике 6), копирует через эле- 45 менты И 10 -10 группы содержимое вычитающего счетчика 6 вХК-триггеры

3 -Зд группы и поступает через элемент ИЛИ 22 на элемент 29 задержки.

Содержимое IК-триггеров 3 -ЗN представляет собой проверяемый набор переменных х(х4,...,х 1), который в виде

:прямых и инверсных значений с выходов триггеров 3 -31 подается на входы

42 -42м и 43,-43> узла 5 идентификации.

На выходе 31 узла 5 идентификации формируется сигнал единичного уровня лишь в том случае, если проверяемый набор поглощается хотя бы одной < элементарных конъюнкций заданной функции. В противном случае на выходе

31 узла 5 идентификации формируется сигнал нулевого уровня. Если на выходе узла 5 идентификации сформирован сигнал единичного уровня, то задержанный на элементе 29 задержки сигнал (величина задержки определяется суммарным временем переходных процессов в элементе И 10, I К-триггере 3; группы и узел 5 идентификации) пройдет через элемент И 14 и установит

IK-триггер 8 в единичное состояние °

В противном случае в I К-триггере 8 записывается сигнал логического "0".

Кроме того, сигнал с выхода элемента ИЛИ 20, задержанный на элементе 27 задержки (задержка определяется сум марным временем переходных процессов в вычитающем счетчике 6, элементе И

10, IK-триггере 31 группы и узле 5 идентификации) после того, как осуществятся указанные действия, пос— тупает на первые входы элементов И

9А-9 1 группы, элемент KIH 22 и элемент 28 задержки. В зависимости от того, по какой переменной х ведется вычисление булевого дифференциала (что определяется единичным состоянием i-го разряда группы входов

1 -11 искомых переменных), сигнал единичного уровня с выхода элемента

И 9 группы поступает на счетный вход соответствующего I К-триггера 3 -3 я группы и устанавливает его в состояние, противоположное исходному, чем обеспечивается преобразование предыдущего набора переменных в набор переменных, у которого значение переменной х; изменилось на противоположное. С этого момента снова повторяется процесс идентификации, т.е. проверка в узле 5 идентификации факта равенства или неравенства заданной функции единице на преобразованном наборе переменных. К этому моменту сигнал с выхода элемента ИЛИ 22, задзржанньй на элементе 29 задержки, поступает на элемент И 14 и в случае единичного сигнала на выходе узла 5 идентификации проходит через этот элемент и устанавливает IK-триггер 8 в состояние, противоположное исходному.

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

1) и "a первоначальном, и на преобразованном — "0";

2) и на первоначальном, и на преобразованном — "1";

3) на первоначальном — "0", а на преобразованном — "1 " ; .

4) на первоначальном — "1", а на преобразованном — "0".

При ситуации 1 или 2 IK-триггер 8 в итоге находится в начальном нулевом состоянии. При этом на элементе И ,19 формируется сигнал нулевого уровня. Закрыты также элементы И 17 и 18 ! (последний сигналом нулевого уровня с выхода дешифратора 4). Поэтому сигнал, задержанный на элементе 28 задержки (задержка определяется суммар- 20 и,w. временем переходных процессов в элементах ИЛИ 22, И 14, IK-триггере 8 и временем задержки на элементе 29) и элементе 30 задержки (задержка определяется суммарным временем перехоцных процессов в элементах И 17, И 18 или И 19, элементах ИЛИ 25 и

И 11) проходит через открытый элемент И 13 и поступает на вход элемен та KIN 20 и счетный вход вычитающего счетчика 6, чем обеспечивается формирование очередного набора переменных и повторение указанного процесса.

При ситуации 3 или 4 на тактовый вход IK-триггера 8 поступает только

33 один сигнал,, что обеспечивает его установку в единичное состояние. При этом элемент И 19 открыт как потенциалом с выхода IK-триггера 8, так и потенциалом с первого выхода дешифратора 4 (в соответствии с выбранным режимом). Поэтому сигнал, задержанный на элементе 28, кроме указанных действий проходит через элементы И 19 и ИЛИ 25, поступает на счетный вход суммирующего счетчика 7 и увеличивает его содержимое на единицу, поступает. на входы элементов И 11 -11 1 группы.

На выходах искож х наборов переменных

33 -331 устройства фиксируется сформированный на вычитающем счетчике 6 набор переменных, который принадлежит искомой булевой разности, На выходе

34 признака определения очередного набора переменных формируется сигнал

55 единичного уровня.

Процесс вычисления заканчивается после обнуления вычитающего счетчика

6. На выходе 32 признака окончания вычисления формируется сигнал диничного уровня, при этом в суммирующем счетчика 7 подсчитывается "вес" булевой разности.

Режим 2. Вычисление булевого дифференциала (разности) по i-й переменной, ориентированного на увеличение (RA х;) .

Булевым дифференциалом„ ориентированным на увеличение, называетсябулева функция, равная единице только на тех наборах переменных, на которых. заданная булева функция изменяется при изменении i-й переменной в этих наборах из нуля в единицу.

После занесения исходных данных для этого режима и подачи единичного сигнала с входа 2 запуска устройства осуществляются действия, аналогичные для режима 1. Особенностью является то, что в данном случае элемент И 19 постоянно закрыт сигналом нулевого уровня (с первого выхода дешифратора

4), а задержанный на элементе 28 задержки сигнал может пройти лишь через .элементы И 17 и ИЛИ 25 и выполнить указанные,в режиме 1) действия. Это случается при наличии .ситуации 3 или

4, а также, когда в преобразованном наборе переменных i-я переменная равна единице, т.е. когда соответствующий (i-й) J K-триггер из группы I Ктриггеров 31-3 > находится в единичном состоянии. Тогда на соответствующем элементе И t21-12 группы произойдет совпадение единичных сигналов.

Сформированный таким образом сигнал единичного уровня через элемент ИЛИ

23 поступает на первый вход элемента

И 16. На втором входе элемента И 16 для данного режима также сигнал еди-" ничного уровня, который с выхода этого элемента через элемент ИЛИ 24 подан на вход элемента И 17. В против.ном случае на элементе И 17 формируется сигнал нулевого уровня.

Режим 3. Вычисление булевого диАференциала (разности) по i-й r.åpåìeíной, ориентированного на уменьшение (kg х;).

Булевым дифференциалом, ориентированным на уменьшение, называется булева функция, равная единице только на т х наборах переменных, на которых заданная булеза функция изменяется при изменении i-й переменной в этих наборах из единицы в нуль.

lO

89942

peнц11ял по переменно11 х q, В 11схо. 1110 состоянии на М (М=З) групп входо11 задания первого кода узла идентификации заносятся следующие данные:

37, — 371 = 01101;

37 — 3? s= 010011;

37 — 37Д = 10110.

На М груйп входов задания второго кода узла идентиАикации заносятся следующие данные:

38(— 38 - = 11111

38(— 38 = 11111

9 1б

Работа устройства аналог11«.11а !IpPдыдущему случаю (режиму 2). Особенностью является то, что элемент И 17 открыт для прохождения сигнала, задержанного на элементе 28 задержки лишь в том случае, когда в преобразованном наборе переменных i-я переменная равна нулю, т.е. когда соответствующий триггер из группы 1К-триггеров 3<-31 находится в нулевом состоянии. При этом ни на одном из элементов И

12 -12И не г.,>оисходит совпадения потенциалов, чем обеспечивается наличие единичного сигнала на инверсном выхо1 де элемента KIN 23. На выходе элемента И 15 Аормируется сигнал единичного уровня (на третьем выходе дешифратора 4 также сигнал единичного уровня) и передается через элемент ИПИ 24 на вход элемента И 17.

Режим 4. Преобразование ДНФ в СДНФ

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

При этом преобразования первоначального набора переменных на fK-триггерах 3 -31 группы не происходит, так как все разряды на группе входов искомых переменных в этом режиме равны нулю. Элементы И 17 и. 19 постоянно закрыты сигналами нулевого уровня (с соответствующих выходов дешиАратора 4), а элемент И 18 постоянно открыт по входу, связанному с четвертым выходом дешифратора 4. Поэтому задержанный на элементе 28 задержки сигнал проходит через элементы И 18, ИЛИ 25 и далее по известным цепям лишь тогда, когда заданная функция на сформированном наборе переменных равна единице, что Аиксируется наличием единичного потенциала на выходе узла

5 идентификации. Состояние JK-триггера 8 в данном случае значения не имеет.

В результате на группу выходов

33 -331,1 исходных наборов переменных выдаются все наборы переменных, представляющие в своей совокупности СДНФфункции, а на суммирующем счетчике 7 фиксируется значение "веса" булевой функции.

Принцип работы устройства для всех режимов поясняется табл.2.

В качестве примера рассматривается функция F(x хд хэ х4 х — х х5Чх ХЯ 4 1Х х х . Определяют булевый диффе38 — 38 g = 11011. з

Соответственно, для первых трех режимов на группу входов 1 -1 иско1ых переменных заносится код 10000, для четвертого режима — 00000.

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

1. Устройство для вычисления булевых диАференциалов, содержащее суммирующий счетчик, группу элементов И ,и элемент И, о т л и ч а ю щ е е с я тем, что, с целью расширения Аункциональных возможностей за счет вычисления булевой разности Аункции, определения "веса" булевой Аункции, "ве-, са" булевой разности и преобразования булевой функции из дизъюнктивной нор- мальной Аормы в совершенную дизъюнктивную нормальную Аорму, оно содерлжт группу I К-триггеров, дешиАратор, узел идентиАикации,вычитающий счетчик, IK-триггер, вторую, третью и четвер-. тую группы элементов И, второй— седьмой элементы И, шесть элементов

ИЛИ и пять элементов задержки, причем первый вход i-ro элемента И первой группы (i-1,И, где N — максимальное число переменных булевых функций) соединен с i-м входом искомых переменных групп, вход запуска устройства соединен с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом первого элемента И и счетным входом вычитающего счетчика, выход i-ro разряда которого соедин:.н с первым входом i-го элемента И второй группы, первым входом i-ro элемента И третьей группы и i-м входом второго элемента KIN прямой выход котоРого соединен с первым входом первого элемента И, второй вход которого соединен с выходом первого элемента задержки, вход которого соединен с выходом второго элемен12

11

16899 та задержки, первыми входами второго, третьего и четвертого элементов И, выход последнего из которых соединен с первым входом третьего элемента

И1И, второй вход которого соединен с выходом второго элемента И, второй вход которого соединен с выходом

I К-триггера и вторым входом третьего элемента И„ выход которого соединен с третьим входом третьего элемента

ИПИ, выход которого соединен с вых< цом признака определения очередного набора переменных, с вторыми входами элементов И третьей группы и счетным входои суммирующего счетчика, вход устачовки в "О" которого соединен с входом обнуления, выход х-го элемента И первой группы соединен с тактовым входом i-го I K-триггера группы, 2g вход установки в "О" которого соединен с выходом первого элемента ИЛИ, входом установки в "0" I К-триггера и входами третьего и четвертого элементов задержки, выход последнего из которых соединен с вторыми входами элементов И первой группы, входом второго элемента задержки и первым входом четвертого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента задержки и вторыми входами элементов И второй группы, выход i-го из которых соединен с входом установки в "1" i-ro IK-триггера группы, прямой выход которого соединен с первым входом -го злемен35 та И четвертой группы и i-м входом первой группы узла идентификации, i-й вход второй группы которого сое« динен с инверсным выходом i-ro IK, 1 триггера группы, первый вход i-. ãî элемента И первой группы соединен с вторым входом i-. го элемента И четВертой группы, выход которого соединен с i-м входом пятого элемента ИЛИ„ прямой выход которого соединен с первым входом пятого элемента И, второй вход которого соединен с первым выхо дом дешифратора, первый и второй входы которого соединены соответственно с первым и вторым настроечными входами устройства, выход пятого элемента И соединен с первым входом шестого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И, первый вход которого соединен с инверсным выходом четвертого элемента

ИПИ, второй вход дешифратора соединен с третьим входом второго ."«"..«.нта И, третий выход дешифрат;p" соединен с вторым входом шестогo элемента И, четвертый выход дешифратоp<. . соединен с вторым входои четвертого элемента И, третий вход которого сс:-:— динен с выходом узла иденФифик",èèè и первым входом седьмого элемента И, выход которого соединен с тактовыи входом 3К-триггера, выход четвертого элемента ИЗЦ1 соединен с входои пятого элемента задержки, выход которого соединен с вторым вхо -„см седьмого элемента Vi, i-й вход вь«читающего счетчика соединен с -и входом группы задания наборов. инверсный выход второго элемента ИЛИ соединен с выходом признака окончания вычисления, выход

1-. го элемента И третьей гр ппы соединен с i-и выходом группы искомых наборов переменных, выход суммирующего счетчика соединен с выходом

"веса" булевой разности, выход шестого элемента ИЛИ соединен с третьим входом третьего элемента И.

2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что узел идентификации содержит два блока элементов ИЛИ по 1 групп элементов ИЛИ в каждом, группу элементов ИЛИ, группу элементов И и элемент ИЛИ, причем -й вход )-й группы задания первого кода узла идентификации «,j=-1,N где

М вЂ” ма«"ииальное число конъюйкний булевой функции) соединен с первым вхо" дом х-rо элемента И j-и группы первого блока, i-й вход j-й группы задания второго кода узла идентификации соединен с первым входом i-го элемента И )-й группы второго блока и с х-м входом )-го элемента И31И группы, выхоц которого соединен с «,2N+1) м входом 1"го элемента И группы, х-й вход которого соеди".ен с выходом

i ro элемента И 1-Й группы первого блока„ i-и вход первой грут,:.пы узла идентификации соединен с вторьпл входаии:ь-х элементов И каждой группы первого блока, i-й вход второй группы узла идентификации соединен с вторыми входами -х элементов И каждой группы второго блока, выход i-го элемента И

j-й группы которого соединен с Y+

+i)-м входом j-ro элемента И группы, выход которого соединен с 1-м входом элемента ИЛИ, выход которого является .выходом узла идентификации, 1689942

Значение i-ro

Содержание режима работы

Ревходы разряда группы входов искомых переменных 1 -1, 39 4С

1 Вычисление неори- "1" (остальные ентированного бу- "О") левого дифференциала по i-й переменной

2 Вычисление булевого дифференциала по i-й переменной, ориентированного на увеличение То же

3 Вычисление булевого дифференциала

no i-й переменной, ориентированного на уменьшение

4 Преобразование

ДНФ в СДНФ

0 0

С 1

1 0

1 1

Все разряды равны "0"

Т а б л и ц а 2

11111

i 1110

11101

11011

11001

10111

10101

1 0011

10010 t 0001

01111

01101

01011

01001

1

1

1

1

1

1

О

О

1

1

1

0

0

О

0

0

С

0

С

0

С

1

1

1

1

1

1

О

1 ,1

1

1

О

0

0

0

С

1

1

1

0

1

1

1

0

0

0

О

1689942 а 3 (4

01000 о оа»1 1

00110 1

ОО1О1 1

00 f00 1

0ОО» 1

Оаа10 1

00001 о

00000 о

Итоговое значение содержимого в суммирующем счетчике 7 ("вес") 22

О

О

О

О

О

О

0 о о