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

(54) УСТР ЭФФИЦ НЫХ БУЛ (57) Изоб ной техни вания в Э команд в на класс л изобрете ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИ К АВТОРСКОМУ СВ 13Суп рун, Э,Г. Лазаревич ОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОИЕНТОВ ПОЛИНОМА ЛИНЕЙЕВЫХ ФУНКЦИЙретение относится к вычислительке и предназначено для использо- ВМ и спецпроцессорах с системой ысокого уровня, ориентированных огико-комбинаторных задач, Цель ния - расширение области примеИзобретение относится к вычислительной технике и предназначено для использования в Э ВМ и спецпооцессорах с системой команд высокого уровня, ориентированных на класс логико-комбинаторных задач.Известен преобразователь формы представления логических (булевых) функций, содержащий и групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА по 2" элементов в каждой. Использование преобразователя позволяет получить коэффициенты полинома Жегалкина из вектора значений логической функции и переменных (т.е, из вектора коэффициентов ее совершенной дизъюнктивной нормальной формы)..Ж 1225214 А 1 нения за счет обеспечения возможности распознавания линейности функций и упрощение, Для этого устройство для вычисления коэффициентов полинома линейных булевых функций и переменных содержит элемент И, иэлементов РАВНОЗНАЧНОСТЬ, и групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ по 2 элементов в 1-й группе ( =Ь 1=1, 2и), 2 п входов и и+2 выходов. Устройство работает следующим образом. На входы устройства поступают компоненты вектора значений У = (уо, у 1,.уп) исследуемой булевой функции Р = ЦХ 1, х 2,хп), На одном из выходов формируется булевая функция 6, единичное значение которой указывает на линейность булевой функции Е. Если 6 = 1, то на остальных и+1 выходах устройства реализуются коэффициенты полинома Жегалкина линейной булевой функции Р,1 ил. Недостатком преобразователя являетсянизкое быстродействие, определяемое глубиной схемы,Наиболее близким техническим решением к предлагаемому является преобразователь формы представления логическихфункций, содержащий и групп элементовСЛОЖЕНИЕ ПО МОДУЛЮ ДВА по 2" элементов в каждой (и - количество логическихпеременных), п элементов НЕ и и групп элементов И - ИЛИ по 2" элементов в каждой,На информационные входы преобразователя подаются коэффициенты совершеннойдизъюнктивной нормальной формы логической функции, на настроечные входы - компоненты вектора поляризации, а на его%+1= О, то переменщественной для фунт с+1 в формуле (1) ЧАЮормиХа) ых И 2 ЩЕЕ И руется о в соответствии с АЮЩЕЕ ИЛИ 1-й ируют кортеж знаб а ( б вЕн ИЗ=и рата ИСКЛЮЧАЮЩЕЕ пы формируется про) б Р 3 (х 4)б Х 4 Л(ий элемен =1,2п) сп Очевидно,есл эводн выходах реализуется вектор коэффициентов поляризованного полиномиального разложения.Недостатком известного преобразователя формы представления логических фун кций является высокая конструктивная сложность,Цель изобретения - упрощение конструкции устройства для вычисления коэффициентов полинома линейных булевых 10 функций и переменных.На чертеже представлена функциональная схема устройства при п = 4.Устройство содержит один элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 1 первой группы,2 =2 15 элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 21 и 22 второй группы, 2 = 4 элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 3134 третьей группы, 2 = 8 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 41,48 четвертой группы, и - 1 = 3 элемента РАВНОЗНАЧНОСТЬЬ 51, 52 и 5 з, элемент И 6, 2" = 16 входов 71716, и + 2 = 6 выходов 8185 и 9.Принцип работы устройства следующий.Булева функция Р = Р(х 1,х 2,.,х,) называется линейной, если имеет местоР = софс 1 х 1 фс 2 х 2 Ф спхп, (1) где сп 6(0,1) и т = 0,1,2п. Опишем алгоритм распознавания (или вычисления коэффициентов полинома) линейных булевых функций и переменных Р=Р(х 1, х 2 хп), реал из о ва н н ы й в устройстве, С этой целью введем в рассмотрение булеву функцию и - 1 переменных рс (хк+1), . хп) = Р (О .,О,хк+1хп), где ОКии Р (х 1 хп) = Р(х 1 х 2 хл)Искомый алгоритм основан на применении следующей теоремы,Т е о р е м а, Если для любого с (О 5 тт и) имеет место б р (хс+1.,хп)%+1,роизводнои , аб Хп - 1+1РАВНОЗНАЧНОСТЬ=ведливость тождества (2),онъюнкция 0 значений сигналов на выходах всех элементов РАВНО НАЧ НОСТЬ равна логической единице; исследуемая функция Р является линейной, а вектор у = (Оо, 01 (уп)= со, с 1, с 2 сп) = с - вектором коэффициентов полинома (1) линейной булевой функции Р. В этом случае оо = Р (0,0,0), а значения о 1( = 1,2п) берутся с выходов одного из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (и -1+ 1)-й группы.Устройство для вычисления коэффициентов полинома при и = 4 работает следующим образом.На входы 717 ы устройства поступают соответственно компоненты уоу 15 вектора значений исследуемой логической функции Р = Р (х 1, х 2, хз, х 4), где ук - значение функции Р на к-м наборе значений переменных х 1, х 2, хз, х 4 и 1 = 0,115. На выходе 9 устройства вычисляется функция 6, единичное значение которой указывает на линейность исследуемой логической функции Р. При 6 = 1 на выходах 8185 формируются соответственно значения сос 4 коэффициентов полинома линейной функции,П р и м е р. Пусть исследуемая логическая функция Р задана посредством следующей дизъюнктивной нормальной формыщ м жР = х 1 х 2 хзх 4 ъ х 1 хзхачх 1 хзха ч х 1 хзх 4 сЧ х 1 хзх 41 г х 1 х 2 хзх 4,Тогда на входы 71,.,716 будет подан вектор значений функции Р, который имеет вид т = (уо, у 1,у 15) = (1001, 1001, 0110, 0110).На выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4148 первой группы формиб Р (х 1, х 2, хЗ, х 4) руется производнаяб х 1б фо (х 1, х 2, хЗ, х 41, вектор значений котоб х 1рой равен Й 1 = (1111 1111).На выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 31.34 второй группы формируется прозводнаяб х 2 б х 2ектор значений которой равен М 2 =(00 одах элементов ИСКЛЮ 1 и 22 третьей группы ф б Р (О, О, хз роизводная б хз,вектор значений кот хз1725214 В. Супр ргентал Составите Техред М орректор М. Кучерявая Редактор ко Заказ 1176 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 оизводственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина На выходе 9 функция 6 равна 1, следовательно,сигналы на выходах 818 в являются компонентами вектора коэффициентов полинома Жегалкина линейной булевой функции, т.е, с = (со, с 1, сг, сз, с 4) = 5 =(1,1,0,1,1).Таким образом, исследуемая булева функция Р является линейной и представима в видег (х 1 х 2, хз х 4) = 1 вх 1 бхз Фхд, 10 Устройство имеет простую конструкцию и высокое быстродействие, обусловленные аппаратной реализацией эффективного алгоритма вычисления коэффициентов полинома линейных булевых 15 функций. Формула изобретенияУстройство для вычисления коэффициентов полинома линейных булевых функ ций, содержащее и групп элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (и - количество логических переменных), о т л и ч а ю щ е е с я тем, что, с целью расширения области применения путем обеспечения возможности распознавания линейности функций и упрощения, оно содержит элемент И и (п)-й элемент РАВНОЗНАЧНОСТЬ, причем 1-я группа элементов ИСКЛЮЧАЮЩЕЕ ИЛИ ( = 1п) содержит по 2элементов, )-й вход устройства= 12 ) соединен с первым входом )-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1-й группы, второй вход которого соединен с (2+-м входом устройства,первый вход которого является первым выходом устройства, второй вход которого соединен с выходом элемента И С КЛ ЮЧАЮЩЕЕ ИЛИ первой группы, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ К-й группы (1 = 2,.,п) соединен с (к+1)-м выходом устройства, выход 1-го ( = 12 ) элемента ИСКЛЮЧАЮЩЕЕ ИЛИ К-й группы соединен с 1-м входом к-го элемента РАВНОЗНАЧНОСТЬ, выход которого соединен с 1-м входом элемента И, выход которого является (и+2)-м выходом устройства,