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

Ё

Изобретение относится к цифровой вычислительной технике и может быть использовано для вычисления булевых функций в системах контроля и управления. Целью изобретения является повышение производительности. Устройство содержит счетчик, к блоков памяти, К функциональных преобразователей, два триггера, девять элементов И, формирователь импульсов, генератор импульсов, три элемента ИЛИ, элемент ИЛИ-НЕ и элемент И. 2 ил.

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

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

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

Устройство для определения значений булевых функций содержит (фиг. 1) группу 1 функциональных преобразователей, первый, шестой элементы И 2, 3, элемент ИЛИ- НЕ 4, первый и второй триггеры 5, 6, группу блоков памяти 7, счетчик 8, формирователь 9 импульсов, генератор 10 импульсов, восьмой, девятый, третий, седьмой, четвертый, пятый, второй элементы И 11-17, элемент НЕ 18, второй, третий, первый элементы ИЛИ 19-21, установочный вход 22, вход 23 запуска, информационные входы 24, информационный выход 25, выход 26 признака окончания вычислений, выходы 27 блоков 7, выход 28 вычисления конъюнкции, выходы 29 вычисления дизъюнкции, выход 30 признака кода операции.

Функциональный преобразователь 1 (фиг. 2) содержит группу элементов НЕ 31, группу элементов И 32, первую, вторую группу 33 элементов И, группу 34 элементов ИЛИ-НЕ, первую и вторую группы 35 и 36 элементов ИЛИ, элемент ИЛИ 37 и элемент И 38.

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

В исходном состоянии триггер 6 сброшен и запрещает работу генератора 10; на выходе 26 - нулевой потенциал, фиксирующий отсутствие момента конца вычисления. На выходе 25 - потенциал, соответствующий результату предыдущей операции. Состояние счетчика 8 безразлично.

00

о ел

N О Ю

В блоки памяти 7 информация заносится до начала вычисления булевых функций: в каждой ячейке блока 7 записано управляющее слово следующего формата: код поля номеров, причем для каждого номера аргумента в управляющем слове зарезервировано два бита - для самого аргумента и для его инверсии; для i-ro аргумента соответственно - 271 и 27i2. При этом, если в некотором терме участвует сам аргумент, сочетание сигналов на выходах 27 равно 10, если - инверсия аргумента - если ни аргумент, ни его инверсия не участвуют в терме, - 00.

