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

 

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

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

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

РЕСПУБЛИН (19) (11) (51)4 G 06 F 7 52

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4157142/24-24 ,(22) 05.1 2.86 (46) 15.08.88.Бюл. И 30 (71) Минский радиотехнический институт (72) А.Г.Батюков и А.А.Шостак (53) 681.325 (088.8) (56) Карцев М.А.. Арифметика цифровых машин, М.: Наука, 1969, с.494, рис.5-1.

Патент США И - 3234367, кл.235-156, 1962.

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

2 делителя, сумматор 3 частного, блок 4 умножения, вычитатели 5,6, сумматор 8 принудительного округления делителя, блок 10 деления усеченных чисел, коммутатор 14 и блок

l5 управления, а также вновь введенные вычитатель 7, коммутатор 9 и регистр 13 цифр частного с соответствующими связями. С помощью введенных в устройство блоков и связей обеспечивается более высокое его быстродействие за счет некоторого распараллеливания вычислительного процесса. 4 ил.! 4170! 0

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

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

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

: устройства. 15

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

-: (фиг.1). . регистр 1 делимого, регистр

: 2 делителя, сумматор 3 частного, блок 4 умножения, вычитатели 5 — 7, сумматор B принудительного округле- 20 ния делителя, коммутатор 9, блок 10 деления усеченных чисел, состоящий, из узла 11 вычисления обратной величины и узла 12 умножения, регистр

1 3 цифр частного, коммутатор 14, блок 25

15 управления, шину 16 данных уст. ройства, вход 17 синхронизации уст— ройства, вход 18 логической единицы устройства, выход 19 частного устройства, выходы 20 регистра 1 делимого, 30 выходы 21 регистра 2 делителя, выходы 22 старших разрядов регистра 2 делителя, выходы 23 сумматора 8 принудительного округления делителя, выходы 24 узла 11 вычисления обратной величины, выходы 25 коммутатора 9, - выходы 26 узла 12 умножения (они же являются и выходами блока !О деления усеченньм чисел), выходы 27 регистра

13 цифр частного, выходы 28 и 29 пер- 40 вой и второй групп блока 4 умножения соответственно, выходы 30 и 31 разности и заема вычитателя 5 соответственно, выходы 32 и 33 старших разрядов разности и заема вычитателя 5 соот- 4 ветственно, выходы 34 вычитателя 6, выходы 35 младших разрядов вычитателя 7, выход 36 старшего разряда вычитателя 7, выходы 37 коммутатора 14, выходы 38 старших "разрядов шины 16 данных устройства, выходы 39 — 43 с первого по пятый блока 15 управления соответственно.

Коммутатор 9 содержит элементы

2И-ЗИ-2ИЛИ 44 (фиг.2) .

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

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

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

2 предназначены для хранения двоичных кодов соответственно делимого (остатков) и делителя. Регистр 1 делимого (n+1) pàçðÿäíbé, из которых один разряд расположен слева от запятой, а остальные — справа от запятой. Регистр 2 делителя содержит и разрядов, которые расположены справа от запятой. В первых двух тактах работы устройства в эти регистры загружаются и-разрядные двоичные коды делимого и делителя (сначала принимается делитель, а потом делимое), которые являются правильными положительными дробями, причем делимое загружается в и разрядов регистра 1, расположенных справа от запятой. Если в устройстве после завершения операции деления двух чисел не требуется формирование и запись в регистр 1 правильного конечного значения остатка, то разрядность регистра 1 может быть уменьшена на К-2 разряда. Это возможно потому, что в нем для формирования К очередных цифр частного используется значение остатка, сформированного на выходах 30 и 31 вычитателя 5 до записи его в регистр 1 делимого. В этом случае не должна производиться и запись (К-3) старших разрядов делимого в регистр 1 с шины 1 6 данных устройства.

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

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

V-входах.

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

3 частное поступает на выход 19 част3 14170 ного устройства. Сумматор 3 частного может быть построен на основе комбинационного сумматора и регистра.

