Устройство для деления Советский патент 1987 года по МПК G06F7/52 

113

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

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

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

Устройство содержит двадцать один умножитель 1, семнадцать сумматоров 2, тринадцать вычитателей 3, объединенных в треугольную матрицу седьмого порядка, блок 4 преобразования избыточного кода, причем :j-я строка матрицы (2 i 7) имеет 8-j столбцов и содержит в каждом столбце умножитель 1, во втором и в каждом нечетном столбце - сумматор 2, в каждом четном столбце - вычитатель 3, первая строка матрицы имеет семь столбцов и содержит в каждом нечетном столбце вычитатель 3, причем первый вход умножителей 1 k-ro столбца (1 4k 6) соединен с k-м входом группы входов 5 делителя устройства, второй ВХОД умножителей 1 т-го столбца () j-й строки для j 3 соединен с выходом сумматора 2 первого столбца (-1)-й строки и первым входом сумматора 2 второго столбца j-й строки, вторые входы умножителей 1 k-ro столб ца второй строки соединены с выходом вычитателя 3 первого столбца первой строки и с первым входом сумматора 2 второй строки второго столбца, второй вход умножителя 1 первого, стодбца j-й строки для j 3 соединен с выходом сумматора второго столбца (j-l)-й строки, выход умножителя 1 j-й строки и 1-го столбца (, 1 - нечетное) соединен с первым входом сумматора 2 этой же строки и этого же столбца, .второй вход которого для соединен с (1+1)-м входом группы входов 5 делителя устройства, выход умножителя 1 k-ro столбца (k - четное) j-й строки соединен с входом вычитаемого вычитателя 3 этой же строки и этого же столбца,.вход уменьшаемого которого для соединен с выходом вычитате- ля 3 (k+l)-ro столбца первой строки, второй вход сумматора 2 j-гй строки для j / 3 1-го столбца (1 - нечетное) соединен с выходом вычитателя 3 (j

5

5

31

5 О 5 0 5

0

22

-1)-й строки ()-го столбца, вход уменьшаемого вычитателя 3 j-й строки для j / 3 k-ro столбца (k - четное) соединены с выходом сумматора 2 (j- -1)-й строки (k+l)-ro столбца, второй вход сумматора 2 второго столбца га-й строки соединен с вторым входом сумматора 2 первого столбца этой же строки, вход уменьшаемого вычитателя

3первого столбца первой строки соединен с первым входом группы входов 6 делимого устройства, а вход вычитаемого соединен с первым входом группы входо в 5 делителя устройства,вход вычитаемого 3 i-ro столбца (,

i - нечетное) первой строки соединен с i-M входом группы входов 5 делителя устройства, а вxoд.I уменьшаемого - с (i-l)-M и 1--М входами группы входов 6 делимого устройства, выходы вычитателя 3 первого столбца первой строки и сумматоров 2 первого столб- ца j-й строки соединены с соответствующими входами блока А преобразования избыточного кода, выходы которого являются выходами 7-7 устройства. Умножитель 1 содержит элементы И 8, сумматор 2 - одноразрядные двоичные сумматоры 9, вычитатель 3 - одноразрядные двоичные вычитатели 10, блок 4 - преобразователи 11, узел 12 преобразования восьмиразрядного кода в двухразрядный и сумматор 13 с параллельным переносом.

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

Q

Q д а,,я,ч,ЧзЯ4Ч5Ч Ч7

где q ;| i-я избыточная цифра частного ().

Из условия можно найти выражения для определения значений избыточных цифр частного. Для этого необходимо приравнять значения сумм соо ТВ е т ствующих раз рядных пр оиз в еде- НИИ произведе;ния A-Q значениям раз- новесовых разрядов делимого С, представленного следуюш,им образом:

