Устройство для сложения @ -разрядных чисел в избыточной системе счисления

 

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 ного суммирующего блока соединены с выходом положительного переноса предыдущего суммирующего блока устройства, а вторые входы элементов И шестых групп соединены с выходом отрицательного переноса предыдущего суммирующего блока устройства , входы формирователя сигналов переноса, с первого по к -и, где к Р , соединены с соответствующими выходами матричных сумматоров по модулю всех сумматоров по модулю Р данного суммирующе го блока, первый выход формирователя сигна ЛОБ переноса соединен с входом отрицательного переноса следующего суммирующего

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

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

РЕСПУБЛИН

„„SU„„1188731 (д) 4 G 06 F 7/49

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3?83060/24-24 (22) 27.06.84 (46) 30.10.85. Бюл. № 40 (72) В. Г. Евстигнеев и О. В. Евстигнеева (71) Московский институт инженеров гражданской авиации (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР № 824198, кл. G 06 F 7/49, 1979.

Proc. 1ЕЕЕ, 1966, v. 54, р. 1910 — 1919.

fig. 1. (54) (57) 1. УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ и-РАЗРЯДНЫХ ЧИСЕЛ В ИЗБЫТОЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ, содержащее и суммирующих блоков, входы первого и второго операндов которых являются первыми и вторыми входами соответствующих разрядов устройства, а выходы— выходами разрядов устройства, отличающееся тем, что, с целью повышения быстродействия, оно дополнительно содержит сумматор по модулю два, а каждый суммирующий блок содержит формирователь сигналов переноса и m сумматоров по модулю

Р; (где;= 1,2,..., m; m — кол и ч ест в о ос нований системы остаточных классов), каждый из которых содержит первый и второй дешифраторы двоичного кода в код один из

Р, матричный сумматор по модулю, первую и вторую группы элементов ИЛИ и шесть групп элементов И, причем в каждом j-м сум= маторе по модулю P входы первого и второго дешифраторов соединены с входами первого и второго операндов j-й группы данного суммирующего блока, а выходы подключены соответственно к первым и вторым входам матричного сумматора по модулю, первый выход которого соединен с первыми входами первого элемента И первой группы, второго элемента И второй группы, Р;-ro элемента И третьей группы, каждый l-й выход матричного сумматора по модулю, где

1=2,3,..., (Р; — 1), соединен с первыми входами l-го элемента И первой группы, (1+ 1) -го элемента И второй группы и

1 1 — 1) -го элемента И третьей группы, а

Р;- и выход соединен с первыми входами

P;-ro элемента И первой группы, первого элемента И второй группы и (Р; — 1)-го элемента И третьей группы, выходы элементов И первой, второй и третьей групп соединены соответственно с первыми, вторыми и третьими входами соответствующих элементов ИЛИ первой группы, выход первого элемента ИЛИ первой группы соединен с первыми входами первого элемента И четвертой группы, второго элемента И пятой группы и Р;-ro элемента И шестой группы, выход каждого l-го элемента ИЛИ первой группы соединен с первыми входами l-ro элемента И четвертой группы (i+ 1) -го элемента И пятой группы и (i — 1)-го элемента И шестой группы, выход Р -ro элемента ИЛИ первой группы соединен с первыми входами P,-ro элемента И четвертой группы, первого элемента И пятой группы и (Р; — 1)-го элемента И шестой группы, выходы элементов И четвертой, пятой и шестой групп соединены соответственно с первыми, вторыми и третьими входами соответствующих элементов

ИЛИ второй группы, вторые входы элементов И четвертых групп всех сумматоров по модулю Р; данного суммирующего блока соединены с выходом нулевого переноса предыдущего суммирующего блока устройства, вторые входы элементов И пятых групп всех сумматоров по модулю Р; данного суммирующего блока соединены с выходом положительного переноса предыдущего суммирующего блока устройства, а вторые входы элементов И шестых групп соединены с выходом отрицательного переноса предыдущего суммирующего блока устройства, входы формирователя сигналов переноса, с первого по к= -й, где к= Р, соединены с соответствующими выходами матричных сумматоров по модулю всех сумматоров по модулю P данного суммируюше

