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

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

Цель изобретения повышение быс .тродействия устройства.

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

Устройство содержит входы 1 значений булевой функции, входы 2 номеров переменных, по которым вычисляется булева производная, блок 3 формирования наборов, мультиплексоры 4 и 5, группу 6 -6 элементов НЕРАВНОЗНАЧНОСТЬ, элемент НЕРАВНОЗНАЧНОСТЬ 7, демультиплексоры 8 и 9, элементы ИЛИ 10, триггеры 11 -11„п, выходы 12 значений булевых производных. Блок 3 формировани наборов содержит элемент И 13, триггер 14, генератор 15 импульсов, управляющий вход 16, выходы 17 блока формирования набора, настраиваемые

Настраи- содержит элементы И 19 и 20, элемент НЕ 21, триггер 22 со счетным входом элемент ИЛИ 23, входы 24 и 25, выходы 26 и 27.

Все элементы схемы являются стан дартнъ1ми и могут быть выполнены по любой известной схеме.

Рассмотрим назначение и состав элементов схемы.

Входы 1 значений булевой функции имеют 2 разрядов. Значения исходной булевой функции на всех двоичных наборах входных переме1шых .(таблица истинности булевой функции) подаются на соответствувэщие разряды входов 1, причем значение булевой функции на i-м наборе.пода- ется на (i+1)-й разряд входов 1 (, ).

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

логические ячейки ваемая логическая ячейка 18

разряд двоичного кода принимает значение

Ч, иначе - О.

0

Блок 3 формирования наборов предназначен для формирования .наборов

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

Настраиваемая логическая ячейка 18 (фиг. 3) в зависимости от значения сигнала на входе 25 ячейки может работать в двух режимах: при сигнале на входе 25 на выходе 26 формируется сигнал О, а на вы- . ход 27 проходит сигнал с входа 24

S ячейки; при сигнале О на входе 25 элемент И 19 закрывается, а элемент И 20 открывается, при этом на выходы 26 и 27 ячейки поступает сигнал с выхода триггера 22 со счетным входом, т.е. в зависимости от значения сигнала на входе 25 (1 или О) настраиваемая логическая ячейка 18 соединяет вход 24 и выход ,27 ячейки (при этом на выходе 26

5 ячейки формируется сигнал О) либо работает как триггер со счетным входом, значение сигнала с выхода которого поступает на выходы 26 и 27 ячейки.

д Блок 3 формирования наборов ра- б.отает следующим образом.

