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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (51)4 С 06 Р 7/04

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 3884 705/24-24 .(22) 17.04.85 (46) 15.12 ° 86. Бюл, ¹ 46 (71) Харьковский ордена Ленина авиационный институт им, Н, Е, Жуковского (72) В, А. Дергачев, С. А. Губка, B. А. Балалаев и А, А, Жалило (53) 681 ° 3(088 ° 8) (56) Авторское свидетельство СССР № 1103221, кл. G 06 F 7/04, 1983.

Авторское свидетельство СССР № 780003, кл. С 06 F 7/04, 1978. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

БУЛЕВЫХ ПРОИЗВОДНЫХ (57) Изобретение относится к области автоматики и вычислительной техники и предназначено для автомати-. зации процесса вычисления булевых производных ° Цель изобретения — повышение быстродействия устройства, Устройство содержит входы значений булевой фракции, входы номеров переменных, по которым вычисляется булева производная, блок формирования на„„SU„, 1277089 А1 боров, два мультиплексора, группу элементов НЕРАВНОЗНАЧНОСТЬ, элемент

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

3 12

Изобретение относится к автоматике и вычислительной технике и предназначено для автоматизации процесса вычисления булевых производных (синонимы: булева разность, булев дифференциал) при проектировании средств тестового контроля и аппаратурного контроля комбинационных схем, Цель изобретения — повышение быстродействия устройства, На фиг., 1 изображена блок-схема устройства для вычисления булевых производных", на фиг. 2 — блок-схема бло-, ка формирования наборов; на фиг ° 3— блок-схема настраиваемой логическ.й ячейки.

Устройство содержит входы 1 значений булевой функции, входы 2 номеров переменных, по которым вычисляется булева производная, блок 3 формирования наборов, мультиплексоры 4 и 5, группу 6 „ -6 элементов

НЕРАВНОЗНАЧНОСТЬ, элемент НЕРАВНОЗНАЧНОСТЬ 7, демультиплексоры 8 и

9, элементы ИЛИ 10> -10,„, триггеры и

11, — 11, выходы 12 значений булевых производных, Блок 3 формирования наборов содержит элемент И 13 триггер 14, генератор 15 импульсов, управляющий вход 16, выходы 17 блока формирования набора, настраиваемые логические ячейки 18 -18, Настраип ваемая логическая ячейка 18 содержит элементы И 19 и 20, элемент

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

Все элементы схемы являются стандартными и могут быть выполнены по любой известной схеме, Рассмотрим назначение и состав элементов схемы, Входы 1 значений булевой функции имеют 2 разрядов. Значения исН ходной булевой функции на всех двоичных наборах входных переменных (таблица истинности булевой функции) подаются на соответствующие разряды входов 1, причем значение булевой функции на i-м наборе подается íà (i+1)-й разряд входов l (1=0,20-1 ), На входы 2 номеров переменных, по которым вычисляется булевая производная, подается п-разрядный двоичный код, несущий информацию о том, по каким переменным вычисляется булева производная, Если она вычисляется по переменной х;, то i-й

77089

10 !

55 разряд двоичного кода принимает значение "l, иначе — "0"

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

Настраиваемая логическая ячейка

l8 (фиг, 3) в зависимости от значения сигнала на входе 25 ячейки может работать в двух режимах: при сигнале "1" на входе 25 на выходе

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

27 ячейки (при ртом на выходе 26 ячейки формируется сигнал "0") либо работает как триггер со счетным входом, значение сигнала с выхода которого поступает на выходы 26 и 27 ячейки, Блок 3 формирования наборов работает следующим образом, В исходном состоянии триггер 14 находится в состоянии "1", а триггеры 22 — в состоянии "0", На управляющий вход 16 подается сигнал

"1", при.этом открывается элемент

И 13 и импульсы с выхода генератора

15 импульсов поступают на первый вход настраиваемой логической ячейки

18 „, Если сигнал на втором входе (поз. 25 на фиг. 3) этой ячейки—

