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

 

Изобретение относится к вычислительной технике и может быть использовано в универсальных и специализированных ЭВМ для построения устройств для деления чисел. Целью изобретения является повышение быстродействия. Устройство содержит группу вычислительных узлов 1i-1m, группу узлов 2i-2m формирования функций генерации и транзита переноса, группу узлов формирования переноса в старший разряд, группу узлов 4i-4m формирования цифры частного. 5 ил.

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

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

РЕСПУБЛИК (я)5 G 06 F 7/52

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4623823/24 (22) 21.12.88 (46) 30.09.91. Бюл. N 36 (72)А.А.Жалковский, А,А.Шостак и Л.О.Шпаков (53) 681.325(088.8) (56) Карцев М,А., Брик В,А. Вычислительные системы и синхронная арифметика. М.: Радио и связь, 1981, с.239 — 242, рис.5.4.3, 5.4.4.

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

М 1594527, кл. G 06 F 7/52, 26.09.88. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ

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

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

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

Устройство для деления содержит (фиг.1) вычислительные узлы 11 — 1, узлы 212m формирования функций генерации и транзита переноса, узлы 31-3 д формирования переносов в старший разряд, узлы 414m формирования цифр частного, вход 5 делителя, входы 6 — 7 делимого и логического нуля, выход 8 частного, первый 9 и второй

10 выходы остатка, вход 11 логической единицы, вход 12 коррекции, выход 13 коррекции, выходы 141-14m сумм и 151 — 15m переносов вычислительных узлов 11-1m соответственно, первые 161 — 16п и вторые

171 — 17„выходы узлов 21 2 соответствен„„RJ„„ 1681303 А1 (57) Изобретение относится к вычислительной технике и может быть использовано в универсальных и специализированных

ЭВМ для построения устройств для деления чисел. Целью изобретения является повышение быстродействия. Устройство содержит группу вычислительных узлов 11 — 1m, группу узлов 21 — 2m формирования функций генерации и транзита переноса, группу узлов 31-3 формирования переноса в старший разряд, группу узлов 41-4П, формирования цифры частного. 5 ил. но, выходы 181 — 18m узлов 31 — 3m, входы 191—

19m Узлов 41 — 4m и входы 201 — 20m настРойки.

Одна из возможных реализаций устройства для деления в аиде модифицированной итеративной сети для 4-разрядного делителя и 8-разрядного делимого приведена на фиг.2. Сеть использует ячейки 21 — 23 трех типов.

Ячейка 21 первого типа содержит(фиг.3) элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 24, одноразрядный двоичный сумматор 25, элемент

И 26, элемент ИЛИ 27, вход 28 разряда делителя, вход 29 управляющего сигнала для данного ряда матрицы (разряд частного, сформированный в .предыдущем ряде матрицы), вход 30 суммы и вход 31 переноса с предыдущего ряда матрицы, вход 32 переноса из соседнего младшего разряда данного ряда матрицы, выход 33 суммы и выход 34 переноса данной ячейки. выход 35 функции генерации G и выход 36 функции транзита Т переноса, формируемые в данной ячейке.

Ячейка 22 второго типа содержит (фиг,4) одноразрядный двоичный сумматор 37, элемент И 38, элемент ИЛИ 39, вход 40 управляющего сигнала для данного ряда матрицы (разряд частного, сформированный в пред1681303

ыдущем ряде матрицы), вход 41 суммы и вход 42 переноса с предыдущего ряда матрицы, вход 43 переноса иэ соседнего младшего разряда данного ряда матрицы, выход

44 переноса данной ячейки, выход 45 функции генерации G и выход 46 функции транзита Т переноса, формируемые в данной ячейке.

Ячейка 23 третьего типа содержит (фиг.5) элемент I-IE 47, элементы И 48 — 56, элементы ИЛИ 57-59, вход 60 коррекции (выход переноса в старший разряд предыдущего ряда матрицы), вход 61 переноса из старшего разряда данного ряда матрицы, входы 62 — 66 функций генерации пе!Зеноса

G 1 — G5 с выходов ячейки 22 и ячеек 21 с первой по четвертую данного ряда матрицы соответственно, входы 67 — 70 функций транзита переноса Т1 — Т4 с выходов ячейки 22 и ячеек

21 с первой по третью данного ряда матрицы соответственно, выход 71 разряда частного и выход 72 переноса в старший разряд данного ряда матрицы.

