close

Вход

Забыли?

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

?

Патент BY 06530

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 6530
(13) C1
(19)
7
(51) G 06F 7/50
(12)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ
ШЕСТИ n-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ
В ПОСЛЕДОВАТЕЛЬНО-ПАРАЛЛЕЛЬНОМ КОДЕ
(21) Номер заявки: a 20000624
(22) 2000.06.30
(46) 2004.09.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович;
Булаш Юрий Леонидович; Петроченко
Андрей Сергеевич; Супрун Валерий
Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
BY 6530 C1
(57)
Устройство для сложения шести n-разрядных двоичных чисел в последовательнопараллельном коде, содержащее три D-триггера, входы установки в ноль которых соединены с входом начальной установки устройства, а входы синхронизации соединены с входом синхронизации устройства, отличающееся тем, что содержит четыре элемента
сложения по модулю два, три элемента ЗАПРЕТ, семь элементов И, два элемента ИЛИ,
два мажоритарных элемента с порогом два, два мажоритарных элемента с порогом четыре
Фиг. 1
BY 6530 C1
и два мажоритарных элемента с порогом шесть, i-й ( i = 1,6 ) вход первого из которых соединен с i-м входом первого мажоритарного элемента с порогом два, i-м входом первого
мажоритарного элемента с порогом четыре, i-м входом первого элемента сложения по модулю два, i-м входом первого элемента И и i-м входом первой группы информационных
входов устройства, i-й вход второй группы информационных входов которого соединен с
i-м входом второго мажоритарного элемента с порогом два, i-м входом второго мажоритарного элемента с порогом четыре, i-м входом второго мажоритарного элемента с порогом
шесть и i-м входом второго элемента сложения по модулю два, выход которого соединен с
первым выходом устройства, второй выход устройства соединен с выходом третьего элемента сложения по модулю два, первый вход которого соединен с выходом второго мажоритарного элемента с порогом четыре, прямым входом первого элемента ЗАПРЕТ, первым
входом второго элемента И и первым входом третьего элемента И, второй вход третьего
элемента сложения по модулю два соединен с выходом первого элемента сложения по
модулю два, входом запрета первого элемента ЗАПРЕТ, первым прямым входом второго
элемента ЗАПРЕТ, первым входом четвертого элемента И, первым входом пятого элемента И, первым входом шестого элемента И и первым входом седьмого элемента И, третий
вход третьего элемента сложения по модулю два соединен с выходом третьего элемента
ЗАПРЕТ, прямой вход которого соединен выходом второго мажоритарного элемента с порогом два, вторым прямым входом второго элемента ЗАПРЕТ, вторым входом пятого
элемента И и вторым входом седьмого элемента И, вход запрета третьего элемента ЗАПРЕТ соединен с выходом второго мажоритарного элемента с порогом шесть, вторым
входом четвертого элемента И, вторым входом шестого элемента И и входом запрета второго элемента ЗАПРЕТ, выход которого соединен с первым входом четвертого элемента
сложения по модулю два, второй вход которого соединен с выходом первого элемента
ЗАПРЕТ, третий вход четвертого элемента сложения по модулю два соединен с выходом
первого мажоритарного элемента с порогом два, вторым входом второго элемента И и
третьим входом пятого элемента И, четвертый вход четвертого элемента сложения по модулю два соединен с выходом первого мажоритарного элемента с порогом четыре, третьим входом шестого элемента И и первым входом первого элемента ИЛИ, пятый вход
четвертого элемента сложения по модулю два соединен с выходом первого мажоритарного элемента с порогом шесть, вторым входом третьего элемента И и третьим входом седьмого элемента И, шестой вход четвертого элемента сложения по модулю два соединен с
выходом первого элемента И и первым входом второго элемента ИЛИ, а выход четвертого
элемента сложения по модулю два соединен с информационным входом первого Dтриггера, выход которого соединен с седьмым входом второго элемента сложения по модулю два, седьмым входом второго мажоритарного элемента с порогом два, седьмым входом второго мажоритарного элемента с порогом четыре и седьмым входом второго
мажоритарного элемента с порогом шесть, выход второго элемента И соединен со вторым
входом первого элемента ИЛИ, третий вход которого соединен с выходом четвертого элемента И, четвертый вход первого элемента ИЛИ соединен с выходом пятого элемента И, а
выход первого элемента ИЛИ соединен с информационным входом второго D-триггера,
выход которого соединен с седьмым входом первого элемента сложения по модулю два,
седьмым входом первого мажоритарного элемента с порогом два, седьмым входом первого мажоритарного элемента с порогом четыре, седьмым входом первого мажоритарного
элемента с порогом шесть и седьмым входом первого элемента И, второй вход второго
элемента ИЛИ соединен с выходом третьего элемента И, третий вход соединен с выходом
шестого элемента И, четвертый вход соединен с выходом седьмого элемента И, а выход
соединен с информационным входом третьего D-триггера, выход которого соединен с
восьмым входом первого элемента сложения по модулю два, восьмым входом первого
мажоритарного элемента с порогом два, восьмым входом первого мажоритарного элемента с порогом четыре, восьмым входом первого мажоритарного элемента с порогом шесть
и восьмым входом первого элемента И.
2
BY 6530 C1
(56)
Белоус А.И. и др. Микропроцессорный комплект БИС серии К1815 для цифровой обработки сигналов. - М.: Радио и связь, 1992. - С. 119.
BY 950174 A, 1997.
BY 960199 A, 1997.
RU 2047216 C1, 1995.
SU 1783516 A1, 1992.
SU 1464155 A1, 1989.
EP 0656582 A1, 1992.
US 5227989 A, 1994.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения быстродействующих арифметических устройств ЭВМ и
специализированных процессоров.
Известно устройство для сложения четырех двоичных чисел в последовательном коде,
содержащее три одноразрядных двоичных сумматора и два триггера [1].
Недостатками устройства являются ограниченные функциональные возможности
(устройство не выполняет сложение более четырех двоичных чисел) и низкое быстродействие, которое обусловлено представлением суммируемых чисел в последовательном коде.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для сложения N двоичных чисел в последовательно-параллельном коде (числа поступают на входы устройства по два разряда одновременно). Устройство содержит дерево конвейерных двухразрядных сумматоров с
запоминанием переноса [2].
Недостатком известного устройства является высокая конструктивная сложность. Так,
например, при N = 6 известное устройство содержит пять конвейерных сумматоров, каждый
из которых включает в себя два комбинационных двоичных сумматора и пять триггеров.
Изобретение направлено на решение задачи упрощения конструкции устройства для
сложения чисел в последовательно-параллельном коде.
Названный технический результат достигается путем введения в состав устройства
элементов сложения по модулю два, мажоритарных элементов, элементов И, элементов
ИЛИ, элементов ЗАПРЕТ, а также изменением связей между элементами устройства.
Устройство для сложения шести n-разрядных двоичных чисел в последовательнопараллельном коде содержит три D-триггера, входы установки в ноль которых соединены
с входом начальной установки устройства, а входы синхронизации соединены с входом
синхронизации устройства.
В отличие от прототипа устройство содержит четыре элемента сложения по модулю
два, три элемента ЗАПРЕТ, семь элементов И, два элемента ИЛИ, два мажоритарных элемента с порогом два, два мажоритарных элемента с порогом четыре и два мажоритарных
элемента с порогом шесть. При этом i-й (i = 1, 6 ) вход первого мажоритарного элемента с
порогом шесть соединен с i-м входом первого мажоритарного элемента с порогом два, i-м
входом первого мажоритарного элемента с порогом четыре, i-м входом первого элемента
сложения по модулю два, i-м входом первого элемента И и i-м входом первой группы информационных входов устройства. В устройстве i-й вход второй группы информационных
входов соединен с i-м входом второго мажоритарного элемента с порогом два, i-м входом
второго мажоритарного элемента с порогом четыре, i-м входом второго мажоритарного
элемента с порогом шесть и i-м входом второго элемента сложения по модулю два, выход
которого соединен с первым выходом устройства. Второй выход устройства соединен с
выходом третьего элемента сложения по модулю два, первый вход которого соединен с
выходом второго мажоритарного элемента с порогом четыре, прямым входом первого
3
BY 6530 C1
элемента ЗАПРЕТ, первым входом второго элемента И и первым входом третьего элемента И. Второй вход третьего элемента сложения по модулю два соединен с выходом первого элемента сложения по модулю два, входом запрета первого элемента ЗАПРЕТ, первым
прямым входом второго элемента ЗАПРЕТ, первым входом четвертого элемента И, первым входом пятого элемента И, первым входом шестого элемента И и первым входом
седьмого элемента И. Третий вход третьего элемента сложения по модулю два соединен с
выходом третьего элемента ЗАПРЕТ. Прямой вход третьего элемента ЗАПРЕТ соединен с
выходом второго мажоритарного элемента с порогом два, вторым прямым входом второго
элемента ЗАПРЕТ, вторым входом пятого элемента И и вторым входом седьмого элемента И.
Вход запрета третьего элемента ЗАПРЕТ соединен с выходом второго мажоритарного
элемента с порогом шесть, вторым входом четвертого элемента И, вторым входом шестого
элемента И и входом запрета второго элемента ЗАПРЕТ. Выход второго элемента ЗАПРЕТ
соединен с первым входом четвертого элемента сложения по модулю два. Второй вход четвертого элемента сложения по модулю два соединен с выходом первого элемента ЗАПРЕТ.
Третий вход четвертого элемента сложения по модулю два соединен с выходом первого
мажоритарного элемента с порогом два, вторым входом второго элемента И и третьим
входом пятого элемента И. Четвертый вход четвертого элемента сложения по модулю два
соединен с выходом первого мажоритарного элемента с порогом четыре, третьим входом
шестого элемента И и первым входом первого элемента ИЛИ. Пятый вход четвертого
элемента сложения по модулю два соединен с выходом первого мажоритарного элемента
с порогом шесть, вторым входом третьего элемента И и третьим входом седьмого элемента И. Шестой вход четвертого элемента сложения по модулю два соединен с выходом
первого элемента И и первым входом второго элемента ИЛИ. Выход четвертого элемента
сложения по модулю два соединен с информационным входом первого D-триггера, выход
которого соединен с седьмым входом второго элемента сложения по модулю два, седьмым входом второго мажоритарного элемента с порогом два, седьмым входом второго
мажоритарного элемента с порогом четыре и седьмым входом второго мажоритарного
элемента с порогом шесть. Выход второго элемента И соединен со вторым входом первого
элемента ИЛИ, третий вход которого соединен с выходом четвертого элемента И. Четвертый вход первого элемента ИЛИ соединен с выходом пятого элемента И. Выход первого
элемента ИЛИ соединен с информационным входом второго D-триггера, выход которого
соединен с седьмым входом первого элемента сложения по модулю два, седьмым входом
первого мажоритарного элемента с порогом два, седьмым входом первого мажоритарного
элемента с порогом четыре, седьмым входом первого мажоритарного элемента с порогом
шесть и седьмым входом первого элемента И. Второй вход второго элемента ИЛИ соединен с выходом третьего элемента И, третий вход соединен с выходом шестого элемента И,
четвертый вход соединен с выходом седьмого элемента И. Выход второго элемента ИЛИ
соединен с информационным входом третьего D-триггера, выход которого соединен с
восьмым входом первого элемента сложения по модулю два, восьмым входом первого
мажоритарного элемента с порогом два, восьмым входом первого мажоритарного элемента с порогом четыре, восьмым входом первого мажоритарного элемента с порогом шесть
и восьмым входом первого элемента И.
На фиг. 1 представлена схема устройства для сложения шести n-разрядных двоичных
чисел в последовательно-параллельном коде.
Устройство содержит четыре элемента сложения по модулю два 1-4, два мажоритарных элемента с порогом два 5 и 6, два мажоритарных элемента с порогом четыре 7 и 8, два
мажоритарных элемента с порогом шесть 9 и 10, семь элементов И 11-17, три элемента
ЗАПРЕТ 18-20, два элемента ИЛИ 21 и 22, три D-триггера 23-25, шесть информационных
входов первой группы 26-31, шесть информационных входов второй группы 32-37, вход
начальной установки 38, вход синхронизации 39 и два выхода 40 и 41.
4
BY 6530 C1
Устройство выполняет сложение шести n-разрядных двоичных чисел Xj = х0j + 2x1j +
+ 4x2j + ... + 2n-1хn-1,j, j = 1,6 , поступающих на его входы в последовательно-параллельном
коде по два разряда одновременно (без потери общности полагаем, что n - четное):
6
6
n / 2 −1
j=1
j=1
t =0
S = ∑Xj = ∑
∑
2 t ( x 2 t , j + 2x 2 t +1, j ) =
n / 2 +1
∑2
k =0
k
(s 2 k + 2s 2 k +1 ),
где sn+3 ≡ 0.
Разрядность суммы S = s0 + 2sl + 4s2 + ... + 2n+2sn+2 равна n + 3 бит, и сложение выполняется за n/2+2 тактов. На каждом такте формируются одновременно по два разряда суммы.
Принцип работы устройства для сложения шести n-разрядных двоичных чисел в последовательно-параллельном коде заключается в потактном сложении двух векторов двоичных
переменных (элементы одного вектора имеют веса, равные 20, а элементы второго вектора веса 21) и формировании на каждом такте очередной пары разрядов суммы (один разряд
имеет вес, равный 20, а второй разряд - вес 21) и трехразрядного вектора переносов. При этом
в каждом такте сложения участвуют шесть пар очередных разрядов операндов (старшие
разряды пар поступают на информационные входы первой группы 26-31, младшие - на
информационные входы второй группы 32-37) и три одноразрядных переноса, хранящихся
в триггерах 23-25 и сформированных на предыдущем такте работы.
Элементы 1-22 (фиг. 1) образуют блок сложения SMU, который выполняет сложение
семи одноразрядных двоичных чисел с весом 20 (четные разряды шести операндов и
младший перенос С1, задержанный на один такт с помощью триггера 23) и восьми одноразрядных двоичных чисел с весом 21 (нечетные разряды шести операндов и два старших
переноса с одинаковыми весами С 2 и С 3 , задержанные на один такт с помощью триггеров 24 и 25).
Здесь и далее веса указаны относительно весов очередных пар разрядов суммируемых
чисел.
Блок сложения SMU формирует пятиразрядный двоичный код: младший разряд текущей пары суммы с весом 20 (выход устройства 41), старший разряд текущей пары суммы с
весом 21 (выход устройства 40), младший перенос С1 с весом 22 (вход триггера 23) и два
старших переноса С2 и С3 с весами 23 (входы триггеров 24 и 25).
Перенос С1 формируется на выходе элемента сложения по модулю два 4, перенос С2 на выходе элемента ИЛИ 21, перенос С3 - на выходе элемента ИЛИ 22. Переносы С1, С2 и
С3 задерживаются на один такт с помощью триггеров 23, 24 и 25 соответственно, поскольку при сложении на следующем такте они должны иметь одинаковые веса с очередными
парами разрядов операндов.
Математическое описание работы устройства для сложения шести n-разрядных двоичных чисел в последовательно-параллельном коде имеет вид:
Q1 (r ) + x 2 r −2,1 + x 2 r − 2, 2 + x 2 r − 2,3 + x 2 r −2, 4 + x 2 r − 2,5 + x 2 r − 2, 6 +
⎫
⎪
+ 2(Q 2 (r ) + Q 3 (r ) + x 2 r −1,1 + x 2 r −1, 2 + x 2 r −1,3 + x 2 r −1, 4 + x 2 r −1,5 + x 2 r −1, 6 ) = ⎪⎪
⎬
= s 2 r − 2 + 2s 2 r −1 + 4C1 (r ) + 8C 2 (r ) + 8C 3 (r );
⎪
⎪
Q1 (r + 1) = C1 (r ); Q 2 (r + 1) = C 2 (r ); Q 3 (r + 1) = C 3 (r ); r = 1, n / 2 + 2, ⎪⎭
где xij, i = 0, n − 1 , j = 1,6 , - значение i-го разряда j-го операнда (очевидно, что xnj = xn+1,j =
= xn+2,j = xn+3,j ≡ 0);
C1(r), C2(r), C3(r) - значения переносов С1, С2 и С3 соответственно, формируемых на r-м
такте и записываемых соответственно в триггеры 23, 24 и 25 в момент окончания такта;
Q1(r), Q2(r), Q3(r) - состояния соответственно триггеров 23, 24 и 25 на r-м такте (очевидно, что Q1(1) = Q2(1) = Q3(1) = 0, поскольку триггеры перед началом работы обнулены,
и Q1(n/2 + 3) = Q2(n/2 + 3) = Q3(n/2 + 3) = 0, так как C1(n/2 + 2) = C2(n/2 + 2) = C3(n/2 + 2) = 0).
5
BY 6530 C1
Работа блока сложения SMU описывается следующей системой булевых функций:
s0 = L(X2);
6
s1 = M 72 (Х2)⋅ M 7 (Х2)⊕ M 74 (Х2)⊕L(Х1);
6
С1= M 74 (Х2)⋅ L (Х1)⊕ M 72 (Х2)⋅ M 7 (Х2)⋅L(Х1)⊕ M 82 (Х1)⊕ M 84 (Х1)⊕ M 86 (X1)⊕ M 88 (X1);
C2= M 67 (X2)⋅L(X1)∨ M 84 (X2)⋅ M 82 (X1)∨ M 72 (X2)⋅ M 82 (X1)⋅L(X1)∨ M 84 (X1);
C3= M 67 (X2)⋅ M 84 (X1)⋅L(X1)∨ M 74 (X2)⋅ M 86 (X1)∨ M 72 (X2)⋅ M 86 (X1)⋅L(X1)∨ M 88 (X1),
где X1=(Q2(r),Q3(r),x2r-1,1,x2r-1,2,x2r-1,3,x2r-1,4,x2r-1,5,x2r-1,6);
X2=(Q1(r),x2r-2,1,x2r-2,2,x2r-2,3,x2r-2,4,x2r-2,5,x2r-2,6);
L(X1)=Q2(r) ⊕ Q3(r) ⊕ x2r-1,1 ⊕ x2r-1,2 ⊕ x2r-1,3 ⊕ x2r-1,4 ⊕ x2r-1,5 ⊕ x2r-1,6;
L(X2)=Q1(r) ⊕ x2r-2,1 ⊕ x2r-2,2 ⊕ x2r-2,3 ⊕ x2r-2,4 ⊕ x2r-2,5 ⊕ x2r-2,6;
Mm8(X1), Mm7(X2) - функции, реализуемые мажоритарными элементами с порогами
m∈{2,4,6,8}, которые определяются следующим образом:
1, если Q 2 (r ) + Q 3 (r ) + x 2 r −1,1 + x 2 r −1, 2 + x 2 r −1,3 + x 2 r −1, 4 + x 2 r −1,5 + x 2 r −1, 6 ≥ m;
M 8m (X1 ) =
0, если Q 2 (r ) + Q 3 (r ) + x 2 r −1,1 + x 2 r −1, 2 + x 2 r −1,3 + x 2 r −1, 4 + x 2 r −1,5 + x 2 r −1, 6 < m,
M 7m (X 2 ) =
1, если Q1 (r ) + x 2 r −2,1 + x 2 r −2, 2 + x 2 r −2,3 + x 2 r −2, 4 + x 2 r −2,5 + x 2 r −2, 6 ≥ m;
0, если Q1 (r ) + x 2 r −2,1 + x 2 r −2, 2 + x 2 r −2,3 + x 2 r −2, 4 + x 2 r −2,5 + x 2 r − 2, 6 < m,
Очевидно, что M 88 (X1) - конъюнкция, реализуемая элементом И:
M 88 (Х1) = Q2(r)⋅Q3(r)⋅x2r-1,1⋅х2r-1,2⋅x2r-1,3⋅x2r-1,4⋅x2r-1,5⋅x2r-1,6.
Устройство для сложения шести n-разрядных двоичных чисел в последовательнопараллельном коде работает следующим образом.
На вход начальной установки 38 подается импульс, обнуляющий триггеры 23-25. В
сопровождении серии из n/2 тактовых импульсов, поступающих на вход синхронизации 39,
на информационные входы первой группы 26-31 последовательно подаются n/2 векторов
нечетных (старших) разрядов (x11, x12,..., x16), (x31, x32,..., x36),…, (xn-1,1, xn-1,2,…, xn-1,6) суммируемых чисел, а на информационные входы второй группы 32-37 - n/2 векторов четных
(младших) разрядов (x01, x02,…, x06), (x21, x22,…, x26),…, (xn-2,1, xn-2,2,…, xn-2,6) суммируемых
чисел.
На выходах 40 и 41 устройства также последовательно формируются пары нечетных и
четных разрядов суммы (sl, s0), (s3, s2),..., (sn-1, sn-2).
После этого подача сигналов на информационные входы 26-37 блокируется, а на вход
синхронизации 39 подаются дополнительно два тактовых импульса, которые обеспечивают формирование трех старших разрядов суммы. Первый (из двух дополнительных) импульс формирует пару (sn+l, sn), а второй - пару (0, sn+2), так как sn+3 ≡ 0.
После прихода (n/2 + 2)-го тактового импульса устройство готово к сложению очередных чисел без предварительного обнуления триггеров 23-25.
Укажем, что нечетные разряды s1, s3,..., sn+1 формируются на выходе 40 устройства, а
четные разряды s0, s2,..., sn+2 - на выходе 41 устройства.
Работа устройства для сложения шести n-разрядных двоичных чисел в последовательно-параллельном коде иллюстрируется таблицей (фиг. 2), в которой представлены сигналы на входах и выходах устройства, а также содержимое триггеров 23-25 при сложении
шести шестиразрядных двоичных чисел (n = 6)
X1 = 100111, X2 = 011110, X3 = 110011, X4 = 111101, X5 = 110110, X6 = 101011:
6
6
2
j=1
j=1 t = 0
4
S = ∑ X j = ∑∑ 2 t ( x 2 t , j + 2x 2 t +1, j ) = ∑ 2 k (s 2 k + 2s 2 k +1 ) =
k =0
= 100111 + 011110 + 110011 + 111101 + 110110 + 101011 = 100010110.
6
BY 6530 C1
Достоинствами устройства для сложения шести n-разрядных двоичных чисел в последовательно-параллельном коде являются простая конструкция, высокое быстродействие и
отсутствие латентности при формировании результата.
Источники информации:
1. SU 1783516 A1. 1992.
2. Белоус А.И. и др. Микропроцессорный комплект БИС серии К 1815 для цифровой
обработки сигналов. -М.: Радио и связь, 1992. - C. 119.
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
Документ
Категория
Без категории
Просмотров
0
Размер файла
198 Кб
Теги
06530, патент
1/--страниц
Пожаловаться на содержимое документа