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

 

1. УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЫХ ЧИСЕЛ, содержащее регист PW делимого, делителя и частного сумматора, блок анализа и блок управления , причем выходы разрядов регистра частного соединены с выходами устройства, входы-устройства, соединены с информационными входами разрядов регистра делителя, выходы, разрядов регистров делимого и делителя соединены с информационными : входами разрядов сумматора, выходы сумматора соединены с информационными входами регистра делимого, выходы прямого и инверсного значений старших .разрядов регистра делимого соединены со входами блока анализа, выходы которого подключены ко входам блока управления, первый выход которого соединен со входами управления сдвигом регистров делимого и мастного, второй и третий выходы блока управления подключены ко входам управления выдачей соо ветственно дополнительного и прямого кодов регистра делителя, четвертый выход блока управления соединен со входом управления приемом информации регистра делимого, о т л и Ча ю щ е ,е с я тем, что, с целью упрощения с тройства, пятый выход блока управления соединен со входом установки знакового разряда регистра делителя, выход старшего разряда регистра делимого подключен ко входу младшего разряда регистра частного . 2. Устройство по п. 1, отличающееся тем, что блок управления содержит генератор импульсов , счетчик,.элементы И, ИЛИ, дешифратор нуля, распределители импульсов и коммутатор, причем выход генератора импульсов подключен ко входу О) первого распределителя импульсов, первый выход которого соединен с пя-. тым выходом блока, а второй выходс первым входрм первого элемента ИЛИ, выход которого соединён с информационным входом коммутатора, управляющий вход которого подключен к первому входу блока, а первый выходко входу второго распределителя импульсов , первый выход которого подключен к первым входам пе.рвого и второго элементов И, вторые входы которых соединены со вторым и третьим входами блока соответственно, а выходы являются вторым и третьим выходами блока соответственно, второй выход второго распределителя импульсов соединен с четвертым выходом блока, а третий выход - с первым входом второго элемента ИЛИ| второй вход которого подключен ко второму выходу коммутатора, а выход - к входу третьего распределителя импульсов, первый выход которого соединен со

2 А

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

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

РЕСПУБЛИН (19) (11) 006 Р 7Л2

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

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

° Г

ОПИСАНИЕ ИЗОБРЕТЕНИЯ . К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3211191/18-24 (22) 15. 08.80 (46) 15. 10.83. Бюл. 38 (72). Б.А.Баклан (53) 681,325.5(088.8) (56) 1. Карцев И.А. Арифметика цифровых машин, Н ., "Наука", 1969, с. 498-500.

2.Клямко Э.И.,Монахов Г.Д. Метод ускоренного двоичного деления в циф-. ровых вычислительных машинах.

"Приборостроение",.1957, 2, / с. 9-11 (прототип). (5") (57) 1. УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ

ДВОИЧНЫХ ЧИСЕЛ, содержащее регист- рь| делимого, делителя и частного сумматора блок анализа и блок управления, причем выходы разрядов регистра частного соединены с выходами устройства, входы устройства, сое-. динены с информационными входами разрядов регистра делителя, выходы, разрядов регистров делимого и дели.теля соединены с информационными входами разрядов сумматора, выходы сумматора соединены с информационными входами регистра делимого, выходы прямого и инверсного значений старших.разрядов регистра делимого соединены со входами блока анализа, выходы которого подключены ко входам блока управления, первый выход ко-. торого соединен со входами управления сдвигом регистров делимого и частного, второй и третий выходы блока управления подключены ко вхо дам управления выдачей соответственно дополнительного и прямого кодов регистра делителя, четвертый выход блока управления соединен со входом управления приемом информации регистра делимого, о т л и ч а " ющ е е с я тем, что, с целью упрощения устройства, пятый выход блока управления соединен со входом установки знакового разряда регистра делителя, выход старшего разряда регистра делимого подключен ко вхо" ду младшего разряда регистра частного.

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

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

1 10484 2

<0 входом счетчика и с первым выходом блока, а второй выход - с управляющим входом дешифратора нуля, информа1

Изобретение относится к вычислит явной технике, в частности к электоонным цифровым вычислительным машинам .

Известны устройства для деления, выполняющие операцию деления двоичных чисел без восстановления остатка f1) .

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

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

