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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН

3(51) G 06 F 15/31

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

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

H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3520768/24-24(22) 10.12,82 (46) 07.12.84. Бюл. Р 45 (72) Н.Т.Березюк, M.Ф.Холодный, В.Ю.Ларченко и Н.Г.Коробков (71) Харьковский ордена Ленина авиационный институт им.Н.Е.Жуковского (53) 681.3(088.8) (56) 1.Авторское. свидетельство СССР

Р 940166, кл. G.06 F 15/31, 1982.

2. Авторское свидетельство СССР

Р 1016778, кл. G 06 F 7/04, 1982. (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ .БУЛЕВЫХ ПРОИЗВОДНЫХ, содержащее коммутаторы, группу элементов НЕРАВНОЗНАЧНОСТЬ, сдвиговые регистры, причем первая группа входов устройства нодключена к информационным входам коммутаторов соответственно, управляющие входы первого коммутатора подключены к выходам первого сдвигового регистра соответственно, управляющие входы второго коммутатора подключены к соответствующим выходам элементов НЕРАВНОЗНАЧНОСТЬ группы, первая группа входов которой подключена к выходам первого сдвигового регистра соответственно, а вторая группа входов подключена к второй группе входов, устройства соответственно, тактовый вход устройства подключен к управляющим входам сдвиговых регистров, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения путем обеспечения возможности вычисления неориентированных и ориентированных булевых производных и функций чувствительности, в него введены блок вычислений и анализатор разрядов, при этом выходы первого и второго коммутаторон соединены соответственно с первым и вторым входами блока вычислений, выход которого соединен с информационным входом нторого сдвигового регистра, первая группа входон анализатора разрядов соединена,ÄÄSUÄÄ 1128263 А с выходами первого сдвигового регистра соответственно, вторая группа входов анализатора разрядов соединена с второй группой входов устройства соответственно, а выход анализатора разрядов подключен к третьему входу блока вычислений, группа входов блока вычислений и третья группа входов анализатора разрядов соединены с третьей группой входов устройства соответственно, блок вычислений состоит из элемента 4И-ИЛИ, причем первый вход блока вычислений соединен с инверсным входом первого элемента И, первым инверсным входом второго элемента И, первыми .прямыми входами третьего и четвертого эле- Я ментов И, второй вход блока вычислений соединен с первыми прямыми входами первого и второго элементов .И, инверсным входом третьего элемен- С та И, третий вход блока вычислении соединен с вторыми прямыми входами первого и третьего элементов И и с вторыми инверсными входами второго и четвертого элементов И, первый вхо » группы входов блока вычислений .соединен с вторым и третьим прямыми входами соответственно второго и третье- (ф го элементов И, второй вход группы-входов блока вйчислений соединен с Я третьим и вторым прямыми входами соответственно первого и четвертого элементов И, выход блока вычислений СФ соединен с выходом элемента ИЛИ, анализатор разрядов содержит элементы И и элемент ИЛИ, причем входы первой и второй групй входов анализатора соединены соответственно с первыми,фЬ и вторыми входами элементов И, первый и второй входы третьей группы входов соединены с первым и вторым входами следующего элемента И, третий вход третьей группы входов соединен с входами .последнего элемента И, выходы элементов И соединены с входами элемента ИЛИ, выход которого соединен с выходом а нализатора разрядов.

1128263;

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

Известны устройства для вычисления неориентированных булевых производных, содержащие счетчик,. коммутаторы, группу элементов НЕРАВНОЗНАЧНОСТЬ, регистр)13.

Наиболее близкой к изобретению по технической сущности является схема сравнения кодов, позволяющая вычислять неориентированные булевые производные и функции чувствительнос" ти и содержащая счетчик, коммутаторы,15 группу элементов НЕРАВНОЗНАЧНОСТЬ, элемент НЕРАВНОЗНАЧНОСТЬ, сдвиговый регистр, при этом входы первой группы схемы подключены к информационным входам коммутаторов соответственно, 20 управ.ляющие входы второго коммутатора подключены к Выходам счетчика соответственно,управляющие ьходы второго коммутатора подключены к выходам элеНЕРАВНОЗНАЧНОСТЬ группы пер 25 вые входы которых подключены к выходам счетчика соответственно, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ подключены к входам второй группы схемы, выходы кдммутаторов подключены к входам

30 элемента НЕРАВНОЗНАЧНОСТЬ соответственно, выход элемента НЕРАВНОЗНАЧНОСТЬ подключен к информационному входу сдвигового регистра, управляющий вход которого подключен к входу подачи счетных импульсов схемы и к счетному входу счетчика Г2).

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

Целью изобретения является расширение области применения путем обеспечения возможности вычисления неоРиентированных и ориентированных 45 булевых производных и функций чувст- . вительности.