"1", то ячейка передает свой первый выход (и, следовательно, на первый вход ячейки 18 ) импульсы с выхода элемента И 13, а на своем втором выходе "0". Если сигнал на втором входе ячейки 18, равен "0", то ячейка работает как счетный триггер, значения которого поступают на первый вход следующей ячейки 18 и на второй выход ячейки. Аналогично работают все настраиваемые ячейки, При появлении на первом выходе ячейки 18 „сигнала "1" сбрасывается триггер 14 в состояние "0", при этом закрывается элемент И 13 и импульсы с выхода генератора 15 импульсов не проходят на вход элемента И 13, Это свидетельствует о том, что все необЭО з 2770 ходимые двоичные наборы сформированы и получен результат, сформированный

В триггерах 11 11

Рассмотрим работу блока 3 формирования наборов на конкретном приме5 ре. Пусть n=4, и булеву производную необходимо вычислить по переменной. х . На входы 2 значений переменных, по которым вычисляется;булева .производная, подаем код 0100 (нумерация разрядов с начала кода),. При этом на выходах 17 блока 3 формирования наборов будет сформирована последовательность двоичных наборов: 0000;

0001 Оlооз 0)01 10003 10011 1100

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

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

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

0...01 — на второй и т.д.), На входы триггеров 11>-11 „ сиг- 4О нал "1" проходит через соответствующие элементы ИЛИ 10 -10 в завит симости от значения сигналов на выходах мультиплексоров, В исходном состоянии триггеры 11 — 11 и находят-.

1 ся в состоянии 0...0, Устройство работает следующим образом.

Значение булевой функции (таблица истинности) подается на входы 1 значений булевой функции, На входы

2 номеров переменных, по которым вычисляется производная, подается иразрядный двоичный код, i-й разряд которого равен "1", если вычисляется булева производная по переменной х, После подачи на управляющий вход 16 сигнала "1" блок 3 формиро8(j 4 вания наборов формирует 2 наборов при вычислении булевой производной по переменной следующего вида: х ... х. 0 х ... х, (1) где х . означает что -я переменная

J р принимает значение или "О" или I

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

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

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

ИЛИ 10, -10 поступают на входы, h триггеров II,-II n и переводят кх в состояние "1". По окончании всех тактов на выходах 12 значений булевой производной сформирован результат, причем значение булевой производной на i-м наборе находится ва (з+П-м разряде выходов 12 (>,О 2 з-1 )

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

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

Т а б л и ц а 1

0 0 1

1 О

1 1

0 О

0 1

1 О

1 1

1277089

Таблица 2

Блок

3 4 6 5 7 8

9 10 11

000 0 010 0 0 00000000 00000000 00000000 00000000

001 1 011 l 0 00000000 00000000 00000000 00000000

100 1 110 1 0 00000000 00000000 00000000 00000000

101 1 111 О 1 00001000 00000001 00001001 00001001

Пусть п=З и булену производную необходимо вычислить по переменной х, На входы 1 значений булевой функцйи подаем в соответствии с таблицей истинности значения разрядов 01011110. На входы 2 значений номеров переменных, по которым выПо окончании всех четырех тактов на выходах 12 значений булевой производной сформирована булева производная, принимающая значения на соответствующих наборах: 00001001.

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

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

40 входы задания номеров переменных первой группы устройства соединены с первыми входами элементов НЕРАВНОЗНАЧНОСТЬ группы, выходы которых

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

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

----9

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

i-й логической настраиваемой ячейки

17

Фиг. Z

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

2. Устройство по п, l о т л и— ч а ю щ е е с я тем, что настраиваемые логические ячейки содержат триггер, первый и второй элементы

И, элемент НЕ и элемент ИЛИ, причем

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

1277089

27

Фиг. 5

Составитель О, Березикова а Корректор И, Пилипенко

Редактор Е, Копча Техред В. Кадар

Заказ 6666/41 Тираж 671

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

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

4/5

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