Устройство для деления Советский патент 1986 года по МПК G06G7/52 

f

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

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

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

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

1п v j младших 5 деления усеченных

жения, первьш вычитатель 7, второй вычитатель 8, коммутатор 9, блок 10 управления, входы 11 делимого, входы 12 делителя, вход 13 синхронизации, вход 14 логической 1, выходы 15 частного, выходы 16 разрядов регистр 1 делимого, выходы 17 старших дов регистра 1. делимого, выходы 18 разрядов регистра 2 делителя, выходы 19 старших разрядов регистра делителя , выходы 20 блока 5 деления усеченных чисел, выход 20f старшего разряда блока 5 деления усеченных чисел, выходы 20, (к - 1) разрядов блока чисел, выходы 21 первой группы блока 6 умножения, выходы 22 второй группы блока 6 умножения, выходы 23 разности второго вычитателя 8, выходы 24 заема второго вычитателя 8, ВЫХОДЫ 25 первого вычитателя 7, выходы 26 коммутатора 9,выходы 27 сумматора 4 принудительного округления делителя, первый, второй, третий, четвертый, пятый и шестой выходы 28-33 бдока 10 управления, седьмой выход 34 блока 10 управления (выход сигнализации окончания деления) , регистр 35, сумматор 36, одноразрядные двоичные вычитатели 37 -37 , счетчик 38, память 39 Микрокоманд.

Информационные входы первой груп ты коммутатора 9 соединены с входа- iviH 11 делимого устройства, информационные входы второй группы комму

татора 9 соединены с выходами 25 пе рвого вычитателя 7, выходы 26 коммутатора 9 соединены с информацион ными входами регистра 1 делимого, информационные входы регистра 2 делителя соединены с входами 12 делителя устройства, выходы 19 старших разрядов регистра 2 делителя соединены с входами сумматора 4 принудительного округления делителя, вход переноса которого соединен с входом 14 логической 1 устройства, выходы 27 сумматора 4 принудительного округления делителя соединены с входами

5 делителя блока 5 деления усеченных чисел, входы делимого которого соединены с выходами 17 старших разрядов регистра 1 делимого, выходы 20 блока 5 деления усеченных чисел соединены

0 с информационньми входами младших разрядов сумматора 3 частного и с входами первой группы блока 6 умножения, входы второй группы которого соединены с выходами 18 разрядов

5 регистра 2 делителя, входы уменьшаемого второго вычитателя 8 соединены с выходами 16 разрядов регистра 1 делимого, а его входы вычитаемого и займа соединены с выходами 21 и 22

0 первой и второй групп блока 6 умножения соответственно, выходы 23 и 24 разности и займа второго вычитателя 8 соединены с входами уменьшаемого и вычитаемого первого вычитателя 7

5 соответственно, синхровходы регистров 1 и 2 делимого и делителя, сумматора 3 частного и блока 10 управления соединены с входом 13 синхронизации устройства, первьй и второй выходы

0 28 и 29 блока управления соединены с первы1 и вторым управляющими входами коммутатора 9 соответственно, третий и четвертый выходы 30 и 31 блока 10 управления соединены с

5 входами разрешения записи регистров 1 и 2 делимого и делителя соответственно, пятый и шестой выходы 32 и 33 .блока 10 управления соединены с входами установки в О и разрешения записи сумматора 3 частного соответственно, седьмой выход 34 блока 10 , управления является выходом сигнализации окончания деления , выходы сумматора 3 частного являются выходами 15 частного устройства.

Рассмотрим функциональное назначение и реализацию основных узлов

0

5

и блоков предлагаемого устройства для деления.

Регистры 1 и 2 делимого и делителя соответственно предназначены для временного хранения двоичных кодов делимого (остатков) и делителя Регистр 1 делимого (п + 1)-разрядный из которых один разряд расположен слева от запятой и И разрядов справа от запятой. Регистр 2 делителя содержит и разрядов, которые все расположены справа от запятой. В первом такте деления в эти регистры загружаются двоичные коды делимого и делителя, которые являются правиль- ными положительными дробями. Регистры реализованы на основе двухтактных синхронных DV-триггеров. Запись информации в регистры производится по синхроимпульсу при наличии разрешающего потенциала на их V-входах.

