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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ФУНДАМЕНТАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ПЯТНАДЦАТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления фундаментальных симметрических булевых функций пятнадцати переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь, й, где 1, 2 18, вход которого соединен с -м входом устройства, а выход - с выходом устройства, причем девятнадцатый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь соединен с семнадцатым входом устройства, восемнадцатый вход которого соединен с двадцатым, двадцать первым и двадцать вторым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь. 14564 1 2011.06.30 Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации фундаментальных симметрических булевых функций пятнадцати переменных. Известно устройство для вычисления фундаментальных симметрических булевых функций пятнадцати переменных, содержащее мажоритарный элемент с порогом пятнадцать, мажоритарный элемент с порогом шестнадцать, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пятнадцать информационных и четыре настроечных входов, выход 1. Недостатками известного устройства являются высокая конструктивная сложность и низкое быстродействие, определяемое глубиной схемы. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления фундаментальных симметрических булевых функций пятнадцати переменных, содержащее мажоритарный элемент с порогом семь, мажоритарный элемент с порогом восемь, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемнадцать настроечных входов и выход 2. Недостатками устройства-прототипа для вычисления фундаментальных симметрических булевых функций являются 1) высокая конструктивная сложность (по числу входов логических элементов), равная 46 2) низкое быстродействие, определяемое глубиной схемы, которое составляет 2, где- задержка на один логический элемент. Изобретение направлено на решение следующих технических задач понижение конструктивной сложности (по числу входов логических элементов) и повышение быстродействия устройства для вычисления фундаментальных симметрических булевых функций пятнадцати переменных. Устройство для вычисления фундаментальных симметрических булевых функций пятнадцати переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь, -й,где 1, 2 18, вход которого соединен с -м входом устройства. Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь соединен с выходом устройства. Причем девятнадцатый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь соединен с семнадцатым входом устройства, восемнадцатый вход которого соединен с двадцатым, двадцать первым и двадцать вторым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь. Названный технический результат достигается путем использования нового логического элемента (элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь). На фигуре представлена схема устройства для вычисления фундаментальных симметрических булевых функций пятнадцати переменных. Устройство для вычисления фундаментальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь 1, восемнадцать входов 2, 319 и выход 20. Устройство для вычисления фундаментальных симметрических булевых функций работает следующим образом. На входы устройства 2, 3 19 поступают сигналы настройки 1, 2 18, значения которых принадлежат множеству 1 , 1 ,2 ,2 15 , 15 ,0,1 , а на выходе реализуется фундаментальная симметрическая булева функция пятнадцати переменных(1, 2 15), определяемая вектором настройки(1, 2 18). Известно, что произвольная симметрическая булева функцияпеременных(1,2 ) с рабочими числами 1, 2(01) принимает значение 1 на тех и только тех наборах значений переменных 1, 2 , которые содержат ровно(1, 2 ) единиц. Такая симметрическая булева функция 1 , 2 (1,2 ) задается посредством (1)-разрядного двоичного (локального) кода(0, 1 ), где 1 (0) тогда и только тогда, когда 1, 2 . Если 1, то симметрическая булева функцияназывается фундаментальной 14564 1 2011.06.30 1, если 12(1 ,2 )0 - в противном случае. На выходе -входового элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом а реализуется фундаментальная симметрическая булева функция( 1,2 )( 1,2 ). Первообразная функция устройства для вычисления фундаментальных симметрических булевых функций пятнадцати переменных имеет вид 7 15 ( 1 ,2 15 )22 (1 ,2 16 , 17 , 17 , 18 , 18 , 18 , 18 ),где 0, 1 15. Посредством таблицы представлена настройка устройства на реализацию шестнадцати фундаментальных симметрических булевых функций пятнадцати переменных. Устройство для вычисления фундаментальных симметрических булевых функций пятнадцати переменных Сигналы настройки Выход 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Пример 1 Допустим, что на выходе заявляемого устройства требуется реализовать фундаментальную симметрическую булеву функцию( 1,2 14 , 15 )1 214 151214 151 214 151 214 15 . Так как рабочим числом заданной симметрической булевой функции является 14,то согласно таблице настройки (таблица) для реализации на выходе устройства функции(1 ,2 15 )15 (1 ,2 15 ) необходимо на его входы подать следующие значения настройки 11,22 1515 , 160, 171 и 181. В таком случае первообразная функция устройства принимает вид 7 1 14 15 ( 1 ,2 15 )22 ( 1 ,2 15 ,0, 1, 1, 1, 1, 1, 1)15 ( 1 ,2 15 )15 ( 1 ,2 15 ). Следует отметить, что заявляемое устройство для вычисления фундаментальных симметрических булевых функций пятнадцати переменных можно обобщить на случай вычисления фундаментальных симметрических булевых функцийпеременных при условии, что 2 - 1, где 2. В общем случае устройство будет содержать единственный элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом 2-1 - 1, а число его настроечных входов будет равно- 1. Сложность такого устройства (по числу входов логического элемента ИСКЛЮЧАЮЩЕЕ ИЛИ) вычисляется по формуле 11 312 12 11. 12 2 1 Пример 2 Если 3, то 2, и устройство для вычисления фундаментальных симметрических булевых функций трех переменных будет содержать элемент ИСКЛЮЧАЮЩЕЕ ИЛИ,порог которого равен единице 3. При этом устройство будет иметь- 14 настроечных входов, а его сложность 314. будет составлять 2 Пример 3. Пусть 7, тогда 3, и устройство для вычисления фундаментальных симметрических булевых функций семи переменных будет содержать элемент ИСКЛЮЧАЮЩЕЕ 31 ИЛИ с порогом три, число входов которого равно 10. Такое устройство для 2 вычисления фундаментальных симметрических булевых функций семи переменных имеет меньшую сложность по сравнению с существующим аналогом 4. Сложность устройства равна 10, в то время как сложность аналога составляет 14. Основными достоинствами заявляемого устройства для вычисления фундаментальных симметрических булевых функций пятнадцати переменных являются 1) низкая конструктивная сложность (по числу входов логических элементов), равная 22 2) высокое быстродействие, которое составляет , где- задержка на логический элемент. Источники информации 1. Патент РБ 2990, МПК 06 7/00, 1999. 2. Патент РБ 5174, МПК 06 7/00, 2003 (прототип). 3. Патент РБ 5938, МПК 06 7/00, 2004. 4. Патент РБ 8421, МПК 06 7/00, 2006. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.