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

 

(19> 01) СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИК

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

r1O ДЕЛА ИЗОБРЕТЕНИЙ V ОТНРЫТИй (21) 3350184/18-24 (22) 29. 10.81 (46) 15.10.84. Бюл. № 38 (72) Г.П. Лопато и А.А. Шостак (71) Минский радиотехнический институт (53) 681.325(088.8) (56) 1. Патент США № 3234367, кл. 235/156, опублик. 1966.

2. Папернов А.А. Логические основы ЦВТ. М., "Советское радио", 1972, с. 230-239 (прототип). (54)(57) устройство для дклкния

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

25 ключены к управляющим входам коммутатора и к первым входам с пятого по восьмой элементов И соответственно, выходы которых подключены к входам первого элемента ИЛИ соответственно, выход которого подключен к входу первого младшего разряда регистра частного, вход второго младшего разряда которого подключен к выходу второго элемента ИЛИ, входы кото1

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

Известно устройство для деления двоичных чисел, формирующее в каждом цикле 1 цифр частного (% = 2, 3, 4, 5, ...).и содержащее регистры делимого и делителя, регистр частного с цепью сдвига, блок умножения, вычитатель, шифратор предсказания

% цифр частного, регистра адреса, блок памяти, регистры верхнего и нижнего значений k цифр частного, группы элементов И, причем входы шифратора предсказания t цифр частного соединениы с вьгходами % старших разрядов регистров делимого и делителя (.11.

Недостатками известного устройства являются невозможность деления чисел в дополнительном коде и низкое быстродействие, вызванное боль-. шой длительностью цикла формирования 4 цифр частного (k цифр частного в известном устройстве формируется по многотактному принципу: минимальное число тактов в цикле равно двум, максимальное — (k + 1). !

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

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

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

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

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

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

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

И, второй вход которого подключен к первому входу четвертого элемента И и к инверсному выходу первого элемента неравнозначности, инверсные выходы второго и пятого элементов неравнозначности подключены к вторым входам второго и четвертого элементов И соответственно, выходы с первого по четвертый элементов И подключены к управляющим входам коммутатора и к первым входам с пятого по восьмой элементов И соответственно, выходы которых подключены к входам первого элемента ИЛИ соответственно, выход которого подключен к входу первого младшего разряда регистра частного, вход второго младшего разряда которого под25

55 ключен к выходу второго элемента

ИЛИ, входы которого подключены к выходам второго и четвертого элементов И соответственно, вторые входы с пятого по восьмой элементов

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

На фиг. 1 приведена структурная схема устройства для деления чисел (рассматривается случай, когда число одновременно формируемых в цикле цифр частного равно трем); на фиг. 2 — функциональная схема узла образования частного, на фиг. 3 функциональная схема i-ro разряда коммутатора.

Устройство для деления чисел содержит (фиг. 1) регистры 1, 2, 3 соответственно делимого, делителя и частного, сумматор-вычитатель 4, первый, второй и третий сумматоры

5, 6 и 7, первый, второй и третий вычитатели 8, 9 и 10, коммутатор

11, узел 12 образования частного, управляющий вход 13. Первый и второй информационные входы сумматоравычитателя 4 подключены к выходам регистров 1 и 2 делимого и делителя соответственно, а его информационный выход соединен с первыми информационными входами первого сумматора 5 и первого вычитателя 8, первые информационные входы второго сумматора 6 и второго вычитателя 9 соеди" нены с информационным выходом первого сумматора 5, первые информационные входы третьего сумматора 7 и третьего вычитателя 10 соединены с информационным выходом первого вычитателя 8, вторые информационные входы сумматоров 5-7 и вычитателей

8-10 соединены с выходом регистра

2 делителя, информационные выходы второго и третьего сумматоров 6 и 7 и второго и третьего вычитателей

9 и 10 соединены с информационными входами коммутатора 11 соответственно, выход которого подключен к информационному входу регистра делимого, управляющие входы сумматора-вычитателя 4 подключены к выходам 14 и 15 знаковых разрядов регистров 1 и 2 делимого и делите1119006 ля соответственно, выходы 15, 16, 17у 18, 19, 20, 21 и 22 знаковых разрядов соответственно регистра 2, сумматора-вычитателя 4, сумматора 5, вычитателя 8, сумматора 6, вычитателя 9, сумматора 7 и вычитателя 10 подключены к информационным входам узла 12 образования частного, первая группа выходов которого подключена к управляющим входам коммутатора 11, а вторая группа выходов подключена к входам трех младших разрядов регистра 3, частного, входы приема информации регистров 1 и 2 делимого и делителя и вход приема и сдвига информации регистра 3 частного соединены с управляющим входом 13 устройства.

Узел 12 образования частного содержит (фиг. 2) семь элементов неравнозначности 23, восемь элементов И 24 и два элемента ИЛИ 25.

Один разряд коммутатора 11 содержит (фиг. 3) четыре элемента И

26 и один элемент ИЛИ 27.

В устройстве регистры 1-3 могут быть построены на двухтактных синхронных D-триггерах. Предполагает- ся, что сумматоры 5-7 и вычитатели

8-10, а также сумматор-вычитатель

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

В зависимости от значения знаковых разрядов регистров 1 и 2 делимого и делителя сумматор-вычитатель 4 настраивается через свои управляющие входы на суммирование либо вы" читание чисел. Если значения знаковых разрядов регистров 1 и 2 совпадают, то сумматор-вычитатель 4 работает как вычитатель, в противном случае он выполняет функцию сумматора ° Функции вычитателей в устройстве могут выполнить и сумматоры, если на их вторые входы подавать вместо прямых инверсные значения разрядов регистра 2 делителя и в качестве входных переносов испольэовать сигнал логической единицы. Сумматор-вычитатель 4 можно заменить в этом случае сумматором с управляемым вторым входом.

На этот вход, в зависимости от значения сигналов на управляющих входах сумматора, будут поступать

45 . ((-)(P+X ) (1((+))(50

+ р„о,ÄÄ), ° (к„,ex») Ä, Здесь, например, через 7 обозна5S чен управляющий сигнал, под действием которого коммутатор 11 осуществляет выборку результата, сформиролибо прямые, либо инверсные значения разрядов регистра 2 делителя

Ъ (в последнем случае в качестве входного переноса сумматора должен исполь5 зоваться сигнал логической единицы.

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

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

25 в виде двух чисел), а регистр делимого имеет такую разрядность, что обеспечивает хранение промежуточных остатков в двухрядном коде.

Узел 12 образования частного выgp полняет две функции: во-первых, формирует сигналы Y, .Y„, Y и У<, о управляющие работой коммутатора 11, во-вторых, образует три двоичные цифры частного Z,,7, Z„ в соответст35 вии с алгоритмом деления без BOccTclновления остатков (Z — старшая и

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

40 коммутатора 11, а также образование цифр частного может осуществляться в узле 12 в соответствии со следующими логическими выражениями:

1119ОО6

55 ванного на выходе сумматора с порядковь!м номером 7 (фиг. 1), Х! обоз начает логическую переменную, соответствующую значению знакового разряда на выходе 15 регистра 2 делителя (М, = 1, если делитель отрицательный, в противном случа еХ, = О) .

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

С помощью коммутатора 11 осуществ— ляется выборка в качестве очередного остатка либо значения суммы S одного из сумматоров 6, 7, либо значения разности R оoдного из вычитателей 9, 10. Управление этой выборкой производится под действием соответствующих сигналов У<, У1 поступающих на управляющие входы коммутатора 11 с выходов первой группы узла 12 образования частного. Функциональная схема

i-ro разряда коммутатора 11 пока-. зана на фиг. 3, где, например, R> обозначает значение разности на выходе l.-го разряда вычитателя с порядковым номером 9 на фиг. 1.

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

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

B исходном состоянии в регистре

1 делимого хранится и-разрядный дополнительный код делимого Я, в регистре 2 делителя — n-ðàçðÿäíûé дополнительный код делителя 8, регистр 3 частного обнулен (предполагается, что делимое и делитель— правильные нормализованные двоичные дроби) . Сразу же после загрузки делимого и делителя в регистры 1 и 2 сумматор-вычитатель 4 настраивается по своим управляющим входам либо на суммирование (если знаки делимого и делителя не совпадают), либо на вычитание (если знаки дели— мого и делителя совпадают), после чего сумматор-вычитатель 4, сумма5 !

О !

40 торы 5-7 и вычитатели 8-10 начинают работать практически одновременно (здесь предполагается, что в сумматорах и вычитателях цепи переноса и заема построены по сквозному принципу). С их помощью на выходах сумматоров 6 и 7 и вычитателей 9 и 1О формируются результаты при всех возможных путях развития вычислительного процесса определения трех наиболее старших двоичных цифр частного по алгоритму деления без восстановления остатков. Очевидно, что в одном цикле определения трех двоичных цифр частного только один из этих четырех результатов может быть правильным. Выбор правильного результата осуществляется с помощью управляющих сигналов Y,, (и

Y„о ° По истечении времени, равного примерно времени суммирования двух п-разрядных двоичных чисел от момента загрузки делимого и делителя в регистры 1 и 2, коммутатор 11 выбирает в качестве первого остатка результат либо одного из сумматоров 6, 7, либо одного из вычитателей 9, 10, который далее с разрешения сигнала на управляющем входе

13 устройства записывается в регистр

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

Одновременно с формированием и записью первого остатка в регистр

1 делимого в узле 12 образуются три наиболее старшие двоичные цифры частного в соответствии с приведенными ранее соотношениями, значения которых записываются соответствующим образом в три младших двоичных разряда регистра 3 частного, после чего в нем осуществляется однотактный сдвиг информации на три двоичных разряда в сторону его старших разрядов. На этом цикл определения трех наиболее старших двоичных цифр частного заканчивается. Определение других цифр частного осущестВляется аналогичным образом. После выполне19006

1,01101

1, 00111

0 01100 0,01100

1,00111 1,00111

1,00110 1,00110 0,01010 0,01010

1,00111 I 00111 1,00111 1,00111

0,01101 1,11111 1,10001 1,00011

Второй цикл Qi 1,11110 определения цифр 1,00111 частного (О О

Э 0

О) 0,10111

1,01110 1,01110

1,00111 1,00111

l< /

1,01010 1,01010 0,01110 0,01110

1,00111 1,00111 i 00111 1,00111

0,10001 О,OOO11 1,101О1 1,ОО111

О 1,00010

9 11 ния и/3 циклов в регистре 3 частного будет сформировано и-разрядное двоичное частное. Очевидно, что для получения более точного значения частного число циклов должно быть определенным образом увеличено. Знак частного может быть сформирован путем сложения по модулю два знаковых разрядов делимого и делителя или же может быть получен автоматически в процессе деления, если ,заранее известно. что условие

IAI< ISI всегда выполняется.

Пример . Пусть n = 6, условие Ihf<151 всегда выполняется, делимое A -0,10011, делитель 8 -0, 11001, Делимое и делитель в регистрах 1 и 2 устройства представлены в дополнительном коде следующим образом: A>< = 1,01101 и 8, „ =

Айалогично может быть разработано устройство для деления двоичных чисел, в каждом цикле которого обра1,00111. Производя деление этих чисел по методу без восстановления остатков, получаем частное С =

0,11000.

Ниже приведен пространственночисловой пример деления этих же чисел в предлагаемом устройстве. В нем вычисления расположены подобно тому, как размещены сумматор-вычитатель 4, сумматоры 5-7 и вычитатели 8-10 на фиг. 1. Правильный путь развития вычислительного процесса определения в цикле трех двоичных

15 цифр частного отмечен двойными линиями, а знаком 0 обозначен дополнительный разряд регистра 1 делимого для хранения знака остатка.

Первый цикл определения цифр

20 частного (О, 1, 1) зуются две или больше чем три дво-: ичных цифры частного. Однако с увеличением числа 1 одновременно обраti 11 зуемых в цикле двоичных цифр частного резко возрастает объем используемого в устройстве оборудования.

Так, например, уже при 1< - =5 в устройстве необходимо использовать пятнадцать сумматоров, пятнадцать вычитателей и один сумматор-вычитатель. Кроме того, несколько усложняются коммутатор и узел образования частного. Поэтому в настоящее время представляют практический интерес устройства для деления„ образующие в одном цикле по предложенному принципу не более шести двоичных цифр частного.

Таким образом, предлагаемое устройство действует быстрее примерно в % раз (k = 2, 3, 4, 5, 6, ...), чем устройство-прототип. Это достигается тем, что в каждом цикле его работы образуется несколько двоичных цифр частного, в то время как в известном устройстве только одна двоичная цифра частного. Длительность же цикла работы предлагаемого устройства

19006 примерно такая же, как и у известного устройства, так как в нем сумматор-вычитатель, все сумматоры и вычитатели начинают работать практически одновременно. Сказанное справедливо только тогда, когда в известном и предлагаемом устройствах используются сумматоры и вычитатели с неускоренными .(например, 1О сквозными) переносом и заемом. В тех же случаях, когда в известном и предлагаемом устройствах используются сумматоры и вычитатели с ускоренным образованием разрядных пе-!

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

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

1119006

7 6, Составитель А. Шостак

Редактор М. Циткина Техред Л,Мартяшова Корректор А. Тяско

Заказ 7454/36 Тираж 698 Подписное

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

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4