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

(19) 01) А УБЛИН Р I РСИОМУ СВИДЕ ЛЬСТИ К"Приборостроение",.с. 9- 11 (прототип),входом управлен регистра делимо ющееся те рощения устройс ка управления с установки знако ра делителя, вы регистра делимо ду младшего раз ия приемом го,отл м,что,с тва, пятый оединен со информа и ч а " 8 ф 38 лью упыход бло входома регисто разрядан ко вхора частАри ука ка циф 69,го раз од старше о подключ яда регис,Д. М ния в тодцифог ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ ПИСАНИЕ ИЗ нахов Г еУ го делех машинах.1957, М 2,,(5")(5) 1. УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯДВОИЧНЫХ ЧИСЕЛ) содержащее регист-ры делимого, делителя и частногосумматора, блок анализа и блок управления, причем выходы разрядоврегистра частного соединены с выходами устройства, входы устройства, соединены с информационными входажиразрядов регистра делителя, выходы,разрядов регистров делимого и дели"геля соединены с информационнымивходами разрядов сумматора, выходы сумматора соединены с информационнымивходами регистра делимого, выходыпрямого и инверсного значений старших.разрядов регистра делимого сое"динены со входами блока анализа,выходы которого подключены ко входамблока управления, первый выход ко-.торого соединен со входами управления сдвигом регистров делимого ичастного, второй и третий выходыблока управления подключены ко вхо дам управления выдачей соответственно дополнительного и прямого кодов регистра делителя, четвертый выход блока управления соединен со 2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок управления содержит генератор импульсов, счетчик, элементы И, ИЛИ, дешиф. ратор нуля, распределители импуль" сов и коммутатор, причем выход генератора импульсов подключен ко входу ф первого распределителя импульсов, первый выход которого соединей с пя-, тым выходом блока, а второй выход" с первым входом первого элемента ИЛИ, выход которого соединен с инфор- Я мационным входом коммутатора, управ" ляющий вход которого подключен к первому входу блока, а первый выходко входу второго распределителя импульсов, первый выход которого подключен к первым входам первого и второго элементов И, вторые входы которых соединены со вторым и третьим 1 входами блока соответственно, а выходы является вторым и третьим выхода ми блока соответственно, второй выход второго распределителя импульсов соединен с четвертым выходом блока, а третий выход - с первым входом второго элемента ИЛИ; второй вход которого подключен ко второму выходу коммутатора, а выход - к входу третьего распределителя импульсов, первый выход которого соединен со10 Й 8472 входом счетчика и с первым выходомблока, а второй выход - с управляющим входом дешифратора нуля, информа 5 10 1Изобретение относится к вычислит явной технике, в частности к элек тоонным цифровым вычислительным машинамИзвестны устройства для деления, выполняющие операцию деления двоичных чисел без восстановления остатка 111 .Однако в таких устройствах дляпределения каждой двоичной цифры частного требуется один такт суммирования (вычитания),что отрицательн:; сказывается на времени выполнения операции деления.Наиболее близким к изобретению является устройство для деления двоичных чисел, содержащее регистры. делителя и частного, накапливающий сумматор, схему сравнения, блок опроса и блок управления, выходы которого, соединены с первыми входами регистров делителя, частного и накапливающего сумматора, первый выход регистра делителя соединен со вторым входом накапливающего сумматора, первый выход которого подключен к первому входу блока управления, третий выход накапливающего сумматора соединен со входом блока опроса, выход которого под.ключен ко второму входу блока управления, вторые выходы регистра делителя и накапливающего сумматора подключены соответственно к первому и второму входам схемы сравнения, выход которой подключен к третьему входу блока управления. Известное устройство обеспечивает ускоренное выполнение операции деления за счет/ / пропусков тактов суммирования (вычитания) для достаточно малых или достаточно больших по абсолютной величине остатков. Так, например, если в результате сложения (вычитания) образуется положительный остаток, содержащий в старших разрядах К нулей, то ближайшие (К) разрядов частного нуля. Для получения следую 5 20 25 30 35 40 45 ционные входы которого подключены квыходам разрядов счетчика, а выходк второму входу первого элемента ИЛИ.щего остатка достаточно первоначальный остаток сдвинуть на К разрядов влево и затем вычесть из него делительАналогично получают достаточно малый по абсолютной величине отрицательный остаток, содержащий встарших разрядах К единицПри этом(К) ближайших разрядов частногоединицы и для получения очередногоостатка достаточно первоначальныйостаток сдвинуть на К разрядов влевои затем прибавить к нему делитель. Случаи малых по абсолютной величине остатков выявляет блок опроса, который анализирует код в трех старших разрядах накапливающего сумматора, содержащего в себе остаток. Случаи больших по абсолютной величине остатков выявляет схема сравнения путем сравнения четырех старших разрядов кода делителя и кода очередного. остатка. Если сравниваемые коды близки, то без предварительного, сдвига выполняется еще один такт сложения (вычитания), в результате чего образуется малый по- абсолютной величине, остаток, для которого правила образования ближайших разрядов частного изложены выше. Если же остаток не является ни достаточно малым, .ни достаточно боль. шим, то для определения разрядов частного применяется обычный метод, при котором значения разрядов частного определяются в блоке управления по знаку остатка 2.Таким образом, в известном устройстве разряды частного образуются по разным правилам для остатков различной величины, что приводит к усложненИю известного устройства,Цель изобретения - упрощение уст. ройства.Для достижения поставленной цели в устройстве для деления двоичных чисел, содержащем регистры дели108 10 15 20 30 35 40 55 мого, делителя и частного, сумматор, блок анализа и блок управ" ления, причем выходы разрядов регистра частного соединены с выходами устройства, входы устройства соединеныс информационными входами разрядоврегистра делителя, выходы разрядоврегистров делимого и делителя соединены с входами разрядов сумматора,выходы сумматора соединены с информационными входами регистра делимо"гб, выходы прямого и инверсного эначений старших разрядов регистра делимого соединены со входами блока айалиэа, выходы которого подключеныко входам блока управления, первыйвыход которого соединен со входами .управления сдвигом регистров делимо" го и частного, второй и третий выходы блока управления подключены ко входам управления выдачей соответственно дополнительного и прямого кодоврегистра делителя, четвертый выходблока управления соединен со входом упРавления приемом информации регист ра делимого, пятый выход блока управления соединен со входом установки знакового разряда регистра делите. ля, выход старшего разряда регистраделимого подключен ко входу младшего разряда регистра частного, блокуправления содержит генератор импульсов, счетчик, элементы И, ИЛИ,дешифратор нуля, распределители импульсов. и коммутатор, причем выход генератора импульсов подключен ко входу первого распределителя импульсов, первый выход которого соединен , с пятым выходом блока, а второй выход - с первым входом первого элемента ИЛИ, выход которого соединен. с информационным входом коммутатора, управляющий вход которого подключен к первому входу блока, а первый выход - к входу второго распределите 45 ля импульсов, первый выход которого подключен к первым входам первого и второго элементов И, вторые входы которых соединены со вторым и.третьим входами блока соответственно, а выходы являются вторым и третьим выходами блока соответственно, второй выход второго распределителя импульсов соединен с четвертым выходом блока, а третий выход - с первымвходом второго элемента ИЛИ, второйвход кбторого подключен ко второмувыходу коммутатора, а выход - к входу третьего распределителя импуль 4 Псов, первый выход которого соединенсо входом счетчика и с первым выходом блока, а второй выход " с управляющим входом дешифратора нуля,информационные входы которого подключены к выходам разрядов счетчика, авыход - к второму входу первого элемента ИЛИ.На фиг. 1 представлена блок-схе"ма устройства для деления двоичныхчисел; на фиг, 2 - функциональная, тор импульсов 9, распределители импульсов 10, 11 и 12, элементы ИЛИ 1311, элементы И 15 и 16 счетчик 17,коммутатор 18, дешифратор нуля 19, .выходы 20-24, входы 25, 26 и 27,Блок анализа 6 содержит элементыИ 28, 29, ИЛИ 30. НЕ 31.Устройство выполняет деление 1-раз"рядных нормализованных двоичных чи"сел, представленных в прямых кодах,частное образуется также в прямомкоде. Порядок и знак частного определяются по известным правилам.Регистры 1, 2 и 3 имеют по одномудополнительному разряду, при этомрегистры,2 и 3 содержат цепи сдвигавлево, регистр 1 может, быть не сдвиговым. Сумматор 11 является (и -1)"раз"рядным сумматором комбинационноготипа и складывает коды, поступающиеиз регистров 1 и 2, результат эа"писывается в регистр 2. Блок 6 анализа вырабатывает сигналыхо=Ь,Ь 1 ч Ь, Ь 1х=Ь Ь 1х=Ьо Ь 4,где Ь - состояние (ф 0" или1 ф).пер"Ового слева (знакового) разряда регистра 2 делимого,Ь 1 - состояние("0" или "1") второго слева (старшего дробного) разряда этого же регистра.значение сигналов хо,х 1,х пода"ются с выходов блока 6 анализа навходы 25, 26 и 27 блока управления5 соответственно.Генератор 9 вырабатывает запускающий импульс в начале выполненияВ 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, если же х=О, то в цикле дополнительно выполняется сложение кодов регистров 1 и 2, 48472 6вход коммутатора 18. Так как на уп= равляющий вход коммутатора 18 в это время поступает нулевой сигнал (хо=0) то импульс проходит на вход распределителя 11. С этого момента начина 1 О 15 20 25 30 35 ется выполнение первого цикла. С первого выхода распределителя 11 импульс поступает на первые входы элементов И 15 и 16. Так как х 1=1, х=О, то импульс проходит через элемент 15 И, выходы 21 блока 5 и далее на вход управления выдачей дополнительного кода регистра делителя Дополнительный код регистра 1, подаваемый на сумматор 4, представляется как его инверсный код и единичный сигнал, поступающий на вход переноса младшего разряда сумматора 4. На сумматоре 4 производится сложение поступившего кода с кодом из регистра 2. Через заданный промежуток времени появляется управляющий. сигнал на втором выходе распределителя 11. Этот сигнал. через выход 23 блока 5 подается на вход управления приемом информации регистра 2. При поступлении этого сигнала производится запись в регистр 2 кода суммы, полученный на сумматоре 4. При этом содержимое дробных разрядов суммыпредставляет из себя остаток в пря; мом или дополнительном коде, а содержимое знакового разряда ("0" или "1") равно значению первой цифры частного.1Перед началом операции деления коды делителя и делимого располагаются в регистрах 1 и 2 соответственно В знаковом разряде каждого из регистров 1 и 2 записан нулевой код, ав старшем дробном разряде - единичный код, так как делитель и делимое являются нормализованными числа" ми. Так как ЬО=О, Ь 1=1, то перед .первым циклом на выходах блока б устанавливаются значения хо=0, х=1, к=0, В начале операции деления генератор 9 вырабатывает запускающий импульс, который подается на вход распределителя импульсов 10. С первого выхода распределителя 10 импульс поступает на выход 24 блока 5 и далее на. вход установки знакового разряда регистра 1 и производит установку этого разряда в единичное состояние. Со второго выхода распределителя 1 О через элемент ИЛИ 13 импульс поступает на информационный 40 45 50 55 Пусть содержимое регистра 2 В=Ь,Ь,Ь 2Ьп, а содержимое регистра 1 О дод 1 д 2дп. В рассматриваемом случае Ьо=0, Ь =1, а две старшие цифры величины О равны единице.д =Д =1 и следовательно их инверснь 1 еозначения д =0 =0. Результат сложениявеличины В с дополнительным кодомОвеличины О равенЬ В О 01 ЬЬ Ь 006 д1 д+2 =о гфЪЕсли делимое больше делителя ипиравно ему, то при сложении возникает перенос Р в старший дробныйразряд и5=Ь +д 4+Р 4 =1+0+1 =О,а перенос в знаковый разряд Рс =1Следовательно значение знакового разряда суммы равноо Ьо+о+Ро 0+0+1 1Р =О,Ь =0; Ь =0; Ь =1; Ьо =1; Ь =0Ь =1. Ф 7 Если делимое меньше делителя, то перенос Р =0 и5Таким образом, для каждого из этих случаев значение 5 совпадает со значением цифры частного, а зна-. чение 5 определяет знак остатка 1 если 5 =О, то остаток положителен . 10 и представлен в прямом коде, если .54 =1, то остаток отрицателен и представлен в дополнительном коре.Далее с третьего выхода распреде- лителя 11 через элемент ИЛИ 11 им пульс поступает на вход распреде" лителя 12. С первого выхода распре" делителя 12 управляющий сигнал подается на вход счетчика 17 и выход 20 блока управления 5. С выхода 20 уп равляющий сигнал поступает на входы управления сдвигом регистров 2 и 3. При поступлении. этого сигнала произ водится совместный сдвиг содераимо= го регистров 2 и 3 влево на один . 25разряд. В результате сдвига полу- ченная цифра частного из знаковогоразряда регистра 2 переписываетсяв младший разряд регистра 3, в своюочереДь, в заковый разряд Регистра 2 ЗОэапиЖвается старший дробный разряд остатка, на его место - следующийза ним разряд и т.д. Одновременно со сдвигом производится прибавление(или вычитание) единицы к содержимому 1 счетчика 17. Далее со второго выходараспределителя 12 импульс подается на дешифратор нуля 19 и, если содержимое счетчика 17 не равно нулюс выхода дешифратора 19 через элемент 4 О ИЛИ 13 на информационный вход комму" татора 18, На этом выполнение первого цикла деления.заканчивается. В резуль тате его выполнения в старших разря; дах регистра, 2 могут возникнуть сле дующие новые комбинации;для положительного остатка для отрицательного остатка Комбинация Ь =0; Ь=1 в точности 55 соответствует исходной комбинациив начале деления, поэтому действия, повторяются. 8Комбинация Ь =1, Ь =0 соответству ет отрицательному остатку, близкому к делителю по абсолютной величине. Следовательно, в этом случае в отличие от описанного необходимо произвести сложение содержимого регистра 2 с прямым кодом содержимого реги" стра 1. Так как сигнал х по-прежнеому равен нулю, то импульс с первого выхода коммутатора 18 подается навход распределителя 11 и далее с первого выхода распределителя 11 на первые входы элементов И 15 16, В этом случае х=0, а х 2=1 поэтому импульс проходит через .элемент И 16 на выход 22 блока 5 и далее на вход управления. выдачей прямого кода регистра делителя 1, в результате чего на вход сумматора подается прямой код регистра 1. При этом сложении, также как и в рассмотренном случае, значение величины 5 О равно значению очередной цифры частного, а значение величины 5 определяет знак вновь полученного остатка., В .этом случае 5=В+0=10 ЬЯЬ 3 Ьпф 114 бс 1 5 о 5525 пЕсли код сдвинутого влево остатка по абсолютной величине больше кода делителя, то Р =0 и т,е. очередная цифра частного равна нулю и новый остаток также является отрицательным, Если код сдвинутого влево остатка по абсолютной величине меньше или равен коду делителя, то.Р =1 и5 -0+1+1=0, Р -1,50 =1+1+1:1,т.е. очередная цифра частного равна единице и новый остаток будетположительным. После выполнения сложения повторяются ранее описанныедействия для случая Ь =О, Ь =1. Ком.бинации Ь 0соответствуют малым по абсолютнойвеличине остаткам по сравнению сделителем. Такт сложения в этом слу"чае может быть пропущей а очередная цифра частного равна значению ЬВ этом случае на управляющий входкоммутатора 18 подается единичныйсигнал х =1, поэтому импульс, посту108пивший на его информационный входпереключается на второй выход и че"рез элемент ИЛИ 14 поступает на входраспределителя 12, Далее аналогичнопроизводится совместный сдвиг регистрое 2 и 3, подсчет количества циклов и проверка окончания деления.После каждого произведенного сдвига возникает одна из четырех возмож"ных комбинаций значений Ь,Ь и опи" Осанные ранее действия повторяются.Операция заканчивается, когда содержимое счетчика,17 становится равнымнчпюТаким образом, каждый цикл деления в зависимости от содержимогол,ву.". старших разрядов регистра 2 сос-.тоит либо из двух тактов: такта алгебраического сложения и такта сдвига, либо только иэ одного такта сдаига, Независимо от выполняемых действий, в каждом цикле в знаковомразряде регистра 2 определяется однацифра частного, которая передаетсяы младший разряд регистра 3 в процессе совместного сдвига этих регистров,Время выполнения деления зависитот соотношения количества тактовсложения и тактов сдвига, так как ЗОпоследние выполняются в несколько разбыстрее тактов сложения. Для оценкибыстродействия предлагаемого устройства необходимо определить математическое ожидание в количества тактовсдвига после такта сложения,После каждого такта сложения обязательно следует один такт сдвига.Последующие действия устройства зависят от содержимого двух старших 40разрядов регистра 2 делимого. Еслисодержимое этих разрядов не совпадает между собой, то выполняетсятакт сложения, в противном случаевыполняется такт сдвига. В дальнейшем такты сдвига повторяются до техпор, пока содержимое двух старших 72 10разрядов регистра 2 не становится разным. Таким образом, общее количество тактов сдвига, выполняемых после такта сложения, равно количеству одинаковых цифр (нулей или единиц), содержащихся в старших дроб ных разрядах полученной суммы .Вычислениями можно установить, что математическое ожидание количе" ства следующих подряд тактов сдвига после такта сложения равно2 -1=,ЕР 1 й уур8 для достаточно больших и прЭто означает, что после каждого такта сложения в среднем выполняется 8/3 тактов сдвига, т.е. на каж. дые 8 разрядов частного приходится в среднем 3 такта сложения.Обозначив через Тсж - время выполнения такта сложения, а через Т э время выполнения такта сдвига, получаем. среднее время Т 0 вычисления Ч разрядов частного3Т = р пТс+ ПТсТаким образом, устройство сокращает, в среднем, количество тактовсложения до 37,53,Дальнейшее повышение быстродействия устройства, как и у прототипаможет быть получено путем аводадополнительных цепей сдвига регистров делимого и частного на два, трии т,д. разряда и соответствующегоувеличения количества анализируемыхразрядов регистра делимого.Следовательно быстродействие данного устройства, по крайней мере,не ниже чем у прототипа.Положительный эффект заключается в упрощении устройства, так какне требуется различных цепей образования цифр частного для остатковразличной величины.1048472 оставитель В,Березкиехред И,Тепер торре Бил едактор А,Долин аказ .7933/54 Тираж 706 ПодпиПИ Государственного комитета СССРделам изобретений и открытийМосква, Ж, Раушская наб., д. 4/5 е филиал ППП "Патент", г. Ужгород, ул. Проектная