close

Вход

Забыли?

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

?

Патент BY7588

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 7588
(13) C1
(19)
(46) 2005.12.30
(12)
7
(51) G 06F 7/49, 7/50
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
МНОГОВХОДОВЫЙ ОДНОРАЗРЯДНЫЙ СУММАТОР ПО
МОДУЛЮ ПЯТЬ
(21) Номер заявки: a 20030179
(22) 2003.02.28
(43) 2003.09.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Петроченко Андрей Сергеевич; Супрун
Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) RU 2047216 С1, 1995.
RU 2018931 C1, 1994.
SU 1783514 A1, 1992.
SU 1730620 A1, 1992.
WO 02/071203 A2.
EP 1052568 A1, 2000.
BY 7588 C1 2005.12.30
(57)
Многовходовый одноразрядный сумматор по модулю пять, содержащий четыре элемента сложения по модулю два и 5k мажоритарных элементов (k = 1, 2, 3, …), i-й (i = 1,
2, …, 5k) из которых имеет порог, равный 2i, а его j-й (j = 1, 2, …, n; n = 10k + 1 - разрядность входного слова) вход соединен с j-м входом первого элемента сложения по модулю
Фиг. 1
BY 7588 C1 2005.12.30
два и j-м входом сумматора, первый, второй и третий выходы которого соединены соответственно с выходами второго, третьего и четвертого элементов сложения по модулю
два, при этом выход мажоритарного элемента с порогом 10l-6 (l = 1, 2,…, k) соединен с l-м
входом второго элемента сложения по модулю два и l-м входом третьего элемента сложения по модулю два, выход мажоритарного элемента с порогом 10l-2 соединен с (k + l)-м
входом третьего элемента сложения по модулю два, выход мажоритарного элемента с порогом 10l-8 соединен с (2k + l)-м входом третьего элемента сложения по модулю два, выход мажоритарного элемента с порогом 10l соединен с (3k + l)-м входом третьего элемента сложения по модулю два, отличающийся тем, что содержит k групп элементов И
по четыре элемента в каждой, причем первый вход первого элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 10l, а выход соединен с (k + l)-м
входом второго элемента сложения по модулю два и (4k + l)-м входом третьего элемента
сложения по модулю два, первый вход второго элемента И l-й группы соединен с выходом
мажоритарного элемента с порогом 10l-2, а выход соединен с (2k + l)-м входом второго
элемента сложения по модулю два, первый вход третьего элемента И l-й группы соединен
с выходом мажоритарного элемента с порогом 10l-4, (3k + l)-м входом второго элемента
сложения по модулю два и l-м входом четвертого элемента сложения по модулю два, а
выход соединен с (4k + l)-м входом второго элемента сложения по модулю два, (5k + l)-м
входом третьего элемента сложения по модулю два и (k + l)-м входом четвертого элемента
сложения по модулю два, первый вход четвертого элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 10l-6, а выход соединен с (5k + l)-м входом
второго элемента сложения по модулю два и (2k + l)-м входом четвертого элемента сложения по модулю два, (3k + l)-й вход которого соединен с выходом мажоритарного элемента с порогом 10l, (4k + l)-й вход которого соединен с выходом первого элемента сложения по модулю два и вторым входом s-го (s = 1, 2, …,4) элемента И l-й группы.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики.
Известен сумматор по модулю пять, содержащий четыре полусумматора, пять элементов ИЛИ-НЕ, элемент ЗАПРЕТ, элемент ИЛИ и элемент И [1]. Сумматор выполняет сложение по модулю пять двух приведенных трехразрядных операндов.
Недостатком устройства является невозможность вычисления суммы по модулю пять
числа единиц, содержащихся во входном n-разрядном двоичном слове.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является многовходовый одноразрядный сумматор, содержащий k элементов сложения по модулю два (k = [log2n], n - разрядность входного слова) и р
мажоритарных элементов (р = [n/2]), i-й из которых (i = 1, 2, ..., р) имеет порог, равный 2i
[2]. Сумматор формирует позиционный двоичный код числа единиц, содержащихся во
входном двоичном слове.
Недостатком известного многовходового одноразрядного сумматора является невозможность вычисления суммы по модулю пять числа единиц, содержащихся во входном
двоичном слове.
Изобретение направлено на решение задачи расширения функциональных возможностей многовходового одноразрядного сумматора за счет вычисления суммы по модулю
пять числа единиц, содержащихся во входном двоичном слове.
Названный технический результат достигается путем введения в состав сумматора
элементов И, а также изменением связей между элементами сумматора.
Многовходовый одноразрядный сумматор по модулю пять содержит четыре элемента
сложения по модулю два и 5k мажоритарных элементов (k = 1, 2, 3, ...), i-й (i = 1, 2, ..., 5k)
из которых имеет порог, равный 2i, а его j-й (j = 1, 2, ..., n; n = 10k + 1 - разрядность входно2
BY 7588 C1 2005.12.30
го слова) вход соединен c j-м входом первого элемента сложения по модулю два и j-м входом сумматора. Первый, второй и третий выходы сумматора соединены соответственно с
выходами второго, третьего и четвертого элементов сложения по модулю два. Выход мажоритарного элемента с порогом 10l-6 (l = 1, 2, ..., k) соединен с l-м входом второго элемента
сложения по модулю два и l-м входом третьего элемента сложения по модулю два. Выход
мажоритарного элемента с порогом 10l-2 соединен с (k + l)-м входом третьего элемента
сложения по модулю два. Выход мажоритарного элемента с порогом 10l-8 соединен с
(2k + l)-м входом третьего элемента сложения по модулю два. Выход мажоритарного элемента с порогом 10l соединен с (3k + l)-м входом третьего элемента сложения по модулю два.
В отличие от прототипа, сумматор содержит k групп элементов И по четыре элемента
в каждой. Первый вход первого элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 10l, а выход соединен с (k + l)-м входом второго элемента сложения
по модулю два и (4k + l)-м входом третьего элемента сложения по модулю два. Первый
вход второго элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 10l-2, а выход соединен с (2k + l)-м входом второго элемента сложения по модулю
два. Первый вход третьего элемента И l-й группы соединен с выходом мажоритарного
элемента с порогом 10l-4, (3k + l)-м входом второго элемента сложения по модулю два и lм входом четвертого элемента сложения по модулю два, а выход соединен с (4k + l)-м
входом второго элемента сложения по модулю два, (5k + l)-м входом третьего элемента
сложения по модулю два и (k + l)-м входом четвертого элемента сложения по модулю два.
Первый вход четвертого элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 10l-6, а выход соединен с (5k + l)-м входом второго элемента сложения
по модулю два и (2k + l)-м входом четвертого элемента сложения по модулю два, (3k + l)й вход которого соединен с выходом мажоритарного элемента с порогом 10l, (4k + l)-й
вход которого соединен с выходом первого элемента сложения по модулю два и вторым
входом s-го (s = 1, 2, ..., 4) элемента И l-й группы.
На чертеже (фиг. 1) представлена схема многовходового одноразрядного сумматора
по модулю пять при n = 11 (k = 1).
Сумматор содержит 5k = 5 мажоритарных элементов (мажоритарный элемент с порогом десять 1, мажоритарный элемент с порогом восемь 2, мажоритарный элемент с порогом шесть 3, мажоритарный элемент с порогом четыре 4, мажоритарный элемент с
порогом два 5), четыре элемента сложения по модулю два 6-9, k = 1 группу из четырех
элементов И 10-13, n = 10k + 1 = 11 входов 14-24, три выхода 25, 26 и 27.
Многовходовый одноразрядный сумматор по модулю пять (при n = 11) работает следующим образом.
На входы 14-24 подаются двоичные переменные х1-х11 (в произвольном порядке), на
выходах 25, 26 и 27 реализуются соответственно булевы функции r1, r2 и r3 результата,
значения которых составляют позиционный двоичный код суммы по модулю пять
R = 4r1 + 2r2 + r3 числа единиц V(X), содержащихся во входном слове X = (х1, х2, ..., х11):
R = V(X) mod 5 = (x1 + x2 + ... + x11) mod 5 = 4r1 + 2r2 + r3.
Схема сумматора при n = 11 (фиг. 1) построена в соответствии со следующими соотношениями:
r1 = М4 ⊕ M4L ⊕ M6 ⊕ M6L ⊕ M8L ⊕ M10L;
r2 = M2 ⊕ M4 ⊕ M6L ⊕ M8 ⊕ M10 ⊕ M10L;
r3 = L ⊕ M4L ⊕ M6 ⊕ M6L ⊕ М10,
где L = x1 ⊕ х2 ⊕ ... ⊕ хn - функция, реализуемая n-входовым элементом сложения по модулю два;
Mh - функция, реализуемая n-входовым мажоритарным элементом с порогом h, которая определяется следующим образом (h ∈ {2, 4, 6, 8, ...}):
1, если x 1 + x 2 + ... + x n ≥ h;
M h = M h ( x 1 , x 2 , ..., x n ) =
0, если x 1 + x 2 + ... + x n < h.
3
BY 7588 C1 2005.12.30
Работа многовходового одноразрядного сумматора по модулю пять при n = 11 поясняется приводимой ниже таблицей (фиг. 2).
В общем случае (для произвольной разрядности n входного слова) многовходовый одноразрядный сумматор по модулю пять формирует трехразрядный позиционный двоичный код суммы по модулю пять R = 4r1 + 2r2 + r3 числа единиц V(X), содержащихся в
n-разрядном входном слове X = (x1, x2, ..., xn):
R = V(X) mod5 = (x1 + x2 + ... + xn) mod5 = 4r1 + 2r2 + r3.
Без потери общности формула изобретения составлена для значений n = 10k + 1 (k = 1,
2, 3, ...).
При этом схема многовходового одноразрядного сумматора по модулю пять может
быть построена согласно следующим соотношениям:
k
r1 = + (M10l-6
M10l-6L
M10l-4
M10l-4L
M10l-2L);
l=1
k
r2 = + (M10l-8
M10l-6
M10l-4L
M10l
M10l-2
M10lL);
l=1
k
r3 = L
+ (M10l-6L
M10l-4
M10l-4L
M10l) .
l=1
Структура сумматора для других значений n получается из устройства при числе входов, равном n* = 10](n-1)/10[+1, путем удаления избыточных логических элементов и межсоединений в схеме.
Достоинствами многовходового одноразрядного сумматора по модулю пять являются
простая конструкция, высокое быстродействие и широкая область применения.
Источники информации:
1. А.с. СССР 1783514, МПК G 06F 7/49, 1992.
2. Патент РФ 2047216, МПК G 06F 7/50, 1995 (прототип).
Таблица работы многовходового одноразрядного сумматора по модулю пять
V(X) = x1 + x2 + .... + x11
Входы 14-24
0
1
2
3
4
5
6
7
8
9
10
11
R = V(X) mod 5 = 4r1 + 2r2 + r3
r1/25
r2/26
r3/27
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
0
0
0
0
0
1
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
Документ
Категория
Без категории
Просмотров
0
Размер файла
233 Кб
Теги
by7588, патент
1/--страниц
Пожаловаться на содержимое документа