, с, с jc с 7Cj c 2 +c2 +0.2- +(2сз+с 2- +0.(2с5+с, ) +0-2-V(2c,+Cg). 2-«.

В результате получается следующая система уравнений:

а, 40.5 .j ;

а1Ч2- агЧ1 эЧо а1Чз+а ч +азЯ,,

3 44+32q3+a3qj+a q +ajq,0; arqs+a q4+a3q3+a qj+a q,,

2cj+c,.

1Ч6+a,jq +а q + +a,q.0;

aiq +a,.q3+abq + ,q,+ajq,2c,+Cj.

С учетом того, что а, с,, 1, выражения для определения значений избыточных цифр частного Q принимают вид:

q,c,-c,;

q -aj-ajq,;

q 2c5+C4-a -a3q -ajqj; (2)

,; .q 2c5+c -aj-a5q -a q,,jq4; ,j-a qj-a3q -a2q5; q,2c +CB-aj,-a-,q,-a,qj-a5q,-a4q4- -a qy-ajq.

Преобразуем систему уравнений (2), подставив в выражение для q значение q из третьего уравнения, в выражение для q, значение q из четвертого уравнения и т.д. Полученные выражения для избыточных цифр частного q (О ) имеют вид:

% ;

j Cj+c -a -ajq -ajC-aj-a q);

q -a5-a4q,(2c3+C4-a4- ,q); ..j.

qs 2cy+Cj,-afc-afqi-a qi-a3q3- -a C-aj-a q -ajq-j -a qj);

,-a4qi-ayq2-a4q,-a3q4- -ai(2cs+Ct-a4-ajqi-a,qj-a3q,-a2q);

,+Cg-ag-aiq,-abqi-aiq,-a4q4- -a.jqs-a,j(Ta7-a q,-ayq.j -a4qj-a3q - -ajqir).

С учетом того, что а, - двоичная переменная, принимающая значения О или 1,- и произведение , выражения в скобках в правых частях уравнений системы (3) можно упростить Например, выражение а(-а ) в правой части четвертого уравнения можно преобразовать к следующему ви- ду:

,

ajC-aa-a q )-aJaз-a4q,

) V i.(-a3-q, ) .

10

15

, е я

332312 4

Выполнив подобные преобразования в пятом, шестому.седьмом и восьмом уравнениях, получаем следующие . выражения для определения цифр част- 5 ного q . (Oil 7):

Ч,

.jqi ;

qj 2c3+c -a4-a3qi+a2(a3+qi); (4) q -as-a q -ajq -ai(2c3-«-c -a4.-ajq,-q);

aj 2cy+Ct-at-ajqi-a q,-ajq5+

+a2(,j+q);

,-ajq,-a q3-a3q4-a(2cy + +Ct-at-a5q ,-a4q,j-ajq,-q4) ;

