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

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

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

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

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

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

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

При этом уровень логического нуля на одном или нескольких выходах поля номеров аргументов блока 7 памяти .свидетельствует о том, что данные аргументы входят в вычислительную конъО1

о

00

10

31508

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

Если булева функция представлена в КНФ, то ее вычисление осуществляется следующим образом.

Сигнал кода операции (уровень логи ческого нуля) поступает из блока 7 памяти.на управляющий вход мультиплексора 4, что обеспечивает передачу информации с RS-триггера 5 через мультиплексор 4 на выход 13 устройства. Сигнал кода начальной установки формирует на выходе RS-триггера 5 сигнал высокого уровня (логическая единица). На вторую группу входов функционального преобразователя 1 с блока. 7 памяти подается код поля номеров аргументов, и происходит вычисление дизъюнкции. Функциональный преобразователь 1 формирует сигнал логического нуля на первом выхо- де, если хотя бы одно из слагаемых дизъюнкции принимает значение логич ес кой единицы.

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

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

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

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

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

Термы с первого по восьмой предназначены для вычисления конъюнкций, а термы с девятого по шестнадцатый для вычисления дизъюнкции.

В табл.2 представлена программа вычисления двух булевых функций у1 и у2:

у1 xlx2x3x4x5Vxlx4x7Vx2x4x8;

у2 (xlVx2Vx3)&(x4Vx5Vx6)&(x7Vx8

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

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

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

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

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

элемента И, два RS-триггера, мультиплексор, счетчик, блок памяти и фор- мирователь импульсов, причем тактовый вход устройства соединен с входом- формирователя импульсов и счетньм входом счетчика, вход обнуления которого соединен с установочным входом устройства, выход счетчика соединен с адресным входом блока памяти, вход стробирования которого соединен с первым выходом формирователя импульсов выход первого элемента И соединен с входом установки в О первого RS- триггера, вход установки в 1 вто- рого RS-триггера соединен с выходом второго элемента И,.отличающее с я тем, что, с целью повышения быстродействия определения значений булевых функций за счет парал- лельной обработки аргументов, входящих в дизъюнкции или конъюнкции булевых функций, представленных в дизъ- ЮНКТД1ВНОЙ нормальной .форме или конь- юнктивной нормальной форме, оно со- держит функциональньй преобразователь, причем информационные входы устройства соединены с первой группой входов функционального преобразователя, вторая группа входов которого соединена с выходом поля номеров аргументов блока памяти , выход вычисления дизъюнкции функционального преобразователя соединен с первым входом первого элемента И, выход вычисления конъюнкции функционального преобразователя соединен с первым входом второго элемента И, вторые входы первого и второго элементов И соединены с вторым выходом формирователя импульсов, выход начальной установки блока памяти соединен с входом установки в 1 первого RS-триггера и с входом установки в О второго RS- триггера, выход кода операции блока памяти соединен с управляющим входом мультиплексора, первый и второй информационные входы которого соединены соответственно с выходом первого и второго RS-триггеров, а выход является выходом устройства.

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

Примечание.Х- безразличное состояние; О - уровень

логического.нуля; 1 - уровень логической единицы; А - активт ш уровень; - - неактивньй уровень.

Таблица 1

Таблица 2