close

Вход

Забыли?

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

?

Патент BY 05312

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 5312
(13) C1
(19)
7
(51) G 06F 11/10
(12)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ И ХРАНЕНИЯ ОСТАТКОВ
ПО МОДУЛЮ ТРИ
(21) Номер заявки: a 19990819
(22) 1999.08.31
(46) 2003.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович;
Булаш Юрий Леонидович; Супрун Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
BY 5312 C1
(57)
Устройство для вычисления и хранения остатков по модулю три, содержащее первый
элемент ИЛИ и первый и второй триггеры, входы установки в ноль которых соединены с
входом начальной установки устройства, отличающееся тем, что содержит два элемента
сложения по модулю два, два элемента И, второй элемент ИЛИ и третий триггер, вход установки в ноль которого соединен с входом начальной установки устройства, счетный
вход соединен с входами синхронизации первого и второго триггеров и с входом синхронизации устройства, а прямой выход соединен с первым входом первого и первым входом
второго элементов сложения по модулю два, второй вход первого элемента сложения по
модулю два соединен с управляющим входом устройства, второй вход второго элемента
сложения по модулю два соединен с управляющим входом устройства, третий вход первого элемента сложения по модулю два соединен с первым входом первого элемента
ИЛИ, первым выходом устройства и прямым выходом первого триггера, счетный вход которого соединен с выходом первого элемента И, первый вход которого соединен с информационным входом устройства, а второй вход соединен с выходом первого элемента
ИЛИ, третий вход второго элемента сложения по модулю два соединен с первым входом
второго элемента ИЛИ, вторым выходом устройства и прямым выходом второго триггера,
счетный вход которого соединен с выходом второго элемента И, первый вход которого
соединен с информационным входом устройства, а второй вход соединен с выходом второго элемента ИЛИ, второй вход первого элемента ИЛИ соединен с выходом второго элемента сложения по модулю два, второй вход второго элемента ИЛИ соединен с
инверсным выходом первого элемента сложения по модулю два.
Фиг. 1
BY 5312 C1
(56)
SU 1211733 A, 1986.
RU 2047217 C1, 1995.
SU 1324486 A1, 1994.
EP 0374420 A2, 1990.
US 3816728 A, 1974.
GB 2033115 A, 1980.
Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения устройств контроля ЭВМ и специализированных процессоров.
Известно устройство для вычисления остатков по модулю три, содержащее m групп
блоков сложения по модулю три и m групп триггеров [1].
Недостатком устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления и хранения остатков по модулю три, содержащее два триггера, две схемы сравнения, элемент И-НЕ и элемент ИЛИ [2].
Недостатком известного устройства для вычисления и хранения остатков по модулю
три являются ограниченные функциональные возможности, обусловленные невозможностью вычисления остатков по модулю три для отрицательных чисел, представленных в
дополнительном коде. Кроме того, устройство требует для своей работы внешних элементов для формирования сигнала, поступающего на управляющий вход устройства. При
этом сигнал на входе синхронизации устройства зависит от значения текущего разряда
обрабатываемого двоичного кода. Указанные недостатки затрудняют использование известного устройства в параллельно-конвейерных системах обработки данных.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства для вычисления и хранения остатков по модулю три.
Названный технический результат достигается путем введения в состав устройства
дополнительно третьего триггера, второго элемента ИЛИ, двух элементов сложения по
модулю два, двух элементов И, а также изменением связей между элементами устройства.
Устройство для вычисления и хранения остатков по модулю три содержит первый
элемент ИЛИ, первый и второй триггеры, входы установки в ноль которых соединены с
входом начальной установки устройства.
В отличие от прототипа, в устройство дополнительно введены два элемента сложения
по модулю два, два элемента И, второй элемент ИЛИ и третий триггер, вход установки в
ноль которого соединен с входом начальной установки устройства. Счетный вход третьего триггера соединен с входами синхронизации первого и второго триггеров и с входом
синхронизации устройства, а прямой выход соединен с первым входом первого и первым
входом второго элементов сложения по модулю два. Второй вход первого элемента сложения по модулю два соединен с управляющим входом устройства, второй вход второго
элемента сложения по модулю два соединен с управляющим входом устройства. Третий
вход первого элемента сложения по модулю два соединен с первым входом первого элемента ИЛИ, первым выходом устройства и прямым выходом первого триггера, счетный
вход которого соединен с выходом первого элемента И, первый вход которого соединен с
информационным входом устройства, второй вход соединен с выходом первого элемента
ИЛИ. Третий вход второго элемента сложения по модулю два соединен с первым входом
второго элемента ИЛИ, вторым выходом устройства и прямым выходом второго триггера,
счетный вход которого соединен с выходом второго элемента И, первый вход которого
соединен с информационным входом устройства, второй вход соединен с выходом второго элемента ИЛИ. Второй вход первого элемента ИЛИ соединен с выходом второго эле-
2
BY 5312 C1
мента сложения по модулю два, второй вход второго элемента ИЛИ соединен с инверсным выходом первого элемента сложения по модулю два.
На фиг. 1 представлена схема устройства для вычисления и хранения остатков по модулю три.
Устройство содержит два синхронных двухступенчатых Т-триггера 1 и 2, двухступенчатый Т-триггер 3, два элемента сложения по модулю два 4 и 5, два элемента ИЛИ 6 и 7,
два элемента И 8 и 9, информационный вход 10, управляющий вход 11, вход синхронизации 12, вход начальной установки 13, выходы старшего 14 и младшего 15 разрядов результата.
Поясним принцип работы устройства. Устройство формирует остаток S по модулю
три входного двоичного слова X, представленного в дополнительном коде и поступающего младшими разрядами вперед на информационный вход устройства:
S = Xmod3,
где S = 2sl + s2, S ∈ {0,1,2}, sl,s2 ∈ {0,1};
X = -2nxn + 2n-l xn-1 + 2n-2 xn-2 + ... + 2x1 + x0, xi ∈ {0,1}, i = 0, n ;
xn - знаковый разряд, который в дополнительном коде имеет отрицательный вес, равный - 2n.
В общем случае остатком по модулю три от целого положительного числа А является
такое число S = Amod3, что А = 3k + S,
где k = 0, 1, 2,...; 0 ≤ S ≤ 2.
Остаток по модулю три для отрицательного числа - А может быть определен следующим образом:
0, если S = 0;
R = (-A)mod3 = (-3k - S)mod3 = (3 - S)mod3 = 1, если S = 2;
(1)
2, если S = 1.
Представим выражение для дополнительного кода входного двоичного слова X в виде:
X = −2 n x n +
]n / 2[−1
¦
i =0
[ n / 2]−1
2 2i x 2i +
¦
j=0
2 2 j+1x 2 j+1 .
Принимая во внимание (2), запишем:
§
§ ]n / 2[−1 ·
·
·
§ [ n / 2] −1
X mod 3 = ¨¨ (−2 n x n ) mod 3 + ¨ ¦ x 2i ¸ mod 3 + 2¨ ¦ x 2 j+1 ¸ mod 3 ¸¸ mod 3 .
¸
¨
¸
¨
¸
¨
© i=0 ¹
¹
© j= 0
¹
©
(2)
(3)
Остаток по модулю три от знакового разряда с учетом (1) вычисляется следующим
образом:
(−2 n x n ) mod 3 =
(− x n ) mod 3 = (2 x n ) mod 3, если n − четное;
(−2 x n ) mod 3 = ( x n ) mod 3, если n − нечетное.
(4)
Тогда из (3) и (4) следуют выражения для вычисления остатка по модулю три:
если n - четное, то
·
§ § n / 2 −1 ·
n / 2 −1
·
§
S = X mod 3 = ¨¨ ¨ ¦ x 2i ¸ mod 3 + 2¨ x n + ¦ x 2 j+1 ¸ mod 3 ¸¸ mod 3 ;
¸
¨
¸
¨ ¨© i = 0 ¸¹
j= 0
¹
©
¹
©
(5)
( n +1) / 2 −1 ·
·
§§
§ ( n −1) / 2 −1 ·
S = X mod 3 = ¨¨ ¨ x n +
x 2i ¸ mod 3 + 2¨ ¦ x 2 j+1 ¸ mod 3¸¸ mod 3 .
¦
¸
¨
¸
¸
¨ ¨©
i =0
¹
¹
© j= 0
¹
©
(6)
если n - нечетное, то
Выражения (5) и (6) определяют алгоритм вычисления остатка по модулю три от дополнительного кода входного слова X, который реализован в устройстве.
3
BY 5312 C1
Устройство содержит два рабочих триггера 1 и 2, которые хранят текущее значение
остатка по модулю три от поступивших разрядов слова X (после подачи на информационный вход 10 всех разрядов слова, включая знаковый, в триггерах будет храниться искомый результат S = Xmod3).
Очередные поступающие разряды слова суммируются по модулю три с остатком, хранящимся в триггерах 1 и 2. Накапливаемый остаток записывается в эти же триггеры. При
этом четные цифровые разряды x0, x2, …, x2]n/2[-2 имеют вес, равный 20 = 1, а нечетные
цифровые разряды х0, х2, ..., х2[n/2]-1 - вес, равный 21 = 2.
Для указания четности (нечетности) очередного цифрового разряда слова служит
триггер 3, состояние которого изменяется на противоположное с приходом каждого импульса синхронизации, поступающего на счетный вход триггера. В устройстве принято,
что нулевое состояние триггера 3 соответствует четному разряду слова, а единичное состояние триггера 3 - нечетному разряду слова.
Последним на информационный вход устройства поступает знаковый разряд хn. Как
следует из (5) и (6), знаковый разряд суммируется по модулю три с содержимым рабочих
триггеров 1 и 2 с таким же весом, как и старший цифровой разряд xn-1 (независимо от четности/нечетности n).
Следовательно, для того, чтобы устройство обрабатывало знаковый разряд так же, как
и цифровой, необходимо изменить состояние триггера 3 на противоположное в момент
прихода знакового разряда. В устройстве это обеспечивается подачей на управляющий
вход специального сигнала “Признак знакового разряда”, который сопровождает знаковый разряд и суммируется по модулю два с состоянием триггера 3.
Устройство для вычисления и хранения остатков по модулю три работает следующим
образом.
На вход начальной установки 13 подается импульс, обнуляющий триггеры 1, 2 и 3.
Далее на информационный вход 10 последовательно во времени подаются разряды x0, x1,
…, xn-1, xn входного слова Х (начиная с младшего цифрового разряда x0 и заканчивая знаковым разрядом xn). Каждый разряд слова (независимо от его значения) сопровождается
тактовым импульсом С, подаваемым на вход синхронизации 12. Знаковый разряд хn сопровождается сигналом "Признак знакового разряда" Z, который поступает на управляющий вход 11. После окончания последнего ((n + 1)-го) тактового импульса С в рабочих
триггерах 1 и 2 будет храниться остаток по модулю три S = 2s1 + s2 = Xmod3 входного
слова X, представленного в дополнительном коде. При этом в триггере 1 будет записан
старший разряд s1, а в триггере 2 - младший разряд s2 остатка S.
Работа устройства описывается приводимой ниже таблицей (фиг. 2).
Устройство построено в соответствии со следующими соотношениями
q1 = x(Ql ∨ (T ⊕ Q2 ⊕ Z));
q2 = x(Q2 ∨ ( T ⊕ Ql ⊕ Z )),
где
q1, q2 - сигналы на счетных входах первого 1 и второго 2 рабочих триггеров соответственно;
Q1, Q2 - состояния первого 1 и второго 2 рабочих триггеров соответственно;
х - текущее значение разряда входного слова, подаваемого на информационный вход
10 устройства;
Т- состояние триггера четности/нечетности 3;
Z - сигнал "Признак знакового разряда", подаваемый на управляющий вход 11 устройства.
На фиг. 3 в качестве примера представлены временные диаграммы работы устройства
при вычислении остатка входного слова, представленного в дополнительном коде:
X = -27x7 + 26x6 + 25x5 + ... + 2x1 + x0 = 11011101.
4
BY 5312 C1
Как следует из фиг. 3, после окончания восьмого тактового импульса С в триггере 1
будет записан старший разряд s1 = Q1 = 0, а в триггере 2 - младший разряд s2 = Q2 = 1 остатка S = 2s1 + s2 = X mod3 = 11011101mod3 = 01.
Действительно, число X = 11011101 в дополнительном коде соответствует отрицательному десятичному числу Х = -35. Тогда (-35)mod3 = (-2)mod3 = 1.
Достоинствами устройства для вычисления и хранения остатков по модулю три являются простая конструкция, высокое быстродействие и широкая область применения.
Источники информации:
1. А.с. СССР 1211733, 1984.
2. А.с. СССР 796849, 1979.
Фиг. 2
Фиг. 3
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
169 Кб
Теги
патент, 05312
1/--страниц
Пожаловаться на содержимое документа