Сумматор 3 частного предназначен для хранения частного, он также участвует при выполнении операции деления в процессе формирования пра вильного значения частного. После завершения деления образованное в нем частное поступает на выходы 15 частного устройства. Сумматор 3 частного содержит (фиг. 2) регистр 35 и комбинационньй двоичный сумматор 36 с ускоренным распространением пере- носа. Регистр 35 реализован на двухтактных синхронных DV-триггерах с возможностью их обнуления. В первом такте деления сумматор 3 обнуляется путем подачи с входа 14 устройства импульса на синхровход регистра 35 и разрешающего потенциала с пятого выхода 32 блока 10 управления на вход резрешения установки в О регистра 35. Во всех других тактах работы устройства в сумматоре 3 осуществляется прибавление к значению младшего разряда содержимого регистра 35, которое подается на входы сумматора 36 со сдвигом влево (в сторону старших разрядов) на (к-1) разрядов, значения старшего разряда к цифр частного, сформированных на выходах 20 блока 5 деления усеченных чисел. Это значение старшего разряда поступает на -вход переноса комбинационного сумматора 36 по выходу 20.. Получившийся на выходах

Т

комбинационного сумматора 36 результат записывается без сдвига в соответствующие старшие разряды регист10

15

495514

,ра 35. В ( к-1) младших разрядов регистра 35 с выходов 20j записьшаются (к-1) младших разрядов к цифр частного, сформированных на выходах 5 20 блока 5 деления усеченных чисел. Запись информации в регистр 35 производится по синхроимпульсу при наличии разрешающего потенциала на его , входе разрешения записи, который подключен к шестому выходу 33 блока 10 управления.

5

5

Сумматор 4 принудительного округления делителя и блок 5 деления усеченных (малоразрядных) чисел непосредственно участвуют в формировании очередных к двоичных цифр частного с точностью до единицы их младшего разряда. Сумматор 4 и блок 5 деления 0 усеченных чисел являются комбинационными схемами. В сумматоре 4 осуществляется принудительное округление делителя путем прибавления к значению старших разрядов делителя, поступаклдих на входы сумматора 4 с выходов 19 регистра 2, через вход 14 устройства единицы в их младший разряд. На выходах 27 сумматора 4 образуется значение старших разрядов делителя, увеличенное на единицу. Этим самьгм устраняется возможность получения на выходах 20 блока 5 деления усеченных чисел, в котором производится деление значения старших разрядов делимого на значение принудительно округленных старших разрядов делителя, частного-с избытком. Старшие разряды делимого поступают на входы делимого блока 5 с выходов 17 старших разрядов регистра 1 делимого, а принудительно округленные старшие разряды делителя подаются на входы делителя блока 5 с выходами 27 сумматора 4.

0

5

0

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

в виде быстрой поисковой таблицы, реализованной на ПЗУ. При больших же значениях К целесообразна реализация блока 5 в виде быстродействующей од- нотактной метричной схемы деления,

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

и другие варианты реализации блока 5 деления усеченных чисел.

Число старших разрядов операндов , обрабатываемых в блоке 5 деления усеченных чисел, определяется в зави- симости от диапазона значений, дели- мого и делителя. Пусть делимое х и делитель у - есть нормализованные положительные двоичные дроби, т.е. 1/2 х-С 1 и 1/2 у - 1 . ЭФо справед- ливо только на первом шаге деления. В дальнейшем, когда в роли делимого выступают промежуточные остатки, возможно нарушение нормализации делимого как влево, так и вправо. В общем случае делимое в предлагаемом устройстве может изменяться в пределах О 4- X 2.у. При принятых допущениях для получения на выходах 20 блока 5 деления усеченных чисел К двоичных цифр частного с точностью до единицы их младшего разряда достаточно обрабатывать (к - 2) старших разрядов делимого у один разряд слева от запятой и (к + 1) разряд справа от запятой и (к + 2) старших разрядов делителя у (все разряды находятся справа от запятой).

