Устройство для сложения @ -разрядных чисел в избыточной системе счисления Советский патент 1985 года по МПК G06F7/49 

блока устройства и вторыми входами элементов И третьих групп всех сумматоров по модулю PI данного суммирующего блока, второй выход формирователя сигналов переноса соединен с входом нулевого переноса следующего суммирующего блока устройства и с вторыми входами элементов И первых групп всех сумматоров по модулю Pj данного суммирующего блока, а третий выход соединен с входом положительного переноса следующего суммирующего блока устройства и вторыми входами элементов И вторых групп всех сумматоров по модулю Pj данного суммирующего блока, выходы элементов ИЛИ второй группы каждого /-го сумматора по модулю PI соединены с выходом суммы по /-му основанию системы остаточных классов данного суммирующего блока, выходы отрицательного и положительного переносов п-го суммирующего блока соединены с первым и вторым входами сумматора по модулю два, третий и четвертый входы которого соединены с первым и вторым входами знаков устройства, а выход - с выходом знака устройства.

2. Устройство по п. 1, отличающееся тем, что формирователь сигналов переноса содержит первый и второй дещифраторы кода системы остаточных классов в код «Один из / (где ), первый и втоЭ

рой элементы ИЛИ, первый и второй элементы НЕ и элемент И, причем входы первого и второго дещифратора, с первого по к-й (где ), соединены с соответствующими входами формирователя сигналов переноса, а выходы подключены соответветственно к входам первого и второго элементов ИЛИ, выходы которых соединены соответственно с первым и третьим выходами формирователя сигналов переноса и с входами первого и второго элементов НЕ, выходы которых соединены с входами элемента Ц выход которого подключен к второму выходу формирователя сигналов переноса.

1. УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ /г-РАЗРЯДНЫХ ЧИСЕЛ В ИЗБЫТОЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ, содержащее п суммирующих блоков, входы первого и второго операндов которых являются первыми и вторыми входами соответствующих разрядов устройства, а выходы - выходами разрядов устройства, отличающееся тем, что, с целью повышения быстродействия, оно дополнительно содержит сумматор по модулю два, а каждый суммирующий блок содержит формирователь сигналов переноса и т сумматоров по модулю PJ (где , 1,2,..., т; т - количество оснований системы остаточных классов), каждый из которых содержит первый и второй дешифраторы двоичного кода в код один из Р , матричньш сумматор по модулю, первую и вторую группы элементов ИЛИ и шесть групп элементов И, причем в каждом j-м сумматоре по модулю Р входы первого и второго дещифраторов соединены с входами первого и второго операндов /-и группы данного суммирующего блока, а выходы подключены соответственно к первым и вторым входам матричного сумматора по модулю, первый выход которого соединен с первыми входами первого элемента И первой группы, второго элемента И второй группы, элемента И третьей группы, каждый /-и выход матричного сумматора по модулю, где ,3,..., (Pj-1), соединен с первыми входами /-ГО элемента И первой группы, (/4-1)-го элемента И второй группы и ll-1)-го элемента И третьей группы, а Р;-й выход соединен с первыми входами Р,-го элемента И первой группы, первого элемента И второй группы и (Р/- 1)-го элемента И третьей группы, выходы элементов И первой, второй и третьей групп соединены соответственно с первыми, вторыми и третьими входами соответствующих элементов ИЛИ первой группы, выход первого элемента ИЛИ первой группы соединен с первыми входами первого элемента И четвертой группы, второго элемента И пятой группы и Pj-ro элемента И шестой группы, выход каждого 1-го элемента ИЛИ первой группы соединен с первыми входами /-ГО элемента И четвертой группы (i + l)-ro элемента И пятой группы и (i-1)-го элемента И шестой группы, выход Р -го элемента ИЛИ первой груп пы соединен с первыми входами Ру-го эле(Л мента И четвертой группы, первого элемента И пятой группы и (Р/-1)-го элемента И шестой группы, выходы элементов И четвертой, пятой и шестой групп соединены соответственно с первыми, вторыми и третьими входами соответствующих элементов ИЛИ второй группы, вторые входы элементов И четвертых групп всех сумматоров по модулю PI данного суммирующего бло00 ка соединены с выходом нулевого перено00 са предыдущего суммирующего блока устройства, вторые входы элементов И пятых групп всех сумматоров по модулю Р,- дан00 ного суммирующего блока соединены с выходом положительного переноса предыдущего суммирующего блока устройства, а вторые входы элементов И шестых групп соединены с выходом отрицательного переноса предыдущего суммирующего блока устройства, входы формирователя сигналов переноса, с первого по к -и, где к Р , соединены с соответствующими выходами матричных сумматоров по модулю всех сумматоров по модулю Р данного суммирующе го блока, первый выход формирователя сигна ЛОБ переноса соединен с входом отрицательного переноса следующего суммирующего

1

Изобретение относится к вычислительной технике и может быть использовано в специализированных ЭВМ.

Цель изобретения - повыщение быстродействия устройства.

На фиг. 1 приведена структурная схема устройства для сложения «-разрядных чисел в избыточной системе счисления- на фиг. 2 - структурная схема суммирующего блока; на фиг. 3 - структурная схема формирователя сигналов переноса; на фиг. 4 - структурная схема сумматора по модулю два.

Устройство содержит п суммирующих блоков 1, входы которых соединены с соответствующими разрядами первого и второго входов устройства, и сумматор 2 по модулю два, первый и второй входы которого соединены с входами знаков устройства, выходы суммирующих блоков соединены с выходами разрядов устройства, выход сумматора по модулю два соединен с выходом знака устройства.

Каждый суммирующий блок 1 содержит т сумматоров 3 по модулю Р/ (где ,2,... гп; m - количество оснований системы остаточных классов (СОК) и формирователь и сигналов переноса. Каждый сумматор по модулю Р; содержит дещифраторы 5 и 6 двоичного кода в код «Один из Р;, матричный сумматор 7 по модулю, группы элементов И 8-13 и группы элементов ИЛИ 14 и 15. Формирователь 4 сигналов переноса содержит дещифраторы 16 и 17 кода СОК в код «Один из R (где , элементы ИЛИ

18 и 19, элементы НЕ 20 и 21, и элемент И 22.

Сумматор 2 по модулю два содержит элементы НЕ 23-25, элемент ИЛИ 26, элементы И 27-30 и элемент ИЛИ 31.

Пусть выбраны m оснований Pj СОК:

R I№j,

в качестве основания избыточной системы счисления можно принять величину: r R/2-4

тогда допустимые значения цифр в данной системе счисления будут

Wi: -г/2, -(г/2-1),..., -2 -1, 0,1,2,..., r/2-l, г/2;

Обозначим операнды через х и у, а их сумму через s. Значения их могут принимать следующие величины.

S.-, X;. yt:-(Т/2+1), -Г/2, (г/2-1),...,

-2,-1,0,1,2,..., г/2-1, г/2, г/2+1.

В дальнейщем отрицательные значения цифр будем обозначать черточкой над соответствующей цифрой.

С учетом введенных обозначений можно записать:

W,-(X;+y/)-rt; ь + ti,

где при Wm, +Y.- WmaA-; t;-| 1 при Xi+yi Wmax; t;. ПрИХгЧ- .

Пример. Выберем систему оснований СОК Pj 3; ,Р2Рз 60; . ДoпYCти Iыe знaчeнияJ W;: 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2,1, О,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13;

S,, X,-, у,-: И, ГЗ, f2, П, Го, 9, 8, 7, 6, 5, 4, 3, 2, Т,

О, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14; Пусть слагаемые X и Y и их сумма S в г-ичной системе счисления имеют вид:

S +0 I. 24; 20; 18; 8

В избыточной г-ичной системе счисления операнды и сумма имеют вид:

Процесс получения суммы выполняется в два этапа: сначала формируется промежуточная сумма W и вектор переносов t, затем определяется значение суммы .

В данном устройстве в каждом суммирующем блоке 1 формируются величины (s-1), S и (s-f-1) с помощью групп 11 -13 элементов И.

По управляющим входам элементы одной из этих групп открываются управляющими сигналами -1 и О, поступающими на них с выхода формирователя сигналов переноса 4 младшего разряда. Таким образом, процесс суммирования W+t заменяется процессом выбора одного из трех значений суммы (s-1), s или (s+1) и передачи его через элементы ИЛИ групп 15 на выход соответствующего разряда. Значение суммы с выходов матричного сумматора 7 в коде

«Один из Ру поступает на входы дешифраторов 16 и 17 формирователя 4 сигналов переноса. Дешифраторы представляют собой совокупность из г/2 элементов И на m входов, Дещифратор 16 дешифрирует числа в диапазоне от 1 до г/2 и с помощью элемента ИЛИ 18 формирует сигнал «Отрицательный перенос (-1), дешифратор 17 дешифрирует числа в диапазоне от Зг/4 до R-2 и с помощью элемента ИЛИ 19 формирует сигнал «Положительный перенос (+1). Сигнал «Нулевой перенос (0) формируется при отсутствии сигналов (-1) и (-1-1).

Кодирование г-ичных чисел с помощью кода СОК применено для повышения быстродействия суммирующих блоков 1, так

как сумматоры 3 по отдельным основаниям СОК могут быть малоразрядными, выполненными таблично и работающими параллельно. Отсутствие переноса между отдельными сумматорами по основанию Pi

0 дает возможность выполнить сложение г-ичных чисел за один такт. Для представления г-ичных цифр кодам СОК применена искусственная форма, когда в качестве нуля принята величина R/2.

5 Положительные г-ичные цифры кодируются в виде:

+ x R/2+x(x60, г/2+1),

отрицательные г-ичные цифры кодируются в виде:

-x R/2-x, (--x6-(r/2-f 1), 0).

Известно, что су.мма двух чисел СОК в искусственной форме получается в два такта: первый такт - суммирование, второй такт - коррекция результата на величину константы R/2.

Пусть исходные операнды в избыточной г-ичной системе счисления те же, что в расс.матриваемом примере, а именно:

10 6

8 10 8 14

у 0

Закодируемкаждую г-ичную цифру кодом СОК пооснованиям Pi 3; в искусственной форме и выполним сложение:

3,4,53,4,5 3,4,5 3,4,5

к. ;

(2,0,0)(0,0,1) (2,2,3)

(1,0,3) (2,2,0) (1,1.4) (0,0,2) 50S-I-20 Результат получен такой же, как и в предыдущем примере. Причем этот результат сформирован на выходе матричных сумматоров: 7Чтобы не производить операцию вычисления константы R/2, имеюш,ую значащую цифру только по четному основанию ( в нащем случае ), целесообразно сумматор 3 по основанию выполнить так, чтобы он вырабатывал результат со смещением на -(R/2)p2 Конструктивно это выполняется при построении матричного сумматора 7. Теперь с помощью элементов И групп 8-10, на входах которых число w представлено в коде «Один из Р/, получают величины (w-br); w; (w-г), что эквивалентно (w+26) w и (w -26), так как единица переноса в старщем разряде эквивалентна величине младщего разряда: 3,4,5 3,4,5 3,4,5 3,4,5

(0,2,4) (1,0,1) (0,3,0) (2,2,3)

(1,0,3) (2,2,0) (1,1,4) (0,0,2) w 1 (2,2,2) (0,0,4) (2,3,3) (1,2,1)

личина w .

В результате сумма на выходе устройства имеет вид: группы элементов И в соответствующих г-ичных разрядах суммирующих блоков 1:9, 10, 10, 8. Сумматор 2 по модулю два в знаковом разряде выдает величину 1. На выходе элементов ИЛИ группы 14 число имеет вид: 3,4,5 3,4,5 3,4,5 I (1,0,3) (0,0,4) (2,3,3) (2,2,3) 38s8 В соответствии с сигналами переносов, поступающими из младщих разрядов ( 1 1 1 9) в старщих г-ичных разрядах суммирующих блоков 1 открываются элементы И следующих групп, 13, 13, 11, 12. Через элементы И групп 13 проходит величина (w + 1/ через элементы И групп 11 - величина (w - 1), через элементы И групп 12 - веОдновременно в каждом г-ичном разряде с помощью формирователя сигналов переноса 4 формируются сигналы переноса, которые поступают на вторые входы элементов И групп 8-10 соответственно:

t 0|1 1 1 О

Таким образом, собственными сигналами переносов открываются следующие

3,4,5

3,4,5 (ТДО

1 (2,1,4) 29 причем На элементах ИЛИ групп 15 г-ичный разряд результата по каждому из оснований представлен двоичным кодом в искусственной форме СОК.

и/4 4

I f

jrN/:

16

18

v

Pm

11

19

V

-/

0 фиг. 3

V

+ /

u

v

:э