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

i

(21)4627535/24

(22)29.12.89

(46) 23.04.91. Бюл. № 15 (72) В.С.Астафьев, Ф.СоСоснин и С.М.Шестимеров

(53)681.3(088.8)

(56)Авторское свидетельство СССР

№ 1532912, кл. G 06 F 7/00,25.10.88.

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

(54)УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ

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

группы блоков 21 -2h и 31-3т памяти констант, где п - количество входных переменных; га - количество выходных переменных , элемент ИЛИ 4, блок 5 ассоциативной памяти, регистр 6, блок 7 управления, счетчик 8, группу 9 информационных входов, группу 10 информационных выходов, вход 11 запуска устройства. В первую и вторую группы блоков памяти констант заносится информация о всех элементарных конъюнкциях, которые встречаются в записях уравнений, представленных в дизъюнктивной нормальной форме (ДНФ). Набор входных сигналов записывается в регистр аргументов и сохраняется до конца вычисления. Процесс вычисления прекращается либо пока значение очередной функции не будет равно единице,либо пока не будут вычислены значения всех уравнений системы. 1 ил. 5 табл.

I

(Л

с

с&

4 4

1C

С

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

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

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

Устройство содержит регистр 1 аргументов, две группы блоков 2. ..2 и 3... Зт памяти констант, элемент ИЛИ 4, блок 5 ассоциативной памяти, регистр 6, блок 7 управления, счетчик 8, группу 9 информационных вХо- дов, группу 10 информационных выхо- дов, вход 11 запуска устройства. В первую и вторую группы блоков 24...2П и 3(...3mпамяти констант (п - количество входных переменных; m - количество выходных переменных) записана информаци о всех элементарных конъюнкциях,которые встречаются в записях уравнений, представленных в дизъюнктивной нормальной форме (ДНФ). При этом независимо от того, в записях какого числа функций встречается та или иная конъюнкция, информация о ней записывается только в одну из ДНФ, реализуемых устройством булевых функций.

В каждый терм конкретного блока памяти констант записывается информация об одной конъюнкции или части ее (если число независимых переменных конъюнкции превышает число адресных входов блока памяти констант), а такж номер функции, в которую входит данная конъюнкция. Запись информации в терм производится согласно следующему правилу:

0,если i-я входная переменная или j-я выходная переменная входит в данную конъюнкцию с отрицанием;

1,если i-я входная переменная или j-я выходная переменная входит в данную конъюнкцию без отрицания;

Х-безразличное состояние, если i-я выходная переменная или j-я выходная переменная не входят в данную конъюнкцию.

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

.

0

Q

0

0

5

ного числа конъюнкций, входящих в систему управлений.

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

Набор входных сигналов параллельным кодом под управлением сигнала начальной установки, вырабатываемым блоком 7 управления, записывается в регистр 1 аргументов и сохраняется в нем до окончания цикла работы устройства, одновременно с этим происходит установка счетчика 8 в исходное состояние (в начале каждого цикла со счетчика 8 на адресные входы групп блоков памяти констант поступает код, указывающий на номер первой функции).С выхода регистра 1 аргументов набор входных сигналов поступает на адресные входы первой группы блоков 2j.. .2 памяти констант, а на адресные входы второй группы блоков 3... Зт памяти констант с выхода регистра 6 поступает набор предыдущих значений (состояний), вычисляемых устройством функций. В первой и второй группах блоков 2( .. .2 и 3 ,... 3, памяти констант происходит параллельное вычисление значений конъюнкций, входящих в состав уравнения системы, номер которой определяется кодом, поступающим со счетчика 8.

Результаты вычислений конъюнкций, входящих в конкретную функцию, с выходом групп блоков памяти констант 2t...2n и 3{... Эру, поступают на входы элемента ИЛИ 4, на выходе которого формируется сигнал, соответствующий значению первого уравнения системы, при конкретных значениях входных переменных. Если значение первого уравнения системы равно нулю, то содержимое счетчика 8 увеличивается на единицу и вычисляется значение следующего уравнения.

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

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

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

Y1 X1X2 X3vX1 XU Y2 v Х5 Х6 Y2 Y3;

Y2 XI Х2 Х5 v ХЗ Tl Y3.Y4 v v Х2 Х4 Y1 v Х5 Х6 Y1 Y3;

Y3 Х4 Х6 Y2 v Х5 Y1 Y2 Y4 v v ХЗ Х4 Х6;

Y4 XI Х2 ХЗ v Х1 Х2 Х4 Х5 Хб,

т.е.

- 6;

где п m 4; г 4, число входных переменных, m - число выходных переменных, Г - максимальное число конъюнкций входящих в одно уравнение. Количество входов блоков

30

2S и Зт (s 1,n, Т 1, га) памяти констант зависит от максимального числа конъюнкций, входящих в одно из уравнений, пусть блоки памяти констант, входящие в группы, имеют по два выхода, следовательно, данный пример реализуется при помощи четы- рех блоков памяти констант.

В данном примере уравнение с нулевым номером (функция Y1) и третье 35 уравнение (функция Y4) содержат одинаковую конъюнкцию XI Х2 ХЗ, т.е. достаточно записать соответствующую константу в один блок памяти констант, а из третьего уравнения исключается 40 первая конъюнкция Х1 Х2 ХЗ. Ассоциативная память 5 запрограммирована таким образом, что на ее выходах, соответствующих значениям функции Y1 и Y4, имеют место сигналы логи-Д5

ческой 1, в случае, если конъюнкция Х1 Х2 ХЗ нулевого уравнения принимает значение Лог. 1.

В первую группу блоков памяти констант (для данного примера - 2.150 и 2.2) записываются значения входных переменных, которые входят в искомые конъюнкции, а во вторую (для данного примера - 3.1 и 3.2) - значения выходных переменных, которые входят в 55 искомые конъюнкции. Термы для блока 2.1 памяти констант приведены в табл. 1, термы для блока 2.2 памяти констант приведены

0

5

0

5

0

5 0 5

0 5

в табл. 2, термы для блока 3.1 памяти констант приведены в табл. 3, термы для блока 3.2 памяти констант приведены в табл. 4. В табл. 5 приведены значения на входах и выходах блока 5 ассоциативной памяти.

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

Устройство для вычисления систем булевых функций, содержащее регистр аргументов, блок ассоциативной памяти, блок управления, регистр, счетчик и элемент ИЛИ;причем информационные входы группы устройства соединены с информационными входами регистра аргу ментов, тактовый вход которого соединен с входом установки в О счетчика, первым тактовым выходом блока управления, вход запуска которого соединен с входом запуска устройства, выход признака конца преобразования блока управления соединен с тактовым входом регистра, информационные входы которого соединены с выходами блока ассоциативной памяти, отличающееся тем, что, с целью повышения быстродействия, оно содержит две группы блоков памяти констант, i-й выход j-ro блока памяти констант первой группы соединен с i-м выходом р-го блока памяти констант второй группы ( г; j 1,п; р 1,т; где n -m; r - максимальное число выходов блока памяти констант, п - число блоков памяти констант, необходимых для записи всех конъюнкций, входящих в систему, m - число блоков памяти, необходимых для записи всех выходных переменных), со старшими разрядами входа признака блока ассоциативной памяти и с входами элемента ИЛИ, выход которого соединен с входом признака конца преобразований блока управления и входом разрешения считывания блока ассоциативной памяти, младшие разряды входа признака которого соединены с младшими разрядами адресных входов блоков памяти констант групп и выходом счетчика, счетный вход которого соединен с вторым тактовым выходом блока управления, третий тактовый выход которого соединен с входом разрешения считывания блоков памяти констант групп, старшие разряды адресных входов первой группы которых соединены с выходом регистра аргументов, выходы

регистра соединены с выходом устройства и со старшими разрядами адресПриме чание: Х- безразличное состояние.

ных входов блоков памяти констант второй группы.

Таблица 1

Примечание: Во всех остальных ячейках ассоциативной памяти 5

записаны Лог . О.