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

11

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

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

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

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

Блок деления усеченных чисел (фиг.2) содержит ячейки 38-41 первого, второго, третьего и четвертого типов, соответственно, входы А, В, С Е, Q ячеек 38 первого типа D, R, S, Н, F, L ячеек 38 первого типа, входы X, У, Z, W ячеек 39 второг типа выходы V, U ячеек 39 второго типа, входы D1, D2, D3, D4, R1, R2, R3, ячеек 40 третьего типа, выходы К ячеек 40 третьего типа, входы N и М ячеек 41 четвертого типа, выходы Т и G ячеек 41 четвертого типа. I.

Блок управления (фиг.4) содержит

счетчик 42 и блок 43 памяти микрокоманд.

5

5

21

5

О

0 , 35

55

45

172

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

i

Сумматор 4 частного предназначен

для хранения частного. В первом такте деления сумматор 4 частного обнуляется путем подачи импульса с входа

14синхронизации устройства на его синхровход и разрешающего потенциала с первого вькода 33 блока 12 управления на вход разрешения установки

в нуль сумматора 4.частного. Во всех других тактах работ ы устройства в сумматоре 4 частного накапливается значение частного. Для этого к значению частного, сформированному на пре- дьщущих тактах работы устройства и сдвинутому на (k-1) разряд влево (в сторону старших разрядов), прибавляется значение k цифр частного, сформированных на выходах 26 второго коммутатора 11 в текущем такте. Запись результата этого суммирования в сумматор 4 частного производится по синхроимпульсу при наличии разрешающего потенциала на входе разрешения записи, который подключен к второму выходу 34 12 управления. После завершения деления образованное в сумматоре 4 частное поступает на выход

15частного устройства. Предполагается, что сумматор 4 частного реализован точно так же, как и в известном

3128

устройстве, т.е. на основе комбинационного сумматора и регистра.

Формирование k цифр частного на каждом такте работы предлагаемого устройства производится путем деления значения старших разрядов неприведенного остатка на значение старших газ- рядов делителя, увеличенное на единицу младшего разряда. Увеличение значения старших разрядов делителя на единицу младгаего разряда устраняет возможность получения в устройстве k цифр частного с избытком. Но, так как в предлагаемом устройстве при формировании k цифр частного используются старшие разряды неприведенного остатка, становится возможным образова- ние значения k цифр частного с избытком. Для исключения этого в устройстве предусмотрены два канала форми-

рования k цифр частного. Первый канал образован первым блоком 5 деления усеченных чисел. На его выходах 24 формируется k цифр частного путем р,е- ления старших разрядов неприведенного остатка на значение старших разрядов делителя, увеличенное на единицу младшего разряда, в предположении,

что после приведения остатка к одно- рядному коду в его старшие разряды не поступает сигнал переноса из младших разрядов. Второй канал включает второй блок 6 деления усеченных чисел. На его выходах 25 формируется k цифр частного путем деления старших разрядов неприведенного остатка на значение старших разрядов делителя, увеличенное на единицу младшего разряда, в предположении. Что после при- ведения остатка к однорядному коду в его старшие разряды поступает единичный сигнал переноса из младших разрядов. Выборка же необходимого значения k цифр частного осуществля- ется с помощью второго сумматора 11, который управляется сигналом, образо ванным на выходе 27 переноса в старшие разряды сумматора 10. Если сигнал на выходе 27 сумматора 10 соответст- вует логическому нулю, то второй коммутатор 11 передает на свои выходы 26 значение k цифр частного, сформированных в первом блоке 5 деления усеченных чисел, в противном случае на выходы 26 второго коммутатора 11 передается значение k цифр частного , образованных во втором блоке 6 деления усечённых чисел. Второй коммута174

тор 11 может быть реализован на элементах 2И-ИЛН.

