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

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

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

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

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

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

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

Наиболее близким к изобретению является устройство для деления двоичных чисел, содержащее регистры делителя и частного, накапливающий сумматор, схему сравнения, блок опроса и блок управления, выходы которого, соединены с первыми входами регистров делителя, частного и накапливающего сумматора, первый выход регистра делителя соединен со вторым входом накапливающего сумматора,первый выход которого подключен к первому входу блока управления, третий выход накапливающего сумматора соединен со входом блока опроса, выход которого под.ключен ко второму входу блока управления, вторые выходы регистра делителя и накапливающего сумматора подключены соответственно к первому и второму входам схемы сравнения, выход которой подключен к третьему входу блока управления. Известное устройство обеспечивает ускоренное выполнение операции деления за счет пропусков тактов суммирования;(вычитания) для достаточно малых или достаточно больших по абсолютной величине остатков. Так, например, если в результате сложения (вычитания) образуется положительный остаток, содержащий в старших разрядах К нулей, то ближайшие (К-1) разрядов частного нуля. Для получения следую-.

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

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

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

Для достижения поставленной цели в устройстве для деления двоичных чисел, содержащем регистры делимого, делителя и частного, сумматор, блок анализа и блок управления, причем выходы разрядовретист ра частного соединены с выходами уст ройства, входы устройства соединены с информационными входами разрядов регистра делителя, выходы разрядов регистров делимого и делителя соединены с входами разрядов сумматора выходы сумматора соединены с информационнЫми входами регистра делимоrd, выходы прямого и инверсного значений старших разрядов регистра дели мого соединены со входами блока анализа, выходы которого подключены ко входам блока управления, первый выход которого соединен со входами управления сдвигом peгиctpoв делимого и частного, второй и третий выход блока управления подключены ко входам управления выдачей соответствен но дополнительного и прямого кодов регистра делителя, четвертый выход блока управления соединен со входом управления приемом информации регист ра делимого, пятый выход блокауправления соединен со входом установки знакового разряда регистра делиТе ля, выход старшего разряда регистра делимого подключен ко входу младшего разряда регистра частного, блок управления содержит генератор импульсов, счетчик, элементы И, ИЛИ, дешифратор нуля, распределители импульсов, и коммутатор, причем выход генератора импульсов подключен ко входу первого распределителя импульсов, первый выхЬд которого соединен с пятым выходом блока, а второй выход - с первым входом первого элемента ИЛИ, выход которого соединен, с информационным входом коммутатора, управляющий вход которого подключен к первому входу блока, а первый йыход - к входу второго распределителя импульсов, первый выход которого подключен к первым входам первогго и второго элементов И, вторые входы которых соединены со вторым и .т|эетьим входами блока соответственно, а. выходы являются вторым и третьим выходами блока соскгветственно, второй выход второго распределителя импульсов соединен с четвертым выхо дом блока, а третий выход -с первым входом второго элемента ИЛИ, второй вход которого подключен ко второму выходу кбммутатора, а выход - к входу третьего распределителя импул со входом счетчика и с первым выходом блока, а второй выход - с управляющим входом дешифратора нуля, информационные входы которого подключены к выходам разрядов счетчика/ а виход - к второму входу первого элемента ИЛИ, На фиг. 1 представлена блок-схема устройства для деления двоичных чисел; на фиг. 2 - функциональная схема блока управления; на фиг. 3 блок анализа. Устройство содержит регистр делителя 1, регистр делимого 2, регистр частного3, сумматор }, блок управления 5, блок анализа 6, вход устройcTsa 7, выход устройства 8. Блок управления 5 содержит генера тор импульсов 9, распределители импульсов 10, 11 и 12, элементы ИЛИ 13 , элементы И 15 и 16 счетчик 17 коммутатор 18, дешифратор нуля 19, выходы 20-2, входы 25, 2б и 27. Блок анализа 6 содержит элементы И 28, 29, ИЛИ 30. НЕ 31. Устройство выполняет деление/ -разрядных нормализованных двоичных чисел, представленных в прямых кодах, частное образуется также в прямом коде. Порядок и знак частного определяются по известным правилам. Регистры 1, 2 и 3 имеют по одному дополнительному разряду, при этом регистры,2 и 3 содержат цепи сдвига влево, регистр 1 может .быть не сдвиговым. Сумматор t является (п-1)-разрядным сумматором комбинационного типа и складывает коды, поступающие из регистров 1 и 2, результат записывается в регистр 2. Блок 6 анализа вырабатывает сигнапы , , где Ьд - состояние (О или 1) .первого слева (знакового) разряда регистра 2 делимого; Ь - состояниеСО или 1) второго слева (старшего дробного) разряда этого же регистра. Значение сигналов XQ,X,Х2 подаются с выходов блока 6 анализа на входы 25, 26 и 27 блока управления 5 соответственно. Генератор 9 вырабатывает запуска ющий импульс в начале выполнения

