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

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

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

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

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

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

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

с булевых функций.

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

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

15 содержит постоянный запоминающий 3ел настроечных кодов, регистр на5 троечных кодов и элементы И и ИЛИ, причём входы постоянного запоминающего узла настроечных кодов подключены к дополнительным k входным шинам устройства соответственно (k ,lt),a j-й выкод постоянного запоминающего узла настроечных кодов (з 1,2,..., -ntl) подключен к

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

30 выходу дешифратора соответственно. выходы элементов И подключены к входам элемента ИЛИ соответственно, выход которого является выходом устройства. Блок для суммирования единичных значений переменных аргумента содержит S ступеней постоянных запоминающих узлов, содержащих 24- ячеек, причём входы блока подключены к входам постоянных запоминающих узлов первой ступени, входу ПЗУ i-ой ступени (i Ь2,...,5; j Jlog nt-Dlog qr+ подключены к выходам постоянных за-.. поминающих узлов (1-1}-й ступени,выходы постоянных запоминающих узлов S-й ступени подключены к выходам бло ка. На фиг.1 показана структурная схе ма устройства для вычисления симметричных булевых функций; на фиг.2 - то же и содержимое ячеек постоянных запоминающих устройств для реализации симметричной булевой функции типа четности; на фиг.З то же и содержимое ячеек постоянных запоминающих устройств для реализации симметричных булевых функций типа мажоритирования, нечетности и специального вида. Устройство .(фиг.1) содержит входные шины аргументов 1, которые соединены со входами первой ступени постоянных запоминающих узлов 2, выходы первой ступени постоянных запоминающих узлов 2 соединены со входами второй ступени постоянных запоминающих узлов, выходы которой соедине ны со входами следующей ступени и т.д., а выходы последней ступени постоянных запоминающих узлов 2 соединены со входом дешифратора 3, выход которого подсоединен к первому входу каждой из групп элементов И 4, второй вход каждой из группы элементов И 4 соединен с выходом одного разряда регистра настроечных кодов 5,вход которого соединен с выходом постоянного запоминающего узла настроечных кодов 6, вход которого соединен с входными шинами 1, Кроме того, выход каждой из групп элементов И 4 соединен со входами элемента ИЛИ 7, выход которой является выходом устройства 8. Все узлы 2 в совокупности образуют блок 9 суммирования единичных значений переменных аргумента. Любая булева функция п аргументов имеет 2 набора, на которых она может принимать два значения: О и 1. Булева функция f(x,x,, .... .,Xj) называется симметричной относительно переменных х и Xj, если ,),Xn,...,X:,...,,..., - ff (.X , Х Х.- , . . . ,Х,- , . . . , Х(/ , т.е. значение функции на данном наборе не зависит от перестановки определенных переменных. Количество таких наборов Р определяется видом симметричной функции (Р i 2). Для, определения принадлежности рассматриваемой булевой функции к классу симметричных, необходимо произвести проверку по соответствую- щим формулам. В частности, к классу симметричных булевых функций относятся функции четности, нечетности, мажоритирования. В устройстве используется тот факт, что произвольная симметричная функция Сх ,Х2,.. . ,Хп} от п переменных принимает единичное значение тогда и только тогда, когда точно аj Сj 1,2,...,Р) переменных равны единице. Например, при п 4 симметричная булева функция четности имеет семь наборов (Р 7), на которых она принимает значение равное 1. Это значит, что для дйнных наборов аргументов возможна перестановка знагчений переменных, но общее число единиц останется тем же (четным) и функция по-прежнему равна единице на этих наборах/ т.е. выполняется условие принадлежности функции к классу симметричных, В таблице приведены значения аргументов (соответствующих наборов) функции четности для п 4 и выделены наборы, для которых она-выполняется. В четвертом столбце указан номер набора (J 1,...,7), на котором ровно aj переменных равны единице (значение а показано в последнем столбце таблицы).

0.000 0001 0010 ООН

о

о о

1

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

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

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

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

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

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

сумма единичных значений аргументов, псэлучаемая с выходов постоянного запоминаквдего узла 2 последней ступени блока 9, поступает на вход дешифратора 3. Дешифратор 3 имеет п-1-1 выходных шин, каждая из которых

Q подключается ко второму входу одной и п+1 элементов И 4. Если сумма единиц значений аргументов равна aj, то единичный уровень присутствует на аj-и шине выхода дешифратора 3.

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

60 шины а,- элемента И 4 возбуждены, то -иа выходе этого элемента И 4 реализуется, симметричная функция fQj(x,. х„).Элемент ИЛИ 7 реализует дизъюнкцию +1 переменных, поступающих с

65 выходов элементов И 4.

Поскольку любая симметричная булева функция представима в виде

f-V

3,с|,г.а,,.-.«р-j,/«j то предлагаемое устройство может реализовать любую симметричную функцию от п переменных.

Вид симметричной функции определяется настроечным кодом, хранящимся В одной из ячеек постоянного запоминающепо узла настроечных кодов 6. Длина ячейки равна разряд, а количество ячеек определяется количеством симметричных функций, которое должно реализовать ;г1огическое устройство. Группа из k разрядов apiryмента, поступающая на вход постоянного запоминающего узла настроечных кодов б , представляет адрес (код) симметричной функции, требующей реализации.

