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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

<>959064

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву(22) Заявлено 04.08. 80 (21) 2967529/18-24 (51)М Кп з

G 06 F 7/00 с присоединением заявки ¹â€”

Государственный комитет

СССР по делам изобретений и открытий (23) Приоритет— (531УДК 681. 3 (088. 8) Опубликовано 1509.82. Бюллетень ¹34

Дата опубликования описания 150982 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧНЫХ

БУЛЕВЫХ ФУНКЦИЙ

Изобретение относится к цифровой вычислительной технике.

Известно устройство для реализации булевых функций, представляющее собой комбинационные схемы из логических элементов И, ИЛИ, НЕ f1).

Недостатком таких устройств является низкая технологичность изготов ления в условиях технологии больших интегральных схем, что связано с нерегулярностью их внутренней структуры.

Наиболее близким по технической сущности к предлагаемому является логическое устройство для вычисления значений булевых функций, содержащее 5 ступеней постоянных запоминающих устройств, первая ступень которых включает S постоянных запоминающих устройств по числу групп обрабатываемых переменных аргументов, входы i-й ступени соединены с выхо дами (i-1)-й ступени, а выходы i-й .

:ступени соединены со входами (i+1)-й . ступени (2).

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

Цель изобретения - расширение области применения устройства путем реализ ации вычисления т. симметричных булевых функций.

Поставленная цель достигается тем, что устройство для вычисления симметричных булевых функций, содержащее блок суммирования единичных значений переменных аргумента и дешифратор, вход которого подключен к выходу блока суммирования единичных значений переменных аргумента,.вход которого подключен к и входным шинам аргументов устройства соответственно, оно содержит постоянный запоминающий узел настроечных кодов, регистр настроечных кодов и элементы И и ИЛИ, причем входы постоянного запоминающего узла настроечных кодов подклю2О чены к дополнительным k входным шинам устройства соответственно (k

=)log if) à j-й выход постоянного запоминающего узла настроечных кодов (j - "1,2,..., п+1) подключен к

25 j-ому входу регистра настроечных кодов соответственно, j-й выход которого подключен к первому входу

j-го элемента И соответственно, вто- . рой вход которого подключен к j-му

30 выходу дешифратора соответственно, 959064 метричных.

Набор х х х4

Набор

0.0 00

0001

0010

0011 выходы элементов И подключены к вхо дам элемента ИЛИ соответственно, выход которого является выходом устройства.

Блок для суммирования единичных значений переменных аргумента содер- 5 жит S ступеней постоянных запоминающих узлов, содержащих 2 ячеек, причем входы блока подключены к входам постоянных запоминающих узлов первой ступени, входу ПЗУ i-ой ступени 30 (i = t, Z,...,S; 3 = )log n 1-)log>q j+1) подключены к выходам постоянных за- помйнающих узлов (i-1)-й ступени,выходы постоянных запоминающих узлов

S-й ступени подключены к выходам бло- 15 ка.

На фиг.1 показана структурная схема устройства для вычисления симметричных булевых функций; на фиг.2 — то.же и содержимое ячеек постоянных запоминающих устройств 4 для реализации симметричной булевой функции типа четности; на фиг.З то же и содержимое ячеек постоянных запоминающих устройств для реализации симметричных булевых функций 25 типа мажоритирования, нечетности и специального вида.

Устройство (фиг.1) содержит входные шины аргументов 1, которые соединены со входами первой ступени по- 30 стоянных запоминающих узлов 2, выходы первой ступени постоянных запоминающих узлов 2 соединены со входами второй ступени постоянных запоминающих узлОВ, выходы которой соедине- 35 ны со входами следующей ступени и т.д., а выходы последней ступени постоянных заломинающих узлов 2 соединены со входом дешифратора 3, выход которого подсоединен к первому входу 4О каждой иэ групп элементов И 4, второй вход каждой иэ группы элементов