Обнуление сумматора 3 производится путем подачи с входа 17 устройства импульса на его синхровход и разрешающего потенциала с второго выхода

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

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

С помощью первого вычитателя 5 формируется значение очередного остатка в двухрядном коде(на выходах 30 вычитателя 5 образуется значение разности, а на выходах 31 значение заема остатка). На входы уменьшаемого вычитателя 5 поступает с выходов 20 регистра 1 значение 5> текущего остатка, а на его входы вычитаемого и заема подается с выходов

28 и 29 блока 4 значение произведения делителя на К цифр частного в двухрядном коде. Вычитатель 5 — комбина55 ционного типа без распространения заема и может быть реализован на основе одноразрядных двоичных вычитателей.

Вычитатель 6 осуществляет преобразование двухрядного кода очередного остатка, образованного на выходах

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

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

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

I коде. Можно показать, что если делимое Х и делитель Y - правильные нормализованные двоичные дроби, т.е.

1/2 6 Х,7 < 1, то для получения в устройстве К очередных цифр частного (один разряд слева от запятой, остальные справа от запятой) с точ-, ностью до единицы их младшего раэря4 да с весом 2 " 1 достаточно обрабатывать в блоке 10 К +4 старших разряда остатка (один разряд слева от запятой, остальные разряды справа от запятой) и К + 3 старших разряда делителя (все разряды справа от запятой). А чтобы значение этих

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

-(к- )

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

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

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

14170 его входы уменьшаемого и вычитаемого с выходов 32 и 33 старших разрядов первого вычитателя 5 подается значение К+5 старших разрядов раз5 ности и заема двухрядного кода очередного остатка, образованного на вы ходах 30 и 31 вычитателя 5. На выходах 35 вычитателя 7 образуются

К + 4 младших разрядов (K+5)-разрядного результата, а на выходе 36 старший разряд результата. Вход заема вычитателя 7 соединен с входом

18 логической единицы устройства.

Фактически с помощью вычитателя 7 15 в устройстве осуществляется опережающее формирование значения К+4 старших разрядов очередного остатка в однорядном коде, так KBK малоразрядный вычитатель 7 работает значи- 20 тельно быстрее многоразрядного вычитателя 6.

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

