Устройство для вычисления булевых производных

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 3(51) 6 06 Р 1 ОПИСАНИЕ ИЗОБРЕТН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ. КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(72) Н.Т.Березюк, И.Ф.Холодный, В.Ю.Ларченко и Н.Г.Коробков (71) Харьковский ордена Ленина авиационный институт им.Н.Е.Жуковского (53) 681.3(088.8)(56) 1.Авторское. свидетельство СССР Р 940166, кл. 6.06 Р 15/31, 1982.2. Авторское свидетельство СССР Р 1016778, кл. С 06 Е 7/04, 1982. (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ .БУЛЕВЫХ ПРОИЗВОДНЫХ, содержащее коммутаторы, группу элементов НЕРАВНОЗНАЧНОСТЬ, сдвиговые регистры,причем первая группа входов устройства нодключена к информационным входам коммутаторов соответственно, управляющие входы первого коммутатора подключены к выходам первого сдвигового регистра соответственно, управляющие входы второго коммутатора подключены к соответствующим выходам элементов НЕРАВНОЗНАЧНОСТЬ группы, первая группа входов которой подключена к выходам первого сдвигового регистра соответственно, а вторая группа входов подключена к второй группе входов, устройства соответственно, тактовый вход устройства подключен к управляющим входам сдвиговых регистров, о т л и ч а ю щ е е с я тем, что, с целью расширения областиприменения путем обеспечения возможности вычисления неориентированных и ориентированных булевых производных и функций чувствительности, в него введены блок вычислений и анализатор разрядов, при этом выходы первого и второго коммутаторон соединены соответственно с первым и вторым входами блока вычислений, выход которого соединен с информационным входом нторого сдвигового регистра, первая группа входон анализатора разрядов соединена801128263 А с выходами первого сдвигового регистра соответственно, вторая группа входов анализатора разрядов соединена с второй группой входов устройства соответственно, а выход анализатора разрядов подключен к третьему входу блока вычислений, группа входов блока вычислений и третья группа входов анализатора разрядов соединены с третьей группой входов устройства соответственно, блок вычислений состоит из элемента 4 И-ИЛИ, причем первый вход блока вычислений соединен с инверсным входом первого элемента И, первым инверсным входом второго элемента И, первыми .прямыми( с входами третьего и четвертого эле- Я ментов И, второй вход блока вычислений соединен с первыми прямымивходами первого и второго элементов.И, инверсным входом третьего элемен- С та И, третий вход блока вычислении соединен с вторыми прямыми входами первого и третьего элементов И и с вторыми инверсными входами второго фие и четвертого элементов И, первый вход группы входов блока вычислений .соединен с вторым и третьим прямыми вхо- Ю дами соответственно второго и третье. ф го элементов И,второй вход группы .- входов блока вйчислений соединен с Ятретьим и вторым прямыми входамисоответственно первого и четвертогоэлементов И, выход блока вычисленийСй соединен с выходом элемента ИЛИ, анализатор разрядов содержит элементы И и элемент ИЛИ, причем входы первойи второй групй входов анализатора соединены соответственно с первыми ,фЬи вторыми входами элементов И, пер"вый и второй входы третьей группы входов соединены с первым и вторым входами следующего элемента И, третий вход третьей группы входов соединен с входами .последнего элемента И, выходы элементов И соединены с входами элемента ИЛИ, выход которого соединен с выходом анализатора разрядов.Изобретение относится к области автоматики и вычислительной техники и может быть использовано при построении устройств тестового и аппаратурного контроля цифровых устройств.Известны устройства для вычисления неориентированных булевых производных, содержащие счетчик,. коммутаторы, группу элементов НЕРАВНОЗНАЧНОСТЬ), регистр).13.Наиболее близкой к изобретению по технической сущности является схема сравнения кодов, позволяющая вычислять неориентированные булевые производные и функции чувствительнос" ти и содержащая счетчик, коммутаторы,15 группу элементов НЕРАВНОЗНАЧНОСТЬ, элемент НЕРАВНОЗНАЧНОСТЬ, сдвиговый регистр, при этом входы первой группы схемы подключены к информационным входам коммутаторов соответственно, 20 управ.ляющие входы второго коммутатора подключены к Выходам счетчика соответственно,управляющие ьходы второго коммутатора подключены к выходам элеНЕРАВНОЗНАЧНОСТЬ группы пер 75 вые входы которых подключены к выходам счетчика соответственно, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ подключены к входам второй группы схемы, выходы кдммутаторов подключены к входам30 элемента НЕРАВНОЗНАЧНОСТЬ соответственно, выход элемента НЕРАВНОЗНАЧНОСТЬ подключен к информационному входу сдвигового регистра, управляющий вход которого подключен к входу подачи счетных импульсов схемы и к счетному входу счетчика Г 23Недостатком известного устройства является невозможность вычисления ориентированных булевых производных и функций чувствительности. 40 Целью изобретения является расширение области применения путем обеспечения возможности вычисления неориентированных и ориентированных 5булевых производных и функций чувст- .вительности.Поставленная цель достигается тем,что в устройство для вычисления булевых производных, содержащее коммутаторы, группу элементов НЕРАВНОЗНАЧНОСТЬ, сдвиговые регистры, причем первая группа входов устройстваподключена к информационным входамкоммутаторов соответственно, управляющие входы первого коммутатораподключены к выходам первого сдвигового регистра соответственно,управляющие входы второго коммутатора подключены к соответствующимвыходам элементов НЕРАВНОЗНАЧНОСТЬ 60группы, первая группа входов которой подключена к выходам первогосдвигового регистра соответственно,а вторая группа входов подключенак второй группе входов устройства 65 соответственно, тактовый вход устройства подключен к управляющим входам сдвиговых.,регистров, введены блок вычислений и анализатор разрядов, при этом выходы первого и второго коммутаторов соединены соответственно с первым и вторым входами блока вычислений, выход которого соединен с информационным входом второго сдвигового регистра, первая группа входов анализатора разрядов соединена с выходами первого сдвигового регистра соответственно, вторая .группа входов анализатора разрядов соединена с входами второй группы устройства соответственно, а выход анализатора разрядов подключен к. третьему входу блока вычисления, группа входов блока вычислений и третья группа входов анализатора разрядов соединены с третьей группой входов устройства соатве 1:твенно, блок вычислений состоит из элемента 4 И-ИЛИ, причем первый вход блока вычислений соединен с инверсным входом первого элемента И, пер- вым инверсным входом второго элемента И, первыми прямыми входами третьего и четвертого элементов И, второй вход блока вычислений соединен с первыми прямыми входами первого и второго элементов И, инверсным входом третьего элемента И, третий вход блока вычислений соединен с вторыми прямыми входами первого и третьего элементов И и с вторыми инверсными входами второго и четвертого элементов И, первый вход группы входов блока вычислений соединен с вторым и третьим прямыми входами соответственно второго и третьего элементов И, второй вход группы входов блока вычислений соединен с третьим и вторым прямыми входами соответственно первого и четвертого элементов. И, выход блока. вычислений соединен с выходом элемента ИЛИ, анализатор разрядов содержит элементы И и элемент ИЛИ, причем входы первой и второй групп входов анализатора соединены соответственно с первыми и вторыми входами элементов И, первый и второй входы третьей группы входов соединены с первым и вторым входами следующего элемента И, третий вход третьей группы соединен с входами последнего эле- мента И, выходы элементов И соединены с входами элемента ИЛИ, выход которого соединен с выходом анализатора разряцов. Д(хПроизводной булевой функцией от функции 1 х) р хХ 1х 2 ррх по переменной х. называется функция, определяемая по формулеаех)Производная функция - Е(-",-характеризует изменение функции й(х) при изменении одной иэ ее переменных х и равна единице на тех входных наборах, на которых изменение переменной х; приводит к изменению Функции. Если рассмотреть булев куб функции й(х), то производная функаах)ция 1 -- характеризует изменениедх,функции Й(х) вдоль ребер куба. Функцией чувствительности 5(хэхот функции Г(х) по подмножествух: х хр)Й х называется Функция,определяемая по формулеЛ(х,х ) ЮЕ(х,х ),1Хх ху Х ХХФункция чувствительности 5 х ха 1рактеризует изменение функций приодновременном изменении несколькихее переменных ххр в х и равнаединице на тех входных наборах, накоторых одновременное изменение нескольких ее переменных приводит .к изменению функции. При рассмотрениибулевого куба функции Й(х) функциячувствительности характеризует изменение функциипо диагоналям куба.Ориентированные булевые производные .ао х (х) а 1 (х) характеризуютдх; ах. не только изменение, но и направление изменения функции Й(х) при изменении одной из ее переменных ха е(х)Возрастающая производная Ооххарактеризует направленное изменениефункции Й(х) при изменении одной из- ее переменных х,. и равна единице натех входных ребрах, на которых функция Г(х) возрастает (убывает) с воз; растанием (убыванием) переменной хПри рассмотрении булевого кубаФункции Й(х) возрастающая производная характеризует направленное (синфазное) изменение функции Х(х) вдольребер куба.1а 1 Е(х)Убывающая производнаяопределяется по формулеайх)- Е (Х 11УХ 1 1 01 Х 11 ф"ах д)( 1"в 111 Фх1д)1характеризует направленное изменениефункции Й(х) при изменении одной иэее переменных х и равна единицена тех входных йаборах, на которыхфункция Й(х) возрастает (убывает)с убыванием (возрастанием) переменной х,. При рассмотрении булевого кубафункции Й(х) убывающая производнаяхарактеризует направленное (проти"вофазное) изменение Функции й(х)вдоль ребер куба.На фиг.1 представлена структурная схеМа устройства для вычислениябулевых производных; на фиг,2-схема блока вычислений 1 на фиг.З-схемаанализатора разрядов.10 Устройство (фиг.1) содержитпервую группу входов 1 устройства,вторую группу входов 2 устройства,первый сдвиговый регистр 3, комму-таторы 4 и 5, группу элементов б 15 НЕРАВНОЗНАЧНОСТЬ, блок 7 вычислений,анализатор 8 разрядов, третью группу входов 9 устройства, второй сдвиговый регистр 10, выход которого является выходом устройства, тактовыйвход 11. Регистры содержат по и разрядов. Блок вычислений (фиг.2) содержит элементы И 7 - 74 и элементИЛИ 7 . Анализатор разрядов (фиг.З)содержит (и+2) элементов И 81 в .8 ,и элемент ИЛИ 8 О.Устройство работает следующимобразом.В исходном состоянии первый сдвиговый регистр 3 находится в нуле.Значения исходной логической функциина всех наборах входных переменных(таблица истинности подаются нагруппу входов 1 устройства. На груп"пу входов 2 устройства подается иразрядный двоичный код, несущий инЗ 5 формацию о том, по каким переменным вычисляются булевые производныепри функции чувствительности. Привычислении последних по переменным х, в 1-х разрядах кода находят ся едйницы, а в остальных - нули.Тип вычисляемой булевой производнойили функции чувствительности задает"ся кодом, поступающим по группевходов 3 устройства.45 С первым тактовым импульсом навходе 11 устройства в первый сдвиговый регистр 3 в младший разрядзаносится 11, которая каждымследующим тактовым импульсом сдви"гается на один разряд в сторонустарших.для каждого состояния регистРа,З припомощи коммутатора 4 опре-деляются значения исходной Функции,которые поступают на первый входблока 7 вычислений. В группе элементов б НЕРАВНОЗНАЧНОСТЬ по полу)чаемому регистром 3 состоянию ипоступающему по входам 2 коду фор"мируегся другой, набор, для которогопри помощи коммутатора 5 определя ется значение исходной функции,которое подается на второй входблока 7 вычислений. В блоке вычислений в зависИмости от режима работыустройства происходит вычисление 65 соответствующего типа булевых произ"1128263 Если в 1-м разряде счетчика 1, тозакрыт элемент И 72 блока вычисленийи на выходе блока 7 формируетсякд):)к,к,.,=к)х).,1)к.о .5Таким образом, на выходе блока вычислений в этом режиме формируется,кквозрастающая производная функцииГ(х) по переменной х,10 Работа устройства в режиме вычисления убывающей производной ана-,"логична работе в режиме вычислениявозрастающей производной. При этом.значения управЛяющих сигналов на15 группе входов 9 устройства следующие: С 1=СЗ=О, С 2=1,3. Вычисление ориентированныхфункций чувствительности.Рассмотрим вычисление возрастающей функции чувствительности. Значения управляющих сигналов на группе входов 9 устройства следующие:С 1=0, С 2=С 3=1. Поскольку С 3=1, навыходе элемента И 8, и выходеанализатора также единичный сигнал.При этом элементЫ И 72 и 74 блокавычислений заперты. Элемент И 7 бло.ка вычислений также закрыт, поскольку С 1=0, На выходе блока вычисленийформируется Функция1 Х 1 = К К =Г (Х, Х )( Х,Х,); где К и Кг - сигналы на выходах коммутаторов 4 и 5 соответственно. В зависимости от комбинаций сигналов на группе входов 2 устройства эта Функция представляет собой не- ориентированную производную или40 функцию чувствительности,2. Вычисление ориентированных производных.Рассмотрим вычисление возрастающей производной. Значения управляющих сигналов на группе входов 9 45 уст)ройства следующие: С 1=1, С 2=СЗ=О. Элементы И 7, и /+ блока вычислений при этом закрыты. В зависимости от выбранной на группе входов 2 устройства переменной хзначение выхода ана лизатора совпадает с 1-м разрядом) набора, сформированным регистром 3. Если в 1-м разряде счетчика 0,то закрыт также элемент И 7 блока вычислений и на выходе блока 7 Формируется 55 водных или функций чувствительности Анализатор 8 разрядов управляет блоком вычислений только при вычис-, лении ориентированных производных. Значение сигнала на выходе анализатора 8 совпадает со значением разряда регистра 3, выбранного сигналами на группе входов 2 устройства. В зависимости от значения этого разряда регистра 3 анализатор 8 коммутирует элементы И блока вычислений таким образом, чтобы вычислялась соответствующая ориентированная производная. Вычисленные значения производных или функций чувствительности по заднему фронту тактовых импульсов, поступающих на вход устройства 11, заносятся в сдвиговый регистр 10.Рассмотрим работу устройства в разных режимах.1. Вычисление неориентированных производных и функций чувствительности. Значения управляющих сигналов на группе входов 9 устройства следующие: С 1 = С 2=1, а СЗ может иметь произвольное значение. Выход анализатора 8 равен 1", так как на входах элемента И 8,присутствуют высокие потенциалы. При этом элементы)И 72 и 7 блока вычислений закрыты Па выходе блока вычислений формируется функция 1 гх кк)К =Х(Х,Х )0(Х,Хг) функция к)х) )к,к=к)к,к)х) представляющая собой возрастающуюфункцию чувствительности.Работа устройства в режиме вычисления убывающей функции чувствительности аналогична работе устройства в режиме вычисления возрастающейфункции, чувствительности. При этомзначения управляющих сигналов нагруппе входов 9 устройства следующие: С 1=С 3=1, С 2=0.Известное устройство Позволяетвычислять два типа дифференциальныхоператоров: неориентированные производные и неориентированные функциичувствительности.Предложенное устройство помимоэтих функций позволяет также вычислять. дополнительно четыре типа дифференциальных операторов: возрастающие производные и функции чувствительности, убывающие производныеи функции чувствительности,Таким образом, число типов вычис.ляемых функций в предлагаемом устройстве по сравнению с известнымвозросло в три раза, что позволяетсущественно расширить область егоприменения,