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

 

Изобретение относится к цифровой вычислительной технике и может быть использовано для вычисления булевых функций в системах контроля и управления. Цель изобретения - повышение быстродействия определения значений булевых функций за счет параллельного вычисления аргументов, входящих в конъюнкции или дизъюнкции булевых функций, представленных в дизъюнктивной нормальной форме (ДНФ) или конъюнктивной нормальной форме (КНФ). Устройство для определения значений булевых функций содержит два элемента И, два RS - триггера, формирователь импульсов, мультиплексор, генератор импульсов, счетчик, блок памяти и функциональный преобразователь. Результат вычисления конъюнкции или дизъюнкции с выходов функционального преобразователя через элементы И и соответствующий RS - триггер в зависимости от формы представления булевой функции поступает на выход устройства. 1 ил., 2 табл.

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

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

РЕСПУБЛИК д11 4 С 06 F 7/00

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4351869/24-24 (22) 29.12.87 (46) 15.09,89. Бюл, ¹ 34 (72) Ф.С.Соснин и С.M,Øåñòèìåðîâ (53) 681.3(088.8) (56) Авторское свидетельство СССР

¹- 1444744, кл. G 06 F 7/00, 19,04,87, Авторское свидетельство. СССР

¹ 1315965, кл. G 06 F 7/00, 1985, (54) УСТРОЙСТВО ДПЯ ОПРЕДЕЛЕНИЯ ЗНАЧЕНИЙ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к цифровой вычислительной технике и может быть использовано для вычисления булевых функций в системах. контроля и управления. Цель изобретения — повышение быстродействия определения значений

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

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

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

10 импульсов, установочный вход 11 устройства, информационный вход 12 устройства и выход 13 устройства, 2 булевых функций за счет параллельного вычисления аргументов, входящих в конъюнкции или дизъюнкции булевых функций, представленных в дизъюнктивной нормальной форме или конъюнктивной нормальной форме. Устройство для определения значений булевых функций содержит два элемента И, два RS-триггера, формирователь импульсов, мультиплексор, генератор импульсов, счетчик, блок памяти и функциональный преобразователь. Результат вычисления конъюнкции или дизъюнкции с выходов функционального преобразователя. через элементы И и соответствующий

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

При подаче на установочный вход

11 устройства уровня логической единицы происходит начальная установка устройства, На выходе блока 7 памяти в зависимости от информации на адресных входах по значению счетчика 8 Формируется управляющее слово. В каждом слове блока 7 памяти записана следующая информация: код поля номеров аргументов; код начальной установки; код операции.

При этом уровень логического нуля на одном или нескольких выходах поля номеров аргументов блока 7 памяти .свидетельствует о том, что данные аргументы входят в вычислительную конь3 150820 юнкцию или диэъюнкцию» Значение кода операции определяет вычисление булевых функций, представленных в дизъюнктивной нормальной форме (ДНФ) или в конъюнктивной нормальной форме (КНФ), Если булева функция представлена в КНФ, то ее вычисление осуществляется следующим образом, Сигнал кода операции (уровень логи-10 ческого нуля) поступает из блока 7 памяти.на управляющий вход мультиплексора 4, что обеспечивает передачу информации с RS-триггера 5 через мультиплексор 4 на выход 13 устройст- 15 ва, Сигнал кода начальной установки формирует на выходе RS-триггера 5 сигнал высокого уровня (логическая единица). На вторую группу входов функционального преобразователя 1 20 с блока. 7 памяти подается код поля номеров аргументов, и происходит вычисление дизъюнкции. Функциональный преобразователь 1 формирует сигнал логического нуля на первом выходе, если хотя бы одно из слагаемых дизъюнкции принимает значение логической единицы.

Сформированное значение с первого выхода функционального преобразова-. 30 теля 1 поступает на первый вход элемента И 2 (на второй вход которого поступает стробирующий сигнал с второго выхода формирователя 9 импуль» сов), и RS-триггер 5 сохраняет значе- 35 ние логической единицы, Данная операция повторяется столько раз, сколько в вычисляемую функцию входит дизъюнкций. Результат вычисления булевой функции формируется на выходе RS-триг 40 гера 5 и через мультиплексор 4 поступает на выход 13 устройства, Вычисление булевых функций, представленных в ДНФ, осуществляется следующим образом. 45

Сигнал кода операции (уровень логической единицы) поступает с блока 7 памяти на управляющий вход мультиплексора 4, в результате чего выход

RS-триггера 6 подключается через мультиплексор 4 к выходу 13 устройства.

Сигнал кода начальной установки формирует на выходе RS-триггера 6 сиг-. нал низкого уровня, На вторую группу входов функционального преобразователя 1 с блока 7 памяти подается код поля номеров аргументов, и происходит вычисление конъюнкции, Функциональный преобразователь 1. формиру4 4 ет на своем втором выходе сигнал логического нуля, если хотя бы один из сомножителей конъюнкции ранен нулю, полученное значение поступает на первый вход элемента И 3 RS-триггер 6

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

В качестве примера в табл,1 приведены термы функционального преобразователя 1 для вычисления значений булевых функций (для восьми аргументов), представленных в ДНФ и КНФ.

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

yl = х1х2х3х4х5Чх1х4х7Чх2х4х8; у2 = (xl Vx2Vx3)g< (x4Vx5Vx6)g (x7Vx8)