Работа устройства происходит в несколько тактов.

В первом такте в соответствии с набором аргументов, поступакядим по входным шинам 1, из первой с гупени постоянных запоминающих узлов 2 считываются числа единиц в группах, этого набора аргументов, а из постоянного запоминающего узла настроечных кодов б - настроечный код, определяющий симметричную функцию.

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

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

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

Если сигнал проходит через элемент И 4, то далее он проходит через элемент ИЛИ 7 на выход 8 устройства, что соответствует единичному значению заданной кодом настройки f симметричной булевой функции на наборе аргументов, поступившим в первом

такте по входным шинам 1 в устройство.

Если сигнал с дешифратора 3 не проходит через элемент И 4, то на выходе устройства присутствует уровень, соответствующий нулевому значению дданной булевой функции.

Определим число ступеней системы постоянных запоминающих узлов, разряд1яость и емкость структурных элеO ментов, входящих в устройство.

Длина аргумента, обрабатываемого устройством, равна сумме .n+k разрядов. Число разрядов k, поступающих на адресный вход постоянного 5 запоминающего узла настроечных кодов б, определяется из соотношения k , где 1 - число реализуемых симметричный функций.

Ширина постоянного запоминающего ft узла настроечных кодов 6 равна п- -1-му разряду. Требуемый объем постоянного запоминающего узла настроечных кодов. б равен Q, 2() бит. Количество ячеек каждого постоянного запоминающего узла 2 определяется как , а

объем равен: для первой ступени (JlogjqC+l) , а для последующих ступеней ( 2)- 2- бит, где г. - количество разрядов, отводимых для двоичного представления Максимальной суммы единиц,.поступив- .

ших из предыдущей 1-й ступени. Значение показателя степени равно сумме длин вступающих в операцию суммирования операндов (адресов).

5 Число ступеней постоянных запоминающих узлов равно S Jlogin -J log,.qf«-5 , а ширина постоянного запоминающего узла 2 последней ступени равна log2n -b1.

0 Выбор 1соличества постоянных запоминающих узлов в каждой ступени следует производить, исходя из структsфнoй организации выпускаемых прогфлоленностыб стандартных постоянных

5 запоминакядих узлов.

Рассмотрим примеры реализации симметричных булевых функций. Для реализации функции четности (фиг.2) необходимо занести в постоянный заIQ поминающий узел 6,код, в 1,3,5,. ..,15 разрядах записаны единицы. Старший (левый) разряд ячейки постоянного запоминающего узла 6 равен О. Это соответствует тому, что

, сумма единиц во входном коде равна О (присутствует единичный сигнал на 0-й шине дешифратора 3). Пусть такой код записан в ячейке 1, а всего реализуется 4 типа симметричных функций (1 4). Тогда количество

разрядов k log2lf 2.

Пусть число обрабатываемых разрядов п 16 и обработка производится по 8 разрядов (q 8). В ячейках постоянных запоминающих узлов 2 первой ступени записываются двоичные

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

На фиг.2 показана обработка входного кода аргумента со значением 0000 1001 0000 ООН и отмечены ячейки (их содержимое) и шины элементов И 4, которые участвуют в реализации рассматриваемой функции четности. Участвукяцие шины и ячейки отмечены стрелками. Из последней ступени по- : стоянных запоминающих узлов 2 считыв§ется позиционный код 0100, ко-; торый преобразуется дешифратором 3 в унитарный что соответствует прИсутствию единичного сигнала на четве1ртой выходной шине дешифратора 3, По-. скольку код настройки, поступающий с регистра настроечных кодов 5 на вторые входы каждого из группы элементов И 4, обеспечивает присутствие едщничного сигнала во 2,4,6 и т.д. элементах И 4 (нумерация соответствует номерам выходных шин дешифратора 3), то на выходе четвертого элемента И 4 присутствует единичный си1-нал. Этот сигнал через элемент ИЛИ 7 поступает на шину результата 8. Единичный уровень говорит о том, что реализуется булева функция четности и число единиц в обрабатываемом коде четное.

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

;Ного запоминающего узла настроечных 1 кодов 6 следует занести код настройки 1 1111 0000 0000. Символически такая функция записывается в виде

(X.

fr) .

, 0,1.1,3,4 ,

На фиг.З йоказана реализация функции мажоритирования, когда поступающий код равен значению 0000 0000 0000 ООН и 0000 0010 0.000 ООН. Для первого случая участвующие ячейки

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

Как видно из фиг.З, йля первого набора аргументов функции мажоритиро вания реализуются, а Для второго - нет. Аналогично реализуются и другие

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

5 jlOlO, а для функции, принимающей единичные значения, тогда и только тогда, когда число единичных значений аргументов кратно восьми - следующий: О 0000 0001 0000 0001. На фиг.З

0 показаны эти коды в 0-й и 3-й ячейке . постоянного запоминающего узла 6.соответственно.

Таким образом, введенные дополнительно структурные элементы по-

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

0

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

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

5

Формула изобретения

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

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

№ 4, С.50, рис.3 (прототип).

ГГЦ

о ,-«.Jtr

к

оо

«so

§§ §

eJ

5§

§§

l

Э «VJ t