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

(5) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ . ДИФФЕРЕНЦИАЛОВ

Устройство относится к автомати- ке и вычислительной технике и предназначено для автоматизации процесс вычисления булевых дифференциалов при проектировании средств тестового и аппаратурного контроля комбинационных устройств, при проектировании систем автоматизированного проектирования дискретных устройств В последнее время интенсивно развивается метод булевых дифференциалов (разностей), позволяющий получить аналитическим путем полное множество тестов, обнаруживающих неисправность. Успешное применение булевых дифференциалов сдерживается отсутствием эффективных способов их вычисления и устройств, автоматизир ющих этот процесс CllИзвестно устройство для сравнени чисел, предназначенное для вычисления булевой разности, содержащее шину исходных данных, шину управле ния, шину реаультата, двоичный счетчик, блок элементов И-НЕ, два мультиплексора, демультиплексор, регистр результата, элемент НЕРАВНОЗНАЧНОСТЬ, причем шина исходных данных соединена с информационными входами первого и второго мультиплексоров, выходы счетчика соединены с управляющими входами первого мультиплексора, демультиплексора и с первой группой входов блока элементов И-НЕ, шина управления соединена с второй группой входов блока элементов И-НЕ, выходы которого соединены с управляющими входами второго мультиплексора, выходы первого и второго мультиплексоров соединены с входами элемента НЕРАВНОЗНАЧНОСТЬ выходы демультиплексора соединены с входами регистра результата, выходы которого являются выходами устройства . Недостатками известного устройства являются ограниченные функциональные возможности, так как оно не вычисляет ориентированных булевы дифференциалов, которые широко применяются для решения задач диагностики кратных неисправностей. Цель изобретения - расширение функциональных возможностей устройства за счет вычисления как ориенти рованных, так и неориентированных булевых дифференциалов. Поставленная цель достигается тем, что в устройство для вычисления булевых дифференциалов, содержа щее двоичный счетчик, блок элементо И-НЕ, два мультиплексора, демультиплексор, регистр результата, элемен НЕРАВНОЗНАЧНОСТЬ, причем информацио ные входы первого и второго мультиплексоров соединены с шиной исходных данных, выходы двоичного счетчик соединены с управляющими входами пер вого мультиплексора, демультиплексор и с первой группой входов блока элементов И-НЕ, вторая группа входов блока элементов И-НЕ соединена с шиной переменных, выходы блока элементов И-НЕ соединены с управляющими входами второго мультиплексора, выхо ды первого и второго мультиплексоров соединены с входами элемента НЕРАВНОЗНАЧНОСТЬ, выходы демультиплексора соединены с входами 5 егистра результата,выходы которого соединены с шиной результата, введены блок разрешения записи, шина выбора режима, элемент И, причем выходы бло ка элементов И-НЕ соединены с первой группой входов блока разрешения записи, вторая группа входов блока раз решения записи соединена с шиной выбора режима, входы элемента И соединены с выходами элемента НЕРАВНОЗНАЧНОСТЬ и блока разрешения записи , выход элемента И соединен с инфо мационным входом демультиплексора. Кроме того, блок разрешения записи содержит выходной элемент И и И функциональных ячеек, состоящих из элемента ИЛИ, элемента И и элемента НЕ, причем первые входы элементов И каждой ячейки являются первой группой входов блока разрешения записи, а вторые входы этих элементов И являются второй группой входов блока разрешения записи, первый выход этого элемента соединен с первым входом элемента ИЛИ, второй вход которого подключен через элемент НЕ к соответствующему разряду второй группы входов блока разрешения записи. ВЫХОДЫ элементов ИЛИ являются выходами функциональных ячеек, которые соединены с входами выходного элемента И, выход которого является выходом блока разрешения записи. На фиг. 1 показана функциональная схема устройства для вычисления булевых дифференциалов; на фиг. 2 блок-схема примера конкретной реализации блока разрешения записи. Устройство для вычисления булевых дифференциалов содержит шину 1 исходных данных, шину 2 переменных, двоичный счетчик 3, мультиплексоры k и 5| блок элементов И-НЕ 6, двухвходовый элемент НЕРАВНОЗНАЧНОСТЬ 7, демультиплексор 8, регистр 9 результата, шину 10 результата, элемент И 11, блок 12 разрешения записи и шину 13 выбора режима. Элементы устройства (фиг. 1) соединены следующим образом. Шина 1 исходных данных соединена с информационными входами I мультиплексоров k и S выходы двоичного счетчика 3 соединены с управляющими входами Ц мультиплексора , демультиплексора .8 и с первой группой 1 входов блока 6, шина 2 соединена с второй группой II входов блока элементов И-НЕ 6, выходы которого соединены с.управляющими входами II мультиплексора 5 и первой группой входов I схемы разрешения элемента-НЕРАВНОЗНАЧНОСТЬ 7, входы элемента И 11 соединены с выходами элемента 7 и блока 12, а выход соединен с информационным входом с демультиплексора 8, выходы демультиплексора 8 соединены с входами регистра 9 результата, выход которого соединен с выходной шиной 10 результата, шина 13 соединена с второй II группой входов блока 12 разрешения записи. Двоичный счетчик 3 это узел, обеспечивающий подсчет поступающих на его вход импульсов. В данном устройстве применяется счетчик суммирующего типа. Счетчик может быть выполнен по любой известной схеме. Мультиплексоры k и S предназначены для выбора на основании управляющего кода П соответствующего разряда из информационного двоичного кода I. Блок элементов И-НЕ 6 предназначен для инвертирования соответствующих разрядов двоичного кода, поступающего на первую группу входных выходов I, в соответствии со значением управляющих сигналов, поступающих на вторую группу входных выводов Л по шине переменных. Элемент НЕРАВНОЗНАЧНОСТЬ 7 предназначен для сравнения сигналов, поступающих с выходов мультиплексоров и 5- Демультиплексор 8 предназначен для выдачи информационного сигнала поступающего с выхода элемента И 1 в соответствии со значением управляющего слова, поступающего с двоичного счетчика 3, на соответствующий выходной наружный вывод. Регистр 9 результата предназначен для хранения и накопления зна чений булевой разности. Выходы регистра результата образуют шину 10 результата. Элементы ЗЮ схемы могут быть выполнены и в известном устройстве так как решают аналогичные задачи. Элемент И 11 предназначен для управления прохождением информацио ного сигнала с выхода элемента НЕРАВНОЗНАЧНОСТЬ 7, на информацион ный вход С демультиплексора 8, в зависимости от значения сигнала 0| с выхода блока разрешения записи. Если , то происходит передача значения сигнала с выхода элемента НЕРАВНОЗНАЧНОСТЬ 7 в демультиплексор 8 и последующая запись в регис 9. При запись не производится (т.е. записывается О). Блок 12 разрешения записи имеет две группы по vi входов (I и П) и один выход а и предназначен для формирования сигнала разрешения записи на основании значений сигналов на входных выводах I и II. Обозначим значения сигналов первой группы входов I через d(,n), а второй группы череа bj (j f7n), тогда логическая функция, описываю щая работу схемы разрешения Записи имеет вид и а.А (b-vri.b.) (1) iti 111 Возможная реализация схемы разрешения записи (фиг. 2) состоит из элементов И.12,1 и 12.3, элемента ИЛИ 12.2, элемента НЕ 12.;-промежуточные функциональные ячейки обо начены позицией 12.0. Элементы схем соединены следующим образом. Первые 66 входы 1-ой функциональной ячейки 12.0 соединены с 1-м разрядом первой группы входов t, вторые входы с i-M разрядом второй группы входов TJ, выходы функциональных ячеек соединены с входами элемента И 12.1, выход которого является выходом схемы разрешения записи. Функциональная ячейка 12.0 состоит из элементов ИЛИ 12.2, И 12.3, НЕ 12.1, соединенных следующим образом. Выходы элементу И 12.3 соединены с первым 1 и вторым TJ входом функциональной ячейки, выход элемента И 12.3 соединен с первым входом элемента ИЛИ 12.2, второй Л вход ячейки соединен через элемент НЕ 12. с вторым входом элемента ИЛИ 12.2. Устройство работает следующим образом. Устройство содержит две шины 2 и 13 управления. Значение сигналов на них определяет режим работы устройства. 1. Вычисление неориентированных булевых дифференциалов (булевых разностей) . Значение управляющих сигналов (все разряды) на шине 13 равны О. При этом на выходе блока 12 разрешения записи формируется сигнал 1. причем это значение не зависит от значений сигналов на выходе блока 6 из уравнения (1) и следовательно, сигнал с выхода элемента 7 поступает на информационный вход с демультиплексора 8. Подавая сигнал 1 на .те разряды шины 2 переменных, номера которых соответствуют номерам переменных, по которым необходимо вычислить булевый дифференциал, на шине 10 результата получаем результат. Работа предлагаемого устройства в этом режиме аналогична работе извёстного. По определению булевым дифференциалом (разностью) логической функции F (xj, ..., х„) по переменной называется логическая функция R (Xj, ..., Xj,) вида R(x, ..., х„) F(x, ..., х, ,.., Ху,)фР (х, ..., , ..., х„), т.е. ДЛЯ вычисления функции R(x, ..., Ху,) необходимо вычислить значение функции F на наборе х., , . . . , х, ) и сложить по модулю 2 со значением исходной функции на рассматриваемом наборе. Значения исходной функции на все двоичных наборах входных переменных (таблица истинности функции) подают ся на шину 1 исходных данных. На шину 2 переменных подается п-разрядный двоичный код, несущий информацию о том, по каким переменным вычисляется булевая разность. Если она вычисляется по переменной х, то в i-M разряде двоичного кода будет 1, во всех остальных разрядах - О. Например, для при вы числении булевой разности по переменной х двоичный код имеет вид 10 Двоичный счетчик 3 формирует последовательность двоичных наборов (двоичных слов). Для каждого набора производятся определенные значения исходной функции на данном наборе (на выходе мультиплексора ij), в бло ке элементов И-НЕ 6 на основании уп равляющего кода формируется набор оп ределяется значение исходной функции на этом наборе (на выходе мультипле1 сора 5) Элемент НЕРАВНОЗНАЧНОСТЬ 7 производит сложение по модулю 2 значений функции на наборах х, .... х -/(. Результат Xvi И Xj, ««, X/ у .., Ху. сложения поступает на информационный вход демультиплексора 8 i4 в зависимости от рассматриваемого двоич ного набора (поступающего с двоичного счетчика 3) выдается по соответствующему выводу в регистр результата. После рассмотрения всех 2 набор в регистре результата сформирована булевая разность. Устройство работа аналогично в случае вычисления булевой разности по нескольким переме ным. 2. Вычисление ориентированных бу левых дифференциалов. Булевым дифференциалом, ориентированным на увеличение d i()y,) (умен шение d€Cx ), называется булева функция, равная 1 тогда и только то да, когда fC) изменяется при измен нии из О в 1 (из 1 в 0). Устройство позволяет вычислять булевы дифференциалы, ориентированные как на увеличение, так и на уменьшение. Для этого необходимо задать следующие значения управляющих сигТйловГ а) шина 2 переменных. Значение 1-го разряда равно 1 (или 0), если необходимо вычислить булевый диффе6ренциал, ориентированный на увеличение (на уменьшение) по i-й переменной. Значение разрядов, соответствующих переменным, для которых не нужно вычислять ориентированный булевый дифференциал, может быть произвольным (О или 1), так как исключение этих значений производится в блоке 12. б) Значение i-ro разряда на шине 13 выбора режима равно 1, если по переменной xi необходимо вычислить ориентированный булев дифференциал, и равно О в противном случае. Пример. Необходимо вычислить ориентированный на увеличение булев дифференциал по переменной х. для логической функции от четырех переменных (). Исходные данные представлены в таблице. После подготовки исходных данных и начала работы схема работает аналогично случаю 1. Особенностью является процесс записи в регистр результата. Значения сигналов на первой 1 группе входов блока 12 разрешения записи соответствует информации о равенстве i-x разрядов, так «ак , где г - значение -го разряда двоичного счетчика 3 - значение i-ro разряда шины 2. Если то удовлетворяется условие ориентирования булевого дифференциала на изменение переменной Х-. При (т.е. ориентирован на увеличение) и 0, то входная X изменяется от О к переменная этом значение сигнала . (1), описываюосновании уравнения щёго работу блока разрешения записи при вычислении ориентированного бу левого дифференциала по i-й переменной, , и следовательно, , т.е. результат вычисления записывается в регистр результата. Это производится для всех наборов, где . При изменении значения х- на 1 нарушается условие ориентированности булевого дифференциала и все значения на этих наборах не заносятся в регистр результата. Устройство работает аналогично в случае вычисления булевых дифференциалов, ориентированных на уменьшеПредлагаемое устройство позволяет вычислять как неориентированные булевы дифференциалы, так и ориентированные булевы дифференциалы, и следовательн91 по сравнению с известным имеформула изобретения 1.«Устройство для вычисления булевых дифференциалов, содержащее двоичный счетчик, блок элементов И-Н два мультиплексора, демультиплексор, регистр результата, элемент НЕРАВНОЗНАЧНОСТЬ, причем информационны входы первого и второго мультиплексоров соединены с шиной исходных данных, выходы двоичного счетчика соединены с управляющими входами первого мультиплексора, демультиплексора и с первой группой входов блока элементов И-НЕ, вторая группа входов блока элементов И-НЕ соединен с шиной переменных, выходы блока эле ментов И-НЕ соединены с управляющими входами второго мультиплексора, выходы первого и второго мультиплексоров соединены с входами элемента НЕРАВНОЗНАЧНОСТЬ, выходы демультигшексора соединены с входами регистра результата, выходы которого соединены с шиной результата, о т гличающееся тем, что, с цель расширения функциональных возможностей за счет вычисления ориентированных булевых дифференциалов, оно содержи г блокJpaзpeшeния записи, шину выбора режима,.элемент И, причемвыходы блока элементов И-НЕ соединен с первой группой входов блока разрешения записи, вторая группа входов блока разрешения записи соединена с шиной выбора режима, входы элемента И соединены соответственно с выхо