В исходном состоянии триггер 14 находится в состоянии 1, а триггеры 22 - в состоянии О. На управляющий вход 16 подается сигнал 1, при-этом открывается элемент И 13 и иютульсы С: выхода генератора 15 импульсов поступают на первый вход настраиваемой логической ячейки 18.,, Если сигнал на втором входе (поз, 25 на фиг. 3) этой ячейки - 1, то ячейка передает свой первый выход (и, следовательно, на первый вход ячейки 18 импульсы с выхода элемента 13, а на своем втором выходе О. Если сигнал на втором входе ячейки 18 , равен О, то ячейка работает как счетный триггер, значения которого поступают на первый вход следующей ячейки 1 8 и на второй выход ячейки. Аналогично работают все настраиваемые ячейки. При появлении на первом выходе ячейки 1 8 сигнала 1 сбрасывается триггер 14 в состояние О, при этом закрывается элемент И 13 и импульсы с выхода генератора 15 импульсов не проходят на вход элемента И 13. Это свидетельствует о том, что все необ5

0

S

0

ходимые двоичные наборы сформированы и получен результат, сформированный в триггерах 11 -Пхь .

Рассмотрим работу блока 3 формирования наборов на конкретном примере. Пусть , и булеву производную необходимо вычислить по переменной. Xj, На входы 2 значений переменных, по которым вычисляется ,булева производная, подаем код 0100 (нумерация разрядов с начала кода),. При этом на выходах 17 блока 3 формирования наборов будет сформирована последовательность двоичных наборов: 0000; 0001; 0100; 0101; 1000-; 1001; 1100; 1101, т.е. настраиваемая ячейка 18. формирует сигнал О во втором (справа) разряде на всех наборах.

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

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

Демультиплексоры 8 и 9 работают как обычгаш коммутаторы и передают значение сигнала на информационном входе на соответствующий выход демультиплексора в зависимости от значения управляющего слова, поступающего на управляющие входы демуль- типлексоров (при значении управляющего слова О,,.00 - на первый выход О,,,01 - на второй и т.д.).

На входы триггеров п сигнал 1 проходит через соответствующие элементы ИЛИ 10 -10, в зависимости от значения сигналов на выходах мультиплексоров. В исходном

состоянии триггеры I 1 -1 L находятся в состоянии 0...0.

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

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

вход

16

сигнала 1 блок 3 формирования наборов формирует 2 наборов при вычислении булевой производной по переменной следующего вида:

X. Ох. , I -i -i-t-t

(1)

где X. означает, чтоj -я переменная

принимает или I,

значение или О

fO

На выходах группы 6 элементов НЕРАВНОЗНАЧНОСТЬ формируются наборы

вида

л,

X,

Xт-1

1 X.

,- .i . (2)

На выходах мультиплексоров 4 и 5 формируются значения исходной булевой функции соответственно на наборах вида (1)и (2). Элемент НЕРАВНОЗНАЧНОСТЬ 7 производит сравнение значений булевой функции на наборах (I) и (2), С выхода элемента НЕРАВНОЗНАЧНОСТЬ 7 сигнал поступает на информационный вход демультиплексоров 8 и 9, на управляющие входы которых поступают отправляющие (адресные) коды соответ- :твенно вида (I) к (2). На выходах демультиплексоров 8 и 9 формируются унитарные коды, значения I в которых через соответствующие элементы ИЛИ lOj 10 поступают на входа , . триггеров П, и переводят их в состояние 1. По окончании всех тактов на выходах 12 значений булевой производной сформирован результат, причем значение булевой произво дной на i-м наборе находится на (i+l)-м разряде выходов 12 (,).

Рассмотрим работу устройства на конкретном примере,

В табл, 1 приведена таблица истинности булевой функции,

Таблица 1

45

50

55

512770896

Пусть и булеву производную числяется булева производная, по- необходимо вычислить по перемен- даем код 010, так как булевая произной Xg, На входы 1 значений булевой функции подаем в соответствии с таблицей истинности значения разря- дов 01011110, На входы 2 значений номеров переменных, по которым выЗиГбГ517 8 Г 9 |lO Т 11

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

Таким образом, предлагаемое устройство решает задачу вычисления буо 1

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

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

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

водная вычисляется по переменной х ,

В табл, 2 приведены значения сигналов на выходах элементов схемы для всех тактов.

Таблица 2

25

30

35

40

45

50

55

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

7

соединен с первым входом (1+1)-й логической настраиваемой ячейки (, п-1), j-й информационный вход блока формирования наборов соединен с вторым входом j-й логической настраиваемой ячейки, второй выход которой соединен с j-м выходом блока формирования наборов (, п).

2. Устройство по п. 1, о т л и - чающееся тем, что настраиваемые логические ячейки содержат триггер, первый и второй элементы И, элемент НЕ и элемент РШИ, причем

17

770898

первый вход ячейки соединен с входом триггера и первым входом первого элемента И, второй вход тсоторого соединен с вторым входом ячейки и J входом элемента НЕ, выход которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом триггера, выходы первого и второго элементов И сое- 10 динены с первым и вторым входами элемента ИЛИ, выход которого является первым выходом ячейки, второй выход которой соединен с выходом второго элемента И,

Фиг.2

W2.J

Редактор Е. Копча

Составитель О, Березикова

Техред В.Кадар Корректор Л. Пилипенко

Заказ 6666/41 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35,.Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4

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