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

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

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

Устройство содержит два коммутатора 1 и 2, дешифратор 3, две группы триггеров 4 и 5, блок 6 памяти программ, элемент НЕ 7, триггер 8, формирователь 9 импульсов, элемент И 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, два сумматора 12 и 13, группу элементов НЕ 14, группу элементов ИЛИ 15, тактовый вход 16, вход 17 установки логического нуля, группу информационных входов 18, группу выходов 19, вход 20 начально.й установки.

Существуют булевые.функции, для которых программа, построенная по линейным бинарным графам (ЛБГ), не является оптимальной по количеству команд. На.пример, рассмотрим функцию уо

X2X1VX2XOVX2X1XO.

ЛБГ этой функции показан на фиг.2а и состоит из шести вершин условных перехо- . дов и двух операторных вершин (вершин присвоения значения уо О и уо 1). Построенная по данному ЛБГ программа вычисления состоит, соответственно, из восьми команд. В табл.1 представлена таблица истинности функции уо.

Представим каждый набор значений аргументов Хо, Xi, Х2 натуральным числом X в соответствии с формулой

X i Xi 2 . .

Теперь процесс вычисления может быть

представлен алгоритмом, второго рода (Л Б Г 2). ЛБГ 2 функции уо (фиг,26) содержит четыре вершины (две вершины условного перехода и две вершины присвоения значений уо О и уо 1), т.е. в два раза меньше, чем в ЛБГ. Таким образом, для функции уо более оптимальной по количеству команд является программа, построенная по ЛБГ 2. Устройство работает следующим образом.

Когда на входе 20 начальной установки имеет место сигнал, запрещающий работу устройства (по отрицательному фронту первого, после появления сигнала запрета, тактового импульса) на выходе триггера 8 . формируется сигнал установки группы триггеров 4 в начальное состояние, При этом на выходах группы триггеров 4 будет иметь

место нулевой код, независимо от поступле- .ния на их тактовые входы тактовых импульсов, а устройство будет находиться в состоянии ожидания. При появлении на вхо- 5 де 20 начальной установки устройства сигнала, разрешающего работу устройства (по отрицательному фронту первого тактового импульса), на выходе триггера 8 сформиру- . ется сигнал, разрешающий работу тригге- 10 оов гоуппы 4.

Каждая команда, записанная в блоке 6 памяти программ, содержит код границы числового интервала: код признака алгоритма; код признака аргумента; код адреса ко- 15 манды, к выполнению которой устройство приступит в следующем такте; код адреса результата вычисляемой функции; код разрешения записи результата вычисления логической функции; код результата вычис- 20 ления логической функции.

Устройство может работать как по программам, составленным по ЛБГ, так и по программам, составленным по ЛБГ 2.

При этом, если код признака алгоритма, 25 поступающий на управляющий вход коммутатора 1, равен Лог.О, то устройство реализует программу, сЪставленную по ЛБГ, в противном случае - по ЛБГ 2.

Процедура вычисления булевых функ- 30 ций заключается в следующем.

Первая.команда программы, находяща- яся в блоке 6 памяти программ, по нулевому адресу, когда устройство находится в состояний ожидания, может быть командой про- 35 граммы, составленной по ЛБГ или по ЛБГ 2. Не нарушая общности, рассмотрим сначала работу устройства по программе, составленной по ЛБГ. В этом случае, при формировании на выходах блока 6 памяти 40 программ первой команды на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 поступает, сигнал, соответствующий значению первого опрашиваемого аргумента первой функции. Выбор опрашиваемого аргумента 45 происходит следующим образом. На управляющий вход коммутатора 1 подается сигнал Лог.О, при этом на вторые входы сумматора 13 поступает код Хо , ... Хп ,

каждый разряд которого формируется по формуле Xi (Х| v Zi), где Zi - соответствующий разряд кода границы числового интервала, поступающий с выходов блока 6 памяти программ на вторые входы элементов ИЛИ 15 группы, Xi - соответствующий 55 аргумент вычисляемой функции.

Для того чтобы значение сигнала на выходе переноса сумматора 13 было равно значению опрашиваемого аргумента, в соответствующий разряд кода границы числовою интервала записывается Лог. Г, в остальные разряды этого кода - Лог.О.

Предположим, что необходимо подать на первый вход элемента ИСКЛЮЧАЮЩЕЕ Или 11 сигнал, соответствующий значению apf MeHTa Xi.