,+C8-a8-a-,q,-a(.q,i-asq,-a4q+- -a3q5+a2(a7+a4q,+a5q,;+a4q3+ .).

В устройстве (фиг. 1) избыточные цифры частного формируются в соответствии с приведенной системой уравнений (4). Так, цифра образуется на выходе вычитателя 3 первой строки первого столбца матрицы,вход уменьшаемого которого подключен к первому входу 6 группы входов делимого устройства, на который подается- значение разряда с делимого С, а вход вычитаемого соединен с первым входом 5 группы входов делителя устройства, на который подается значение разряда а. делителя А. Цифра

20

25

30

г

формируется следующим образом. С

помош |Ю умножителя 1 второй строки первого столбца матрицы вычисляется значение , которое далее поступает -на первый вход сумматора 2 этой же строки и этого же столбца,

на второй вход которого подается значение разряда а, делителя А с второго входа 5,j группы входов делителя устройства. Таким образом, на выходе этого сумматора 2 образуется

результат aj+a,, который только знаком отличается от соответствую- щего результата q в системе уравнений (4). Полученное значение -q поступает на соответствующий вход

блока 4 преобразования избыточного кода, где оно с учетом своего знака суммируется с остальными цифрами частного. Цифра q формируется на выходе сумматора 2 третьей строки первого столбца матрицы следующим об- - разом.

С помощью умножителя 1 второго столбца второй строки матрицы вычисляется значение , которое поступает на вход вычитаемого вычитателя 3 этой же строки и этого же столбца, на вход уменьшаемого которого подается значение . с выхода вычитателя 3 первой строки третьего столбца, на входы уменьшаемого которого поданы соответственно значения разрядов Cj и с делимого С с второго и третьего входов 6j и 6 группы . входов делимого устройства, а на вход вычитаемого этого вычитателя подано значение разряда а с третье- 5, группы входов делителя

го входа 2 устройства.

На выходе в.ычитателя 3 второй строки второго столбца формируется результат, равный , который поступает на второй вход сумматора 2 третьей строки первого столбца, на первьй вход которого поступает произведение a() с выхода соответствующего умножителя 1, первый вход которого соединен с первым входом 5 .группы входов делителя устройства, а второй вход - с выходом сумматора 2 второй строки второго столбца матрицы, на первый вход которого поступает значение q с выхода вычитателя 3 первой строки первого столбца, а на второй вход - значение разряда а делителя. А с второго входа 5 группы входов длителя устройства. Таким образом, на вь1ходе сумматора 2 третьей строки первого столбца формируется значение цифры qj 2cj+c -a -a3qi+a(aj+q.,

Цифра q формируется с обратным знаком на выходе сумматора 2 четвертой строки первого столбца матрицы следующим образом. На выходе сумматора 2 второй строки третьего столбца матрицы формируется результат результате сложения значения -разряда а делителя А, поступающего с четвертого входа 5. группы входов делителя устройства, со значением произведения a4q, поступающего с выхода умножителя 1 второй строки третьего столбца матрицы..С выхода соответствуищего сумматора 2 значение подается на вход уменьшаемого вычитателя 3 третьей строки второго столбца матрицы, на вход вычитаемого которого поступает произ ведение с выхода умножителя 1 третьей строки второго столбца матрицы. С выхода соответствующего вычитателя 3 результат , поступает на второй вход сумматора 2

32312

четвертой ступени первого столбца, на первый вход которого подается значение а„ (2Cj+с. ,j) , которое формируется на выходе умножителя I четвертой строки первого столбца матрицы, первый вход которого соединен с первым входом 5 группы входов делителя устройства, а второй вход соединен с выходом сумматора 2 третьей строки второго столбца матрицы, на выходе которого формируется значение 2Cj+c.-a jq -q. Таким образом на выходе сумматора 2 четвертой строки первого столбца формируется значение -q4 a5+a4q,+a3q,+a,(2c,+c -a -ajq которое только знаком отличает10

15

20

25

30

35

40

-q),

ся от значения q в системе уравнений (4).

Подобным образом в устройстве вычисляются и значения остальных избыточных цифр частного q, q и q,. Следует отметить, что цифры q, q., q вычисляются с противоположным знаком, однако это учитывается в блоке 4 преобразования избыточного кода при преобразовании частного из избыточной формы в обычную. Значение цифры q частного всегда равно единице, поэтому она явно в устройстве не формируется. Однако ее значение учитывается в блоке 4 преобразования избыточного кода при формировании окончательного значения частного в простом двоичном

коде ,, зЧ+ч Нт выходах 7i-7g устройства.

В таблице приведены максимально и минимально возможные значения из- быточных цифр частного Q для предлагаемого устройства.

Максимальное и минимальное значения избы- .g точных цифр

Избыточные цифры частного

1 1 4 3 7 8 13 -1 -1 -2 -5 -5 -9 -13

50

55

Следует отметить, что если разрядность делимого и делителя, nocTynaJO- щих на входы устройства, нечетная (например, ), то в этом .случае делимо.е С в предлагаемом устройстве представляется следующим образом:

Й°

С.,С,

с,с,с,2

Г1

+ c,rt

+0 2 +(2с J+C4 ) 2-5+(2c5-+c-J-2 +

+с.

71

Это влияет на выражение для определения последней цифры частного q , которое, в отличие от .приведенного вьше выражения для случая четной разрядности операндов, имеет вид:

,-aT-a q -a5.q,,-a3q+- -aj (2cj + c -a -aj-q -a4q4-a3q3-q 4)

Рассмотрим реализацию узлов уст- ройства на примере умножителя 1 и сумматора 2 четвертой строки первого столбца, вычитателя 3 первой строки третьего столбца и блока 4 преобразовани я избыточного кода (дру гие узлы устройства могут быть разработаны аналогичным образом). Здесь и в дальнейшем для определенности предполагается, что избыточные цифры частного представляются в двоичном дополнительном коде. Они могут быть представлены в обратйом, или же в прямом коде. При этом несколько изменится реализация узлов устройства,

Умножитель 1 предназначен для формирования произведения а (2cJ+ ) , которое, как следует из третьего уравнения системы уравнений-(2), численно равно значению произведений- третьей цифры

частного q. и разряда делителя а , А так как и q -2 ( но таблице), то умножитель 1 может быть реализован на четырех двухвхо- довых элементах И (фиг. 2), Элемент И 8, участвует в формировании знака этого произведения.

Сумматор 2 осуществляет алгебраическое с-уммирование результатов, сформированных на выходах умножителя 1 четвертой строки первого столбца и вычитателя 3 третьей строки второго столбца. На выходе сумматора 2 образуется значение (-q4). которое по модулю не превышает значение пятерки (согласно таблице). Этот сумматор может быть реализован на четырех одноразрядных двоичных сумматорах 9 -9 , из которых первый знаковый (фиг. 3),

С помощью вычитателя 3 осуществляется вычисление разности 2с,,+С4-а Его функциональная схема включает два одноразрядных двоичных вычитателя 10 и 10, (фиг. А ), Выход заема вычитателя 10 является знаковым разрядом получаемой разности.

Блок 4 предназначен для преобразования частного, представленного в

5

0

0

5

виде набора избыточных цифр q-. (Ofi 7), в простой двоичный код с учетом

того, что ЦИфpЫ.q Ч q В уСТрОЙстве формируются с противоположными знаками. Упрощенная структурная схема блока 4 преобразования избыточного кода имеет вид, приведенный на фиг, 5, Он содержит преобразователи Ц, осуществляющие изменение знака избыточных цифр -qj, .Ч.4 4t. узел 12 преобразования восьмиряд- ного кода в двухрядный и сумматор 13 с параллельным переносом,. Преобразователи 11,-1Ц фактически выполняют функции образования дополнительного кода. Однако с целью повышения быстродействия в предлагаемом устройстве предполагается, что преобразователи формируют обратный код, а преобразование его в дополнительный производится в узле 12 путем подачи единичных входных переносов на входы переносов соответствующих сумматоров узла 12, Узел 12 выполняет функции узла многовходового алгебраического суммирования. Таким образом, на выходе сумматора 13 формируется значение частного Q в простом двоичном коде.

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

На входы и 5,-5 одновременно подаются значения семи младших разрядов соответственно делимого , с, с , Cg и делителя , а,а 3 (значения старших разрядов делимого С, 1 и делителя непосредственно не участвзтот в формировании цифр частного и на входы устройства не поступают), Далее последовательно во времени с помощью умножителей 1, сумматоров 2, вычита- телей 3 формируются значения семи избыточных цифр результата q, -qj

Чз s fe 1 соответствии с уравнениями системы (4) (сначала формируется значение цифры q ,, потом .-q,., и т,д,). Считая, что , значение цифры q сформируется от момента поступления на входы 6.-6 и , устройства соответственно делимого и делителя через, время, примерно равное ., По мере формирования значений всех избыточных цифр частного они поступают на соответствующие входы блока 4 преобразования: избыточного кода, в котором осуществляется их алгебраическое суммирование, и на выходах 7, -7 устройства формируется результат Q

q,, простом двоичном коде. Общее время формирования результата в устройстве равно 4t+ + 7tc-i-t,,p.

Следует отметить, что одновременно с формированием в устройстве более младших избыточных цифр результата более старшие избыточные цифры поступают в блок 4, где происходит их предва рительная обработка. Этим обеспечивается некоторое перекрытие во времени работы блока 4 преобразо- .вания избыточного кода с работой других узлов устройства, В общем случае (для четных значений р) время формирования результата в предлагаемом устройстве примерно равно

Т (p-l)tc+(p/2)t:,, + t

пр

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

Устройство для деления, содержащее (п-2)(п-1)/2 умножителей, п/2 ((п+ +1)/2, если п - нечетное) вычитате- лей и (п +2п-12)/4((п +2п-11)/4, если п - нечетное) сумматоров, объедиI ненных в треугольную матрицу порядка (п - разрядность делимого и

делителя), блок преобразования избыточного кода, причем j-я строка матрицы () имеет n-j столбцов и содержит в каждом столбце умножитель во втором и в каждом нечетном столбце - сумматор, а первая строка матрицы имеет (п-1)-й столбец и содержит в каждом нечетном и в (п-1)-м столбце (если п - нечетное) вычитатель.

го - с первым входом группы входов делителя устройства, вход вычитаемого вычитателя первой строки i-ro столбца (, L - нечетное) соединен с i-M входом группы входов делителя устройства, а входы уменьшаемого - с (i-l)-M и i-M входами группы входов делимого устройства, входы вычитаемого и уменьшаемого вычитателя (n-l)-ro столбца первой строки (если п - нечетное) соединены соответственно с (п-1)-м входом группы входов делимого и (п-1)-м входом группы входов делителя устройства, а его выход соединен с вторым входом сумматора второй строки (п-2)-го- столбца, выхода: сумматоров первого столбца нечетных строк и вычитателя первой строки первого столбца соединены с соатветствующими входами блока преобразования избыточного кода, выходы которого являются выходами устройства, отличающееся тем, 4fo, с целью повьш1ения быстродействия, устройство содержит в k-м столбце (k - четном) т-й стро1си матрицы ()-й вычитатель, вход вычитаемого которого соединен с выходом .умножителя этого же столбца и этой же строки, а вход уменьшаемого для m 7/ 3 соединен с выходом сумматора (т-1)-й строки (k+-l)-ro столбца, вход уменьшаемого вычитателя второй строки и k-ro столбца (k - четное) 35 соединен с выходом вычитателя (k+ +1)-го столбца первой строки, выход вычитателя га-й строки и k-ro столбца (k - четное) соединен с вторым входом сумматора (т+1)-й строки (k-l)-ro

25

30

причем вход умножителей k-ro столбца 0 столбца, первый вход сумматора ш-й () соединен с -k-M входом груп- строки второго столбца для m 3 соединен с выходом сумматора первого столбца (т-1)-й строки и с вторыми входами умножителей четных столбцов

пы входов делителя устройства, выход умножителя j-й строки и 1-го столбца (), 1-- нечетное) соединен с

первым входом сумматор.а этой же стро-45 т-й строки, второй вход этого же Сумки и этого же столбца, второй вход матора соединен с выходом вычитателя которого для соединен с (1+1)-м (т-1)-й строки этого же столбца, а

входом группы входов делителя устройства, вторые входы умножителей j-й строки для J7/3 и 1-го столбца для /3 (1 - нечетное) соединены с выходом сумматора первого столбца (-1)-й строки, вторые входы умножителей второй строки и столбда (k - нечет- -ное) соединены с выходом вычитателя первой строки первого столбца, вход у1ченьгааемого которого соединен с первым входом группы входов делимого -устройства, а вход вычитаемо10

15

33231210

го - с первым входом группы входов делителя устройства, вход вычитаемого вычитателя первой строки i-ro столбца (, L - нечетное) соединен с i-M входом группы входов делителя устройства, а входы уменьшаемого - с (i-l)-M и i-M входами группы входов делимого устройства, входы вычитаемого и уменьшаемого вычитателя (n-l)-ro столбца первой строки (если п - нечетное) соединены соответственно с (п-1)-м входом группы входов делимого и (п-1)-м входом группы входов делителя устройства, а его выход соединен с вторым входом сумматора второй строки (п-2)-го- столбца, выхода: сумматоров первого столбца нечетных строк и вычитателя первой строки первого столбца соединены с соатветствующими входами блока преобразования избыточного кода, выходы которого являются выходами устройства, отличающееся тем, 4fo, с целью повьш1ения быстродействия, устройство содержит в k-м столбце (k - четном) т-й стро1си матрицы ()-й вычитатель, вход вычитаемого которого соединен с выходом .умножителя этого же столбца и этой же строки, а вход уменьшаемого для m 7/ 3 соединен с выходом сумматора (т-1)-й строки (k+-l)-ro столбца, вход уменьшаемого вычитателя второй строки и k-ro столбца (k - четное) 35 соединен с выходом вычитателя (k+ +1)-го столбца первой строки, выход вычитателя га-й строки и k-ro столбца (k - четное) соединен с вторым входом сумматора (т+1)-й строки (k-l)-ro

20

25

30

. выход этого сумматора соединен с вторым входом умножителя (т+1)-й строки

50 первого столбца, первьтй вход сумматора второй строки второго столбца соединен с выходом вычитателя первой строки и первого столбца и вторыми входами умножителей четных столбцов

55 второй строки, второй вход этого сумматора соединен с вторым входом группы входов делителя устройства, а его выход соединен с вторым входом умножителя первого столбца третьей стро11133231212

ки, выходы сумматоров четных строк ветствующими входами блока преобра- первого столбца соединены с соот- зования избыточного кода.

51 5

52 2 4 5 5f 5б 6f 5 5

г;

7,

«;.

Изобретение относится к вычислительной технике и может быть использовано для быстрого вычисления частного двух чисел. Целью изобретения является повьш1ение быстродействия устройства. Цель достигается за счет того, что устройство содержит в k-M столбце (k - четное) т-й строки матрицы (2im n-2) вычита- тель, вход вычитаемого которого соединен с выходом умножителя этого же столбца и этой же строки, а вход уменьшаемого для m 3 соединен с выходом сумматора (т-1)-й строки (k+ +1)-го столбца, вход уменьшаемого вычитателя второй строки и k-ro столбца (k - четное) соединен с выходом вычитателя (k+l)-ro столбца первой строки, выход вычитателя т-й строки и k-ro столбца (k - четное) соединен с вторым входом сумматора (т+1)-й строки (k-l)-ro столбца,первый вход сумматора т-й строки второго столбца для m 3 соединен с выходом- сумматора первого столбца (ш- -1)-й строки и с вторыми входами умножителей четных столбцов т-й строки, второй вход этого же сумматора соединен с выходом вычитателя (т-1)-й строки этого же столбца, а выход этого сумматора соединен с вторым входом умножителя (т+1)-й строки первого столбца, первый вход сумматора второй строки второго столбца соединен с выходом вычитателя первой строки первого столбца и вторыми входами умножителей четных столбцов второй строки, второй вход этого сумматора соединен с вторым входом группы входов делителя устройства, а его выход соединен с вторым входом умножителя первого столбца тр етьей, строки, выходы сумматоров четных строк первого столбца соединены с соответствующими входами блока преобразования избыточного кода. 5 ил, 1 табл. i (Л СР 00 ю со 1С

J

-39

f (tf

Фи.д CifO

10i

Фиг.

iO И

a о5з

7/ 7г 7з Ъ Is 7б l .7д Фие,5

Составитель А.Клюев Редактор Е.Папп Техред И.Попович

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

ВНИИПИ Государствениого -комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная 4

Корректор Е.Рошко.