И 4 соединен с выходом одного разряда регистра настроечных кодов 5,вход которого соединен с выходом постоянного запоминающего узла настроечных кодов 6, вход которого соединен с входными шинами 1. Кроме того, выход каждой из групп элементов И 4 соединен со входами элемента ИЛИ 7, выход которой является выходом уст- 50 ройства 8. Все узлы 2 в совокупности образуют блок 9 суммирования единичных значений переменных аргумента °

Любая булева функция и аргументов имеет 2 набора, на которых она может принимать два значения: "0" .и

"1". Булева функция f(xÄ,х,..., х,,...,х,...,x„) называется симметрйчной относительно переменных х; и х), если

f(xÄ,х,,...,х;,...,х,...,x„) (xgpxgp ° ° х p ° ° ° «х1 y ° ° ° }xp) т ° е. значение функции на данном наборе не зависит от перестановки определенных переменных, Количество таких наборов P определяется видом симметричной функции (P < 2 )

Для. определения принадлежности рассматриваемой булевой функции к классу симметричных, необходимо произвести проверку по соответствующим формулам. В частности, к классу симметричных булевых функций относятся функции четности, нечетности, мажоритирования °

В устройстве используется тот факт, что произвольная симметричная функция f(x„ õ2,...,x„) от и переменных принимает единичное. значение тогда и только тогда, когда точно а (j = 1,2,...,P) переменных равны единице. Например, при n = 4 симметричная булева функция четности имеет семь наборов (Р = 7), на которых она принимает значение равное "1".

Это значит, что для данных наборов аргументов возможна перестановка значений переменных, но общее число едйниц останется тем же (четным) и. функция по-прежнему равна единице на этих наборах, т.е. выполняется условие принадлежности функции к классу симВ таблице приведены значения аргументов (соответствующих наборов) функции четности для и = 4 и выделены наборы, для которых она выполняется. В четвертом столбце указан номер набора (j = 1,...,7), на котором ровно а переменных равны единице (эначенйе а- показано в последнем столбце. таблицы), 959064

Продолжение таблицы абор

Ю(Х4 Х1 ХЭ Х4) Набор

2 Э 4

° 0

0100

0101

3 .«д». 2

0110

0111

1000

1001

1010

1011

1100

1101

1110

15

Приведенные рассуждения справедливы и для других симметричных функций. Для определения принадлежности функции к классу симметричных можно определить число единиц в обрабатываемом наборе и сопоставить его со значением а реализуемой функции. В случае равенства этих значений реализуется симметричная булева функция и значение функции равно единице (при условии, что функция принадлежит к классу симметричных).

Суммирование единичных значений переменных аргумента выполняется блоком 9, причем вход первой ступени узлов 2 которого соединен с и входными шинами аргументов 1, а выполнение требуемой симметричной функции осуществляется с помощью настроечных кодов, поступающих из постоянного запоминающего устройства настроечных кодов 6 на регистр настроечных кодов 5, а затем на первый вход каждого из элементов И 4 группы. Значение настроечного кода определяется группой из разрядов аргументов, поступающих в качестве адреса на вход постоянного запоминающего узла настроечных кодов 6.

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

Каждая ячейка постоянного узла 2

З5 первой ступени содержит двоичный код числа единиц в обрабатываемой группе разрядов кода аргумента. Ячейка постоянного запоминающего узла 2 второй и последующих ступеней содержит

40 двоичный код суммы двоичных чисел, поступивших с выходов постоянных запоминающих устройств предыдущей ступени.

Сумма единичных значений аргумен45 тов, получаемая с выходов постоянного запоминающего узла 2 последней ступени блока 9, поступает на вход дешифратора 3. Дешифратор 3 имеет и+1 выходных шин, каждая из которых щ подключается ко второму входу одной из n+1 элементов И 4. Если сумма единиц значений аргументов равна а., то единичный уровень присутствует на а -й шине выхода дешифратора 3.

