close

Вход

Забыли?

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

?

Патент BY9837

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2007.10.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/48
G 06F 7/38
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ N ДВОИЧНЫХ ЧИСЕЛ В
ПОСЛЕДОВАТЕЛЬНОМ КОДЕ ПО МОДУЛЮ ТРИ
(21) Номер заявки: a 20050903
(22) 2005.09.19
(43) 2006.02.28
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Супрун Валерий Павлович (BY)
BY 9837 C1 2007.10.30
BY (11) 9837
(13) C1
(19)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 5224 C1, 2003.
BY a 20030229, 2003.
BY 5094 C1, 2003.
BY 5079 C1, 2003.
SU 1783516 A1, 1992.
US 4229802, 1980.
JP 1304532 A, 1989.
(57)
Устройство для сложения N двоичных чисел (N ≥ 2) в последовательном коде по модулю три, содержащее многовходовый одноразрядный сумматор по модулю три, i-й вход
( i = 1, N ) которого соединен с i-м информационным входом устройства, два двухступенчатых синхронных D-триггера, входы синхронизации которых соединены с входом синхронизации устройства, а входы обнуления - с входом начальной установки устройства, отличающееся тем, что информационный вход первого синхронного D-триггера соединен с
выходом старшего разряда многовходового одноразрядного сумматора по модулю три, а
прямой выход - с первым выходом устройства и (N + 1)-м входом многовходового одноразрядного сумматора по модулю три, выход младшего разряда которого соединен с информационным входом второго синхронного D-триггера, прямой выход которого соединен со вторым выходом устройства и (N + 2)-м и (N + 3)-м входами многовходового
одноразрядного сумматора по модулю три.
Фиг. 1
BY 9837 C1 2007.10.30
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики.
Известно устройство для сложения N двоичных чисел в последовательном коде, содержащее многовходовый одноразрядный сумматор и р сдвигающих регистров
(p = [log2m], где m = N + p) [1].
Недостатком устройства является невозможность вычисления остатка по модулю три
от суммы N двоичных чисел.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для сложения шести n-разрядных двоичных чисел в последовательно-параллельном коде, содержащее два семивходовых одноразрядных сумматора, полусумматор, блок суммирования и три двухступенчатых синхронных D-триггера [2].
Недостатком известного устройства является невозможность сложения по модулю три
N n-разрядных двоичных чисел.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления остатка по модулю три от суммы N n-разрядных двоичных чисел.
Названный технический результат достигается путем изменения связей между элементами устройства.
Устройство для сложения N двоичных чисел (N≥2) в последовательном коде по модулю три содержит многовходовый одноразрядный сумматор по модулю три, i-й вход
( i = 1, N ) которого соединен с i-м информационным входом устройства, и два двухступенчатых синхронных D-триггера, входы синхронизации которых соединены с входом синхронизации устройства, а входы обнуления - с входом начальной установки устройства.
В отличие от прототипа информационный вход первого D-триггера соединен с выходом старшего разряда многовходового одноразрядного сумматора по модулю три, а прямой
выход - с первым выходом устройства и (N + 1)-м входом многовходового одноразрядного
сумматора по модулю три. Выход младшего разряда многовходового одноразрядного
сумматора по модулю три соединен с информационным входом второго D-триггера, прямой выход которого соединен со вторым выходом устройства и (N + 2)-м и (N + 3)-м входами многовходового одноразрядного сумматора по модулю три.
На чертеже (фиг. 1) представлена схема устройства для сложения N двоичных чисел в
последовательном коде по модулю три.
Устройство содержит многовходовый одноразрядный сумматор по модулю три 1, два
двухступенчатых синхронных D-триггера 2 и 3, N информационных входов 41-4N, вход
синхронизации 5, вход начальной установки 6 и два выхода 7 и 8.
Поясним принцип работы устройства.
Устройство выполняет сложение по модулю три N n-разрядных двоичных чисел
Хi = 2n-1 хi,n + 2n-2 хi,n-1 + ... + 2хi,2 + хi,1, xi,j ∈ {0,1}, i = 1, N , j = 1, n , поступающих одновременно на входы устройства в последовательном коде младшими разрядами вперед:
 N

R = 2r1 + r2 =  ∑ X i  mod 3 ,
(1)
 i=1 
где r1, r2 ∈ {0,1}.
Для определенности полагаем, что n = 2k, k = 1, 2, 3,... Представим (1) в виде:
2
BY 9837 C1 2007.10.30
k

