close

Вход

Забыли?

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

?

Патент BY5353

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 5353
(13) C1
(19)
7
(51) G 06F 7/00, 7/49, 7/50
(12)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
МНОГОВХОДОВЫЙ ОДНОРАЗРЯДНЫЙ СУММАТОР
(21) Номер заявки: a 19990818
(22) 1999.08.31
(46) 2003.09.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович;
Петроченко Андрей Сергеевич; Супрун
Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
BY 5353 C1
(57)
Многовходовый одноразрядный сумматор, содержащий p элементов сложения по модулю два, в котором p определено по формуле:
p = [log2n],
где n = 2r + 1 - разрядность входного двоичного слова;
r = 1, 2, 3,…;
выход i-го элемента сложения по модулю два (i = 1,2,…,p) соединен с i-м выходом сумматора,
j-й информационный вход (j = 1, 2,…, n) которого соединен с j-м входом первого элемента сложения по модулю два, отличающийся тем, что содержит (p + 1)-й элемент сложения по модулю два, элемент ИЛИ и r мажоритарных элементов, k-й из которых (k = 1, 2,…, r) имеет порог,
равный 2k + 1, при этом выход (р + 1)-го элемента сложения по модулю два соединен c(р + 1)-м
Фиг. 1
BY 5353 C1
выходом сумматора, j-й информационный вход которого соединен с j-м входом элемента ИЛИ
и j-м входом k-го мажоритарного элемента, управляющий вход сумматора соединен с (n + 1)-м
входом элемента ИЛИ, (n + 1)-м входом k-гo мажоритарного элемента и первым входом (i + 1)го элемента сложения по модулю два, второй вход которого соединен с выходом элемента
ИЛИ, (t + 2)-й вход (t = 1, 2,…, [r/i]) (i + 1)-го элемента сложения по модулю два соединен с выходом (t⋅2i-1)-го мажоритарного элемента.
(56)
RU 2047216 C1, 1995.
BY 2305 C1, 1998.
RU 2021630 C1, 1994.
SU 1068932 A, 1984.
SU 1827671 A1, 1993.
JP 02207323 A, 1990.
EP 0353041 A2, 1990.
JP 01304532 A, 1989.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения быстродействующих арифметическо-логических устройств
ЭВМ и специализированных процессоров.
Известен многовходовый одноразрядный сумматор, содержащий преобразователи
двоичных кодов в унитарные и блок суммирования унитарных кодов [1].
Недостатком устройства является низкое быстродействие, а также формирование на
выходах унитарного кода, затрудняющее применение сумматора при построении арифметических устройств.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому является многовходовый одноразрядный сумматор, содержащий p элементов сложения по модулю два (p = [log2n], n - разрядность входного двоичного слова) и r мажоритарных элементов (r = [n/2]), k-й из которых (k = 1, 2,…, r) имеет
порог, равный 2k [2]. На выходах сумматора формируется позиционный двоичный код
числа единиц, содержащихся во входном двоичном слове.
Недостатком известного многовходового одноразрядного сумматора является ограниченные функциональные возможности, поскольку он не обеспечивает формирование дополнительного кода результата.
Изобретение направлено на решение задачи расширения функциональных возможностей многовходового одноразрядного сумматора за счет формирования прямого и дополнительного кодов числа единиц, содержащихся во входном двоичном слове.
Названный технический результат достигается путем введения в состав сумматора дополнительно элемента ИЛИ, элемента сложения по модулю два, мажоритарных элементов
с нечетными порогами, а также изменением связей между элементами сумматора.
Многовходовый одноразрядный сумматор содержит p элементов сложения по модулю
два, в котором p определено по формуле: p = [log2n], где n = 2r + 1 - разрядность входного
двоичного слова, r = 1, 2, 3,… Выход i-го элемента сложения по модулю два (i = 1, 2,…, p)
соединен с i-м выходом сумматора. В сумматоре j-й информационный вход (j = 1, 2,…, n)
соединен с j-м входом первого элемента сложения по модулю два.
В отличие от прототипа сумматор содержит (p + 1)-й элемент сложения по модулю
два, элемент ИЛИ и r мажоритарных элементов, k-й из которых (k = 1, 2,…, r) имеет порог, равный 2k + l. Выход (p + 1)-го элемента сложения по модулю два соединен с (p + 1)м выходом сумматора, j-й информационный вход которого соединен с j-м входом элемента ИЛИ и j-м входом k-го мажоритарного элемента. Управляющий вход сумматора соеди2
BY 5353 C1
нен с (n + 1)-м входом элемента ИЛИ, (n + 1)-м входом k-го мажоритарного элемента и
первым входом (i + 1)-го элемента сложения по модулю два, второй вход которого соединен с выходом элемента ИЛИ. Выход (t·2i-1)-го мажоритарного элемента соединен с
(t + 2)-м входом (i + 1)-го элемента сложения по модулю два (t = 1, 2,…, [r/i]).
На фиг. 1 представлена схема многовходового одноразрядного сумматора при n = 11.
При n = 11 (n = 2r + 1, r = 5) сумматор содержит p + 1 = 4 (p = [log2/n] = 3) элементов
сложения по модулю два 1-4, элемент ИЛИ 5, r = 5 мажоритарных элементов 6-10, n = 11
информационных входов 11-21, управляющий вход 22, p + 1 = 4 выхода. При этом мажоритарные элементы 6, 7, 8, 9 и 10 имеют пороги соответственно три, пять, семь, девять и
одиннадцать.
Предлагаемый многовходовый одноразрядный сумматор работает в двух режимах режиме формирования прямого кода и режиме формирования дополнительного кода числа единиц, содержащихся во входном двоичном слове X = (x1, x2,…, xn). Выбранный режим определяется значением сигнала, подаваемого на управляющий вход сумматора.
В режиме формирования прямого кода числа единиц на управляющий вход сумматора
подается сигнал u = 1, а на информационные входы - двоичные переменные x1-xn. На выходах сумматора формируется (p + 1)-разрядный позиционный двоичный код (sp, sp-1,…,s0)
числа S(0 ≤ S ≤ n) единиц во входном слове Х:
S = x1 + x2 + … + xn= 2p·sp + 2p-1·sp-1… + 2s1 + s0.
В режиме формирования дополнительного кода числа единиц на управляющий вход
сумматора подается сигнал u = 0, а на информационные входы - двоичные переменные x1-xn.
На выходах сумматора формируется дополнительный (p + 1)-разрядный позиционный
двоичный код (cp, cp-1,…, c0) числа S единиц во входном слове X:
С = [S]доп. = 2p·cp + 2p-1·cp-1 …+ 2c1 + с0,
где
0, если S = 0;
C = [S]доп. = p +1
2
− S, если 1 ≤ S ≤ n.
Многовходовый одноразрядный сумматор при n = 11 (фиг. 1) работает следующим
образом. На управляющий вход 22 подается сигнал u, определяющий режим работы. На
информационные входы 11-21 подаются двоичные переменные x1-x11 (в произвольном порядке). На выходах 23-26 формируются соответственно сигналы s0-s3 (при u = 1) или c0-с3
(при u = 0).
Работа многовходового одноразрядного сумматора при n = 11 поясняется приводимой
ниже таблицей (фиг. 2).
Многовходовый одноразрядный сумматор при n = 11 построен в соответствии со следующими соотношениями:
r0 = x1 ⊕ x 2 ⊕ ! ⊕ x11;


