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

 

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

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

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

РЕСПУБЛИН

11 А1 (19) П1) (51) 4 G 06 F 7 52

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA

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

К A BTOPGHOMY СВИДЕТЕЛЬСТВУ Si„: (21 ) 3 921 201 /24-24 (22) 28.06.85 (46) 07.01.87. Бюл. Ф 1 (71) Минский радиотехнический институт (72) А.Г.Батюков и А.А.Штостак (53) 681.325(088.8) (56) Карцев M.À., Брик В.А., Вшчислительные системы и синхронная арифметика.- N.: Советское радио, 1981, с. 239-242, рис. 5.4.3, 5.4.4.

Авторское свидетельство СССР

Ф 1249551, кл. G 06 F 7/52, 1984. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ (57) Изобретение относится к вычислительной технике и может быть применено для выполнения операции деления чисел. Целью изобретения является повышение быстродействия за счет образования остатка в двухрядном коде за счет формирования в каждом цикле по значению старших рязрядов делителя и остатка нескольких цифр частного. Правильное формирование цифр частного в устройстве осуществляется с помощью двух блоков деления усеченных чисел, коммутатора и сумматора.

4 ил.

1282117

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

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

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

Устройство для деления содержит (фиг.1) первый 1 и второй 2 регистры остатка, регистр 3 делителя, сумма гор 4 частного, первый 5 и второй 6 блоки деления усеченных чисел, первый коммутатор 7, блок 8 умножения, вычитатель 9, сумматор 10, второй коммутатор 11, блок 12 управления, входы данных 13 и синхронизации 14 устройства, выходы частного 15 и остатка 16 устройства, выходы 17 и 18

25 первого и второго регистров остатка соответственно, выходы 19 и 20 старших разрядов первого и второго регистров остатка соответственно, выходы

21 первого коммутатора, выходы 22 ре- 30 гистра делителя, выходы 23 старших разрядов регистра делителя, выходы

24 и 25 первого и второго блоков деления усеченных чисел соответственно, выходы 26 второго коммутатора, выхо-. 35 ды 27 и 28 переноса в старшие разря ды и суммы сумматора 10 соответственно, .выходы .29 и 30 первой и второй группы блока умножения, выходы 31 и

32 разности и заема вычитателя, первый, второй, третий, четвертый и пятый выходы 33-37 блока управления.

Блок деления усеченных чисел

1 (фиг.2) содержит ячейки 38-41 первого, второго, третьего и четвертого типов, соответственно, входы А, В, С, Е, Q ячеек 38 первого типа выходы

D, R, S Н, Р, L ячеек 38 первого типа, входы Х, У, Z M ячеек 39 второго типа, выходы V U ячеек 39 второго типа, входы 01, D2, D3, D4, R1, В2, R3 ячеек 40 третьего типа, выходы К ячеек 40 третьего типа, входы N u N ячеек 41 четвертого типа, выходы Т и G ячеек 41 четвертого типа. 55

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

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

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

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

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

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

Формирование k цифр частного на каждом такте работы предлагаемого устройства производится путем деления.5 значения старших разрядов неприведенного остатка на значение старших разрядов делителя, увеличенное на единицу младшего разряда. Увеличение значения старших разрядов делителя на !О единицу младшего разряда устраняет возможность получения в устройстве k цифр частного с избытком. Но, так как в предлагаемом устройстве при формировании k цифр частного используются старшие разряды неприведенного остатка, становится возможным образова-, ние значения k цифр частного с избытком. Для исключения этого в устройстве предусмотрены два канала форми- 20 рования k цифр частного. Первый канал образован первым блоком 5 деленияусеченных чисел. На его выходах 24 формируется k цифр частного путем де25 ления старших разрядов неприведенного остатка на значение старших разрядов делителя, увеличенное на единицу младшего разряда, в предположении, I что после приведения остатка к однорядному коду в его старшие разряды не поступает сигнал переноса из младших разрядов ° Второй канал включает второй блок 6 деления усеченных чисел. На его выходах 25 формируется

k цифр частного путем деления старших разрядов неприведенного остатка на значение старших разрядов делителя, увеличенное на единицу младшего разряда, в предположении, что после приведения остатка к однорядному коду в его старшие разряды поступает единичный сигнал переноса из младших разрядов. Выборка же необходимого значения .k цифр частного осуществля- 45 ется с помощью второго сумматора 11, который управляется сигналом, образованным на выходе 27 переноса в старшие разряды сумматора 10. Если сигнал на выходе 27 сумматора 10 соответствует логическому нулю, то второй коммутатор 1! передает на свои выходы

26 значение k цифр частного,,сформированных в первом блоке 5 деления усеченных чисел, в противном случае на выходы 26 второго коммутатора 11 передается значение k цифр частного, образованнык во втором блоке 6 делег ния усеченных чисел. Второй коммутатор 11 может быть реализован на элементах 2И-ИЛИ.

Число старших разрядов делителя и остатка, необходимое для обработки в первом 5 и втором 6 блоках деления усеченных чисел для получения значения k цифр частного с точностью до единицы их младшего разряда, зависит от диапазона значений делимого и делителя. Пусть делимое х и делитель у — нормализованные положительные двоичные дроби, т.е, 1/2 с х - 1 и

1/2 у 1. Разумеется, что это справедливо только на первом шаге деления ° -,В дальнейшем, когда в роли делимого выступают промежуточные остатки, возможно нарушение нормализации делимого как влево, так и вправо. В общем случае делимое х в предлагаемом устройстве может изменяться в пределах 0 х с 2у. При принятых допущениях для получения на выходах 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, увеличенное на единицу младшего разряда, в предположении, что после приведения остатка к однорядному коду в его старшие раэря5 128211 ды поступает единичный сигнал переноса из младших разрядов. При этом значение k-разрядного частного, получаемого на выходах 26, может быть либо равно значению старших К разрядов частного, получаемому при делении и-разрядных чисел, либо меньше его на единицу младшего разряда с весом