/ / пропусков тактов суммирования (вычитания) для достаточно малых или достаточно больших по абсолютной величине остатков. Так, например, если в результате сложения (вычитания) образуется положительный остаток, содержащий в старших разрядах

К нулей, то ближайшие (К-1) разрядов частного нуля. Для получения следую15

45 ционные входы которого подключены к выходам разрядов счетчика, а выходк второму входу первого элемента ИЛИ.

2 щего остатка достаточно первоначальный остаток сдвинуть на К разрядов влево и затем вычесть из него делитель ° Аналогично получают достаточно малый по абсолютной величине отрицательный остаток, содержащий в старших разрядах К единиц..При этом (К-1) ближайших разрядов частного единицы и для получения очередного остатка достаточно первоначальный .. остаток сдвинуть на К разрядов влево и затем прибавить к нему делитель.

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

Случаи больших по абсолютной величине остатков выявляет схема сравнения путем сравнения четырех старших разрядов кода делителя и кода очередного. остатка. Если сравниваемые коды близки, то без предварительного, сдвига выполняется еще один такт сложения (вычитания), в результате чего образуется малый поабсолютной величине, остаток, для которого правила образования ближайших разрядов частного изложены выше. Если же остаток не является ни достаточно малым, .ни достаточно большим, то для определения разрядов частного применяется обычный метод, при котором значения разрядов частного определяются в блоке управления по знаку остатка (2) .

Таким образом, в известном устройстве разряды частного образуются по разным правилам для остатков различной величины, что приводит к усложненИю известного устройства.

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

Для достижения поставленной цели в устройстве для деления двоичных чисел, содержащем регистры дели1048 мого, делителя и частного, сумматор, блок анализа и блок управ" ления, причем выходы разрядов регистра частного соединены с выходами устройства, входы устройства соединены с информационными входами разрядов регистра делителя, выходы разрядов регистров делимого и делителя сое-. динены с входами разрядов сумматора, выходы сумматора соединены с информационными входами регистра делимого, выходы прямого и инверсного эна10 чений старших разрядов регистра делимого соединены со входами блока айалиэа, выходы которого подключены ко входам блока управления, первыйвыход которого соединен со входами . управления сдвигом регистров делимо"

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

35 генератора импульсов подключен ко входу первого распределителя импульсов, первый выход которого соединен, с пятым выходом блока, а второй выход - с первым входом первого эле40 мента ИЛИ, выход которого соединен. с информационным входом коммутатора, управляющий вход которого подключен к первому входу блока, а первый выход - к входу второго распределите45 ля импульсов, первый выход которого подключен к первым входам первого и второго элементов И, вторые входы которых соединены со вторым и.третьим входами блока соответственно, а выходы являются вторым и третьим выходами блока соответственно, второй выход второго распределителя импульсов соединен с четвертым выходом блока, а третий выход — с первым входом второго элемента ИЛИ, второй вход кбторого подключен ко второму выходу коммутатора, а выход - к

55 входу третьего распределителя импуль» управления приемом информации регист- Z5

472 4 сов, первый выход которого соединен со входом счетчика и с первым выходом блока, а второй выход " с управляющим входом дешифратора нуля, информационные входы которого подключены к выходам разрядов счетчика, а выход - к второму входу первого элемента ИЛИ.

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

Устройство содержит регистр де" лителя 1, регистр делимого 2, регистр частного 3, сумматор 4, блок управления 5, блок анализа б, вход устройIcrsa 7, выход устройства 8.

Блок управления 5 содержит генера, тор импульсов 9, распределители импульсов 10, 11 и 12, элементы ИЛИ 13

14, элементы И 15 и 16 счетчик 17, коммутатор 18, дешифратор нуля 19, выходы 20-24, входы 25, 26 и 27.

Блок анализа 6 содержит элементы

И 28, 29, ИЛИ 30. НЕ 31.

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

