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

«3

4

з«

fivf.i

Изобретение относится к вычислительной технике и может быть использовано в быстродействующих арифметических устройствах для выполнения операции деления чисел. : Цель изобретения - повышение jбыстродействия устройства. На фиг.1 приведена структурная схема устройства для деления чисел; на фиг.2 - функциональная схема второго коммутатора; на фиг.З - функ- :циональная схема блока управления; I на фиг.4 - микропрограмма работы i устройства.

Устройство для деления содержит |(фиг.1). регистр 1 делимого, регистр 2 делителя, сумматор 3 частного, блок 4 умножения, вычитатели 5-7, сумматор 8 принудительного округле- ния делителя, коммутатор 9, блок 10 деления усеченных чисел, состоящий из узла 11 вьмисления обратной величины и узла 12 умножения, регистр 13 цифр частного, коммутатор 14, бло 15 управления, шину 16 данных устройства, вход 17 синхронизации устройства, вход 18 логической единицы устройства, выход 19 частного устройства, выходы 20 регистра 1 делимого, выходы 21 регистра 2 делителя, выходы 22 старших разрядов регистра 2 делителя, выходы 23 сумматора 8 приндительного округления делителя, выходы 24 узла 1 1 вычисления обратной величины, выходы 25 коммутатора 9, выходы 26 узла 12 умножения (они же являются и выходами блока 10 деления усеченных чисел), выходы 27 регистра 13 цифр частного, выходы 28 и 29 пер вой и второй групп блока 4 умножения соответственно, выходы 30 и 31 разноти и заема вычитателя 5 соответственно, выходы 32 и 33 старших разрядов разности и заема вычитателя 5 соот- ветственно, выходы 34 вычитателя 6, выходы 35 младших разрядов вычитателя 7, выход 36 старшего разряда вычитателя 7, выходы 37 коммутатора 14, выходы 38 старших разрядов шины 16 данных устройства, выходы 39-43 с первого по пятый блока 15 управления соответственно.

Коммутатор 9 содержит элементы 2И-ЗИ-21 ШИ 44 (фиг.2).

Блок 15 управления может быть выполнен в виде совокупности счетчика 45 и элементов 46 памяти микрокоманд . ,

, tO 5

0 5 30 Q

0

В блоке 10 деления усеченных чисел входы узла 11 вычисления обратной величины являются входами делителя блока 10, а выходы 24 соедине-, ны с входами первой группы узла 12 умножения, входы второй группы которого являются входами делимого блока ГО, выходы узла 12 умножения являются выходами 26 блока 10.

Регистры делимого 1 и делителя

2предназначены для хранения двоичных кодов соответственно делимого (остатков) и делителя. Регистр 1 делимого (п+1)-разрядный, из которых один разряд расположен слева от запятой, а остальные - справа от запятой.. Регистр 2 делителя содержит п разрядов, которые расположены справа от запятой. В первых двух тактах работы устройства в эти регистры загружаются п-разрядные двоичные коды делимого и делителя (сначала принимается делитель, а потом делимое) , которые являются правильными положительньми дробями, причем делимое загружается в п разрядов регистра 1, расположенных справа от запятой . Если в устройстве после завершения операции деления двух чисел не требуется формирование и запись в регистр 1 правильного конечного значения остатка, то разрядность регистра 1 может быть уменьшена на К-2 разряда. Это возможно потому, что в нем для формирования К очередных цифр частного используется значение остатка, сформированного на выходах 30 и 31 вычитателя 5 до записи его в регистр 1 делимого. В этом случае не должна производиться

и запись (К-3) старших разрядов делимого в регистр 1 с шины 16 данных устройства.

Предполагается, что все регистры устройства реализованы на основе двухтактных синхронных DV-триггеров. Запись информации в регистры производится по синхроимпульсу при наличии разрешающего потенциала на их V-входах.

Сумматор 3 частного предназначен для хранения частнот о.Он также участвует при выполнении операции деления в процессе формирования правильного значения частного. После завершения деления образованное в сумматоре

3частное поступает на выход 19 част3lA

ного устройства. Сумматор 3 частного может быть построен на основе комбинационного сумматора и регистра. Обнуление сумматора 3 производится путем подачи с входа 17 устройства импульса на его синхровход и разрешающего потенциала с второго выхода 40 блока 15 управления. Запись информации в сумматор 3 также осуществляется по синхроимпульсу при наличии разрешающего потенциала на его . входе разрешения записи, которьй подключен к третьему выходу 41 блока 15 управления.- В ходе вьтолнения собственно деления чисел в каждом такте работы устройства в сумматоре 3 осуществляется прибавление к его содер- жимому, сдвинутому на К-1 разряд в сторону старших разрядов, значения К очередных цифр частного, поступающего на входы его младших разрядов с выходов 27 регистра 13 цифр частного (старшая цифра из К очередных цифр частного является корректирующей для частного, сформированного к данному моменту в сумматоре 3 частного)

