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

 

Союз Советскик

Социапистичвскик

Рвснубякк

О Л И С А Н И Е ()94()16 8

ИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6l ) Дополнительное к авт. свид-ву (22)Заявлено 31.12.80 (2l) 3228977/18-24 с присоединением заявки № (23) Приоритет (51)M. Кл.

G 06 F 15/31

3Ьеудврстеапвй комитет

СССР ае денем нзабрвтенн11 н втерытнй

Опубликовано 30. 06. 82. Бюллетень № 24

Дата опубликования описания 30. 06. 82 (53) УДК 681. . 325(088. 8) Э.В. Лысенко, И.Т. Скибенко, В.А. Дергачев и В.Ф. Огородов (72) Авторы изобретения

Харьковский ордена Ленина авиационный институт им. Н.Е.Жуковского (7l ) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ

ДИФФЕРЕНЦИАЛОВ

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

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

Известно устройство для сравнения 2о чисел предназначенное для вычисления булевой разности, содержащее шину исходных данных, шину управле" ния, шину результата, двоичный

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

/ выходы демультиплексора соединены с входами регистра результата, выходы которого являются выходами устройства Pj

Недостатками известного устройства являются ограниченные функциональные возможности, так как оно

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

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

Устройство для вычисления булевых дифференциалов содержит шину 1 исходных данных, шину 2 переменных, двоичный счетчик 3, мультиплексоры 4 !

5 и 5, блок элементов И-НЕ 6, двухвходовый элемент НЕРАВНОЗНАЧНОСТЬ

7, демультиплексор 8, регистр 9 результата, шину 10 результата, элемент

И 11, блок 12 разрешения записи и

zo шину 13 выбора режима.

Элементы устройства (фиг. 1) соединены следующим образом. Шина 1 исходных данных соединена с информационными входами 1 мультиплексоров 4 и 5 гз выходы двоичного счетчика 3 соединены с управляющими входами 11 мультиплексора 4, демультиплексора .8 и с первой группой 1 входов блока 6, шина

2 соединена с второй группой 11 входов блока элементов И-НЕ 6, выходы которого соединены с,управляющими входами ?1 мультиплексора 5 и первой группой входов I схемы разрешения элемента НЕРАВНОЗНАЧНОСТЬ 7, входы элемента И 11 соединены с выхода 35 ми элемента 7 и блока 12, а выход соединен с информационным входом с демультиплексора 8, выходы демультиплексора 8 соединены с входами регистра 9 результата, выход которого соединен с выходной шиной 10 результата., шина 13 соединена с втоР рой П группой входов блока 12 разрешения записи.

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

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

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

И-НЕ, два мультиплексора, демультиплексор, регистр результата, элемент

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

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

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

НЕ, причем первые входы элементов И каждой ячейки являются первой группой входов блока разрешения записи, а вторые входы этих элементов И являются второй группой входов блока разрешения записи, первый выход этого элемента соединен с первым входом элемента ИЛИ, второй вход которого подключен через элемент НЕ к соответствующему разряду второй группы входов блока разрешения записи, Мультиплексоры 4 и 5 предназначены для выбора на основании управляющего кода II соответствующего разряда из информационного двоичного кода I.

Блок элементов И-НЕ 6 предназначен для инвертирования соответ0166 6 входы l-ой функциональной ячейки

12.0 соединены с i-м разрядом первой группы входов Г, вторые входыс i-м разрядом второй группы входов

7), выходы функциональных ячеек соединены с входами элемента И 12.1, выход которого является выходом схемы разрешения записи. Функциональная ячейка 12.0 состоит из элементов о ИЛИ 12.2, И 12.3, HE 12.4, соединенных следующим образом. Выходы элемента

И 12.3 соединены с первым 3 и вторым

tJ входом функциональной ячейки, выход элемента И 12.3 соединен с первым

15 входом элемента ИЛИ 12.2, второй

JL вход ячейки соединен через элемент

НЕ 12.4 с вторым входом элемента

ИЛИ 12.2.

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

Устройство содержит две шины 2 и

13 управления. Значение сигналов на них определяет режим работы устройства.

z5 1. Вычисление неориентированных булевых дифференциалов (булевых разI ностей).

