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

(54) УСТРОЙСТВО ДЛЯ ВЬЧИСЛЕНИЯ ФУНДАМЕНТАЛЬНЬТХ СИММЕТРИЧЕСКИХ БУЛЕВЬТХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет (В)(73) Патентообладатель Белорусский государ ственный университет (ВЧ)Устройство штя вычисления фундаментальных симметрических булевых функций, содержащее три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый и второй мажоритарные элементы с порогами 2 р-2 (рп/2 п - количество переменных фунтошй) и 2 р соответственно, элемент И, выход которою соединен с выходом устройства, а входы с первого по третий соединены соответственно с выходами первого, второю и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, при этом первые входы второго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединены соответственно с выходами первого и второю мажоритарных элементов, информационные входы устройства с первого по п-й соединены соответственно с первою по 11-й входами первого и второго мажоритарных элементов и первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, (п 1)-й вход которого соединен с первым настроенным входом устройства, второй и третий настроенные входы которого соединены со вторыми входами соответственно втошго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, отличающееся тем, что 3-й (1 4, р 1) настроенный вход устройства соединен сИзобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации фундаментальных симметрических булевых функций п переменных.Известно устройство для вычисления фундаментальных симметрических булевых функций п переменных, содержащее К (1 1 о 32 п 1) элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, эле п мент ИЛИ-НЕ, р (р мажоритарных элементов с порогами 24,,2 р п информационныхНедостатком устройства является высокая конструктивная сложность по числу входов логических элементов. О ПНаиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство штя вычисления фундаментальных симметрическихНедостатком известного устройства для вычисления фундаментальных симметрических булевых функций является высокая конструктивная сложность, которая по числу входов логиче п ских элементов равна (п 3)-1.Изобретение направлено на решение технической задачи поъшжения конструктивной сложности устройства для вычисления фундаментальных симметрических булевых функций п переменных. Устройство для вычисления фундаментальных симметрических булевых функций содержит три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый и второй мажоритарные элементы сдом устройства, а входы с первого по третий соединены соответственно с выходами первого, второго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА Первые входы второго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединены соответственно с выходами первого и второго мажоритарных элементов. Информационные входы устройства с первого по п-й соединены соответственно с первого по п-й входами первого и второго мажоритарных элементов и первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, (п 1)й вход которого соединен с первым настроечным входом устройства. Второй и третий настроечные входы устройства соединены со вторыми входами соответственно второго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. В отличие от устройства - прототипа 3-й 6 4,р 1) настроечный вход устройства соединен с (п 2-7)-м и (п 26)-м входами первого и второго мажоритарных элементов.Основной технический результат изобретения заключается в понижении конструктивной сложности устройства для вычисления фут-шаментальных симметрических булевых функций п Переменных. Названный технический результат достигается путем изменения межсоединений элементов в схеме устройства.На чертеже (фиг.1 ) представлена схема устройства для вычисления фундаментальных симметрических булевых функций п переменных, а в таблице (фиг.2) приведена настройка устройства на реализацию фундаментальных симметрических булевых функций п переменных. Опиетим, что последняя строка таблицы настройки используется только при нечетном п.Устройство для вычисления фундаментальных симметрических булевых функций п переменных содержит элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1,2 и 3, мажоритарные элемен Ь.)тт ты 4,5, элемент И 6, тт информационных входов 7,72,7 р 1 (р настроечньтх входовУстройство для вычисления футшаментальных симметрических булевых функций работает следующим образом. На информационт-тьте входы 7,72,,7 поступают двоичные переменные хд,х 2 х (в произвольном порядке ) на насгроечньте входы 8828, - сигналы настройки цд,и 2,,ир.,.д значения которых принадлежат множеству 01. На выходе 9 реализуется фундаментальная сщшегрическая булева функция Р Р (х 1,х 2,,х), определяемая вектором настройки Н (и 1 ц 2,ир 1).Известно, что произвольная симметрическая булева функция п переменных Р Р (х 1 х 2 х), с рабочими числами а 1,а 2,а, (0 5 г 5 п) принимает значение 1 на тех и только тех наборах переменньтх х 1,х 2,,х которые содержат ровно ад 6 1,2 т ) единиц. Такая симметрическая булева функция обозначается через Р Р (хд,х 2,,х). Если т 1, то симметрическая булева функция Р Р называется фундаментальной (или элементарной), т.е.аа 1 симметрическая булева функция М (х 1,х 2 х) р п (хьхъщхп) а на вьшоде птходовоюэлемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА - тшнейная булева функция Д, 1. (хд х 2,х ) где13,,п 1 Р (хд,х 2 хп),если п четное, ьп (хЬхЪ-чхп) ьзрщп Рп (хдхдщхд) в противном случае. Первообразная устройства для вычисления фундаментальных симметрических булевых функций п переменньтх х 1,х 2,х имеет вид НХьХъ-Хпз ПтЪ 12 ч 11 рт) П-п (Хт. Х 2 Хп Ю 1111Поясним алгоритм настройки. Так, например, вектором настройки устройства на реализацию фундаментальной симметрической булевой функции Р Р (хдх 2,,х) являетсяСледовательно для реализации на выходе 9 устройства фундаментальной симметрической булевой функции Р Р (хх 2 х) необходимо на настроечные входы 8. и 81 подать сигналлогического нуля, а на настроечные входьт 83848 р - сигнал логической единицы . Достоинством устройства для вычисления фундаментальных симметрических булевых функций п перемет-п-тьтх является низкая конструктивная сложность, которая по числу входов лоптчестатх эле П п ментов равна Зтт 4 (сложность устройства-прототипа составляет (тт 3)-5- 1). При этомбыстродействие устройства совпадает с быстродействием устройства-прототипа и вычисляется как 31, где т - задержка на вентиль.Рабочие числа функции Р, реализуемой на выходе 9Заказ 0061 Тираж 20 экз. Государственный патентный комитет Республики Беларусь. 220072. г. Минск, проспект Ф. Скорины, 66.