Поставленная цель достигается тем, что в устройство для вычисления булевых производных, содержащее коммутаторы, группу элементов НЕРАВНОЗНАЧНОСТЬ, сдвиговые регистры, причем первая группа входов устройства подключена к информационным входам коммутаторов соответственно, управляющие входы первого коммутатора подключены к выходам первого сдвигового регистра соответственно, управляющие входы второго коммутатоРа подключены к соответствующим выходам элементов НЕРАВНОЗНАЧНОСТЬ 60 группы, первая группа входов которой подключена к выходам первого сдвигового регистра соответственно, а вторая группа входов подключена к второй группе входов устройства 65 соответственно, тактовый вход устройства подключен к управляющим входам сдвиговых.,регистров, введены блок вычислений и анализатор разрядов, при этом выходы первого и второго коммутаторов соединены соответственно с первым и вторым входами блока вычислений, выход которого соединен с информационным входом второго сдвигового регистра, первая группа входов анализатора разрядов соединена с выходами первого сдвигового регистра соответственно, вторая .группа входов анализатора разрядов соединена с входами второй группы устройства соответственно, а выход анализатора разрядов подключен к. третьему входу блока вычисления, группа входов блока вычислений и третья группа входов анализатора разряцов соединены с третьей группой входов устройства соатве1 =твенно, блок вычислений состоит из элемента 4И-ИЛИ, причем первый вход блока вычислений соединен с инверсным входом первого элемента И, пер- вым инверсным входом второго элемента И, первыми прямыми входами третьего и четвертого элементов И, второй вход блока вычислений соединен с первыми прямыми входами первого и второго элементов И, инверсным входом третьего элемента И, третий вход блока вычислений соединен с вторыми прямыми входами первого и третьего элементов И и с вторыми инверсными входами второго и четвертого элементов И, первый вход группы входов блока вычислений соединен с вторым и третьим прямыми входами соответственно второго и третьего элементов И, второй вход группы входов блока вычислений соединен с третьим и вторым прямыми

L входами соответственно первого и четвертого элементов. И, выход блока. вычислений соединен с выходом элемента ИЛИ, анализатор разрядов содержит элементы И и элемент ИЛИ, причем входы первой и второй групп входов анализатора соединены соответственно с первыми и вторыми входами элементов И, первый и второй входы третьей группы входов соединены с первым и вторым входами следующего элемента И, третий вход третьей группы соединен с входами последнего эле- мента И, выходы элементов И соединены с входами элемента ИЛИ, выход которого соединен с выходом анализатора разряцов. 3 (x)

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

