close

Вход

Забыли?

вход по аккаунту

?

Патент BY5220

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 5220
(13) C1
(19)
7
(51) G 06F 7/00, 7/50
(12)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
УСТРОЙСТВО ДЛЯ ПОДСЧЕТА ЧИСЛА ЕДИНИЦ
(21) Номер заявки: a 19990616
(22) 1999.06.22
(46) 2003.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович;
Булаш Юрий Леонидович; Супрун Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
BY 5220 C1
(57)
Устройство для подсчета числа единиц, содержащее первый одноразрядный двоичный
сумматор, первый элемент И, два мажоритарных элемента с порогом два, два мажоритарных элемента с порогом четыре и пять элементов сложения по модулю два, первый вход
первого элемента сложения по модулю два соединен с выходом первого мажоритарного
элемента с порогом два, второй вход соединен с выходом первого мажоритарного элемента с порогом четыре, третий вход соединен с выходом первого элемента И, первый вход
второго элемента сложения по модулю два соединен с выходом второго мажоритарного
элемента с порогом два, второй вход соединен с выходом второго мажоритарного элемента с порогом четыре и первым входом третьего элемента сложения по модулю два, выход
Фиг. 1
BY 5220 C1
которого соединен с первым выходом устройства, отличающееся тем, что дополнительно
содержит шестой элемент сложения по модулю два, четыре элемента ЗАПРЕТ, второй,
третий, четвертый и пятый элементы И, второй, третий, четвертый, пятый и шестой одноразрядные двоичные сумматоры, при этом (3i + j-3)-й вход устройства (i = 1, 2,..., 6; j = 1,
2, 3) соединен c j-м входом i-го одноразрядного двоичного сумматора, выход суммы которого соединен с j-м входом первого элемента И, j-м входом первого мажоритарного элемента с порогом два, j-м входом первого мажоритарного элемента с порогом четыре и j-м
входом четвертого элемента сложения по модулю два, выход которого соединен со вторым выходом устройства, выход переноса i-го одноразрядного двоичного сумматора соединен с j-м входом второго элемента И, j-м входом второго мажоритарного элемента с
порогом два, j-м входом второго мажоритарного элемента с порогом четыре и j-м входом
пятого элемента сложения по модулю два, выход которого соединен с первым входом
третьего элемента И, первым входом четвертого элемента И, первым прямым входом первого элемента ЗАПРЕТ, входом запрета второго элемента ЗАПРЕТ, первым входом запрета третьего элемента ЗАПРЕТ, первым прямым входом четвертого элемента ЗАПРЕТ и
четвертым входом первого элемента сложения по модулю два, выход которого соединен с
третьим выходом устройства, четвертый выход которого соединен с выходом второго
элемента сложения по модулю два, третий вход которого соединен с выходом второго
элемента И и первым входом пятого элемента И, выход которого соединен со вторым
входом третьего элемента сложения по модулю два и первым входом шестого элемента
сложения по модулю два, выход которого соединен с пятым выходом устройства, а второй
вход соединен с выходом четвертого элемента И, второй вход которого соединен со вторым входом третьего элемента И, первым входом запрета четвертого элемента ЗАПРЕТ,
выходом первого элемента И и входом запрета первого элемента ЗАПРЕТ, второй прямой
вход которого соединен с выходом первого мажоритарного элемента с порогом два и вторым прямым входом четвертого элемента ЗАПРЕТ, третий прямой вход которого соединен с выходом второго мажоритарного элемента с порогом два и первым прямым входом
третьего элемента ЗАПРЕТ, второй вход запрета которого соединен с выходом второго
мажоритарного элемента с порогом четыре, третьим входом четвертого элемента И и вторым входом запрета четвертого элемента ЗАПРЕТ, выход которого соединен с третьим
входом третьего элемента сложения по модулю два, четвертый вход которого соединен с
выходом третьего элемента И, пятый вход соединен с выходом третьего элемента ЗАПРЕТ, второй прямой вход которого соединен со вторым входом пятого элемента И, выходом первого мажоритарного элемента с порогом четыре и прямым входом второго
элемента ЗАПРЕТ, выход которого соединен с пятым входом второго элемента сложения
по модулю два, шестой вход которого соединен с выходом первого элемента ЗАПРЕТ.
(56)
SU 1839248 A1, 1993.
RU 2129730 C1, 1999.
RU 2020744 C1, 1994.
RU 2030783 C1, 1995.
RU 2047216C1, 1995.
RU 2043651 C1, 1995.
EP 0602888 A1, 1994.
US 4218747 A, 1980.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения быстродействующих арифметических устройств ЭВМ и
спецпроцессоров.
2
BY 5220 C1
Известно устройство для подсчета числа единиц (многовходовый одноразрядный
сумматор), содержащее k элементов сложения по модулю два (k = [log2n], n - разрядность
входного слова) и р мажоритарных элементов (р = [n/2]), i-й из которых (i = 1, 2, ..., р)
имеет порог, равный 2i [1]. Устройство формирует позиционный двоичный код числа
единиц, содержащихся во входном двоичном слове.
Недостатком известного устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для подсчета числа единиц в тринадцатиразрядном входном слове, содержащее полусумматор, одноразрядный двоичный сумматор, пять элементов сложения по модулю два, элемент И, два мажоритарных элемента с
порогом два, два мажоритарных элемента с порогом четыре, мажоритарный элемент с порогом шесть и мажоритарный элемент с порогом восемь [2].
Недостатком известного устройства являются ограниченные функциональные возможности, т.к. устройство формирует позиционный двоичный код числа единиц во входном слове, разрядность которого не превышает тринадцати бит.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства для подсчета числа единиц за счет увеличения разрядности входного двоичного слова до восемнадцати бит.
Названный технический результат достигается путем введения в состав устройства
дополнительно элемента сложения по модулю два, элементов ЗАПРЕТ, элементов И, одноразрядных двоичных сумматоров, а также изменением связей между элементами устройства.
Устройство для подсчета числа единиц содержит первый одноразрядный двоичный
сумматор, первый элемент И, два мажоритарных элемента с порогом два, два мажоритарных элемента с порогом четыре и пять элементов сложения по модулю два. Первый вход
первого элемента сложения по модулю два соединен с выходом первого мажоритарного
элемента с порогом два, второй вход соединен с выходом первого мажоритарного элемента с порогом четыре, третий вход соединен с выходом первого элемента И. Первый вход
второго элемента сложения по модулю два соединен с выходом второго мажоритарного
элемента с порогом два, второй вход соединен с выходом второго мажоритарного элемента с порогом четыре и первым входом третьего элемента сложения по модулю два. Выход
третьего элемента сложения по модулю два соединен с первым выходом устройства.
В отличие от прототипа устройство дополнительно содержит шестой элемент сложения по модулю два, четыре элемента ЗАПРЕТ, второй, третий, четвертый и пятый элементы И, второй, третий, четвертый, пятый и шестой одноразрядные двоичные сумматоры.
В устройстве (3i + j-3)-й вход (i = 1,2,...,6; j = 1,2,3) соединен с j-м входом i-го одноразрядного двоичного сумматора, выход суммы которого соединен с j-м входом первого
элемента И, j-м входом первого мажоритарного элемента с порогом два, j-м входом первого мажоритарного элемента с порогом четыре и j-м входом четвертого элемента сложения
по модулю два, выход которого соединен со вторым выходом устройства. Выход переноса
i-го одноразрядного двоичного сумматора соединен с j-м входом второго элемента И, j-м
входом второго мажоритарного элемента с порогом два, j-м входом второго мажоритарного элемента с порогом четыре и j-м входом пятого элемента сложения по модулю два. Выход пятого элемента сложения по модулю два соединен с первым входом третьего
элемента И, первым входом четвертого элемента И, первым прямым входом первого элемента ЗАПРЕТ, входом запрета второго элемента ЗАПРЕТ, первым входом запрета
третьего элемента ЗАПРЕТ, первым прямым входом четвертого элемента ЗАПРЕТ и четвертым входом первого элемента сложения по модулю два. Выход первого элемента сложения по модулю два соединен с третьим выходом устройства, четвертый выход которого
соединен с выходом второго элемента сложения по модулю два, третий вход которого соединен с выходом второго элемента И и первым входом пятого элемента И. Выход пятого
3
BY 5220 C1
элемента И соединен со вторым входом третьего элемента сложения по модулю два и
первым входом шестого элемента сложения по модулю два, выход которого соединен с
пятым выходом устройства, а второй вход соединен с выходом четвертого элемента И.
Второй вход четвертого элемента И соединен со вторым входом третьего элемента И,
первым входом запрета четвертого элемента ЗАПРЕТ, выходом первого элемента И и
входом запрета первого элемента ЗАПРЕТ. Второй прямой вход первого элемента ЗАПРЕТ соединен с выходом первого мажоритарного элемента с порогом два и вторым прямым входом четвертого элемента ЗАПРЕТ, третий прямой вход которого соединен с
выходом второго мажоритарного элемента с порогом два и первым прямым входом
третьего элемента ЗАПРЕТ. Второй вход запрета третьего элемента ЗАПРЕТ соединен с
выходом второго мажоритарного элемента с порогом четыре, третьим входом четвертого
элемента И и вторым входом запрета четвертого элемента ЗАПРЕТ, выход которого соединен с третьим входом третьего элемента сложения по модулю два. Четвертый вход
третьего элемента сложения по модулю два соединен с выходом третьего элемента И, пятый вход соединен с выходом третьего элемента ЗАПРЕТ, второй прямой вход которого
соединен со вторым входом пятого элемента И, выходом первого мажоритарного элемента с порогом четыре и прямым входом второго элемента ЗАПРЕТ. Выход второго элемента ЗАПРЕТ соединен с пятым входом второго элемента сложения по модулю два, шестой
вход которого соединен с выходом первого элемента ЗАПРЕТ.
На фиг. 1 представлена схема устройства для подсчета числа единиц.
Устройство содержит шесть одноразрядных двоичных сумматоров 1-6, шесть элементов сложения по модулю два 7-12, два мажоритарных элемента с порогом два 13 и 14, два
мажоритарных элемента с порогом четыре 15 и 16, пять элементов И 17-21, четыре элемента ЗАПРЕТ 22-25, восемнадцать входов 26-43, пять выходов 44-48.
В общем случае устройство для подсчета числа единиц имеет n входов и
k = ]log2(n+1)[ выходов. На входы устройства подаются двоичные переменные Х = (х1, х2,
..., хn), на выходах устройства реализуются симметрические булевы функции (с.б.ф.)
ϕ0(X), ϕ1(X), ..., ϕk-l(X), значения которых составляют позиционный двоичный код числа N
единиц, содержащихся в векторе входных переменных X.
Пусть х1 + х2 + ... + хn = N, 0≤N≤n. Тогда, очевидно, что
N = ϕ 0 G1N , G 0n − N + 2ϕ1 G1N , G 0n − N + ... + 2 k −1 ϕ k −1 G1N , G 0n − N ,
(
)
(
)
(
)
где G sh = (h , h,..., h ) - некоторый кортеж длины s, содержащий только элементы h ∈
{0,1} и G 0h ≡ ∅ .
Устройство для подсчета числа единиц работает следующим образом.
На входы 26-43 подаются двоичные переменные х1, х2,..., x18 (в произвольном порядке), на выходах 44, 45,..., 48 соответственно реализуются с.б.ф. ϕ0(Х), ϕ1(X),..., ϕ4(Х), значения которых составляют позиционный двоичный код числа единиц, содержащихся во
входном двоичном слове X = (x1, x2,..., x18).
Работа устройства для подсчета числа единиц описывается приводимой ниже таблицей (фиг. 2).
Устройство построено в соответствии со следующими соотношениями:
ϕ0 = l;
ϕ1 = L ⊕ m 2 ⊕ m 4 ⊕ k;
ϕ 2 = Lm 4 ⊕ Lm 2 k ⊕ M 2 ⊕ M 4 ⊕ K;
ϕ3 = Lk ⊕ M 2 M 4 Lm 4 ⊕ M 2 M 4 Lm 2 k ⊕ Km 4 ⊕ M 4 ;
ϕ 4 = M 4 Lk ⊕ Km 4 ,
где
l = s1 ⊕ s2 ⊕ s3 ⊕ s4 ⊕ s5 ⊕ s6 ;
4
BY 5220 C1
L = p1 ⊕ p2 ⊕ p3 ⊕ p4 ⊕ p5 ⊕ p6;
k = s1s2s3s4s5s6;
K = p1p2p3p4p5p6;
m2 = m2(s1, s2, s3, s4, s5, s6), M2 = M2(p1, p2, p3, p4, p5, p6) - функции, реализуемые мажоритарными элементами с порогом два;
m4 = m4(sl, s2, s3, s4, s5, s6), M4 = М4(р1, р2, р3, р4, р5, р6) - функции, реализуемые мажоритарными элементами с порогом четыре;
si = х3i-2 ⊕ х3i-1 ⊕ x3i - функция, реализуемая на выходе суммы i-го одноразрядного
двоичного сумматора, i = 1,6 ;
pi = х3i-2х3i-1 ∨ х3i-2х3i ∨ х3i-1х3i - функция, реализуемая на выходе переноса i-го одноразрядного двоичного сумматора.
Отметим, что функция, реализуемая на выходе n-входового мажоритарного элемента с
порогом k(1≤k≤n), определяется следующим образом:
1, если z1 + z 2 + ... + z n ≥ k;
M kn = M kn (z1 , z 2 ,..., z n ) =
0, если z1 + z 2 + ... + z n < k; 1 ≤ k ≤ n ,
где z t ∈ {0,1}, t = 1, n.
Достоинствами устройства для подсчета числа единиц являются простая конструкция,
высокое быстродействие и широкая область применения.
Источники информации:
1. Патент РФ 2047216, 1995.
2. А.с. СССР 1839248, 1993.
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
188 Кб
Теги
by5220, патент
1/--страниц
Пожаловаться на содержимое документа