3
5
7
9
11
r1 = D12 ( u, X ) ⊕ M12 ( u, X ) ⊕ M12 ( u, X ) ⊕ M12 ( u, X ) ⊕ M12 ( u, X ) ⊕ M12 ( u, X ) ⊕ u;
 (1)
5
9
r2 = D12 ( u, X ) ⊕ M12
( u, X ) ⊕ M12
( u , X ) ⊕ u;


9
r3 = D12 ( u, X ) ⊕ M12 ( u, X ) ⊕ u,

где
r0-r3 - функции, реализуемые соответственно на выходах 23-26 сумматора;
Х = (х1, x2,…, x11) - вектор входных двоичных переменных;
D12(u, X) = u ∨ x1 ∨ х2 ∨…∨ x11 - функция, реализуемая двенадцативходовым элементом ИЛИ 5;
k
M 12
(u, X) , k∈{3, 5, 7, 9, 11} - функция, реализуемая двенадцативходовым мажоритарным элементом с порогом k (элементы 6-10).
3
BY 5353 C1
Отметим, что функция, реализуемая m-входовым мажоритарным элементом с порогом
t (1 ≤ t ≤ m) определяется следующим образом:
1, если z1 + z 2 + ! + z m ≥ t;
t
Mm
( Z) =
0, если z1 + z 2 + ! + z m < t,
где Z = (z1, z2,…,zm); z1∈{0, 1}, l = 1, 2,…, m.
При u = 1 элемент ИЛИ 5 реализует функцию "константа 1", поскольку D12(l, X) ≡ 1;
двенадцативходовые мажоритарные элементы с нечетными порогами 6-10 реализуют
функции одиннадцативходовых мажоритарных элементов с четными порогами, меньшими на единицу:
k
k −1
M 12
(1, X) = M 11
(X), k∈(3, 5, 7, 9, 11}.
Следовательно, при вычислении прямого кода числа единиц (u = 1) соотношения (1),
описывающие работу сумматора, примут вид:
s 0 = x1 ⊕ x 2 ⊕ ! ⊕ x11;