Число старших разрядов делителя и остатка, необходимое для обработки в первом 5 и втором 6 блоках деления усеченных чисел для получения значения k цифр частного с точностью до единицы их младшего разряда, зависит от диапазона значений делимого и делителя . Пусть делимое х и делитель у - нормализованные положительные двоичные дроби, т.е. б 1 и . Разумеется, что это справедливо только на первом шаге деления. -,Б дальнейшем, когда в роли делимого выступают промежуточные остатки, возможно нарушение нормализации делимого как влево, так и вправо. В общем случае делимое х в предлагаемо устройстве может изменяться в пределах . При принятых допущения для получения на выходах 24 и 25 первого 5 и второго 6 блоков деления усеченных чисел k двоичных цифр частного с точностью до единицы их младшего разряда достаточно обработать (k+2) старших разрядов делимого х (один разряд - слева от запятой, а (k+1) разрядов - справа от запятой) и (k+2) старших разрядов делителя у (все разряды находятся справа от запятой) .. В первом блоке 5 производится деление значения старших (k+2) разрядов неприведенного остатка, поступающих на входы делимого первой и второй групп блока 5 с выходов 19 и 2 старших разрядов первого и второго регистров 1 и 2 соответственно, на значение старших (k+2) разрядов делителя, поступающих на входы делителя блока 5 с выходов 23 старших разрядов регистра 3, увеличенное на единицу младшего разряда, в предположении, что после приведения остатка к однорядному коду в его старшие разряды не поступает сигнал переноса из младших разрядов. В блоке 6 производится деление .значения старших (k+2) разрядов неприведенного остатка, поступающих на входы делимого блока 6 с выходов 19 и 20 старших разрядов регистров 1 и 2 соответственно, на значение старших (k+2) разрядов делителя, поступающих на входы делителя блока 6 с выходов 23 старших разрядов регистра 3, увеличенное на единицу младшего разряда, в предположении, что после приведения остатка к однорядному коду в его старшие разря512821

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