2 - (х-

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

С помощью сумматора 10 двухрядный код остатка, хранимый в первом 1 и втором 2 регистрах остатка, преобразуется в однорядный код. Если вычитатель 9 реализован на одноразрядных двоичных вычитателях и в нем формируется остаток в двухрядном коде в виде разности и займа, то сумматор 10 фактически осуществляет операцию вычитания. Предполагается, что эта операция выполняется через суммирование.

Для этого необходимо информацию, поступающую на его вход с выхода 18 регистра 2, проинвертировать, а на вход переноса сумматора 10 подать сигнал логической единицы (сумматор

10 комбинационного типа с ускоренным распространением переноса). На выход

27 переноса в старшие разряды сумматора 10 поступает сигнал переноса, образованный в разряде сумматора 10 с весом 2 (" . Этот же сигнал переноса поступает в разряд сумматора 10 с весом 2

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

Однотактная делительная матрица (фиг.2) выполняет деление (k+2)-разрядного делимого, представленного в двухрядном коде, на (k+2)-разрядный делитель по методу без восстановления 15 остатка и без приведения переносов в остатках. Если цифра частного равна единице, то вычитание делителя из остатка производится прибавлением обратного кода делителя без прибавления 20 единицы в младший разряд. Если цифра частного равна нулю, то к значению остатка прибавляется значение прямого кода делителя с прибавлением единицы в младший разряд. Этим обеспечивается 25 увеличение значения делителя на единицу младшего разряда. Делимое поступает в матрицу по шинам 19 и 20 в двухрядном коде, делитель подается по шине 23, Иатрица для деления реализо- 30 вана на ячейках четырех типов. Выходные сигналы ячейки 38 первого типа формируются по следующим булевым выражениям: F = Q, Н = С; S, = Ai+ B +

+ C + Q; Р = (A + S + C + Q) &Z; К = З5 — (А + В + С + Q) + Е; I. = (А + В)& (С + Q) + A&8. Выходные сигналы ячейки 39 второго типа формируются по булевым выражениям . U Z U = х + у +

+ Z + M. Выходные сигналы ячейки 40 - 40 третьего типа формируются по булевым выражениям . К = Р4 КЗ&К2&К1 + РЗ&КЗ&х х К1 + D2&R1 + Р1. Выходные сигналы ячейки 41 четвертого типа формируются по булевым выражениям: Т = N + И; 45

С = Я + И. В первом блоке 5 на входы

А и В младшей ячейки (типа 38) первой линейки матрицы с шины P подается сигнал логического нуля, в блоке 6 на входы А и В младшей ячейки 38 пер- 50 вого типа первой линейки матрицы с шины P подается сигнал логической единицы. Последним обеспечивается . увеличение значения старших разрядов неприведенного остатка на единицу 55 младшего разряда в блоке 6, в котором формируются k разрядов частного, в предположении, что после приведения остатка к однорядному коду в его стаВ самом начале работы устройства счетчик 42 устанавливается в некоторое исходное состояние, например в ноль (на фиг.4 цепь установки счетчика 42 в исходное состояние не показана).

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

Пусть:на вход 13 устройства уже поступили и-разрядные двоичные коды делимого х и делителя у (здесь предполагается, что делимое и делитель правильные положительные дроби), а счетчик 42 блока 12 управления установлен в исходное нулевое состояние.

По содержимому счетчика 42, которое служит адресом обращения к блоку 43 памяти микрокоманд блока 12 управления, as памяти 43 считывается микрокоманда "1", которой соответствуют управляющие сигналы УЗЗ, У35, У36

7 1282 (фиг.3). В результате этого соответственно на первом 33, третьем 35 и четвертом 36 выходах, блока 12 управления устанавливаются уровни логической единицы. Под действием этих управляющих сигналов первый коммутатор

7 пропускает на информационные входы первого регистра 1 остатка делимое х с входа 13 устройства, регистры остатка 1 и делителя 3 подготовлены к 10 приему информации, так как на их входах разрешения записи присутствуют потенциалы логической единицы, а второй регистр 2 остатка и сумматор 4 частного настроены на обнуление. С приходом первого импульса на вход 14 синхронизации устройства производится запись двоичных кодов делимого х и делителя у в регистры 1 и 3 соответственно, а также обнуление второго 20 регистра 2 остатка и сумматора 4 частного и установка счетчика 42 блока

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

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

5 деления усеченных чисел формируется

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

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

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

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

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

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

Устройство для деления, содержащее первый регистр остатка, регистр делителя, сумматор частного, первый блок деления усеченных чисел, блок умножения, вычитатель, первый комму- 25 татор, блок управления, причем вход ,данных устройств соединен с информа .) ционным входом регистра делителя и с первой группой информационных входов первого коммутатора, выход которого Зр соединен с информационным входом первого регистра остатка, выходыстарших разрядов которого соединены с первой группой входов делимого первого блока деления усеченных чисел, выход регистра делителя соединен с первой группой входов блока умножения, выходы первой и второй групп которого соединены с первой и второй группьйи входов вычитаемого вычита- 40 теля соответственно, входы синхронизации первого регистра остатка, регистра делителя, сумматора частного и блока управления соединены с входом синхронизации устройства, первый выход блока управления соединен с первым управляющим входом первого коммутатора и с входом установки в "0" сумматора частного, второй выход блока управления соединен с вторым упра-50 вляющнм входом первог, коммутатора и с входом разрешения записи сумматора

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

1282117

1282117,у д дуюз

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

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

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

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

ВНИИЛИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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