5

.операции деления. Распределители 10

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

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

12на вход элемента ИЛИ 13, в том случае, если состояние счетчика 17. и равно нулю, тем самым обеспечивается повторение циклов деления до определения всех цифр частного. Если же состояние счетчика 17 становится равным нулю, то дешифратор нуля 19 не пропускает сигнал на вход элемента ИЛИ 13 и выполнение циклов деления прекращается. Коммутатор 1о переключает поступающий

на его вход сигнал либо на вход распределителя 1 1 при отсутствии СИ1-

кала XQ на входе 25 блока 5, либо на вход элемента ИЛИ Н при наличии сигнала на входе 25 блока 5. Тем самым обеспечивается изменение состава действий в каждом цикле в зависимости от наличия сигнала хр. Если , то цикл деления содерн ит только совместный сдвиг регистров 2 и 3 влево по управляющему сигналу с выхода 20 блока 5, если же , то в цикле дополнительно выполняется сложение кодов регистров 1 и 2,

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

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

то импульс проходит через элемент

15 И, выходы 21 блока 5 и далее .на вход управления выдачей дополнительного кода регистра делителя 1. Дополнительный код регистра 1, подаваемый на сумматор 4, представляется как его инверсный код и единичный сигнал, поступающий на вход переноса младшего разряда сумматора 4. На сумматоре 4 производится сложение

поступившего кода с кодом из регистра 2. Через заданной промежуток времени появляется управляющий, сигнална втором выходе распределителя 11. iЭтот сигнал.через выход 23 блока 5

подается на вход управления приемом информации регистра 2. При поступлении этогосигнала производится запись в регистр 2 кода суммы, полученный на Сумматоре Ц. При этом

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

частного.

