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

 

Изобретение относится к автоматике и вычислительной технике и предназначено для вычисления булевых функций. Цель изобретения - сокращение объема памяти, необходимого для записи программы вычисления булевых функций за счет обеспечения возможности перехода к следующей по номеру команде при неравенстве значений аргумента и его признака. Устройство содержит мультиплексор 1, блок 2 памяти программ, дешифратор 3, две группы 4 и 11 триггеров, генератор 5 импульсов, вход 6 начальной установки, элемент НЕ 7, триггер 8, формирователь 9 импульсов, элемент И 10, информационные входы 12 и выходы 13, элемент СУММА ПО МОДУЛЮ ДВА 14, коммутатор 15, сумматор 16, шину 17 логического нуля. Устройство вычисляет булевые функции по заданной программе. При этом обеспечивается возможность перехода к следующей по номеру команде в случае, когда значение аргумента и его признака неравны между собой. 2 ил. 1 табл.

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

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

РЕСПУБЛИК (s» 4 С 06 F 7/00

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4369489/24-24 (22) 26.01.88 (46) 15.08.89. Бюл. ¹ 30 (72) В.Н. Вавилов, Е.С. Вальшонок, А.С. Сигалов и А.А. 0!алыто (53) 681.3(088.8) (56) Авторское свидетельство. СССР № 955027, кл. G 06 F 7/00, 1980.

Авторское свидетельство СССР № 1339545, кл. G 06 F 7/00, 1986.

„„SU„„1501033 A 1 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к автоматике и вычислительной технике и предназначено для вычисления булевых функций. Цель изобретения — сокращение объема памяти, необходимого для записи программы вычисления булевых функций за счет обеспечения возможности перехода к следующей по номеру

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

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

Целью изобретения является упрощение устройства за счет сокращения объема памяти.

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

Устройство для вычисления булевых функций содержит мультиплексор 1, блок 2 памяти программ, дешифратор 3, группу триггеров 4, генератор 5 импульсов, вход 6 начальной установки, элемент НЕ 7, триггер Я,формирователь

9 импульсов, элемент И 10, группу 35 триггеров 11, информационные входы

12, выходы 13, элемент СУММА ПО МОДУЛЮ ДВА 14, коммутатор 15,сумматор 16, шину 17 логического нуля.

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

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

6 сигнала,. разрешающего работу устрой.55 ства, по отрицательному фронту первого тактового импульса, поступающего с выхода генератора 5 импульсов, на выходе триггера 8 сформируется сиг-. элемент СУММА ПО МОДУЛЮ ДВА 14, коммутатор 15, сумматор 16, шину 17 логического нуля. Устройство вычисляет булевые функции по заданной программе. При этом обеспечивается возможность перехода к следующей по номеру команде в случае, когда значение аргумента и его признака не равны между собой. 2 ил. 1 табл. нал, разрешающий работу группы триггеров 4 по тактовым входам. Пб положительным фронтам тактовых импульсов производится вызов команд программы вычисления булевых функций, записанной в блоке 2 памяти программ. Каждая команда содержит код aqpeca опрашивае мого аргумента, поступающий на управляющие входы мультиплексора 1; код признака аргумента, равный "1", если аргумент входит в линейную граф-схему алгоритма с отрицанием, и "О в противном случае, и поступающий на второй вход элемента СУММА ПО МОДУЛЮ ДВА

14; код адреса команды, к выполнению которой устройство приступит на следующем такте, если в данном такте на выходе элемента СУММА ПО МОДУЛЮ ДВА

14 сформировался сигнал "0", этот код поступает на первые входы коммутатора 15; код адреса результата вычисляемой функции, который поступает па . " адресные входы дешифратора 3; код разрешения записи результата вычисления логической функции, который поступает на первый вход элемента И 10; код результата вычисления логической функции, который поступает на информационные входы триггеров группы 11. .Процедура вычисления булевых функций заключается в следующем.

По первой команде программы, находящейся в блоке 2 памяти программ по нулевому адресу и формирующейся на выходах блока 2 памяти программ, когда устройство находится в состоянии ожидания, на первый вход элемента

СУММА ПО МОДУЛЮ ДВА 14 поступает сигнал, соответствующий значению первого опрашиваемого. аргумента первой функции. На второй вход элемента

СУММА ПО МОДУЛЮ ДВА 14 поступает сигнал, соответствующий признаку этого аргумента. Могут иметь место два

1501033 случая: на первый и второй входы элемента СУММЛ ПО МОДУЛЮ ДВА 14 поступают разные сигналы; на первый и второй входы элемента СУ!«МЛ IIO МОДУЛЮ

ДВА 14 поступают одинаковые сигналы.

В первом случае на выходе элемен,та СУММА ПО МОДУЛИ ДВА 14 сформирует ся сигнал "1", ло которому на вторых входах сумматора 16 сформируется код, 1О соответствующий числу 1, а на первые входы сумматора 16 через коммутатор 15 поступит код с выходов триггеров группы 4. Обозначим число, соответствующее этому коду, A. Тогда на выходах сумматора 16 сформируется код, соответствующий числу (A+1).

Во втором случае на выходе элемента СУММА ПО МОДУЛЮ ДВА 14 сформируется сигнал "0", по которому на вторых входах сумматора 16 сформируется нулевой код, а на первые входы сумматора 16 через коммутатор 15 поступит код адреса команды с выходов кода адреса команды блока 2 памяти про- 25 грамм. В этом случае этот же код chop-. мируется и на выходах сумматора 16.

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

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

16, записывается в группу триггеров

4 и формируется на его выходах. По этому коду на выходах блока 2 памяти программ формируется код новой команды. В первом случае это будет код следующей ло порядку команды, но втором — код той команды, которая записана в блоке 2 памяти программ по адресу, равному коду номера команды, записанному в предыдущей команде.При этом, если значение опропжнного ар50 . гумента не полностью определяет значение функции, то по этой команде осуществляется опрос другого аргумента этой же функции, если значение функции полностью определяется значе- 55 нием опрошенного аргумента, то осуществляется запись результата вычисления функции в один из триггеров группы 11 и форин!>Уетс я Tr>a >. T Il T»»рехода к первой Tl(>t!TTTTT! !>: .;>« !:TT! вы— числе ния следующей фулкш.и. Это Tlpnl!еходит следующим обр,l 1,1. „>;л. ь рсЗУЛЬтата ОСУЩЕСтн T«eтo>T Л> ОДНОМУ ИЗ тактовых входов группы три веров 11.

Результат вычисления посту лет из блока 2 памяти программ, номер тактового входа определяется кодом адреса результата, который поступаеT ТТа адресные входы дешифратора 3 из блока

2 памяти программ. Дешифратор 3 стробируется импульсом, формируемым по отрицательному фронту тактового импульса формирователем 9 импульс н.

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

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

1, который соединен с шиной 17 логического нуля. В поле признака аргумента записывается сигнал "О", в лоле адреса команды записывается код адреса команды, ло которой производится опрос и анализ первого аргумента следующей функции. После вычисления всех логических функций устройство может опять перейти к вычислению первой функции. Для этого в поле адреса команды двух последних команд программы необходимо записать адреса первой команды программы. Кроме этого, устройство может прекратить вычисления, для чего в лоле адреса команды двух последних команд программы вычисления записывается код адреса дополнительной "пустой" команды в поле адреса опрашиваемого аргумента которой записывается адрес константы "0", в поле адреса ксианды— адрес ее самой, в поле признака аргумента — "0". Тогда устройство будет постоянно выполнять эту команду до перевода его в состояние ожидания сигналом с входа 6.

Для примера и пояснения работы устройства, а также способа его программирования в таблице представлена программа вычисления двух функций, 1501033 рассмотренных в описании устройствапрототипа

Х (Х,V Х (Х 4Х Х ) V Х Х

Х Х V 7 Х (Х Ч Х,).

Для составления программы вычисления этих функций необходи ° î построить блок-схему алгоритма бинарной программы вычисления, которая представлена на фиг. 2а. Далее необходимо перейти к линейной блок-схеме алгоритма бинарной программы (к линейному бинарному графу — ЛБГ), которая показана на фиг. 2о. Для этого все аргументы функции записываются в линию в том порядке, в котором они стоят в блок-схеме алгоритма бинарной программы.

По этой линии фиксируются единичные переходы от аргумента к аргументу.

Далее, в блок-схеме алгоритма бинарной программы переход от Х; к Х осуществляется по нулевому значению

X, в ЛБГ аргумент Х; берется с отрицанием. Остальные переходы, переходы по нулевому значению аргументов, строятся в соответствии с блок-схемой алгоритма бинарной программы с учетом проставленных инверсий.

Составление программы вычисления производится следующим образом:

1) в столбец 1 аблицы "Код адреса аргумента" записываются коды адресов аргументов первой функции в том порядке, в котором эти аргументы расположены в ЛБГ;

2) в каждую строку столбца таблицы "Признак аргумента записывается

"1", если аргумент, код адреса которого записан в этой строке, входит 40 в ЛБГ с инверсией, в противном случае записывается "0";

3) в каждую строку столбца "Код адреса команды" записывается код адреса той команды, к выполнению кото- 45 рой необходимо перейти по нулевому значению выражения, стоящего в соответствующей этой строке вершине ЛБГ;

