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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИКЫ 1)50 обг 7 ПИСАНИЕ ИЗОБРЕТЕНИЯ СВИДЕТЕЛЬСТВ Н АВТОРСНО Р987Ь ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(54) УстРойст ВЫХ ДИффЕРЕН 1 (57) Изобрете тике и вычисл назначено для вычислений пр тестового и а бинационных с турной надежи 0 ЛЛЯ ВЫЧИСЛЕНИЯ ВУЛЕ 1 ИАЛОВие относится к автомательной технике и пред- автоматизации процессапроектировании средствпаратного контроля комем и для анализа струк- ости дискретных уст1689942 10 ройств. Целью изобретения являетсярасширение Аункциональных возможностей устройства за счет вычислениябулевой разности Аункции, заданнойв дизъюнктивной нормальной Аорме(ДНФ), определения "веса" булевойфункции и "веса" булевой разности,а также преобразования булевой функции из ДНФ в совершенную ДНФ (СДНФ)Устройство для вычисления булевыхдифференциалов содержит группу входов1)-11 л искомых переменных, вход 2запуска устройства, группу 7 К-триггеров, 3-ЗИ, дешиАратор 4, узел 5идентификации, вычитающий счетчик 6,суммирующий счетчик 7, 7 К-триггер 8четыре группы элементов И 9 -91)1,101-101, 111-1114 и 121-121, семь Изобретение относится к автоматикеи вычислительной технике и предназначено для автоматизации процесса вычислений при проектировании средствтестового и аппаратного контроля ком" 30бинационнь 1 х схем и для анализа структур-,ной надежности дискретных устройств.Цель изобретения - расширениефункциональных возможностей устройства за счет вычисления булевой разности функции, заданной в дизъюнктивной35нормальной форме (ДНФ), определение"веса" булевой Аункции и "веса" булевой разности, а также преобразованиябулевой функции из ДНФ в совершеннуюДНФ (СДНФ),На фиг.1 представлена структурнаясхема устройства для вычисления булевых дифференциалов; на фиг.2 функциональная схема узла идентиАикацииеУстройство (фиг,1) содержит груп-,пу входов 11-1 ц искомых переменных1 - максимальное число переменныхбулевых Функций) вход 2 запуска50устройства, группу .1 К-триггеров,3 -Зщ, дешифратор 4, узел 5 идентификации, вычитающий счетчик 6, сумми"рующий счетчик 7, ХК-триггер 8, четы"ре группы элементов И 9 -911 10 -10 цФ5511 -111)1, 121-121, семь элементов И13-19, шесть элементов ИЛИ 20"25,. пять элементов 26-30 задержки, выход31 узла 5 идентификации, выход 32 элементов И 13-19, шесть элементовИЛИ 20-25 и пять элементов задержки26-30. Устройство в зависимости откода настройки может работать в четырех режимах. На группу входов искомых переменных заносится код, определяющий, по какой переменной проводится вычисление булевого диААеренциала. В вычитающий счетчик 6 заносится код, соответствующий максимальному числу наборов искомой Аункции,в узел идентиАикации заносится кодэлементарных конъюнкций. На выходесуммирующего счетчика 7 Аормируетсязначение "веса" искомой Аункции длязаданного режима. 1 з.п. А-лы, 2 ил.,2 табл. признака окончания вычисления 32,группу выходов искомых наборов переменных 331 -331)1, выход 34 признакаопределения очередного набора переменных, вход 35 обнуления, выход 36Н Ивеса булевой .разности, М групп входов задания первого кода 37 -37Нузла идентификации (М - максимальноеколичество элементарных конъюнкцийзаданной Аункции), М групп входоввторого кода 38-381, два настроечныхЯвхода 39 и 40 устройства, группу входов задания наборов 41-41, двегруппы входов 42-42 ц и 43 -43 узла5 идентиАикации.Узел 5 идентиАикации (Аиг.2) содержит два блока групп элементовИПИ 44-44 Н и 45, -45, группу злеменИтов ИЛИ 46-46, груйпу элементов И47 -47 м и элемент ИЛИ 48,Элементарную конъюнкцию ранга6 п можно кодировать двумя двоичнымии-разрядными кодами А (аа;а)н В ГЬЬ;Ьд), где е,Ье)0,1),причем для всех х;, содержащихся вэлементарной конъюнкции, и толькодля них в -х разрядах первого кодазаписьвается "0", в остальных разря 11е.ьдах 1, а для всех х - в -х разрядах второго кода 0 , в остальныхразр.дах - "1". При этом, если и (М,то в оставшиеся (Ж- п)старших разрядов групп кодов записьваются единицы.Незадействованные входы кодов групп(не содержащие элементарных конъюнкций) должны быть обнуленыПри таком способе кодирования определение факта поглощения элементарной конъюнкцией принятого набора переменньк х(хх,х ), где х,=О или1 (=1,И), осуществляется проверкойследующего условия;и" а 1 ОДМа,х;)=/ (Я Ь 1 х; = 1.:4 .-4 : 4Устройство работает следующим образом,В исходном состоянии в узел 5 15идентификации поступают коды элементарных конъюнкций, В и младших разрядов вычитающего счетчика 6 записываются "1", в остальные - "0" (исходяиз количества и переменных заданной 20Функции), суммирующий счетчик 7 обнуляется сигналом с входа 35 обнуления.Работа устройства начинается с приходом единичного сигнала на вход 2запуска устройства. Устройство может 25работать в четырех режимах.Коды настроек для каждого из четырех режимов приведены в табл.1.Режим 1, Вычисление неориентированных булевых дифференциалов (К,). 30Булевым дифференциалом (разностью)логической функции Е(хх 1) попеременной х; называется логическаяфункция К(х,уухд)=Р(хеух).рх) Е(х ,х;, ,х) .Определение наборов переменных,соответствующих Функции К(хх 11),осуществляется следующим образом.Сигнал с входа 2 запуска устройствачерез элемент ИЛИ 20 обнуляет 1 Ктриггеры З -Зц группы и 1 К-триггер8, задерживается на элементе 26 задержки (время задержки определяется временем переходных процессов в вычитающем счетчике 6), копирует через элементы И 10-10 м группы содержимоевычитающего счетчика 6 в 1 К-триггеры3 -Зд группы и поступает через элемент ИЛИ 22 на элемент 29 задержки.Содержимое 1 К-триггеров З -3представляет собой проверяемый набор переменных х(х 4хд), который в видепрямых и инверсных значений с выходовтриггеров Зподается на входы42-421 и 43-43 узла 5 идентификации.На вьмоде 31 узла 5 идентификацииФормируется сигнал единичного уровнялишь в том случае, если проверяемый набор поглощается хотя бы однойэлементарных конъюнкций заданной Функции, В противном случае на выходе 31 узла 5 идентификации формируется сигнал нулевого уровня. Если на выходе узла 5 идентификации сформирован сигнал единичного уровня, то задержанный на элементе 29 задержки сигнал (величина задержки определяется суммарным временем переходньк процессов в элементе И 10, 1 К-триггере 3; группы и узел 5 идентиФикации) пройдет через элемент И 14 и установит 1 К-триггер 8 в единичное состояниеВ противном случае в 1 К-триггере 8 записывается сигнал логического "0".Кроме того, сигнал с выхода элемен" та ИЛИ 20, задержанный на элементе 27 задержки (задержка определяется сум марным временем переходных процессов в вычитающем счетчике 6, элементе И 10, 1 К-триггере 31 группы и узле 5 идентификации) после того, как осуществятся указанные действия, поступает на первые входы элементов И 9 Агруппы, элемент ИЛИ 22 и эле" мент 28 задержки. В зависимости от того, по какой переменной х ведется вычисление булевого дифференциала (что определяется единичным состоянием з.-го разряда группы входов 11 -11 искомьк переменных), сигнал единичного уровня с выхода элемента И 9 группы поступает на счетный вход соответствующего 1 К-триггера 3 -3группы и устанавливает его в состояние, противоположное исходному, чем обеспечивается преобразование предыдущего набора переменных в набор переменных, у которого значение переменной х; изменилось на противоположное. С этого момента снова повторяется процесс идентификации, т.е. проверка в узле 5 идентификации Факта равенства или неравенства заданной функции единице на преобразованном наборе переменньк. К этому моменту сигнал с выхода элемента ИЛИ 22, зад .ржанный на элементе 29 задержки, поступает на элемент И 14 и в случае единичного сигнала на выходе узла 5 идентификации проходит через этотэлемент и устанавливает 1 К-триггер 8 в состояние, противоположное исходному. Таким образом, возможны четыре различные ситуации, которые характеризуются тем, что заданная Аункцияможет принимать значения:1) и на первоначальном, и на преобразованном - "0";2) и на первоначальном, и на преобразованном - "1";3) на первоначальном - "0", а напреобразованном - "1";4) на первоначальном - "1", а напреобразованном - "О",При ситуации 1 или 2 1 К-триггер 8в итоге находится в начальном нулевом состоянии. При этом на элементе И,19 Формируется сигнал нулевого уровня, Закрыты также элементы И 17 и 18(последний сигналом нулевого уровняс выхода дешиАратора 4). Поэтому сигнал, задержанный на элементе 28 задержки (задержка определяется суммари,ж временем переходных процессов вэлементах ИЛИ 22, И 14, 1 К-триггере 8и временем задержки на элементе 29)и элементе 30 задержки (задержка определяется суммарным временем перехоцных процессов в элементах И 17,И 18 или И 19, элементах ИЛИ 25 иИ 11), проходит через открытый элемент И 13 и поступает на вход элемента ИЛИ 20 и счетный вход вычитающего 30счетчика 6, чем обеспечивается Аорми-.рование очередного набора переменныхи повторение указанного процесса.При ситуации 3 или 4 на тактовыйвход 1 К-триггера 8 поступает только3 эодин сигнал, что обеспечивает егоустановку в единичное состояние. Приэтом элемент И 19 открыт как потенциалом с выхода 1 К-триггера 8, так ипотенциалом с первого выхода дешиАратора 4 (в соответствии с выбраннымрежимом). Поэтому сигнал, задержанныйна элементе 28, кроме указанных действий проходит через элементы И 19и ИЛИ 25, поступает на счетный вход 45суммирующего счетчика 7 и увеличиваетего содержимое на единицу, поступает.на входы элементов И 111-111 группы.На выходах искожх наборов переменных33 -33 устройства Аиксируется сАормированный на вычитающем счетчике бнабор переменных, который принадлежитискомой булевой разности, На выходе34 признака определения очередногонабора переменных Аормируется сигнал55единичного уровня,Процесс вычисления заканчиваетсяпосле обнуления вычитающего счетчика6,. На выходе 32 признака окончания вычисления Аормируется сигнал диничного уровня, при этом в суммирующемсчетчика 7 подсчитывается "вес" булевой разности,Режим 2, Вычисление булевого диАференциала (разности) по -й переменной, ориентированного на увеличение(К 1 х;).Булевым дифАеренциалом ориентированным на увеличение, называется .булева Аункция, равная единице толькона тех наборах переменных, на которых,заданная булева Аункция изменяетсяпри изменении -й переменной в этихнаборах из нуля в единицу.После занесения исходных данныхдля этого режима и подачи единичногосигнала с входа 2 запуска устройстваосуществляются действия, аналогичныедля режима 1. Особенностью являетсято, что в данном случае элемент И 19постоянно закрыт сигналом нулевогоуровня (с первого выхода дешиАратора4), а задержанный на элементе 28 задержки сигнал может пройти лишь через.элементы И 17 и ИЛИ 25 и выполнитьуказанные (в режиме 1) действия. Этослучается при наличии .ситуации 3 или4, а также, когда в преобразованномнаборе переменных -я переменная равна единице, т,е. когда соответствующий (-й) 3 К-триггер из группы 1 Ктриггеров 31-3находится в единичном состоянии. Тогда на соответствующем элементе И 12,1-12 группы произойдет совпадение единичных сигналов.Сформированный таким образом сигналединичного уровня через элемент ИЛИ23 поступает на первый вход элементаИ 16, На втором входе элемента И 16для данного режима также сигнал еди-"ничного уровня, который с выхода этого элемента через элемент ИЛИ 24 подан на вход элемента И 17. В против.ном случае на элементе И 17 формируется сигнал нулевого уровня.Режим 3. Вычисление булевого диАференциала (разности) по -й переменной, ориентированного на уменьшение(Н х;),Булевым дифференциалом, ориентированным на уменьшение, называется булева Аункция, равная единице только на тх наборах переменных, на которых заданная булеза Аункция изменяется при изменении х-й переменной в этих наборах из единицы в нуль.О89942ренцпал по переменной х, В псхоппог:состоянии на М (11=3) групп входовзадания первого кода узла идентификации заносятся следующие данные: 537- 37 = 01101;37 - 3 ф= 010011;3 Я - 3 Д = 10110.На М груйп входов задания второгокода узла идентиАикации заносятсяследующие данные:38 38- = 11111338( - 38 = 11111;Я 15 20 25 30 35 40 45 50 9 бРабота устройства аналогк.па предыдущему случаю (режиму 2), Особенностью является то, что элемент И 17открыт для прохождения сигнала, задержанного на элементе 28 задержки лишьв том случае, когда в преобразованномнаборе переменных -я переменная равна нулю, т,е. когда соответствующийтриггер из группы 1 К-триггеров 3-3,1находится в нулевом состоянии. Приэтом ни на одном из элементов И12-12 И не п,оисходит совпадения потенциалов, чем обеспечивается наличиеединичного сигнала на инверсном выходе элемента ИЗЫДИ 23. На выходе элемента И 15 Аормируется сигнал единичного уровня (на третьем выходе дешиАратора 4 также сигнал единичного уровня) и передается через элемент ИПИ 24на вход элемента И 17.Режим 4, Преобразование ДНФ в СДНФПосле начальных установок, заданиярежима работы и подачи единичногосигнала с входа 2 запуска устройствасхема работает аналогично режиму 1.При этом преобразования первоначального набора переменных на 1 К-триггерах 3 -31 группы непроисходит, таккак все разряды на группе входов искомых переменных в этом режиме равнынулю. Элементы И 17 и, 19 постояннозакрыты сигналами нулевого уровня(с соответствующих выходов дешиАратора 4), а элемент И 18 постояннооткрыт по входу, связанному с четвертым выходом дешиАратора 4. Поэтомузадержанный на элементе 28 задержкисигнал проходит через элементы И 18,ИЛИ 25 и далее по известным цепямлишь тогда, когдазаданная Аункция насформированном наборе переменных равна единице, что Аиксируется наличиемединичного потенциала на выходе узла5 идентификации. Состояние УК-триггера 8 в данном случае значения неимеет,В результате на группу выходов33 -331,1 исходных наборов переменныхвыдаются все наборы переменных, представляющие в своей совокупности СДНФфункции, а на суммирующем счетчике 7фиксируется значение "веса" булевойфункции.Принцип работы устройства для всехрежимов поясняется табл,2,В качестве примера рассматриваетсяфункция Р(х хдхэх 4 ххдхЬЧх хьЯ1 ххьх. Определяют булевый диффе 38 - 38= 11011.зСоответственно, для первых трех режимов на группу входов 1 -1 искоьых переменных заносится код 10000, для четвертого режима - 00000. Формула из обре те ния1. Устройство для вычисления булевых диАФеренциалов, содержащее суммирующий счетчик, группу элементов И ,и элемент И, о т л и ч а ю щ е е с я тем, что, с целью расширения Аункциональных возможностей за счет вычисления булевой разности Аункции, определения "веса" булевой Аункции, "ве-, са" булевой разности и преобразования булевой Функции из дизъюнктивной нор- мальной Аормы в совершенную дизъюнктивную нормальную Аорму, оно содерлжт группу 1 К-триггеров, дешиАратор, узел идентиАикации,вычитающий счетчик, 1 К-триггер, вторую, третью и четвер-. тую группы элементов И, второй -седьмой элементы И, шесть элементовИЛИ и пять элементов задержки, причемпервый вход х-го элемента И первойгруппы (=1,3, где М - максимальноечисло переменных булевых Функций)соединен с 1-м входом искомых переменных групп, вход запуска устройствасоединен с первым входом первого элемента ИЛИ, второй вход которого соединен с выходом первого элемента Ии счетным входом вычитающего счетчика, выход -го разряда которого соедин:.н с первым входом -го элемента Ивторой группы, первым входом -гоэлемента И третьей группы и -м входом второго элемента И 31 И, прямой выход которого соединен с первымвходом первого элемента И, второй вход которого соединен с выходом первого элемента задержки, вход которого соединен с выходом второго элемен12 42 1116899 та задержки, первыми входами второго, третьего и четвертого элементов И, выход последнего из которых соединен с первым входом третьего элемента И 1 И, второй вход которого соединен с выходом второго элемента И, второй вход которого соединен с выходом 1 К-триггера и вторым входом третьего элемента И выход которого соединен с третьим входом третьего элемента ИПИ, выход которого соединен с выходом признака определения очередного набора переменных, с вторыми входами элементов И третьей группы и счетным вхсдои суммирующего счетчика, вход устачовки в "О" которого соединен с входом обнуления, выход х-го элемента И первой группы соединен с тактовым входом 1-го 1 К-триггера группы, 20 вход установки в "О" которого соединен с выходом первого элемента ИЛИ, входом установки в "О" 1 К-триггера и входами третьего и четвертого элементов задержки, выход последнего 25 из которых соединен с вторыми входами элементов И первой группы, входом второго элемента задержки и первым входом четвертого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента задержки и вторыми входами элементов И второй группы, выход .-гс из которых соединен с входом установки в "1" х-го 1 К-триггера груплл, прямой выход которого соединен с первым входом -гс злемен 35 та И четвертой группы и х-и входом первой группы узла идентификации, х-й вход второй группы которого соеахинеи с инверсным выходом -го 1 Ктриггера группы, первый вход з.-го элемента И первой группы соединен с вторым входом -. го элемента И четВертой группы, выход которого соединен с х-м входом пятого элемента ИЛИ прямой выход которого соединен с первым входом пятого элемента И, второй вход которого соединен с первым выхо- дом дешиФратора, первый и второй входы которого соединены соответственно с первым и вторым настроечными входами устройства, выход пятого элемента И соединен с первым входом шестого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И, первый вход которого соединен с инверсным выходом четвертого элемента ИПИ, второй вход дешийратсра соединен с третьим входом второго ." т"и нта И, третий выход ДешиАратора соединен с вторым входом шестогс элемента И, четвертый выход дешиюратсрсоединен с вторым входои четвертсгс элемента И, третий вход которого сое - динен с выходом узла иденФидикапии и первым входом седьмого элемента И, выход которого соединен с тактовыи входом 3 К-триггера, выход четвертого элемента ИЗБ соединен с входои пятого элемента задержки ВыхОд которого соединен с вторым входом седьмого элемента И, -й вход Вычитающегс счетчика соединен с . -и входом группы задания наборов. инверсный выход второго элемента ИЛИ соединен с вьгхсдои признака окончания вычисления, выход . го элемента И третьей грппы соединен с -и выходом группы искомых наборов переменных, выход суммирующего счетчика соединен с Выходом "веса" булевой разности, выход шестого элемента ИЛИ соединен с третьим входом третьего элемента И.2, Устройство по п.1, о т л и ч а ю щ е е с я тем, что узел идентиФикации содержит два блока элементов ИЛИ по 1 групп элементов ИЛИ в каждом, группу элементов ИЛИ, группу элементов И и элемент ИЛИ, причем х-й вход 1-й группы задания первого кода узла идентификации (,3=.1,Г 1, где М - ма ."ииальное число кснъюйкций булевой функции) соединен с первым вхо" дом х.-го элемента И 1-и группы первого блока, 1-й вход 1-й группы задания второго кода узла идентиАикации соединен с первым входом -Го элемента И 1-й группы второго блока и с х-м входом 1-го элемента ИЗБ группы, выхоц которого соединен с 2 М+1)-и входом 1"гс элемента И Группы, х-й вход которого соединен с выходом х-го элемента И 1-й группы первого блока х-и вход первой группы узла идентификации соединен с вторыми вхсдаии .ь-х элементов И каждой группы первого блока, -й вход второй группы узла идентификации соединен с вторымивходами -х элементов И каждой группывторого блока, выход х-ГО элемента И.1-й группы которогс соединен с (Х++1)-м входом 1-го элемента И группы,выход которого соединен с 1-м входомэлемента ИЛИ, выход которогс являетсявыходом узла идентификации,1689942 Значение ь.-го Содержание режима работы Ревходы разряда группывходов искомыхпеременных 1 -1,39 40 О 0 0 1 1 О 1 1 Все разрядыравны "0" Т а б л и ц а 2 1 1 1 11111 11110 11101 11100 11011 11010 11001 11000 10111 10110 10101 10100 10011 10010 10001 10000 01111 01110 01101 01100 01011 01010 01001 0 1 0 0 1 0 0 1 0 1 1 Вычисление неори- "1" (остальныеентированного бу- "0")левого ди 4 хЪеренциала по х-й переменной2 Вычисление булевого диФференциалапо ь.-й переменной,ориентированногона увеличение То же3 Вычисление булевого дифференциалапо -й переменной,ориентированногона уменьшение4 ПреобразованиеДНФ в СДНФ01000 о ОО 777 1 001 70 1 ОО 1 О 7 1 00700 1 ООО 17 1 ООО 1 О00001 о 00000 о Итоговое значение содержимого в суммирующем счетчике 7 ("вес") 22 0 0 0 0 0 0 0 О О