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

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

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

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

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

г° г

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

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

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

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

Устройство содержит один элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 1 первой группы, 21 2 элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 и2а второй группы, 22 4 элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 3134 третьей группы, 23 8

элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4i4в

четвертой группы, п - 1 3 элемента РАВ- НОЗНАЧНОСТЬ 51, 62 и 5з, элемент И 6, 2П 16 входов 7i,...,7i6, п + 2 6 выходов 8185 и 9.

Принцип работы устройства следующий.

Булева функция F F(xi,X2xn) называется линейной, если имеет место

F Со еС1Х1«С2Х2ф..СпХп,(1)

гдестЈ{0,1}и т 0,1,2п.

Опишем алгоритм распознавания (или вычисления коэффициентов полинома) линейных булевых функций п переменных F F(xi,X2xn), реализованный, в устройстве. С этой целью введем в рассмотрение булеву функцию n-k переменных pk (xk-н)хп) F (0 ...,0,xk+iхп), где 0

k П-1 И p0 (X1Xn) F(X1,X2Xn).

Искомый алгоритм основан на применении следующей теоремы.

Теорема. Если для любого t (0 t t n-2) имеет место

dfrOft +1Xn)+

dxt +

(2)

где Ot + it{0 1} T° F(xi, X2xn)-линейная

булева функция.

Причем, если в (2)0t +1 0, то переменная xt+1 является несущественной для фун- кции F и коэффициент ct+t в формуле (1) равен 0.

Устройство построено в соответствии с (2). Элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 1-й группы (I 1,2п) формируют кортеж зна-

d Фп -

чений булевой производной --, а

d xn -1 + 1

(n-JJ-й элемент РАВНОЗНАЧНОСТЬ 0

1,2п-1) справедливость тождества (2).

Очевидно, если конъюнкция G значений сиг5

10

15

0

5

0 5

0

5

налов на выходах всех элементов РАВНОЗНАЧНОСТЬ равна логической единице, исследуемая функция F является линейной, а вектор 0 (а0, ) со, ci,

С2Сп) с - вектором коэффициентов

полинома (1) линейной булевой функции F. В этом случае а0 F (0,0,..,0), а значения а (I 1,2,...,п) берутся с выходов одного из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (п - + 1)-й группы.

Устройство для вычисления коэффициентов полинома при п 4 работает следующим образом.

На входы 7i,...,7i6 устройства поступают соответственно компоненты y0,...,yis вектора значений исследуемой логической функции F F (xi, Х2, хз, Х4), где yk - значение функции F на k-м наборе значений переменных xi, Х2, хз, Х4 и k 0,115. На выходе 9

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

При G 1 на выходах 8i85 формируются

соответственно значения с0,...,С4 коэффициентов полинома линейной функции.

Пример. Пусть исследуемая логическая функция F задана посредством следующей дизъюнктивной нормальной формы

F Х1Х2ХЗХ4 VX1X3X4VX1X3X4 VX1X3X4 V V X1X3X4VX1X2X3X4.

Тогда на входы 7i7ie будет подан

вектор значений функции F, который имеет

вид Y (уо, yiУ15) (1001, 1001, 0110,

0110).

На выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4i4в первой группы формируется производная d F (Х1 2 хз

d xi

d Ро (Х1, Х2, ХЗ, Х4)

- .s вектор значении котоd xi

рой равен NI (1111 1111).

На выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3i84 второй группы формируется проd F (О, Х2. ХЗ. Х4) d (Х2. ХЗ. Х4) d X2d X2

вектор значений которой равен N2 (0000).

изводная

Нз выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 2i и 22 третьей группы формируется производная . 3 4

а хз

d (pi (ХЗ, Х4)

- -Ј-- вектор значении которой равен N3 (11).

На выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1 четвертой группы формируется проd F (О, О, О, Х4) d с0з (х4) изводная5 -- v 1.

d X4

d X4

На выходе 9 функция G равна 1, следо- вательно,сигналы на выходах 8i,...,8s являются компонентами вектора коэффициентов полинома Жегалкина линейной булевой функции, т.е. с (с0, ci, С2, сз, СА) (1,1,0,1,1).

Таким образом, исследуемая булева функция F является линейной и представи- ма в виде

F (Х1, Х2, ХЗ, Х4) 1 ©Х1 Фхз Х4.

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

Формула изобретения Устройство для вычисления коэффициентов полинома линейных булевых функ- ций, содержащее п групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (п - количество логических переменных), отличающееся

0

5

0

тем, что, с целью расширения области применения путем обеспечения возможности распознавания линейности функций и упрощения, оно содержит элемент И и (п-1)-й элемент РАВНОЗНАЧНОСТЬ, причем i-я группа элементов ИСКЛЮЧАЮЩЕЕ ИЛИ

(I 1п) содержит по 2м элементов, j-й

вход устройства Q 1,...,2М) соединен с первым входом j-ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1-й группы, второй вход которого соединен с (2 +j)-M входом устройства, первый вход которого является первым выходом устройства, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ первой группы, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ k-й группы (к 2п) соединен с (к+1)-м выходом устройства, выход 1-го (I ) элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ k-й группы соединен с 1-м входом k-ro элемента РАВНОЗНАЧНОСТЬ, выход которого соединен с к-м входом элемента И, выход которого является (п+2)-м выходом устройства.

Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с системой команд высокого уровня, ориентированных на класс логико-комбинаторных задач. Цель изобретения - расширение области применения за счет обеспечения возможности распознавания линейности функций и упрощение. Для этого устройство для вычисления коэффициентов полинома линейных булевых функций h переменных содержит элемент И, п-1 элементов РАВНОЗНАЧНОСТЬ, п групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ по 2й элементов в 1-й группе (i i, 2n), 2 п входов и п+2 выходов. Устройство работает следующим образом. На входы устройства поступают компоненты вектора значений Y (у0, yi,...yn) исследуемой булевой функции F F(xi, X2,...xn). На одном из выходов формируется булевая функция G, единичное значение которой указывает на линейность булевой функции F. Если G 1, то на остальных п+1 выходах устройства реализуются коэффициенты полинома Жегалкина линейной булевой функции F. 1 ил. сл