4) в каждую строку столбца "Разрешение записи результата записывается "0";

5) что будет записано в столбцах

"Результат вычисления" и "Адрес результата" значения не имеет;. б) в следу зщей по порядку строке записывается команда записи результата вычисления функции по единичному значению выражения, стоящего в последней вершине ЛБГ первой функции, далее записывается команда записи противоположного результата;

7) в последующих строках таким же образом формируется программа вычисления второй функции и т.д. ,Отметим особенности формирования команд записи результата. В поле адреса аргумента этих команд записывается адрес константы "О", в поле 1Признак аргументап — тоже "О", в поле "Код адреса команды — код номера команды, следующей за этими командами, или, если необходимо после их выполнения организовать циклическое выполнение всей программы, нулевой код (т.е. начальной команды). В поле "Адрес результата" заносится код номера функции, в поле "Результат вычисления" — соответствующий результат, в поле "Разрешение записи" — "1".

Вычисления указанных функций при значениях аргументов Х = 1; Х1 = 0;

Х вЂ” 1;.:«-О; ) =1; Xg-1;

Х, = 0 состоит в следующем.

При нулевом коде на адресном входе блока 2 памяти программ производится опрос аргумента Х, входящего в первую функцию. Поскольку Х„ = 1, то на выходе сумматора 16 сформируется код

