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

/о

(Л

сд

со со

3,50

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

1033

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

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

10 собой. 2 ил. 1 табл.

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

.

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

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

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

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

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

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

25

30

35

40

45 JQ 55

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

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

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

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

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

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

да адреса команды блока 2 памяти про- 25 результата вычисления, в поле кода грамм. В этом случае этот же код сфор- адреса аргумента записьшается код

30

35

40

мируется и на выходах сумматора 16,

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

50

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

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

пы 11 и формируется Kfi, Vr :IM|. ц.-)1 II 111 рехода к герной ксп пил - прчт р.чмм пы- числе.ния следующей функтпя. Эчо происходит следующим обр.ччиг-. i.-iyin Mi результата осуществияетс .я по олиому из тактовых входов riiyniHii ipnrr-ej nn 1 1 . Результат вычисления поступает на блока 2 памяти программ, номер тактового входа определяется кодом адреса результата, который поступает на адресные входы дешифратора 3 из блока 2 памяти программ. Депгифратор 3 стро- бируется импульсом, формируемым по

отрицательному фронту тактового импульса формирователем 9 импульс.)в. Этот импульс поступает на.стробирую- щий вход дешифратора 3 с ллс- ,мента И 10 при наличии на его первом

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

результата вычисления, в поле кода адреса аргумента записьшается код

30

35

40

5545

50

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

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

рассмотренных в описании устройства- прототипа

YO. X,,(X,V Хг (X,VX4- Xj) V Х X Y, Х. X,VX,. XgCXgVX,.

Для составле}1ия пpoгpaм iЬ .вычисления этих функций необходи о построит блок-схему алгоритма бинарной програмы вычисления, которая представлена на фиг. 2а. Далее необходимо перейти к линейной блок-схеме алгоритма бинарной программы (к линейному бинарному графу - ЛБГ), которая показана на фиг. 25. Для этого все аргументы функции записываются в линию в том порядке, в котором они стоят в блок- схеме алгоритма бинарной программы. По этой линии фиксируются единичные переходы от аргумента к аргументу. Далее, в блок-схеме алгоритма бинарной программы переход от X - к Xj осуществляется по нулевому значению X,, в ЛБГ аргумент Х берется с отрицанием. Остальные переходы, перехо- ды по нулевому значению аргументов, строятся в соответствии с блок-схемой алгоритма бинарной программы с учетом проставленных инверсий.

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

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

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

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

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

5)что будет записано в столбцах Результат вычисления и Адрес результата значения не имеет;

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

0

0

0

5

0

5

g

5

далее записывается команда записи противоположного результата;

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

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

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

6 2 1 j 9 1 5 X Q О состоит в следующем.

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

По адресу 00001 в блоке 2 памяти программ записана команды № 2, по этой команде будет анализироваться значение аргумента X,. Так как Х 1, то следующей будет вьшолняться команда, код адреса которой равен 000014 00001 00010 (суммирование производится в двоичном коде), т.е. команда № 3. По этой команде анализируется значение Х, так как Х 1, то код

адреса следующей команды равен 00010-i- 00001 00011, т.е. будет выполняться команда № 4. Поскольку значение аргумента Х О и, следовательно, 1 , то код адреса следующей команды 0001 1 + 0001- - 00100, т.е. на следующем такте будет выполняться команда № 5 и анализироваться аргумент Х. Так как Xj 1 и входит в ЛБГ с инверсией, то н.а. этом такте на выходе элемента СУММА ПО МОДУЛЮ ДВА 14 сформируется сигнал О. По этому сигналу на первые входы сумматора 16 через коммутатор 15 поступит код с выходов кода адреса команды блока 2 памяти программ, т.е.

код 01000. При этом на вторых входах сумматора 16 сформируется код 00000, а на выходах, следовательно, код 01000, т.е. код адреса команды № 9, которая и будет выполняться на следующем такте работы. По этой команде осуществляется запись результата YO О по адресу j О в группе триггеров 11. При этом на информационных входах группы триггеров 4 сформируется код 01010 - код адреса команды, которая будет выполняться на следующем такте. Это команда № 11 - первая команда программы вычисления функции Y. По этой команде производится анализ переменной X , так как X , О, то осуществляется переход к команде № 13, по которой осуществляется анализ Хд. Поскольку Хд 1, ТО осутце- ствляется переход к следующей по порядку команде, т.е. к команде № 14. По команде № 14 проводится анализ переменной Х и, поскольку О, осуществляется переход к команде, код номера которой 10000, это код команды № 17, по этой команде осуществляется запись результата Y О по адресу j 1 и формируется код адреса первой команды программы 00000.

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

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

5

0

5

рого соединен с выходом И, первьп вход которого соединен с выходом разрешения записи результата блока памяти программ, второй вход элемента И соединен с выходом формирователя импульсов, вход которого соединен с тактовым входом триггера и выходом элемента НЕ, вход которого соединен с тактовьпч входом устройства и тактовьми входами тригге- ров первой группы, установочные входы которых соединены с выходом триггера, информационный вход которого соединен с входом начальной установки устройства, выходы которого соединены с выходами триггеров второй группы, тактовые входы которых соединены с выходами дешифратора, а информационные входы триггеров второй группы соединены с выходом значения результата блока памяти программ, адресные входы которого соединены с выходами триггеров первой группы, отличающееся тем, что, с целью упрощения за счет сокращения объема памяти, оно содержит элемент СУММА ПО МОДУЛЮ ДВА, коммутатор и сумматор, причем выход мультиплексора соединен с первым входом элемента СУММА ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом признака аргументов блока памяти программ, выходы кода адреса условного перехода которого соединены с первыг-ш входами коммутатора, выходы которого соединены с первыми входами сумматора, старшие разряды вторых входов которого соединены с вторьм информационным входом мультиплексора и с 1Ш1Ной логического нуля, вход младшего разряда вторых входов сумматора соединен с выходом элемента СУММА ПО МОДУЛЮ ДВА и с управляющим входом коммутатора, вторые входы которого соединены с выходами триггеров первой группы, информационные входы которых соединены с выходами сумматора..

11

-X Разряд может принимать любое значение.

1 fe fffJ

V f n t г i 4. t

I 2 Продолжение таблицы

Ч у