Значение управляющих сигналов (все разряды) на шине 13 равны "0".

При этом на выходе блока 12 разреше3Е

1l1 11 ния записи формируется сигнал 1;, причем это значение не зависит от значений сигналов на выходе блока

6 из уравнения (1) и следовательно, сигнал с выхода элемента 7 поступает

55 на информационныи вход с демультич плексора 8. Подавая сигнал "1" на ,те разряды шины 2 переменных, номера которых соответствуют номерам пере40 менных, по которым необходимо вычислить булевый дифференциал, на шине

10 результата получаем результат.

Работа предлагаемого устройства

s этом режиме аналогична работе изф5 ве ог

5 94 ствующих разрядов двоичного кода, поступающего на первую группу входных выходов 1, в соответствии со значением управляющих сигналов, поступающих на вторую группу входных выводов 1? по шине переменных.

Элемент НЕРАВНОЗНАЧНОСТЬ 7 предназначен для сравнения сигналов, поступающих с выходов мультиплексоров 4 и 5.

Демультиплексор 8 предназначен для выдачи информационного сигнала, поступающего с выхода элемента И ll в соответствии со значением управляющего слова, поступающего с дво- . ичного счетчика 3, на соответствующий выходной наружный вывод.

Регистр 9 результата предназначен для хранения и накопления значений булевой разности. Выходы регистра результата образуют шину 10 результата.

Элементы 3-10 схемы могут быть выполнены и в известном устройстве, так как решают аналогичные задачи.

Элемент И 11 предназначен для управления прохождением информационного сигнала с выхода элемента

НЕРАВНОЗНАЧНОСТЬ 7, на информационный вход с демультиплексора 8, в зависимости от значения сигнала с1 с выхода блока разрешения записи.

Если а=1, то происходит передача значения сигнала с выхода элемента

НЕРАВНОЗНАЧНОСТЬ 7 в демультиплексор 8 и последующая запись в регистр 9. При а=О запись не производится (т.е. записывается "0").

Блок 12 разрешения записи имеет две группы по 1 входов (1 и II) и один выход а и предназначен для формирования сигнала разрешения записи на основании значений сигналов на входных выводах I и И .

Обозначим значения сигналов первой группы входов I через д„(i=i ï), а второй группы череэ Ь ()=Г,п), тогда логическая функция, описывающая ая работу схемы разрешения записи, имеет вид я а= Л (Ь.vd„b-) . (1) Возможная реализация схемы разрешения записи (фиг. 2) состоит из элементов И. 12, 1 и 12. 3, элемента

ИЛИ 12.2, элемента НЕ 12.4;- . промежуточные функциональные ячейки обозначены позицией 12.0. Элементы схемы соединены следующим образом. Первые, Ilo определению булевым дифференциалом (разностью) логической функции F (х, ..., х„) по переменной х называется логическая

1 функция R (х,, x ) вида

В(х.1, ..., х ) = F(x<, ..., х„, х)8F(х,1, ..., х.,, ..., x ), т е. и

-для вычисления функции К(х„, x ) необходимо вычислить значение и функции F на наборе х,, ..., х, °, хи и сложить по модулю 2 со значением исходной функции на рассматриваемом наборе.

7 9401

Значения исходной функции на всех двоичных наборах входных переменных (таблица истинности функции) подаются на шину 1 исходных данных.

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

Если она вычисляется flO переменной

x., то в 1-м разряде двоичного кода to будет н1", во всех остальных разрядах - "0". Например, для и 3 при вычислении булевой разности по переменной х,1 двоичный код имеет вид 100.

Двоичный счетчик 3 формирует по- ls следовательность двоичных наборов

{двоичных слов). Для каждого набора производятся определенные значения исходной функции на данном наборе (на выходе мультиплексора 4), в блоке элементов И-HE 6 на основании уп* равляющего кода формируется набор х, ..., х,;, ..., х, и определяется значение исходной функции на этом наборе (на выходе мультиплексора 5) рз

Элемент НЕРАВНОЗНАЧНОСТЬ 7 производит сложение по модулю 2 значений функции на наборах x ..., x х„, и х, ..., х„, ...,х . Результат сложения поступает на ийформационный вход демультиплексора 8 ьф в зависимости от рассматриваемого двоичного набора (поступающего с двоичного счетчика 3) выдается по соответствующему выводу в регистр результата.