В блоке 4 осуществляется перемножение К-разрядного частного, сформированного на выходах 27 регистра 13 и поступающего на входы второй групп блока 4 умножения, и п-разрядного делителя, хранимого в регистре 2 и поступающего на входы первой группы ,блока 4 с выходов 21 регистра 2. На выходах 28 и 29 первой и второй групп блока 4 умножения образуется произведение в двухрядном коде (в виде двух чисел). Блок 4 может быть реализован в виде совокупности из п/К К-разрядньк двоичных умножителей.

С помощью первого вычитателя 5 формируется значение очередного остатка в двухрядном коде( на выходах 30 вычитателя 5 образуется значение разности, а на выходах 31 - значение заема остатка). На входы уменьшаемого вычитателя 5 поступает с выходов 20 регистра 1 значение текущего остатка, а на его входы вычитаемого и заема подается с выходов 28 и 29 блока 4 значение произведения делителя на К цифр частного в двухрядном коде. Вычитатель 5 - комбинационного типа без распространения эаема и может быть реализован на основе одноразрядных двоичных вычита- телей.

...

Вычитатель 6 осуществляет преобразование двухрядного кода очередного остатка, образованного на выходах 30 и 31 вычитателя 5, в однорядный код и является вычитателем комбинационного типа с распространением заема. С выходов 34 вычитателя 6 значение очередного остатка в однорядном

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

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

С помощью вычитателя 7, коммутатора 9, сумматора 8 принудительного округления делителя и блока 10 деления усеченных чисел, состоящего из узла 11 вычисления обратной величины и узла 12 умножения, в устройстве по значенью старших разрядов делимого (остатка) и делителя формируется К двоичных цифр частного, причем- его формирование происходит параллельно с работой вычитателя 6, на выходах 34 которого образуется значение очередного остатка в однорядном

коде. Можно показать, что если делимое X и делитель Y - правильные нормализованные двоичные дроби, т.е. 1/2 6 X,Y 1, то для получения в устройстве К очередных цифр частного (один разряд слева от запятой,

остальные справа от запятой) с точ-. костью до единицы их младшего разряда с весом достаточно обраба- тьюать в блоке 10 К +4 старших разряда остатка (один разряд слева от запятой, остальные разряды справа от запятой) и К + 3 старших разряда делителя (все разряды справа от запя той) . А чтобы значение зтих

К цифр частично не превышало истинное значение, т.е. чтобы оно было равно значению или бьто меньше его на единицу младшего разряда с весом

„-(ic-i)

2 , в сумматоре 8 осуществляется

принудительное увеличение значения старших разрядов делителя на единицу их младшего разряда, а в третьем вычитателе 7 производится принудительное уменьшение значения старших

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

Вычитатель 7 - комбинационного ипа с распространением заема. На

его входы уменьшаемого и вычитаемого с выходов 32 и 33 старших разряов первого вычитателя 5 подается значение К+5 старших разрядов разности и заема двухрядного кода очередного остатка, образованного на вы- ходах 30 и 31 вычитателя 5. На вы- ходах 35 вычитателя 7 образуются К + 4 младших разрядов (К+5)-раз- рядного результата, а на выходе 36 - старший разряд результата. Вход заема вычитателя 7 соединен с входом 18 логической единицы устройства, Фактически с помощью вычитателя 7 в устройстве осуществляется опере- жающее формирование значения К+4 старших разрядов очередного остатка в однорядном коде, так как малоразрядный вычитатель 7 работает значи- тельно быстрее многоразрядного вычи- тателя 6.

Сумматор 8 - (К+3)-разрядный ком- бинационного типа. На его вход переноса с входа 18 устройства поступает сигнал логической единицы с весом

(к+з) 2 . На выходах 23 сумматора 8

образуется (К+4)-разрядный результат (один разряд слева от запятой, а остальные разряды справа от запятой)

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

С помощью коммутатора 9 осуществляется передача на входы делимого блока 10 деления усеченных чисел значения (К+4)-разрядного 1сода делимого (один разряд слева от запятой, остальные разряды справа от запятой) . .На фиг,2 приведена функциональная схема этого коммутатора, содержащая К+4 логических элемента 2И-ЗИ-2ИЖ 44.

