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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (11) 57946 А1 (51) 4 G 06 F 7/52

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ. (21) 3997908/24-24 (22) 30. 12. 85 (46) 07. 12.87. Бюл. ¹ 45 (71) Минский радиотехнический институт (72) А.Г.Батюков и А.A.Øoñòàê (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 802962, кл. G 06 F 7/52,.1978.

Авторское свидетельство СССР № 1322264, кл. G 06 Р 7/52, 1985. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ (57) Изобретение относится к вычислительной технике и может быть применено для быстрого деления чисел в любой позиционной системе счисления.

Целью изобретения является повышение быстродействия устройства. Она достигается за счет сокращения длительности такта работы устройства, содержащего регистры 1 и 2 делимого и делителя, сумматор 3 частного, коммутаторы 4, 5 и 10, вычитатель 6, регистр

7 старших разрядов делителя, сумматор 8 принудительного округления, узел 9 вычисления. обратной величины, блоки 11 и 12 умножения и блок 13 микропрограммного управления. 4 ил.

1 13579

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

5 деления чисел.

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

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

Устройство для деления (фиг.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 блоков

i1 и 12, выход 29 вычитателя, выходы

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

12, сумматор 37 и регистр 38.

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

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

Регистр 1 — (и+Е+5)-разрядный, из .которых один разряд расположен слева от запятой и и разрядов — справа от

50 запятой. В исходном состоянии в этом регистре хранится и-разрядный двоичный код делимого без знака, а в процессе деления в него записываются значения остатков. Регистр 2 †(n+k+

+ 1)-разрядный, причем все разряды расположены справа от запятой. В регистре 2 в исходном состоянии хранит46 2 ся п-разрядный двоичный код делителя беэ знака, прижатый к левой границе регистра 2, а к началу собственно деления в него записывается (и+К+1) разрядов произведения п-разрядного делителя на (k+2) старших разрядов обратной величины, вычисленной по значению (k+3) принудительно округ-. ленных (увеличенных на единицу младшего разряда) старших разрядов делителя.Сумматор 3 предназначен для хранения частного, Он также участвует при выполнении операции деления в процессе формирования правильного значения частного. После завершения деления образованное в нем частное поступает на выход 17 частного устройства. Перед выполнением в устройстве собственно деления сумматор 3 обнуляется путем подачи с входа 15 устройства импульса на синхровход регистра 38 и разрешающего потенциала с первого выход» 30 блока 13 управления на вход установки в "0" регистра 38. В процессе собственно деления в сумматоре 3 через шину 28, осуществляется прибавление к значению младших разрядов содержимого регистра 38, которое подается на входы сумматора 37 со сдвигом влево (в сторону старших разрядоз) на (k-1) разрядов, значения (k+5) старших разрядов

2(k+2) -разрядного произведения, сформированного на выходах 28 блока 12.

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

28 блока 12 умножения. Запись информации в регистр 38 производи"..ся по синхроимпульсу при наличии разрешающего потенциала на его входе разрешения записи, который подключен к второму выходу 31 блока 13 управления. С помощью коммутатора 4 осуществляется передача на информационные входы регистра 1 делимого либо делимого с входа 14 данных устройств, когда на первом выходе 30 блока 13 формируется сигнал логической "1", либо осФ

3 13579 татка, образованного на выходах 29 вычитателя 6, когда на втором выходе 31 блока 13 формируется сигнал логической "1".

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

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

Пусть делимое х и делитель у — положительные нормализованные двоичные дроби, т.е. 1/2 «с х (1 и 1/2 у с1.

Однако это справедливо только на первом шаге деления. В дальнейшем же, когда в роли делимого выступают промежуточные остатки, возможно нарушение нормализации делимого как влево, так и вправо. В общем случае делимое х в устройстве может изменяться в 40 пределах 0 « х <2у. Пусть х, — значение старших (k+3) разрядов делимого (остатка); у, — значение старших

- v > (k+3) разрядов делителя, у, у, +2 значение принудительно округленных 45 (k+3) разрядов делителя; С вЂ” значение обратной величины от принудительно округленных старших (k+3) разрядов делителя (С = 1/(у, + 2 ); С, значение старших (k+2) разрядов об- 50 ратной величины С.

В устройстве формирование k цифр

1 частного Z производится путем вычис I ления произведения Z = х< С,, старшие Е разрядов которого и являются

1 частным Z . Параллельно с формироваt нием k цифр частного Z вычисляется и следующий остаток. Для этого в устройстве на подготовительном этапе

И

Z х чисел 2 =—

=х, С) прн делах и произведением этом заключается в преФ л -(к-))

-"2-2 i2 или

-х (K-i)

0 E= — — х (С вЂ” С )(2 у (1

Доказывают неравенство

Я=--х (С-С) с2

X -(K i) у 1 2

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

B ToM спучае. когда С т С2 макс = — 2

С учетом этого получают — — х 1/(у + 2 ) — 2 (2-("-) или х — (к )

+ 2 ° x<

2 -«+»

< 2-(K-t)

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

+ 2-як+э) (-(Kti) -к

2 х,<2

Левая часть в первом неравенстве принимает свое максимальное значение, когда y = 0 (T.e. y =.y„), х -б

=.ахмакс 2у 2 э + = х макс =

2-lKi )

С учетом этого первое неравенство можно переписать в виде х(у,+2 ) -у, ° х,<2 ° у, х х(у,+2" )

„(к+э) или

Последнее неравенство выполняется, если справедливо следующее деления формируется произведение W делителя у на значение старших (k+2) разрядов обратной величины С, (W

= у C ) . При выполнении собственно деления следующий остаток х вычисляf ется по формуле х = х — W х, параллельно с вычислением k „ цифр частного

Z по формуле Z" "= х, С,.

C=-С-С,,x =x-õ,,ó

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

13579

5

2 (к+0 2 к (+ 2() ) ! или что у 2 - 2

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

Эти соотношения выполняются при всех значениях делителя у, заключенного в пределах 1/2 у 1. Регистр

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

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

"1" устройства (т.е. в сумматоре 8 вычисляется значение у, + 2 ) ..

-(к+з)

На выходах 21 сумматора 8 образуется значение старших разрядов делителя, увеличенное на единицу младшего раз- 25 ряда. Этим самым устраняется возможность получения на выходах 28 блока

12 частного с избытком.

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

22 узла 9 формируется значение старших (k+2) разрядов обратной величины

35 принудительно округленного усеченного делителя.

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

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

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

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

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

Блок 13 микропрограммного управления координирует работу узлов и блоков устройства при выполнении в нем операции деления чисел. Вход счета счетчика 39 соединен с входом 15 синхронизации устройства. В качестве элемента 40 памяти микрокоманд может быть применена быстродействующая постоянная память емкостью (m+3) х 7, и где m = ††. В самом начале работы

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

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

Пусть на вход 14 данных устройства уже поступил п-разрядный двоичный код делителя у, а счетчик 39 блока 13 установлен в исходное нулевое состояние. По содержимому счетчика 39, которое служит адресом обращения к эле-, менту 40 памяти микрокоманд блока 13, из элемента 40 памяти микрокоманд считывается микрокоманда "1"., которой соответствуют управляющие сигналы

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

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

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

1 1 вход 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 формируется произведение и-разрядного делителя и значения старших разрядов обратной величины С, (W = C< у).

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

3 настроен на обнуление. С приходом второго импульса на вход 15 синхронизации устройства производится запись двоичных кодов делимого х и произведения Ы в регистры соответственно 1 и 2, а также обнуление сумматора 3 и установка счетчика 39 блока 13 в состояние "2". С момента окончания действия второго импульса на входе 15 синхронизации устройства заканчивается второй такт (и подготовительный этап) работы устройства и начинается собственно деление, в процессе которого в течение m тактов формируется

m(k-1)+1 двоичных цифр частного.

t0

В первом такте собственно деления из элемента 40 памяти микрокоманд блока 13 считывается микрокомачда 3, которой соответствуют управляющие сигналы У31 и У32, и соответственно на выходах 31 и 32 блока 13 устанавливаются уровни логической I""..

Под действием этих управляющих сигналов коммутатор 4 пропускает на инфор мационные входы регистра 1 результат с выходов 29 вычитателя 6, регистр 1 и сумматор 3 подготовлены к приему информации, коммутатор 10 пропускает на входы блока 11 значение старших разрядов делимого с выходов 19 регистра 1. Это позволяет произвести в устройстве следующие вычисления.

По значению старших разрядов делимого х (на следующих тактах в роли делимого будет выступать остаток, хранящийся в регистре 1 делимого) и значению старших разрядов обратной величины С<, сформированной на выходах 22 узла 9 по значению принудительно округленных старших разрядов делителя у,, хранящихся в регистре 7, на выходах 28 блока 12 формируется

И произведение Z = х, С,, старшие разрядов которого и являются Е оче-! редными цифрами частного Z . Сформированное на выходах 28 блока 12

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

11. В результате этого на выходах 27 блока 11 образуется значение х, у С<.

Следующий остаток х формируется на выходах 29 вычитателя 6 по значению делимого х, поступающему на входы уменьшаемого вычитателя 6 с выходов

18 разрядов регистра 1 и значению произведения х, у С,, поступающему на входы вычитаемаго вычитателя 6 с выходов 27 блока 11 (х = х — х, у ° х

I х С,) . С приходом третьего импульса на вход 15 синхронизации устройства в регистр 1 записывается сформированный на выходах 29 вычитателя 6 оста9 13579 ток х,, в регистр 38 сумматора 3 заносится результат сумматора 37, а счетчик 39 блока 13 устанавливается в состояние "3".

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

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

После выполнения последнего (m+2) такта.на выходе 17 частного устройст-, ва образуется и-разрядное частное.

Одновременно с этим из элемента 40 памяти микрокоманд блока 13 считывается микрокоманда (m+3}, которой со.— ответствует управляющий сигнал У34 25 и соответственно на пятом выходе 34 блока 13 устанавливается уровень логической "1", сигнализирующий об окончании операции деления.

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

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

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

Ю 71 32Л345536