ro блока, первый выход формирователя сигна лов переноса соединен с входом отрицательного переноса следующего суммирующего

1188731

10 блока устройства и вторыми входами элементов И третьих групп всех сумматоров по модулю Р; данного суммирующего блока, второй выход формирователя сигналов переноса соединен с входом нулевого переноса следующего суммирующего блока устройства и с вторыми входами элементов И первых групп всех сумматоров по модулю

Р; данного суммирующего блока, а третий выход соединен с входом положительного переноса следующего суммируюгцего блока устройства и вторыми входами элементов И вторых групп всех сумматоров по модулю Р; данного суммирующего блока, выходы элементов ИЛИ второй группы каждого 1-ro сумматора по модулю Р; соединены с выходом суммы по

j-му основанию системы остаточных классов данного суммирующего блока, выходы отрицательного и положительного переносов и-ro суммирующего блока соединены с первым и вторым входами сумматора по модулю два, третий и четвертый входы кото1

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

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

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

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

Каждый суммирующий блок 1 содержит т сумматоров 3 по модулю Р; (где j= l 2,...

m; m — количество оснований системы остаточных классов (СОК) и формирователь и сигналов переноса. Каждый сумматор по модулю Р; содержит дешифраторы 5 и 6 двоичного кода в код «Один из Р;», матричный сумматор 7 по модулю, группы элементов

И 8 -13 и группы элементов ИЛИ 14 и 15.

Формирователь 4 сигналов переноса содеррого соединены с первым и вторым входами знаков устройства, а выход — с выходом знака устройства.

2. Устройство по п. 1, отличающееся тем, что формирователь сигналов переноса содержит первый и второй дешифраторы кода системы остаточных классов в код

«Один из R» (где R=IXR;), первый и втоj=i рой элементы ИЛИ, первый и второй элементы НЕ и элемент И, причем входы первого и второго дешифратора, с первого по к-й (где к=ХР;), соединены с соответJ=i ствующими входами формирователя сигналов переноса, а выходы подключены соответветственно к входам первого и второго элементов ИЛИ, выходы которых соединены соответственно с первым и третьим выходами формирователя сигналов переноса и с входами первого и второго элементов НЕ, выходы которых соединены с входами элемента И, выход которого подключен к второму выходу формирователя сигналов переноса.

2 жит дешифраторы 16 и 17 кода СОК в код

«Один из R» (где К=ЯР;, элементы ИЛИ

1--1 Р

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

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

И 27 — 30 и элемент ИЛИ 31.

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

В качестве основания избыточной системы счисления можно принять величину: г= R/2 — 4 тогда допустимые значения цифр в данной системе счисления будут

w;: — r/2, — (r/2 — 1),..., — 2 — 1, 0,1,2,..., r/2 — 1, г/2;

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

s;, х;, у,: — (г/2+ 1), — r/2, — (r/2 — 1),..., — 2,— 1,0,1,2,..., r/2 — 1, r/2, г/2+1.

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

1188731

w;=(x;+y;) — rt; I;

S;=W;+ t;, 25

Зо

40 х=! (10 6 8 8

+ х=1 у =0 (2,0,0) (2,2,3) (2,2,3) (1,2,2) (0,2,0) (0,2,0) 55 ь =1

w=1

С учетом введенных обозначений можно записать: где tl =0 при и„„„(х 1- j i(wmax, ti (= 1 при xi+ ji) %так

ti.I= 1 прих;+ gr(wmin

Пример. Выберем систему оснований

СОК Р, =3; Рз=4; Рз=5; К= Р Р Рз

=60; R/2=30; г=26.

Допустимые значения:

w;: 13, 12, П, 10, 9, 8, 7, 6, 5, 4, 3, 2,1, О, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13;

s;, х;, у;: 14, 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, 14;

Пусть слагаемые Х и У ии иих х ссууммма S в

r-ичной системе счисления имеют вид:

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

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

t, затем определяется значение суммы

s=w+t.

В данном устройстве в каждом суммирующем блоке 1 формируются величины (s — 1), s и (s+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). Сигнал

«Нулевой перенос» (О) формируется при отсутствии сигналов (— 1) и (+1).

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

СОК могут быть малоразрядными, выполненными таблично и работающими IIapaëлельно. Отсутствие переноса между отдельными сумматорами по основанию Р, дает возможность выполнить сложение r-ичных чисел 3а один такт. Для представления r-ичных цифр кодам СОК применена искусственная форма, когда в качестве нуля принята величина R/2.

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

+х= R/2+х (х5 О, r/2+ 1), отрицательные r-ичные цифры кодируются в виде: — x= R/2 — х, (— х — (r /2+ 1 ), О) .

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

Пусть исходные операнды в избыточной

r-ичной системе счисления те же, что в рассматриваемом примере, а именно: у = О 8 14 1! 10

Закодируем каждую r-ичную цифру кодом СОК по основаниям Р =З; Рз= — 4;

Рз=5 в искусственной форме и выполним сложение:

3,4,5

3,4,5 3,4,5 3,4,5 (0,0,1) (2,2,3) (1,2,2) (2,0,4) (2,1,1) (2,0,0) ъ =1 (1,2,3) (2,0,0)

R/2=0 (0,2,0) (0,2,0) (1,0,3) (2,0) (1,1,4) (0,0,2)

28 =-2 50 = — +20 49 = — -+! 9 12=- -1 8

1188731

3,4,5

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

w =w+26=1 ь =w= l

w =w — 26=1

D ° D

Э D °

Ф ° °

Результат получен такой же, как и в предыдущем примере.

Причем этот результат сформирован на выходе матричных сумматоров: 7.

Чтобы не производить операцию вычисления константы R/2, имеющую значащую цифру только по четному основанию (в нашем случае < z — — 2), целесообразно сумматор 3 по основанию Р =4 выполнить так, чтобы он вырабатывал результат со смещением на — (R/2)ð, . Конструктивно это выполняется при построении матричного сумматора 7.

Теперь с помощью элементов И групп

8 — 10, на входах которых число w представлено в коде «Один из Р;», получают величины (ю-+r); w; (w — r), что эквивалентно (w+26) ъ и (w — 26), так как единица переноса в старшем разряде эквивалентна величине r=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,3 (2,2,2) (0,0,4) (2,3,3) (1,2,1) Одновременно в каждом r-ичном разряде с помощью формирователя сигналов переноса 4 формируются сигналы переноса, которые поступают на вторые входы элементов И групп 8 — IO соответственно:

1=0) 1 1 1 0

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

r- ичных разрядах суммирующих блоков

1:9, 10, 10, 8. Сумматор 2 по модулю два в знаковом разряде выдает величину 1. На выходе элементов ИЛИ группы 14 число имеет вид:

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

28— = 2 24— = -6 23= -7 ЭЗЙ 8

В соответствии с сигналами переносов, поступающими из младших разрядов (1=0/

1 1 1 9) в старших r-ичных разрядах сумми15 рующих блоков 1 открываются элементы И следующих групп, 13, 13, 11, 12. Через элементы И групп 13 проходит величина (w + 1) через элементы И групп 11 — величина (w" — 1), через элементы И групп 12 — величина %

В результате сумма на выходе устройства имеет вид:

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

S= 1 (2,1,4) (I 0,0 0,2,2) (2,2 3)

29=-1 25=-5 22=-3 38=8, причем На элементах ИЛИ групп 15 r-ичный разряд результата по каждому из оснований представлен двоичным кодом в искусственной форме СОК.

1188731

Ур

Хр

Фиг 2

1188731 а

Редактор Л. Пчелинская

Заказ 6746/51

Составитель А. Степанов

Техред И. Верес Корректор М. Пожо

Тираж 709 Подписное

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

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

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4