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

1

соединены с выходами частного устрой- ; ства, вьгходы разрядов первого регист- Iра остатка соединены с входами уменьшаемого второго вычитателя, входы вычитаемого которого соединены с выходами разрядов второго регистра остатка, выходы разности второго вычитателя соединены с входами Уменьшаемого третьего вычитателя и соединены с выходами остатка устройства, выходы разрядов регистра делителя соединены с входами вычитаемого третьего вычитателя и входами второй группы блока умножения, выходы первой)и второй групп которого соединены с входами |вьгчитаемого первой и второй групп первого вычитателя соответственно, вход синхронизации устройства соединен с синхровходами регистра частного первого и второго регистров остатка и с первым входом блока управления, второй вход которого соединен с пер- 1вым управляющим входом узла коррек- |ции частного и с выходом заема старше :го разряда третьего вычитателя, третий вход блока управления соединен с выходом старшего разряда коммутатора блока деления усеченных чисел, первый выход блока управления соеди09

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

1

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

Цель изобретения - сокращение ко- личества оборудования.

На чертеже представлена схема уст- )ройства для деления чисел.

Устройство содержит первый регистр I остатка, второй регистр. 2 остатка, регистры 3 и 4 делителя и частного, блок 5 деления усеченных чисел, сумматор 6 принудительного округления делителя блока 5, первый и второй вы- читатели 7 и 8 блока 5, первый и вто- рой узлы 9 и 10 деления блока 5, ком- гутатор 11 блока 5, блок 12 умножения первьгй, второй и третий вычитатели 53- 15, первый и второй коммутатору. 16 k 17, узел 18 коррекции частного, блок 19 управления, входы 20 и 2 данных и синхронизации, выходы 22 и 23 остатка.

и частного, шины 24 и 25, логической единицы и логического нуля, выходы 26- разрядов регистра 1, выходы 27 старших разрядов регистра 1, выходы 28 разрядов регистра 2, выходы 29 старших разрядов регистра 2, выходы 30 разрядов регистра 3, выходы 3 старших разрядов регистра 3, выходы 32 коммутатора 11, выходы 33 коммутато- ра 11 за исключением старшего разряда, выход 34 старшего разряда коммутатора 11, выходы 35 разности вычитателя 14, выход 36 заема в старшие разряды вычитателя 14, выход 37 заема старшего разряда вычитателя 15, выходы 38 разности вычитателя 15, выходы

39разрядов коммутатора 17, выходы

40и 41 первой и второй групп блока 12, выходы 42 и 43 разности и заема вычитателя 13, выходы 44 NuiaAinnx ра з- рядов регистра 4, выходы 45 узла 18, выходы 46-31 блока 19.

Выходы разрядов 26 первого регистра I остатка соединены с входами уменьшаемого второго нычнтателя 14, входы вычитаемого которого соединены с выходами разрядов 28 второго регистра 2 остатка, выходы 35 разности второго вычитателя 14 соединены с входами уменьшаемого третьего вычитателя 15, с информационными входами первой группы второго коммутатора 17 и являются выходами 22 остатка устройства, выходы 30 разрядов регистра делителя 3 соединены с входами вьши- таемого третьего вычитателя 15 и с входами второй группы блока 12 умножения, выходы 40 и 41 первой и второй групп блока 12 умножения соединены с входами вычитаемого первой и второй групп первого вычитателя 13 соответ- ственно, выходы 35 разности третьего вычитателя 15 соединены с входами второй группы второго коммутатора 17, выходы 39 второго коммутатора 17 соединены с входами уменьп аемого перво- го вычитателя 13 и с информационными входами третьей группы первого коммутатора 16, вход 20 данных устройства соединен с информационными входами регистра делителя 3 и с инфор- мационными входами первой группы первого коммутатора 16, информационные входы второй группы которого соединены с выходами 42 разности первого вы- читателя 13, выходы первого коммутатора 16 соединены с информационными входами первого регистра 1 остатка, информационные §ходы второго регистра 2 остатка соединены с выходами 43 займа первого вычитателя 13, выходы 31 старших разрядов регистра 3 делителя соединены с входами сумматора 6 принудительного округления делителя блока 5 деления усеченных чисел, вход переноса сумматора принудительного округления делителя 6 блока 5 подключен к шине 24 логической единицы, а-выходы соединены с входами делителя первого и второго узлов 9 и 10 деления блока 5, входы делимого которых соединены с выходами первого и второго вычитателей 7 и 8 блока 5 соответственно, входы уменьшаемого первого и второго вычитателей 7 и 8 блока 5 соединены с выходами 27 старших разрядов первого регистра 1 ос татка, их входы вычитаемого соединены с выходами 29 старших разрядов второго регистра 2 остатка, входы

,

т о 15 20 , 25зо35

45

50

55

займа первого р, второго вычитателей 7 и 8 блока 5 подключены к иинлм 24 и 25 логической единицы и нуля соответственно, выходы первого и второго узлов Ч и 10 деления блока 5 соединены с информационными входами первой и второй групп коммутатора 11 блока 5 соответственно, выход займа в старшие разряды 36 второго вычитателя 14 соединен с управляющим входом ко(му- татора 1 1 блока 5., выходы 33 которого, за исключением старшего разряда, соединены с информационными входами первой группы блока 12 умножения и с информационными входами первой . группы узла 18 коррекции частного, иН(1юрмационные входы второй группы которого соединены с выходами 44 младпих разрядов регистра 4 частного, выходы 45 узла коррекции частного соединены с информационньп {и входами младших разрядов регистра 4 частного, выходы разрядов которого являются выходом 23 частного устройства, вход 2 синхронизации устройства соединен с синхровходом регистра 4 частного, первого и второго регистров 1 и 2 остатка и с первым входом блока 19 управления, второй вход которого соединен с первым управляющим входом узла 18 коррекции частного, управляющим входом второго коммутатора 17 и с выходом 37 займа старшего разряда третьего вычнтателя 15, третий вход блока 10 управления соединен с выходом старшего разряда 34 коммутатора 11 блока 5, первый выход 46 блока 19 управления соединен с синхровходом-регистра делителя 3 и с входом установки в нуль первого регистра 1 остатка, второй, третий и четвертый выходы 48- 50 блока 19 управления соединены с первым, вторым и третьим управляющими входами первого коммутатора 16 соответственно, пятый выход блока 19 управления является выходом сигнализации окончания деления устройства, шестой выход 47 блока 19 управления соединен с входом установки в нуль второго регистра 2 остатка, седьмой выход 51 блока 19 управления соединен с вторым управляюгдим входом узла 18 коррекции частного,

Первьй регистр 1 остатка (п+1)- разрядный, из которых один разряд расположен слева от занятой и п разрядов справа от занятой. В исходном состоянии в этом регистре хранится п-раз514

рядньй дво1Г1Ньгй код делимого оез зна- рса, а в процессе деления в него за- исьгоамтся значения разности очеред- ых остатков, формируемых в устройст- ре в двухрядном коде (в виде двух чиселг первое число является разность остатка, а второе - его займом). Второй регистр 2 остатка содержит п разрядов, на которых один расположен еле за от занятой, а (п-1)-- справа, В сходном состоянии этот регистр обнулено Регистры 3 и 4 делителя и частно о п-разрядные, причем в регистре 3 делителя все разряды расположены спра ,за от занятой, а в регистре 4 частно- : о один разряд находится слева от }анятой, а (п-1) разрядов - справа от занятой. В регистре 3 делителя в исходном состоянии хранится п-разряд- :1ьй двоичный код делителя без знака. Регистр 4 частного в исходном состоянии не обнуляется. Разрядность указанных регистров и расположенные в них информации могут быть и нес- колько иными. Регистры I - 4 построены на основе двухтактных синхронных D-триггеров с асинхронными установоч ними входами. Регистр 4 частного имеет цепи однотактного сдвига, влево на (Кг1) разрядов.

Блок 5 деления усеченных (малораз-- рядных} чисел предназначен для формирования по значению определенного числа старших разрядов делителя и остатка К цифр частного с точностью до единицы их младшего разряда. Все узлы блока 5 комбинационного типа, В сумматоре 6 осуществляется принудительное округление делителя путем прибавления к значению его старпих разрядов, поступающих на входы сумма- трра 6 с выходов 31 регистра 3 делителя единигда в их младший разряд (срг- нал логической единицы постоянно подается на вход переноса сумматора 6 с шины 24 устройства), На выходе сумматора 6 образуется значение старших разрядов делителя, увеличенное на единицу. Этим самым устраняется возможность получения на выходах 32 блока 5 из-за отбрасывания младших разрядов делителя значения К цифр частного с избытком. Но так как в блоке 5 при формировании К цифр частного используются старшие разряды не- приведенного остатка (представленного в двухрядном коде), то становится возможным образование на выходах 32

Q . 20 5 JQ

- (5

0

15

096

блока 5 значения К цифр частного с избытком. Для исключения этого в блоке 5 деления усеченных чисел предус-. мотрены два канала формирования нифрч частного. Первый канал образован сумматором 6, первым вычитателем 7 и первым узлом 9 деления На выходах первого узла 9 деления формируются К цифр частного в предположении, что после проведения остатка к однорядному коду в его старшие разряды поступает единичный сигнал займа из млад- ших разрядов (на вход займа первого вьгчитателя 7 подан с шины 24 устройства сигнал логической единицы),: Второй канал включает тот же сумматор принудительного окрзтления делителя 6, а также второй вычитатель 8 и второй узел 10 деления. На выходах второго узла 10 деления формируется К цифр частного в .предположении, что после приведения остатка к однорядному коду в его старшие разряды поступает нулевой сигнал займа из младших разрядов (на вход займа второго вьгчитателя 8 подан с шины 25 устройства сигнал логического нуля), Выборка обходимого значения К цифр частного и подача его на выходы 32 блока 5 осуш,ествляется с помощью коммутатора 11, который управляется сигналом на выходе 36 займа в старшие разряды второго вычитателя 14, Если сигнал

на выходе 36 второго вычитателя 14 соответствует логической единице, то коммутатор 11 передает на выходы 32 блока 5 значение К цифр частного, сформированньк в первом узле 9 деления, в противном случае на выходы 32

блока 5 передается значение К цифр г

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

71

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

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

1 ,1 ,

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

Покажем, что при принятых допущениях, для получения на выходах 32 блока 5 деления усеченных чисел двоичных цифр частного с точностью до единицы их младшего разряда, достаточно обрабатывать (К+2) старших, разрядов делимого X (один разряд слева от занятой и (К+1)-й разряд справа от занятой) и (К+2) старпих разрядов делителя у (все разряды находятся справа от занятой).

Действительно, пусть К - значение старших (К+2) разрядов делимого х,у, значение старших (К+2) разрядов делителя у, х, х - х,} у у - у.Подсажем, что максимальная абсолютная погрешность (разность между значением частного, полученным при делении п- разрядных чисел и значением частного, получаемым при делении усеченных (К+2)-разрядных чисел) при этом будет заключаться в пределах

1--- .

у у, + /.

Выполнение левого условия очевидно, поэтому ограничимся лить доказательстнеравенства

X Х(

У У, -) 2

-(1с-И

которое мопяо переписать в виде

X ,,-(г . „-( х(у, -I- ;. ) - х,у 2 у «

-(ч-2) У, 2 .).

098

Нетрудно видеть, что м-чксимальная абсолютная погрепность ь будет в том

случае, когда у, П, т.е. у у, ; у - V - ;-(: О j- o ,,

2 /- , X MCTir

-. 2. с учетом этого получим:

J

„-(к.г) -(4) .. . Х 2 + , 2 У| (У, +2 )

или

-1 . „-(гч

(2у, -2 ).2 +(2 -

.) У, (у, + 2 )

Последнее неравенство будет выполняться, если справедливо следующее

(

; 1

jn

js -

30

0

0

5

-(k + 2)

или 1 2(у, +2 ).

Последнее соотношение выполняется при всех значениях делителя у, зак1 ,

люченных в пределах , следовательно, значение К-разрядного частного, получаемого на выходах 32 блока 5 при делении в нем (К+2)-разрядных чисел, может быть либо равно значению старших К разрядов частного, получаемого при делении п-разрядных чисел, либо MeHbDje его на единицу 1№адшего разряда с весом .

В блоке умножения осуществляется перемножение (К-1) младших разрядов частного, сформированного на выходах 35 блока 5 деления усеченных чисел и поступающего на входы первой группы блока 12 умножения, и п-разрядно- го делителя, хранимого в регистре 3 и поступающего на входы второй группы блока 12 умножения с выходов разрядов 30 регистра делителя 3. На выходах 40 и 41 первой и второй групп блока 12 образуется произведение в двухрядном коде (в виде двух чисел). Блок 12 умножения комбицационного типа.

Первый вычитатель 13 комбинационного типа и выполнен по принципу за- пояинания заема. Как и в известном устройстве он содержит (п+1) одноразрядных вычитателей, Б первом вычита- теле 13 осуществляется вычитание из разности, сформированной на выходах 39 второго коммутатора 17, произведения делителя на (К-1) цифру частного, образованного в двухрядном коде на .выходах 40 и 41 первой и второй групп

914

:блока 12 умноженияt Результат этого вычитания, являющийся очередным ос- ITHTKOM, получается на выходах 42 и A3 разности и заема вычитателя 13 в двух рядном коде.

Второй и третий вьгчитатели 4 и ;15 комбинационного типа с ускоренным ;распространением заема. С помощью второго вычитателя 14 двухрядный код ос- Iтатка, хранящийся в первом и втором регистрах Г и 2 остатка в виде разности и заема, преобразуется в одно- рядньй код. На выход 36 второго вычитателя 14 поступает сигнал заема, о® разованный в разряде вычитателя с весом 2 . Этот сигнал заема поступает в разряд вычитателя 14 с весом В третьем вычитателе 15 из I однорядного кода остатка вычитается I делитель, хранящий в регистре 3.

С помощью второго коммутатора 17 осуществляется передача на входы уменьшаемого первого вычитателя 13 и ка информационные входы третьей группы первого коммутатора -16 либо значения разности с выходом 36 второго вычитателя 14, когда на выходе заема старшего разряда 37 третьего вычитателя 15 присутствует сигнал логи- чёской единицы, либо значения разности с выходов 38 третьего вычитателя 15, когда на выходе заема старшего разряда 37 третьего вычитателя 15 присутствует сигнал логического нуля.

На информационных входах 39 вто- рого коммутатора 17 формируется либо разность остатка в однорядном коде получаемого на вьтодах 35 второго вычитателя 14 и делителя, хранимого в регистре 3,. если остаток на выходе 35 второго вычитателя болыче делителя, либо остаток, получаемый на выходах 35 второго вычитателя 14, если этот остаток меньше делителя, т.е на выходах 39 второго коммутатора 17 формируется остаток такой., какой он получается в процессе деления при определении одной цифры частного,

С помощью первого коммутатора 18 осуществляется передача на информационные входы первого регистра 1 остатка, либо значения делимого с входа 20 данных устройства, когда на втором выходе 48 блока 19 управления присутствует сигнал логической единицы, либо значение с разности с выходов 42 первого вычитателя 13, когда на третьем выходе 49 блока 19 управления

09to

формируется сигнал логической единицы, или же значения выходов 39 разрядов второго коммутатора 17, когда на четвертом выходе 50 блока 19 управления присутствует сигнал логической единицы.

Узел 18 коррекции частного предназначен как для коррекции, в случае необходимости, (K-l) младших разрядов -частного, образованного в предыдущем такте работы устройства, так и для коррекции частного, сформированного в текущем такте. Коррекция ()младишх разрядов частного, сформированного в предыдущем такте, осуществляется, если сигнал заема на выходе 37 старшего разряда третьего вычитателя 15 соответствует уровню логического нуля, а коррекция цифр частного, образованного в текущем такте, осугчествляётся, если сигнал на седьмом выходе 51 блока 19 управления соответствует уровню логического нуля, причем коррекция цифр частного, сформированного в текущем , также приводится в результате коррекции из вида ОХХХ.,,Х к виду 100..,О

К

К

5 n

0

5

Блок 19 управления координирует работу узлов и блоков устройства при выполнении на нем операции деления чисел.

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

По первому синхроимпульсу на входе 21 синхронизации устройства на первом и шестом выходах 46 и 47 блока 19 управления формируются сигналы,по .которым осуществляется запись п-разрядно- го делителя в регистр 3 делителя с входа 20 данных устройства, и обнуляется первый и второй регистры 1 и 2 остатка. По истечении действия первого импульса На входе 21 синхрониза- ции устройства появляется потенциал логической единицы на втором выходе 48 блока 19 управления. Так как в первом и втором регистрах 1 и 2 остатка хранятся нулевые коды, то на выходах 32 блока 5 деления усеченных чисел формируется нулевой код К-разрядного частного, на выходе 37 займа cTaprje- го разряда третьего вычитателя 10 об- зуется сигнал логической единигда, на входах 39 разрядов второго коммутатора 16 форьшруется нулевой код, на выходах 42 и 43 разности и займа

и14291

первого вычитптеля 13 формируются нулевые коды, С приходом второго импульса на вход 21 синхронизации устройства осуществляется запись с входа 20 данными устройства п-разрядно- го кода делимого в лервьпЧ регистр 1 остатка нулевого кода займа первого вычитателя 13 - во второй регистр 2 остатка и нулевого кода частного в ю г-шадшие разряды регистра А частного, По истечении действий второго импуль- са на входе 21 синхронизации устройства подготовительный этап, включающий два такта, заканчивается и далее ,5 выполняется собственно деление, в процессе которого за m тактов формируется п(К-1)+1 двоичных цифр частного.

Рассмотрим более детально работу устройства в течение одного i-ro такта () формирования К цифр част ного. По значению старших разрядов те кущего остатка, хранимого в регистрах 1 и 2 в двухрядном коде, и делителя хранимого в регистре 3 делителя, на выходах первого узла 9 деления блока 5 деления усеченных чисел формируется К двоичных цифр частного в предположении, что при проведении двухрядного кода теку1чего остатка в однорядный код образуется сигнал заема из младших разрядов остатка в старшие, а на выходах второго узла 10 деления блока 5 деления усеченных чисел формируется К двоичных цифр частного в предположении, что при приведении двухрядного кода текущего остатка в однорядный код не образуется сигнал займа из младиих разрядов остатка в старшие. Параллельно с работой блока 5 деления усеченных чисел работает второй вычитатель 14, который преобразует двухрядный код текущего остатка в однорядный код. По значению си:- нала заема в старшие разряды на выходе 36 этого вычитателя осуществляется оконч.ательное формирование К цифры частного на выходах 32 блока 5 деле-. НИН усеченных чисел. Если этот сигнал займа соответствует сигналу логической единицы, то в качестве К-разряд- ного частного в устройстве использует ся К цифр частного, образованных на выходах первого узла 9 деления блока деления усеченных чисел, а если сигнал заема соответствует сигналу логического нуля, то в качестве К-разряд- ного частного в устройстве используется значение К цифр частного, сформиро09

2

0

5

0

5

0

5

0

5

ванного на выходах второго узла 10 деления блока 5 деления усеченных чисел. Сформированные на выходах блока 5 деления усеченных чисел (К-1) младших разрядов частного поступают в узел 18 коррекции частного и одновременно подаются на входы первой : группы блока 12 умножения, на выхо,дах 40 и 41 которого oбpaзveтcя про(k-if

изведение у/; в двухрядном коде.

На выходах 39 второго коммутатора 17 формируется разность г г;, ( - значение текущего остатка в однорядном оде на выходах 35 второго вычитателя 14; Z - значение старшего разряда частного, который опре

II деляется по знаку разности г ;

- у, сформированной на выходах - 36 третьего вычитателя 15). Если сигнал заема на выходе 37 заема старшего разряда третьего вычитателя 15 равен логической единице, то Z; равно нулю, а если сигнал заема равен логическому нулю, то 7,. равно единице. На выходах 42 и 43 первого вычитателя 13 формируется в двухрядном коде разность

- . -у г Если разность г ; - г,., - у, сформированная на выходах 38 третьего вычитателя 15, положительна, , старший разряд 7- равен единице, старший разряд К-разрядного частного, сформированного в блоке 5 деления усеченных чисел, равен нулю, то в i-м также на седьмом выходе 51 блока 19 управления появляется сигнал логичес - кого нуля и в узле 18 коррекции частного образуется скорректированное К- разрядное частное в виде 100,, ,0, а

ТГ

в качестве очередного остатка г пер- вым коммутатором 16 устройства выбирается разность rj , Значение этой разности записьтается в первый регистр 1 остатка со сдвигом на (К-1) разрядов влево, а второй регистр 2 остатка при этом обнуляется. Во всех же других случаях в качестве очередного остатка выбирается разность г. , значение которой в виде двух чисел за- письшается соответствукацим образом со сдвигом влево на (К-1) разрядов в первый и второй регистры 1 и 2 остатка. При этом в узле 18 коррекции частного сформированное на выходах 32 блока деления усеченных чисел 5 К-разрядное частное не корректируется. Аналогичным образом работает VCTП .14291П91-

ройство во всех других тактах форми- рования К двоичных цифр ч.чстного.