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

W,

V

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

22

JJr

Л

35

(Л

С

с

00 Ю Ю 4 Ю

ройств. Целью изобретения является расширение функциональных возможностей устройства за счет вычисления булевой разности функции, заданной в дизъюнктивной нормальной форме (ДНФ), определения веса булевой функции и веса булевой разности, а также преобразования булевой функции из ДНФ в совершенную ДНФ (СДНФ). Устройство для вычисления булевых дифференциалов содержит группу входо искомых переменных, вход 2 запуска устройства, группу Зк-триг- геров, , дешифратор 4, узел 5 идентификации, вычитающий счетчик 6, суммирующий счетчик 7, ЭДс-триггер 8, четыре группы элементов И , 10,-10W, 11rf-1lN и , семь

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

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

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

Устройство (фиг.1) содержит труп-, пу входов (4 искомых переменных (N - максимальное число переменных булевых функций), вход 2 запуска устройства, группу IK-триггеров, 3 -3|у, дешифратор 4, узел 5 идентификации, вычитающий счетчик 6, суммирующий счетчик 7, 1К-триггер 8, четыре группы элементов И , , , 12t-12|4, семь элементов И 13-19, шесть элементов ИЛИ 20-25, пять элементов 26-30 задержки, выход 31 узла 5 идентификации, выход 32

элементов И 13-19, шесть элементов ИЛИ 20-25 и пять элементов задержки 26-30 Устройство в зависимости от кода настройки может работать в четырех режимах. На группу входов искомых переменных заносится код, определяющий, по какой переменной проводится вычисление булевого дифференциала,, В вычитающий счетчик 6 заносится код, соответствующий максимальному числу наборов искомой функции, в узел идентификации заносится код элементарных конъюнкций На выходе суммирующего счетчика 7 формируется значение веса искомой функции для заданного режима, 1 з„По ф-лы, 2 ил,, 2 табл.

5

о

Q

,-

0

5

признака окончания вычисления 32, группу выходов искомых наборов переменных 33,|-33 , выход 34 признака определения очередного набора переменных, вход 35 обнуления, выход 36 веса булевой разности, М групп входов задания первого кода 37J-37 узла идентификации (М - максимальное количество элементарных конъюнкций заданной функции), М групп входов второго кода , два настроечных входа 39 и 40 устройства, группу входов задания наборов 41/(-41щ, две группы входов и 43я-43 узла 5 идентификации

Узел 5 идентификации (фиг.2) содержит два блока групп элементов ИЛИ 44J-44JJ и 45/-45J, группу элементов ИЛИ , группу элементов И 47, -47м и элемент ИЛИ 48.

Элементарную конъюнкцию ранга можно кодировать двумя двоичными п-разрядными кодами А (а...а;..,ач) и В (Ь ... Ъ; ... bn), где af,bjЈ{o,1, причем для всех х j, содержащихся в элементарной конъюнкции, и только для них в 1-х разрядах первого кода записывается О, в остальных разрядах 1, а для всех го - в 1-х разрядах второго кода О, в остальных разрядах - 1. При этом, если , то в оставшиеся (N«-n)старших разрядов групп кодов записываются единицы Незадействованные входы кодов групп

(не содержащие элементарных конъюнкций) должны быть обнулены

При таком способе кодирования определение факта поглощения элсментар- ной конъюнкцией принятого набора пере менных х(хх. . оХ,-. оХ), где х.(0 или 1 (,N), осуществляется проверкой следующего условия: п

J jJ|a;Xi)-Ј4 1.

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

В исходном состоянии в узел 5 идентификации поступают коды элементарных конъюнкций. В п младших разрядов вычитающего счетчика 6 записываются 1, в остальные - О (исходя из количества п переменных заданной функции), суммирующий счетчик 7 обнуляется сигналом с входа 35 обнуления. Работа устройства начинается с приходом единичного сигнала на вход 2 запуска устройства. Устройство может работать в четырех режимах.

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

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

Булевым дифференциалом (разностью) логической функции F(x,...,хп) по переменной х j называется логическая функция R(X,J ,... ,xn)F(x/,..-. ,xj,..., х„)ф F(xt , .. .,х; , ...,х„.) .:

Определение наборов переменных, соответствующих функции R(x,,0..,х), осуществляется следующим образом. Сигнал с входа 2 запуска устройства через элемент ИЛИ 20 обнуляет IK- триггеры 3,1 -3 N группы и I К-триггер 8, задерживается на элементе 26 задержки (время задержки определяется временем переходных процессов в вычитающем счетчике 6), копирует через элементы И группы содержимое вычитающего счетчика 6 в К-триггеры группы и поступает через элемент ИЛИ 22 на элемент 29 задержки. Содержимое IK-триггеров представляет собой проверяемый набор переменных х(хд, а.. ,хр) , который в виде прямых и инверсных значений с выходов триггеров 3,|-3 ft подается на входы и узла 5 идентификации.

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

0

5

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

Кроме того, сигнал с выхода элемента ИЛИ 20, задержанный на элементе 27 задержки (задержка определяется сум марным временем переходных процессов в вычитающем счетчике 6, элементе И 10, IK-триггере 3j группы и узле 5 идентификации) после того, как осуществятся указанные действия, поступает на первые входы элементов И 9л-9N группы, элемент ИЛИ 22 и элемент 28 задержки. В зависимости от того, по какой переменной х ведется

0 вычисление булевого дифференциала (что определяется единичным состоянием 1-го разряда группы входов 1,|-1 ц искомых переменных), сигнал единичного уровня с выхода элемента

, И 9 группы поступает на счетный вход соответствующего IК-триггера ц группы и устанавливает его в состояние, противоположное исходному, чем обеспечивается преобразование преды0 дущего набора переменных в набор

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

5 в состояние, противоположное исходному.

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

1)и на первоначальном, и на преобразованном -

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

3)на первоначальном - 0 а на преобразованном - 1й;

4)на первоначальном - 1, а на преобразованном - О.

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

Пои ситуации 3 или 4 на тактовый вход IK-триггера 8 поступает только один сигнал, что обеспечивает его установку в единичное состояние. При этом элемент И 19 открыт как потенциалом с выхода I К-триггера 8, так и потенциалом с первого выхода дешифратора 4 (в соответствии с выбранным режимом)о Поэтому сигнал, задержанньй на элементе 289 кроме указанных действий проходит через элементы И 19 и ИЛИ 25, поступает на счетный вход суммирующего счетчика 7 и увеличивае его содержимое на единицу, поступает на входы элементов И 11.-11 группы0 На выходах искомых наборов переменны устройства фиксируется сформированный на вычитающем счетчике 6 набор переменных5 который принадлежи искомой булевой разности. На выходе 34 признака определения очередного набора переменных формируется сигнал единичного уровня

Процесс вычисления заканчивается после обнуления вычитающего счетчика 6, На выходе 32 признака окончания

0

5

0

5

0

5

0

5

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

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

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

После занесения исходных данных для этого режима и подачи единичного сигнала с входа 2 запуска устройства осуществляются действия,аналогичные для режима 1. Особенностью является то, что в данном случае элемент И 19 постоянно закрыт сигналом нулевого уровня (с первого выхода дешифратора 4)s а задержанный на элементе 28 задержки сигнал может пройти лишь через элементы И 17 и ИЛИ 25 и выполнить указанные (в режиме 1) действия. Это случается при наличии ситуации 3 или 4 а также, когда в преобразованном наборе переменных i-я переменная равна единице, т.е. когда соответствующий (1-й) tJK-триггер из группы I К триггеров находится в единичном состоянии. Тогда на соответствующем элементе И группы произойдет совпадение единичных сигналов Сформированный таким образом сигнал единичного уровня через элемент ИЛИ 23 поступает на первый вход элемента И 16. На втором входе элемента И 16 для данного режима также сигнал единичного уровня, который с выхода этого элемента через элемент ИЛИ 24 подан на вход элемента И 17. В противном случае на элементе И 17 формируется сигнал нулевого уровня.

Режим 3„ Вычисление булевого дифференциала (разности) по i-й переменной, ориентированного на уменьшение (К xs).

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

Работа устройства аналогична предыдущему случаю (режиму 2). Особенностью является то, что элемент И 17 открыт для прохождения сигнала, задержанного на элементе 28 задержки лишь в том случае, когда в преобразованном наборе переменных 1-я переменная равна нулю, т.е. когда соответствующий триггер из группы К-триггеров находится в нулевом состоянии. При этом ни на одном из элементов И 12(-12м не происходит совпадения потенциалов, чем обеспечивается наличие единичного сигнала на инверсном выхо- де элемента ШШ 23. На выходе элемента И 15 формируется сигнал единичного уровня (на третьем выходе дешифратора 4 также сигнал единичного уровня) и передается через элемент ИЛИ 24 на вход элемента И 17.

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

После начальных установок, задания режима работы и подачи единичного сигнала с входа 2 запуска устройства схема работает аналогично режиму 1. При этом преобразования первоначального набора переменных на UK-триггерах группы не происходит, так как все разряды на группе входов искомых переменных в этом режиме равны нулю. Элементы И 17 и. 19 постоянно закрыты сигналами нулевого уровня (с соответствующих выходов дешифратора 4), а элемент И 18 постоянно открыт по входу, связанному с четвертым выходом дешифратора 4 Поэтому задержанный на элементе 28 задержки сигнал проходит через элементы И 18, ИЛИ 25 и далее по известным цепям лишь тогда, когда заданная функция на сформированном наборе переменных равна единице, что фиксируется наличием единичного потенциала на выходе узла 5 идентификации. Состояние t/K-тригге- ра 8 в данном случае значения не имеет.

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

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

В качестве примера рассматривается функция F(x, ,xe,xs,xx,x x4x5Vxc xsV .. Определяют булевый диффе

Ы

10

. -

ренциал по переменной х. К исхочнг состоянии на М () групп иходоп задания первого кода узла идентификации заносятся следующие данные:

- 37 01101;

37f 37| 010011;

37 37| Ю110.

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

38J - 38 11111;

я«2 3

- 38 11111;

D

38 - 38g 11011.

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

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

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

111

та задержки, первыми входами второго третьего и четвертого элементов И, выход последнего из которых соединен с первым входом третьего элемента ИЛИ, второй вход которого соединен с выходом второго элемента И„ второй вкод которого соединен с выходом I ЕС-триггера и вторым входом третьего элемента И, выход которого соединен с третьим входом третьего элемента ИЛИ, выход которого соединен с выхо дом признака определения очередного набора переменных, с вторыми входами элементов И третьей группы и счетным входом суммирующего счетчика, вход установки в О которого соединен с входом обнуления, выход 1-го элемента И первой группы соединен с такто вым входом 1-го IK-триггера группы, вход установки в О которого соединен с выходом первого элемента ИЛИ, входом установки в О I К-триггера и входами третьего и четвертого элементов задержки, выход последнего из которых соединен с вторыми входам элементов И первой группы, входом второго элемента задержки и первым входом четвертого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента задержки и вторыми входами элементов И второй группы, выход 1-го из которых соединен с входом установки в 1 1-го IK-триггера группы, прямой выход которого соединен с первым входом 1-го элемента И четвертой группы и i-м входом первой группы узла идентификации, i-й вход второй группы которого соединен с инверсным выходом i-го IK- 1 риггера группы, первый вход i-ro элемента И первой группы соединен и вторым входом ITQ элемента И четвертой группы, выход которого соединен с i-м входом пятого элемента ИЛИ Прямой выход которого соединен с первым входом пятого элемента И, второй вход которого соединен с первым выходом дешифратора, первый и второй входы которого соединены соответственно с первым и вторым настроечными входа устройства, выход пятого элемента И соединен с первым входом шестого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И, первый вход которого соединен с инверсным выходом четвертого элемента ИЛИ, второй вход дешифратора соеци

0

5

0

5

942

12

нен с третьим входом второго та И, третий выход дешифратора сие- динен с вторым входом шестогп элемента И, четвертый выход дешифратора соединен с вторым входом четвертого элемента И, третий вход которого соединен с выходом узла идентификации и первым входом седьмого элемента И, выход которого соединен с тактовым входом ЗК-триггера, выход четвертого элемента ИЛИ соединен с входом пятого элемента задержки, выход которого соединен с вторым входом седьмого элемента И, i-й вход вычитающего счетчика соединен с i-м входом группы задания наборов, инверсный выхоп второго элемента ИЛИ соединен с выходом признака окончания вычисления, выход i-ro элемента И третьей гр тиш соединен с i-м выходом группы искомых наборов переменных, выход суммирующего счетчика соединен с выходом веса булевой разности, выход шестого элемента ИЛИ соединен с. третьим входом третьего элемента И.

левой функции) соединен с первым входом i-ro элемента И j-и группы первого блока, i-й вход j-й группы задания второго кода узла идентификации соединен с первым входом i-го элемента И j-й группы второго блока и с i-м входом j-го элемента ИЛИ группы, выход которого соединен с (2N+1)M входом j го элемента И группы, i-й вход которого соединен с выходе 1-го элемента И группы первого блока, i-й вход первой грутпы узла идентификации соединен с вторыми входами i-x элементов И каждой группы первого блока, i-к вход второй группы узла идентификации соединен с вторыми входами i-x элементов И каждой группы второго блока, выход i-ro элемента И j-й группы которого соединен с (N4 «1)-м входом j-то элемента И группы, выход которого соединен с j-м входом .элемента ИЛИ, выход которого является выходом узла идентификации.

0

5

0

5

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

Вычисление булево- го дифференциала по i-й переменной, ориентированного на увеличение Вычисление буле- вого дифференциала по i-й переменной, ориентированного на уменьшение Преобразование ДНФ в СДНФ

11111 11110 11101 11100 11011 11010 11001 11000 10111 10110 10101 10100 10011 10010 10001 10000 01111

ото

01101 01100 01011 01010 01001

Таблица 1

О О

То же

О 1

Все разряды равны л

О1

Таблица2

о о о о о о о о о о о о о о о о 1 1 1 1 о 1 о

1 1 1 1 о 1 о о 1 1 1 1 1 1 о о о о о о о о о

1

1 1

1 1 1 1 о 1 1 1 1 1 1 о о о о о о 1 о 1