N k
R =  ∑  ∑ 22l − 2 x i, 2l −1 + ∑ 22l −1 x i , 2l   mod 3 =

 i =1  l =1
l =1
N
N
k




 
=  ∑   ∑ 22l − 2 x i, 2l −1  mod 3 +  ∑ 22l −1x i, 2l  mod 3   mod 3 =

 i =1


 l =1   i =1
(2)

 N


 k  N
=  ∑   ∑ x i, 2l −1  mod 3 +  2∑ x i, 2l  mod 3   mod 3.

 i =1


 l =1   i =1
Из (2) следует, что нечетные разряды xi,1, хi,3, ..., хi,n-1 должны суммироваться по модулю три с весом 2°, а четные разряды xi,2, xi,4, ..., xi,n - с весом 21, i = 1, N .
Принимая во внимание (2), сумму по модулю три S j = 2s1j + s 2j , s1j , s 2j ∈ { 0, 1 } , первых
(начиная с младших) j, 1 ≤ j ≤ n, разрядов (с учетом их весов) суммируемых чисел Xi можно записать в виде:
N
 j 


S j =  ∑  2 2[ t / 2 ]− t +1 ∑ x i, t  mod 3  mod 3 .
(3)

 t =1 

i =1
Здесь [а] - ближайшее целое, не превышающее а.
Очевидно, что Sn = R и s1n = r1 , s n2 = r2 .
Тогда
N


S j =  2 2[ j / 2]− j+1 ∑ x i , j + S j−1  mod 3 =
i =1


 N

 ∑ x i , j + 2s1j−1 + s 2j−1  mod 3, если j − нечетное;

=  i=1 N


 2∑ x i , j + 2s1j−1 + s 2j−1  mod 3, если j − четное,
 i=1

(4)
где S0 ≡ 0.
Выравнивая веса суммируемых разрядов, перепишем (4) в виде:
 N

 ∑ x i, j + s1j−1 + s1j−1 + s 2j−1  mod 3, если j − нечетное;

S j =  i =1 N
(5)
 
j−1
j−1
j−1  
 2 ∑ x i, j + s1 + s 2 + s 2   mod 3, если j − четное.
  i =1

Таким образом, соотношения (5) определяют процедуру вычисления суммы по модулю три N n-разрядных двоичных чисел Хi как итерационный n-шаговый процесс, на j-м
шаге которого (1 ≤ j ≤ n) выполняется сложение по модулю три N одноименных разрядов
операндов x1,j, x2,j, ..., xN,j и трех разрядов накопленной частичной суммы S j-1 − s1j−1 , s1j−1 и
s 2j−1 на нечетном шаге сложения и s1j−1 , s 2j−1 и s 2j−1 на четном шаге сложения. При этом все
участвующие в сложении по модулю три одноразрядные двоичные числа имеют одинаковые веса - 20 на нечетном шаге сложения и 21 на четном шаге сложения.
В устройстве сложение по модулю три N + 3 одноразрядных двоичных чисел выполняется многовходовым одноразрядным сумматором по модулю три 1, а для хранения разрядов s1j и s 2j накапливаемой частичной суммы Sj используются триггеры 2 и 3. При этом
выход старшего разряда (с весом 21) сумматора 1 соединен с информационным входом
первого триггера 2, а выход младшего разряда (с весом 20) - с информационным входом
второго триггера 3. Сигналы с прямых выходов триггеров 2 и 3 подаются на информационные входы сумматора 1, причем сигнал с выхода триггера 3 - в раздвоенном виде.
Напомним, что в общем случае многовходовый одноразрядный сумматор по модулю
три выполняет сложение по модулю три m одноразрядных двоичных чисел (с весом 20):
3
BY 9837 C1 2007.10.30
S = 2s1 + s2 = (y1 + y2 + ... + ym) mod 3,
где s1, s2 ∈ {0,1} - значения соответственно старшего и младшего разрядов результата,
формируемых на выходах сумматора.
Такой сумматор может выполнять и сложение по модулю три одноразрядных двоичных чисел, имеющих вес 21. Действительно,
(2у1 + 2у2 + ... + 2уm) mod 3 = (2(2s1 + s2))mod 3 = (4s1 + 2s2)mod 3 = 2s2 + s1.
(6)
Из (6) следует, что при сложении одноразрядных двоичных чисел с весом 21 старший
разряд результата формируется на выходе младшего разряда сумматора, а младший разряд
результата - на выходе старшего разряда сумматора.
Предлагаемое устройство построено с учетом соотношений (5) и (6).
Обозначим: Q1j−1 и Q 2j−1 - состояния соответственно первого 2 и второго 3 триггеров
перед началом j-го шага сложения, 1 ≤ j ≤ n и Q10 ≡ 0 , Q 02 ≡ 0 .
Тогда работа устройства может быть описана следующими соотношениями:

 N