Каждый из узлов 1> — 1m предназначен для вычисления соответствующего остатка в виде двух чисел: первого числа, составленного из поразрядных сумм, и второго числа, составленного из поразрядных переносов (сумма этих двух чисел равна соответствую.щему остатку). Входной информацией для каждого из узлов 11 — 1!и являются три числа; первое — делитель, второе и третье представляют собой совокУпность поразрядных сумм и поразрядных переносов соответствующего остатка (для первого вычислителя второе число — делимое, а третье число— нулевая информация) с присоединенными младшими разрядами, поступающими с первого б и второго 7 входов делимого устройства, фактически, в каждом узле 12 — 1П1 к значению остатка, представленному в виде совокупности поразрядных сумм поразрядных переносов, прибавляется значение делителя в прямом или дополнительном коде. (т.е, делитель прибавляется или вычитается) в соответствии с алгоритмом без восстановления остатка, в результате чего образуется двухрядный код следующего остатка. Особенностью первого узла 1 является то, что на его входы второй и третьей групп подаются либо значения делимого и нулевой информации соответственно, либо (при многократном использовании устройства) значение остатка с первого 9 и второго 10 выходов остатка устройства в виде совокупности поразрядных сумм и поразрядных переносов.

Одной из возможных реализаций узлов

1>-1! является их построение в виде совокупности элементов ИСКЛЮЧАЮЩЕЕ ИЛИ

24 и сумматоров 25 и 37 (фиг.З и 4), между которыми отсутствуют переносы.

Узлы 2> — 2m для каждого разряда определяют значения функций генерации Qn u

5 транзита переноса Т, по значениям разрядной суммы Sn и переноса In, поступившим в данный разряд, при этом

Gn = Sn In

Тп = Sn + In

10 и = 1,2,...,N, где N — количество разрядов делителя с учетом знакового разряда (в примере на фиг,2

N =5).

По значению переноса в старший раз15 ряд предыдущего ряда К!, поступающему на вход 60 ячейки 23, и значению переноса из с -!шего разряда данного ряда lo, поступающему на вход 61 ячейки 23, формируются дополнительные функции генерации Go u

20 транзита переноса То, Go = К! !о, To= К!+ Io.

Узлы 2> — 2П могут быть реализованы на элементах И 26, 38, 48, элементах ИЛИ 27, 25 39, 57 и элементе Н Е 47 (фиг.3-5).

Узлы 3! и 4! по значениям функций генерации и транзита переноса, вырабатываемым узлами 21, вычисляют значение К! переноса в старший разряд данного ряда

30 матрицы и значение q! разряда частного соответственно, При этом функции, реализуемые узлами 3! и 4!, определяются выражениями;

35 К! = G! + Т263 + Т2 ТЗ Gn + ... + Т2 ТЗ."TN-1

«6д;

q! = Go+ Т061+ ТОТ162+ ... + То Т1...TN-1к м6

Для случая реализации устройства для

40 деления, приведенного на фиг.2, узлы 3! и 4! определяются выражениями (фиг.5):

К! = 62 + Т2 63+ Т2 ТЗ 64 + Т2 Тз Т4 65, Ц! = 60 + ТО G1+ ТО 62 Т1+ ТОТ1Т2ТЗ GÇ +

+To Т ..Т2.ТЗ G4 + TP Т1.Т2 ТЗ Т4 65

45 Узлы 31 — Зп могут быть реализованы на элементах И 54-56 и элементе ИЛИ 59, а формирвоатели 41-4п — нэ элементах И 49—

53 и элементе ИЛИ 58.

Рассмотрим работу устройства для де50 ления на примере реализации приведенном на фиг.2, На вход 5 делителя поступает четырехразрядный делитель С = со,cic2c3c4, на вход

6 делимого — восьмирэзрядное делимое А =

55 80,8182838485858 88, а на вход 7 логического нуля устройства — нули. Предполагается, что делимое и делитель являются положительными нормализованными дробями (т.е, ао =

=c0-0; 81= с1=1). Так как А < 1 — « С<1

1 1

2 2 то частное Q = q>q2q3q4q5 — положительное

1681303

35

55 число, лежащее в диапазоне — < Q < 2, т.е.

q> — целая часть этого числа.

Деление выполняется по алгоритму без восстановления остатка и каждый разряд qi является управляющим сигналом для следующей строки матрицы, т,е. определяет, какую операцию — сложение или вычитание— нужно выполнять в этой строке. В устройстве вычитание делителя осуществляется путем прибавления дополнительного кода числа (-с) (дополнительный код получается инвертированием всех цифр разрядов с; делителя с на элементах ИСКЛЮ4АЮЩЕЕ

ИЛИ 24 с последующим прибавлением единицы в младший разряд узла 1i), Первый вычислительный узел 1 управляется уровнем логической единицы, поступающим с входа 11 устройства. На вход 12 коррекции устройства поступает уровень логического нуля, либо (при многократном использовании устройства) значение с выхода 13 коррекции устройства.

Остаток В в каждой строке матрицы вычисляется в виде двух чисел: числа S u числа Е, составленных из поразрядных сумм S и поразрядных переносов l> соответственно, формируемых на выходах сумм и переносов одноразрядных двоичных сумматоров 25 и 37 (сумма этих двух чисел равна В ), Очередной разряд частного q> определяется по значению переноса из старшего разряда узла 1ь при этом учитывается, что в текущем остатке В -1, передаваемом на следующий ряд матрицы в двухрядном коде s виде поразрядных сумм S;-1 и поразрядных переносов Ei->, может сохраниться перенос в старший разряд узла 1.-, о котором сигнализирует сигнал К-1 на выходе формирователя 3i-1. Таким образом, очередной разряд

qi на выходе Si узла 4i определяется по формуле. сц = Ki-i loi + (Ki-1+ !о ) !та = Go + То ать где К|-1 — инверсное значение переноса в старший разряд вычислителя ii-1, формируемого на выходе узла 3-1 (на выходе 72 ячейки 23);

ioi — значение переноса из старшего разряда узла 1ь формируемого на выходе 44 переноса ячейки 22 старшего разряда;

lzgi — значение переноса из старшего разряда вычислительного узла 1i, формируемого по значению всех разрядов двухрядного кода остатка Вь

На выходах 9 и 10 частного формируется двухрядный код остатка, который при необходимости может быть приведен к однорядному с помощью двухвходового сумматора (этот сумматор может являться общесистемным средством).

В случае невозможности получения всех разрядов частного за один такт устройство можно использовать и в многотактном режиме, при этом информация с выходов 9 и 10 остатка, сигнал коррекции с выхода 13 коррекции устройства и младший разряд частного с выхода Sm поступает на входы 6 и

7 делимого, вход 12 коррекции и вход 11 уровня логической единицы соответственно (через соответствующие промежуточные регистры) для получения очередной группы разрядов частного.

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

Устройство для деления, содержащее m вычислительных узлов, где m — число формируемых цифр частного, m узлов формирования функций генерации и транзита переноса, m узлов формирования переносов в старший разряд и m узлов формирования цифр частного, причем вход делителя устройства соединен с входами первой группы i-го вычислительного узла (где i =

1,2„.,m), выходы суммы и переноса которого соединены с входами первой и второй групп соответственно I-го узла формирования функций генерации и транзита переноса, выходы младших разрядов первой и второй групп которого соединены с входами первой и второй групп соответственно i-го узла формирования переноса в старший разряд, входы старших разрядов делимого и нуля устройства соединены с входами второй и третьей групп соответственно первого вычислительного узла, вход настройки которого соединен с входом логической единицы устройства, вход настройки (j+1)-го вычислительного узла, где (j = 1,2,...,m — 1), соединен с выходом j-ro узла формирования цифр частного, входы младших разрядов второй и третьей групп ()+1)-.го вычислительного узла соединены с входами собтветствующих разрядов делимого и нуля устройства соответственно, выходы узлов формирования цифр частного соединены с выходами разрядов частного устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, входы первой и второй групп )-го узла формирования функции генерации и транзита переноса соединены с входами старших разрядов второй и третьей групп (j+1)-го вычислительного узла соответственно, первый и второй выходы остатка устройства соединены с входами первой и второй групп m-го узла формирования функций генерации и транзита переноса, выход коррекции устройства соединен с выходом

m-го узла формирования переноса в старший разряд, выход j-го узла формирования

3681303 переноса в старший разряд соединен с входом коррекции (+1}-го узла формирования функций генерации и транзита переноса, вход коррекции первого узла формирования функций генерации и транзита переноса соединен с входом коррекции устройства, входы первой и второй групп I-го узла формирования цифр частного соединены с выходами первой и второй групп I-го узла формирования функций генерации и транзита переноS са соответственно.

1681303

1681303

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

Техред М.Моргентал Корректор М. Шароши

Редактор А, Лежнина

Производственно-издательский комбинат "Патент", r. ужгород, ул.Гагарина, 101

Заказ 3312 Тираж371 Подписное

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

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