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

3. Устройство поп, 1, отличающееся тем, что блок управления содержит генератор сйнхроипульсов,счетчик,первый и второй триггры,дешифратор,пять элементов И ишесть элементов ИЛИ, причем входы Лервого элемента И соединены с инверсными выходами счетчика, вход первого элемента ИЛИ соединен с первым входом блока управления, первый вход второг элемента И подключен к второму эходу блока, второй вход - к первому ВЫХОДУ-дешифратора, а выход - к Первому .выходу блока, первый вход второго элемента ИЛИ подключен к Второму выходу дешифратора, второй вход - к четвертому выходу дешифратора, а выход - к второму выходу блока,вход третьего элемента ИЛИ соединен с выходом первого элемента И, первый вход третьего элеNjeHTa И подключен к третьему выходу дешифратора, второй вход - к ин- версному выходу первого элемента ИЛИ, третий вход - к инверсному выkoдy третьего элемента ИЛИ, а выход - к третьему выходу блока, первый вход четвертого элемента И подключен к третьему выходу дешифратора, второй вход - к инверсному выходу первого элемента ИЛИ, третий вход - к выходу первого элемента И, первый вход пятого элемента И подключен к третьему выходу дешифратора, второй вход - к первому входу блока, первый вход четвертого элемента ИЛИ подключен к выходу четвертого элемента И, второй вход - к выходу пятого элемента И, а выход к четвертому выходу блока, первый вход пятого элемента ИЛИ подключен к второму выходу дешифратора, второ вход - к выходу четвертого элемента ИЛИ, а выход - к счетноГ1у входу первого триггера, первый вход шестого элемента ИЛИ подключен к выходу второго элемента И, второй вход к выходу второго элемента ИЛИ, третий вход - к выходу третьего элемента И, а выход - к счетному входу второго триггера, первый прямой вход дешифратора подключен к прямому выходу первого триггера, первы инверсный вход - к инверсному выходу первого триггера, второй прямой вход - к прямому выходу второго триггера, второй инверсный вход к инверсному выходу второго триггера, информационные входы счетчика подключены к третьим входам блока, вычитающий вход - к выходу второго элемента ИЛИ, управляющий вход - к выходу второго элемента И, выход генератора синхроимпульсов соединен ,с синхровходами первого и второго триггеров и дешифратора.

1. УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БУЯЕИЛХ ФУНКЦИЙ, содержащее блок управления, элементы ИЛИ, элемент И, входы которого соединены с выходами элементов ИЛИ, отличающееся тем, что, с целью повышения быстродействия, в него введены блок памяти адресов, блок ассоциативной памяти, первый регистр, второй регистр, третий регистр, четыре группы схем сравнения, счетчик и дешифратор, причем входы первого регистра соединены с входами устройства, информационные входы второго регистра соединены с выходами блока ассоциативной памяти, первые входы схем сравнения первой группы подключены к первой группе выходов блока памяти адресов, вторые входы - к прямым выходам первого регистра, а выходы - к первым входам элементов ИЛИ первой группы, первые входы схем сравнения второй группы подключены к второй группе выходов блока памяти адресов, вторые входы к прякым выходам второго регистра, а выходы - к первым входам элементов ИЛИ второй группы, первые входы схем сравнения третьей группы подключены к третьей группе выходов бло ка памяти адресов, вторые входы - к инверсным выходам первого регистра, а выходы - к вторым входам элементов ИЛИ первой группы. Первые входы схем сравнения четвертой группы подключены к четвертой группе выходов блока памяти адресов, вторые входы - к инверсным выходам второго регистра, а выходы - к вторым входам элементов ИЛИ второй группы, входы элемента И соединены с выходами элементов ИЛИ первой и второй групп, первые информационные входы третьего регистра подключены к выходу элемента И, вторые информационные входы - к выходам дешифратора, а выходы - к информационным входам блока ассоциативной памяти, выходы счетчика соединены с адресными входами блока памяти адресов и входами дешифратора, первый вход блока уп(Л равления подключен к выходу элемента и, второй вход.- к входу пуска устройства, третий вход - к установочному входу устройства, первый выход - к управляющим входам первого и третьего регистров и к установочному входу счетчика, второй выход к управляющему входу блока памяти адресов, третий выход - к счетному входу счетчика, четвертый выход к управлякнцим входам второго регистсо ю ра и блока ассоциативной памяти, а с выходами устройства соединены пря4i мые выходы второго регистра, 2. Устройство по п. 1, отлисл чающееся тем, что блок ассоциативной памяти содержит регистры, элементы И и элементы ИЛИ, причем прямые выходы каждого регистра соединены с первыми входами соответствующих элементов И, выходы которых соединены с входами соответствующего элемента ИЛИ, выходы элементов ИЛИ являются вьЕсодами блока, информационные входы блока соединены с вторыми входами соответствующих элементов И, третьи входы элементов И подключены к управляющему входу блока.

Изобретение относится к вычислительной технике и может быть использовано для управления технологическим оборудованием, функционирование которого описывается системой булевых функций, а также для моделирования цифровых устройств. Известно устройство для моделирования конечных автоматов, содержащее блок памяти, мультиплексор, сумматор по модулю два, блок вычисления булевых функций, первый и второй дешифраторы, первый и второй регистры l} Недостатком устройства является низкое быстродействие, ввиду того, Что вычисление значений булевых функ ций в устройстве осуществляется путем последовательной подачи значений переменных, их кодов и кодов служебных символов на входы блока вычисления булевых функций. Наиболее близким к предлагаемому по технической сущности является логический автомат, содержащий блок ввода переменных, блок памяти, блок задержек, программоноситель с вентилями, элемент И, элементы ИЛИ и НЕ блок вывода 2 . Однако данное устройство характеризуется низким быстродействием, обусловленным тем, что в процессе работы автомата производится вычисление всех без исключения элементарных конъюнкций,входящих в систему реализуемых автоматом логических функций. Цель изобретения - повышение быстродействия . Указанная цель достигается тем, что в устройство, содержащее блок управления, элементы, ИЛИ, элемент И, входы которого соединены с выходами элементов ИЛИ, введены блок памяти адресов, блок ассоциативной памяти, первый регистр, второй регистр, третий регистр, четыре группы схем сравнения, счетчик и Дешифратор, причем входы первого регистра соединены с входами устройства, информационные входы второго регистра соединены с выходами блока ассоциативной памяти, первые входы схем сравнения первой группы подключены к первой группе выходов блока памяти адресов, вторые входы - к прямым выходам первого регистра, а выходы - к первым входам элементов ИЛИ первой группы, первые входы схем сравнения второй группы подключены к второй группе выходов блока памяти адресов, вторые входы - к прямым выхо дам второго регистра, а выходы - к первым входам элементов ИЛИ второй группы, первые входы схем сравнения третьей группы подключены ft третьей группе выходов блока памяти адресов вторые входы к инверюным выхо- дам первого регистра, а выходы к вторым входам элементов ИЛИ перво группы, первые входы схем сравнения четвертой группы подключены к четвер той группе выходов блока памяти адресов, вторые входы - к инверсным выходам второго регистра, а выходы к вторым входам элементов ИЛИ второй группы, входы элемента И соединены с выходами элементов ИЛИ первой и второй групп, первые информационные входы Третьего регистра подключены к выходу элемента И, вторые информационные входы - к выходам дешифратора, а Выходы - к информационным входам блока ассоциативной памяти, выходы счетчика соединены с адресными входами блока памяти адресов и входами дешифратора, первый вход блока управления подключен к выходу элемента И, второй вход - к входу пуска устройства, третий вход - к установочному входу устройства, первый выход - к управляющим входам первого и третьего регистров и к установочному входу счетчика, второй выход к управляющему входу блока памяти адресов, третий выход - к счетному входу счетчика, четвертый выход к управляющим входам второго регистра и блока ассоциативной памяти, а ,с выходами устройства соединены прямые выходы второго регистра. Блок ассоциативной памяти содержит регистры, элементы И и элементы ИЛИ, причем прямые выходы каждого регистра соединены с первыми входами соответствующих элементов И, выходы которых соединены с входами соответствующего элемента ИЛИ, выходы элементов ИЛИ являются выходами блока, информационные входы блока соединены С вторыми входами соответствукяцих элементов и, третьи входы элементов И подключены к управляющему входу блока. Блок управления содержит генерато синхроимпульсов, счетчик, первый и второй триггеры, дешифратор, пять .элементов И и шесть элементов ИЛИ, причем входы первого элемента И соединены с инверсными выходами счетчика, вход первого элемента ИЛИ соединен с первым входом блока управления, первый вход второго элемента И подключен к второму входу блока, второй вход - к первому выходу дешифратора, а выход - к первому выходу блока, первый вход второго элемента ИЛИ подключен к второму выходу дешифратора, второй вход - к четвертому выходу дешифратора, а выход - к второму выходу блока, вход третьего элемента ИЛИ соединен с выходом первого элемента И, первый вход третьего элемента И подключен к третье- му выходу дешифратора, второй вход к инверсному выходу первого элемента ИЛИ, третий вход - к инверсному выходу третьего элемента ИЛИ, а вы- ход - к третьему выходу блока, первый вход четвертого элемента И подключен к третьему выходу дешифратора, второй вход - к инверсному выходу первого элемента ИЛИ, третий вход к выходу первого элемента И, первый вход пятого элемента И подключен к третьему выходу дешифратора, второй вход - к первому входу блока, первый вход четвертого элемента ИЛИ подключен к выходу четвертого элемента И, второй вход - к выходу пятого элемента И, а выход к четвертому выходу блока управления, первый вход пятого элемента ИЛИ подключен к второму выходу дешифратора, второй вход - к выходу чет вертого элемента ИЛИ, а выход - к счетному входу первого триггера, первый вход шестого элемента ИЛИ подключен к выходу второго элемента И, второй вход - к выходу второго элемента ИЛИ, третий вход к,выходу третьего элемента И, а выход - к счетному входу второго триг- гера, первый прямой вход дешифратора подключен к прямому выходу первого триггера, первый инверсный вход - к инверсному выходу первого триггера, второй прямой вход - к прямому выходу второго триггера I второй инверсный вход - к инверсному выходу второго триггера, информационные входы счетчика подключены к третьим входам блока управления, вычитающий вход - к выходу второго элемента ИЛИ, управляющий вход к выходу второго элемента И, выход генератора синхроимпульсов соединены с синхровходами первого и второго триггеров и дешифратора. На фиг. 1 изображена структурная схема устройства для реализации булевых функций; на фиг, 2 - схема блока ассоциативной памятиj на фиг. 3 схема блока управления. Устройство (фиг. 1) содержит блок 1 управления, блок 2 памяти адресов, блок 3 ассоциативной памяти,