31(х) х 1"" 1-1 1 1+1 - 1® (1 -

1128263

Производная функция †- (†-", -характеризует изменение функции f(х) при изменении одной иэ ее переменных х„ и равна единице на тех входных наборах, на которых изменение переменной х; приводит к изменению функции. Если рассмотреть булев куб функции f(х), то производная функах(х) ция! — — характеризует изменение

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

1 функцией чувствительности эх„ от функции f (х) по подмножеству х„= 1х„,..., «райх называется Функция, определяемая по Формуле

Л(х,х ) а%(х, х- ), 1

X = х,,x ), Х =Х Х„, ( функция чувствительности gx xa1 рактеризует изменение функций при одновременном изменении нескольких ее переменных х„,...,хр в х и равна единице на тех входных наборах, на которых одновременное изменение нескольких ее переменных приводит .к изменению функции. При рассмотрении булевого куба функции f(х) функция чувствительности характеризует изменение функции по диагоналям куба.

Ориентированные булевые производные .ао х (х) „а1

a«1 дх, . не только изменение, но и направление изменения функции f(х) при изменении одной из ее переменных х„ .. а е(х)

Возрастающая производная о .определяется по.формуле 1. — = Е(х,..1х., О, х;.,„,...,х„I (х„...,.х; „,, Дх. = (11--;, 1+ х характеризует направленное изменение функции f(x) при изменении одной из — ее переменных х,. и равна единице на тех входных ребрах, на которых функция f(x) возрастает (убывает) с воз.

; растанием (убыванием) переменной х, .

При рассмотрении булевого куба

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

1 а„1(х)

Убывающая производная определяется по формуле а„йх> . —" — =Е(х1,...,Х;1,0,«,,„, .,«n)1(х„,...,хj „ > х.

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

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

На фиг.l представлена структурная схеМа устройства для вычисления булевых производных; на фиг.2-схема блока вычислений; на фиг.3-схема анализатора разрядов.

10 Устройство (фиг.l) содержит первую группу входов 1 устройства, вторую группу входов 2 устройства, первый сдвиговый регистр 3, коммутаторы 4 и 5, группу элементов б

15 НЕРАВНОЗНАЧНОСТЬ., блок 7 вычислений, анализатор 8 разрядов, третью группу входов 9 устройства, второй сдвиговый регистр 10, выход которого является выходом устройства, тактовый вход 11. Регистры содержат по и разрядов. Блок вычислений (фиг.2) содержит элементы И 7„ — 74 и элемент

ИЛИ 7> . Анализатор разрядов (фиг.3) содержит (и+2) элементов И 8> †.8 „+ и элемент ИЛИ 8О.

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

В исходном состоянии первый сдвиговый регистр 3 находится в нуле.

Значения исходной логической функции на всех наборах входных переменных (таблица истинности подаются на группу входов 1 устройства. На груп" пу входов 2 устройства подается и разрядный двоичный код, несущий инЗ5 формацию о том, по каким переменным вычисляются булевые производные" при функции чувствительности. При вычислении последних по переменным х, в 1-х разрядах кода находят40 ся едйницы, а в остальных — нули.

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

45 С первым тактовым импульсом на входе ll устройства в первый сдвиговый регистр 3 в младший разряд заносится 1, которая каждым следующим тактовым импульсом сдви" гается на один разряд в сторону старших.для каждого состояния регистРа,3 при помощи коммутатора 4 опре- деляются значения исходной функции, которые поступают на первый вход блока 7 вычислений. В группе элементов б НЕРАВНОЗНАЧНОСТЬ по полу чаемому регистром 3 состоянию и поступающему по входам 2 коду формируегся другой, набор, для которого при помощи коммутатора 5 определяется значение исходной функции, которое подается на второй вход блока 7 вычислений. В блоке вычислений в зависИмости от режима работы устройства происходит вычисление 5 соответствующего типа булевых произ"

1128263

Если в i-м разряде начетчика 1, то закрыт элемент И 7 блока вычислений и на выходе блока 7 формируется Kl=je,к,jl»,=Ïõi)„,1 >j„

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

- . Г возрастающая производная функции

f(х) по переменной х, 10 Работа устройства в режиме вычисления убывающей производной ана-, логична работе в режиме вычисления возрастающей производной. При этом .значения управЛяющих сигналов на

15 группе входов 9 устройства следующие: Сl=СЗ=О, С2=1, 3. Вычисление ориентированных функций чувствительности.

Рассмотрим вычисление возрастающей функции чувствительности. Значения управляющих сигналов на группе входов 9 устройства следующие:

Cl=0, C2=C3=1. Поскольку C3=-1, на выходе элемента И 8„, и выходе анализатора также единичный сигнал.

При этом элементЫ И 7 и 74 блока вычислений заперты. Элемент И 7> бло. ка вычислений также закрыт, поскольку С1=0. На выходе блока вычислений формируется функция (Х)-К К 1(Х,Х)f(Õ,Х,) где К„ и К вЂ” сигналы на выходах 35 коммутаторов 4 и 5 соответственно.

В зависимости от комбинаций сигналов на группе входов 2 устройства эта функция представляет собой неориентированную производную или

40 функцию чувствительности.

2. Вычисление ориентированных производных.

Рассмотрим вычисление возрастающей производной. Значения управляющих сигналов на группе входов 9 45 устройства следующие: Сl=l, С2=СЗ=О.

Элементы И 7, и /+ блока вычислений при этом закрыты. В зависимости от выбранной на группе входов 2 устройства переменной х„. значение выхода ана- 50 лизатора совпадает с i-м разрядом набора, сформированным регистром 3.

Если в i-м разряде счетчика 0,то закрыт также элемент И 7 блока вычислений и на выходе блока 7 формируется55 водных или функций чувствительности

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

Значение сигнала на выходе анализатора 8 совпадает со значением разряда регистра 3, выбранного сигналами на группе входов 2 устройства. В заВНсНМосТН от значения этого разряда регистра 3 анализатор 8 коммутирует элементы И блока вычислений таким образом, чтобы вычислялась соответствующая ориентированная производная.

Вычисленные значения производных или функций чувствительности по заднему фронту тактовых импульсов, поступающих на вход устройства 11, заносятся в сдвиговый регистр 10.

Рассмотрим работу устройства в разных режимах.

1. Вычисление неориентированных производных и функций чувствительности. Значения управляющих сигналов на группе входов 9 устройства следующие: Cl = С2=1, а СЗ может иметь произвольное значение. Выход анализатора 8 равен 1, так как на входах элемента И 8„+„присутствуют высокие потенциалы. При этом элементы

И 7 и 7 блока вычислений закрыты., На выходе блока вычислений.формируется функция

У К K YK К -К 9К Х(Х х )О (Х,X ), функцHя

q p xi =(ic, к, j/„, = К i XlI „, < ixi) „ представляющая собой возрастающую функцию чувствительности.

Работа устройства в режиме вычисления убывающей функции чувствительности аналогична работе устройства в режиме вычисления возрастающей функции. чувствительности. При этом значения управляющих сигналов на группе входов 9 устройства следующие: Cl=C3=1, С2=0.

Известное устройство Позволяет вычислять два типа дифференциальных операторов: неориентированные производные и неориентированные функции чувствительности.

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

Таким образом, число типов вычис.ляемых функций в предлагаемом устройстве по сравнению с известным возросло в три раза, что позволяет существенно расширить область его применения.

1128263

1128263

Фи8 У

Составитель И.Пчелинцев

Техред M.Êóçüìà КОрректор Л.Пилипенко

Редактор А.Гратилло

Подписное

Заказ 9063/37 Тираж 698

ВНИИПИ ГосударстВенного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП Патент, r.Óæãîðîä, ул.Проектная, 4