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

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при построении устройств тестового и аппаратурного контроля цифровых устройс Известны устройства для вычислеВИЯ неориентированных булевых производных, содержащие счетчик, коммутаторы, группу элементов НЕРАВНОЗНАЧНОСТЬ регистр 13. . Наиболее близкой к изобретение по технической сущности является схема сравнения кодов, позволяющая вычислять неориентированные булевые производные и функции чувствительнос ти и содержащая счетчик, коммутаторы группу элементов НЕРАВНОЗНАЧНОСТЬ, элемент НЕРАВНОЗНАЧНОСТЬ, сдвиговый регистр, при этом входы первой группы схемы подключены к информационным входам коммутаторов соответственно, управляющие входы второго коммутатор подключены к Ьыходам счетчика соответственно,управляющие ьходы второго коммутатора подключены к выходам эле ментов НЕРАВНОЗНАЧНОСТЬ; группы-, пер вые входы которых подключены к выход счетчика соответственно, вторые вход элементов НЕРАВНОЗНАЧНОСТЬ подключен к входам второй группы схемы, выходы кбммутаторов подключены.к входам элемента НЕРАВНОЗНАЧНОСТЬ соответственно, выход элемента НЕРАВНОЗНАЧНОСТЬ подключен к информационному входу сдвигового регистра, управляющий вход которого подключен к входу подачи счетных импульсов схемы и к счетному входу, счетчика Гз, Недостатком известного устройств является невозможность вычисления ориентированных булевых производных и функций чувствительности. Цепью изобретения является расширение области применения путем обеспечения возможности вычисления неориентированных и ориентированных булевых-производных и функций чувствительности. Поставленная цель достигается тем что в устройство для вычисления булевых производных, содержащее коммутаторы, группу элементов НЕРАВНО- ЗНАЧНОСТЬ, сдвиговые регистры, причем первая группа входов устройства подключена к информационным входам коммутаторов соответственно, управляющие входы первого коммутатора подключены к выходам первого сдвигового регистра соответственно, управляквдие входы второго коммутато ра подключены к соответствующим выходам элементов НЕРАВНОЗНАЧНОСТЬ группы первая группа входов которой подключена к выходам первого ( сдвигового регистра соответственно, а вторая группа входов подключена к второй группе входов устройства соответственно, тактовый вход устройства подключен к управляющим входам сдвиговых.регистров, введены блок вычислений и анализатор разрядов, при этом выходы первого и второго коммутаторов соединены соответственно с первым и вторым входами блока вычислений, выход которого соединен с информационным входом второго сдвигового регистра, первая группа входов анализатора разрядов соединена с выходами первого сдвигового регистра соответственно, вторая .группа входов анализатора разрядов соединена с входами второй группы устройства соответственно, а Выход анализатора разрядов подключен К- третьему входу блока вычисления, группа входов блока вычислений и третья группа входов, анализатора разрядов соединены с третьей группой входов устройства соотве ственно, блок вычислений- состоит из элемента 4И-ИЛИ, причем первый вход блока вычислений соединен с инверсным входом первого элемента И, первым инверсным входом второго элемента И, первыми прямыми входами третьего и четвертого элементов И, второй вход блока вычислений соединен с первыми прямыми входами первого и второго элементов И, инверсным входом третьего элемента И, третий вход блока вычислений соединен с вторьп«1и прямыми входами первого и третьего элементов И и с вторыми инверсными входами второго и четвертого элементов И, первый вход группы входов блока вычислений соединен с вторым и третьим прямыми входами соответственно второго и третьего элементов И, второй вход группы входов блока вычислений соединен с третьим и вторым прямыми входами соответственно первого и четвертого элементов. И, выход блока, вычислений соединен с выходом элемента ИЛИ, анализатор разрядов содержит элементы И и элемент ИЛИ, причем входы первой и второй групп входов анализатора соединены соответственно с первыми и вторыми входами элементов И, первый и второй входы третьей группы входов соединены с первым и вторым входами следующего элемента И, третий вход третьей группы соединен с входами последнего элемента И, выходы элементов И соединены с входами элемента ИЛИ, выход которого соединен с выходом анализатора разрядов.. j Производной булевой функцией от функции {(xl, Х {ХтХ2 , . , . ,Х по переменной х. называется функция , определяемая по формуле f К.-м.,,-,,...,Xn)©f(,-.,-, i 1 i+1 1---I

характеПроизводная функция изменение функьГни f (х) при j ризует

изменении одной из ее переменных х и равна единице на тех входных .наборах, на которых изменение переменной х,; приводит к изменению функции. Если рассмотреть булев куб функции f(x), то производная функ,(Jf(x)

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

ция

функции f(х) вдоль ребер куба.

Функцией чувствительности . . - ,

ОТ функции f(х) по подмножеству

. называется функция,

определяемая по формуле

:-fr(S.2)®(.) .

. . NMs- pV- r i--iiUi

функция чувстйительности sx, 5 рактеризует изменение функций при одновременном изменении нескольких ее- переменных х,...,Хре х и равна единице на тех входных наборах, на которых одновременное изменение нескольких ее переменных приводит к изменению функции. При рассмотрении булевого куба функции f(x) функция чувствительности характеризует изменение функции по диагоналям куба. Ориентированные булевые производные характеризуют dx, (Зх . - ке только изменение, но и направление изменения функции f(х) при изменении одной из ее переменных,х ..

дМ Возрастающая производная °--определяется по.формуле i ,U) 7

::(x,,...,x.,,o,x.,,...,Xrt)f(,.,..

Xj

it-ir-- 1

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

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

При рассмотрении булевого куба функции f(х) возрастающая производная характеризует направленное (синфазное) . изменение функции f(х) вдоль .ребер куба. Убывающая производная определяется по формуле i

t(x,XM,o.4.,-.n)fiN.-.. ..

.%)

V.

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

При рассмотрении булевого куба функции f(x) убывающая производная характеризует направленное (противофазное) изменение функции f(x) вдоль ребер куба.

На фиг.1 представлена структурна я схема устройства для вьлчисления булевых производных; на фиг.2-схема блока вычислений; на фиг.З-схема анализатора разрядов. 10 Устройство (фиг.1) содержит

первую группу входов 1 устройства, вторую группу входов 2 устройства, первый сдвиговый регистр 3, комму-, таторы 4 и 5, группу элементов 6 5 НЕРАВНОЗНАЧНОСТЬ-, блок 7 вычислений, анализатор 8 разрядов, третью группу входов 9.устройства, второй сдви говый регистр 10, выход которого является выходом устройства, тактовый 0 ВХОД 11. Регистры содержат по п разрядов. Блок вычислений (фиг.2) содержит элементы И. 7 и элемент ИЛИ 7 . Анализатор разрядо в (фиг.З) содержит (п+2) элементов- И 8.,-..8 . и элемент ИЛИ 8.

5

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

В исходном состоянии первый сдвиговый регистр 3 находится в нуле. Значения исходной логической функции на всех наборах входных переменных (таблица истинности подаются на группу входов 1 устройства. На груп- пу входов 2 устройства подается п

разрядный двоичный код, несущий ин- 5 формацию о том, по каким переменным вычисляются булевые производныепри функции чувствительности. При вычислении последних по переменным х. в i-x разрядах кода находят0 ся единицы, а в остальных - нули. Тип вычисляемой булевой производной или функции чувствительности задается кодом, поступающим по группе входов 3 устройства.

5 С первым тактовым импульсом на входе 11 устройства в первый сдвиговый регистр 3 в младший разряд заносится 1 , которая каждым следующим тактовым импульсом сдвип .гается на один разряд в сторону тарших.Для каадого состояния регист рй, 3 при помощи коммутатора 4 определяются значения исходной функции, .которые поступают на первый вход б.11ока 7 вычислений. В группе эле ментов 6 НЕРАВНОЗНАЧНОСТЬ по полу чаемому регистром 3 состоянию и поступающему по входам 2 коду формируется другой, набор, для которого при помощи коммутатора 5 определя0 ется значение исходной Функции, которое подается на второй вход блока 7 вычислений. В блоке вычислений в зависимости от режима работы ,устройства происходит вычисление 5.соответствующего типа булевых ПроизВОДНЫХ или функций чувствительности Анализатор 8 разрядов управляет блоком вьачислений только при вьгчис- лении ориентированных производных, значение сигнала на вьрсоде анализатора 8 совпадает со значением разря да регистра 3, выбранного сигналами на группе входов 2 устройства. В за висимости от значения этого разряда регистра 3 анализатор 8 коммутирует элементы И блока вычислений таким образом, чтобы вычислялась соответс вующая ориентированная производная. Вычисленные значения производных или функций чувствительности по зад нему фронту тактовых импульсов, пос тупающих на вход устройства 11, заносятся в сдвиговый регистр 10. Рассмотрим работу устройства в разных режимах. 1,Вычисление неориентированных производных и функций чувствительности. Значения управляющих сигнало на группе входов 9 устройства следу щие: С1 , а СЗ может иметь произвольное значение. Выход анализ тора 8 равен , так как на входах элемента И 8,. присутствуют высокие потенциалы. При этом элементы И 7 и 7 блока вычислений закрыты. На выходе блока вычислений.формируётся функция l.XhR, )(®K2 f(x,xJ®(x,,X), где К, и Kj - сигналы на выходах коммутаторов 4 и 5 соответственно. В зависимости от комбинаций сигналов на группе входов 2 устройства эта функция представляет собой неориентированную производную или функцию чувствительности. 2.Вычисление ориентированных производных. Рассмотрим вычисление возрастающей производной. Значения управляющих сигналов на группе входов 9 устройства следующие: , Элементы И 7 и / блока вычислений при этом закрыты. В зависимости от выбранной на группе входов 2 устрой ва переменной Х;; значение выхода анализатора совпадает.с i-м разрядом набора, сформированным регистром 3. Если в i-M разряде счётчика О,т закрыт также элемент И 7j блока выч лений и на выходе блока 7 формирует функция (-(.4,-о-Щ,-о Щ сЕсли в 1-м разряде счетчика , то закрыт элемент И 7 блока вычислений и. на выходе блока 7 формируется (-..)1хр1 Ихг- Н.г-0 Таким образом, на выходе блока вычислений в этом режиме формируется возрастающая производная функции f(x) по переменной х,., Рабрта устройства в режиме вычисления убывающей производной ана-. логична работе в режиме вычисления возрастающей производной. При этом значения управляющих сигналов на группе входов 9 устройства следующие: , . , 3. Вычисление ориентированных функций чувствительности. , Рассмотрим вычисление возрастающей функции чувствительности. Зна- , ченияуправляющих сигналов на группе входов 9 устройства следующие: , . Поскольку , на выходе элемента И Q. и выходе анализатора также единичный сигнал. При этом элементы VI 7 к 7 блока вычислений заперты. Элемент И 7j блока вычислений также закрыт, поскольку . На выходе блока вычислений формируется функция (x,)(2)f()c,,7, , представляющая собой возрастающую функцию чувствительности. Работа устройства в режиме вычисления убывающей функции чувствительности аналогична работе устройства в режиме вычисления возрастающей функции, чувствительности. При этом значения управляющих сигналов на группе входов 9 устройства следующие: , . Известное устройство позволяет вьгчислять два типа дифференциальных операторов: неориентированные производные и неориентированные функции чувствительности. Предложенное устройство помимо этих функций позволяет также вычислять дополнительно четыре типа дифференциальных операторов: возрастающие производные и функции чувствительности, убывающие производные и функции чувствительности. Таким образом, число типов вычисляемых функций в предлагаемом уст- . ройстве по сравнению с известным возросло в три раза, что позволяет существенно расширить область его применения.

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ .БУЛЕВЫХ ПРОИЗВОДНЫХ, содержащее коммутаторы, группу элементов НЕРАВНОЗНАЧНОСТЬ, сдвиговые регистры, причем первая группа входов устройства подключена к информационным входам коммутаторов соответственно, управляющие йходы первого.коммутатора подключены к выходам первого сдвигового регистра соответственно, управляющие входы второго ком1иутатора подключены к соответствующим выходам элементов НЕРАВНОЗНАЧНОСТЬ группы, первая группа входов которой подключена к выходам первого сдвигового регистра соответственно, а вторая группа входов подключена к второй группе входов .устройства соответственно, тактовый вход устройства подключен к управляющим входам сдвиговых регистров, от ли чающееся тем, что, с целью расширения области применения путем обеспечения возможности вычисления неориентированных и ориентированных булевых производных и функций чувствительности, в него введены блЪк вычислений и анализатор разрядов, при этом выходы первого и второго коммутаторов соединены соответственно с первым и вторым входами блока вычислений, выход которого соединен с информационным входом второго сдвигового регистра, первая группа входов анализатора разрядов соединена с выходами первого сдвигового регистра соответственно,вторая группа входов анализатора разрядов соединена с второй группой входов устройства соответственно, а выход анализатора разрядов подключен к тре-тьему входу блока вычислений, группа входов блока вычислений и третья группа входов анализатора разрядов соединены с третьей группой входов устройства соответственно, блок вычислений состоит из элемента 4И-ИЛИ, причем первый вход блока вычислений соединен с инверсным входом первого элемента И, первым инверсным входом второго элемента И, первыми .прямыми входами третьего и четвертого ментов И, второй вход блока вычис(Л лений соединен с первыми прямыми входами первого и второго элементов И, инверсным входом третьего элемента И, третий вход блока вычислений соединен с вторыми прямыми входами первого и третьего элементов И и с вторыми инверсными входами второго и четвертого элементов И, первый вход группы входов блока вычислений .соедиto нен с вторым и третьим прямыми входами соответственно второго и третье00 го элементов И,-второй вход группыto входов блока вычислений соединен с третьим.и вторым прямыми входами Ot) соответственно первого и четвертого оо элементов И, выход блока вычислений соединен с выходом элемента ИЛЙ анализатор разрядов содержит элементы И и элемент ИЛИ, причем входы первой и второй групп входов анализатора соединены соответственно с первыми и вторыми входами элементов И, первый и второй входы третьей группы входов соединены с первым и вторым входами следующего элемента И, третий вход третьей группы входов соединен с входами .последнего элемента И, выходы элементов И coejзинeны с вхо:дами элемента ИЛИ, выход которого i соединен.с выходом анализатора разрядоа

Ml

11

8

fptiZ.I