ет более широкие функциональные возможности, позволяет автоматизировать процесс вычисления булевых дифференциалов различного вида и сократить трудоемкость по сравнению с ручными методами. дами элемента НЕРАВНОЗНАЧНОСТЬ и блока разрешения записи, выход элемента И соединен с информационным входом демультиплексора. 2. Устройство по h. 1, отличающееся тем, что блок разрешения записи содержит выходной элемент И и у| функциональных ячеек, состоящих из элемента ИЛИ, элемента И и элемента НЕ, причем первые входы элементов И каждой ячейки являются первой группой входов блока разрешения записи, а вторые входы этих элементов И являются второй группой входов блока разраиения записи, выход элемента И подключен к первому вхо- ДХ элемента ИЛИ, второй вход которого через элемент НЕ подключен к соответствующему разряду второй группы входов блока разрешения записи, выходы элементов ИЛИ являются выходами функциональных ячеек, которые соединены с входами выходного элемента И, выход которого является выходом блока разрешения записи. Источники информации, принятые во внимание при экспертизе 1. Суворов Ю.И. Эффективный метод вычисления булевых разностей.-Автоматика и контрольно-измерительные приборы, 1975, № 2, с. 7-11. 2. Авторское свидетельство СССР по заявке ff 2719919/18-2 4, кл. G Об F 7/02, 27.06.79 (прототип).

«SI