Устройство для вычисления булевых функций
Изобретение относится к области автоматики и вычислительной техники и предназначено для вычисления булевых функций в системах контроля и управления. Целью изобретения является повышение производительности устройства. Устройство для вычисления булевых функций содержит два коммутатора 1 и 2, дешифратор 3, две группы триггеров 4 и 5, блок памяти программ 6, элемент НЕ 7, триггер 8, формирователь импульсов 9, элемент И 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, два сумматора 12 и 13, группу элементов НЕ 14, группу элементов ИЛИ 15. Устройство позволяет производить вычисление булевых функций по программам, составленным по трем видам линейных бинарных графов (ЛБГ), что позволяет выбрать алгоритм, наиболее оптимальный по количеству команд и минимальному времени вычисления. 2 ил., 2 табл.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
1 А1 (19) (51)5
ГОС
ПО
ПР (21) (22) (46) (72) лов (53 (56 (54
ЛЕ (57 ма нэ
Фу в(ДАРСТВЕННЫЙ КОМИТЕТ
ЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ГКНТ СССР
К ВТОРСКОМУ СВИДЕТЕЛЬСТВУ
4612127/24-24
30.11.88
23,11.90. Бюл. hh 43
В.Н.Вавилов, E.Ñ.Âàëüøîíîê, А.С.Сигаи А.А.Шалыто
681.3 (088.8)
Авторское свидетельство СССР
339545, кл, G 06 Р 7/00, 1986.
Авторское свидетельство СССР
501033, кл. G 06 F 7/00, 1988.
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЫХ ФУНКЦИЙ
Изобретение относится к области автоики и вычислительной техники и предначено для вычисления булевых кций в системах контроля и управления, Целью изобретения является повышение производительности устройства. Устройство для вычисления булевых функций содержит два коммутатора 1 и 2, дешифратор 3, две группы триггеров 4 и 5, блок памяти программ 6, элемент НЕ 7, триггер 8, формирователь импульсов 9, элемент И 10, элемент ИСКЛЮЧА)ОЩЕЕ ИЛИ 11, два сумматора 12 и 13, группу элементов НЕ 14, группу элементов ИЛИ 15. Устройство позволяет производить вычисление булевых функций по программам, составленным по трем видам линейных бинарных графов (Л БГ), что позволяет выбрать алгоритм, наиболее оптимальный по количеству команд и минимальному времени вычисления, 2 ил., 2 табл.
1608641
Изобретение относится к автоматике и вычислительной технике и предназначено для вычисления булевых функций в системах контроля и управления.
Целью изобретения является повыше- 5 ние производительности устройства.
На фиг.1 представлена структурная схема устройства для вычисления булевых функций; на фиг,2 — граф-схемы алгоритмов вычисления булевых функций. 10
Устройство содержит два коммутатора . 1 и 2, дешифратор 3, две группы триггеров
4 и 5, блок 6 памяти программ, элемент
НЕ 7, триггер 8, формирователь 9 импульсов, элемент И 10, элемент ИСКЛЮЧАЮ- 15
ЩЕЕ ИЛИ 11, два сумматора 12 и 13, группу элементов НЕ 14, группуэлементов ИЛИ 15, тактовый вход 16, вход 17.установки логического нуля, группу информационных входов 18, группу выходов 19, вход 20 начальной 20 установки.
Существуют булевые функции, для которых программа, построенная по линейным бинарным графам (ЛБГ), не является оптимальной по количеству команд. 25
Например, рассмотрим функцию yp=
= X2X1VX2XPVX2X1XP
ЛБГ этой функции показан на фиг.2а и состоит из шести вершин условных переходов и двух операторных вершин (вершин 30 присвоения значения yp= О и yp= 1). Построенная по данному ЛБГ программа вычисления состоит, соответственно, из восьми команд..B табл.1 представлена таблица истинности функции уо, 35
Представим каждый набор значений аргументов Хо, Х1, Хг натуральным числом Х в соответствии с формулой г
Х=,, Х1.2. 40
i=0
Теперь процесс вычисления может быть представлен алгоритмом второго рода (ЛБГ 2). ЛБГ 2 функции уо (фиг,2б) содержит четыре вершины (две вершины условного 45 перехода и две вершины присвоения значений уо = О и yp = 1); т.е. в два раза меньше, чем в ЛБГ,.Таким образом, для функции ур более оптимальной по количеству команд
1 является программа, построенная по ЛБГ 2,:,5
Устройство работает следующим образом.
Когда на входе 20 начальной установки имеет место сигнал, запрещающий работу устройства (по отрицательному фронту первого, после появления сигнала запрета, так тового импульса) на выходе триггера 8 формируется сигнал установки группы триггеров 4 в начальное состояние, При этом на выходах группы триггеров 4 будет иметь место нулевой код, независимо от поступления на их тактовые входы тактовых импульсов, а устройство будет находиться в состоянии ожидания, При появлении на входе 20 начальной установки устройства сигнала, разрешающего работу устройства (по отрицательному фронту первого тактового импульса), на выходе триггера 8 сформируется сигнал, разрешающий работу триггеоов гDYflllbl 4, Каждая команда, записанная в блоке 6 памяти программ, содержит код границы числового интервала; код признака алгоритма; код приз ; код адреса команды, к выполнению которой устройство приступит в следующем такте; код адреса результата вычисляемой функции; код разрешения записи результата вычисления логической функции; код результата вычисления логической функции, Устройство может работать как по программам, составленным по ЛБГ, так и по программам, составленным по ЛБГ 2.
При этом, если код признака алгоритма, поступающий на управляющий вход коммутатора 1, равен "Лог.О", то устройство реализует программу, составленную по ЛБГ, в противном случае — по ЛБГ 2, Процедура вычисления булевых функций заключается в следующем, Первая. команда программы, находящаяся в блоке 6 памяти программ, по нулевому адресу, когда устрой тво находится в состоянии ожидания, может быть командой программы, составленной по ЛБГ или по ЛБГ 2, Не нарушая общности, рассмотрим сначала работу устройства по программе, составленной по ЛБГ, В этом случае, при формировании на выходах блока 6 памяти программ первой команды на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 посту-. пает. сигнал, соответствующий значению первого опрашиваемого аргумента первой функции. Выбор опрашиваемого аргумента происходит следующим образом. На управляющий вход коммутатора 1 подается сигнал "Лог,О", при этом на вторые входы сумматора 13 поступает код Xp, ... Х„
1 1 каждый разряд которого формируется по формуле Xi = (Xi ч Zi), где Zl — соответствующий разряд кода границы числового интервала, поступающий с выходов блока 6 памяти программ на вторые входы элементов ИЛИ 15 группы, Xi — соответствующий аргумент вычисляемой функции.
Для того чтобы значение сигнала на выходе переноса сумматора 13 было равно значению опрашиваемого аргумента, в соответствующий разряд кода границы число5 1608641 о интервала записывается "Лог.1", в осьные разряды этого кода — "Лог.О .
Предположим, что необходимо подать первый вход элемента ИСКЛЮЧАЮЩЕЕ
И 11 сигнал, соответствующий значению мента Хь
Тогда код соответствующей границы лового интервала равен О ... О, 1, 0 ... О, „только в l-й разряд записывается г.1", в остальные разряды — "Лог.О".
При этом на выходе коммутатора 1 форруется код X> ... Х +1, 1, )4-1.,.. Хо, который туиает на вторые входы сумматора 13, на рвые входы которого поступает код Хл ... во та на
И ар
10 чи т.
"Л м и п
Xi и н
Хо. При сложении этих кодов на выходе
15 реноса сумматора 13 формируется сиг, соответствующий значению Х .
Таким образом, при работе устройства программе, составленной по ЛБГ, устйство позволяет использовать код грании
Ц н э ва
20 числового интервала для формирования выходе переноса сумматора 13 сигнала, чение которого равно значению опрашимого аргумента. срого равно значению опрашиваемого гумента, на второй вход элемента ИСКЧАЮЩЕЕ ИЛИ 11 поступает сигнал изнака этого аргумента, равный "Лог.1", и аргумент входит в ЛБГ алгоритма с ицанием, и "Лог.О" в противном случае.
Если на выходе элемента ИСКЛЮЧАЮЕЕ ИЛИ 11 формируется сигнал "Лог.1", на вторых входах сумматора 12 формирук а
Л п е о
35 т е п г э с
А я код, соответствующий числу "1", а на рвые входы сумматора 12 через коммутар 2 поступит код с выходов триггеров 4 ппы. Обозначим число, соответствующее му коду А. Тогда на выходе сумматора 12 ормируется код, соответствующий числу
1, Если на выходе элемента ИСКЛЮЧАЮЕЕ ИЛИ 11 сформируется сигнал "Лог.О", на выходах сумматора 12 сформируется д адреса команды из блока 6 памяти проамм, Код на выходах сумматора 12 определя40
45, какую команду устройство выполнит в е с э в и д едующем такте работы. В первом случае о будет следующая по порядку команда, втором — команда, код которой записан в ле номера команды выполняемой коман50
После появления на установочных вхо- 55 х группы триггеров 4 сигнала, разрешаюго их работу по тактовым входам, по ложительному фронту первого тактового пульса код, имеющий место на выходах мматора 12, записывается в группу тригНа первый вход элемента ИСКЛЮЧАЮ-. 25
ЕЕ ИЛИ 11 поступает сигнал, значение герое 4, По этому коду в блоке 6 памяти программ формируется код новой команды.
При этом, если значение опрошенного аргумента не полностью определяет значение функции, то по этой команде осуществляется опрос другого аргумента этой же функции. Если значение функции полностью определяется значением опрошенного аргумента, то осуществляется запись результата вычисления функции в один из триггеров 5 группы, в зависимости от кода адреса результата, который поступает на адресные входы дешифратора 3 из блока 6 памяти программ, и формируется код условного перехода к первой команде программы вычисления следующей функции. Для перехода к вычислению следующей функции в команде, по которой производится запись результата вычисления, в поле кода границы числового интервала записывается нулевой код. В поле признака аргумента записывается сигнал "Лог.0", в поле адреса команды записывается кодадреса команды, по которой производится опрос и анализ первого аргумента следующей функции, или код адреса первой команды программы вычисления следующей функции, построенной по ЛБГ 2.
Работа устройства по программе, составленной по ЛБГ 2.
По программе этого типа на сумматоре
13 производится последовательное сложение значения вектора Х = (Х, ..., Xo) с числами Zi, записанными в поле кода границы, числового интервала, при этом Z представляет собой дополнительный код границы числовых интервалов Zt, 2н-, на которых вычисляемая функция принимает противоположн.ые значения. Кроме того, при выполнении программы, составленной по
ЛБГ 2, в поле признака алгоритма всех команд этой программы, эа исключением команд присвоения значения, записывается
"Лог.1", в поле признака аргумента записывается "Лог,О", остальные поля команд в блоке 6 памяти программ формируются так же, как для программ, построенных по ЛБГ.
По командам программы, построенной по ЛБГ 2, производится сложение вектора значений аргументов с дополнительным кодом границ, Эта операция эквивалентна сравнению числа, соответствующего вектору значений аргументов и границы, Если
Х Z>, то на выходе переноса сумматора 13 формируется сигнал "Jlor.1" и по этому сигналу устройство переходит к выполнению следующей по порядку команды. Если Х < Zi, то на выходе переноса сумматора 13 формируется сигнал "Лог.О", По этому сигналу устройство переходит к выполнению коман1608641
30
50 ды, адрес которой записан в поле адреса команды. Переход к последующей команде и в том и в другом случае выполняется так же, как и при реализации программы, построенной по ЛБГ. Это же можно сказать о командах записи результата — для всех типов программ они формируются аналогично, После вычисления всех логических функций оо любым типам программ устройство может перейти к вычислению первой функции. Для этого в поле адреса команды двух последних команд программы необходимо записать адрес первой команды программы.
Кроме того, устройство может.прекратить вычисления„для чего в поле адреса команды двух последних команд программы вычисления записывается код адреса дополнительной, пустой команды, в поле кода границы числового интервала которой записываются логические нули, в поля признака алгоритма и признака аргумента — "Лог.0", в поле адреса команды — адрес этой команды, в поле разрешения выдачи результата—
"Лог.0", В этом случае устройство будет постоянно выполнять эту команду до перевода
его в состояние ожидания сигналом с входа
20 начальной установки устройства, В табл.2 представлены две программы вычисления функции;
yO = Х2Х1ЧХ2ХОЧХ2Х1ХО, При этом первая программа (команды
0 — 7) построена по ЛБГ, а вторая (команды
8 — 11) — по ЛБГ 2. Для составления программ вычисления строятся ЛБГ и ЛБГ
2 этой функции (фиг.2а, б).
Составление программы вычисления по
ЛБГ производится следующим образом (табл.2, команды 0 — 5), В столбец 4 записываются коды адресов аргументов вычисляемой функции в том порядке, в котором эти аргументы расположены в ЛБГ; при этом код адреса любой переменной формируется следующим образом, в тот разряд кода, номер которого идентичен номеру рассматриваемого аргумента, записывается "1", в остальные разряды — "0", в каждую строку столбца 5 заносится . Il ail
I в каждую строку столбца 6 заносится
"1", если аргумент, код адреса которого записан в этой строке, входит в ЛБГ с инверсией, в противном случае записывается "0"; в каждую строку столбца 7 записывает ся код адреса той команды, к выполнению которой необходимо перейти по нулевому значению выражения, стоящего в соответствующей этой строке вершина ЛБГ; в каждую строку столбца 9 записывается "0"; что будет записано в столбцах 8 и 10, значения не имеет; в следующей по порядку строке (команда 6) записывается команда записи результата вычисления функции по единичному значению выражения, стоящего в последней вершине ЛБГ, далее записывается команда записи противоположного результата (команда 7), Команды записи результата формируются одинаково для любой из рассматриваемых в описании программ. При этом в столбцы 4, 5, 6 записываются нулевые коды, в столбец 9 — "1", в столбец 8 — код номера вычисляемой функции, в столбец 10 — соответствующие значения функции, в столбец
7 заносится код адреса команды„к которой необходимо перейти после записи результата.
Составление программы вычисления по
ЛЕГ 2 производится следующим образом (команды 8 и 9 табл,2).
В столбец 4 записываются дополнительные коды границ числовых интервалов; в столбец 5 — "1"; в столбец 6 — "0", в каждую строку столбца 7 записывается код адреса той команды, к выполнению которой необходимо перейти по нулевому значению выражения, стоящего в соответствующей этой строке вершине ЛБГ 2, при этом считается, что вершина ЛБГ 2 принимает нулевое значение, если выражение, записанное в нем, не выполняется; в столбец 9 записывается "0"; что будет записано в столбцах 10 и 8, значения не имеет.
Команды записи результата (команды
10 и 11 табл.2) формируются и чередуются так же, как при составлении программы по ЛБГ.
Рассмотрим процесс вычисления уО при следующих значениях аргументов Xo = 1, Х1= 1, X2= 1.
Командами 0 — 2 осуществляется последовательный опрос аргументов Х2, Х1 ХО и переход к следующей по порядку команде, поскольку все эти аргументы имеют значение "1" и признак "0". Команда 3 осуществляет повторный анализ аргумента Х2 с признаком "1", пос кол ьку Х2 =" 1 и формирует условный переход к комэчде, записанной пО адрЕСу 01112, По этому адресу находится команда записи результата (команда 7) по адресу 0 (т.е. триггер с нулевым адресом группы тригге1608641
poa5 перв фор соот
Pbl 1 мато уров
"0", ЩЕЕ сигн рехо
1000 пров
111г сло и 101 ла 3) 5
15 сумм поск выхо фор этом нени
Поз лови по р пере
10. П резу
30 прои мам, 35 лиза ритм функ
55 сост пред фиг.2 вычи сост ных любо пять лени
ЛБГ две реал перв води кома
X явля
ЛБГ. Поскольку по этой команде на входах го и второго слагаемых сумматоров ируются коды Хг, Х1, Хо и Xz, Х1, Хо етственно (для нашего примера это ко1z и 000z), то на выходе переноса сума 13 формируется сигнал нулевого я, Так как признак аргумента равен о и на выходе элемента ИСКЛЮЧАЮИЛИ 11 тоже формируется нулевой л. По этому сигналу организуется пек команде 8, находящейся по адресу
По этой команде производится рка условия 7 «3 (в двоичных кодах
«011z), эта проверка производится ением на сумматоре 13 кодов 111z г (где 101г - дополнительный код чисри этом. сигнал на выходе переноса тора 13 примет единичное значение и, льку признак аргумента равен "0", на е элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 ируется сигнал единичного уровня. По сигналу устройство перейдет к выполследующей по порядку команды 9, и команде производится проверка ус7 " 7 и, как в предыдущей команде, зультату сравнения осуществляется од к следующей по порядку команде этой команде осуществляется запись ьтата вычисления по адресу 01. аким образом, устройство позволяет водить вычисление как по програмпостроенным по ЛБГ, так и по ЛБГ 2. роме того, устройство позволяет реаать программы по смешанному апго, примере которого дан на фиг.2в для ии: у1 = x>vx ro из них необходимо использовать команд. Смешанный алгоритм вычис(назовем его ЛБГ третьего рода или ) содержит две условные вершины и ператорные, соответственно для его зации требуется четыре команды. По и команде (команда 12 табл.2) произся анализ переменной Xt, а по второй де (команда 13) проверяется условие 5. Две последние команды (14 и 15) тся командами записи результата. озможность составления программ по обеспечивается за счет сопрягаемости команд анализа значения переменной и команд проверки выполнения условия "Больше или равно". Формула изобретения Устройство для вычисления булевых функций, содержащее блок памяти программ, дешифратор, две группы триггеров, элемент НЕ, триггер, формирователь импульсов, элемент И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, первый коммутатор, первый сумматор, причем выходы кода адреса результата блока памяти программ соединены с адресными входами дешифратора, стробирующий вход которого соединен с выходом элемента И, первый вход которого соединен с выходом разрешения записи результата блока памяти программ, второй вход элемента .1 соединен с выходом формирователя импульсов, вход которого соединен с тактовым входом триггера и выходом элемента НЕ, вход которого соединен с тактовым входом устройства и тактовыми входыми триггеров первой группы, входы установки в "0" которых соединены с выходом триггера, информационный вход которого соединен с входом начальной установки устройства, выходы которого соединены с выходами триггеров второй группы, тактовый вход i-ro из которых соединены с i-м выходом дешифратора fi = 1, n), информационные входы триггеров второй группы соединены с выходом значения результата блока памяти программ, адресные входы которого соединены с выходами триггеров первой группы, первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом признака аргумента блока памяти программ, выходы кода адреса условного перехода которого соединены с первыми входами первого коммутатора, управляющий вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и с входом младшего разряда первого слагаемого первого сумматора, входы старших разрядов первого слагаемого которого соединены с входом установки логического нуля устройства, входы второго спагаемо о первого сумматора соединены с выходом первого коммутатора, вторые входы которого соединены с выходами триггеров первой группы, информационные входы которых соединены с выходами первого сумматора, о т и ич а ю щ е е с я тем, что, с целью повышения производительности, оно содержит группу элементов НЕ, rpynny элементов ИЛИ, второй коммутатор и второй сумматор, причем вход первого слагаемого второго сумматора соединен с информационными входами группы устройства, i-й информационный вход которой соединен c -м элементом НЕ 1608641 12 валов блока памяти программ, выход признака алгоритма которого соединен с управляющим входом второго коммутатора,. выход которого соединен с входом второго 5 слагаемого второго сумматора, выход переноса которого соединен с вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. группы, выход которого еоединен с первым входом i-ro элемента ИЛИ группы, выход которого соединен с 1-м входом первой груп-. пы входов второго коммутатора, I-й разряд второй группы входов которого соединен с вторым входом i-ro элемента ИЛИ группы и с l-м выходом кода границ числовых интерТаблица 1 Таблица 2 П or амма вычисления логических нк ий Код «оманды Команда Код раз- 3 начереш- ние у ния записи Признак апгоритма Код адреса команды Признак Код адреса или доп. код границы Код М функции Х2 Х1 ХО Х2 Х1 ХО (3) 011 (7) 111 Х1 (5) 101 О 2 4 6 8 11 12 13 14 0001 0011 0101 0111 1001 1011 1101 1111 Аналиэируемый аргумент или код границы числового интер вала 001 001 101 001 011 000 аоо О О О О О О О О 1 О О 1 О О О О О О О О О О О О О О 0011 0111 0111 0111 101.1 1111 .0000 0000 01 01 * О О О О О 1 О О 1 О О 1. О 1 О
