Устройство для подсчета числа единиц

(12) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ПОДСЧЕТА ЧИСЛА ЕДИНИЦ(71) Заявитель Белорусский государственный университет(72) Авторы Авгуль Леонид Болеславович Булаш Юрий Леонидович Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для подсчета числа единиц, содержащее первый одноразрядный двоичный сумматор, первый элемент И, два мажоритарных элемента с порогом два, два мажоритарных элемента с порогом четыре и пять элементов сложения по модулю два, первый вход первого элемента сложения по модулю два соединен с выходом первого мажоритарного элемента с порогом два, второй вход соединен с выходом первого мажоритарного элемента с порогом четыре, третий вход соединен с выходом первого элемента И, первый вход второго элемента сложения по модулю два соединен с выходом второго мажоритарного элемента с порогом два, второй вход соединен с выходом второго мажоритарного элемента с порогом четыре и первым входом третьего элемента сложения по модулю два, выход 5220 1 которого соединен с первым выходом устройства, отличающееся тем, что дополнительно содержит шестой элемент сложения по модулю два, четыре элемента ЗАПРЕТ, второй,третий, четвертый и пятый элементы И, второй, третий, четвертый, пятый и шестой одноразрядные двоичные сумматоры, при этом (3-3)-й вход устройства (1, 2 61,2, 3) соединен-м входом -го одноразрядного двоичного сумматора, выход суммы которого соединен с -м входом первого элемента И, -м входом первого мажоритарного элемента с порогом два, -м входом первого мажоритарного элемента с порогом четыре и -м входом четвертого элемента сложения по модулю два, выход которого соединен со вторым выходом устройства, выход переноса -го одноразрядного двоичного сумматора соединен с -м входом второго элемента И, -м входом второго мажоритарного элемента с порогом два, -м входом второго мажоритарного элемента с порогом четыре и -м входом пятого элемента сложения по модулю два, выход которого соединен с первым входом третьего элемента И, первым входом четвертого элемента И, первым прямым входом первого элемента ЗАПРЕТ, входом запрета второго элемента ЗАПРЕТ, первым входом запрета третьего элемента ЗАПРЕТ, первым прямым входом четвертого элемента ЗАПРЕТ и четвертым входом первого элемента сложения по модулю два, выход которого соединен с третьим выходом устройства, четвертый выход которого соединен с выходом второго элемента сложения по модулю два, третий вход которого соединен с выходом второго элемента И и первым входом пятого элемента И, выход которого соединен со вторым входом третьего элемента сложения по модулю два и первым входом шестого элемента сложения по модулю два, выход которого соединен с пятым выходом устройства, а второй вход соединен с выходом четвертого элемента И, второй вход которого соединен со вторым входом третьего элемента И, первым входом запрета четвертого элемента ЗАПРЕТ,выходом первого элемента И и входом запрета первого элемента ЗАПРЕТ, второй прямой вход которого соединен с выходом первого мажоритарного элемента с порогом два и вторым прямым входом четвертого элемента ЗАПРЕТ, третий прямой вход которого соединен с выходом второго мажоритарного элемента с порогом два и первым прямым входом третьего элемента ЗАПРЕТ, второй вход запрета которого соединен с выходом второго мажоритарного элемента с порогом четыре, третьим входом четвертого элемента И и вторым входом запрета четвертого элемента ЗАПРЕТ, выход которого соединен с третьим входом третьего элемента сложения по модулю два, четвертый вход которого соединен с выходом третьего элемента И, пятый вход соединен с выходом третьего элемента ЗАПРЕТ, второй прямой вход которого соединен со вторым входом пятого элемента И, выходом первого мажоритарного элемента с порогом четыре и прямым входом второго элемента ЗАПРЕТ, выход которого соединен с пятым входом второго элемента сложения по модулю два, шестой вход которого соединен с выходом первого элемента ЗАПРЕТ.(56)1839248 1, 1993.2129730 1, 1999.2020744 1, 1994.2030783 1, 1995.20472161, 1995.2043651 1, 1995.0602888 1, 1994.4218747 , 1980. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения быстродействующих арифметических устройств ЭВМ и спецпроцессоров. 2 5220 1 Известно устройство для подсчета числа единиц (многовходовый одноразрядный сумматор), содержащееэлементов сложения по модулю два (2,- разрядность входного слова) и р мажоритарных элементов (р/2), -й из которых (1, 2, , р) имеет порог, равный 2 1. Устройство формирует позиционный двоичный код числа единиц, содержащихся во входном двоичном слове. Недостатком известного устройства является высокая конструктивная сложность. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для подсчета числа единиц в тринадцатиразрядном входном слове, содержащее полусумматор, одноразрядный двоичный сумматор, пять элементов сложения по модулю два, элемент И, два мажоритарных элемента с порогом два, два мажоритарных элемента с порогом четыре, мажоритарный элемент с порогом шесть и мажоритарный элемент с порогом восемь 2. Недостатком известного устройства являются ограниченные функциональные возможности, т.к. устройство формирует позиционный двоичный код числа единиц во входном слове, разрядность которого не превышает тринадцати бит. Изобретение направлено на решение задачи расширения функциональных возможностей устройства для подсчета числа единиц за счет увеличения разрядности входного двоичного слова до восемнадцати бит. Названный технический результат достигается путем введения в состав устройства дополнительно элемента сложения по модулю два, элементов ЗАПРЕТ, элементов И, одноразрядных двоичных сумматоров, а также изменением связей между элементами устройства. Устройство для подсчета числа единиц содержит первый одноразрядный двоичный сумматор, первый элемент И, два мажоритарных элемента с порогом два, два мажоритарных элемента с порогом четыре и пять элементов сложения по модулю два. Первый вход первого элемента сложения по модулю два соединен с выходом первого мажоритарного элемента с порогом два, второй вход соединен с выходом первого мажоритарного элемента с порогом четыре, третий вход соединен с выходом первого элемента И. Первый вход второго элемента сложения по модулю два соединен с выходом второго мажоритарного элемента с порогом два, второй вход соединен с выходом второго мажоритарного элемента с порогом четыре и первым входом третьего элемента сложения по модулю два. Выход третьего элемента сложения по модулю два соединен с первым выходом устройства. В отличие от прототипа устройство дополнительно содержит шестой элемент сложения по модулю два, четыре элемента ЗАПРЕТ, второй, третий, четвертый и пятый элементы И, второй, третий, четвертый, пятый и шестой одноразрядные двоичные сумматоры. В устройстве (3-3)-й вход (1,261,2,3) соединен с -м входом -го одноразрядного двоичного сумматора, выход суммы которого соединен с -м входом первого элемента И, -м входом первого мажоритарного элемента с порогом два, -м входом первого мажоритарного элемента с порогом четыре и -м входом четвертого элемента сложения по модулю два, выход которого соединен со вторым выходом устройства. Выход переноса-го одноразрядного двоичного сумматора соединен с -м входом второго элемента И, -м входом второго мажоритарного элемента с порогом два, -м входом второго мажоритарного элемента с порогом четыре и -м входом пятого элемента сложения по модулю два. Выход пятого элемента сложения по модулю два соединен с первым входом третьего элемента И, первым входом четвертого элемента И, первым прямым входом первого элемента ЗАПРЕТ, входом запрета второго элемента ЗАПРЕТ, первым входом запрета третьего элемента ЗАПРЕТ, первым прямым входом четвертого элемента ЗАПРЕТ и четвертым входом первого элемента сложения по модулю два. Выход первого элемента сложения по модулю два соединен с третьим выходом устройства, четвертый выход которого соединен с выходом второго элемента сложения по модулю два, третий вход которого соединен с выходом второго элемента И и первым входом пятого элемента И. Выход пятого 3 5220 1 элемента И соединен со вторым входом третьего элемента сложения по модулю два и первым входом шестого элемента сложения по модулю два, выход которого соединен с пятым выходом устройства, а второй вход соединен с выходом четвертого элемента И. Второй вход четвертого элемента И соединен со вторым входом третьего элемента И,первым входом запрета четвертого элемента ЗАПРЕТ, выходом первого элемента И и входом запрета первого элемента ЗАПРЕТ. Второй прямой вход первого элемента ЗАПРЕТ соединен с выходом первого мажоритарного элемента с порогом два и вторым прямым входом четвертого элемента ЗАПРЕТ, третий прямой вход которого соединен с выходом второго мажоритарного элемента с порогом два и первым прямым входом третьего элемента ЗАПРЕТ. Второй вход запрета третьего элемента ЗАПРЕТ соединен с выходом второго мажоритарного элемента с порогом четыре, третьим входом четвертого элемента И и вторым входом запрета четвертого элемента ЗАПРЕТ, выход которого соединен с третьим входом третьего элемента сложения по модулю два. Четвертый вход третьего элемента сложения по модулю два соединен с выходом третьего элемента И, пятый вход соединен с выходом третьего элемента ЗАПРЕТ, второй прямой вход которого соединен со вторым входом пятого элемента И, выходом первого мажоритарного элемента с порогом четыре и прямым входом второго элемента ЗАПРЕТ. Выход второго элемента ЗАПРЕТ соединен с пятым входом второго элемента сложения по модулю два, шестой вход которого соединен с выходом первого элемента ЗАПРЕТ. На фиг. 1 представлена схема устройства для подсчета числа единиц. Устройство содержит шесть одноразрядных двоичных сумматоров 1-6, шесть элементов сложения по модулю два 7-12, два мажоритарных элемента с порогом два 13 и 14, два мажоритарных элемента с порогом четыре 15 и 16, пять элементов И 17-21, четыре элемента ЗАПРЕТ 22-25, восемнадцать входов 26-43, пять выходов 44-48. В общем случае устройство для подсчета числа единиц имеетвходов и 2(1) выходов. На входы устройства подаются двоичные переменные Х(х 1, х 2 х), на выходах устройства реализуются симметрические булевы функции (с.б.ф.) 0, 1, , -, значения которых составляют позиционный двоичный код числаединиц, содержащихся в векторе входных переменных . Пусть х 1 х 2 х, 0. Тогда, очевидно, что 0 1 ,021 1 ,0211 1 ,0,где( , ) - некоторый кортеж длины , содержащий только элементы 0,1 и 0. Устройство для подсчета числа единиц работает следующим образом. На входы 26-43 подаются двоичные переменные х 1, х 2 18 (в произвольном порядке), на выходах 44, 45 48 соответственно реализуются с.б.ф. 0(Х), 1 4(Х), значения которых составляют позиционный двоичный код числа единиц, содержащихся во входном двоичном слове(1, 2 18). Работа устройства для подсчета числа единиц описывается приводимой ниже таблицей (фиг. 2). Устройство построено в соответствии со следующими соотношениями 0 5220 1123456123456123456 22(1, 2, 3, 4, 5, 6), 22(1, 2, 3, 4, 5, 6) - функции, реализуемые мажоритарными элементами с порогом два 44(, 2, 3, 4, 5, 6), 4 М 4(р 1, р 2, р 3, р 4, р 5, р 6) - функции, реализуемые мажоритарными элементами с порогом четырех 3-2 х 3-13 - функция, реализуемая на выходе суммы -го одноразрядного двоичного сумматора,1,6 х 3-2 х 3-1 х 3-2 х 3 х 3-1 х 3 - функция, реализуемая на выходе переноса -го одноразрядного двоичного сумматора. Отметим, что функция, реализуемая на выходе -входового мажоритарного элемента с порогом (1), определяется следующим образом 1, если 12(1 ,2 ) 0, если 121, где 0,1,1, . Достоинствами устройства для подсчета числа единиц являются простая конструкция,высокое быстродействие и широкая область применения. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5