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

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

Изобретение относится к вычислительной технике и может быть исполь зовано для быстрого деления двоичных чисел в дополнительном коде. Известно устройство для деления двоичных чисел, формирующее в каждом цикле цифр частного (1с 2, 3, 4, 5, ...) и содержащее регистры делимого и делителя, регистр частного с цепью сдвига, блок умножения вычитатель, шифратор предсказания 1с цифр частного, регистра адреса, блок памяти, регистры верхнего и нижнего значений V цифр частного, группы элементов И, причем входы шифратора предсказания k цифр частного соединенны с выходами У- старши разрядов регистров делимого и делителя С1 3. Недостатками известного устройст ва являются невозможность деления чисел в дополнительном коде и низкое быстродействие, вызванное боль шой длительностью цикла формирования U цифр частного ( k цифр часткого в известном устройстве формируется по многотактному принципу: минимальное число тактов в цикле равио двум, максимальное - ( + 1) I Наиболее близким по технической сущности к изобретению является устройство для деления чисел, содержащее регистры делимого, делите ля и частного, сумматор-вычитатель причем первый и второй информацион Hbie входы сумматора-вычитателя под ключены к выходам регистров делимо го и делителя соответственно, а его информационный выход подключен к входу регистра делимого, управляющие входы сумматора-вычитателя подключены к выходам знаковых разрядов регистров делимого и делителя, входы приема информации регистров делимого и делителя и вход приема и сдвига информации регистра частного подключены к управляющему входу устройства, информационный вход младшего разряда регистра частного подключен к выходу узла анализа сочетания знаков Г2. Недостаток известного устройства заключается в низком быстродействии, вызванном в первую очередь невозможностью формирования в цикле нескольких двоичных цифр частного . Цель изобретения - повышение быстродействия устройства для деления чисел за счет одновременного формирования в цикле нескольких двоичных цифр частного. Поставленная цель достигается тем, что в устройство для деления чисел, содержащее регистры делимого и делителя, регистр частного и сумматор-вычитатель, первый и второй информахщонные входы которого подключены к выходам регистров делимого и делителя соответственно, управляющие входы сумматора-вычитателя подключены к выходам знаковых разрядов регистров делимого и делителя, входы приема информации регистров делимого и делителя и вход приема и сдвига информации регистра частного пЪдключены к управляющему входу устройства, введены сумматоры, вычитатели, коммутатор и узел образования частного, причем первые информационные входы первого сумматоpa и первого вычитателя соединены с. лнформационуым выходом сумматоравычитателя, первые информационные входы второго сумматора и второго вычитателя соединены с информационным выходом первого сумматора, первые информационные входы третьего сумматора и третьего вычитателя соединены с информационнь1М выходом первого вычитателя, вторые информационные входы сумматоров и вычитателей соединены с выходом регистра делителя, информационные выходы второго и третьего сумматоров и второго и третьего вычитателей соответственно соединены с информационными входами коммутатора, выход которого подключен к информационному входу регистра делимого, при этом узел образования частного содержит элементы неравнозначности, И и ИЛИ, причем выход знакового разряда регистра делителя подключены к первым входам с первого по седьмой элементов неравнозначности, выходы знаковых разрядов сумматора-вычитателя, первого, второго и третьего сумматоров первого, второго и третьего вьгаитателей подключены к вторым входам с первого по седьмой элементов неравнозначности соответственно,

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

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

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

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

Устройство для деления чисел содержит (фиг. 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 соответственно, выход которого подключен к информационному входу регистра 1

делимого, управляющие входы сумматора-вычитателя 4 подключены к выходам 14 и 15 знаковых разрядов регистров 1 и 2 делимого и делитеSля соответственно, выходы 15, 16, 17, 18, 19, 20, 21 и 22 знаковых разрядов соответственно регистра 2 сумматора-вычитателя 4, сумматора вычитателя 8, сумматора 6, вычитателя 9, сумматора 7 и вычитателя 1 подключены к информационным входам узла 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 мож но заменить в этом случае сумматором с управляемым вторым входом. На этот вход, в зависимости от зна чения сигналов на управляющих входах сумматора, будут поступать 6 либо прямые, либо инверсные значения разрядов регистра 2 делителя (в последнем случае в качестве входного переноса сумматора должен использоваться сигнал логической единицы. Следует особо отметить, что с целью обеспечения максимально возможного быстродействия устройства в нем необходимо использовать сумматоры с ускоренном образованием разрядных переносов. Однако во многих случаях этого же быстродействия можно достичь при существенно меньших аппаратурных затратах, если в устройстве использовать сумматоры без распространения, переносов (сумматоры с сохранением переносов), организовав ускоренное формирование переносов только в их знаковые разряды. Структура устройства при этом не изменяется, если предполагать, что на информационном выходе каждого сумматора результат формируется в двухрядном коде (т.е. в виде двух чисел), а регистр делимого имеет такую разрядность, что обеспечивает хранение промежуточных остатков в двухрядном коде. Узел 12 образования частного выполняет две функции: во-первых, формирует сигналы Y,; , .Y, , Y., и Y, б 7 Э 10 управляющие работой коммутатора 11, во-вторых, образует три двоичные цифры частного 2-3 , „ , Z в соответствии с алгоритмом деления без восстановления остатков (Zj - старшая и 2 - младшая двоичная цифра из трех формируемых в цикле цифр). Формирование сигналов, управляющих работой коммутатора 11, а также образование цифр частного может осуществляться В узле 12 в соответствии со (ледующими логическими вьгражениями: ); .)(.) )( SJ(.) AV , )r-(V ( «®2,)7( «®22)0 Здесь, например, через Т-, обозначен управляющий сигнал, под действием которого коммутатор 11 осуществляет выборку результата, сформиро71ванного на выходе сумматора с поряд ковым номером 7 (фиг. 1) , Х обозначает логическую переменную, соответствуюп уш значению знакового разр да на выходе 15 регистра 2 делителя ( 1, если делитель отрицательный, в противном случаеХ 5 0). На фиг. 2 изображена функциональ ная схема узла 12 образования частного, работающая в соответствии с приведенными логическими вьфажениями. Разумеется, что эта схема может быть определенным образом преобразо вана для обеспечения ее более высо кого быстродействия. С помощью коммутатора 11 осущест ляется выборка в качестве очередного остатка либо значения суммы S од ного из сумматоров 6, 7, либо значения разности R одного из вычитателей 9, 10. Управление этой выборкой производится под действием соот ветствующих сигналов Yt 7 5 9 10 поступающих на управляющие входы коммутатора 11 с выходов первой группы узла 12 образования частного. Функциональная схема i-ro разряда коммутатора 11 пока-зана на фиг. 3, где, например, R обозначает значение разности на выходе 1-го разряда вычитателя с порядковым номером 9 на фиг. 1. Если в устройстве используются сумматоры без распространения переносов (т.е. формирующие на своих информационных выходах результат в двухрядном коде), то i-й разряд коммутатора 11 должен включать две такие схемы. Устройство для деления чисел работает следующим образом. В исходном состоянии в регистре 1 делимого хранится п-разрядньй дополнительный код делимого А , в регистре 2 делителя - п-разрядный дополнительный код делителя В , регистр 3 частного обнулен (предпо лагается , что делимое и делитель правильные нормализованные двоичны дроби). Сразу же после загрузки делимого и делителя в регистры 1 и 2 сумматор-вычитатель 4 настраивается по своим управляющим входам либо на суммирование (если знаки делимого и делителя не совпадают), либо на вычитание (если знаки дели мого и делителя совпадают), после чего сумматор-вычитатель 4, сумма8торы 5-7 и вычитатели 8-10 начинают работать практически одновременно (здесь предполагается, что в сумматорах и вычитателях цепи переноса и заема построены по сквозному принципу) . С их помощью на выходах сумматоров 6 и 7 и вычитателей 9 и 10 формируются результаты при всех возможных путях развития вычислительного процесса определения трех наиболее старших двоичных цифр частного по алгоритму деления без восстановления остатков. Очевидно, что в одном цикле определения трех двоичных цифр частного только один из этих четырех результатов может быть правильным. Выбор правильного результата осуществляется с помощью управляющих сигналов Yg, Ч, Yg и . По истечении времени, равного примерно времени суммирования двух п-разрядных двоичных чисел от момента загрузки делимого и делителя в регистры 1 и 2, коммутатор 11 выбирает в качестве первого остатка результат либо одного из сумматоров 6, 7, либо одного из вычитателей 9, 10, который далее с разрешения сигнала на управляющем входе 13 устройства записывается в регистр 1 делимого со сдвигом на один двоичный разряд влево. Здесь важно отметить, что при записи в регистр 1 очередного остатка со сдвигом его влево на один двоичный разряд возможно искажение знака остатка. Поэтому необходимо предусмотреть в регистре 1 делимого дополнительный (п + 1)-й разряд для хранения знака остатка, полученного в очередном цикле деления. Одновременно с формированием и записью первого остатка в регистр 1 делимого в узле 12 образуются три наиболее старшие двоичные цифры частного в соответствии с приведенными ранее соотношениями, значения которых записываются соответствующим образом втри младших двоичHbDc разряда регистра 3 частного, после чего в нем осуществляется однотактный сдвиг информации на три двоичных разряда в сторону его старших разрядов. На. этом цикл определения трех наиболее старших двоичных цифр частного заканчивается. Определение других цифр частного осуществляется аналогичным образом. После вьшолнеяия n/3 циклов в регистре 3 частного будет сформировано п-разрядное двоичное частное. Очевидно, что для получения более точного значения частного число циклов должно быть определенным образом увеличено. Зна частного может быть сформирован путем сложения по модулю два знаковых разрядов делимого и делителя япи же может быть получен автоматически в процессе деления, если ,|аранее известно, что условие IAKIBI всегда вьтолняется.

Пример . Пусть п 6, условие |Л| |В1 всегда вьтолияется, делимое А -0,10011 делитель 8 « -О,t1001. Делимое и делитель в регистрах 1 и 2 устройства представлены в дополнительном коде следующим образом: Адц 1,01101 и Вд

1,01101 1,00111

0,00110.

0,01100 1,00111

1,10011

/

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

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

Второй цикл определения цифр частного (О, О, 0)

1,01110 1,00111

0,10101

/

1,01010 1,01010 1,00111 1,00111

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

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

Первый цикл определения цифр частного (О, 1, 1)

0,01100 1,00111

1,001.01

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

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

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

:л

п

.1

612

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

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

во всех сумматорах и вычитателях

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

к

ж

13

LZIJ