2
4
6
8
s1 = M11
( X ) ⊕ M11
( X ) ⊕ M11
( X ) ⊕ M11
( X ) ⊕ M10
11 ( X );

4
8
s 2 = M11
( X ) ⊕ M11
( X );


8
s 3 = M11 ( X ).

При u = 0 элемент ИЛИ 5 реализует функцию D12(0, X) = D11(X) = x1 ∨ х2 ∨…∨ x11;
двенадцативходовые мажоритарные элементы с нечетными порогами 6-10 реализуют
функции одиннадцативходовых мажоритарных элементов с нечетными порогами (такими
же порогами):
k
k
M 12
(0, X) = M 11
(X), k∈(3, 5, 7, 9, 11}.
Следовательно, при вычислении дополнительного кода числа единиц (u = 0) соотношения (1), описывающие работу сумматора, примут вид:
с 0 = x1 ⊕ x 2 ⊕ ! ⊕ x11;


3
5
7
9
с1 = D11 ( X ) ⊕ M11
( X ) ⊕ M11
( X ) ⊕ M11
( X ) ⊕ M11
( X ) ⊕ M11
11 ( X );

5
9
с 2 = D11 ( X ) ⊕ M11
( X ) ⊕ M11
( X );


9
с 3 = D11 ( X ) ⊕ M11
( X ).

Без потери общности формула изобретения составлена для нечетных значений n.
Структура сумматора для четных значений n получается из устройства при числе входов,
равном n + 1, путем удаления избыточных конструктивных узлов.
Достоинствами многовходового одноразрядного сумматора являются широкие функциональные возможности и высокое быстродействие.
Источники информации:
1. А.с. СССР 1068932, 1984.
2. Патент РФ 2047216, 1995.
4
BY 5353 C1
Таблица работы многовходового одноразрядного сумматора при n = 11
Дополнительный код
Прямой код
Режим
Сигнал на управляющем входе
u/22
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
Вес входного слова
Сигналы на выходах сумматора
S = x1 + x2 + … +x11
Входы 11-21
s3(c3)/26 s2(c2)/25 s1(c1)/24 s0(c0)/23
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
4
0
1
0
0
5
0
1
0
1
6
0
1
1
0
7
0
1
1
1
8
1
0
0
0
9
1
0
0
1
10
1
0
1
0
11
1
0
1
1
0
0
0
0
0
1
1
1
1
1
2
1
1
1
0
3
1
1
0
1
4
1
1
0
0
5
1
0
1
1
6
1
0
1
0
7
1
0
0
1
8
1
0
0
0
9
0
1
1
1
10
0
1
1
0
11
0
1
0
1
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
131 Кб
Теги
патент, by5353
1/--страниц
Пожаловаться на содержимое документа