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

 

Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с системой команд высокого уровня, ориентированных на класс логико-комбинаторных задач. Цель изобретения - расширение области применения за счет обеспечения возможности распознавания линейности функций и упрощение . Для этого устройство для вычисления коэффициентов полинома линейных булевых функций 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 ил. сл

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (я)5 G 06 F 7/00

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4798197/24 (22) 28.02.90 (46) 07.04.92. Бюл. hb 13 (72) Л.Б. Авгуль, B.Ï. Супрун, Э,Г. Лазаревич и В.И. Костеневич (53) 681.3 (088.8) (56) Авторское свидетельство СССР

М 1124281, кл. G 06 F 5/00, 1983. Авторское свидетельство СССР

hh 1441381, кл. G 06 F 5/00, 7/00, 1987. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ПОЛИНОМА ЛИНЕЙНЫХ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с системой команд высокого уровня, ориентированных на класс логико-комбинаторных задач, Цель изобретения — расширение области примеИзобретение относится к вычислительной технике и предназначено для использования в Э ВМ и спецпроцессорах с системой команд высокого уровня, ориентированных на класс логико-комбинаторных задач.

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

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА по 2" элементов в каждой. Использование преобразователя позволяет получить коэффициенты полинома Жегалкина из вектора значений логической функции п переменных (т.е. из вектора коэффициентов ее совершенной дизъюнктивной нормальной формы). Ж 1725214 А1 нения за счет обеспечения возможности распознавания линейности функций и упрощение, Для этого устройство для вычисления коэффициентов полинома линейных булевых функций п переменных содержит элемент И, п-1 элементов РАВНОЗНАЧНОСТЬ, и групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ по 2 элементов в i-й группе (i =

I-1

=i, 2,...,n), 2 и входов и n+2 выходов. Устройство работает следующим образом. На входы устройства поступают компоненты вектора значений Y = (yo, у1,...yn) исследуемой булевой функции F = F(xi, xz,...xr), На одном из выходов формируется булевая функция G, единичное значение которой указывает на линейность булевой функции

F. Если G = 1, то на остальных и+1 выходах устройства реализуются коэффициенты полинома Жегалкина линейной булевой функции F, 1 ил.

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

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА по 2" элементов в каждой (и — количество логических переменных), и элементов НЕ и и групп элементов И вЂ” ИЛИ по 2" элементов в каждой.

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

1725214 бр(хс+1" хп)

%+1, (2) ГдЕ О1 + 1 (0,1}, та F (X1, Х2,...,Xn) — ЛИНЕйНая булева функция.

Причем, если в (2) % +1 = О, то переменная х1+1 является несущественной для фун- 50 кции F и коэффициент с +1 в формуле (1) равен О.

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

d pn — 1 чений булевой производной, а б Xn — 1+1 (n-j)-й элемент PABНОЗНАЧНОСТЬ (j =

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

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

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

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

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

Устройство содержит один элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 1 первой группы,2 =2 15 элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 21и22 второй группы, 2 = 4 элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 31,...,34 третьей группы, 2 = 8 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 41„„,48 четвертой группы, n - 1 = 3 элемента PAB- 20

НОЗНАЧНОСТЬ 51, 52 и 5з, элемент И 6, 2п = 16 входов 71...„716, n + 2 = 6 выходов

81,...,85 и 9.

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

Булева функция F = F(x1,x2 х,) называется линейной, если имеет место

F = Co+C1X1@C2X24 " СпХп, (1) где cmC(0,1) и m = 0,1,2,...,n.

Опишем алгоритм распознавания (или 30 вычисления коэффициентов полинома) линейных булевых функций и переменных Е=

F(X1,X2,...,Хп), РЕаЛИЗОВаННЫй В УСтройстве. С этой целью введем в рассмотрение булеву функцию n — k переменных 35 р< (Xk+1)...,Xn) = Р (О ...,О,ХК+1,...,Xn), ГдЕ О (+k (и-1 и ро (x1,...,хп) = F(x1,x2,...,xn), Искомый алгоритм основан на применении следующей теоремы, Т е о р е м а. Если для любого t (О (t 40 т(п-2) имеет место налов на выходах всех элементов РАВНО3 НАЧ НОСТЬ равна логической единице; исследуемая функция F является линейнОй, а вЕктОР 0 = (Oo, О 1, ..,, 0 и)= Со, С1, C2„...Cn) = С вЂ” ВЕКТОРОМ КОЭффИЦИЕНтОВ полинома (1) линейной булевой функции F. В этом случае оп = F (0,0...,0), а значения Oj(i = 1,2,...,п) берутся с выходов одного из элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ (n - i + 1)-й группы.

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

На входы 71,...,7ы устройства поступают

СООтВЕтСтВЕННО КОМПОНЕНТЫ yo,".,y1S ВЕКтОра значений исследуемой логической функции F = F (х1, x2i х3, х4), где ук — значение функции F на к-м наборе значений переменных х1, х2, х3, х4 и k = 0,1,...,15. На выходе 9 устройства вычисляется функция G, единичное значение которой указывает на линейность исследуемой логической функции F.

При G = 1 на выходах 81,...,85 формируются

СООтВЕтСтВЕННО ЗНаЧЕНИЯ Co,...,Ñ4 КОЭффИЦИентов полинома линейной функции.

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

F = Х1Х2ХЗХ4 v X1X3X4vx1X3X4VX1X3X4 i

V x1x3x4xi x1õ2õ3õ4

Тогда на входы 71,...,716 будет подан вектор значений функции F, который имеет вид Y = (уо, у1 ° у15) = (1001, 1001, 0110, 0110).

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

d x1 б Ро (Х1, Х2, ХЗ, Х41, вектор значений котоd x1 рой равен N1 = (1111 1111).

На выходах элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ 31...„34 второй группы формируется производная б х2 бх2 вектор значений которой равен N2 =(0000).

Нз выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 21 и 22 третьей группы формиб F (0, 0, õç, õ4) руется производная б хз б Р2 (x3 х4) ,вектор значений которой pad хз вен N3 = (11).

На выходе элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ 1 четвертой группы формируется npod F (О, О, О, x4) d рз (х4)

d X4 б Х4

1725214

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

Техред М.Моргентал

Корректор М. Кучерявая

Редактор B. Данко

Заказ 1176 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

На выходе 9 функция G равна 1, следовательно,сигналы на выходах 8,...,8s являются компонентами вектора коэффициентов полинома Жегалкина линейной булевой функции, т.е, с = (со, с1, сг, сз, с4) = 5

=(1,1,0,1,1).

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

F (x1, хг, х3, х ) = 1 +x1@хз ха, . 10

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

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

Устройство для вычисления коэффициентов полинома линейных булевых функ- 20 ций, содержащее и групп элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ (и — количество логических переменных), о т л и ч а ю щ е е с я тем, что, с целью расширения области применения путем обеспечения возможности распознавания линейности функций и упрощения, оно содержит элемент И и (п-1)-й элемент РАВНОЗНАЧНОСТЬ, причем i-я группа элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (! = 1,...,n) содержит по 2 элементов, J-й вход устройства () = 1,...,2 ) соединен с первым входом J-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1-й группы, второй вход которого соединен с (2+))-м входом устройства, i первый вход которого является первым выходом устройства, второй вход которого соединен с выходом элемента И С КЛ ЮЧАЮЩЕЕ ИЛИ первой группы, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ k-й группы (k = 2,. „n) соединен с (1+1)-м выходом устройства, выход 1-го (I = 1,...,2 ) элемента

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

k-м входом элемента И, выход которого является (и+2)-м выходом устройства.