После рассмотрения всех 2 наборов и в регистре результата сформирована булевая разность. Устройство работает аналогично в случае вычисления булевой разности Ilo нескольким переменным.

2. Вычисление ориентированных булевых дифференциалов.

Булевым дифференциалом, ориентированным на увеличение д 1(gД)(уменьшение d f (x ), называется булева функция, равная l тогда и только тогда, когда f(2) изменяется при изменении из О в 1 (из 1 в О)., Устройство позволяет вычислять булевы дифференциалы, ориентированные как на увеличение, так и на уменьшение. Для этого необходимо задать следующие значения управляющих сигйалов: а) шина 2 переменных. Значейие

i-ro разряда равно 1 (или О), если необходимо вычислить булевый дифференциал, ориентированный на увеличение (на уменьшение) no i-й переменной. Значение разрядов, соответствующих переменным, для которых не нужно вычислять ориентированный булевый дифференциал, может быть произвольным (О или l), так как исключение этих значений производится в блоке 12. б) Значение i-ro разряда на шине

13 выбора режима равно 1, если по переменной xi необходимо вычислить л ориентированный булев дифференциал, и равно О в противном случае.

Пример . Необходимо вычислить ориентированный на увеличение булев дифференциал по переменной х для логической функции от четырех переменных (n-4).

Исходные данные представлены в таблице.

После подготовки исходных данных и начала работы схема работает аналогично случаю l. Особенностью является процесс записи в регистр результата. Значения сигналов на первой 1 группе входов блока 12 разрешения записи соответствует информации о равенстве i-х разрядов, так как d ã-® „, где г„- значение 1-го разряда двоичного счетчика 3; („ - значение i ãî разряда шины 2.

Если г„фц„, то удовлетворяется условие ориентирования булевого дифференциала на изменение переменной х . При о =1 (т.е. ориентирован

1 на увеличение) и г„.=О, то входная переменная х„. изменяется от 0 к 1, при этом значение сигнала d„-=1. На основании уравнения (1), опйсывающего работу блока разрешения записи ! при вычислении ориентированного булевого дифференциала по i-й переменной, Ь„=l, и следовательно, а=l, iT.е. результат вычисления записывается в регистр результата. Это производится для всех наборов, где х„=О.

При изменении значения x„ íà "l нарушается условие ориентированности булевого дифференциала и все значения на этих наборах не заносятся в регистр результата.

Устройство работает аналогично в случае вычисления булевых дифференциалов, ориентированных на уменьше«ие.

9 . 940166 10

Предлагаемое устройство позволяет ет более широкие функциональные aosвычислять как неориентированные буле- можности, позволяет автоматиэиоовать вы дифференциалы, так и ориентирован- процесс вычисления булевых дифференцианые булевы дифференциалы, и следова- лов различного вида и сократить трудоемтельно» по сравнению с .известным име- s кость по сравнению с ручными методами, Номер разряда

Значение i-го разряда

--Т ( (0,1) 1 (0,1) (0,1} на шине 2 на шине 13

0 0

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

Источники информации, принятые во внимание при экспертизе

1. Суворов lO.И. нЭффективнйй метод вычисления булевых разностей".-"Автоматика и контрольно-,измерительные приборы", 1975, М 2, с. 7-11.

2. Авторское свидетельство СССР по заявке И 2719919/18-24, кл..G 06 F 7/02, 27.06.79 (прототип).

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

$0 блока разрешения записи соединена с шиной выбора режима, входы элемента И соединены соответственно с выходами элемента НЕРАВНОЗНАЧНОСТЬ и блока разрешения записи, выход элемента И соединен с информационным входом демультиплексора.

2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что блок разрешения записи содержит выходной, элемент И и и функциональных ячеек, состоящих из элемента ИЛИ, элемента

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

940166

I

1 ! !! и !

I !

Составитель А. Чеканов

Т М. Гергель Корректор M.Koc a

9/7 1 Подписное

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

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

Филиал ППП "Патент, г. Ужгород, ул. Проектная,