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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК сю ПИСАНИЕ ИЗОБРЕТЕНИ(56) 1. АвР 383043 2/18-282 льство О, 1974 ство СС1970 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР 0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ К АВТОРСКОМУ СВИДЕТЕЛЬСТ 3 Бюл. 9 28 лин, В.В.Бодунов иГ.М,Ре левский маш р ельный25 (088.8)торское свидете СССРкл. 6 06 Г 15/22. Авторское свидетель СР Р 276516, кл. О 06 Г 7/00 (прототип).(54)(57) 1. УСТРОЙСТВО ДЛЯ РЕАЛИЗА- цИИ ВУЛЕВХ фуИКцИЙ, содержащее блок управления, элементы ИЛИ, элемент И, входы которого соединены с выходами элементов ИЛИ, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок памяти адресов, блок ассоциативной памяти, первый регистр, второй регистр, третий регистр, четыре группы схем сравнения, счетчик и дешифратор, причем входы первого регистра соединены с входами устройства, информационные входы второго регистра соединены с выходами блока ассоциативной памяти, пЕрвые входы схем сравнения первой группы подключены к первой группе выходов блока памяти адресов, вторые входы - к прямым выходам первого регистра, а выходы - к первым входам элементов ИЛИ первой группы, первые входы схем сравнения второй группы подключены к второй группе выходов блока памяти адресов, вторые входык прямым выходам второго регистра, а выходы - к первым входам элементов ИЛИ второй группы, первые входы схем сравнения третьей группы подключены к третьей группе выходов бло ка памяти адресов, вторые входы - кинверсным выходам первого регистра, а выходы - к вторым входам элеЯО 1032451 А ментов ИЛИ первой группы, первые входы схем сравнения четвертой груп" пы подключены к четвертой группе выходов блока памяти адресов, вторые входы - к инверсным выходам второго регистра, а выходы - к вторым входам элементов ИЛИ второй группы, входы элемента И соединены с выходами элементов ИЛИ первой и второй групп, первые информационные входы третьего регистра подключены к выходу элемента И, вторые информационные входы - к выходам дешифратора, а выходы - к информационным входам блока ассоциативной памяти, выходы счетчика соединены с адресными входами блока памяти адресов и входами ц дешифратора, первый вход блока управления подключен к выходу элемента И, второй вход .- к входу пуска устройства, третий вход - к установочному входу устройства, первый выход - к управляющим входам первого и третьего регистров и к установочному входу счетчика, второй выход к управляющему входу блока памяти адресов, третий выход - к счетному входу счетчика, четвертый выход " (, ) к управляющим входам второго регистра и блока ассоциативной памяти, а с выходами устройства соединены пря- Я мые выходы второго регистра, ф,2. Устройство по п, 1, о т л и ч а ю щ е е с я тем, что блок ас- СД социативной памяти содержит регистры, элементы И и элементы ИЛИ, причем прямые выходы каждого регистра соединены с первыми входами соответствующих элементов И, выходы которых Ффф соединены с входами соответствующего элемента ИЛИ, выходы элементов ИЛИ являются выходами блока, информационные входы блока соединены с вторыми входами соответствующих элементов И, третьи входы элементов И подключены к управляющему входу блока.1032451 3, Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок управления содержит генератор сннхроимпульсов, счетчик, первый и второй триггеры,дешифратор, пять элементов И и шесть элементов ИЛИ, причем входы йервого элемента И соединены с инверсными выходами счетчика, вход первого элеМента ИЛИ соединен с первым входом блока управления, первый вход второго элемента И подключен к второму входу блока, второй вход - к первому выходу дешифратора, а выход - к Первому выходу блока, первый вхсд второго элемента ИЛИ подключен к второму выходу дешифратора, второй вход - к четвертому выходу дешифратора, а выход - к второму выходу блока, вход третьего элемента ИЛИ соединен с выходом первого элемента И, первый вход третьего элемента И подключен к третьему выходу дешифратора, второй вход - к ин- . версному выходу первого элемента ИЛИ, третий вход - к инверсному выходу третьего элемента ИЛИ, а выход - к третьему выходу блока, первый вход четвертого элемента И подключен к третьему выходу дешифратора, второй вход - к инверсному выходу первого элемента ИЛИ, третий вход - к выходу первого элемента И, первый вход пятого элемента И под 1Изобретение относится к вычислительной технике и может быть использовано для управления технологическим оборудованием, Функционирование которого описывается системой булевых функций, а также для моделирования цифровых устройств,Известно устройство для моделирования конечных автоматов, содержащее блок памяти, мультиплексор, сумматор по модулю два, блок вычисления булевых функций, первый и второй дешифраторы, первый и второй регистры 11.Недостатком устройства является низкое быстродействие, ввиду того, 15 Что вычисление значений булевых Функций в устройстве осуществляется путем последовательной подачи значений переменных, их кодов и кодов служебных символов на входы блока Вычисления булевых функций.Наиболее близким к предлагаемому по технической сущности является логический автомат, содержащий блок Ввода переменных, блок памяти, блок р 5 ключен к третьему выходу дешифрато.ра, второй вход - к первому входублока, первый вход четвертого элемента ИЛИ подключен к выходу четвертого элемента И, второй вход - квыходу пятого элемента И, а выходк четвертому выходу блока, первыйвход пятого элемента ИЛИ подключенк второму выходу дешифратора, второйвход - к выходу четвертого элемента ИЛИ, а выход - к счетному входупервого триггера, первый вход шестого элемента ИЛИ подключен к выходу второго элемента И, второй вход -к выходу второго элемента ИЛИ, третий вход - к выходу третьего элемента И, а выход - к счетному входу второго триггера, первый прямойвход дешифратора подключен к прямому выходу первого триггера, первыйинверсный вход - к инверсному выходу первого триггера, второй прямой вход - к прямому выходу второготриггера, второй инверсный вход -к инверсному выходу второго триггера, информационные входы счетчикаподключены к третьим входам блока,вычитающий вход - к выходу второгоэлемента ИЛИ, управляющий вход - квыходу второго элемента И, выходгенератора синхроимпульсов соединенс синхровходами первого ивторого триггеров и дешифратора,задержек, программоноситель с вентилями, элемент И, элементы ИЛИ и НЕблок вывода 1 2 .Однако данное устройство характеризуется низким быстродействием,обусловленным тем, что в процессеработы автомата производится вычисление всех без исключения элементарных конъюнкций, входящих в системуреализуемых автоматом логическихФункций,Цель изобретения - повышение быстродействия.Указанная цель достигается тем,что в устройство, содержащее блокуправления, элементы ИЛИ, элемент И,входы которого соединены с выходамиэлементов ИЛИ, введены блок памятиадресов, блок ассоциативной памяти,первый регистр, второй регистр, третий регистр, четыре группы схем сравнения, счетчик и Дешифратор, причемвходы первого регистра соецинены свходами устройства, информационныевходы второго регистра соединеныс выходами блока ассоциативной памяти, первые входы схем сравнения перной группы подключены к первой группе выходов блока памяти адресов, вторые входы - к прямым ныхо" дам первого регистра, а выходы - к первым входам элементов ИЛИ первой группы, первые входы схем сраннения второй группы подключены к второй группе выходон блока памяти адресов, вторые входы - к прямым выхо дам второго регистра, а выходы - к первым входам элементов ИЛИ второй группы, первые входы схем сравнения третьей группы подключены Ф третьей группе выходов блока памяти адресон, 15 вторые входык инверсным выходам первого регистра, а выходы - к вторым входам элементов ИЛИ первой группы, первые входы схем сравнения четвертой группы подключены к четвер- р той группе выходов блока памяти адресов, вторые входы - к инверсным выходам второго регистра, а выходы к вторым входам элементов ИЛИ второй группы, входы элемента И соединены с выходами элементов ИЛИ первой и второй групп, первые информационные входы третьего регистра подключены к выходу элемента И, вторые информационные входы - к выходам дешифратора, а выходы - к информационным входам блока ассоциативной памяти, выходы счетчика соединеныс адресными входами блока памяти адресов и входами дешифратора, первый вход блока управления подключен к выходу 35 элемента И, второй вход " к входу пуска устройства, третий вход - к установочному входу устройтва, первый выход -к управляющим входам первого итретьего регистров и к устано-. 40 ночному входу счетчика, второй выход к управляющему входу блока памяти адресов, третий выход - к счетному входу счетчика, четвертый выход - к управляющим входам второго регистра и блока ассоциативной памяти, а .с выходами устройства соединены прямые выходы второго регистра.Блок ассоциативной памяти содержит регистры, элементы И и элементы ИЛИ, причем прямые выходы каждого регистра соединены с первыми входами соответствующих элементов И, выходы которых соединены с входами соответствующего элемента ИЛИ, выходы элементов ИЛИ являются выходами блока, информационные входы блока соединены с вторыми входами соответствующих элементов И, третьи входы элементов И подключены к управляющему входу блока. 60Блок управления содержит генератор синхроимпульсон, счетчик, первый и второй триггеры, дешифратор, пять элементов И и шесть элементов ИЛИ, причем входы перного элемента И сое динены с инверсными выходами счетчика, вход первого элемента ИЛИ соединен с первым входом блока управления, первый вход второго элемента И подключен к второму входу блока, второй вход - к первому выходу дешифратора, а выход - к первому выходу блока, первый вход второго элемента ИЛИ подключен к второму выходу дешифратора, второй вход - к четвертому выходу дешифратора, а выход - к второму выходу блока, вход третьего элемента ИЛИ соединен с выходом пер" ного элемента И, первый вход третьего элемента И подключен к третье му выходу дешифратора, второй вход - к инверсному выходу первого элемента ИЛИ, третий вход - к иннер:ному выходу третьего элемента ИЛИ, а выход - к третьему выходу блока, пер- . вый вход четвертого элемента И подключен к третьему выходу дешифратора, второй вход - к инверсному выходу первого элемента ИЛИ, третий вход " к выходу первого элемента И, первый вход пятого элемента И подключен к третьему выходу дешифратора, второй вход - к первому входу блока, первый вход четвертого элемента ИЛИ подключен к выходу. четвертого элемента И, второй вход - к выходу пятого элемента И, а выход - к четвертому выходу блока управления, первый вход пятого элемента ИЛИ подключен к второму выходу дешифратора, второй вход - к выходу четвертого элемента ИЛИ, а выход - к счетному входу первого. триггера, первый вход шестого элемента ИЛИ подключен к выходу второго элемента И, второй вход - к выходу второго элемента ИЛИ, третий нход к,выходу третьего элемента И, а выход - к счетному входу второго триг-ф гера, первый прямой вход дешифратора подключен к прямому выходу первого триггера, первый инверсный вход - к инверсному ныходу первого триггера, второй прямой вход - к прямому выходу второго триггера, второй инверсный вход - к инверсному выходу второго триггера, информационные входы счетчика подключены к третьим входам блока управления, нычитающий вход - к выходу второго элемента ИЛИ, управляющий вход к выходу второго элемента И, выход генератора синхроимпульсон соединены с синхровходами первого и второго триггеров и дешифратора.На фиг. 1 изображена структурная схема устройства для реализации булевых функций, на фиг. 2 - схема блока ассоциативной памяти, на фиг. 3 схема блока управления.Устройство (фиг. 1) содержит блок 1 управления, блок 2 памяти адресов, блок 3 ассоциативной памяти, 1032451первый регистр 4, второй регистр 5,третий регистр 6, четыре группысхем сравнения 7171, 88 о9 .9 и, 10 101 элементы ИЛИ11 1111,щ, элемент И 12, счетчик13, дешифратор 14,В блок 3 ассоциативной памятифиг. 2) входят регистры 15 . 15 иэлементы И 16 169, элементы ИЛИ17 А 17, причем первый выход блока 1 управления подключен к управляющим входам первого и третьего регистров и к установочному входу счетчикавторой выход - к управляющему входублока памяти адресов, третий выходк счетному входу счетчика, четвертый выход - к управляющим входам второго регистра и блока ассоциативнойпамяти, с выходами устройства соединены прямые выходы второго регистра, и тем, что блок ассоциативнойпамяти содержит регистры, элементы Ии элементы ИЛИ, причем прямые выходы каждого регистра соединены с первими входами соответствующих элементов И, выходы которых соединеныс входами соответствующего элемента ИЛИ, выходы элементов ИЛИ являются выходами блока ассоциативной памяти, информационные входы блокаассоциативной памяти соединены с вторыми входами соответствующих элементов И, третьи входы элементов И подключены к управляющему входу блокаассоциативной памяти; а также тем,что блок управления содержит генератор синхроимпульсов, счетчик, первый и второй триггеры, дешифратор,пять элементов И и шесть элементов ИЛИ, причем входы первого элемента И соединены с инверсными выходами счетчика, вход первого элемента ИЛИ соединен с первым входомблока управления, первый вход второго элемента И подключен к второмувходу блока управления, второй входк первомувыходу дешифратора, авыход - к первому выходу блока управления, первый вход второго элемента ИЛИ подключен к второму выходу дешифратора, второй вход - н;четвертому выходу дешифратора, авыход - к второму выходу блон:а управления, вход третьего элемента ИЛИсоединен с выходом первого элемента И, первый вход третьего элементаИ подключен к третьему выходу дешифратора, торой вход - к инверсномувыходу первого элемента ИЛИ, третийвход - к инверсному выходу третьегоэлемента ИЛИ, а выход - к третьемувыходу блока управления, первый входчетвертого элемента И подключен к оотретьему выходу дешифратора, второйвход - к инверсному выходу первогоэлемента ИЛИ, третий вход - к .: выхо,ду первого элемента И, первый входпятого элемента, первый информацион ный вход блока 3 ассоциативной памяти соединен с вторыми входами элементов и 161, 161-, и 16 1., второй информационный вход блока ассоциативной памяти 3 соединен с вторыми входами элементов И 16, 161.169 1и т.д., " -й вход блока 3 ассоцйативной памяти соединен со вто. рыми входами элементов И 16 , 16.1- 16 в(,: и,-, где ю - число уравнений, " - число различных конъюнкций). Первые входы элементов И 164,16 аналогичным образом сое-:", динены с соответствующими выходами регистров 15,15 р, третьи входы элементов И 16,1 бв соединены с управляющим входом блока 3 ассоциативной памяти, Выходы элементов И 16,161. соединены с входами элемента ИЛИ 17, выходы элементов И 161 .1, 1621-, выходы элементов16 , ,16 соединены с входами элемента ИЛИ 17 щВ блок 1 управления (Фиг. 3) входят генератор синхроимпульсов 18,счетчик 19, первый 20 и второй 21триггеры, дешифратор 22, элементы И23, 25, 27-29, элементы ИЛИ 24,26, 30-33,В блок 2 памяти адресов записанаинФормация о всех различных элементарных конюнкциях,которые хотя быодин раз встречаются в записях ДНФ,реализуемых устройством булевыхфункций. Причем независимо от того,в записях какого числа функцийвстречается та или иная элементарная конъюнкция, информация о нейзаписывается в блок 2 памяти адресов только один раз. Каждая ячейкаблока 2 памяти адресов соответствует одной элементарной конъюнкции,длина ячейки равна 2-И+ щ) разрядов, где И - число входных переменных х, е - число выходных пере менных Ч ( Функций), входящих в систему. Запись информации в первыеИ разрядов -и ячейки блока 2 памяти адресов производится согласно правилу:О, если -я переменная хвходит в данную-юконъюнкцию с отрицанием;1, если 1-я переменная хвходит в 1.-ю коньюнкциюбез отрицания, либо отсутствует,Аналогично заполняются следующиею разрядов 4 -й ячейки:О, если -я переменнаявходит в 1 -ю конъюнкцию с отрицанием,1, если Ктя переменнаявходит в 1 -ю конъюнкцию без отрицания, либо отсутствует.Для заполнения второй части-й ячейки блока 2 памяти адресов используются следующие правила: О, если -я переменная х входит в 1-ю конъюнкцию без отрицания;1, если 1-я переменная х входит в-ю конъюнкцию с отрицанием, либо отсут-, стует,О, если К-я переменная У входит в 4 -ю конъюнкцию без отрицания;1 если К-я переменная ) входит вс-м конъюнкцию с отрицаа "дфоп Устройство работает следующим образом.Набор входных сигналов, характеризующих состояние объекта управления, параллельным кодом принимается в первый регистр 4 и сохраняется в нем до окончания цикла работы устройства. Одновременно с приемом набора входных сигналов происходит сброс третьего регистра б и установка начального кода в счетчике 13. Затем считывается первое слово из блока 2 памяти адресов по адресу, хранящемуся в счетчике 13 (в начале каждого цикла в счетчике хранится код адреса первой по счету ячейки блока 2 памяти адресов. Считанное 50 55 нием, либо отсутствует; 15=1,2,ИК=1 2, ,и.В приведенных правилах а.пЙбфнтщ; О 1+2 п+м есть значения соответст"венно,1-го, (К +л)-го,( ип Фю )-го и (кую Фщ ) -го разрядов 6-й ячейки блока 2 па- О мяти адресов;и к- номера переменных (входных и выходных соответственно), Например, в случае элементарной конъюнкции 7;: К АХэМЛМпри я=в=3 4-я ячейка памяти должйа быть 25 заполнена следующей информацией: 011110110011 1 номера разрядов считаются слева направо) .В блоке 3 ассоциативной памяти в каждый из регистров 15 15 и, число которых равно числу реализуемых устройством булевых функций, записана информация о вхождении элементарных конъюнкций в соответствующую функцию. При этом разрядность каждого из регистров 15 15, равна количеству ячеек блока 2 памяти адресов. Запись информации в К-й регистр 15 К, блока 3 ассоциативной памяти производится согласно правилу: О, если 1-я конъюнкция не 40 входит в К -ю функцию,еслия конъюнкция входит в К-ю функцию,Здесь Ь- значение-го разКч ряда регистра 15 К блока 3 ассоци ативной памяти.Первый регистр 4 служит для приема входных сигналов. слово поступает на соответствующие входы схем сравнения 77, 8 8и 99 10 10, ина выходе элемента И 12 появляется сигнал, соответствующий значению первой элементарной конъюнкции при конкретных значениях входных переменных. Это значение записывается в соответствующий разряд третьего регистра б по первым информационным входам. Выбор этого разряда осуществляется с помощью дешифратора 14, указывающего по вторым информационным входам третьего регистра б, в какой именно разряд этого регистра производится запись. Если значение первой элементарной конъюнкции равно нулю, то содержимое счетчика 13 по счетному входу увеличивается на 1. Считывается следующее слово из блока 2 памяти адресов, вычисленное значение элементарной коньюнкции с выхода элемента И 12 поступает на первые информационные входы третьего регистра б и запоминается в соответствующем разряде. Так происходит до тех пор, пока очередная элементарная конъюнкция не примет значение "1", либо пока не будут вычислены все различные элементарные конъюнкции, входящие в систему реализуемых устройством булевых Функций. После этого подается сигнал на управляющий вход блока 3 ассоциативной памяти, в результате происходит сравнение содержимого третьего регистра б с содержимым каждого из регистров 15 15 блока ассоциативной памяти 3 и на выходах элементов ИЛИ 174 17 Формируются сигналы, соответствующие значениям булевых функций при данном наборе входных переменных. Эти значения засылаются в соответствующие разряды второго регистра 5 и могут участвовать в дальнейших вычислениях.устройство для реализации булевых функций позволяет сократить время на вычисление значений функци за счет исключения несущественных участ ков вычислений, которые не могут повлиять на значение функции в силу свойства дизъюнкции: 110=1. Так, если в систему реализуемых устройством булевых Функций входитразличных элементарных конъюнкций, то вычисление значений булевых Функций для каждого набора входных переменных в известных устройствах осуществляется за время Т 0 = 1 ", где 1 к - время вычисления одной элементарной конъюнкции.Минимальное время вычисления значений булевый функций в данном устройстве равно: Т, =К в силу того, что первая вычисляемая элементарная конъюнкция может принять значение, равное ф 1".Таким образом, для реальных функций, реализуемых предлагаемым устройством, увеличение быстродействия по сравнению с базовым вариантом будет находиться в пределах: 19 "1032451 Филиал ППП "Патент",г.Ужгород,ул.Проектна ВН Ти Заказ 5401/52Об Подписное