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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ нп 959064 Союз СоветскихСоциалистическихРеспублик(61) Дополнительное к авт, свид-ву(22) Заявлено 04.08,80 (21) 2967529/18-24 51) М. Кп.з 6 06 Р 7/00 с присоединением заявки Мо -Государственный комитет С С С.Р по делам изобретений и открытий(088, 8) Опубликовано 1509.82. Бюллетень Йо 34Дата опубликования описания 150982 4) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ асширение обства путемсиммет ичных 10 ойства приме- жносю13 стного ус ая област иду невозм произволь ю функцию Изобретение относится к цифровой вычислительной технике.Известно устройство для реализации булевых функций, представляюще собой комбинационные схемы из логических элементов И, ИЛИ, НЕ 1)Недостатком таких устройств является низкая технологичность изготовления в условиях технологии больших интегральных схем, что связано с нерегулярностью их внутренней структуры. Наиболее близким по технической сущности к предлагаемому является логическое устройство для вычисления значений булевых функций, содержащее 5 ступеней постоянных запоминающих устройств, первая ступень .которых включает 8 постоянных запоминающих устройств по числу групп обрабатываемых переменных аргументов, входы 1-й ступени соединены с выходами (1-1)-й ступени, а выходы 1-й . ступени соединены со входами (1+1)-й ступени 123. 25Недостатком изве тр является ограниченн ь нения устройства вв о , ти вычислять любую ну симметричную булеву 0 Цель изобретения - рласти применения устройреализ ации вычисления Р булевых Функций.Поставленная цель достигается тем, что устройство для вычисления симметричных булевых Функций, содержащее блок суммирования единичных значений переменных аргумента и дешифратор, вход которого подключен к выходу блока суммирования единичных значений переменных аргумента,.вход которого подключен к и входным шинам аргументов устройства соответственно, оно содержит постоянный запоминающий узел настроечных кодов, регистр настроечных кодов и элементы И и ИЛИ, причем входы постоянного запоминающего узла настроечных кодов подключены к дополнительным 1 с входным шинам устройства соответственно (1 с =Д 1 од 1),а 3-й выход постоянного запоминающего узла настроечных кодов Я - "1,2 п+1) подключен к 3-ому входу регистра настроечных кодов соответственно, 1-й выход которого подключен к первому входу -го элемента И соответственно, вто-, рой вход которого подключен к 1-му выходу дешифратора соответственно,959064 метричных. 1 НаборХ Х Х 4 Набор Е( х, х 2 хх 4) 0.0 00 0001 0010 0011 выходы элементов И подключены к входам элемента ИЛИ соответственно,выход которого является выходом устройства,Блок для суммирования единичныхзначений переменных аргумента содержит Б ступеней постоянных запоминающих узлов, содержащих 2ячеек, причем входы блока подключены к входампостоянных запоминающих узлов первойступени, входу ПЗУ 1-ой ступени 10(1 = 1, 2,Б; 3 = 31 од 1 и (- )1 одц +1)подключены к выходам постоянных за-.помйнающих узлов (1-1)-й ступени,выходы постоянных запоминающих узловЯ-й ступени подключены к выходам блока,На фиг.1 показана структурная схема устройства для вычисления симметричных булевых функций; нафиг,2 - то же и содержимое ячеекпостоянных запоминающих устройств 4для реализации симметричной булевойфункции типа четности; на Фиг.Зто же и содержимое ячеек постоянныхзапоминающих устройств для реализации симметричных булевых функций 25типа мажоритирования, нечетности испециального вида.Устройство (фиг.1) содержит входные шины аргументов 1, которые соединены со входами первой ступени постоянных запоминающих узлов 2, выходы первой ступени постоянных запоминающих узлов 2 соединены со входами второй ступени постоянных запоминающих узлов, выходы которой соединены со входами следующей ступени ит.д., а выходы последней ступени постоянных запоминающих узлов 2 соединены со входом дешифратора 3, выходкоторого подсоединен к первому входукаждой иэ групп элементов И 4, второй вход каждой иэ группы элементовИ 4 соединен с выходом одного разряда регистра настроечных кодов 5,входкоторого соединен с выходом постоянного запоминающего узла настроечныхкодов 6, вход которого соединен свходными шинами 1. Кроме того, выход каждой из групп элементов И 4соединен со входами элемента ИЛИ 7,выход которой является выходом уст ройства 8. Все узлы 2 в совокупности образуют блок 9 суммирования единичных значений переменных аргументаЛюбая булева функция и аргументов имеет 2 набора, на которых она может принимать два значения: "Оф и "1". Булева функция Е(х,х ,, х,хх) называется симметрйчной относительно переменных х; и х), еслиЕ(х 1 ухтуух;,ее.,х уфух) =Е(х 1 з х ффх ют х 1 эю х). э т.е. значение Функции на данном наборе не зависит от перестановки определенных переменных, Количество таких наборов Р определяется видом симметричной функции (Р2 ).Для,определения принадлежности рассматриваемой булевой функции к классу симметричных, необходимо произвести проверку по соответствующим формулам. В частности, к классу симметричных булевых функций относятся функции четности, нечетности, мажоритированияВ устройстве используется тот факт, что произвольная симметричнаяФункция Е(х,ххи) от и переменных принимает единичное значениетогда и только тогда, когда точноа 1(Э = 1,2Р) переменных равныединице. Например, при и = 4 симметричная булева функция четности имеет семь наборов (Р = 7), на которыхона принимает значение равное "1".Это значит, что для данных набороваргументов возможна перестановка значений переменных, но общее число едйниц останется тем же (четным) и. Функция по-прежнему равна единице на этихнаборах, т.е. выполняется условие принадлежности Функции к классу симВ таблице приведены значения аргументов (соответствующих наборов) Функции четности для и = 4 и выделены наборы, для которых она выполняется. В четвертом столбце указан номер набора Ц = 17), на котором ровно а переменных равны единице (эначенйе а показано в последнем столбце. таблицы),959064 Продолжение таблицы Е( х, ех 1 юх фх 4) 1 абор Набор 2 Э 4 100 101 3 011 011 1000 1001 10 011 00 110 14 Приведенные рассуждения справедливы и для других симметричных функций. Для определения принадлежности функции к классу симметричных можно определить число единиц в обрабатываемом наборе и сопоставить его со значением а реализуемой функции. В случае равенства этих значений реализуется симметричная булева Функция и значение Функции равно единице (при условии, что функция принадлежит к классу симметричных).Суммирование единичных значений переменных аргумента выполняется блоком 9, причем входпервой ступени узлов 2 которого соединен с и входными шинами аргументов 1, а выполнение требуемой симметричной функции осуществляется с помощью настроечных кодов, поступающих из постоянного запоминающего устройства настроечных кодов 6 на регистр настроечных кодов 5, а затем на первый вход каждого из элементов И 4 группы. Значение настроечного кода определяется группой из разрядов аргументов, поступающих в качестве адреса на вход постоянного запоминающего узла настроечных кодов 6. Таким образом, поступающий код аргумента состоит из Е разрядов, определяющих вид реализуемой симметричной функции, и и разрядов переменных,Каждая ячейка постоянного узла 2 З 5 первой ступени содержит двоичный кодчисла единиц в обрабатываемой групперазрядов кода аргумента. Ячейка постоянного запоминающего узла 2 второй и последующих ступеней содержит 40 двоичный код суммы двоичных чисел,поступивших с выходов постоянных запоминающих устройств предыдущей ступени.Сумма единичных значений аргумен тов, получаемая с выходов постоянного запоминающего узла 2 последнейступени блока 9, поступает на входдешифратора 3. Дешифратор 3 имеети+1 выходных шин, каждая из которых 5 О подключается ко второму входу однойиз и+1 элементов И 4. Если сумма единиц значений аргументов равна ато единичный уровень присутствуетна а -й шине выхода дешифратора 3.Вйход а -го элемента И 4 возбужден, если одновременно на а -й шиненастройки (с регистра настроечных3кодов 5) и а -й выходной шине дешифратора 3 присутствуют единичные сигналы. Таким образом, если входныешины а элемента И 4 возбуждены, тума выходе этого элемента И 4 реализуется. симметричная Функция Ец;(х ,х).Элемент ИЛИ 7 реализует дизъюйкцию +1 переменных, поступающих с 65 выходов элементов Й 4.959064Поскольку любая симметричная бу-такте по входным шинам 1 в устройст- лева Функция представима в виде во.Если сигнал с дешифратора 3 не проходит через элемент И 4, то на выход,с,с о= .о то предлагае- де устройства присутствует уровень, мое ус,ойство может реа изовать лю 5 соответствующ й нулево у значению бую симметричную функцию от и пере- заданной бУлевой функции. менных. Определим число ступеней системыВид симметричной функций опреде- постоянных запоминающих узлов, разляется настроечным кодом, хранящимся Рядность и емкость структурных элен одной из ячеек постоянного запоми- О ментов, входящих в устройство. нающего узла настроечных кодов б, Длина аргумента, обрабатываемоДлина ячейки ранна и+1 разряд а ко- го УстРойством, равна сумме .и+К личество ячеек определяется количес- разрядов, Число разрядов Е, посту- твом симметричных Функций, которое пающих на адресный вход постоянного должно реализовать логическое уст запоминающего узла настроечных коРойство. Группа из Е разрядов аргу- дов б, определяется из соотношения мента, поступающая на вход постоянно- к = .1 од 1где 1 - число реализуго запоминающего узла настроечных ко- емых симметричный Функций. дов б, представляет адрес (код) сим- Ширина постоянного запоминающего метричной функции, требующей реали О узла настроечных кодов б равна и+1-му зации. разряду. Требуемый объем постоянногоРабота устройства происходит в . запоминающего узла настроечных кодов, несколько тактов. б равен Я = 2 (и+) бит. КоличествоВ первом такте в соответствии с Ячеек кажДого постоЯнного запоминаю- набором аргументов, поступающим по 25 щего Узла 2 определяется как 2, а входным шинам 1, из первой ступени объем равен: для первой ступени постоянных запоминающих узлов 2 (31 одцГ+1) 2 ф бит, а для последую- считываются числа единиц в группах. щих ступеней 31 од 1 г +2) 2 бит, этого набора аргументов, а из по- где г; - количество разрядов, отвостоянного запоминающего узла настро- димых для двоичного представления ечных кодов б - настроечный код, оп- максимальной суммы единиц,.поступивределяющий симметричную Функцию. ших из предыдущей 1-й ступени. ЗнаВо втором такте происходит считы- чение показателя степени равно сумвание частичных сумм из первой ступе- ме длин вступающих в операцию суммини постоянных запоминающих узлов 2, рования операндов адресов). а также запись кода настройки в ре- З Число .ступеней постоянных запомигистр 5. нающих узлов равно 5=1 одп 1-) 1 ор,Ч+)В третьем такте считываются час- а ширина постоянного запоминающего тичные суммы из второй ступени по- узла 2 последней ступени равна стоянных запоминающих узлов 2, затем )1 ояапиз третьей ступени и т,д., пока 46 Выбор количества постоянных запоне будет считана окончательная сумма минающих узлов в каждой ступени единиц входного набора из постоянно- следует производить, исходя из струкго запоминающего узла 2 последней - турной организации выпускаемых проступени. мышленностью стандартных постоянныхВ следующем такте окончательная 45 запоминакщих узлов. сумма единиц преобразовывается дешиф- Рассмотрим примеры реализации ратором 3, из двоичной позиционной симметричных булевых Функций. Для системы счисления в унитарный двоич- реализации функции четности (фиг,2) ный код и сигнал,по соответствующей необходимо занести в постоянный зашине ыхода дешифратора 3 поступает р йоминаювЯй Узел б,код, в 1,3,515 на второй вход каждого из элементов разрядах которого записаны едийицы, И 4 группы. В зависимости от кода Старший левый) разряд ячейки посто- настройки, поступающего с выходов янного запоминающего узла 6 равен регстра 5 на первый вход каждого О". Это соответствует тому, что из улементов И 4 группы, сигнал ли-сУмма единиц во входном коде равна бо проходит, либо не проходит через "О" (присутствует единичный сигнал соответствующий элемент И 4 на его на О-й шине дешифратора 3). Пусть выход. такой код записан в ячейке 1,.а всего реализуется 4 типа симметричныхЕсли сигнал проходит через эле- функций 1 = 4). Тогда количество мент И 4, то далее он проходит че- ф разрядов 1 с =)1 од 1= 2. рез элемент ИЛИ 7 на выход 8 устрой- Пусть число обрабатываемых раз 3.ства, что соответствует единичному рядов ц = 16 и обработка производит- значению заданной кодом настройки.ся по 8 разрядов Ч = 8). В ячейках симметричной булевой Функции на набо" постоянных запоминающих узлов 2 перре аргументов, поступившим в первом Ы вой ступени записываются двоичныеФ959064 10 коды, соответствующие сумме единиц вкоде адреса группы обрабатываемых переменных. Начальные фрагменты содержимого постоянных запоминающих устройств первой ступени, следующей ступени (в данном случае она являетсяи последней ступенью) постоянных запоминающих узлов 2 и б показаны нафиг.2, С левой стороны от географи ческих обозначений постоянных запоминающих устройств указаны адресаячеек. По коду адреса, соответствующему числу единиц в группе обрабатываемых переменных, производитсясчитывание числа единиц из содержи-,мого ячейки постоянных запоминающихаргумента определяет адрес ячейки:,в. которой записано число единиц в этом адресе: нулевой адрес - нуль единиц, первый адрес - одна единица, второй адрес - одна единица и т.д. Далее считанное значение определяет адрес ячейки постоянного запоминающего узла 2 последней ступени, в которой хранится сумма числа единиц присутствующих на входе в качестве адреса. Адрес составляется из значений, считанных из ячеек предыдущей ступени и равен в данном случае 34. Значение суммы поступает на вход дешифратора 3 и преобразовывается им в унитарный код.На фиг.2 показана обработка входного кода аргумента со значением 0000 1001 0000 0011 и отмечены ячейки (их содержимое) и шины элементов И 4, которые участвуют в реализации рассматриваемой функции четности . Участвующие шины и ячейки отмечены стрелками. Из последней ступени по-стоянных запоминающих узлов 2 считывается позиционный код 0100, ко-, торый преобразуется дешнфратором 3 в унитарный, что.соответствует присутствию единичного сигнала на четвертой выходной шине дешифратора 3, По-. скольку код настройки,. поступающий с регистра настроечных кодов 5 на вторые входы каждого из группы элементов И 4, обеспечивает присутствие единичного сигнала во 2,4,б и т,д. элементах И. 4 (нумерация соответствует номерам выходных шин дешифратора 3), то на выходе четвертого эле"мента И 4 присутствует единичный сигнал. Этот сигнал через элемент ИЛИ 7 поступает на шину результата 8. Единичный уровень говорит.о том, что реализуется булева функция четности и число единиц в обрабатываемом коде четное.Если требуется реализовать функцию мажоритирования от 16 переменных, принимающую единичное значение тогда, и только тогда, когда число единичных значений -аргументов не превосходит 4, то в ячейку постоянформула изобретения 1. Устройство для вычисления симметричных булевых функций, содержащее блок суммирования единичных значений переменных аргумента н дешифратор, вход которого подключен к выходу блока суммирования единичных значений переменных аргумента, вход ного запоминающего. узла настроечных ,:кодов 6 следует занести код настрой-ки 1 1111 0000 0000. Символическитакая Функция записывается в виде;о,1 , з,м (х 1хь)5йа фиг.З показана реализация функции мажоритирования, когда поступающий код равен значению 0000 00000011 и 0000 0010 0000 0011. Дляпервого случая участвующие ячейки1 О (их содержимое) и шины элементов И 4отмечены одной звездочкой, а во втором " двумя. Предполагается, что коднастройки расположен во второй ячейке постоянного запоминающего узла б.;35 поэтому значение адресных разрядов узлов 2 первой ступени, т.е. значение соответствует коду "10 ф.Как видно из фиг.З,;цля первогонабора аргументов функции мажоритирования реализуются, а для второгонет. Аналогично реализуются и другиесимметричные булевы функции, длячего требуется эанести соответствующий код настройки. Например, для ре,ализации функции нечетности код на-.5 стройки имеет вид 0 1010 1010 10101010, а для Функции, принимающей единичные значения, тогда и толькотогда, когда число единичных значенийаргументов кратно восьми - следующийз 0 0000 00010000 0001. На фиг.Зпоказаны эти коды в 0-й и 3-й ячейкепостоянного запоминающего узла б.соответственно.Таким образом, введенные дополнительно структурные элементы по-3 э зволяют реализовать данным устройством любую Функцию из класса симметричных булевых (в устройстве-прототипе реализуется только мажоритарнаяфункция)49 Применение данного изобретенияпозволяет значительно увеличить скорость логических преобразований, повысить технологичность и надежностьустройств для реализации сложных45 логических зависимостей в системахконтроля и управления, Кроме того,повышается многофункциональное использование устройства для различных применений, поскольку одно такоещ устройство позволяет реализовать несколько Функций. Это служит предпосылкой к унификации подобных устройств, а следовательно, и к снижению стоимости каждого логическогоц устройства..4/ ктнай,4 лиал ППП "Патентф город,акаэ 7017/65 Тираж 731 ВНИИПИ ГоСударственно по делам изобретени 113035, Москва, Ж, Р