close

Вход

Забыли?

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

?

Патент BY7590

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 7590
(13) C1
(19)
(46) 2005.12.30
(12)
7
(51) G 06F 7/49, 7/50
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
МНОГОВХОДОВЫЙ ОДНОРАЗРЯДНЫЙ СУММАТОР ПО
МОДУЛЮ СЕМЬ
(21) Номер заявки: a 20030181
(22) 2003.02.28
(43) 2003.12.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Петроченко Андрей Сергеевич; Супрун
Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) RU 2047216 С1, 1995.
RU 2028660 C1, 1995.
SU 1730620 A1, 1992.
WO 02/071203 A2.
EP 1052568 A1, 2000.
BY 7590 C1 2005.12.30
(57)
Многовходовый одноразрядный сумматор по модулю семь, содержащий четыре элемента сложения по модулю два и 7k мажоритарных элементов (k = 1, 2, 3, …), i-й (i = 1,
2, …, 7k) из которых имеет порог, равный 2i, а его j-й (j = 1, 2, …, n; n = 14k + 1 - разрядность входного слова) вход соединен с j-м входом первого элемента сложения по модулю
Фиг. 1
BY 7590 C1 2005.12.30
два и j-м входом сумматора, первый, второй и третий выходы которого соединены соответственно с выходами второго, третьего и четвертого элементов сложения по модулю
два, при этом выход мажоритарного элемента с порогом 14l - 10 (l = 1, 2, …, k) соединен с
l-м входом второго элемента сложения по модулю два и l-м входом третьего элемента
сложения по модулю два, выход мажоритарного элемента с порогом 14l - 6 соединен с
(k + l)-м входом второго элемента сложения по модулю два, (k + l)-м входом третьего элемента сложения по модулю два и l-м входом четвертого элемента сложения по модулю
два, выход мажоритарного элемента с порогом 14l - 2 соединен с (2k + l)-м входом второго элемента сложения по модулю два и (2k + l)-м входом третьего элемента сложения по
модулю два, выход мажоритарного элемента с порогом 14l - 12 соединен с (3k + l)-м входом третьего элемента сложения по модулю два, выход мажоритарного элемента с порогом 14l - 8 соединен с (4k + l)-м входом третьего элемента сложения по модулю два, выход мажоритарного элемента с порогом 14l - 4 соединен с (5k + l)-м входом третьего
элемента сложения по модулю два, отличающийся тем, что содержит k групп элементов
И по пять элементов в каждой, причем первый вход первого элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 14l, (3k + l)-м входом второго элемента
сложения по модулю два и (k + l)-м входом четвертого элемента сложения по модулю два,
а выход соединен с (6k + l)-м входом третьего элемента сложения по модулю два, первый
вход второго элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 14l - 2, а выход соединен с (4k + l)-м входом второго элемента сложения по модулю
два, первый вход третьего элемента И l-й группы соединен с выходом мажоритарного
элемента с порогом 14l - 4, а выход соединен с (5k + l)-м входом второго элемента сложения по модулю два, первый вход четвертого элемента И l-й группы соединен с выходом
мажоритарного элемента с порогом 14l - 6, а выход соединен с (6k + l)-м входом второго
элемента сложения по модулю два и (2k + l)-м входом четвертого элемента сложения по
модулю два, первый вход пятого элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 14l – 8, а выход соединен с (7k + l)-м входом второго элемента
сложения по модулю два, (7k + l)-м входом третьего элемента сложения по модулю два и
(3k + l)-м входом четвертого элемента сложения по модулю два, (4k + l)-й вход которого
соединен с выходом первого элемента сложения по модулю два и вторым входом s-го
(s = 1, 2,…,4) элемента И l-й группы.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики.
Известно устройство для сложения по модулю семь, содержащее шесть элементов
сложения по модулю два, три мажоритарных элемента с порогом два и двадцать четыре
элемента И [1]. Устройство выполняет сложение по модулю семь трех полных трехразрядных операндов.
Недостатком устройства является невозможность вычисления суммы по модулю семь
числа единиц, содержащихся во входном n-разрядном двоичном слове.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является многовходовый одноразрядный сумматор, содержащий k элементов сложения по модулю два (k = [log2n], n - разрядность входного слова) и р
мажоритарных элементов (р = [n/2]), i-й из которых (i = 1, 2, ..., p) имеет порог, равный 2i
[2]. Сумматор формирует позиционный двоичный код числа единиц, содержащихся во
входном двоичном слове.
Недостатком известного многовходового одноразрядного сумматора является невозможность вычисления суммы по модулю семь числа единиц, содержащихся во входном
двоичном слове.
2
BY 7590 C1 2005.12.30
Изобретение направлено на решение задачи расширения функциональных возможностей многовходового одноразрядного сумматора за счет вычисления суммы по модулю
семь числа единиц, содержащихся во входном двоичном слове.
Названный технический результат достигается путем введения в состав сумматора
элементов И, а также изменением связей между элементами сумматора.
Многовходовый одноразрядный сумматор по модулю семь содержит четыре элемента
сложения по модулю два и 7k мажоритарных элементов (k = 1, 2, 3, ...), i-й (i = 1, 2, ..., 7k)
из которых имеет порог, равный 2i, а его j-й (j = 1, 2, ..., n; n = 14k + 1 - разрядность входного слова) вход соединен c j-м входом первого элемента сложения по модулю два и j-м
входом сумматора. Первый, второй и третий выходы сумматора соединены соответственно с выходами второго, третьего и четвертого элементов сложения по модулю два. Выход
мажоритарного элемента с порогом 14l-10 (l = 1, 2, ..., k) соединен с l-м входом второго
элемента сложения по модулю два и l-м входом третьего элемента сложения по модулю
два. Выход мажоритарного элемента с порогом 14l-6 соединен с (k + l)-м входом второго
элемента сложения по модулю два, (k + l)-м входом третьего элемента сложения по модулю два и 1-м входом четвертого элемента сложения по модулю два. Выход мажоритарного элемента с порогом 14l-2 соединен с (2k + l)-м входом второго элемента сложения по
модулю два и (2k + l)-м входом третьего элемента сложения по модулю два. Выход мажоритарного элемента с порогом 14l-12 соединен с (3k + l)-м входом третьего элемента сложения по модулю два. Выход мажоритарного элемента с порогом 14l-8 соединен с
(4k + l)-м входом третьего элемента сложения по модулю два. Выход мажоритарного элемента с порогом 14l-4 соединен с (5k + l)-м входом третьего элемента сложения по модулю два.
В отличие от прототипа, сумматор содержит k групп элементов И по пять элементов в
каждой. Первый вход первого элемента И l-й группы соединен с выходом мажоритарного
элемента с порогом 14l, (3k + l)-м входом второго элемента сложения по модулю два и
(k + l)-м входом четвертого элемента сложения по модулю два, а выход соединен с
(6k + l)-м входом третьего элемента сложения по модулю два. Первый вход второго элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 14l-2, а выход
соединен с (4k + l)-м входом второго элемента сложения по модулю два. Первый вход
третьего элемента И 1-й группы соединен с выходом мажоритарного элемента с порогом
14l-4, а выход соединен с (5k + l)-м входом второго элемента сложения по модулю два.
Первый вход четвертого элемента И 1-й группы соединен с выходом мажоритарного элемента с порогом 14l-6, а выход соединен с (6k + l)-м входом второго элемента сложения
по модулю два и (2k + l)-м входом четвертого элемента сложения по модулю два. Первый
вход пятого элемента И l-й группы соединен с выходом мажоритарного элемента с порогом 14l-8, а выход соединен с (7k + l)-м входом второго элемента сложения по модулю
два, (7k + l)-м входом третьего элемента сложения по модулю два и (3k + l)-м входом четвертого элемента сложения по модулю два, (4k + 1)-й вход которого соединен с выходом
первого элемента сложения по модулю два и вторым входом s-го (s = 1, 2, ..., 5) элемента
И l-й группы.
На фиг. 1 представлена схема многовходового одноразрядного сумматора по модулю
семь при n = 15 (k = 1).
Сумматор содержит 7k = 7 мажоритарных элементов (мажоритарный элемент с порогом четырнадцать 1, мажоритарный элемент с порогом двенадцать 2, мажоритарный элемент с порогом десять 3, мажоритарный элемент с порогом восемь 4, мажоритарный элемент с порогом шесть 5, мажоритарный элемент с порогом четыре 6, мажоритарный
элемент с порогом два 7), четыре элемента сложения по модулю два 8-11, k = 1 группу из
пяти элементов И 12-16, n = 14k + 1 = 15 входов 17-31, три выхода 32, 33 и 34.
Многовходовый одноразрядный сумматор по модулю семь (при n = 15) работает следующим образом.
3
BY 7590 C1 2005.12.30
На входы 17-31 подаются двоичные переменные x1-x15 (в произвольном порядке), на
выходах 32, 33 и 34 реализуются соответственно булевы функции r1, r2 и r3 результата,
значения которых составляют позиционный двоичный код суммы по модулю семь
R = 4r1 + 2r2 + r3 числа единиц V(X), содержащихся во входном слове X = (х1, х2, ..., х15):
R = V(X) mod7 = (x1 + x2 + ... + x15) mod7 = 4r1 + 2r2 + r3.
Схема сумматора при n = 15 (фиг. 1) построена в соответствии со следующими соотношениями:
r1 = М4 ⊕ M6L ⊕ M8 ⊕ M8L ⊕ M10L ⊕ M12 ⊕ M12L ⊕ M14;
r2 = M2 ⊕ M4 ⊕ M6 ⊕ M6L ⊕ M8 ⊕ M10 ⊕ M12 ⊕ M14L;
r3 = L ⊕ M6L ⊕ M8 ⊕ M8L ⊕ М14,
где L = x1 ⊕ х2 ⊕ ... ⊕ xn - функция, реализуемая 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.
Работа многовходового одноразрядного сумматора по модулю семь при n = 15 поясняется приводимой ниже таблицей.
В общем случае (для произвольной разрядности n входного слова) предлагаемый многовходовый одноразрядный сумматор по модулю семь формирует трехразрядный позиционный двоичный код суммы по модулю семь R = 4r1 + 2r2 + r3 числа единиц V(X), содержащихся в n-разрядном входном слове X = (x1, x2, ..., хn):
R = V(X) mod 7 = (x1 + х2 + ... + xn) mod 7 = 4r1 + 2r2 + r3.
Без потери общности формула изобретения составлена для значений n = 14k + 1
(k= 1, 2, 3, ...).
При этом схема многовходового одноразрядного сумматора по модулю семь может
быть построена согласно следующим соотношениям:
k
r1 = + (M14l-10
M14l-8L
M14l-6
M14l-6L
M14l-4L
M14l-2
M14l-2
M14l);
M14l-10
M14l-8
M14l-8L
M14l-6
M14l-4
M14l-2
M14lL);
l=1
k
r2 = + (M14l-12
l=1
k
r3 = L
+ (M14l-8L
M14l-6
M14l-6L
M14l) .
l=1
Структура сумматора для других значений n получается из устройства при числе входов, равном n* = 14](n-1)/14[+1, путем удаления избыточных логических элементов и межсоединений в схеме.
Достоинствами многовходового одноразрядного сумматора по модулю семь являются
простая конструкция, высокое быстродействие и широкая область применения.
Источники информации:
1. Патент 3707 C1 BY, МПК G 06F 7/49, 2000.
2. Патент РФ 2047216, МПК G 06F 7/50, 1995 (прототип).
4
BY 7590 C1 2005.12.30
Таблица работы многовходового одноразрядного сумматора по модулю семь
V(X) = x1 + x2 + .... + x15
Входы 17-31
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
R = V(X) mod 7 = 4r1 + 2r2 + r3
r1/32
r2/33
r3/34
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
0
0
0
0
1
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
Документ
Категория
Без категории
Просмотров
0
Размер файла
97 Кб
Теги
патент, by7590
1/--страниц
Пожаловаться на содержимое документа