SU1048472A1 - Устройство дл делени двоичных чисел - Google Patents

Abstract

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

Description

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

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

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

Известны устройства дл  делени , выполн ющие операцию делени  двоичных чисел без восстановлени  остатка 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 в точности соответствует исходной комбинации ( в начале делени , поэтому действИ Я, повтор ютс . . :72 Q - , 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

Фт.З

Claims (2)

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

2. Устройство по π. 1, отличающееся тем, что блок управления содержит генератор импульсов, счетчик, элементы И, ИЛИ, дешифратор нуля, распределители импульсов и коммутатор, причем выход генератора импульсов подключен ко входу первого распределителя импульсов, первый выход которого соединен с пя-, тым выходом блока, а второй выходс первым входом первого элемента ИЛИ, выход которого соединён с информационным входом коммутатора, управляющий вход которого подключен к первому входу блока, а первый выходко входу второго распределителя импульсов, первый выход которого подключен к первым входам первого и второго элементов И, вторые входы которых соединены со вторым и третьим! входами блока соответственно, а выходы являются вторым и третьим выхода· ми блока соответственно, второй выход второго распределителя импульсов соединен с четвертым выходом блока, а третий выход - с первым входом второго элемента ИЛИ, второй вход которого подключен ко второму выходу коммутатора, а выход - к входу третьего распределителя импульсов, первый выход которого соединен со ,SU,„. 10484721048472 входом счетчика и с первым выходом ционные входы которого подключены к блока, а второй выход - с управляю- выходам разрядов счетчика, а выход щим входом дешифратора нуля, информа-' к второму входу первого элемента ИЛИ.