Коммутатор 9 работает следующим образом. Если на его первом управляющем входе, которьш подключен к второму выходу 40 блока 15 управления, присутствует сигнал логической единицы, то на выходы 25 коммутатора- 9 с выходов 38 старших разрядов входа 16 данных устройства передается значение К+3 старших разрядов делимого (все разряды справа от запятой) вместе., с нулевой целой частью (на выходе 38, присутствует потенциал логического нуля). Если же на второй управляющий вход коммутатора 9,который подключен к третьему вьгходу

- -

-170106

41 блока 15 управления, поступает сигнал логической единицы, а на его третьем управляю- шем входе, который соединен с выходом 36 старшего разряда вычитателя 7, присутствует сигнал логического нуля, то к его выходам 25 подключаются информационные входы первой груп- 10 пы, на которые подается с выходов 35 значение К+4 младших разрядов результата вычитателя 7 (один разряд слева от запятой, а все остальные разряды расположены справа от запятой).

15 Если же в этом случае на третьем равляющем входе коммутатора 9 присутствует сигнал логической едини- цы, то передача информации на его выходы 25 с информационных входов

20 первой группы блокируется, т.е. на выходах 25 коммутатора 9 формируется нулевой код 0,000...0.

В блоке 10 осуществляется деление (К+4)-разрядных двоичных чисел (один

25 их разряд расположен слева от запятой, а все остальные справа от запятой) с. образованием на выходах 26 К цифр.частного. В блоке 10 деление осуществляется путем умножения значе30 ния делимого на значение обратной величины делителя. Для этого блок 10 содержит комбинационный узел 11 вычисления обратной величины (на его .выходах 24 образуется (К+2)-разрядjg ный код старших разрядов обратной величины) и комбинационньш узел 12 умножения. Узел 11 . может быть реализован совнестно с сумматором В.на ПЗУ по соответствующей таблице истин40 ности. Блок 10 деления усеченных чисел может быть реализован и другими . способами, например, в виде одно- тактной матрицы, реализующей алгоритм деления с восстановлением или

45 без восстановления остатка.

Регистр 13 предназначен для временного хранения сформированных на выходах 26 блока 10 К очередных цифр частного. Запись в него информации

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

55

С помощью коммутатора 14 осуществляется передача на информационные входы регистра 1 либо делимого с шины 16 данных устройства, когда на

втором выходе 40 блока 15 управлени сформирован сигнал логической единицы, либо однорядного кода остатка с выходов 34 вычитателя 6, когда на выходе 41 блока 15 имеется сигнал единицы, коммутатор 14 может быть реализован на элементах 2И-21-ШИ.

Блок 15 управления координирует работу всех других узлов и блоков устройства при вьшолнении на нем операции деления чисел. Он может быть реализован самыми различными методами и средствами. На фиг.З в кчестве примера приведена реализация блока 15 управления на основе счетчика 45 и элементов 46 памяти микрокоманд. Счетчик 45 - накапливающего типа и предназначен для естественной адресации микрокоманд. Вход счета счетчика 45 соединен с входом 17 синхронизации устройства. В качестве элементов 46 памяти микрокоманд может быть применена быстродействующая постоянная память емкость

(М+3)«5, где М -|;7-I - число

тактов собственно деления, в течение которых в устройстве формируется М.(К-1) + 1 цифр частного; 3 ближайшее целое, большее или равное X. В самом начале работы устройства счетчик 45 устанавливается в некоторое исходное состояние, например, сбрасывается в О (на фиг.З цепь установки счетчика 45 в исходное состояние не показана). На фиг.4 показана микропрограмма работы устройства.

