Устройство для деления

 

Изобретение относится к области вычислительной техники и может быть использовано для быстрого выполнения операции деления. Изобретение позволяет существенно повысить быстродействие известного устройства за счет того, что в него дополнительно введены два блока суммирования, блок формирования произведений и блок инверсии , что обеспечивает (в совокупности с известными блоками, старыми и новьЕми связями) одновременность начала формирования всех избыточных цифр частного и преобразования его в двоичную форму в процессе вычисления его избыточных цифр. Избыточные цифры частного определяются из условия равенства значений сумм соответствующих разрядов произведения делителя и частного равновесовым разрядам делимого . 5 ил. с S (Л

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

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

РЕСПУБЛИК (51)4 G 06 F 7/52

ВС1ХОН)30 4 и

13,",", Ц

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Н А 8ТОРСНОМУ СВИДЕТЕЛЬСТВУ (2 1) 3905807/24-24 (22) 03. 06. 85 (46) 23.02.87 Бюл. У 7 (71) Минский радиотехнический институт (72) А.И.Нозик и А.А.Шостак (53) 681.325(088.8) (56) Stefanelli Р. A; suggestion for а high — speed parallel binary divider — IREE Trans, Comput, 1972, v. 21, Ф 1, р. 42-55, f ig, 2. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ (57) Изобретение относится к области вычислительной техники и может быть использовано для быстрого выполнения операции деления. Изобретение позво„„SU„„1291971 А 1 ляет существенно повысить быстродействие известного устройства за счет того, что в него дополнительно введены два блока суммирования, блок формирования произведений и блок инверсии, что обеспечивает (в совокупности с известными блоками, старыми и новыми связями) одновременность начала формирования всех избыточных цифр частного и преобразования его в двоичную форму в процессе вычисления его избыточных цифр. Избыточные цифры частного определяются из условия равенства значений сумм соответствующих разрядов произведения делителя и частнбго равновесовым разрядам дели- Я мого ° 5 ил.

1291971

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

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

На фиг. 1 приведена структурная схема устройства для деления, на фиг.2 функциональная схема блока формирования частичных произведений; на фиг.3-5 — функциональные схемы соответственно второго, третьего и первого блоков. суммирования (для случая, когда n=P=6, где P — число избыточных цифр частного, n — разрядность one15 рандов).

Устройство содержит блок 1 формирования частичных произведений, второй блок 2 суммирования, третий блок 3 суммирования, группу элементов

НЕ 4 и первый блок 5 суммирования, входы 6 делителя устройства, вход 6

1 < 2 делимого устройства, выход 7 устройства.

Блок 1 формирования произведений

l (фиг.2) содержит семнадцать элементов И 8< -8„, выходы 9„-9„блока 1.

Второй блок 2 суммирования (фиг.3) содержит шесть сумматоров 10, -10,, выходы 11 -11 блока 2 в двух-

6 рядном коде.

Третий блок 3 суммирования (фиг. 4) содержит двенадцать сумматоров

12< - I 2„, выходы 13< -13„35 двухрядном коде.

Первый блок 5 суммирования (фиг.5) содержит десять сумматоров 14< -14, и сумматор 15 с параллельным переносом, выходы которого являются и выходами 7 устройства.

Идея, положенная в основу устройства для деления, заключается в следующем. Пусть делимое и делитель — нормализованные шестираэрядные положительные двоичные дроби соответственно С=О, С, С СЗС,С,С и а а а а а а а значение их частно l 3 4 3 6

ro Q представляется в виде

С

А о где q — - i-ая избыточная цифра частного (О c i - 5).

Из условия А Q=0 можно найти выражения для определения значений избыточных цифр частного. Для этого необходимо приравнять значения сумм соотнетстнуюших разрядных нроизвелений произведения А- значениям ранновесовык раэрядон делимого С.

В результате получим следующую систему уравнений: а, qî=-С1 а q +a q =с а а q +a q +а 1 =с

3 а< q +а q +a q +a q =с, (1) а q +а q +а q +а q +а q =с

3 3 2 4 1 а о 3 а1q +а2q4+аэq +а q +a q +а,q.= á

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

q =1 а

q =с -а,,с1, q =с. -à q, -à q, (2)