S j = 2s1j + s 2j =  ∑ x i, j + Q1j−1 + Q 2j−1 + Q 2j−1  mod 3;
 i =1


j

s , если j − нечетное;
Q1j = 1 j
(7)

s 2 , если j − четное;


s 2j , если j − нечетное;
j

Q2 =

s1j , если j − четное.
Распишем выполнение процедуры (7) по шагам (для четных значений n).
 N

1
1
j = 1 : S1 = 2s1 + s 2 =  ∑ x i ,1 + 0 + 0 + 0  mod 3; Q11 = s11 ; Q12 = s12 .
 i =1

N


j = 2 : S 2 = 2s12 + s 22 =  ∑ x i, 2 + s11 + s12 + s12  mod 3; Q12 = s 22 ; Q 22 = s12 .
 i =1

N


j = 3 : S 3 = 2s13 + s 32 =  ∑ x i,3 + s 22 + s12 + s12  mod 3; Q13 = s13 ; Q 32 = s 32 .
 i =1

N


j = 4 : S 4 = 2s14 + s 42 =  ∑ x i , 4 + s13 + s 32 + s 32  mod 3; Q14 = s 42 ; Q 42 = s14 .
 i =1

………………………………………………………………………………………….
 N

j = n − 1 : S n −1 = 2s1n −1 + s n2 −1 =  ∑ x i,n −1 + s n2 − 2 + s1n − 2 + s1n − 2  mod 3; Q1n −1 = s1n −1 ; Q n2 −1 = s n2 −1
 i =1

N


j = n : S n = 2s1n + s n2 =  ∑ x i ,n + s1n −1 + s n2 −1 + s n2 −1  mod 3; Q1n = s n2 ; Q n2 = s1n .
 i =1

n
n
Результат R = 2r1 + r2 = Sn и r1 = s1 = Q 2 , r2 = s n2 = Q1n .
Таким образом, после выполнения n-го шага во втором триггере 3 будет записан старший разряд r1 результата, а в первом триггере 2 - младший разряд r2 результата вычисления остатка по модулю три от суммы N n-разрядных двоичных чисел.
Очевидно, если разрядность n нечетная, то по окончании n-шага старший разряд r1 результата будет записан в первом триггере 2, а младший разряд r2 - во втором триггере 3.
Устройство для сложения N двоичных чисел в последовательном коде по модулю три
работает следующим образом.
На вход начальной установки 6 подается импульс, обнуляющий триггеры 2 и 3. На
информационные входы 41,42, ..., 4N подаются последовательно во времени разряды xl,j,
4
BY 9837 C1 2007.10.30
x2,j, ..., xN,j суммируемых по модулю три чисел X1, X2, ..., XN (начиная с младших разрядов
x1,1, x2,1, ..., xN,l), сопровождаемые серией из n тактовых импульсов, поступающих на вход
синхронизации 5.
После окончания последнего (n-го) тактового импульса в триггерах 2 и 3 будут запи N

саны двоичные разряды r1 и r2 результата операции R =  ∑ X i  mod 3 , которые поступают
 i=1 
на выходы 7 и 8 устройства.
Работу устройства проиллюстрируем на примере сложения шести восьмиразрядных
двоичных чисел X1 = 10111010, Х2 = 01100111, Х3 = 01001100, Х4 = 10011110,
Х5 = 10100110, Х6 = 00011101.
В таблице (фиг. 2) для каждого такта (шага) приведены значения сигналов на входе
многовходового одноразрядного сумматора по модулю три 1 и значения сигналов на выходах старшего (поступает на вход первого триггера 2) и младшего (поступает на вход
второго триггера 3) разрядов сумматора 1 с указанием их принадлежности к старшему s1j
или младшему s 2j разрядам частичной суммы Sj.
Из фиг. 2 видно, что в конце последнего (восьмого) такта сложения в первый триггер 2
будет записана логическая единица ( s 82 = 1 ), а во второй триггер 3 - логический ноль ( s18 = 0 ).
 6

Следовательно, R = 2r1 + r2 =  ∑ X i  mod 3 = S8 = 2s18 + s 82 = 01 .
 i=1 
В десятичной системе счисления суммируемые в рассмотренном примере числа имеют вид: Х1 = 186, Х2 = 103, Х3 = 76, Х4 = 158, Х5 = 166, Х6 = 29.
 6

