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

 

СОКИ СОВЕТСКИХ

СОЩ1АЛИСТИЧЕСНИХ PECflVSllHH

ÄÄSUÄÄ 1644126 А } (51)5 G 06 F 7/00

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4627535/24 (22) 29. 12. 89 (46) 23.04. 91. Бюл. М - 15 (72) В. С. Астафьев, Ф. С. Соснин и С.M. Ше стиме ров (53) 681 ° 3 (088. 8) (56) Авторское свидетельство СССР

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

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

У 1032451, кл. G 06 F 7/00, 1982. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИСТЕМ

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

Цель изобретения - повышение быстродействия устройства. Устройство содержит регистр 1 аргументов, две

2 группы блоков 2 -2 и 31-3п, памяти констант, где n — количество входных переменных; m — количество выходных переменных, элемент ИЛИ 4, блок 5 ассоциативной памяти, регистр 6, блок 7 управления, счетчик 8, группу

9 информационных входов, группу 10 информационных выходов, вход 11 запуска устройства. В первую и вторую группы блоков. памяти констант заносится информация о всех элементарных конъюнкциях, которые встречаются в записях уравнений, представленных в дизъюнктивной нормальной форме (ДНФ).

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

1 ил. 5 табл.

1644126

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

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

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

Устройство содержит регистр 1 аргументов, две группы блоков 2 ...2, и 31... З„памяти констант, элемент

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

В каждый терм конкретного блока

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

О, если i-я входная переменная или

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

1 если i-я входная переменная или

j "я выходная пе реме иная входит в данную конъюнкцию беэ отрицания;

Х- безразличное состояние, если

i"ÿ выходная переменная или j-я выходная переменная не входят в

55 данную конъюнкцию.

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

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

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

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

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

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

Сигнал с выхода элемента ИЛИ 4 поступает на управляющий вход блока

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

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

Y1=X1X2 ХЗ ч Х1 Х4 У2 ч Х5 Хб

У2 YÇ;

Y2 = Х1 Х2 X5 v ХЗ Т1 УЗ.У4 ч

v Х2 Х4 Y1 v X5 Хб У1 УЗ;

Y3= Х4Х6Y2v Х5 Y1Y2У4 v ч ХЗ Х4 Хб;

У4 Х1 Х2ХЗч Х1 Х2 Х4Х5 Хб, 29 те. п=б; m=4; r=4, гдеп— число входных переменных, m - число выходных переменных, Г - максимальное число конъюнкций входящих в одно уравнение. Количество входов блоков . 25

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

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

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

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

Термы для блока 2.1 памяти констант приведены в табл. i термы для блока 2,2 памяти констант приведены

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

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

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

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

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

Та блица 1 регистра соединены с выходом устройства и со старели разрядами адресНомер терма

Выходы

Адресные входы

Входные переменные

Х1 Х2 ХЗ Х4 Х5 Хб

В2

Номер ДНФ

В1 а1 а2

1 1 1 1 X X X 0

2 t Х Х О Х Х 0

3 0 0 X Х. 1 X 1

4 Х Х 1 Х Х Х 1

5 Х Х Х 1 Х 1 0 б Х Х Х Х 1 Х 0

7 0 0 X 0 0 0

Таблица 2

Выходы

Номер терма

Адресные входы

Входные пе еменные Номер ДНФ

Х1 Х2 ХЗ Х4 Х5 Хб а1 а2 ВЗ В4

0 0 1 0

1 0 1 0

1 0 0 1

0 1 1 0

1 X Х Х Х 1 1

2 Х 1 Х 1 Х Х

3 Х Х Х Х 1 0

4 Х Х 1 1 Х 1

Таблица. 3

Номер терма

Выходы

Адресные входы

Номер ДЦФ а1 а2

В1 В2

Выходные переменные

T1 T

У1 У2 У3 74

0 0 1 0

0 0 0 1

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 1

1 1 0 1

Таблйца 4

Адресные входы

Выходные переменные омер ДНФ В1 В2 а2

Выходы

Номер терма

У3 . Y4 . а1

У1 У2

О X 0 0 1 0

Х Х 1 0 1 0

1 Х .1 0 0 1

X Х 0 1 1 0

П р и м е ч а н и е: Х вЂ”, безразличное состояние..1 Х

2 Х

3 Х

4 0

5 Х

6 0

7 Х

1 Х

2 1

4 Х

Х Х Х

Х Х

Х Х Х

X 0 0

1 Х Х

0 Х 1

Х Х Х

Х

Х

0

0

1

1 0

0 1

1 0

0 1

1 0

0 1

О 1

1644126

Таблица5

Адресные входы.

Выходы

Номер Управлятерма ющий вход

Входные переменные

1 В2 ВЗ

Номер ДНФ

01 02 03

В В4 а1 а2

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

Составитель В. Сорокин

Редактор Е. Папп Техред Л. Сердюкова Корректор Л. Бескид

Закаэ 1241 Тираж 401 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Ужгород, ул. Гагарина, 101

1 1 1

2 1 О

3 1 О

4 1 1

5 1 О

6 1 О

7 1 О

8 1 1

9 1 О

10 1 0

11 1

О 1

О

1

О

О

О

О О

О О

О

О О

О О

О

О

О О

О О

1 О

О О

О О

О О

О О

1 О

1 О

1 О

О

О 1

О 1

О 1

1 1

1 0

1 О

1 О

О 1

О 1

О 1

О 1

О О

О О

О О

О О

О 1

О О

О О

О О

О О

О О

О О

О

1 О

1 О

О 1