Устройство для формирования остатка по модулю @ =2 @ +1

 

Изобретение относится к вычислительной технике-, предназначено для формирования остатка по -модулю + +1 и может быть использовано для контроля вычислительных операций сумми f I--I I -Л I рования, вычитания, з ножения. и передачи данных, а также в модулярной арифметике. Цель изобретения - упрощение устройства и повьшение быстродействия . Устройство содержит одноразрядные сумматоры 1, блоки одноразрядных сумматоров 2, входы 3 устройства , выходы 4 остатка устройства, причем количество блоков сумматоров равно (1+1), где I log2n, п - разрядность входного числа, количество сумматоров в i-M блоке 2, где ,...,

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН („)SU(„) А1 (51) 4 С 06 F 11/10

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21-) 3961665/24-24 (22) 16.08.85 (46) 23.09.87. Бюл. 9 35 (7.1) Львовский политехнический институт им. Ленинского комсомола (72) Н.В.Черкасский и В.М.Титков (53) 681.3(088.8) (56) Авторское свидетельство СССР

N 1084799, кл. G 06 F 11/10, 1982.

Авторское свидетельства СССР

М 1084798, кл. G 06 F 1 1/08, 1982, (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ .ОСТАТКА ПО МОДУЛЮ m=2 +1 (57) Изобретение относится к вычислительной технике; предназначено для

K формирования остатка по .модулю ш=2 +

+1 и может быть использовано для контроля вычислительных операций суммирования, вычитания, умножения и передачи данных, а также в модулярной арифметике. Цель изобретения — упрощение устройства и повьппение быстродействия. Устройство содержит одноразрядные сумматоры 1, блоки одноразрядных сумматоров 2, входы 3 устройства, выходы 4 остатка устройства, причем количество блоков сумматоров равно (1+1), где 1=1од и, n — разрядность входного числа, количество сумматоров в i-м блоке 2, где i=1,..., (1-1), равно р k/2, количество сумматоров в i — м блоке 2 — (k+1), количество сумматоров в (1+1)-м блоке

2 — k. Положительный эффект достигается за счет новых взаимосвязей между блоками сумматоров и новой структуры (1+1)-ro блока. 1 ил, 1 133956

Изобретение относится к вычислительной технике, предназначено для формировауния остатка по модулю m=

=:2 +1 и может быть использовано для

:) контроля вычислительных операций суммирования, вычитания, умножения и передачи данных, а также в модулятор. ной арифметике.

Цель изобретения — упрощение устройства и повышение быстродействия, На чертеже изображено предлагаемое устройство.

Устройство содержит одноразрядные сумматоры 1, блоки 2 одноразрядных сумматоров, входы 3 устройства, выходы 4 остатка устройства, причем количество блоков сумматоров равно (1+ I), 1-ре 1=1.ogden, n — разрядность го числа, количество сумматоров в

: — м блоке 2, где i=1,..., (1 — 1), равно р-k/2,, количество сумматоров в

1-м блоке 2 — (k+1), количество сумматоров в (1+1)-м блоке 2

Устройство работает следующим об- 2 разом.

В основу принципа действия устройства заложен алгоритм вычисления ос(4) Отсюда

k k (А) 2 .<-1=<А -А<+А —...+A(>2 +1 (5)

Так как для правой части (5) справедливо правило ассоциативности, то

k — (А,+A +...+А z;Ä ) 2 +1. (6) сумма 2

< А>2 +1=аА,+А +...+А; > 2 +1

k k сумма 1

2 +1

2 татка по модулю 2"+1. Представим п-разрядное двоичное число А в виде суммы разрядов со своими весовыми множителями

А =a,2 +a,2 +...+а„ „ 2 ... (1)

Найдем выражение для остатка по модулю m=2 +1. Для этого разобъем

k число (1) на группы цифр так, чтобы

А=А,2 +А<2 +А 2 +...+А 2, (2) причем

А,=а 2 +а,2 +...+а 2 о < k

А< =а 2 +ak+z 2 +... +а 2 (3) л< k+Z

О < k

А=а „2 +а „2 +...+а, 2 (II+<1

Здесь А, А, . ..А — k-разрядные числа.

В этом случае остаток от деления

k числа А по модулю 2 +i равен е (А> 2 +1=(,2 А, 2 > 2 +1.

Значащий разряд переполнения mразрядной сетки суммы 1 выражения (6) эквивалентен младшему разряду суммы и наоборот.

Схема устройства реализует выражение (5). Б сумматорах первых (1-1) блоков начинают суммы 1 и 2, а в сумматорах 1-го блока складывают обе суммы, причем сечения 2 инвертируют.

В 1-м блоке сумматоров имеется (k+1) -й сумматор знаков, учитывающий знак суммы, получаемой в сумматорах этого блока. Если образуется отрицательное число, его надо превратить в положительное, для этого его надо вычесть из модуля числа. Но так как результат на 1-м блоке получается в обратном коде, его надо сложить с модулем числа, это действие эквивалентно суммированию к коду числа 10 . В соответт ствии с этим выбрана оптимальная структура (1+1)-ro блока.

Формула и з о б р е т е н и я

Устройство для формирования остатКа по модулю m=2 +1, где k=1,2,..., k содержащее блоки одноразрядных сумматоров, причем входы сумматоров первого блока являются входами устройства, выходы сумматоров последнего блока являются выходами остатка, первые входы k сумматоров последнего блока соединены с выходами k первых сумматоров предпоследнего блока, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, исходное и-разрядное число разделено на а5 р=п/ групп (с добавлением нулевых значений разрядов до ближайшего большего целого числа кратного двум) по

k разрядов, общее число блоков сумматоров равно 1+1, где 1=logan, число сумматоров в i — м блоке сумматоров, где i 1,...,1-1, равно р k/2, число сумматоров в 1.-м и (1+1)-м блоках сумматоров равно соответственно k+1 и k причем первые и вторые входы сум55 маторов 1 -й нечетной группы первого блока соединены соответственно с Q-й и (Q+1) и нечетными группами из k разрядов исходного числа, где = 1, ...,1/4, Я=2<-1, первые и вторые вхоСоставитель М.Иваныкин

Редактор Е.Папп Техред М.Дидык Корректор М.Демчик

Заказ 4223/39 Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4 з 133 ды сумматоров -й четной группы первого блока соединены соответственно с Q-й и (Q+1)-й четными группами входов иэ k разрядов исходного числа, выход переноса последнего сумматора

j-го блока сумматоров соединен с входом переноса первого сумматора (j+1)— го блока сумматоров Д=1,...,1), первые и вторые входы сумматоров о -й нечетной группы ы-ro блока сумматоров соединены соответственно с выходами -й и (P+1)-й нечетными группами сумматоров (а-1)-ro блока сумматоров, . первые и вторые входы сумматоров М -й

9566 4 четной группы р -ro блока сумматоров соединены соответственно с выходами

P — и и ()+1) — и четными группами сумматоров (u-1)-го блока сумматоров, где (й=2,..., (1-1); Ы =1,..., р/2, (3 =2 -1; первые прямые и вторые инверсные входы сумматоров 1-го блока соединены соответственно с выходами сумматоров первой и второй групп (1-1)-го блока, первый вход (k+1)-го сумматора 1-го блока подключен к шине логической единицы, выход (k+1)-го сумматора

1-ro блока подключен к второму входу второго сумматора (1+1)-го блока.