Тогда R =  ∑ X i  mod 3 = 718 mod 3 = 01 .
 i=1 
Отметим, что из рассмотренного принципа работы устройства непосредственно следует, что устройство может выполнять сложение по модулю три двоичных чисел, поступающих и старшими разрядами вперед.
Если разрядность n суммируемых чисел нечетная, то вес по модулю три старшего разряда равен 20, и в конце первого такта в триггеры 2 и 3 будут записаны соответственно
значения s11 и s12 , а в конце n-го такта - s1n и s n2 .
Если разрядность n суммируемых чисел четная, то вес по модулю три старшего разряда равен 21, и в конце первого такта в триггеры 2 и 3 будут записаны соответственно значения s12 и s11 , а в конце n-го такта - s1n и s n2 .
Иными словами, при подаче суммируемых по модулю три чисел старшими разрядами
вперед на входы устройства независимо от величины n по окончании последнего такта
старший разряд результата будет записан в первый триггер 2, младший разряд результата
- во второй триггер 3.
Укажем, что при сложении по модулю три младшими или старшими разрядами вперед
в общем случае накапливаемые частичные суммы Sj при 1 ≤ j ≤ n-1 не совпадают, однако в
любом случае на последнем такте S n = 2s1n + s n2 = R = 2r1 + r2 .
Процесс сложения чисел (из рассмотренного выше примера) по модулю три старшими
разрядами вперед иллюстрируется таблицей (фиг. 3).
Из фиг. 3 следует, что в конце последнего (восьмого) такта сложения в первый триггер
2 будет записан логический ноль ( s18 = 0 ), а во второй триггер 3 - логическая единица
( s 82 = 1 ). Таким образом, результат R = S8 = 2s18 + s 82 = 01 .
Достоинствами устройства для сложения N двоичных чисел в последовательном коде
по модулю три являются простая конструкция, высокое быстродействие и широкие функциональные возможности.
5
BY 9837 C1 2007.10.30
Источники информации:
1. Патент РБ № 4931, МПК G 06F 7/50, 2003.
2. Патент РБ № 5224, МПК G 06F 7/50, 2003 (прототип).
Работа устройства при сложении чисел по модулю три
младшими разрядами вперед
Сигналы на вхо№ такСигналы на входах сумматора по модулю три 1
дах триггеров
та
j−1
j−1
j−1
j
х1,j / 41 х2,j / 42 х3,j / 43 х4,j / 44 x5,j / 45 x6,j / 46 Q1 /7 Q 2 /8 Q 2 /8
2
3
1
0
1
0
0
0
1
0
0
0
s11 = 1
s12 = 0
2
1
1
0
1
1
0
1
0
0
s 22 = 1
s12 = 0
3
0
1
1
1
1
1
1
0
0
s13 = 0
s 32 = 0
4
1
0
1
1
0
1
0
0
0
s 42 = 0
s14 = 1
5
1
0
0
1
0
1
0
1
1
s15 = 1
s 52 = 0
6
1
1
0
0
1
0
1
0
0
s 62 = 0
s16 = 1
7
0
1
1
0
0
0
0
1
1
s17 = 0
s 72 = 1
8
1
0
0
1
1
0
0
1
1
s 82 = 1
s18 = 0
Фиг. 2
Работа устройства при сложении чисел по модулю три
старшими разрядами вперед
Сигналы на вхо№ такСигналы на входах сумматора по модулю три 1
дах триггеров
та
j−1
j−1
j−1
j
х1,9-j / 41 х2,9-j / 42 х3,9-j / 43 х4,9-j / 44 x5,9-j / 45 x6,9-j / 46 Q1 /7 Q 2 /8 Q 2 /8
2
3
1
1
0
0
1
1
0
0
0
0
s12 = 0
s11 = 0
2
0
1
1
0
0
0
0
0
0
s12 = 1
s 22 = 0
3
1
1
0
0
1
0
1
0
0
s 32 = 0
s13 = 1
4
1
0
0
1
0
1
0
1
1
s14 = 1
s 42 = 0
5
1
0
1
1
0
1
1
0
0
s 52 = 1
s15 = 0
6
0
1
1
1
1
1
1
0
0
s16 = 0
s 62 = 0
7
1
1
0
1
1
0
0
0
0
s 72 = 0
s17 = 1
8
0
1
0
0
0
1
0
1
1
s18 = 0
s 82 = 1
Фиг. 3
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
132 Кб
Теги
by9837, патент
1/--страниц
Пожаловаться на содержимое документа