Пусть х значение старших (к+2) разрядов делимого У,1 значение старших (к+2) разрядов делителя у ;

- л Уг У У Максимальная абсолютная погрешность (разность между значением частного, получаемьм при делении И -разрядных чисел, и значением частного, получаемым при делении усеченных (к+2)-разрядных чисел) при этом заключена в пределах

п / f - „Ъ / 9-(к-1)

О i - У 9..2-

Вьтолнение левого условия очевид- tiOf поэтому ограничимся лишь доказательством неравенства

-(K-f)

л

2

у ) которое можно переписать в виде

)- X, у (i,+2--)

Х(

-С + г) .;-(14-1) / .о(гК

Максимальная абсолютная погрешность будет в том случае, когда yj О, т.е. а j,; х, ,

2 -2- X 2 М - 2

., -mdx y

- j 10 м is 20 25

12495516

С учетом этого получим

..., ,(«.

ИЛИ

(2у,-2-) +(2- V -2 У у,( у,+2- - ).

Последнее неравенство выполняется, если справедливо следующее

2, + , . . У/У,+ ) или, что

(.,, + ).

Последнее соотношение выполняется при всех значениях делителя у , заключенных в пределах у tl. I Следовательно 5 значение к-разряд- ного частного, получаемого на выходаХ| 20 блока 5 при делении в нем (к+2)- разрядных чисел, может быть либо равно значению старших К разрядов частного, получаемого при делении и-разрядных чисел, либо меньше его

на единицу младшего разряда с весом

2-{к-1(

В блоке 6 осуществляется перемножение к-разрядного частного,сформи- рованн ого на выходах 20 блока 5 и поступающего, на первую группу входов блока 6 умножения, и и-разрядного делителя, хранимого в регистре 2 и поступающего на вторую группу входов блока 6 с выходов 18 разрядов регистра 2. На выходах 21 и 22 первой и второй групп блока 6 образуется произведение в двухрядном коде (в виде двух чисел) . Биггок 6 умножения -комбинационного типа может быть реализован в виде совокупности из п/к К-разрядных двоичных умножителей.

С помощью первого вычитателя 7 производится вычитание из значения разности, сформированной на выходах 23 второго вычитателя 8, значения заема, образованного на выходах 24 второго вычитателя 8. Первьш вычи- татель 7 комбинационного типа с ускоренным распространением займа. Он может быть заменен быстродействующим сумматором, если информацию, поступающую на его вход вычитаемого, про7

инвертировать, а на вход переноса сумматора подать сигнал логической 1.

Второй вычитатель 8 комбинацион- ного типа выполнен по принципу запоминания заема. Он содержит (фиг. 3) одноразрядные двоичные вычитатели 37, -37j , где через Д , 6 , С обозначены входы уменьшаемого, вычитаемого и заёма соответственно. В вычи- тателе 8 осуществляется вычитание из содержимого регистра 1 делимого произведения , сформированного на выхода 21 и 22 блока 6 умножения в двухрядном коде. Результат вычитания образуется на выходах 23 и 24 разности и займа вычитателя 8 в двухрядном коде

С помощью коммутатора 9 осуществляется передача на информационные входы регистра 1 делимого с входов 11 устройства, когда на первом выходе 28 блока 10 управления формируется сигнал логической 1, либо остатка, образованного на выходах 25 первого вычитателя 7, когда на вто- ром выходе 29 блока tO управления формируется сигнал логической 1. Коммутатор 9 может быть реализован на элементах 2И-2Ш1И.

Блок 10 управления координирует работу узлов и блоков устройства при выполнении на нем операции деления двух чисел. Как и в известном устройстве он может быть реализован самыми различными методами и средО

ствами. На фиг. 4 в качестве примера приведена реализация блока 10 управления на основе счетчика 38 и памяти 39 микрокоманд. Счетчик 38 накапливающего типа предназначен для естественной адресации микрокоманд. Вход счета счетчика соединен с входом 13 синхронизации устройства. В качестве памяти 39 микрокоманд может быть применена; быстродействующая постоянная память емкостью С 7, где f - число тактов работы устройства. В самом начале работы устройства счетчик 38 устанайливается в некоторое исходное состояние, например сбрасывается (нафиг.4цепь установки счетчика 38 в исходное состояние не показана).

Граф-схема (фиг. 5) алгоритма работы блока 10 управления содержит вершины начала и окончания работы блока 10 по реализации в устройстве операции деления, а также (т+1)

495518

операторную вершину. Во время вьшол- нения первой операторной вершины в устройстве производится загрузка ис- Ходных операндов в регистры 1 и 2

5 делимого и делителя, а также обнуление сумматора 3 частного. Далее в устройстве выполняется гя однотипных вершин, в течение каждой из которых формируется К двоичных цифр част 0 ного. На фиг. 5 йриняты следующие обозначения управляющих сигналов (они соответствуют принятым ранее обозначениям выходов блока 10 управления) ;

5 у28 - управляющий сигнал, под действием которого на выходы 26 коммутатора 9 передается значение делимого с входов 11 устройства;

у29 - управляющий сигнал, под

20 действием которого на выходы 26 коммутатора 9 передается значение разности с выходов 25 первого вычитателя 7;

У 30 и у 31 - управляющие сигналы,

5 разрешающие запись информации в регистры 1 и-2 соответственно;

У 32 - управляющий сигнал, разрешающий еброс сумматора 3 частного в

0 л 33 - управляющий сигнал, разрешающий запись информации в сумматор 3 частного;

у 34 - управляющий сигнал, сообщающем об окончании операции;

5 m - число тактов, в течение которых формируется Нт(к-1) + 1 разрядное частное в сумматоре 3.

Устройство для деления работает следующим образом.

Пусть на входы 11 и 12 устройства уже поступили N-разрядные двоичные коды делимого X и делителя j (здесь предполагается, что делимое и делитель правильные положительные дро-,

5 би), а счетчик 38 блока 10 управления установлен в исходное нулевое состояние. По содержимому счетчика 38, которое служит адресом обращения к памяти 39 блока 10 управления, из

0 памяти 39 считьшается следующий двоичный код первой микрокоманды МК1 1011100. Старший разряд этого кода формируется на первом выходе 28 блока 10, а младший разряд образуется на

седьмом выходе 34 блока 10 управления. Под действием кода МК1 коммутатор 9 пропускает на информационные входы регистра 1 делимое X с входов

91

11 устройства, регистры 1 и 2 подготовлены к приему информации, так как на их входах разрешения записи присутствуют потенциалы логической 1, а сумматор 3 частного настроен йа обнуление. С приходом первого импульса на вход 13 синхронизации устройства производится запись двоичных кодов делимого X и делителя у в регистры соответственно 1 и 2, а также обнуление сумматора 3 частного и установка счетчика 38 блока 10 управления в состояние 1. С момента окончания действия первого импульса на входе 13 синхронизации устройства заканчивается подготовительный этап и начинается собственно деление, в процессе которого в течение t тактов формируется т-(к-1)+1 двоичных цифр частного.

В некоторых случаях можег оказаться целесообразньгм подготовитель- ньй этап организовать двзосш 1говым, причем на его первом шаге осуп1ествля ют запись только делителя iJ в регистр 2, а на втором шаге производят запись делимого в регистр 1 и обнуляют сумматор 3 частного. Этим самым обеспечивается меньшая длит ель ность такта работы устройства, так как временная задержка сумматора 4 принудительного округления делителя не влияет в этом случае на временный цикл работы устройства, В тех же случаях, когда операнды не могут быть загружены в регистры 1 и 2 одновременно (например, при последовательной их выборке из памяти), необходимо всегда производить в первую очередь запись делителя, а потом делимого.

В первом такте собственно деления по значению старших разрядов делимого ; и делителя у на выходах 20 блока 5 деления усеченных чисел формируются наиболее старшие k двоичных цифр z частного z, которые далее поступают на информационные входы 1«1падших разрядов сумматора 3. На выходах 21 и 22 блока 6 умножения образуются в двухрядном коде произведение уz , а с помощью первого и вто ,рого вычитателей 7 и 8 формируется разность x-yz , которая в дальнейшем служит первым остатком и подается на входы второй группы коммутатора 9 со сдвигом на (к-1)разрядов влево (в сторону старших разрядов). Одно

4955Г10

временно с этим из памяти 39 блока 10 считывается код второй- микрокоманды Ж2 0110010. С приходом второго импульса на вход 13 устройства в 5 регистр 1 делимого записывается сформированный на выходах 25 первого вычитателя 7 первый остаток, в млад- шие разряды сумматора 3 частного заносятся К старших цифр частного, а 10 счетчик 38 блока 10 управления устанавливается в состояние 2.

Аналогичным образом устройство работает и .в других тактах. В каждом. такте старшая цифра из К очередных цифр Частного, образованных на,выходах 20 блока 5 и поступающих на информационные входы младших разрядов сумматора 3 частного, подсумми- руется к младшему разряду содержимого сумматора 3, сдвинутому на (к-1) разрядов в сторону его старших разрядов. После выполнения последнего fn гго такта на седьмом выходе 34 блока 10

5

20

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

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

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

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

соединены с выходами старших разрядов регистра делимого, выходы блока деления усеченных чисел соединены с информационными входами младших раз11

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

Фи.1

49551 12

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

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

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

t5 умножения соответственно,выходы разности и займа второговычитателя соединены с входами уменьшаемого и вычитаемого первоговычитателя соответственно.

(ре/г.1

28 19 JO J/ J/ 7J 3

сриг.

Редактор Л. Гратилло

Фиг. 6

Составитель A. Клюев Техред В.Кадар

Заказ 4327/51

Тираж 671

ВНЙИПИ Государственного комитета. СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб. , д. 4/5

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

Корректор М, Шароши

Подписное

Изобретение относится к вычислительной технике и может быть применено в быстродействующих арифметических устройствах для выполнения операции деления чисел. Целью изобретения является повьппение быстро- действия устройства за счет сокращения длительности такта формирования К цифр частного и остатка (2((4 4 /2-разрядность делимого и делителя) . Устройство содержит регистры делимого и делителя, сумматор частного, сумматор принудительного округления делителя, блок деления усеченных чисел, блок умножения, два вычи- тателя, коммутатор и блок управления, причем информационные входы первой группы коммутатора соединены с входами делимого устройства, информационные входывторой группыкоммутатора -; с выходами первого вычитателя, выходы коммутатора - с информационньтми входами регистра делимого, информационные входы регистра делителя - с входами делителя устройства, выходы старших разрядов регистра делителя - с входами сумматора принудительного округления делителя, выходы которого соединены с входами делителя блока деления усеченных чисел,входы делимого которого соединены с выходами старших разрядов регистра делимого, выходы блока деления усеченных чисел соеди- нень с информационными входами младших разрядов сумматора частного и с входами первой группы блока умножения , входы второй группы которого соединены с выходами разрядов регистра делителя, входы уменьшаемого второго вычитателя соединены с выходами разрядов регистра делимого, а его входы вычитаемого и займа - с выходами первой и второй групп блока . . умножения соответственно, выходы разности и займа второго вычитателя - с входами уменьшаемого и вычитаемого первого вычитателя соответственно. Цель достигнута за счет введения в устройство второго вычитателя, выполненного как вычитатель с запоминанием займа, причем входы уменьшаемого второго вычитателя соединены с выходами разрядов регистра делимого, а его входы вычитаемого и займа - с выходами первой и второй групп блока умножения соответственно, выходы разности и займа второго вычитателя - с входами уменьшаемого и вычитаемого первого вычитателя соответственно. 6 ил. (Л