Регистры 1, 2 и 3 имеют по одному дополнительному разряду, при этом регистры,2 и 3 содержат цепи сдвига влево, регистр 1 может, быть не сдвиговым. Сумматор 4 является (и -1)"раз" рядным сумматором комбинационного типа и складывает коды, поступающие из регистров 1 и 2, результат записывается в регистр 2. Блок 6 анализа вырабатывает сигналы

xo=boЬ1 V Ь, Ь1 х1--Ь Ь х =Ьо Ь4, где Ь - состояние ("0" или 1").перP

) вого слева (знакового) разряда регистра 2 делимого

Ь1 - состояние("0" или "1") второго слева (старшего дробного) разряда этого же регистра.

Значение сигналов хо,х1,х пода" ются с выходов блока 6 анализа на входы 25, 26 и 27 блока управления

5 соответственно.

Генератор 9 вырабатывает запуска ющий импульс в начале выполнения

48472 6

В 1.0 операции деления. Распределители 10, 11 и 12 обеспечивают временное распределение управляющих сигналов в соответствии с длительностью действий, выполняемых по каждому из этих сигналов. Счетчик 17 предназначен для подсчета количества циклов таким образом, что устанавливается в нуль при выполнении всех циклов.

Дешифратор нуля 19 подключает сигнал со второго выхода распределителя

12 на вход элемента ИЛИ 13, в том случае, если состояние счетчика 17 н равно нулю, тем самым обеспечивается повторение циклов деления до определения всех цифр частного. Если е состояние — ÷åò÷èêà 17 становится равным нулю, то дешифратор нуля 19 не пропускает сигнал на вход элемента ИЛИ 13 и выполнение циклов деления прекращается. КоммувЂ,атор 18 переключает поступающий на его вход сигнал либо на вход распределителя 11 при отсутствии сиг- .ала х на входе 25 блока 5, либо на вход элемента ИЛИ 14 при наличии сигнала на входе 25 блока 5. Тем самым обеспечивается изменение состава действий в каждом цикле в зависимости от наличия сигнала хо. Если хо=1, то цикл деления содержит только совместный сдвиг регистров 2 и 3 влево по управляющему сигналу с выхода 20 блока 5, если же хо--0, то в цикле дополнительно выполняется сложение кодов регистров 1 и 2, !

О !

35 вход коммутатора 18. Так как на уп= равляющий вход коммутатора 18 в это время поступает нулевой сигнал (xo=0) то импульс проходит на вход распределителя 11. С этого момента начинается выполнение первого цикла. С первого выхода распределителя 11 импульс поступает на первые входы элементов И 15 и 16. Так как х1-1, х =О, то импульс проходит через элемент

15 И, выходы 21 блока 5 и далее на вход управления выдачей дополнительного кода регистра делителя

Дополнительный код регистра 1, подаваемый на сумматор 4, представляется как его инверсный код и единичный сигнал, поступающиЙ на вход переноса младшего разряда сумматора 4.

На сумматоре 4 производится сложение поступившего кода с кодом из регистра 2. Через заданный промежуток времени появляется управляющий. сигнал. на втором выходе распределителя 11.

Этот сигнал. через выход 23 блока 5 подается на вход управления приемом информации регистра 2. При поступлении этого сигнала производится запись в регистр 2 кода суммы, полученный на сумматоре 4. При этом содержимое дробных разрядов суммы представляет из себя остаток в пря; мом или дополнительном коде, а содержимое знакового разряда ("О" или

"1") равно значению первой цифры частного.

Перед началом операции деления коды делителя и делимого располагаются в регистрах 1 и 2 соответственно

В знаковом разряде каждого из регистров 1 и 2 записан нулевой код, а в старшем дробном разряде - единичный код, так как делитель и делимое являются нормализованными числами. Так как ЬО=О, Ь =1, то перед первым циклом на выходах блока 6 устанавливаются значения хо=0, х =1, x =0, В начале операции деления генератор 9 вырабатывает запускающий импульс, который подается на вход распределителя импульсов 10. С первого выхода распределителя 10 импульс поступает на выход 24 блока 5 и далее на- вход установки знакового разряда регистра 1 и производит установку этого разряда в единичное состояние. Со второго выхода распределителя 1О через элемент ИЛИ 13 импульс поступает на информационный