По нулевому коду счетчика 8, т,е. до начала вычислений, из блока 7 памяти выбирается слово О, при этом единичный сигнал с выхода начальной установки блока 7 памяти поступает на S-вход RS-триггера 5 и íà R-вход

RS-триггера 6 и устанавливает эти триггеры соответственно в единичное и нулевое состояния.

Командами, записанными в словах

1-3, осуществляются вычисления соответственно первой, второй и третьей конъюнкций функции yl и результат вычисления функции yl с выхода RSтриггера 5 через мультиплексор 4 поступает на выход 13 устройства, По команде, записанной н слое 4, происходит установка RS-триггеров 5 и 6 соответственно н нулевое и едйничное состояния, выход RS-триггера

6 через мультиплексор 4 подключается к выходу 13 устройства, Командами, записанными в словах

5-7 осуществляется вычисление соот-ветствующих дизъюнкций функции у2, и результат вычисления функции у2 с выхода RS-триггера 6 через мультиплексор 4 поступает на выход )3 устройства.

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

Устройство для определения значений булевых функций, содержащее дна

4 6 тель, причем информационные входы устройства соединены с первой группой входов функционального преобразователя, вторая группа входов которого соединена с выходом поля номеров аргументов блока памяти, выход вычисления дизъюнкции функционального преобразователя соединен с первым входом первого элемента И, выход вычисления конъюнкции функционального преобразователя соединен с первым входом второго элемента И, вторые входы первого H второго элементов И соединены с вторым выходом формирователя импульсов, выход начальной установки блока памяти соединен с входом установки в "1" первого КБ-триггера и с входом установки в "0 второго RSтриггера, выход кода операции блока памяти соединен с управляющим входом мультиплексора, первый и второй информационные входы которого соединены соответственно с выходом первого и второго RS-триггеров, а выход является выходом устройства.

5 150820 элемента И, два RS-триггера, мультиплексор, счетчик, блок памяти и фор- мирователь импульсов, причем тактовый вход устройства соединен с входом. формирователя импульсов и счетным входом счетчика, вход обнуления которого соединен с установочным входом устройства, выход счетчика соединен с адресным входом блока памяти, вход .10 стробирования которого соединен с первым выходом формирователя импульсов, выход первого элемента И соединен с входом установки в "0" первого RS триггера, вход установки в "1" вто- !5 рого RS-триггера соединен с выходом второго элемента И,.о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия определения значений булевых функций за счет парал- 20 .лельной обработки аргументов, входящих в дизъюнкции или конъюнкции булевых функций, представленных в дизьюнкт1ивной нормальной форме.или коньюнктивной нормальной форме, оно со- 25 держит функциональный преобразоваТаб лица 1

Терм Первая группа входов Вторая группа входов Выходы х1 х2 хЗ х4 х5 х6 х7 x8 al а2 аЗ а4 а5 аб а1 а2 а7 а8

Х 0 Х Х

Х Х 0 Х

Х Х Х 0

Х Х Х Х

Х Х Х Х

Х Х Х Х

Х Х Х Х

О Х Х Х

Х 0 Х Х

Х Х 0 Х

Х Х Х 0

Х Х Х Х

ХХХ.Х

Х Х Х Х

Х Х Х Х

Х Х Х Х

А

А

А

А

А

А

А

П р и м е ч а н и е. Х вЂ” безразличное состояние; 0 — уровень логического. нуля; I — уровень логической единицы; А - активный уровень; неактивный уровень, 1 0 Х Х Х X

2 X 0 Х Х Х

3 Х Х 0 X Х

4 Х Х Х 0 Х

5 Х Х Х Х 0

6 Х Х Х Х Х

7 Х Х Х К Х

8 Х Х Х Х Х

9 Х Х Х Х Х

10 Х Х Х Х Х

11 Х Х Х Х Х

12 Х Х Х X Х

13 Х Х X Х Х

14 Х Х Х Х Х

15 Х Х Х Х Х

16 Х Х Х Х .Х

Х Х

Х Х

Х Х

Х Х

Х Х

0 Х

Х 0

Х Х

Х Х

Х Х

Х Х

Х Х

Х Х

Х Х

Х X

Х Х

Х Х Х

Х X Х

Х Х Х

0 Х Х

Х 0 Х

Х Х 0

Х Х Х

X Х Х

Х Х Х

Х Х Х

Х Х Х

0 Х Х

Х 0 Х

Х Х О

X X Х

Х Х Х

Х Х

Х Х

Х Х

Х Х

Х Х

Х Х

0 Х

Х 0

Х Х

Х Х

Х Х

X Х

Х Х

Х Х

0 Х

Х 0

1508204

Т а б л и ц а 2

Код поля номеров аргументов

Код операции

Слово

Код начальной установки

Составитель В,Сорокин

Рецактор А.Огар Техред Д.Олийнык

Корректор Н.Борисова

Заказ 5541/50 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101

0 Х Х Х

1 0 0 0

2 .0 1 1

3 1 0 1

4 Х Х Х

5 0 0 0

6 1 1 1

7 1 1 1

Х Х Х Х

0 0 ) 1

0 1 1 0

О 1 1 1

Х Х Х Х

1 1 1 1

0 0 0 1

1 1.1 0

Х 1

1 0

1 0

0 0

Х 1

1 0

1 0

0 0

1

1

0