Тогда код соответствующей границы 10ВОГО интервала равен О ... О, 1,0 ... О, только в 1-й разряд записывается зг.Г, в остальные разряды - Лог.О.

При этом на вы)оде KOMMyTajopa 1 фор- ми|руется код Хп ... Хни, 1, i-i... Хо, который ступает на вторые входы сумматора 13, на рвые входы которого поступает код Хп ... -,, Хо. При сложении этих кодов на выходе реноса сумматора 13 формируется сиг- на1л, соответствующий значению Xi.

Таким образом, при работе устройства ПС программе, составленной по ЛБГ, устройство позволяет использовать код грани- ць числового интервала для формирования на выходе переноса сумматора 13 сигнала, значение которого равно значению опрашиваемого аргумента.

На первый вход элемента ИСКЛЮЧАЮ- :Е ИЛИ 11 поступает сигнал, значение горого равно значению опрашиваемого аргумента, на второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 поступает сигнал признака этого аргумента, равный Лог.Г, 1И аргумент входит в ЛБГ алгоритма с зицанием, и Лог.О в противном случае. Если на выходе элемента ИСКЛЮЧАЮ- ||ЕЕ ИЛИ 11 формируется сигнал Лог.1, (на вторых входах сумматора 12 формиру- :я код, соответствующий числу 1, а на первые входы сумматора 12 через коммута: TOJP 2 поступит код с выходов триггеров 4 /ппы. Обозначим число, соответствующее DMy коду А. Тогда на выходе сумматора 12 сформируется код, соответствующий числу

- 1.

Если на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 сформируется сигнал Лог.О, на выходах сумматора 12 сформируется кед адреса команды из блока 6 памяти программ,

Код на выходах сумматора 12 определяет, какую команду устройство выполнит в с/ едующем такте работы. В первом случае этр будет следующая по порядку команда, в( втором - команда, код которой записан в п(1ле номера команды выполняемой коман- дн.

После появления на установочных вхо- дг X группы триггеров 4 сигнала, разрешающего их работу по тактовым входам, по положительному фронту первого тактового импульса код, имеющий место на выходах сумматора 12. записывается в группу триггеров 4. По этому коду в блоке 6 памяти программ формируется код новой команды. При этом, если значение опрошенного аргумента не полностью определяет значение

функции, то по этой команде осуществляется опрос другого аргумента этой же функции. Если значение функции полностью определяется значением опрошенного аргумента, то осуществляется запись резуль0 тата вычисления функции в один из триггеров 5 группы, в зависимости от кода адреса результата, который поступает на адресные входы дешифратора 3 из блока 6 памяти программ, и формируется код услов5 ного перехода к первой команде программы вычисления следующей функции. Для перехода к вычислению следующей функции в команде, по которой производится запись результата вычисления, в поле кода грани0 цы числового интервала записывается нулевой код. В поле признака аргумента записывается сигнал Лог.О. в поле адреса команды записывается код адреса команды, по которой производится опрос и анализ

5 первого аргумента следующей функции, или код адреса первой команды программы вычисления следующей функции, построенной по ЛЕГ 2.

Работа устройства по программе, со0 ставленной по .ПБГ 2.

По программе этого типа на сумматоре 13 производится последовательное сложение значения вектора X {Хп,..., Хо} с числами Zi, записанными в поле кода границы,

5 числового интервала, при этом Zi представляет собой дополнительный код границы числовых интервалов Zi, Zn-i, на которых вычисляемая функция принимает противоположные значения. Кроме того, при

0 выполнении программы, составленной по ЛВГ 2, в поле признака алгоритма всех команд этой программы, за исключением команд присвоения значения, записывается Лог. 1, в поле признака аргумента записы5 ваётся Лог.О, остальные поля команд в

блоке 6 памяти программ формируются так

же, как для программ, построенных по ЛБГ.

По командам программы, построенной

по ЛБГ 2, произзодится сложение вектора

0 значений аргументов с дополнительным кодом границ. Эта операция эквивалентна сравнению числа, соответствующего вектору значений аргументов и границы. Если X Zi, то на выходе переноса сумматора 13

5 формируется сигнал Лог.1 и по этому сигналу устройство переходит к выполнению следующей по порядку команды. Если X Zi, то на выходе переноса сумматора 13 формируется сигнал Лог.О. По этому сигналу устройство переходит к выполнению команды, адрес которой записан в поле адреса команды. Переход к последующей команда и в том и в другом случае выполняется так же, как и при реализации программы, построенной по ЛБГ. Это же можно сказать о командах записи результата - для всех типов программ они формируются аналогично.

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

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

В этом случае устройство будет постоянно выполнять эту команду до перевода его в состояние ожидания сигналом с входа 20 начальной установки устройства.

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

УО X2X1VX2XOVX2X1XO.

При этом первая программа (команды 0-7) построена по ЛБГ, а вторая (команды 8 - 11) - по ЛБГ 2. Для составления программ вычисления строятся ЛБГ и ЛБГ 2 этой функции (фиг.2а, б).

Составление программы вычисления по ЛБГ производится следующим образом (табл.2, команды О - 5).

В столбец 4 записываются коды адресов аргументов вычисляемой функции в том порядке, в котором эти аргументы расположены в ЛБГ; при этом код адреса любой переменной формируется следующим образом, в тот разряд кода, номер которого идентичен номеру рассматриваемого аргумента, записывается 1, в остальные разряды -

в каждую строку столбца 5 заносится

в каждую строку столбца 6 заносится 1, если аргумент, код адреса которого записан в этой строке, входит в ЛБГ с )- сией, в противном случае записывается

в каждую строку столбца 7 записывается код адреса той команды, к выполнению которой необходимо перейти по нулевому

значению выражения, стоящего в соответствующей этой строке вершине ЛБГ; .

в каждую строку столбца 9 записывается

что будет записано в столбцах В и 10,

значения не имеет;

в следующей по порядку строке (команда 6) записывается команда записи резуль- и тата вычисления функции по единичному 0 значению выражения, стоящего в последней вершине ЛБГ, далее записывается команда записи противоположного результата (команда 7).

Команды записи результата формиру- 5 ются одинаково для любой из рассматриваемых в описании программ. При этом в столбцы 4, 5, 6 записываются нулевые коды, в столбец 9 - 1, в столбец 8 - код номера вычисляемой функции, в столбец 10 - соот- 0 ветствующие значения функции, в столбец 7 заносится код адреса команды, к которой необходимо перейти после записи результата.

Составление программы вычисления по 5 ЛБГ 2 производится следующим образом (команды 8 и 9 табл.2).

В столбец 4 записываются дополнительные коды границ числовых интервалов ;

в столбец 5 - 0в столбец

в каждую строку столбца 7 записывается код адреса той команды, к выполнению которой необходимо перейти по нулевому значению выражения, стоящего всоответст- 35 вующей этой строке вершине ЛБГ 2, при этом считается, что вершина ЛБГ 2 принимает нулевое значение, если выражение, записанное в нем, не выполняется; в столбец 9 записывается О ; 40 что будет записано в столбцах 10 и-8, значения не имеет.

Команды записи результата (команды 10 и 11 табл.2) формируются и чередуются так же, как при составлении программы

45 по ЛБГ.

Рассмотрим процесс вычисления уо при Следующих значениях аргументов Хо 1.

Xl 1,.

Командами 0-2 осуществляется после- 50 довательный опрос аргументов Х2, Xi, Хо и переход к следующей по порядку команде, поскольку все эти аргументы имеют значение 1 и признак О. Команда 3 осуществляет повторный анализ аргумента Х2 с 55 признаком 1, посколькуХ2-- 1 иформирует условный переход к.команде, записанной

по адресу 01112.

По этому адресу находится команда записи результата (команда 7) по адресу О (т.е. триггер с нулевым адресом группы тригге О, ЩЕЕ

СИГНс

рехо 1000 пров

1112

ТО

ров5|. Поскольку по этой команде на входах перв1)го и второго слагаемых сумматоров

фОр1УИруЮТСЯ коды Х2. Xl, Хо и Х2. Xl, (0

cooTt етственно (для нашего примера это ко- 12 и ОООа), то на выходе переноса сум- матоЬа 13 формируется сигнал нулевого уровня. Так как признак аргумента равен и на выходе элемента ИСКЛЮЧАЮ- ИЛИ 11 тоже формируется нулевой л. По этому сигналу организуется пе- к команде 8, находящейся по адресу По этой команде производится зрка условия 7 3(в двоичных кодах S0112), эта проверка производится сло 1ением на сумматоре 13 кодов 1112 и 1012 (где 1012 - дополнительный код числа 3)

Г ри этом- сигнал на выходе переноса сумматора 13 примет единичное значениеи, поскольку признак аргумента равен О, на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 формируется сигнал единичного уровня. По сигналу устройство перейдет к выпол- о следующей по порядку команды 9. эт1ой команде производится проверка ус- 7 7 и, как в предыдущей команде, зультату сравнения осуществляется од к следующей по порядку команде этой команде осуществляется запись резу ьтата вычисления по адресу 01.

ЭТОМ

нени

По

лови;

по р

пере:

10.

П)

Таким образом, устройство позволяет прои )водить вычисление как по программам, построенным по ЛБГ, так и по ЛБГ 2.

Кроме того, устройство позволяет реализовать программы по смешанному алгоритма, примере которого дан на фиг.2в для функ ии;

yi X1VX1X2XO.

г рограмма вычисления этой функции, состс вленная по смешанному алгоритму, представлена в табл.2 (команды 12- 15). На фиг.2г, д представлены два вида алгоритмов вычисления - ЛБГ и ЛБГ 2. Каждый из них состоит из трех условных и двух операторных вершин. Это значит, что для реализации любого из них необходимо использовать пять команд. Смешанный алгоритм вычис- лени51 (назовем его ЛБГ третьего рода или ЛБГ 3) содержит две условные вершины и две ( ператорные, соответственно для его реализации требуется четыре команды. По первой команде (команда 12 табл.2) производи ся анализ переменной Xi, а по второй команде (команда 13) проверяется условие X 2: 5. Две последние команды (14 и 15) являится командами записи результата.

Возможность составления программ по ЛБГ 3 обеспечивается за счет сопрягаемости команд анализа значения переменной и команд проверки выполнения условия Больше или равно.

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

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

функций, содержащее блок памяти программ, дешифратор, две группы триггеров, элемент НЕ, триггер, формирователь импульсов, элемент И, элемент ИСКЛЮЧАЮ0 ЩЕЕ ИЛИ, Иервый коммутатор, первый сумматор, причем выходы кода адреса результата блока памяти программ соединены с адресными входами дешифратора, стро- бирующий вход которого соединен с выхо5 дом элемента И, первый вход которого соединен с выходом разрешения записи результата блока памяти программ, второй вход элемента .1 соединен с выходом формирователя импульсов, вход которого сое0 динен с тактовым входом триггера и выходом элемента НЕ, вход которого соединен с тактовым входом устройства и тактовыми входыми триггеров первой группы, входы установки в О которых соединены с

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

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

5 первой группы, первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом признака аргумента блока памяти программ, выходы кода адреса условного перехода которого соединены с первыми

0 входами первого коммутатора, управляющий вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и с входом младшего разряда первого слагаемого первого сумматора, входы старших разрядов

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

5 элементов-НЕ, группу элементов ИЛИ, второй коммутатор и второй сумматор, причем вход первого слагаемого второго сумматора соединен с информационными входами группы устройства, i-й информационный вход которой соединен с I-M элементом НЕ

группы, выход которого соединен с первым входом 1-го элемента ИЛИ группы, выход которого соединен с 1-м входом первой группы входов второго коммутатора. 1-й разряд второй группы входов которого соединен с вторым входом i-ro элемента ИЛИ группы и С 1-м выходом кода границ числовых интервалов блока памяти программ, выход признака алгоритма которого соединен с управляющим входом второго коммутатора., выход которого соединен с входом второгр слагаемого второго сумматора, выход переноса которого соединен с вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ.

Та б л и ца 1

Изобретение относится к области автоматики и вычислительной техники и предназначено для вычисления булевых функций в системах контроля и управления. Целью изобретения является повышение производительности устройства. Устройство для вычисления булевых функций содержит два коммутатора 1 и 2, дешифратор 3, две группы триггеров 4 и 5, блок памяти программ 6, элемент НЕ 7, триггер 8, формирователь импульсов 9, элемент И 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, два сумматора 12 и 13, группу элементов НЕ 14, группу элементов ИЛИ 15. Устройство позволяет производить вычисление булевых функций по программам, составленным по трем видам линейных бинарных графов (ЛБГ), что позволяет выбрать алгоритм, наиболее оптимальный по количеству команд и минимальному времени вычисления. 2 ил., 2 табл.

Xi О О 1 1 О

о 1 1

Хо О 1 О 1 О

1 о 1

Уо О

о о 1 1 1 1 о

10

Таблица 2