Пусть содержимое регистра 2 B=bo„

b,b,:...,Ьп, а содержимое регистра 1 Обоd d,...,äl . В рассматриваемом случае Ьо=О, .Ь =1, а две старшие цифры величины 0 равны единице.

0 =4 =1 и следовательно их инверсные о значения d =d! =О. Результат сложения величины В C 40fl0llHNTeJlbHblM кодом О величины 0 равен

S=B> Щ01Ь Ь,...,Ьп 00d d,. с1„,+

-Н

+2 = о S2 .,Ъ„

Если делимое больше делителя ипи равно ему, то при сложении возникает перенос Р в старший дробный разряд и

S =b +d4+Р„=1+0+!=О, а перенос в знаковый разряд Рд=1 °

Следовательно значение знакового разряда суммы равно

So bo+do+P0 0+0+1=1.

1048472

S» =1+0+0=1, S =0+0+0=0.

P =0, 5» =О+ 1+0=1

5 =1+1+0=0

О

Р, =О, bi=0;

Ь„=1 1

bÎ =0;

b», bb =1;

Ь =О

Ь =l.

» ю

Если делимое меньше делителя, то перенос Р» =0 и

Таким образом, для каждого из этих случаев значение S совпадает . со значением цифры частного, а зна-. чение S» определяет знак остатка если S 0, то остаток положителен - . 10 и представлен в прямом коде, если .

54 =1, то остаток отрицателен и представлен в дополнительном коре.

Далее с третьего выхода распреде- лителя 11 через элемент ИЛИ 14 им- »5 пульс поступает на вход распределителя 12. С первого выхода распре" делителя 12 управляющий сигнал подается на вход счетчика 17 и выход 20 блока управления 5. С выхода 20 уп 2»Е равляющий сигнал поступает на входы управления сдвигом регистров 2 и 3.

При поступлении. этого сигнала произ водится совместный сдвиг содержимо=

ro регистров 2 и 3 влево на один разряд. В результате сдвига полученная цифра частного из знакового разряда регистра 2 переписывается в младший разряд регистра 3, в свою очередь, в заковый разряд регистра 2 эапиЖ вается старший дробный разряд остатка, на его место - следующий за ним разряд и т. д. Одновременно: со сдвигом производится прибавление (или вычитание) единицы к содержимому счетчика 17. Далее со второго выхода распределителя 12 импульс подается на дешифратор нуля 19 и, если содержимое счетчика 17 не равно нулю,с выхода дешифратора 19 через элемент 4О

ИЛИ 13 на информационный вход комму" татора. 18. На этом выполнение первого цикла деления. заканчивается. В резуль тате его выполнения в старших разрядах регистра, 2 могут возникнуть.сле- 45 дующие новые комбинации:

1 для положительного остатка для отрицательного остатка

Комбинация Ь =0; b» =1 в точности 55 соответствует исходной комбинации в начале деления, поэтому действия. повторяются.

Комбинация Ь =1, b 0 соответству. ет отрицательному остатку, близкому к делителю по абсолютной величине.

Следовательно, в этом случае в отличие от описанного необходимо произвести сложение содержимого регистра 2 с прямым кодом содержимого регистра 1. Так как сигнал х по-прежнео му равен нулю, то импульс с первого выхода коммутатора 18 подается на вход распределителя 11 и далее с первого выхода распределителя 1 1 на первые входы элементов И 15, 16. 8 этом случае х»=0, а х = 1, поэтому импульс проходит через .элемент И 16 на выход 22 блока и далее на вход управления. выдачей прямого кода регистра делителя 1, в результате чего на вход сумматора подается прямой код регистра 1. При этом сложении, также как и в рассмотренном случае, значение величины 5О равно значению очередной цифры частного, а значение величины S» определяет знак вновь полученного остатка., В .этом случае