Преобразуем систему уравненйй (2) подставляем в выражение для q значе1 ние q, из первого уравнения. Получен- .ное выражение для q,вместе со значением q. из первого уравнения подставляем в третье уравнение в выражение для q ; полученное в:результате этого выражение для q вместе с ранее полученными выражениями для q u q.подставляем в выражение для q, полученное в результате этого выражение для q, вместе с выражениями для и„

q u q подставляем н выражение для

1 а и т.д. В результате получаем сле4 дующие выражения для избыточных цифр частного q„. (О.c i 5):

q =1

<1 =с -а

q, =с -а -а с +а

3 3 2 2 2 (3)

3 4

2 4

5 l 4

Полученные выражения (3) для избыточных цифр частного q (О ci c 5)

1 подставляем в выражение для частного Q

-1 -2 q2 q34,q <,q3 < 2 +q 2 +q22 +

-3 Ч32 +q,2 +q 2 = 1 2 +(с -a,) 2 +

-(с -a -а с +а ) 2 +(с -a -а с +

3 3 2 2- 2 4 4 3

+2а а, -а с +а с -а ) 2 +(с -а -а с +

3 3 2 2- 3 5 4

+2а2а -аЗсз- а 3+2азаяс2-Заза2-аасл+

+а с. +а2-а,с2) 2 +(с,.-ад-а с +2а2а31291971

-а с +2а а +2а а с -3 а а -а с +а с +

3 3 4 24 2 2 4 34 3 2

+2аза2сз — За а с — а2с +аза2+а с -а, сз—

-а +а с ) 2 3 (4):

Преобразуем полученное выражение 5 (4) для частного Q, сгруппировав отдельно положительные члены и отдельно отрицательные члены, в результате чего получаем следующее выражение:

10 ! -2 -3

Q=f1+c 2 +(с +а )2 +(с,+2аза +а c) 2+

+(с,+2а2a„+aз 2а за 2с +а сз +а2 ) 2 +