00001, этот же код сформируется на выходах группы триггеров 4 по положительному фронту первого тактового импульса.

По адресу 00001 в блоке 2 памяти программ записана команды Р 2, по этой команде будет анализироваться значение аргумента Х,. Так как Х, = 1, то следующей будет выполняться команда, код адреса которой равен 00001+

00001 = 00010 (суммирование производится в двоичном коде), т.е ° команда

Р 3. По этой команде анализируется значение Х, так как Х = 1, то код адреса следующей команды равен 00010+

00001 = 00011, т.е. будет выполняться команда Р 4, Поскольку значение аргумента Хт = 0 и, следовательно, Х = 1, то код адреса следующей команды 00011+

0001+=00100, т.е. на следующем такте будет выполняться команда Р 5 и анализироваться аргумент Х . Так как

Х = 1 и входит в ЛБГ с инверсией, то на, этом такте на выходе элемента СУММА

ПО МОДУЛЮ ДВА 14 сформируется сигнал

"0". По этому сигналу на первые входы сумматора 16 через коммутатор 15 поступит код с выходов кода адреса команды блока 2 памяти программ, т.е.

1501033!

О код 01000, При этом «а вторых входах сумматора 16 сформируется код 00000„ а на выходах, следовательно, код

01000, т.е. код адреса команды № 9, которая и будет выполняться на следующем такте работы, По этой команде осуществляется запись результата

Y = О по адресу j = 0 в группе триггеров 11. При этом на информационных входах группы триггеров 4 сформируется код 01010 — код адреса команды, которая будет выполняться на следующем такте. Зто команда ¹ 11 — первая команда программы вычисления функции

Y F. По этой команде производится анализ переменной Х, так как Х, = О, то осуществляется переход к команде № 13, по которой осуществляется анализ Х . Поскольку Ху = 1, то осуществляется переход к следующей по порядку команде, т.е, к команде - 14.

По команде № 14 проводится анализ переменной Х„ и, поскольку Х, = О, осуществляется переход к команде, код номера которой 10000, это код команды № 17, по этой команде осуществляется запись результата Т„ = 0 по адресу j = 1 и формируется код адреса первой команды программы 00000.

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

Код Код раз- У;

j реш,эаписи

ПризКод адреса команКод адре са ды нак

Х;

V л1 ды

1 00000 Х 0 0000

2 00001 Х, 0001

3 00010 Х, 0110 формула изобретения рого соединеч с выходом эдеме.нта И, первый вход которого соединен с выходом разрешения записи результата блока памяти программ, второй вход элемента И соединен с выходом формирователя импульсов, вход которого соединен с тактовым входом триггера

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

СУММА ПО МОДУЛЮ ДВА, коммутатор и сумматор, причем выход мультиплексора соединен с первым входом элемента

СУММА ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом признака аргументов блока памяти программ, выходы кода адреса условного перехода которого соединены с первыми входами коммутатора, выходы которого соединены с первыми входами сумматора, старшие разряды вторых входов которого соединены с вторым информационным входом мультиплексора и с шиной логического нуля, вход младшего разряда вторых входов сумматора соединен с выходом элемента СУММА ПО МОДУЛЮ

ДВА и с управляющим входом коммутатора, вторые входы которого соединены с выходами триггеров первой группы, информационные входы которых соединены с выходами сумматора.

0 01000 0

1 01001 * 0

0 00100 * 0

15() !().33!

Продолжение тлблнны

К" кс- Код

<

Про1 рлммл вычисления лог.функднй руемый аргумент

Х, млнды комли

< ды

Код

НриэКод

Код разреш.заКод

<1дpе и

<< ды Разряд может принимать любое. значение. а) Составитель M,Kàóëü

Редактор О.Спесивых Техред Л.Олийнык Корректор Н.Борисова

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

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина,!01

5

7

9

11

12

13

14

16

17

00011

00101

00111

01001

01011

01101

01111

10001 хт

"2

ХЗ . 5

Х4

"0" н0н х

Х

X g

ХО хв

Хт

"0" ион

0111

0011

0101

1111

1111

0001

1001

0111

1111

1111

1

О

О

О

О

О

О

О

О.

О

О

01001

01001

01001

010!О

10001

01 110

10001

00000

О *

О *

* 0 *

* О *

* 0 *

0 1 О

О 1 1

* О *

О *

* 0 *

* 0 *

* О *

0 *

1 1 0

1 1 1