(

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

Пусть в исходном состоянии на шине 16 данных устройства присутствует п-разрядный двоичный код делителя Y без знака, а счетчик 45 блока 15 управления установлен в начальное нулевое состояние, Тогда на первом выходе 39 блока 15 управления сформирован единичньй сигнал, под действием которого регистр 2 5ели- теля подготовлен к приему инфррмации С приходом первого импульса на вход 17 синхронизации осуществляется запись двоич ного кода делителя Y в регистр 2 и установка счетчика 45 блока 15 управления в состояние 1. После завершения действия импульса на входе 17 синхронизации первый

17010°

такт работы устройства заканчивается.

Во втором такте работы устройства на втором 40 и четвертом 42 выходах блока 15 управления образуются сигналы логической единицы (см.микропрограмму на фиг.4, под действием которых в устройстве выполняются следую 0 Щие действия: первый коммутатор 14 пропускает на информационные входы регистра 1 значение делимого X с входа 16 данных устройства; коммутатор 9 пропускает на входы делимого

15 блока 10 деления усеченных чисел значение старших разрядов делимого с выходов 38 входа 16 данных устройства; на выходах 26 блока 10 деления формируется значение Z, самых стар20 ших К цифр частного Z; регистры 1 и 13 подготовлены к приему информации, а сумматор 3 частного - к обнулению. При поступлении второго импульса на вход 17 синхронизации

25 устройства осуществляется запись в регистр I значения делимого X, в регистр 13 - значения Z самых старших К цифр частного Z, сумматор 3 частного обнуляется,а счетчик 45

30 блока 15 управления переводится в состояние 2. По истечении действия второго импульса на входе 17 синхронизации второй такт работы устройства завершается, после чего начинаетое ся собственно деление чисел. 35 I

, В третьем такте (в первом из М тактов собственно деления) по содержимому счетчика 45 из элементов 46

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

5 фиг.4. Под действием этих управляющих сигналов в устройстве выполняются следующие действия: с помощью блока 4 умноженияформируется в двухрядном коде значение произведения

Q Y Z,, ас помощью первого 5 и второго 6 вычитателей на выходах 34 последнего образуется значение первого остатка X - Y.-Z J в однорядном коде, которое далее через первый коммутатор

g 14 передается на информационные входы регистра 1 со сдвигом на К-1 разряд в направлении старших разрядов; по значению старших разрядов разности и заема, образованному на выходах

91

32 и 33 вьгчитателя 5, на выходах 35 младших разрядов вьгчитателя 7 форми- ,руется значение старших разрядов однорядного кода первого остатка в предположении, что сигнал заема из 1 ладших разрядов полноразрядного о:статка равен единице, которое далее Предается через коммутатор 9 (если т{олько сигнал на выходе 36 старшего р}азряда вычитателя 7 не равен единиv. Це) на входы делимого блока О деле- н ия усеченных чисел, на выходах 26 которого и получается значение Zj,/ с1педугощих К двоичных цифр частного Z (|все эти действия вьшолняются одно- йременно с работой вычитателя 6), к С;одержимому сумматора 3 частного (;В этом такте содержимое сумматора 3 еще равно нулю), сдвинутому на К-1 разряд в сторону его старших разрядов, осуществляется прибавление значения Zj частного Z, которое хранит- с|я в течение третьего такта в регистре 13 цифр частного и подается на входы младших разрядов сумматора 3 частного; регистры 1 и 13 и сумма- fop 3 подготовлены к приему информа- Ции. Если на выходе 36 старшего раз- ряда вычитателя 7 сформирован сигнал логической единицы, то на вход делимого блока 10 деления усеченных чисел поступает нулевой.двоичный код. С приходом третьего импульса на вход 17 синхронизации устройства осуществляется запись в регистр 1 делимого значения первого остатка, в регистр 13 - значения Z очередных К двоичных цифр частного Z, в младшие разряды сумматора 3 частного записьша- ется значение Z самых старших К двоичных цифр частного Z, счетчик 45 блока 15 управления переводится в состояние 3. На этом третий такт работы устройства заканчивается и далее выполняется еще М-1 аналогичных тактов, в течение которых (включа я третий такт) формируется в сумматоре 3 частного м-(К-1)+1 двоичных цифр частного Z. В каждом из этих тактов старшая цифра из К очередных двоичных цифр частного , образованных на выходах 27 регистра 13 и поступающих на входы младших разрядов сумматора 3 частного, подсуммируется к младшему разряду содержащего сумматора 3, сдвинутому на К-1 разрядов в сторону его старших разрядов.

417010 ,10

После выполнения (М+2)-го такта на пятом выходе 43 блока 15 управления появляется сигнал логической еди- 5 ницы, сигнализирующей об окончании-в устройстве операции деления чисел.

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

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

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

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

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

45 принудительного округления делителя соединены с входами делителя блока деления усеченных чисел, синхровхо- ды регистров делимого и делителя, сумматора частного и блока управле5Q ния соединены с входом синхрониза- ции устройства, первый выход блока управления соединен с входом разрешения записи регистра делителя второй и третий выходы блока управ55 ления соединены с первым и вторым

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

11

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

J5/

58i

56

&

t

1701012

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

10 управляющими входами первого и второго коммутаторов, а вход разрешения записи - с вторыми управляющими входами первого и второго коммутаторов, выход старшего разряда третьего вы15 читателя соединен с третьим управляющим входом второго коммутатора, синхровход и вход разрешения записи регистра цифр частного соединены с синхровходом и входом разрешения

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

382SSff ff

S I &

4,

i

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

25 fuf.2

Ъ9 0 1 7 3

0/7

Pue.5

сриеЛ

/77