+(с,+2а2а +2аза +2 а2а с +a с +

2 3 3 4 2 4 2 3 2

+2а а с +а а +а са+а с ) 23) — (а.2 +

+(а +а2с2) 2 +(а,+азс2+а с +а2) 2 +

3 3 3 2 2 4 2

+(а+ас+а с+За а+а с+а с ) 2+

+(с З.а,с +а с +За à +a с +За а с +

3 i 4 3 2 а 3 а 3 2

+а2с5+а2сз+а ) 2 (5)

Слагаемые в круглых скобках, которые входят в полученное выражение (5) с коэффициентами, отличными от единицы, группируем со слагаемыми с другим весом. Например, положительное слагаемое 2 а а, входящее в вы-з 25 ражение для частного с весом 2

43 — 2 учитывая что 2 аза 2 = а а 2, груп3 2 пируем с положительными слагаемыми с весом 2, исключив его их числа

-3 слагаемых с весом 2 . Аналогично отрицательное слагаемое — 3 а а с веЗ 2 сом 2 4 заменяем двумя отрицательными

-3 4 слагаемыми — а а с весами 2 и 2

3 соответственно. Выполнив подобные преобразования со всеми остальными положительными и отрицательными сла- 35 гаемыми с коэффициентами, отличными от единицы, получаем следующее выражение для частного Q: !

Q= (1+c2 2 + (cç+a2+a3 a2 ) 2 + (c4 +a2 с +4@

+а, а„+а3 а2 с, ) 2= +(с, +а3+а2 c3+a2+

+а2 a3+a3 a„+a2 а4 с2 +аз а2 сз ) 2 + (с +

+a3 c2+a3 a2+a2 с +а2 с2 ) 2 1 -(а 2 +

2 45

+(а, +а, с, ) 2 + (g+a3 c2+a2 c3+a2+ (6)

+а а,) 2 +(a,+а„с +a с +а а +а с +

+а,с,+а,а„+а,а с,) 2 +(а +азс + чсз+

Полученное выражение (6) преобразуем с целью уменьшения в нем общего числа слагаемых путем суммироваHHH одинаковых слагаемых с разными 55 знаками и весами. Например, слагаемые а, входят в выражение для частного Q с положительным знаком и весами 2 и 2 и отрицательным

2 4 знаком и весами 2",2 3,2 . Учитывая, что а 2 +а 2 -а -а 2 -а 2 = а (2 +2

-2 4 >1 -3 -S 2,-4

-2 -2 -23)=a (-2 -2 -2 )=a (-2 2 +

+2 )=а 2 -а 2 -а 2

2 2 из выражения (6) для частного Ц можно исключить слагаемые а с положительным знаком и весами 2 и 2 " и отрицательным знаком и весами 2 и 2 и ввести в него это же слагаемое с

-3 положительным знаком и весом 2

-2 и отрицательным знаком и весом 2

Это уменьшает число разновесовых слагаемых а, с пяти до трех.Аналогично можно исключить, например, слагаемые а с, входящие в выражение (6) для частного с положительным

-3 знаком и весами 2 и 2 и с отрица-2 -4 тельным знаком и весами 2 и 2 из этого выражения и ввести в него слагаемые а с 2 с отрицательным зна-3 -3 ком и весами 2 и 2, что уменьшает число разновесовых слагаемых а, с, с четырех до двух. Проведя подобные преобразования со всеми Остальными слагаемыми выражения (6) для част— ного Q, получаем

-з .Я=(1+с 22 +с32 +с, 2 +(сз+а2аз+ азаа+

+а,a„c +а а с +а,а ) 2 +(с +а а,с +

3 -2

+а, а, +а2+аза2) 2 )- (а22 +(а, +аз+а,+

-З -3

+а,c,) 2 +(а +a, с + а,сз+ аз+а,c +

+азс2) 2 +(а, +азс2+азс2+а,сз+а2са"

I

В предлагаемом устройстве частное формируется в соответствии с выражением (7).

Рассмотрим .работу устройства на примере деления в нем 6-разрядных двоичных нормализованных чисел.

В этом случае на входы 6 устройства подаются значения разрядов С 2,С3, ro С и делителя А соответственно (значения разрядов а, и С, равны единице и на входы устройства не поступают). По значениям разрядов делимого и делителя в блоке 1 формируются в соответствии с выражением (7) произведения. Произведения, которые входят в выражение (7) с положительным знаком, подаются с выходов блока 1 на входы второй группы второго блока 2 суммирования, а произведения, которые входят в выражение (7) с отрицательным знаком, поступают

12919/1 с выходов блока 1. на входы второй группы третьего блока 3 суммирования.

На входы первой группы блоков 2 и 3 поступают значения определенных разрядов делимого и делителя, которые являются соответственно положительными и отрицательными слагаемыми в выражении (7). Блоки 2 и 3 работают, по возможности, параллельно, после чего сформированные на их выходах 10 значения сумм поступают на входы соответственно второй и третьей групп первого блока 5 суммирования. Значение суммы, сформированной на выходах блока 2, подается непосредственно i 15 на входы второй группы первого блока 5 суммирования, в то время как значение суммы блока 3 поступает на входы третьей группы блока 5 через группу элементов НЕ 4. Этим самым 20 осуществляется образование обратного кода от значения этой суммы. Получение же дополнительного кода этой суммы производится в первом блоке 5 суммирования путем подачи единичных сигналов на соответствующие входы его суммирующих элементов, На первую группу входов блока 5 подаются значения тех разрядов операндов, которые, являясь положительными слагаемыми 30 в выражении (7), непосредственно не участвуют в суммировании во втором блоке 2 суммирования. После завершения переходных процессов в блоках

1-5 устройства не выходах первого блока 5 суммирования формируется частное в простой двоичной форме q, q, I

q q q которое далее и поступа з ет на выходы 7 устройства.

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

Устройство для деления, содержащее первый блок суммирования, выходы которого являются выходами устройст- 45 ва, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия,в него введены второй блок суммирования, содержащий шесть сумматоров, третий блок суммирования, содержащий двенад- 50 цать сумматоров, блок формирования частичных произведений, содержащий семнадцать элементов И, группу элементов НЕ, первый блок суммирования содержит десять сумматоров и сумматор с параллельным переносом, причем входы второго третьего, четвертого, пятого и шестого разрядов делимого и делителя являются входами делимогo и делителя устрс йства соответственно, вход второго разряда делителя устройства соединен с первыми входами первого, второго, третьего, четвертого, пятого, шестого, седьмого, восьмого, девятого и десятого элементов И блока формирования частичных произведений, первым входом первого сумматора второго блока суммирования и первым входом первого сумматора третьего блока суммирования, вхоц третьего разряда делителя устройства соединен с первыми входами одиннадцатого, двенадцатого, тринадцатого и четырнадцатого элементов И, с вторыми входами третьего, четвертого и шестого элементов И блока формирования частичных произведений, с вторым входом первого и первым вхоцом второго сумматоров третьего блока суммирования, вход четвертого разряда делителя устройства соединен с первыми входами пятнадцатого и шестнадцатого элементов И с вторыми входами второго, пятого и одиннадцатого элементов И блока формирования частичных произведений, и с входом переноса первого сумматора третьего блока суммирова ° ния, вход пятого разряда делителя устройства соединен с первым входом семнадцатого элемента И, с вторым входом первого элемента И блока формирования частичных произведений, и с вторым входом второго сумматора третьего блока суммирования, вход второго разряда делимого устройства соединен с вторыми входами седьмого, тринадцатого, пятнадцатого и семнадцатого элементов И, с третьими входами второго и шестого элементов И блока формирования частичных произведений и с первым входом первого сумматора первого блока суммирования, вход третьего разряда делимого устройства соединен с вторыми входами восьмого, двенадцатого и шестнадцатого элементов И, третьим входом третьего элемента И блока формирования частичных произведений и первым входом второго сумматора первого блока суммирования, вход четвертого разряда делимого устройства соединен с вторыми входами девятого и четырнадцатого элементов И блока формирования частичных произведений и первым входом второго сумматора второго блока суммирования, вход пятого разряда делимого устройства соединен

1291971 с вторым входом десятого элемента И блока формирования частичных произведений и первым входом третьего сумматора второго блока суммирования, вход шестого разряда делителя устрой- 5 ства соединен с входом переноса третьего сумматора третьего блока суммирования, вход шестого разряда делимого устройства соединен с входом пе О реноса первого сумматора второго блока суммирования, выход первого элемента И блока формирования частичных произведений соединен с вторым входом третьего сумматора второго блока сум5 мирования, выходы одиннадцатого и шес. того элементов И блока формирования частичных произведений соединены с входами переноса третьего и четвертого сумматоров соответственно второго блока суммирования, выходы второго и третьего элементов И блока фор мирования частичных произведений соединены с первым и вторым входами соответственно пятого сумматора второго блока суммирования, выход четвертого элемента И блока формирования частичных произведений соединен с входом переноса пятого сумматора и первым входом четвертого сумматора второго блока суммирования, выход пятого элемента И блока формирования частичных произведений соединен с вторым входом четвертого сумматора второго блока суммирования, выход двенадцатого элемента И блока формирования.частичных произведений соединен с первым входом четвертого сумматора третьего блока суммирования, второй вход которого соединен с первым входом пятого сумматора третьего блока суммирования, и выходом тринадцатого элемента И блока формирования частичных произведений, выход восьмого элемента И блока формирова- 4. ния частичных произведений соединен с входом переноса четвертого и вто1 рым входом пятого сумматоров третье го блока суммирования, выходы семнадцатого и шестнадцатого элементов И блока формирования частичных произведений соединены с первым и вторым входами соответственно шестого сумматора третьего блока суммирования, выход седьмого элемента И блока формирования частичных произведений соединен с первым входом седьмого и входом переноса пятого сумматоров третьего блока суммирования, выход пятнадцатого элемента И блока формирования частичных произведений соединен с входом переноса второго сумматора третьего блока суммирования, выходы девятого и четырнадцатого элементов И блока формирования частичных произведений соединены с входами переноса соответственно шестого и восьмого сумматоров третьего блока суммирования, выход девятого элемента И блока формирования частичных произведений соединен с первым входом третьего сумматора третьего блока суммирования, выходы переноса третьего и пятого сумматоров второго блока суммирования соединены с вторым входом и входом переноса соответственно второго блока суммирования, выходы сум,мы третьего и пятого сумматоров второго блока суммирования соединены с первым и вторым входами соответ,ственно шестого сумматора второго блока суммирования, выходы переноса и суммы четвертого сумматора второго блока суммирования соединены соответственно с входом переноса и вторым входом соответственно шестого и первого сумматоров второго блока суммирования, выход переноса сумматора второго блока суммирования соединен с вторым входом второго сумматора первого блока суммирования, выходы суммы второго и переноса шестого сумматоров второго блока суммирования соединены с первым и вторым входами соответственно третьего сумматора первого блока суммирования, выходы суммы шестого и первого сумматоров второго блока суммирования соединены с первыми входами четвертого и пятого сумматоров соответственно первого блока суммирования, выход переноса первого сумматора второго блока суммирования соединен с вторым входом четвертого сумматора первого блока суммирования, выход переноса и первый вход первого сумматора третьего блока суммирования соединены с первым и вторым входами соответственно цевятого сумматора третьего блока суммирования, выходы суммы второго и четвертого сумматоров соединены с первым и вторым входами соответственно десятого сумматора третьего блока суммирования, выходы -суммы пятого и шестого сумматоров соединены . с первым и вторым входами соответ) 29) 97) ) (2 ственно восьмого сумматора третьего блока суммирования, выходы переноса второго и пятого сумматоров соединены с входами переноса соответственно седьмого и десятого сумматоров 5 третьего блока суммирования, выходы переноса четвертого и шестого сумматоров соединены с первыми входами одиннадцатого и двенадцатого сумматоров соответственно третьего блока

10 суммирования, выходы суммы первого и восьмого сумматоров соединены с вторыми входами седьмогс) и третьего сумматоров соответственно третьего блока суммирования, выходы переноса седьмого, десятого и восьмого сумматоро соединены с входами переноса соответственно девятого, одиннадцатого и двенадцатого сумматеров третьего блока суммирования, выходы суммы

20 седьмого и десятого сумматоров сое динены с вторыми входами соответственно одиннадцатого и двенадцатого сумматоров третьего блока суммирования, выходы суммы и переноса девятого, одиннадцатого, двенадцатого и третьего сумматоров соединены с входами элементов НЕ группы, выход первого элемента НЕ группы соединен с вторым входом первого сумматора первого блока суммирования, вход переноса первого сумматора соединен с первым входом шестого сумматора первого блока суммирования и с шиной логического нуля устройства, второй вход шестого сумматора соединен с первым входом седьмого сумматора, с входом переноса пятого сумматора, первым входом четвертого разряда сумматора с параллельным переносом первого блока суммирования и с шиной логической единицы устройства, выходы переноса первого, второго, третьего четвертого и пятого сумматоров соеди45 нены с входами переноса шестого, седьмого, восьмого, девятого и десятого сумматоров соответственно первого блока суммирования, выходы суммы первого, второго, третьего и четвертого сумматоров соединены с вторым входом седьмого и с первыми входами восьмо— го, девятого и десятого сумматоров соответственно первого блока суммирования, выход второго элемента HE группы соединен с входом переноса второго сумматора первого блока суммирования, выход третьего элемента

HE группы соединен с вторым входом восьмого сумматора первого блока суммирования, выходы четвертого и пятого элементов HF группы соединены с входом переноса третьего и вторым входом девятого сумматоров соответственно первого блока суммирования, выходы шестого и седьмого элементов

НЕ группы соединены с входом переноса четвертого и вторым входом десятого сумматоров соответственно первого блока суммирования, выход восьмого элемента НЕ группы соединен с вторым входом пятого сумматора первого блока суммирования, выходы

1 суммы шестого, седьмого, восьмого и девятого сумматоров соединены с первыми входами нулевого, первого, второго и третьего разрядов сумматора с параллельным переносом первого блока суммирования, выходы переноса седьмого, восьмого, девятого и десятого сумматоров соединены с вторыми входами нулевого, первого, второго, третьего и четвертого разрядов сумматора с параллельным переносом первого блока суммирования, выход суммы десятого сумматора соединен с вторым входом четвертого разряда сумматора с параллельным переносом первого олока суммирования, выход суМматора с параллельным переносом первого блока суммирования является выходом первого блока суммирования.

l 29I 971

) 29) 97) Составитель Н-.Маркелова

Редактор Н.Лазаренко. Техред В.Кадар Корректор С.Черни

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

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

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

Заказ 265/47

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