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

11

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

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

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

Устройство содержит двадцать восемь элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2 1-28, восемь входов 29-36 устройства восемь выходов 37-44 первой группы, восемь выходов 45-52 второй группы.

Симметрическая булевая функция (с.б.ф.) F F(x ,,х) может быть преставлена двоичным вектором ТГСР) (1Г(, , ST, где значение F на наборе (любом) п двоичных перемен- ных с i единицами (,...п).

Пусть P(F) и Q(F) - монотонно поляризованные полиномы с.б.ф. F, причем полином P(F) поляризован по переменным х,,...,х„ положительно, а по- лином Q(F) - отрицательно. В общем случае полиномы P(F) и Q(F) для с.б. можно записать следующим образом:

P(F) + у(х, .; ,вх,)Ф ),(х,...

eXjX e&XjX ®. . .вх,

Хл;

р(Р) Но®иД5с,.. .Фх J®/Xj(. . ..„., х„)Ф.. .... Xv,;

где -J-o h ,l ) и i ().

Поскольку полиномы P(F) и Q(F) однозначно определяются (h+1)-разрядными булевыми векторами y(F)(y , „) и 4(F) () то задача полиномиального разложения с.б.ф. F сводится к преобразованию вектора ir(F) в булевы векторы ) и f(F)

соответственно.

Введем в рассмотрение специ-альную двоичную таблицу треугольного вида,

которую обозначим через Т(,(о()

ol;jji,, где i (ОТп) и j (0,n-i).

Таблица T(d) имеет n+l строку и ее 0я строка совпадает с некоторьм (п+1)-разрядным вектором ci ( , ). Остальные элементы Т„(о) связаны между собой следующими соотношениями:

K,- ° t-i J

(1)

где - j-й злемент К-й строки

(,...,п| ,...,п-к). Пусть крайние левые (правые) зле- менты строк таблицы Т(й() образуют булев вектор R(R j), где 13, (ofoe ,

) ч с о Oh he/

Будем говорить, что булев вектор fl(flj) является результатом преобразования . ((I) заданного вектора d.

Работа устройства основана на следующем утверждении.

Если F симметрическая булевая функция (с. б .ф.) , то

(F) И, (ff (F)); (2)

H(F) (ff (F, (3)

и с учетом (1) и (2) имеет место:

f(F) л(

Пример . Пусть и (i CF) (00111), т.е. F F(x,X,)

jVXjX VXjX .

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

t ff. 1Г. ff. fi.

50

r- И4

Очевидно, что j (F) (00101) и H(F) (10011). Тогда

P(F)x, х,Хз Ф х,х ф XjX @

, ® х,х

Q(F) © ® ©

+ X,

Устройство работает (согласно

(3)) следующим образом.

На

(2)

его i-й вход, где i (1,п+1), подается (1-1)-я компонента j.i вектора n( F) разлагаемой с.б.ф, F F(x,x). На i-oM выходе устройства первой группы выходов формируется (1-1)-я компонента -уц., вектора (F), а на i-oM выходе устройства второй группы выходов - (1-1)-я компонента р,-. вектора /и ().

Если же на входы устройства подать соответствующие ко1«ц1оненты вектора F) , то учитывая (4), на выходах первой группы будут сформированы компоненты вектора 1Г().

Так, если на входы 29-36 устройства подать вектор « (F) (01100111) некоторой с.б.ф. (x77x) то на его выходах 37-44 .первой группы получим вектор -J(F) (01100001) , а на выходах 45-52 второй группы - вектор M(F)(10011111).

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

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

10

15

20

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

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

. j-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2

(К-1)-й группы, второй вход соединен 25 с выходом (j+1)-ra элемента СЛОЖЕНИЕ

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

30

35

29

373839 0 1 2 J

1 г Ь1гг1 т1г11г11г112

- Г в 7« 7 23 25 гв

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

JZ

11

17

35

46

r

36 5

49

22