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

 

Изобретение относится к области вычислительной техники и предназначено для использования в ЭВМ и специализированных процессорах с системой команд высокого уровня. Цель изобретения - упрощение устройства для полиномиального разложения симметрических булевых функций и расширение его функциональных возможностей за счет реализации монотоннЬ поляризованных полиномиальных разложений. Поставленная цель достигается тем, что устройство для полиномиального разложения симметрических булевых функций от п переменных содержит п групп элементов СЛОЖЕНИЕ ПО МОДУЛО 2 по n-i+1 элементов в (,2,...,n), n+l входов, n+1 выходов первой группы выходов и п+1 выходов второй группы выходов. На входы устройства подается булев вектор однозначно задающий разлагаемую симметрическую булеву функцию, а на выходах устройства первой и второй групп реализуются булевы , определяющие соответственно попожительно и отрицательно поляризованные полиномы симметрической булевой функции- 1 ил. § (Л

СЭОЗ СОВЕТСНИХ

СОЦИАЛ ИСТИЧЕСНИХ

РЕСПУБЛИН

ОПИСАНИЕ ИЗОБРЕТЕНИЙ

К А BTOPCHOlVIY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4234306/24-24 (22) 22.04.87 .(46) 15.12.88. Бюл. У 46 (72) Л.Б. Авгуль и В . П, Супрун (53) 681.3(088.8) (56) Авторское свидетельство СССР

Р 781822, кл. С 06 F 15/31, 1978.

Авторское свидетельство СССР

Ф 1124281, кл. G 06 F 5/00, 1983. (54) УСТРОЙСТВО ДЛЯ ПОЛИНОМИАПЬНОГО

РАЗЛОЖЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ

ФУНКЦИЙ (57) Изобретение относится к области вычислительной техники и предназначено для использования в ЭВМ и специализированных процессорах с системой команд высокого уровня. Цель изобретения — упрощение устройства для полиномиального разложения симметрических булевых функций и расширение

ÄÄSUÄÄ 444743 А1 (51)4 С 06 F 5/00 его функциональных возможностей за счет реализации монотонно поляризо-ванных полиномиальных разложений.

Поставленная цель достигается тем, что устройство для полиномиального разложения симметрических булевых функций от п переменных содержит п групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ

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

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

1 ил.

1444 к = к-1 3 ® к-(J + 1 э

К1 (2) (3) т, О 1 О О, 721 1 О Р2 у, 0 1 Н

f41 р4

Хп т

+ Х Х Х Ю Х1Х Х Х

Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и специализированных процессорах с системой команд высокого уровня.

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

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

Устройство содержит двадцать восемь элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2

1-28, восемь входов 29-36 устройства восемь выходов 37-44 первой группы, восемь выходов 45-52 второй группы. 20

Симметрическая булевая функция (с.б.ф.) F = F(x,х„) может быть представлена двоичным вектором rr(F)

=(,, Т, где Р; — значение F на наборе (любом) и двоичных перемен- 25 ных с i единицами (i=O;...,n), Пусть P(F) и Q(F) — монотонно поляризованные полиномы с.б.ф. F, причем полином P(F) поляризован по переменным х,,...,х„ положительно, а по- 30 ликом Q(F) — отрицательно. В общем случае полиномы P(F) и Q(F) для с.б.ф можно записать следующим образом:

Р(Р) g,+ у (х, ®Х Э...ЕХ„)Е у (х„х @... 35

®X r X ЮХ Х Юа ° Зх Х )Юв ° е®) Х Х а ° °

Q (F) = p @p„(x„&x Ф ° ° Фхн ) EB p<(x„®x

Qx„x„9x х 9...8R„, х„)9...®p„x х где p, ; е10,1 1 и i = (О,n), Поскольку полиномы P(F) и Q(F) однозначно определяются (h+1)-разрядными булевыми векторами 1 (F) =(g у„) и р(Р) = (р,,р„), то задача полиномиального разложения с.б,ф. F сводится к преобразованию вектора

«(F) в булевы векторы у(Р) и p(F) соответственно.

Введем в рассмотрение специальную двоичную таблицу треугольного вида, которую обозначим через Т„(5 )

=(A;; jIr, где i = (O,n) и j = (О,п-i).

743 г I

Таблица Т„() имеет n+1 строку и ее

О-я строка совпадает с некоторым (n+1) -разрядным вектором а(= (с, 3,Д) . Остальные элементы Т„() связа ны между собой следующими соотношениями: где а(к1 — j-й элемент К-й строки (К=1,...,n; п=о,...,n-К) .

Пусть крайние левые (правые) элементы строк таблицы Т „() образуют булев вектор И,(И ), где l3, = (a(„, ° ° ° э".о); e = (î„э,аь 1э ° ° ° эАь) °

Будем говорить, что булев вектор и (В ) является результатом преобразования . i„() заданного вектора a(.

Работа устройства основана на следующем утверждении, Если F симметрическая булевая функция (с.б;ф.), то

1 (F) = i„ ((F));

p(F) = r g(«(F).), и с учетом (1) и (2) имеет место:

7rr(F) = .,((Р)) (4) Пример . Пустьn=4 и «(Р)= (00111), т.е. F = F(x,...,,õ ) — xÄxzvxÄx > X Äx

Используя вышеописанный метод, сформируем таблицу Т <(fr(F) ):

y,о о 1 1 1Р, Очевидно, что (Р) = (00101) и

p(F) = (10011) . Тогда

Р(Р)=х„х 9 х„х Ых,х Ж х,х Щ х х

9х х ®х х х х

Q(F) — 1®х х х Ю х 1х х 9 Х1х х У

3 14447

Устройство работает (согласно (2) и (3)) следующим образом.

На его i-й вход, где i = (1,п+1), подается (i-1)-я компонента ; вектора и(Р) разлагаемой с.б.ф. F =

= F(x õ„). На i-ом выходе устройства первой группы выходов формируется (i-1)-я компонента 1;»,вектора

» (F), à íà i-ом выходе устройства 10 второй группы выходов — (i-1)-я компонента p,, вектора p (F) .

Если же на входы устройства подать соответствующие компоненты вектора фР), то учитывая (4), на выхо- 15 дах первой группы будут сформированы компоненты вектора 7(Р).

Так, если на входы 29-36 устройства подать вектор It(F)=(01100111) некоторой с.б.ф. F=F(x,,õ ), то на 20 его выходах 37-44,первой группы получим вектор т(Р)=(01100001), а на выходах 45-52 второй группы - вектор

» (Р) = (10011111) .

При подаче же на входы 29-36 устройства значения вектора у(Р) (01100001) на выходах 37-44 первой группы получим обратное преобразование — вектор 7/ (Р) =(01100111) . 30

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

43

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

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

1 функций, содержащее п групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2 (и — количество двоичных переменных разлагаемой функции), о т л и ч а ю щ е е— с я тем, что, с целью упрощения и расширения функциональных возможностей за счет реализации монотонно поляризованных полиномиальных разложений, каждая i-я группа содержит по и-i+1 элементов СЛОЖЕНИЕ ПО МОДУЛЮ

2 (i = 1,...,n), причем i-й вход устройстЪа соединен с первым входом хго элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 первой группы, второй вход которого соединен с (i+1). — м входом устройства, первый вход j-го элемента СЛОЖЕНИЕ

ПО МОДУЛЮ 2 К-й группы (1= 1,...,п-.

К+1; К=2, ...,n) соединен с выходом

j-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 (К-1)-й группы, второй вход соединен с выходом (j+1)-го элемента CJIOKEHHE

ПО МОДУЛЮ 2 (К-1)-й группы, первый вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 i-й группы соединен с i-ым выходом устройства первой группы, второй вход (п-i+t)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 i-й группы соединен с i-ым выходом устройства второй группы выходов, (п+1)-й выход которой соединен с (n+1)-ым выходом устройства первой группы и выходом элемента

СЛОЖЕНИЕ ПО МОДУЛЮ 2 п-й группы. 1444743

С ос тавит ел ь В . С ор окин

Редактор А,Ревин Техред М. Ходанич Корректор M Ïîæî

Заказ .6506/47 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул, Проектная, 4