close

Вход

Забыли?

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

?

Патент BY7591

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 7591
(13) C1
(19)
(46) 2005.12.30
(12)
7
(51) G 06F 7/49, 7/50,
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ ТРИ В
ПОСЛЕДОВАТЕЛЬНОМ ДОПОЛНИТЕЛЬНОМ КОДЕ
(21) Номер заявки: a 20030229
(22) 2003.03.13
(43) 2003.12.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Петроченко Андрей Сергеевич; Супрун
Валерий Павлович (BY)
BY 7591 C1 2005.12.30
G 01F 11/10
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) SU 796849, 1981.
BY 3703 C1, 2000.
SU 1084799 A, 1984.
JP 2207323 A, 1990.
EP 0353041 A2, 1990.
(57)
Устройство для сложения чисел по модулю три в последовательном дополнительном
коде, содержащее первый элемент ИЛИ и первый и второй триггеры, входы установки в
ноль которых соединены с входом начальной установки устройства, отличающееся тем,
что содержит два элемента сложения по модулю два, четыре элемента И, два элемента
ЗАПРЕТ, полусумматор, второй и третий элементы ИЛИ и третий триггер, вход установки
в ноль которого соединен с входом начальной установки устройства, счетный вход соединен со входами синхронизации первого и второго триггеров и входом синхронизации устройства, а прямой выход соединен с первым входом первого и первым входом второго
элементов сложения по модулю два, второй вход первого элемента сложения по модулю
два соединен со вторым входом второго элемента сложения по модулю два и управляющим входом устройства, третий вход соединен с первым входом первого элемента И, первым выходом устройства и прямым выходом первого триггера, счетный вход которого соединен с выходом второго элемента ИЛИ, третий вход второго элемента сложения по
модулю два соединен с первым входом второго элемента И, вторым выходом устройства
и прямым выходом второго триггера, счетный вход которого соединен с выходом третьего
Фиг. 1
BY 7591 C1 2005.12.30
элемента ИЛИ, первый вход второго элемента ИЛИ соединен с выходом первого элемента
ЗАПРЕТ, второй вход соединен с выходом третьего элемента И, третий вход соединен с
выходом первого элемента И, второй вход которого соединен со вторым входом второго
элемента И и выходом первого элемента ИЛИ, i-й (i = 1, 2) вход которого соединен с i-м
информационным входом устройства и i-м входом полусумматора, первый вход третьего
элемента ИЛИ соединен с выходом второго элемента ЗАПРЕТ, второй вход соединен с
выходом четвертого элемента И, третий вход соединен с выходом второго элемента И,
выход суммы полусумматора соединен с первым входом третьего элемента И и прямым
входом второго элемента ЗАПРЕТ, вход запрета которого соединен с выходом первого
элемента сложения по модулю два и первым входом четвертого элемента И, второй вход
которого соединен с выходом переноса полусумматора и прямым входом первого элемента ЗАПРЕТ, вход запрета которого соединен с выходом второго элемента сложения по
модулю два и вторым входом третьего элемента И.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения устройств контроля ЭВМ и специализированных процессоров.
Известно устройство для вычисления остатков по модулю три, содержащее m групп
блоков сложения по модулю три и m групп триггеров [1].
Недостатками устройства являются высокая конструктивная сложность и ограниченные функциональные возможности.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления и хранения остатков по
модулю три, содержащее два триггера, две схемы сравнения, элемент И-НЕ и элемент
ИЛИ [2].
Недостатком известного устройства являются ограниченные функциональные возможности, обусловленные невозможностью вычисления остатков по модулю три от суммы двоичных чисел, представленных в позиционной системе счисления в дополнительном
коде.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет обеспечения вычисления остатков по модулю три от суммы двух
двоичных чисел, представленных в позиционной системе счисления в дополнительном
коде.
Названный технический результат достигается путем введения в состав устройства
третьего триггера, второго и третьего элементов ИЛИ, двух элементов сложения по модулю два, четырех элементов И, двух элементов ЗАПРЕТ и полусумматора, а также изменением связей между элементами устройства.
Устройство для сложения чисел по модулю три в последовательном дополнительном
коде содержит первый элемент ИЛИ, первый и второй триггеры, входы установки в ноль
которых соединены с входом начальной установки устройства.
В отличие от прототипа, устройство содержит два элемента сложения по модулю два,
четыре элемента И, два элемента ЗАПРЕТ, полусумматор, второй и третий элементы ИЛИ
и третий триггер, вход установки в ноль которого соединен с входом начальной установки
устройства, счетный вход соединен с входами синхронизации первого и второго триггеров
и входом синхронизации устройства, а прямой выход соединен с первым входом первого
и первым входом второго элементов сложения по модулю два. Второй вход первого элемента сложения по модулю два соединен со вторым входом второго элемента сложения
по модулю два и управляющим входом устройства, третий вход соединен с первым входом первого элемента И, первым выходом устройства и прямым выходом первого триггера, счетный вход которого соединен с выходом второго элемента ИЛИ. Третий вход второго элемента сложения по модулю два соединен с первым входом второго элемента И,
вторым выходом устройства и прямым выходом второго триггера, счетный вход которого
2
BY 7591 C1 2005.12.30
соединен с выходом третьего элемента ИЛИ. Первый вход второго элемента ИЛИ соединен с выходом первого элемента ЗАПРЕТ, второй вход соединен с выходом третьего элемента И, третий вход соединен с выходом первого элемента И, второй вход которого соединен со вторым входом второго элемента И и выходом первого элемента ИЛИ, i-й (i = 1,
2) вход которого соединен с i-м информационным входом устройства и i-м входом полусумматора. Первый вход третьего элемента ИЛИ соединен с выходом второго элемента
ЗАПРЕТ, второй вход соединен с выходом четвертого элемента И, третий вход соединен с
выходом второго элемента И. Выход суммы полусумматора соединен с первым входом
третьего элемента И и прямым входом второго элемента ЗАПРЕТ, вход запрета которого
соединен с выходом первого элемента сложения по модулю два и первым входом четвертого элемента И, второй вход которого соединен с выходом переноса полусумматора и
прямым входом первого элемента ЗАПРЕТ, вход запрета которого соединен с выходом
второго элемента сложения по модулю два и вторым входом третьего элемента И.
На фиг. 1 представлена схема устройства для сложения чисел по модулю три в последовательном дополнительном коде.
Устройство содержит двухступенчатый Т-триггер 1, два синхронных двухступенчатых
Т-триггера 2 и 3, два элемента сложения по модулю два 4 и 5, три элемента ИЛИ 6, 7 и 8,
полусумматор 9, четыре элемента И 10, 11, 12 и 13, два элемента ЗАПРЕТ 14 и 15, управляющий вход 16, два информационных входа 17 и 18, вход синхронизации 19, вход начальной установки 20, выходы старшего 21 и младшего 22 разрядов результата.
Поясним принцип работы устройства. Устройство формирует остаток S по модулю
три от суммы двух (n + 1)-разрядных двоичных чисел (один разряд - знаковый), представленных в дополнительном коде и поступающих младшими разрядами вперед на информационные входы устройства:
S = (X + Y)mod3,
где S = 2s1 + s2, S ∈ {0,1,2}, s1,s2 ∈ {0,1};
X = –2nхn + 2n-1xn-1 + 2n-2xn-2 +...+ 2x1 + x0, хi ∈ {0,1}, i = 0, n ;
Y = –2nyn + 2n-1yn-1 + 2n-2yn-2 +…+ 2y1 + y0, yi ∈ {0,1};
хn, уn - знаковые разряды, которые в дополнительном коде имеют отрицательные веса,
равные –2n.
В общем случае остатком по модулю три от целого положительного числа А является
такое число S = Amod3, что А = 3k + S,
где k = 0,1,2,...; S ∈ {0,1,2}.
Остаток по модулю три для отрицательного числа –А может быть определен следующим образом:
0, если S = 0;
R = (− A) mod 3 = (−3k − S) mod 3 = (3 − S) mod 3 = 1, если S = 2;
(1)
2, если S = 1.
Представим выражения для дополнительных кодов суммируемых чисел X и Y в виде:
X = −2 n x n +
Y = −2 y n +
n
]n / 2 [ −1
∑
i =0
]n / 2[ −1
∑
i=0
22i x2i +
2 y 2i +
2i
[ n / 2 ]−1
∑
j=0
2 2 j+1 x 2 j+1,
(2)
[ n / 2 ]−1
∑
j= 0
2
2 j+1
y 2 j+1 .
Принимая во внимание (2), запишем:



 ]n / 2 [−1
 − 2 n ( x n + y n ) mod 3 +  ∑ ( x 2 i + y 2 i )  mod 3 + 



 i =0
( X + Y ) mod 3 = 
 mod 3.
[ n / 2 ]−1

 + 2 ∑ ( x + y )  mod 3
2 j+1 

  j=0 2 j+1


 
(
)
3
(3)
BY 7591 C1 2005.12.30
Остаток по модулю три от суммы знаковых разрядов с учетом (1) вычисляется следующим образом:
(− ( x n + y n )) mod 3 = (2( x n + y n )) mod 3, если n - четное ;
− 2 n ( x n + y n ) mod 3 =
(4)
(− 2(x n + y n ) ) mod 3 = (x n + y n ) mod 3, если n - нечетное.
Тогда из (3) и (4) следуют выражения для вычисления остатка по модулю три от суммы S = X + Y дополнительных кодов чисел:
если n - четное, то

  n / 2−1


  ∑ ( x 2 i + y 2 i )  mod 3 +


  i =0
(5)
S = ( X + Y ) mod 3 = 
 mod 3;
−
n
/
2
1


 + 2 ( x n + y n ) + ∑ ( x 2 j+1 + y 2 j+1 )  mod 3 


 
j=0


 
если n - нечетное, то
( n +1) / 2−1



  ( x n + y n ) + ∑ ( x 2i + y 2i )  mod 3 + 


 
i =0

(6)
S = (X + Y) mod 3 = 
 mod 3.

  ( n −1) / 2−1 

 + 2 ∑ x 2 j+1  mod 3


  j=0
Выражения (5) и (6) определяют алгоритм вычисления остатка по модулю три, который реализован в предлагаемом устройстве.
Устройство содержит два рабочих триггера 2 и 3, которые хранят текущее значение
остатка по модулю три от суммы поступивших разрядов чисел X и Y (после подачи на
информационные входы 17 и 18 всех разрядов чисел, включая знаковые, в триггерах будет
храниться искомый результат S = (X + Y)mod3).
Очередные поступающие пары разрядов чисел суммируются по модулю три с остатком, хранящимся в триггерах 2 и 3. Накапливаемый остаток записывается в эти же триггеры. При этом цифровые разряды четных пар (хо, уо),(х2, у2),...,(х2]n/2[-2, у2]n/2-2) имеют вес,
равный 20 = 1, а цифровые разряды нечетных пар (x1, y1),(х3, у3),...,(x2[n/2]-1, y2[n/2]-l) - вес,
равный 21 = 2.
Для указания четности (нечетности) очередной пары цифровых разрядов используется
триггер 1, состояние которого изменяется на противоположное с приходом каждого импульса синхронизации, поступающего на счетный вход триггера. В устройстве принято,
что нулевое состояние триггера 1 соответствует четным парам, а единичное состояние
триггера 1 - нечетным парам разрядов чисел.
Последними на информационные входы устройства поступают знаковые разряды хn и
уn. Как следует из (5) и (6), знаковые разряды суммируется по модулю три с содержимым
рабочих триггеров 2 и 3 с такими же весами, как и старшие цифровые разряды хn-1 и уn-1
(независимо от четности/нечетности n).
Следовательно, для того чтобы устройство обрабатывало знаковые разряды так же,
как и цифровые, необходимо изменить состояние триггера 1 на противоположное в момент прихода знаковых разрядов. В устройстве это обеспечивается подачей на управляющий вход 16 специального сигнала "Признак знакового разряда", который сопровождает
знаковые разряды чисел и суммируется по модулю два с состоянием триггера 1.
Устройство для сложения чисел по модулю три в последовательном дополнительном
коде работает следующим образом.
На вход начальной установки 20, подается импульс, обнуляющий триггеры 1, 2 и 3.
Далее на информационные входы 17 и 18 последовательно во времени подаются пары
разрядов (х0, y0),(х1, y1),...,(хn-1, yn-1),(xn, yn) суммируемых чисел Х и Y (начиная с младших
цифровых разрядов (х0, у0) и заканчивая знаковыми разрядами (хn, уn)). Каждая пара разрядов чисел сопровождается тактовым импульсом С, подаваемым на вход синхронизации
19. Знаковые разряды (хn, уn) сопровождаются также сигналом "Признак знакового разряда" Z, который поступает на управляющий вход 16.
(
)
4
BY 7591 C1 2005.12.30
После окончания последнего, (n + 1)-го, тактового импульса С в рабочих триггерах 2 и
3 будет храниться остаток по модулю три S = 2s1 + s2 = (X + Y)mod3 от суммы чисел X и
Y, представленных в дополнительном коде. При этом в триггере 2 будет записан старший
разряд s1, а в триггере 3 - младший разряд s2 остатка S.
Работа устройства описывается приводимой ниже таблицей (фиг. 2).
Устройство построено в соответствии со следующими соотношениями:
q1 = (x ∨ y)Q1 ∨ (x ⊕ y)(T ⊕ Q2) ∨ xy( T ⊕ Q2 );
q2 = (x ∨ y)Q2 ∨ (x ⊕ y)( T ⊕ Q1 ) ∨ xy(T ⊕ Q1),
где q1, q2 - сигналы на счетных входах первого 2 и второго 3 рабочих триггеров соответственно;
Q1, Q2 - состояния рабочих триггеров 2 и 3 соответственно;
x, у - текущие значения разрядов чисел, подаваемые на информационные входы 17 и
18 устройства;
T - состояние триггера четности/нечетности 1;
Z - сигнал "Признак знакового разряда", подаваемый на управляющий вход 16 устройства.
Укажем, что полусумматор 9 формирует на своих выходах сигналы суммы s = х ⊕ у и
переноса р = ху, где х и у - сигналы на входах полусумматора.
На фиг. 3 в качестве примера приведены временные диаграммы работы устройства
при вычислении остатка по модулю три от суммы представленных в дополнительном коде
чисел:
X = –27x7 + 26x6 + 25x5 +...+ 2x1 + x0 = 11011101;
Y = –27у7 + 26у6 + 25у5 +...+ 2у1 + у0 = 11100101.
Как следует из фиг. 3, после окончания восьмого тактового импульса С в триггере 2
будет записан старший разряд s1 = Q1 = 0, а в триггере 3 - младший разряд s2 = Q2 = 1 остатка S = 2s1 + s2 = (X + Y)mod3 = 11011101mod3 = 01.
Действительно, число X = 11011101 в дополнительном коде соответствует отрицательному десятичному числу X = –35, а число Y = 11100101 - отрицательному десятичному числу Y = –27. Тогда (–35–27)mod3 = (–62)mod3 = (–2)mod3 = 1.
Достоинствами устройства для сложения чисел по модулю три в последовательном
дополнительном коде являются простая конструкция, высокое быстродействие и широкая
область применения.
Источники информации:
1. А.с. СССР 1211733, МПК G 06F 11/10, 1984.
2. А.с. СССР 796849, МПК G 06F 11/10, 1979 (прототип).
Таблица работы устройства для сложения чисел по модулю три
в последовательном дополнительном коде
Признак Признак четного
Результат (состояния
Значения текущих Исходные состоязнакового разряда (выход
перехода триггеров
разрядов чисел ния триггеров 2 и 3
разряда
триггера 1)
2 и 3)
Z/16
T
x/17
y/18
Q1/21
Q2/22
s1/21
s2/22
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
0
0
5
BY 7591 C1 2005.12.30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
Фиг. 2
Фиг. 3
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
Продолжение табл.
1
0
0
0
0
1
0
0
0
1
1
0
1
0
0
0
0
1
1
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
1
1
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
Документ
Категория
Без категории
Просмотров
0
Размер файла
114 Кб
Теги
патент, by7591
1/--страниц
Пожаловаться на содержимое документа