Пусть содержимое регистра 2 , Ьц fbq i,., , а содержимое регистра 1 , . ., ,c(f. В рассматриваемом случае , , а две старшие цифры величины D равны единице. и следовательно их инверсные значения . Результат сложения величины В с дополнительным кодом

ВД величины D равен

S B4 D 01bjb3b OOd d, ,....,а„4

о -с еес

t- -OQ o/i о ,

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

- 1+0+1 0,

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

So bo+do+Po 0+0+1 K Если делимое меньше делителя, топеренос R, 0 и Si 1+0+0 1, $0 0+0+0 0. Таким образом, для каждого из этих случаев значение SQ совпадает со значением цифры чайтного, а значение $1 определяет знак остатка; если , то остаток положителен и представлен в прямом коде, если , то остаток отрицателен и представлен в дополнительном коде. Далее с третьего выхода распределителя 11 через элемент ИЛИ 1 импульс поступает на вход распределителя 12. С первого выхода распределителя 12 управляющий сигнал подается на вход счетчика 17 и выход 20 блока управления 5. С выхсуда 20 управляющий сигнал поступает на входы управления сдвигом регистров 2 и 3. При поступлении, этого сигнала произ водится совместный сдвиг содержимо го регистров 2 и 3 влево на один разряд. В результате сдвига полученная цифра частного из знакового разряда регистра-2 переписывается в младший разряд регистра 3, в свою очередь, в заковый разряд регистра 2 эапи Ь1вается старший дробный разряд остатка, на его место - следующий за ним разряд и т.д. Одновременно со сдвигом производится прибавлени-е (или вычитание) единицы к содержимом счетчика 17. Далее со второго выхода распределителя 12 импульс подается, на дешифратор нуля 19 и, если содержимое счетчика 17 не равно нулю,с выхода дешифратора 19 через элемент ИЛИ 13 на информационный вход коммутатора. 18. На этом выполнение первог цикла деления заканчивается. В резуд тате его выполнения в старших разрядах регистра, 2 могут возникнуть следующие новые комбинации: . J для положительного остатка :„ для отрицательного остатка Комбинация Ь| 1 в точности соответствует исходной комбинации ( в начале деления, поэтому действИ Я, повторяются. . :72Q - , 1 -О соответствуКомбинация Ьет отрицательному остатку, близкому к делителю по абсолютной величине. Следовательно, в этом случае в отличие от описанного необходимо произвести сложение содержимого регистра 2 с прямым кодом содержимого регистра 1. Так как сигнал х по-прежнему равен нулю, то импульс с первого выхода коммутатора 18 подается на вход распределителя 11 и.далее с первого выхода распределителя 11 на первые входы элементов И 15, 1б. В этом случае , а Хп 1 , поэтому импульс проходит через элемент И 16 на выход 22 блока 5 и далее на вход управления .выдачей прямого кода регистра делителя 1, в результате чего на вход сумматора подается прямой код регистра 1. При этом сложении, также как и в рассмотренном случае, значение величины SQ равно значению очередной цифры частного, а значение величины 5 определяет знак вновь полученного остатка. .В этом случае Ob2 b ,. . . , (,. . ., djj SgS Sj ,,. . ,Sj Если код сдвинутого влево остатка по абсолютной величине больше кода делителя, то и $1 0+1+0 1, , 5 1+1+0 0, т.е. очередная цифра частного равна нулю и новый остаток также является отрицательным. Если код сдвинутого влево остатка по абсолютной величине меньше или равен коду делителя, т о Р. 1 и 5 0+1+1 0,: 5 1+1+1 1, Т.е. очередная цифрачастного равна единице и новый остаток будет положительным. После выполнения сложения повторяются ранее описанные действия для случая , , Комбинации , , и Ьо 1 , , соответствуют малым по абсолютной величине остаткам по сравнению с делителем. Такт сложения в этом случае может быть пропущен, а очередная цифра частного равна значению Ь,, В этом случае на управляющий вход коммутатора 18 подается единичный сигнал поэтому импульс, поступивший на его информационный вход переключается на второй выход и через элемент ИЛИ 14 поступает на вход распределителя 12. Далее аналогично производится совместный сдвиг регистров 2 и 3 подсчет количества цик лов и проверка окончания деления. После каждого произведенного сдв га возникает одна из четырех возможных комбинаций значений b,b и описанные ранее действия повторяются. Операция заканчивается, когда содержимое счетчика ,17 становится равным Таким образом, каждый цикл деления в зависимости от содержимого пеух. старших разрядов регистра 2 сос тоит либо из двух тактов: такта алгебраического сложения и такта сдвига, либо только из одного такта сдви га. Независимо от выполняемых действий, в каждом цикле в знаковом разряде регистра 2 определяется одна цифра частного, которая передается ti младший разряд регистра 3 в процессе совместного сдвига этих регистров. Время выполнения деления зависит от соотношения количества тактов сложения и тактов сдвига, так как последние выполняются в несколько ра быстрее тактов сложения. Для оценки быстродействия предлагаемого устройства необходимо определить математическое ожидание m.j. количества тактов сдвига после такта сложения. После каждого такта сложения обязательно следует один такт сдвига. Последующие действия устройства зависят от содержимого двух старших разрядов регистра 2 делимого. Если содержимое этих разрядов не совпадает между собой, то выполняется такт сложения, в противном случае выполняется такт сдвига. В дальнейшем такты сдвига повторяются до тех пор,.пока содержимое двух старших 7210 разрядов регистра 2 не становится разным. Таким образом, общее количество тактов сдвига, выполняемых после такта сложения, равно количеству одинаковых цифр (нулей или единиц), содержащихся в старших дробных разрядах полученной суммы S. Вычислениями можно установить, что математическое ожидание количества следующих подряд тактов сдвига после такта сложения равно п-1 , JPj для достаточно больших и т.я-г- , Это означает, что после каждого такта сложения в среднем выполняется 8/3 тактов сдвига, т.е. на каждые 8 разрядов частного приходится в среднем 3 такта сложения. Обозначив через T.J - время выполнения такта сложения, а через T.g время выполнения такта сдвига, получаем, среднее время TQ вычисления Г) разрядов частного о ЁГ СА5К ЦВТаким образом, устройство сокращает, в среднем, количество тактов сложения.до 37,5. Дальнейшее повышение быстродействия Устройству, как и у прототипа может быть получено путем ввода дополнительных цепей сдвига регистров делимого и частного на два, три и т.д. разряда и соответствующего увеличения количества анализируемых разрядов регистра делимого. Следйаательно быстродействие данного устройства, по крайней мере, не ниже чем у прототипа. Положительный эффект заключается в упрощении устройства, так как не трё буется различных цепей образования цифр частного для остатков различной величины. 26A.Zf 22 Л. 27 JA

Фт.З