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

Изобретение относится к автоматике и цифровой вычислительной технике и может быть использовано в системах контроля и управления, а также для моделирования различных объектов, функционирование которых описывается системой булевых функций.Цель изобретения - повышение быстродействия устройства1 ОНа чертеже приведена структурная схема устройства для вычисления систем булевых .функций.Устройство содержит регистр 1 аргументов, две группы блоков 2 12, и 31 3 памяти констант, элемент ИЛИ 4, блок 5 ассоциативной памяти, регистр 6, блок 7 управления, счетчик 8, группу 9 информационных входов, группу 10 информационных выходов, вход 11 запуска устройства. В первую и вторую группы блоков 2, ,2 в и 33 п,памяти констант (и - количество входных переменных; ш - количество выходных переменных) записана информация; о всех элементарных конъюнкциях, которые встречаются в записях уравнений, представленных в дизъюнктивной нормальной форме (ДНФ). При этом независимо от того, в записях какого числа функций встречается та или иная коньюнкция, информация о ней записывается только в одну иэ ДНФ, реализуемых устройством булевых функций. В каждый терм конкретного блока : памяти констант записывается информация об одной конъюнкции или части ее (если число независимых переменных конъюнкции превышает число адресных входов блока памяти констант), а также номер функции, в которую входит данная конъюнкция. Запись информации в терм производится согласно следующему правилу:15О, если 1-я входная переменная или1-я выходная переменная входитв данную конъюнкцию с отрицанием;1 если -я входная переменная или501 "я выходная переменная входитв данную конъюнкцию беэ отрицания;Х- безразличное состояние, если1"я выходная переменная или 1-явыходная переменная не входят в55данную конъюнкцию.Количество выходов г групп блоков памяти констант зависит от максимального числа конъюнкций, входящих в систему управлейий.Устройство работает следукщим образом.Набор входных сигналов параллельным кодом под управлением сигнала начальной установки, вырабатываемым блоком 7 управления, записывается в регистр 1 аргументов и сохраняется в нем до окончания цикла работы устройства, одновременно с этим происходит установка счетчика 8 в исход" ное состояние (в начале каждого цикла со счетчика 8 на адресные входы групп блоков памяти констант поступает код, укаэывакщий на номер первой функции). С выхода регистра 1 аргументов набор входных сигналов поступает на адресные входы первой группы блоков 22 памяти констант, а на адресные входы второй группы блоков 3Зщ памяти констант с выхода регистра 6 поступает набор предыдущих значений (состояний), вычисляемых устройством функций. В первой и второй группах блоков 2 2 и 33, памяти констант происходит параллельное вычисление значений конъюнкций, входящих в состав уравнения системы, номер которой определяется кодом, поступающим со счетчика 8.Результаты вычислений конъюнкций, входящих в конкретную функцию, с выходом групп блоков памяти констант 212 п и 33 щпоступают на входы элемента ИЛИ 4, на выходе которого формируется сигнал, соответствукщий значению первого уравнения системы, при конкретных значениях входных переменных. Если значение первого уравнения системы равно нулю, то содержимое счетчика 8 увеличивается на единицу и вычисляется значение следующего уравнения.Так происходит до тех пор, пока значение очередной функции не будет равно единице, либо пока не будут вычислены значения всех уравнений, входящих в систему, при данном наборе входных сигналов.Сигнал с выхода элемента ИЛИ 4 поступает на управлящций вход блока 5 ассоциативной памяти и в соответствии с значениями конъюнкций и номером уравнения на выходе блока 5 ассоциативной памяти формируются сигналы соответствующие значениям булевых функций при данном наборе входВ5 16441 ных сигналов. По сигналу конец преобразования, вырабатываемому блоком 7 управления значения функций, записываются в регистр 6 и могут участвовать в дальнейших вычислениях.Предположим, что работа устройства для реализации булевых функций описывается следующей системой буле" вых функций (уравнений):11=Х 1 Х 2 ХЗч Х 1 Х 4 72 ч Х 5 Х 672 ГЗ;72 = Х 1 Х 2 Х 5 ч ХЗ Т 1 ГЗ.Г 4 ч15ч Х 2 Х 4 У 1 ч Х 5 Х 6 11 УЗ;73 = Х 4 Х 6 12 ч Х 5 У 1 72 У 4 чч ХЗ Х 4 Х 6;У 4Х 1 Х 2 ХЗ ч Х 1 Х 2 Х 4 Х 5 Х 6, 29 те. п=6; в=4; г=4, гдеп -число входных переменных, ш - числовыходных переменных, Г - максимальноечисло конъюнкций входящих в одноуравнение. Количество входов блоков. 252 иЗг (з = 1,п, Т= 1, т) памятиконстант зависит от максимальногочисла конъюнкций, входящих в одно изуравнений, пусть блоки памяти констант, входящие в группы, имеют подва выхода, следовательно, данныйпример реализуется при помощи четые рех блоков памяти констант,В данном примере уравнение с нулевым номером (функция 71) и третье 35уравнение (функция У 4) содержат одинаковую конъюнкцию Х 1 Х 2 ХЗ, т,е.достаточно записать соответствующуюконстанту в один блок памяти констант,а из третьего уравнения исключается 40первая конъюнкция Х 1 Х 2 ХЗ. Ассоциативная память 5 запрограммированатаким образом, что на ее выходах,соответствующих значениям функции71 и У 4, имеют место сигналы логической "1", в случае, если конъюнкция Х 1 Х 2 ХЗ нулевого уравнения принимает значение Лог. "1".В первую группу блоков памяти констант (для данного примера - 2. 1 50и 2.2) записываются значения входныхпеременных, которые входят в искомыеконъюнкции, а во вторую (для данногопримера - 3, 1 и 3,2) - значения вы"ходных переменных, которые входят в 55искомые конъюнкции.Термы для блока 2,1 памяти констант приведены в табл. 1, термы дляблока 2,2 памяти констант приведены 26 4в табл. 2, термы для блока 3,1 памяти констант приведены в табл. 3, термы для блока 3.2 памяти констант приведены в табл. 4. В табл. 5 приведены значения на входах и выходах блока 5 ассоциативной памяти. Формула изо бре тения Устройство для вычисления систем булевых функций, содержащее регистр аргументов, блок ассоциативной памяти, блок управления, регистр, счетчик и элемент ИЛИ;причем информационные входы группы устройства соединены с информационными входами регистра аргументов, тактовый вход которого соединен с входом установки в "О" счет" чика, первым тактовым выходом блока управления, вход запуска которого со" единен с входом запуска устройства, выход признака конца преобразования блока управления соединен с тактовым входом регистра, информационные, входы которого соединены с выходами блока ассоциативной памяти, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит две группы блоков памяти констант, 1-й выход 1-го блока памяти констант первой группы соединен с 1-м выходом р-го блока памяти констант второй группы (ь=1, г; 1 = 1,п; р = 1,щ; где и ш: г - максимальное число выходов блока памяти констант, п - число блоков памяти констант, необходимых для записи всех конъюнкций, входящих в систему, ш - число блоков памяти, необходимых для записи всех выходных переменных), со старшими разрядами входа признака блока ассоциативной памяти и с входами элемента ИЛИ, выход которого соединен с входом признака конца преобразований блок а управле ния и входом раз решения считывания блока ассоциативной памяти, младшие разряды входа признака которого соединены с младшими разрядами адресных входов блоков памяти констант групп и выходом счетчика, счетный вход которого соединен с вторым тактовым выходом блока управления, третий тактовый выход которого соединен с входом разрешения считывания блоков памяти констант групп, старшие разряды адресных входов первой группы которых соединены с выходом регистра аргументов, выходы1644126 ных входов блоков памяти константвторой группа.Та блица 1 регистра соединены с выходом устройства и со старели разрядами адресНомер терма Выходы Адресные входы Входные переменныеХ 1 Х 2 ХЗ Х 4 Х 5 Х 6 В 2 Номер ДНФ В 1 а 1 а 2 1 1 1 1 Х Х Х 0 2 1 Х Х О Х Х О 3 0 0 Х Х. 1 Х 1 4 Х Х 1 Х Х Х 1 5 Х Х Х 1 Х 1 0 6 Х Х Х Х 1 Х 0 7 0 0 Х О 0 0 1 Таблица 2 Выходы7 Номер терма Адресные входы Входные пе еменные Номер ДНФ РХ 1 Х 2 ХЗ Х 4 Х 5 Х 6 а 1 а 2 ВЗ В 4 0 0 1 0 1 0 1 0 1 0 01 0 1 1 0 1 Х Х Х Х 1 1 2 Х 1 Х 1 Х Х 3 Х Х Х Х 1 О 4 Х Х 1 1 Х 1 Таблица. 3 Номер терма Выхода Адресные входы Номер ДЦФа 1 а 2 В 1 В 2 Выходные переменные Т 1 Т 71 72 73 74 0 0 1 0 0 0 0 1 1 0 1 0 1 0 О 1 0 1 1 0 0 1 0 1 1 1 0 1 Таблйца 4Адресные входыВыходные переменные омер ДНФ В 1 В 2а 2 Выходы Номер терма УЗ . У 4 а 1 71 72 О Х, 0 01 0 Х Х 1 0 1 0 1 Х .1 0 0 1 Х Х 0 1 1 0 П р и м е ч а н и е: Х - , безразличное состояние.1644126 Таблица 5 Ацресные входы Выходы Номер Управлятерма ющий вход Входные переменные1 В 2 ВЗ Номер ДНФ 01 02 03 04 В В 4 а 1 а 2 П р и м е ч а н и е: Во всех остальных ячейках ассоциативной памяти 5 записаны "Лог".О". Составитель В, СорокинРедактор Е. Папп Техред Л. Сердюкова Корректор Л. Бескид Закаэ 1241 Тираж 401 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, -35, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина, 101 1 1 1 2 1 0 3 1 0 4 1 1 5 1 0 6 1 0 7 1 0 8 1 1 9 1 0 10 1 0 11 1 0 0 1 0 О 1 0 0 0 1 0 1 0 О 0 0 1 0 0 О 0 0 1 О 0 0 0 0 0 1 О 0 0 0 0 0 О 0 0 1 0 1 0 1 00 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 0 1 01 0 0 0 0 0 0 0 0 0 1 0 О 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1