Вйход а> -го элемента И 4 возбужден, если одновременно на а -й шине настройки (с регистра настроечных

3 кодов 5) и а. -й выходной шине дешифратора 3 присутствуют единичные сиг-. налы. Таким образом, если входные шины а элемента И 4 возбуждены, то ма выходе этого элемента И 4 реализуется симметричная Функция Ец-(х „,..., а

x„),Элемент ИЛИ 7 реализует дизъюйкцию +1 переменных, поступающих с

6$ выходов элементов H 4.

959064

Поскольку любая симметричная бу- такте по входным шинам 1 в устройст- лева -функция представима в виде во.

Если сигнал с дешифратора 3 не проходит через элемент И 4, то на выхо4 . < аз,"- Ор ; 1 ОФ! То предлагае де Устройства присутствует уровень мое ус,ройство может ре,изовать лю 5 соответствующий нулевоу значению бую симметричную функцию от и пере- заданной бУлевой функции. менных. Определим число ступеней системы

Вид симметричной функций опреде- постоянных запоминающих узлов, разляется настроечным кодом, хранящимся РЯцность и емкость стРУктУРных элен одной из ячеек постоянного запоми- 10 ментов, вхоДЯЩих в Устройство. нающево узла настроечных кодов 6. Длина аргумента, обрабатываемо Длина ячейки ранна и+) разряд, а ко- го Устройством, Равна сУмме n+k личество ячеек определяется количес- разрядов H CIIo PaaPsaoa k твом симметричных функций, которое пающих на адресный вход постоянного должно реализовать логическое уст- 15 запоминающего Узла настРоечных кородство. ГрУппа из k разрядов аргу- дов 6, определяется из соотношения мента, поступающая на вход постоянно- k 31oggl ),,rze 1 — achro Реали у

ro запоминающего узла настроечных ко- e z ierp ma функ ий дов 6, представляет адрес (код) сим- ШиРина постоЯнного запоминающего метричной функции, требующей реали- .щ Узла настРоечных коДов 6 Равна и+1-му зации. разряду. Требуемый объем постоянного

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

6 равен Я = 2 (и+1) .бит. Количество

1с

В первом такте в соответствии с Ячеек кажДого постоЯнного запоминаюнабором аргументов, поступающим по 25 щего Узла 2 определяется как 2, а входным шинам 1, из первой ступени объем Равен: длЯ пеРвой стУпени постоянных запоминающих узлов 2 (31og>q 3+ 1 ) -2 Ч бит, а для последуюсчитываются числа единиц в группах. щих ступеней ()loggry l +2) 2 "" бит, этого набора аргументов, а из по- где г; - количество разрядов, отвостоянного запоминающего узла настро- ДимЫх ДлЯ Двоичного пРеДставлениЯ ечных кодов 6 — настроечный код, оп- максимальной сУммы еДиниц,. постУпивределяющий симметричную функцию. ших из предыдущей i-й ступени. ЗнаВо втором такте происходит считы- чение показателя степени Равно сумвание частичных сумм из первой ступе- ме длин вступаюших в опеРацию сУммини постоянных эаломинающих узлов 2, Рования операндов (адресов). а также запись кода настройки B pe - З Число ступеней постоЯнных запомигистр 5. йающих узлов равно S=>logan(-) logq f+) >

В третьем такте считываются час- а ширина постоянного запоминающего тичные суммы из второй ступени по- узла 2 последней ступени равна стоянных запоминающих узлов 2, затем )1ояХп из третьей ступени и т.д., пока 46 Выбор количества постоянных запоне будет считана окончательная сумма минающих Узлов в каждой стУпени единиц входного набора иэ постоянно- слеДУет произвоДить, иохоДЯ из стРУкго запоминающего узла 2 последней - турной оРганизации выпускаемых проступени. мышленностью стандартных постоянных