+О 1 0bg b$ Ь„+ 1 1 2 1 5 ° ° °

= „5

Если код сдвинутого влево остатка по абсолютной величине больше кода делителя, то Р» =0 и т.е. очередная цифра частного равна нулю и новый остаток также является отрицательным. Если код сдвинутого влево остатка по абсолютной величине меньше или равен коду делителя, то.P =1 и

»

5 ;-0+1+1=0, Р =1, S0 =1+1+1=1, т.е. очередная цифра частного равна единице и новый остаток будет положительным. После выполнения сло жения повторяются ранее описанные действия для случая Ь =О, Ь =l. Комбинации Ь =-О, Ь» =О, и bo=1, Ь» =1 соответствуют малым по абсолютной величине остаткам по сравнению с делителем. Такт сложения в этом слу" чае может быть пропущей, а очередная цифра частного равна значению b

8 этом случае на управляющий вход коммутатора 18 подается единичный сигнал х =1, поэтому импульс, посту10484 пивший на его информационный вход переключается на второй выход и че" рез элемент ИЛИ 14 поступает на вход распределителя 12. Далее аналогично производится совместный сдвиг регистров 2 и 3, подсчет количества циклов и проверка окончания деления.

После каждого произведенного сдви га возникает одна из четырех возможных комбинаций значений b>,b< и опи- 10 санные ранее действия повторяются.

Операция заканчивается, когда содержимое счетчика lj становится равным нчпю °

Таким образом, каждый цикл деле- 15 ния в зависимости от содержимого ,ву. старших разрядов регистра 2 сос-. тоит либо из двух тактов: такта алгебраического сложения и такта сдвига, либо только иэ одного такта сдаи- 20 га. Независимо от выполняемых действий, в каждом цикле в знаковом разряде регистра 2 определяется одна цифра частного, которая передается

ы младший разряд регистра 3 в про- 25 цессе совместного сдвига этих регистров.

Время выполнения деления зависит от соотношения количества тактов сложения и тактов сдвига, так как ЭО последние выполняются в несколько раз быстрее тактов сложения. Для оценки быстродействия предлагаемого устройства необходимо определить математическое ожидание вс количества тактов сдвига после такта сложения.

После каждого такта сложения обязательно следует один такт сдвига.

Последующие действия устройства зависят от содержимого двух старших 4п разрядов регистра 2 делимого. Если содержимое этих раз;)ядов не совпадает между собой, то выполняется такт сложения, в противном случае выполняется такт сдвига. В дальней- 45 шем такты сдвига повторяются до тех пор, пока содержимое двух старших

72 \0 разрядов регистра 2 не становится разным. Таким образом, общее количество тактов сдвига, выполняемых после такта сложения, равно количеству одинаковых цифр (нулей или единиц), содержащихся в старших дроб. ных разрядах полученной суммы S.

Вычислениями можно установить, что математическое ожидание количе" ства следующих подряд тактов сдвига после такта сложения равно

2 -1 —, z ) ° Pj ° -т))р,) с 1=1

8 для достаточно больших и m a-, Это означает, что после каждого такта сложения в среднем выполняется 8/3 тактов сдвига, т.е. на каждые 8 разрядов частного приходится в среднем 3 такта сложения.

Обозначив через Т,„ — время выполнения такта сложения, а через Т „ время выполнения такта сдвига, получаем. среднее время Т0 вычисления

11 разрядов частного

Та = р IlTgII + ПТс в.

Таким образом, устройство сокращает, в среднем, количество тактов сложения до 37,5i. .Дальнейшее повышение быстродействия устройства, как и у прототипа может быть получено путем авода дополнительных цепей сдвига регистров делимого и частного на два, три и т.д. разряда и соответствующего увеличения количества анализируемых разрядов регистра делимого.

Следовательно быстродействие данного устройства, по крайней мере, не ниже чем у прототипа.

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

1048472 и.

1048472

Составитель В. Березкин

ТехРед И.Тепер

Корректор О.Билак

Редактор А. Долинич филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

Заказ 7933/54 Тираж 706 Подписное

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

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