на единицу младшего разряда с весом 2-(к-0 ,

I10

Однотактная делительная матрица (фиг,2) выполняет деление (k+2)-pa3- рядного делимого, представленного в двухрядном коде, на (k+2)-разрядный делитель по методу без восстановления 5 остатка и без приведения переносов в остатках. Если цифра частного равна единице, то вычитание делителя из остатка производится прибавлением обратного кода делителя без прибавления 20 единицы в младший разряд. Если цифра частного равна нулю, то к значению остатка прибавляется значение прямого кода делителя с прибавлением единшда в младший разряд. Этим обеспечивается 25 увеличение значения делителя на единицу младшего разряда. Делимое поступает в матрицу по шинам 19 и 20 в двухрядном коде, делитель подается по шине 23. Матрица для деления реализо- ЗО вана на ячейках четьфек типов, Выходные сигналы ячейки 38 первого Tjma формируются по следующим булевым выражениям; F Q, Н С; S, А + В + +C+Q; D(A+B+C+ Q)&E; И 35 (А -I- В + С + Q) + Е; 1 L (А + В)& (с + Q) + А&В. Выходные сигналы ячейки 39 второго типа формируются по булевым выражениям: + Z + W. Выходные сигналы ячейки 40 40 третьего типа формируются по булевым выражениям; К D4 R3RR2&R1 -f D3&R3&X X R1 + D2&R1 + D1. Выходные сигналы ячейки 41 четвертого типа формируются по булевым выражениям; Т N + М; 45 G N + М. В первом блоке 5 на входы А и В младшей ячейки (типа 38) первой линейки матрицы с шины Р подается сигнал логического нуля, в блоке 6 на входы А и В младшей ячейки 38 пер- 50 вого типа первой линейки матрицы с шины Р подается сигнал логической единицы. Последним обеспечивается . увеличение значения старших разрядов неприведенного остатка на единицу 55 младшего разряда в блоке 6, в котором формируются k разрядов частного, в предположении, что после приведения остатка к однорядному коду в его ста176

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

С помощью сумматора 10 двухрядный код остатка, хранимый в первом 1 и втором 2 регистрах остатка, преобразуется в однорядный код. Если вычи- татель 9 реализован на одноразрядных двоичных вычитателях и в нем формируется остаток в двухрядном коде в виде разности и займа, то сумматор 10 фактически осуществляет операцию вычитания. Предполагается, что эта операция выполняется через суммирование. Для зтого необходимо информацию, по- ступающзто на его вход с выхода 18 регистра 2, проинвертировать, а на вход переноса сумматора 10 подать сигнал логической единицы (сумматор 10 комбинационного типа с ускоренным распространением переноса). На выход 27 переноса в старшие разряды сумматора 10 поступает сигнал переноса, образованный в разряде сумматора 10 с весом Этот же сигнал переноса поступает в разряд сумматора 10 с весом ,

Блок 12 управления координирует работу узлов и блоков устройства при выполнении в нем операции деления чисел. Счетчик 42 накапливающего типа и предназначен для естественной адресации микрокоманд. Вход счета счетчика соединен с входом 14 синхронизации устройства. В качестве блока 43 памяти микрокоманд может быть применена быстродействующая постоянная память емкостью (т+2) 5, где m г-т.

В caNJoM начале работы устройства счетчик 42 устанавливается в некоторое исходное состояние, например в ноль (на фиг.4 цепь установки счетчика 42 в исходное состояние не показана) .

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

Пусть на вход 13 устройства уже поступили п-разрядные двоичные коды делимого X и делителя у (здесь предполагается, что делимое и делитель Правильные положительные дроби), а счетчик 42 блока 12 управления установлен в исходное нулевое состояние. По содержимому счетчика 42, которое служит адресом обращения к блоку 43 памяти микрокоманд блока 12 управления, из памяти 43 считывается микрокоманда 1, которой соответствуют згаравляющие сигналы УЗЗ, У35, У36

fO

(фиг.З). В результате этого соответственно на первом 33, третьем 35 и четвертом 36 выходах, блока 12 управления устанавливаются уровни логиче- ской единицы. Под действием этих управляющих сигналов первый коммутатор 7 пропускает на информационные входы первого регистра 1 остатка делимое х с входа 13 устройства, регистры остатка 1 и делителя 3 подготовлены к приему информации, так как на их входах разрешения записи присутствуют потенциалы логической единицы, а второй регистр 2 остатка и сумматор 4 частного настроены на обнуление, С 5 приходом первого импульса на вход 14 синхронизации устройства производится запись двоичных кодов делимого х и делителя у в регистры 1 и 3 соответственно, а также обнуление второго 20 регистра 2 остатка и сумматора 4 частного и установка счетчика 42 блока 12 управления в состояние 1, С момента окончания действия первого имнал соответствует уровню логической единицы, то в качестве k-разрядного частного в устройстве используется значение k цифр частного, образован 5 ных на выходах блока 6, а если сигн переноса соответствует сигналу логи ческого нуля, то в качестве k-разряд ного частного в устройстве используется значение k цифр частного, сформированных на выходах блока 5, Сформированное на выходах второго коммутатора 11 k-разрядное частное Z (на следующих тактах - Е;,-где i - номер такта собственно деления) поступает на информационные входы младших разрядов сумматора 4, На выходах 29 и 3 блока 8 образуется в двухрядном коде произведение yZj, а с помощью вычи- тателя 9 формируется разность х - yZ в двухрядном коде, которая в дальней шем служит остатком и подается на ин формационные входы второй группы ком мутатора 7 и регистра 2 остатка со сдвигом на (k-1) разрядов влево (в

пульса на входе синхронизации устрой-- сторону старших разрядов), Одновременно с этим из блока 43 памяти микрокоманд блока 12 управления считы- вается микрокоманда 2, которой соответствуют управляющие сигналы У34, У35, и соответственно на втором и третьем выходах 34 и 35 блока 12 управления устанавливаются уровни ло гической единицы. Под действием упра вляющих сигналов коммутат ор 7 пропускает на информационные входы регист ра 2 остатка результат с выходов 31 вычитателя 9, регистры 1 и 2 остатка и сумматор 4 частного подготовлены к приему информации, С приходом второго импульса на вход 14 синхронизации устройства в регистры 1 и 2 остатка записывается сформированный на выходах 31 и 32 вычитателя 9 двухряд ный код остатка, в младшие разряды сумматора 4 частного заносятся k старших цифр частного, а счетчик 42 блока 12 упра.вления устанавливается в состояние 2,

ства заканчивается подготовительный этап и начинается собственно деление, в процессе которого в течение m тактов формируется m(k-1)+1 двоичных цифр частного.

В первом такте собственно деления по значению старших разрядов делимого X (на следующих тактах в роли делимого выступает остатокj хранящийся в регистрах 1 и2 в двухрядном коде) и делителя у на выходах первого блока 5 деления усеченных чисел формируется k двоичных цифр частного в предположении, что при приведении двухрядного кода текущего остатка в однорядный - код на сумматоре 10 не образуется сигнал переноса из младших разрядов остатка в старшие, а на выходах второго блока 6 деления усеченных чисел формируется k двоичных цифр частного в предположении, что при приведении двухрядного кода текущего остатка в однорядный код образуется сигнал переноса из младших разрядов остатка в старшие. Параллельно с работой блоков 5 и 6 работает сумматор 10, который преобразует двухрядный код текущего остатка в однорядный код. По значению сигнала переноса в старшие разряды этого сумматора (этот сигнал переноса образуется на выходе 27 сумматора 10) осуществляется окончательное формирование k цифр частного. Если этот сиг

нал соответствует уровню логической единицы, то в качестве k-разрядного частного в устройстве используется значение k цифр частного, образован- ных на выходах блока 6, а если сигнал переноса соответствует сигналу логического нуля, то в качестве k-разряд- . ного частного в устройстве используется значение k цифр частного, сформированных на выходах блока 5, Сформированное на выходах второго комму . татора 11 k-разрядное частное Z (на следующих тактах - Е;,-где i - номер такта собственно деления) поступает на информационные входы младших разрядов сумматора 4, На выходах 29 и 30 блока 8 образуется в двухрядном коде произведение yZj, а с помощью вычи- тателя 9 формируется разность х - yZ в двухрядном коде, которая в дальнейшем служит остатком и подается на информационные входы второй группы коммутатора 7 и регистра 2 остатка со сдвигом на (k-1) разрядов влево (в

сторону старших разрядов), Одновре

менно с этим из блока 43 памяти микрокоманд блока 12 управления считы- вается микрокоманда 2, которой соответствуют управляющие сигналы У34, У35, и соответственно на втором и третьем выходах 34 и 35 блока 12 управления устанавливаются уровни логической единицы. Под действием управляющих сигналов коммутат ор 7 пропускает на информационные входы регист- ра 2 остатка результат с выходов 31 вычитателя 9, регистры 1 и 2 остатка и сумматор 4 частного подготовлены к приему информации, С приходом второго импульса на вход 14 синхронизации устройства в регистры 1 и 2 остатка записывается сформированный на выходах 31 и 32 вычитателя 9 двухрядный код остатка, в младшие разряды сумматора 4 частного заносятся k старших цифр частного, а счетчик 42 блока 12 упра.вления устанавливается в состояние 2,

Аналогичным образом устройство работает и в других тактах. При этом в каждом такте старшая двоичная ццф- ра из k очередных цифр частного, образованных на выходах 26 второго коммутатора 11 и поступающих на информационные входы младших разрядов сумматора 4, подсуммируется к младшему двоичному разряду содержимого сумматора 4, сдвинутому на (k-1) раз-

912821

рядов в сторону его старших разрядов,

После выполнения последнего (т+1) такта на выходе 15.частного устрой- с ства образуется п-разрядное частное, на выходе 16 остатка устройства образуется п-разрядный остаток. Одновременно с этим из блока 43 памяти микрокоманд блока 12 управления считыва- tO ется микрокоманда (т+2), которой соответствует управляющий сигнал У37, и соответственно на пятом выходе 37 блока 12 управления устанавливается уровень логической единицы, сигнали- 5 Jиpyющий об окончании операции деления .

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

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

O 5

0

5 О с 0 5 Q

710

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

ZMZSi

чшг.г

щщузв

/3,35

-f 1

ч

l

m+2

У

/«

оФиг 3

Редактор О.Бугир

Составитель Н.Маркелова

Техред Л.Сердюкова Корректор М.Пожо

Заказ 7267/47Тираж 670 Подписное

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

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

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

33 3 353637

( I о о о I

/ S А у у / V / .

12

3

2

фиг.

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