Булевы функции в устройстве вычисляются либо на основе дизъюнктивной нормальной формы (ДНФ), либо на основе конъюнктивной нормальной формы (КНФ). Каждый терм (тип задания функции определяется дополнительным сигналом с выхода 30 первого блока памяти; для ДНФ - 1, для КНФ - О (вычисляется из значений аргументов на входе 24 устройства и поля номеров аргументов соответствующего блока памяти по данному адресу - функциональным преобразователем, связанным с данным блоком памяти. Пусть число аргументов в некоторой функции равно N. Пусть число блоков памяти 7 равно К. Пусть также максимальное число термов в некоторой функции равно М. Если М К, очевидно, не все ячейки соответствующего адреса, задаваемого счетчиком 8, будут заняты термами и вычисление функции производится за один такт работы. Если же М К, то вычисление функции требует более одного такта работы; назовем значение функции после некоторого (не последнего) такта частичной ДНФ (КНФ)-сокращенно: ЧДНФ (ЧКНФ). В свободные, не используемые ячейки блоков памяти достаточно для корректной работы записать любые уже использованные в данной функции термы. Еще одно условие корректного заполнения ячеек памяти - после исчерпания термой некоторой функции по следующему адресу во все блоки памяти записываются нулевые значения в поля номеров аргументов.

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

Перед началом работы непосредственно на входы 24 подаются значения аргументов, а на входы 22 - начальный адрес, по которому в блоках памяти записаны управляющие слова данной функции. Изменяя начальный адрес, можно вычислять требуемое значение необходимого пользователю количества различных булевых функций.

Положительный короткий сигнал, подаваемый на вход 23 запуска устройства, инициирует начало работы: записывает в счетчик 8 код начального адреса требуемой

функции, устанавливает триггер 6 в единичное состояние. Адрес с выхода блока 8 поступает на адресные входы блоков памяти, на выходах которых (поля номеров аргументов) формируются управляющие сигналы в

0 функциональные преобразователи 1. На дополнительном выходе 30 блока памяти 71 формируется сигнал типа операции; этот сигнал - один и тот же для всех последовательных ячеек блока 71 для данной булевой

5 функции.

Пусть М Ж (более общий случай). Пусть функция должна быть также представлена в виде ДНФ.

В этом случае единичный сигнал с выхо0 да 30 открывает элементы И 2, 11 и 13. Элементы И 3, 12 и 14 - в закрытом состоянии.

Под управлением разрешающего сигнала с триггера 6 генератор 10 формирует так5 товые импульсы. Первый импульс поступает на элементы И 2 и 3 и устанавливает триггер 5 в начальное состояние: (для нашего примера - ДНФ - в нулевое состояние). Импульс поступает и на элемент И 16,

0 осуществляя опрос состояния элемента ИЛИ-НЕ 4. В первом такте работы хотя бы один терм - ненулевой (иначе - пустая булева функция). На выходе элемента ИЛИ-НЕ - нулевой сигнал, следовательно, сигнал на

5 выходе элемента И 16 не формируется.

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

0 формирователя 9 проходит на тактовых вход триггера 5 и записывает в него значение ЧДНФ (по первым К термам), сформированное на выходе элемента 20 ИЛИ.

Частичная (или полная - при М К)

5 ДНФ формируется в блоках 1 следующим образом:

На входы 24 функционального преобразователя (фиг. 2) поступают значения аргументов - в прямом виде - на элементы И 32

0 и в инверсном виде - на элементы И 33. Сигналы на входах 37 коммутируют на выходы элементов И 32 и 33 соответствующие значения аргумента, которые подвергаются операции дизъюнкции на элементе ИЛИ 35.

5 На элементе ИЛИ 37 формируется внутренняя дизъюнкция данного (для конкретного блока 1) терма при реализации функции в виде КНФ путем логического ИЛИ выбранных значений аргументов. На элементе И 38 формируется внутренняя конъюнкция терма по тем же аргументам при реализации выходной функции в виде КНФ. Если некоторый аргумент не участвует в данной терме, нулевой сигнал на выходе элемента 35 не влияет на корректность работы эле-, мента ИЛИ 37, но, чтобы сохранить корректность для элемента И 38, используются элементы ИЛИ-НЕ 34 и ИЛИ 36, которые в случае нулевых значений сигнала на обоих входах 27 формируют для данного аргумента на соответствующем входе элемента 38 единичный сигнал.

На элементах ИЛИ 19 и И 12 формируются соответственно частичные ДНФ и КНФ требуемой булевой функции/Для рассматриваемого примера значение ЧДНФ коммутируется через элементы И 11 и ИЛИ 20 на информационный вход триггера 5 и записывается в него импульсом с первого выхода формирователя 9. Импульс с второго выхода блока 9 инкрементирует содержимое счетчика 8, задающего для данной функции следующие адреса, и подает сигнал опроса на элементы И 13 и 14. Опрос осуществляется со следующей целью: если реализуется ДНФ и ЧДНФ, устанавливает триггер 5 в единичное состояние, дальнейшее вычисление функции не имеет значения, так как ее значение заведомо единичное. Аналогично, при КНФ можно прекратить дальнейшее вычисление, если ЧДНФ устанавливает триггер 5 в О. Итак, если триггер устанавливается при вычислении ДНФ в единичное состояние, по сигналу с второго выхода формирователя 9 срабатывает элемент И 13 и сигнал через элемент ИЛИ 21 поступает на выход 26 устройства, сигнализируя об окончании процесса вычисления функции, а также на вход сброса триггера 6, с прямого выхода которого после этого снимается разрешающий сигнал на генератор 10 и вычисление прекращается. Аналогично при КНФ срабатывает элемент И 14 и дальнейший процесс аналогичен.

Если в промежуточном такте не сформировался сигнал об окончании вычисления, генератор 10 формирует следующий тактовый импульс, по которому аналогично опи- санному осуществляется обработка следующей порции термов. Так происходит до исчерпания всех термов функции. В последнем такте, после исчерпания термов, все сигналы на входах элементов ИЛИ-НЕ принимают нулевое значение и сигнал с выхода генератора 10 открывает элемент И 16, формируя сигнал окончания процесса на выходе элемента ИЛИ 21. Устройство устанавливается в исходное состояние, причем установка триггера 6 в нулевое состояние

открывает элемент И 15, с выхода которого вычисленное значение булевой функции подается на выход 25. При этом по окончании процесса вычисления по нулевому содержимому блоков памяти нулевое значение сигнала на прямом выходе триггера 6 запрещает запись информации в триггер 5, не искажая информацию.

Таким образом, устройство позволяет

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

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

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

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

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

К-й блоки памяти, (К - количество дизъюнктивных или конъюнктивных членов в функции), с второго по К-й функциональные преобразователи, элемент НЕ, элемент ИЛИ-НЕ, с третьего по девятый элементы И

и три элемента ИЛИ, причем вход запуска устройства соединен с синхровходом счетчика и установочным входом второго триггера, прямой выход которого соединен с входом генератора импульсов и первым входом второго элемента И, выход которого соединен с тактовым входом первого триггера, прямой выход которого соединен с первыми входами третьего и четвертого элементов И, вторые входы которых соединены

соответственно с вторым выходом формирователя импульсов и инверсным выходом второго триггера, вход сброса которого соединен с выходом первого элемента ИЛИ и является выходом признака окончания вычислений устройства, информационные входы которого соединены с входами первой группы с второго по К-й функциональных преобразователей, входы второй группы которых соединены с выходами с второго по К-й блоков памяти соответственно, выходы всех блоков памяти соединены с входами элемента ИЛИ-НЕ, выход которого соединен с первым входом пятого элемента И, второй вход которого соединен с выходом генератора импульсов и первыми входами первого и шестого элементов И, а выход - с установочным входом первого триггера, инверсный выход которого соединен с первым входом седьмого элемента И, второй вход которого соединен с первым выходом формирователя импульсов, второй выход которого соединен с вторым входом второго элемента И, второй вход первого элемента И соединен с выходом признака кода операции первого блока памяти, третьим вхо2«

0

5

0

5

дом третьего элемента И, первым входом восьмого элемента И и входом элемента НЕ, выход которого соединен с вторым входом шестого элемента И, третьим входом седьмого элемента И, выход которого соединен с первым входом первого элемента ИЛИ, второй и третий входы которого соединены соответственно с выходами третьего и пятого элементов И, выход счетчика соединен с адресными входами с второго по К-й блоков памяти, выходы вычисления конъюнкции всех функциональных преобразователей соединены с входами второго элемента ИЛИ, выход которого соединен с вторым входом восьмого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, второй вход которого соединен с выходом девятого элемента И, первый вход которого соединен с выходом элемента НЕ, а остальные входы девятого элемента И соединены с выходами значений дизъюнкции всех функциональных преобразователей, выход третьего элемента ИЛИ соединен с информационным входом первого триггера, выход четвертого элемента И является информационным выходом устройства.

Фаг. 1

Фиг. 2