В следующем такте окончательная 45 запомина оЩих Узлов. сумма единиц преобразовывается дешиф- Рассмотрим примеры реализации ратором 3, из двоичной позиционной симметричных булевых функций. Для системы счисления в унитарный двоич- реализации функции четности (фиг.2) ный код и сигнал,по соответствующей необходимо занести в постоянный зашине выхода дешифратора 3 поступает 1р йоминаюаяй узел 6,код, в 1,3,5,...,15 на второй вход каждого из элементов Разрядах которого записаны едийицы.

И 4 группы. В зависимости от кода Старший (левый) разряд ячейки постонастройки, поступающего с выходов янного запоминающего узла 6 равен регИстра 5 на первый вход каждого "0". Это соответствует тому, что из руементов И 4 группы, сигнал ли- сУмма единиц во входном коде Равна бо проходит, либо не проходит через "0" (присутствует единичный сигнал соответствующий элемент И 4 на его на 0-й шине дешифратора 3). Пусть выход. такой код записан в ячейке 1, .а всего реализуется 4 типа симметричных

Если сигнал проходит через эле- функций (1 = 4). Тогда количество мент И 4, то далее он проходит че- @ разрядов k =)log 1(= Z. рез элемент ИЛИ 7 на выход .8 устрой- Пусть число обрабатываемых раз2. ° ства, что соответствует единичному рядов n = 16 и обработка производитзначению заданной кодом настройки ся по 8 Разрядов (q = 8). В ячейках симметричной булевой функции на набо- постоянных запоминающих узлов 2 перре аргументов, поступившим в первом 45 вой ступени записываются двоичные

959064 10 коды, соответствующие сумме единиц в коде адреса группы обрабатываеьнх переменных. Начальные фрагменты содержимого постоянных запоминающих устройств первой ступени, следующей ступени (в данном случае она является и последней ступенью) постоянных запоминающих узлов 2 и б показаны на фиг.2. С левой стороны от географи ческих обозначений постоянных запоминающих устройств указаны. адреса ячеек. По коду адреса, соответствующему числу единиц в группе обрабатываемых переменных, производится считывание числа единиц из содержи-, мого ячейки постоянных запоминающих- аргумента определяет адрес ячейки:,в которой записано число единиц в этом адресе: нулевой адрес — нуль единиц, первый адрес — одна единица, второй адрес — одна единица и т.д.

Далее считанное значение определяет адрес ячейки постоянного запоминающего узла 2 последней ступени, в которой хранится сумма числа единиц,, присутствующих на входе в качестве адреса. åñ составляется из значений, считанных из ячеек предыдущей ступени и равен в данном случае 34.

Значение суммы поступает на вход дешифратора 3 и преобразовывается им в унитарный код.

На фиг.2 показана обработка входного кода аргумента со значением

0000 1001 0000 0011 и отмечены ячейки (их содержимое) и шины элементов

И 4, которые участвуют в реализации рассматриваемой функции четности .

Участвующие шины и ячейки отмечены стрелками. Из последней ступени по- стоянных запоминающих узлов 2 считывается позиционный код 0100, ко-, торый преобразуется дешнфратором 3 в унитарный, что.соответствует присутствию единичного сигнала на четвертой выходной шине дешифратора 3. По-. скольку код настройки,. поступающий с регистра настроечных кодов 5 на вторые входы каждого из группы элементов И 4, обеспечивает присутствие единичного сигнала во 2,4,6 и т.д. элементах И. 4 (нумерация соответствует номерам выходных шин дешифратора 3), то на выходе четвертого эле"мента И 4 присутствует единичный сигнал. Этот сигнал через элемент

HJIH 7 поступает на шину результата

8. Единичный уровень говорит.о том, что реализуется булева функция четности и число единиц в обрабатываемом коде четное.

Если требуется реализовать функцию мажоритирования от 16 переменных, принимающую единичное значение тогда, и только тогда, когда число единичных значений -аргументов не превосходит 4, то в ячейку постоянФормула изобретения

1. Устройство для вычисления симметричных булевых функций, содержащее блок суммирования единичных значений переменных аргумента н дешифратор, вход которого подключен к выходу блока суммирования единичных значений переменных аргумента, вход ного запоминающего. узла настроечных,; кодов 6 следует занести код настрой- ки 1 1111 0000 0000. Символически такая Функция записывается в виде, 0, 1 2, 3, 4 (х 1 э ° ° ° э хЯр) °

5 ka фиг.3 показана реализация функции мажоритирования, когда поступающий код равен значению 0000 0000

ОООО 0011 и ОООО 0010 ОООО 0011. Для первого случая участвующие ячейки

I0 (их содержимое) и шины элементов И 4 отмечены одной звездочкой, а во втором - двумя. Предполагается, что код настройки расположен во второй ячейке постоянного запоминающего узла б.;

f5 поэтому значение адресных разрядов узлов 2 первой ступени, т.е. значение соответствует коду "10".

Как видно из фиг.3 цля первого набора аргументов функции мажоритирования реализуются, а à второго нет. Аналогично реализуются и другие симметричные булевы ФУнкции, для чего требуется эанести соответствующий код настройки. Например, для ре.ализации функции нечетности код на-.

5 стройки имеет вид 0 1010 1010 1010 1010, а для функции, принимающей единичные значения, тогда и только тогда, когда число единичных значений аргументов кратно восьми - .следующийз 0 0000 0001 0000 0001. На фиг.3 показаны эти коды в 0-й и 3-й ячейке постоянного запоминающего узла б.соответственно.

Таким образом, введенные дополнительно структурные элементы поЗ5 зволяют реализовать данным устройством любую функцию из класса симметричных булевых (в устройстве-прототипе реализуется только мажоритарная функция) ..

49 Применение данного изобретения позволяет значительно увеличить скорость логических преобразований, повысить технологичность и надежность устройств для реализации сложных

45 логических зависимостей в системах контроля и управления. Кроме того, повышается многофункциональное использование устройства для различных применений, поскольку одно такое

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

55 устройства.

959064

12 которого подключен к п входным шинам аргументов устройства соответственно, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения путем реализации вычисления 1 симметричных булевых функций, оно содержит постоянный запоминающий узел настроечных кодов, регистр настроечных кодов и элементы И и ИЛИ, Причем входы постоянного запоминающего узла настроечных кодов подключены к допол- 10 нительным k входным шинам устройства соответственно (k = ) logroll. à j-й выход постоянного запоминающего узла .настроечных кодов (j = 1,2,...,п+l) подключен к j-му входу регистра на- 15 строечных кодов соответственно,j-й выход которого подключен к первому входу j-ro элемента И соответственно, второй вход которого подключен к .1-му выходу дешифратора соответственно, выходы элементов И подключены к входам элемента ИЛИ соответственно, выход которого является выходом устройства.

2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок для суммирования единичных значений переменных аргумента содержит s ступеней постоянных запоминающих узлов, содержащих 2 ячеек, причем входы блока подключены к входам постоянных запоминающих узлов первой ступени, входу

ПЗУ i-й ступени (i = 1,2,...,s; s

= ) 1од п(-)1од с((+1) подключены к выходам постоянных запоминающих узлов (i- l)-й ступени, выходы постоянных запоминающих узлов s-й ступени подключены к выходам блока.

Источники информации, при ня тые во в нимани е при эк сперти з е

1. Заявка ФРГ.Р 2063199, кл. G 06..F 7/38, 1974.

2. Коубилар A. Диндсей Р., Питрода С. Снижение стоимости и повышение быстродействия детекторов на основе ПЗУ. "Электроника", 1973, Р 4, с.50, рис.3 (прототип).

959064

Составитель В. Кайданов

Редактор A.Ãóëüêî Техред М.Коптура Корректор Г.Огар г

Заказ 70 17/65 Тираж 731 . Подписное

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

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

Филиал ппп "патент", г.ужгород, ул.проектная,4