первый регистр 4, второй регистр 5, третий регистр б, четыре группы схем сравнения 7

lyt О . . . OKU/

элементы ИЛИ

12, счетчик 11 . . . 11, , элемент 13, дешифратор 14.

В.блок 3 ассоциативной памяти ,фиг. 2) входят регистры 15|...15у„, элементы И 16...16i;, элементы ИЛИ 17 ...,, причем первый выход блока 1 управления подключен к управляюрим входам первого и третьего регистров и к установочному входу счетчика второй выход - к управляющему входу блока памяти адресов, третий выход к счетному входу счетчика, четверТгый выход к управляющим входам второго регистра и блока ассоциативной памяти, с выходами устройства соедиг нены прямые выходы второго регист-, .ра; и тем, что блок ассоциативной памяти содержит регистры, элементы И и элементы ИЛИ, причем прямые выходы каждого регистра соединены с п ервыми входами соответствующих элементов И, выходы которых соединены с входами соответствующего элемента ИЛИ, выходы элементов ИЛИ являются выходами блока ассоциативной памяти, информационные входы блока ассоциативной памяти соединены с вторыми входами соответствующих элементов И, третьи входы элементов И подключены к управляющему входу блока ассоциативной памяти; а также тем, что блок управления содержит генератор синхроимпульсов, счетчик, первый и второй триггеры, дешифратор, пять элементов И и шесть элементов ИЛИ, причем входы первого элемента И соединены с инверсными выходами счетчика, вход первого элемента ИЛИ соединен с первым входом блока управления, первый вход второго элемента И подключен к второму входу блока управления, второй вход к первому выходу дешифратора, ei выход - к первому выходу блока управления, первый вход второго элемента ИЛИ подключен к второму выходу дешифратора, второй вход - к четвертому выходу дешифратора, а выход - к второму Выходу блока управления,- вход третьего элемента ИЛИ соединен с выходом первого элемента И, первый вход третьего элемента И подключен к третьему выходу дешифратора, йторой вход - к инверсному выходу первого элемента ИЛИ, третий вход - к инверсному выходу третьего элемента ИЛИ, а выход - к третьему выходу блока управления, первый вход четвертого элемента И подключен к третьему выходу дешифратора, второй вход - к инверсному выходу первого элемента ИЛИ, третий вход - к л-выхо,ду первого элемента и, первый вход пятого элемента, первый информационный вход блока 3 ассоциативной памяти соединен с вторыми входами элементов И 16 , lб. и ,.-4 второ информационный вход блока ассоциативной памяти 3 соединен с вторыми входами элементов И 16,, . i ,,j и т.д., -и вход блока 3 ассоциативной памяти соединен со втрыми входами элементов И 16 ri 16/2.Г) 16(5(.r , где т- число уравнений, - число различных конъюнкций). Первые входы элементов и 16/j,...16, аналогичным образом соединены с соответствуюидами выходами регистров 15,...15т, третьи входы элементов И l&f ,...165 соединены с управляющим входом блока 3 ассоциативной памяти. Выходы элементов И 16 ,...16) соединены с входами элемента ИЛИ 17( , выходы элементов И 1б;-ц. , Ifi выходы элементов И ,...16. соединены с входами элемента ИЛИ ..

В блок 1 управления (фиг. 3 входят генератор синхроимпульсов 18, счетчик 19, первый 20 и второй 21 триггеры, дешифратор 22, элементы И 23, 25, 27-29, элементы ИЛИ 24,

26, 30-33,

В блок 2 памяти адресов записана информапия о всех различных элементарных конюнкциях,которые хотя бы один раз встречаются записях ДНФ, реализуемых устройством булевых функций. Причем независимо от того, в записях какого числа функций встречается та или иная элементарная конъюнкция, информация о ней записывается в блок 2 памяти адресов только один раз. Каждая ячейка блока 2 памяти адресов соответствует одной элементарной конъюнкции, длина ячейки равна 2-(и+ ш) разрядов , где У1 - число входных пере- менных X, m - число выходных переменных V (функций), входящих в систему. Запись информации в первые И разрядов ячейки блока 2 памяти адресов производится согласно правилу:

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

Аналогично заполняются следующие m разрядов ячейки:

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

ijKW

1,если Кг-я переменная

J) входит в -ю конъюнкцию без отрицания, либо отсутствует. Для заполнения второй части -i -и ячейки блока 2 памяти адресов используются следующие правила: 0,если j-H переменная х входит в 1-ю конъюнкцию без отрицания; 1,если j-я переменная х входит в 1 -ю конъюнкцию с отрицанием, либо отсут- , стёует; О, если К-я переменная вхо дит в -ю конъюнкцию без отрицания; i,.ntm Ij если К.-Я переменная вхо .дит Bt-H конъюнкцию с отрица нием, либо отсутствует; j 1,2, . . ., И , ,2, ...,П1 В приведенных правилах ai,j;ai к + и e/jtrttn ;й/ц 2ги-«есть значения соотвётст венно, f-ro, ((( +n)-roJ(J tm )-го и Гч+ -t-JT) } -го разрядов ячейки блока 2 па мяти адресов; j и к- номера переменных (входных и выходных соответственно) . Например, в случае элемен тарной конъюнкции 2,. Х,AX AV jAVnpH 1-я ячейка памяти должна быть заполнена следующей информацией: 011110110011 (номера разрядов считаются слева направо). В блоке 3 ассоциативной памяти в каждый из регистров 15 ...15щ, число которых равно числу реализуемых устройством булевых функций, за писана информация о вхождении элеме тарных конъюнкций в соответствующую функцию. При этом разрядность каждо го из регистров 15 . . .15 равна кол честву ячеек блока 2 памяти адресов Запись информации в К-и регистр 15« блока 3 ассоциативной памяти производится согласно правилу: 10, если 1-я конъюнкция не входит в К-ю функцию; 1, если (-я конъюнкция входит в К-ю функцию. Здесь - значение -го разряда регистра 15|( блока 3 ассоциативной памяти. Первый регистр 4 служит для прие ма входных сигналов. Устройство работает-следующим образом. Набор входных сигналов, характеризующих состояние объекта управления, параллельным кодом принимается в первый регистр 4 и сохраняется в нем до окончания цикла работы устройства. Одновременно с приемом набора входных сигналов происходит сброс третьего регистра б и установ ка начального кода в счетчике 13, Затем считывается первое слово из блока 2 памяти адресов по адресу, хранящемуся в счетчуке 13 (в начале каждого цикла в счетчике хранится код адреса первой по счету ячейки блока 2 памяти адресов. Считанное слово поступает на соответствующие входы схем сравнения 7 . . . 7 , 8 . . . 8, 9 . . , 9f,, 10 ... 10у„, и на выходе элемента И 12 появляется сигнал, соответствующий значению первой элементарной конъюнкции при конкретных значениях входных переменных. Это значение записывается в соответствующий разряд третьего регистра 6 по первым информационным входам. Выбор этого разряда осуществляется с помощью дешифратора 14, указывающего по вторым информационным входам третьего регистра 6, в какой именно разряд этого регистра производится запись. Если значение первой элементарной конъюнкции равно нулю, то содержимое счетчика 13 по счетному входу увеличивается на 1. Считывается следующее слово из блока 2 памяти адресов, вычисленное значение элементарной конъюнкции с выхода элемента И 12 поступает на первые информационные входы третьего регистра 6 и запоминается в соответствующем разряде. Так происходит до тех пор, пока очередная элементарная конъюнкция не примет значение 1, либо пока не будут вычислены все различные элементарные конъюнкции, входясдие в систему реализуемых устройством булевых функций. После этого подается сигнал на управляющий вход блока 3 ассоциативной памяти, в результате происходит сравнение содержимого третьего регистра 6 с содержимым каждого из регистров 15 ...15 блока ассоциативной памяти 3 и на выходах элементов ИЛИ 17 ... формируются сигналы, соответствующие значениям булевых функций при данном наборе входных переменных. Эти значения засылаются в соответствующие разряды второго регистра 5 и могут участвовать в дальнейших вычислениях. Устройство для реализации булевых функций позволяет сократить время на вычисление значений функци за счет исключения несущественных участ ков вычислений, которые не могут повлиять на значение функции в силу свойства дизъюнкции: . Так, если в систему реализуемых устройством булевых функций входит И различных элементарных конъюнкций, то вычисление значений булевых функций для каждого набора входных переменных в известных устройствах осуществляется за время Tg-Q- , где tx время вычисления одной элементарной конъюнкции. Минимальное время вычисления значений булевый функций в данном устройстве равно: Ту, -Ь в силу того, что первая вычисляемая элементарная конъюйкция может принять значение, равное 1. Таким образом, для реальных функций, реализуемых предлагаемым устройством, увеличение быстродействия по сравнению с базовым варианfoM будет находиться в пределах: