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

ся n-разрядный двоичный код делит

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

Цель изобретения - повьппение бы- .стродействия устройства за счет сокращения длительности такта формирования k цифр частного и остатка.

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

10

без знака, прижатый к левой прани регистра 2, а к началу собственн деления в него записывается (n+k+ разрядов произведения п-разрядног делителя на (k+2) старших разрядо обратной величины, вычисленной по значению (k+3) принудительно окру ленных (увеличенных на единицу мла шего разряда) старших разрядов дел теля.

Сумматор 3 предназначен для хр нения частного. Он также участвуе

работы устройства.

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

6,регистр 7 старших разрядов делителя, сумматор 8 принудительного округления делителя, узел 9 вычисления обратной величины, второй коммутатор 10, второй 11 и первый 12 блоки умножения, блок 13 микропрограммного управления, входы данных 14 и синхронизации 15, вход 16 логической 1, выход, 17 частного, выход 18 регистра делимого, выход 19 старших разрядов регистра делимого, выход 20 регистра

7,выход 21 сумматора 8, выход 22 уза 9, выходы 23 и 24 коммутаторов 4

и 5, выход 25 регистра 2, выход 26 коммутатора 10, выходы 27 и 28 блоков 11 и 12, выход 29 вычитателя, выходы 30 - 36 блока 13. ,

Сумматор частного (фиг.2) содержит, входы 28,-28 (k+5) старших и (k-1) младших разрядов произведения блока 12, сумматор 37 и регистр 38.

Блок микропрограммного управления (фиг.З) содержит счетчик 39 и элемент 40 памяти микрокоманд.

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

Регистр 1 - (n+k+5)-paзpядньш, из которых один разряд расположен слева от запятой и п разрядов - справа от запятой. В исходном состоянии в этом регистре хранится п-разрядный двоичный код делимого без знака, а в процессе деления в него записываются значения остатков. Регистр 2 -(n+k+ +1)-разрядный, причем все разряды расположены справа от запятой. В регистре 2 в исходном состоянии хранится n-разрядный двоичный код делителя

при выполнении операции деления в процессе формирования правильного

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

Сумматор 3 предназначен для хранения частного. Он также участвует

0

значения частного. После завершения деления образованное в нем частное поступает на выход 17 частного устройства. Перед выполнением в устройстве собственно деления сумматор 3 обнуляется путем подачи с входа 15 устройства импульса на синхровход регистра 38 и разрешающего потенциа5 ла с -первого выхода 30 блока 13 управления на вход установки в О регистра 38. В процессе собственно деления в сумматоре 3 через шину 28, осуществляется прибавление к значению

Q младших разрядов содержимого регистра 38, которое подается на входы сумматора 37 со сдвигом влево (Е сторону старших разрядов) на (k-1) райря- дов, значения (k+5) старших разрядов 2(k+2)-разрядного произведения, сфор- мированного на выходах 28 блока 12. Младшие (k-1) разрядов этого произведения по шине 282 непосредственно поступают на информационные входы младших разрядов регистра 38„ Получившийся на выходах комбинационного сумматора 37 результат записывается без сдвига в соответствующие старшие разряды регистра 38. В (k-1) младших разрядов регистра 38 с шины 28 запи

0

5

0

5

сываются (k-1) младших разрядов произведения, сформированного на выходах 28 блока 12 умножения. Запись информации в регистр 38 производи :гся по синхроимпульсу при наличии разрешающего потенциала на его входе разрешения записи, который подключен к второму выходу 31 блока 13 управления.

С помощью коммутатора 4 осуществля- ется передача на информационные входы регистра 1 делимого либо делимого с входа 14 данных устройств, когда на первом вьпсоде 30 блока 13 формируется сигнал логической 1, либо остатка, образованного на выходах 29 вычитателя 6, когда на втором выходе 31 блока 13 формируется сигнал логической 1.

С помощью коммутатора 5 осущест- вляется передача на информационные входы регистра 2 делителя, либо делителя с входа 14 данных устройства, когда на шестом выходе 35 блока 13 формируется сигнал логической 1, либо произведения, образованного на выходах 27 блока 11, когда на седьмом выходе 36 блока 13 формируется сигнал логической 1. Первый 4 и второй 5 коммутаторы могут быть pea- лизованы на элементах 2И-2ИЛИ.

С помощью вычитателя 6 производится вычитание из значений текущего ос- татка, поступающего на входы умень- щаемого вычитателя 6 с выходов 18 разрядов регистра 1 делимого, и произведения , поступающего на входы вычитаемого вычитателя 6 с выходов 27 блока 11 умножения. Вычйтатель 6 - комбинационного типа с ускоренным распространением займа.

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

Пусть делимое х и делитель у - положительные нормализованные двоичные дроби, т.е. 1/2 X 1 и 1. Однако это справедливо только на первом шаге деления. В дальнейшем же, когда в роли делимого выступают промежуточные остатки, возможно нарушение нормализации делимого как влево, так и вправо. В общем случае делимое X в устройстве может изменяться в пределах О & к , Пусть х, - значение старших (k+3) разрядов делимого (остатка) у, - значение старших , (k+3) разрядов делителя; у, у, +2 - значение принудительно округленных (k+3) разрядов делителя; С - значение обратной величины от принудительно округленных старших (k+3) разрядов делителя (С 1/(у, + ),- С, - значение старших (k+2) разрядов об- ратной величины С.

В устройстве формирование k цифр частного Z производится путем вычисления произведения Z х, С,, старшие k разрядов которого и являются частным Z . Параллельно с формированием k цифр частного Z вычисляется и следующий остаток. Для этого в устройстве на подготовительном этапе

деления формируется произведение W делителя у на значение старших (k+2) разрядов обратной величины С, (W у С,). При выполнении собственно деления следующий остаток х вычисляется по формуле х X-W X, параллельно с вычислением kv цифр частного Z по формуле Z х,-С,.

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

X

чисел Z - и произведением Z X , С, ) при зтом заключается в преД .-(.-о

или

О - - X,- (С - С) Доказывают неравенство

. -х,(С-С,) ,

Максимальная погрешность будет

том случае, когда С С «-(k-O .

С учетом этого получают 2-х, l/(y, +

X

у, у

X,

.. 9

+

г ()

ч

X 9

+

):

Для доказательства этого неравенства достаточно доказать следующую систему неравенств:

X X (

у , 2

Левая часть в первом неравенстве принимает свое максимальное значени когда у О (т.е. у .у,), х

.Хма(1сс У мокс . - 2 .

С учетом этого первое неравенств можно переписать в виде

х(у, + ) - у, .х,2.у, X

X (у, + 2- или

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

.2-%,(у,+ ).

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

у .

- ( Kt-0

2

ли, что

2 - 2

5

у,(у

-и-э)

4- 2

)

Второе же неравенство указанной системы можно переписать в виде

х, 2.

Эти соотношения выполняются при всех значениях делителя у, заключенного в пределах 1/2 у - 1. Регистр 7 - (k+3)-разрядный и предназначен для хранения у, - старших (k+2) разрядов делителя у без знака.

Сумматор 8 является комбинационной

В блоке 12 осуществляется перемножение значения (k+2) старших разрядов обратной величины от принудительно 1Q округленного значения старших разрядов делителя, образованного на выходах 22 узла 9 и поступающего на первую группу входов блока 12, и значения старших (k+3) разрядов делимого.

схемой. В нем осуществляется принуди-15 поступающих с выходов 19 старших раз- тельное округление значения старших (k+3) разрядов делителя у путем прибавления единицу в его младщий разряд, поступающей на вход переноса сумматора 8 через вход 16 логической 1 устройства (т.е. в сумматоре 8 вычисляется значение у, + ), На выходах 21 сумматора 8 образуется значение старших разрядов делителя.

рядов регистра 1 делимого на группу входов блока 12. На выходах 28 блока 12 образуется 2(k+2)-разрядный результат, который подается на входы 2Q младших разрядов сумматора 3.

Блок 13 микропрограммного управления координирует работу узлов и блоков устройства при выполнении в нем операции деления чисел. Вход счета

увеличенное на единицу младшего раз-25 счетчика 39 соединен с входом 15 син- ряда. Этим самым устраняется возмож- хронизации устройства. В качестве

ность получения на выходах 28 блока 12 частного с избытком.

Узел 9 производит вычисление значения-старших (k+2) разрядов обратной величины С, от принудительного округленного значения старших разрядов делителя, поступающего на входы узла 9 с выходов 21 сумматора 8, На выходах 22 узла 9 формируется значение старших (k+2) разрядов обратной величины принудительно округленного усеченного делителя.

С помощью коммутатора 10 осуществляется передача на входы блока 11 либо значения старших (k+2) разрядов обратной величины от принудительно округленного значения старших разрядов делителя, обра;зованного на выходах 22 узла 9, когда на выходе 36 блока 13 формируется сигнал логичес

КОЙ 1, либо значения старших (k+3) разрядов делимого, поступающих с выходов 19 регистра 1, когда на втором выходе 31 блока 13 формируется сигнал логической 1.

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

3579466

старших разрядов делимого, поступающего на вторую группу входов блока 11 с выходов 26 коммутатора 10. На выходах 27 блока 11 умножения образуется произведение в однорядном коде,

В блоке 12 осуществляется перемножение значения (k+2) старших разрядов обратной величины от принудительно 1Q округленного значения старших разрядов делителя, образованного на выходах 22 узла 9 и поступающего на первую группу входов блока 12, и значения старших (k+3) разрядов делимого.

поступающих с выходов 19 старших раз-

рядов регистра 1 делимого на группу входов блока 12. На выходах 28 блока 12 образуется 2(k+2)-разрядный результат, который подается на входы младших разрядов сумматора 3.

Блок 13 микропрограммного управления координирует работу узлов и блоков устройства при выполнении в нем операции деления чисел. Вход счета

элемента 40 памяти микрокоманд может быть применена быстродействующая постоянная память емкостью (т+3) х 7,

где m

п

,т. в самом начале работы

гС I

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

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

Пусть на вход 14 данных устройства уже поступил п-разрядный двоичньш код делителя у, а счетчик 39 блока 13 установлен в исходное нулевое состояние. По содержимому счетчика 39, которое служит адресом обращения к элементу 40 памяти микрокоманд ешока 13, из элемента 40 памяти микрокоманд считывается микрокоманда 1,, которой соответствуют управляющие сигналы УЗЗ, У35 (фиг.4). В результате этого соответственно на четвертом 33 и шестом 35 выходах блока 13 устанавливаются уровни логической 1, Под действием этих управляющих сигналов второй коммутатор 5 пропускает на информационные входы регистра 2 делитель с входа 14, регистр 2 и регистр 7 подготовлены к приему информации, так как на их входах разрешения записи

присутствуют потенциалы логической

1. С приходом первого импульса на II

вход 15 устройства производится запись двоичного кода делителя у в регистр 2 и двоичного кода старших разрядов делителя у, в регистр 7, а также установка счетчика 39 блока 13 в состояние 1. С момента окончания

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

Во втором такте работы устройства из элемента 40 памяти микрокоманд считывается микрокоманда 2, которо соответствуют управляющие сигналы УЗО, У32, УЗЗ и У36. Б результате этого соответственно на первом 30, третьем 32, четвертом 33 и седьмом 36 выходах блока 13 устанавливаются уровни логической 1. Под действием этих управляющих сигналов коммутатор 4 пропускает на информационные входы регистра 1 делимое х с входа 14, регистр 1 подготовлен к приему информации, коммутатор 10 пропускает на входы блока 11 умножения значение старших разрядов обратной величины С,, сформированной на выходах 22 узл 9 по значению принудительно округленных в сумматоре 8 старших разрядов делителя у, , хранящихся в регистре 7. На выходе блока 11 формируется произведение п-разрядного делителя и значения старших разрядов обратной величины С I (W С, у),

-jg ших разрядов сумматора 3. Параллельно с работой блока 12 и сумматора 3 работает блок 11 и вычитатель 6. На выходах блока 11 формируется произведение величины W у С,, хранящей-

Под действием управляющего сигнала с выхода 36 блока 13 коммутатор 5 пропускает на информационные входы регистра 2 это произведение W С, у 40 регистре 2 и поступающей на вхо- с выходов 27 блока 11, а под действи- ды блока 11 с выходов 25 разрядов

регистра 2, на значение старших разрядов делимого х , хранящихся в регистре 1 и поступающих с его выходов 19 45 через коммутатор 10 на входы блока 11. В результате этого на выходах 27 блока 11 образуется значение х,-у-С,. Следующий остаток х формируется на выходах 29 вычитателя 6 по значению но 1 и 2, а также обнуление суммато- ц делимого х, поступающему на входы ра 3 и установка счетчика 39 блока 13 уменьшаемого вычитателя 6 с выходов в состояние 2. С момента окончания 18 разрядов регистра 1 и значению действия второго импульса на входе 15 произведения х,- у С,, поступающему

на входы вычитаемого вычитателя 6 с g(- выходов 27 блока 11 (х х - х,-У Х X С,). С приходом третьего импульса

ем управляющего сигнала с выхода 33 блока 13 регистр 2 подготовлен к приему информации. Кроме того, сумматор 3 настроен на обнуление. С приходом второго импульса на вход 15 синхронизации устройства производится запись двоичных кодов делимого х и произведения W в регистры соответственсинхронизации устройства заканчивается второй такт (и подготовительный этап) работы устройства и начинается собственно деление, в процессе которого в течение m тактов формируется m(k-1)+1 двоичных цифр частного.

на вход 15 синхр,онизации устройства в регистр 1 записывается сформированный на выходах 29 вычитателя 6 оста- .

I

йа

10

357946°

В первом такте собственно деления из элемента 40 памяти микрокоманд блока 13 считывается микрокоманда 3, которой соответствуют управляющие сигналы У31 и У32, и соответственно на выходах 31 и 32 блока 13 устанавливаются уровни логической 1. Под действием этих управляющих сигналов коммутатор 4 пропускает на инфор1мационные входы регистра 1 результат с выходов 29 вычитателя 6, регистр 1 и сумматор 3 подготовлены к приему информации, коммутатор 10 пропускает

15 на входы блока 11 значение старш1х разрядов делимого с выходов 19 регистра 1. Это позволяет произвести в устройстве следующие вычисления. По значению старших разрядов дели20 мого X (на следующих тактах в роли делимого будет выступать остаток, хранящийся в регистре 1 делимого) и значению старших разрядов обратной величины С, , сформированной на выхо25 дах 22 узла 9 по значению принудительно округленных старших разрядов делителя у,, хранящихся в регистре 7,

на выходах 28 блока 12 формируется произведение Z х, С,, старшие k

30 разрядов которого и являются k очередными цифраьш частного Z . Сформированное на выходах 28 блока 12 2(k+2)-разрядное произведение z поступает на информационные входы млад-jg ших разрядов сумматора 3. Параллельно с работой блока 12 и сумматора 3 работает блок 11 и вычитатель 6. На выходах блока 11 формируется произа40 регистре 2 и поступающей на вхо- - ды блока 11 с выходов 25 разрядов

ведение величины W у С,, хранящей-

регистре 2 и поступающей на вхо- ды блока 11 с выходов 25 разрядов

на вход 15 синхр,онизации устройства в регистр 1 записывается сформированный на выходах 29 вычитателя 6 оста- .

9

ток х , в регистр 38 сумматора 3 заносится результат сумматора 37, а счетчик 39 блока 13 устанавливается в состояние 3.

Аналогичным образом устройство работает и в других тактах. Однако в каждом такте значение произведения, сформированное на выходах 28.блока 12, подсуммируется к младшим разрядам содержимого сумматора 3, сдвинутого на (k-1) разрядов в сторону его старших разрядов, а остаток, образованный на выходах 29 вычитателя 6, поступает на информационные входы коммутатора 4 со сдвигом на (k-1) разрядов в сторону его старших разрядов.

После выполнения последнего (т+2) такта на выходе 17 частного устройства образуется п-разрядное частное. Одновременно с этим из элемента 40 памяти микрокоманд блока 13 считывается микрокоманда (т+3), которой соответствует управляюш 1й сигнал У34 и соответственно на пятом выходе 34 блока 13 устанавливается уровень логической 1, сигнализирующий об окончании операции деления.

13

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

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

, м , 15

20

25

35794610

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

30

35

40

45

50

55

JOJ132333 J5J6

Ф г г Т т г Т

.2

Изобретение относится к вычислительной технике и может быть применено для быстрого деления чисел в любой позиционной системе счисления. Целью изобретения является повьппение быстродействия устройства. Сна достигается за счет сокращения длительности такта работы устройства, содержащего регистры 1 и 2 делимого и делителя, сумматор 3 частного, коммутаторы 4, 5 и 10, вычитатель 6, регистр 7 старших разрядов делителя, сумматор 8 принудительного округления, узел 9 вычисления.обратной величины, блоки 11 и 12 умножения и блок 13 микропрограммного управления. 4 ил. СО сд со 1 о

JL /50-

/j

У30.узг,узз, yj6

сриг.з

y33,y3S

У31, узг

yj4

сриг.