-(М

2 . На выходах 23 сумматора 8 образуется (К+4)-разрядный результат (один разряд слева от запятой, а ВО остальные разряды справа от запятой)

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

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

2И-ЗИ-2ИЛИ 44.

Коммутатор 9 работает следующим образом. Если на его первом управляющем входе, который подключен к второму выходу 40 блока 15 управления, присутствует сигнал логической единицы, то на выходы 25 коммутатора 5р

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

10 6

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

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

Если же в этом случае на третьем уп" равляющем входе коммутатора 9 присутствует сигнал логической единицы, то передача информации íà его выходы 25 с информационных входов первой группы блокируется, т.е. на выходах 25 коммутатора 9 формируется нулевой код 0,000...0.

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

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

ПЗУ по соответствующей таблице истинности. Блок 10 деления усеченных чисел может быть реализован и другими способами, например, в виде однотактной матрицы, реализующей алгоритм деления с восстановлением или без восстановления остатка.

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

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

I

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

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

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

17 синхронизации осуществляется запись двоичного кода делителя 7 в регистр 2 и установка счетчика 45 бло" ка 15 управления в состояние "1".

После завершения действия импульса на входе 1/ синхронизации первый

7 1417 втором выходе 40 блока 15 управления, сформирован сигнал логической единицы, либо однорядного кода остатка с выходов 34 вычитателя 6, когда на

5 выходе 41 блока 15 имеется сигнал единицы, коммутатор 14 может быть реализован на элементах 2И-2ИЛИ, Блок 15 управления координирует работу всех других узлов и блоков устройства при выполнении на нем операции деления чисел. Он может быть реализован самыми различными методами и средствами. На фиг.3 в качестве примера приведена реализация блока 15 управления на основе счетчика 45 и элементов 46 памяти микрокоманд. Счетчик 45 — накапливающего типа и предназначен для естественной адресации микрокоманд, Вход счета счетчика 45 соединен с входом 17 синхронизации устройства. В качестве элементов 46 памяти микрокоманд может быть применена быстродействующая постоянная память емкостью 25 ! п-1 (М+3) ° 5 где M = J — --- — число

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

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

Во втором такте работы устройства на втором 40 и четвертом 42 выходах блока 15 управления образуются сигналы логической единицы (см.микропрограмму на фиг,4), под действием которых в устройстве выполняются следующие действия: первый коммутатор 14 пропускает на информационные входы регистра 1 значение делимого Х с входа 16 данных устройства; коммута" тор 9 пропускает на входы делимого блока 10 деления усеченных чисел значение старших разрядов делимого с выходов 38 входа 16 данных устройства; на выходах 26 блока 10 деления формируется значение Е, самых старших К цифр частного Z; регистры 1 и 13 подготовлены к приему информации, а сумматор 3 частного — к обнулению. При поступлении второго импульса на вход 17 синхронизации устройства осуществляется запись в регистр 1 значения делимого Х, в регистр 13 — значения Z самых старших К цифр частного Z сумматор 3 частного обнуляется, а счетчик 45 ! блока 15 управления переводится в состояние "2". По истечении действия второго импульса на входе 17 синхронизации второй такт работы устройства завершаешься, после чего начинается собственно деление чисел.

В третьем такте (в первом иэ М тактов собственно деления) по содержимому счетчика 45 из элементов 46 памяти микрокоманд считывается третья микрокоманда, которой соответствуют сигналы логической единицы на третьем 4! и четвертом 42 выходах блока

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

7 Z а с помощью первого 5 и второго 6 вычитателей на выходах 34 последнего образуется значение первого остатка Х вЂ” Y Z в однорядном коде, которое далее через первый коммутатор

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

1417010 .

5Î

32 и 33 вычитателя 5, на выходах 35 младших разрядов вычитателя 7 форми,руется значение старших разрядов однорядного кода первого остатка в предположении, что сигнал заема из младших разрядов полноразрядного астатка равен единице, которое далее передается через коммутатор 9 (если только сигнал на выходе 36 старшего разряда вычитателя 7 не равен едини це) на входы делимого блока 10 деления усеченных чисел, .на выходах 26 которого и получается значение Z следующих К двоичных цифр частного Z („:;все эти действия выполняются одновременно с работой вычитателя 6), к содержимому сумматора 3 частного ив этом такте содержимое сумматора

3 еще равно нулю), сдвинутому на К-1 разряд в сторону его старших разрядов, осуществляется прибавление знаЧения Z частного 2, которое хранится в течение третьего такта в регистре 13 цифр частного и подается на входы младших разрядов. сумматора 3 частного; регистры 1 и 13 и сумматор 3 подготовлены к приему информации. Если на выходе 36 старшего разряда вычитателя 7 сформирован сигнал логической единицы, то на вход делимого блока 10 деления усеченных чисел поступает нулевой. двоичный код.

C приходом третьего импульса на вход

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

13 — значения Е очередных K двоичных цифр частного Z, в младшие разряды сумматора 3 частного записывается значение Z самых старших К двоичных цифр частного Z счетчик

45 блока 15 управления переводится в состояние "3" . На этом третий такт работы устройства заканчивается и далее выполняется еще М-1 аналогичных тактов, в течение которых (включая третий такт) формируется в сумматоре 3 частного (М (К-1)+lj двоичных цифр частного Z, В каждом из этих тактов старшая цифра из К очередных двоичных цифр частного,i образованных на выходах 27 регистра 13 и поступающих на входы младших разрядов сумматора 3 частного, подсуммируется к младшему разряду содержащего сумматора 3, сдвинутому на К-1 разрядов в сторону его старших разрядов.

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

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

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

14170! О

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

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

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

l 4I 70I 0

Составитель В.Березкин

Редактор E.Êîï÷à Техред Л.Олийнык Корректор JI,Ïèëèïåíêo

Заказ 4067 /48 Тираж 704 Подписное

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

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

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