Асинхронное матричное устройство для деления

 

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

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

РЕСПУБЛИК

09) (И) I у5)) 6 06 Г 7/54

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

Н ABT0PCH0MV СВИДЕТЕЛЬСТВУ

)

3 <" >v

)

) Ь:ьи, 3 (21) 3414273/18-24 (22) 25.03.82 (46) 07.06.83. Бюл. и 21 (72) А.Н.Шейк-Сейкин и Ю.В.Нечипуренко (71) Одесский ордена Трудового Красного Знамени политехнический институт (53) 681 325(088.8) (56) 1. Патент США и 3803393, кл. G 06 F 7/54, опублик. 1974.

2. Патент США И 3956621, кл. G 06 F 7/54, опублик. 1976.

3. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. И., "Иир", 1978, с.580 (прототип). (54)(57) АСИНХРОННОЕ ИАТРИЦНОЕ УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ, содержащее регистры делимого, делителя, частного, узлы свертки по модулю два, элемент

НЕ и L-1 (где L - число разрядов частного. К -разрядных (где К - число разрядов делителя) сумматоров-вычитателей, причем выходы разрядов регистра делимого с (й-К)-го по (й-1) (где и - число разрядов делимого- под" ключены к первым входам разрядов с первого по К -й первого сумматоравычитателя соответственно, выходы разрядов с первого по (K"1)-й i ãî (где i - порядковый номер строки) сумматора-вычитателя (i 1,...,J-1, 3+1,...,L-2) подключены к. первым входам разрядов с второго по К-й (i+1)-ro cy aropa-вычитателя соответственно, вторые входы- разрядов с первого по К-й i1-го (1 1,...J) сум.матора-вычитателя соединены с выходами разрядов с первого по К-й регистра делит ля соответственно, первые входы первых разрядов сумматоров-вычитателей с второго no J-й (где J - число разрядов буферного регистра частного) соединены с выходами разрядов с (й-К-1)

rio(N-К-3+1) регистра делимого соответственно, выходы и -го разряда регистра делимого и К-го разряда регистра делителя соединены соответственно с первым и вторым входами первого узла свертки по модулю два, выход которого соединен с входом элемента НЕ,,У подключенного выходом к входу переноса первого сумматора-вычитателя, выход (К+1)-го разряда i-ro (i=1,..., J-1, J+1,...,1.-2) сумматора"вычитателя подключен к первому входу (i+1)-го Я узла свертки по модулю два, выход которого подключен к входу переноса (i+1)-го сумматора-вычитателя, второй ,вход i-го узла свертки по модулю два (-1=!,...,Л) подключен к выходу К-го разряда регистра делителя, выход (К+1)-го разряда i-го (i=J+I,..., L-1) сумматора"вычитателя соединен с входами разрядов с (L-3-1) по первый соответственно регистра частного, о т л и ч а ю щ е е с я тем, что, с целью увеличения его быстродействия, введены буферные регистры частного, частичного делимого, остатка делимого и делителя, причем вход нулевого разряда буферного регистра частного соединен с входом элемента НЕ, выход

-(К+1)-го разряда 1-го сумматора-вычитателя соединен с i-м (il,... )),Ь входом буферного регистра частного, -выходы разрядов с первого по К-"

3-го сумматора-вычитателя соединены с входами разрядов с первого по К-й буферного регистра частичного делимого соответственно, выходы разрядов

1022157

10

15 — л с й-К-J) по первый регистра делимого соединены с входами разрядов с перво" го по m-й (где а " число разрядов буферного регистра остатка делимого) буферного регистра остатка делимого соответственно, выходы разрядов с пер" вого по К-й регистра делителя соеди" нены с входами разрядов с первого .по

К-й буферного регистра делителя соответственно, выходы разрядов с нулевого по (J-1)-й буферного регистра част. ного подключены к входам разрядов с

L-ro по (Я+1)-й регистра частного соответственно, вмход J-ro разряда подключен к входу (L-J)-го разряда регистра частного и первому входу

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

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

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

Наиболее близким по технической сущности и достигаемому результату к предлагаемому является асинхронное матричное устройство для деления hJразрядного двоичного числа (делимого) на К"разрядное двоичное число (делитель),содержащее регистрм делимого, делителя, частного, узлы свертки по модулю два, элемент НЕ и L -1 (где

tL - число разрядов частного) К-разрядных сумматоров-вычитателей, причем

30 (J+1)-ro узла свертки по модулю два, выходы разрядов с первого по (К-1)-й ° буферного регистра частичного делимого подключены к первым входам разрядов с второго по К-й (3+1)-ro сумматора-вычитателя соответственно, выходы разрядов с первого по m-й буферного регистра остатка делимого соединены с первыми входами первых разрядов 1 -х (I J+I б-1) сумматоров-вычитателей, вторые входы которых подключены к вы" ходам разрядов с первого по К-й буферного регистра делителя, к выходу

К-го разряда которого подключены вторые входы узлов свертки по модулю два с (.У+1)-го по (L- 1)-й. выходы разрядов регистра делимого с (N-К)-го по (й-1) -й подключены к первым входам разрядов с первого по К-й первого сумматора"вычитателя соответственно, выходы разрядов с первого по (К-1)-й i-го (где i - порядковый номер строки) сумматора-вычитателя (i 1,...., J-1 J+1,...L-2) подключены к первым входам разрядов с второго по К-й (i+1)-ro сумматоравычитателя соответственно, вторые входы разрядов с первого по К-й i - го (i 2,...,J) сумматора-вычитателя соединены с выходами разрядов с первого по. К-й регистра делителя соответственно, первые входы первых разрядов сум" маторов-вычитателей с второго по J-й (где J - число разрядов буферного ре" гистра частного) соединены с выходами регистров с (М-К-1) по(й"К-3+1)регистраа делимо ro соот ветс твенно, выходы й-го разряда регистра делимого и К-го разряда регистра делителя соединены соответственно с первым и вторым входами первого узла свертки по модулю два, выход которого соединен с входом элемента НЕ, подключенного выходом к входу переноса первого сумматора-вычитателя, выход К+1го разряда i-го(1 *1...,J-1, J+ I „...

l.-2) сумматора-вычитателя подключен к первому входу f i+1)-ro узла свертки по ьюдулю два, выход которого подключен к входу переноса (i+1)-ro сумматора-вычитателя,, второй вход

3 -"1 022!

i-ro узла свертки по модулю два (i 1,...J) подключен к выходу К-го разряда регистра делителя, выход (К+1) -ro разряда i-ro(i=J+1,...1.-1) сумматора-вычитателя соединен с вхо- < дами разрядов с (Я-1) по первый coj ответственно регистра частного f3 ) .

Недостаток известного устройства состоит в том, что быстродействие ограничено заданной разрядностью де- 10 лимого, делителя и частного. При й-разрядном делимом, К-разрядном делителе и L-разрядном частном (обычно

L N"К} максимальное время выполнения операции te, )q (L 1)йкпе, где

tK e - время расйространения сигнала перейоса в К"разрядном сумматоре-вычитателе. Это время можно уменьшить, вычисляя частное по частям, что эквивалентно уменьшению величины L. Полу- 2О чение требуемой разрядности частного при вычислении его no частям осущест" вляется увеличением числа К-разрядных сумматоров-вычитателей.

Цель изобретения - увеличение быстродействия асинхронного матричного устройства деления.

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

e""ro сумматора-вычитателя соединен с 35

4 м (i i ° ...J) входом буферного регистра частного, выходы с пераого по К-й J-ro сумматора-вычитателя соединены с входами разрядов с nepeoro по К-й буферного регистра частичного 4О делимого соответственно, выходы разрядов с (й-К-Я) по первый регистра делимого соединены с входами -разрядов с первого no m-й (где m --число разрядов буферного регистра остатка делимого) буферного регистра остатка делимого соответственно, выходы разрядов c nepsoro no К-й регистра делителя соединены с входами разрядов с пер« вого по К-й буферного регистра дели- 59 теля соответствейно, выходы разрядов с нулевого no (J-. 1)-й буферного регистра частного подключены к входам разрядов с L-ro no (L-Х+1)-й региСтра частного соответственно, выход 55

J-го разряда подключен к входу (1. J)ro разряда регистра частного.и первому входу (3+1)-го узла свертки по

57 4 модулю два, выходы разрядов с первого по (К-1)-" буферного регистра частич" ного делимого подключены к первым входам разрядов с второго по К-й (У+1)-го сумматора-вычитателя .соответственно, выходы разрядов с первого по m-й буферного регистра остатка делимого соединены с первыми входами первых разрядов i-x (iJ+1,...,1 -1) сумматоров-вычитателей, вторые входы которых подключены к выходам разрядов с первого по К-й буферного регистра делителя, к выходу К-ro разряда ко:торого подключены вторые входы узлов свертки по модулю два с (3+1)-. ro no (1 -1)-й.

На чертеже изображена структурная схема устройства.

Устройство содержит регистры делимого I и делителя 2, К"разрядный сумматор-вычитатель 3, узел 4 свертки по модулю два, элемент НЕ 5, буферные регистры частного 6, частичного делимого 7, остатка делимого 8, делителя 9 и регистр 10 частного.

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

Тактовый импульс, поступающий в момент времени t на синхровходы регистров 1, 2, 6-10, передает информацию с входов этих регистров на их выходы. При этом-с регистров 1 и 2, являющихся входом устройства, на К-раэ рядные сумматоры-вычитатели и на узлы свертки по модулю два, находящиеся на строках с первой no J-o, подаются (X+J) старших разрядов делимого и

К разрядов делителя соответственно, . что позволяет вычислить старшие (3+1) разрядов частного. .Процесс вычисления -протекает сле.дующим образом.

Если знаковые разряды делимого и делителя (выход М регистра 1 и выход

К регистра 2) не равны, то узел 4 свертки по модулю два знаков делимого и делителя вырабатывает сигнал логической единицы, который после прохож" дения элемента НЕ 5 ииеет значение логического нуля на входе переноса первого сумматора-вычитателя 3. Последний выполняет операции (А+В), если на входе переноса -.логический нуль, и (А-В), если на входе переноса - логическая единица. Таким образом, при неравенстве знаков делимого и делителя происходит сложение первого частичного делимого и делителя, а при равенстве знаков - вычитание де1022157 . лителя из частичного делимого. Знак частного, вырабатываемый узлом 4 свертки по модулю два знаков делимого, и делителя, поступает на вход "Нуль" регистра 6 (L-й разряд частного), а 5 на первый вход этого же регистра поступает с выхода (К+1)-го разряда первого сумматора-вычитателя 3 знак вто" рого частичного делимого, являющийся одновременно (L-1)-м разрядом частного. Для вычисления (L-2)-ro разряда частного необходимо знать соотношение между знаками второго частичного делимого и делителя. Сигнап с выхода, (К+1)-го разряда первого сумматоравычитателя, соответствующий (L-1)-му разряду частного, и К-й разряд делителя подаются на узел 4 свертки по модулю два, вырабатывающий управляющий сигнал на входе переноса второго 20 сумматора-вычитателя 3, что, в зави" симости от значения этого сигнала, приводит к сложению либо вычитанию делителя из второго частичного делимого и, в оеэультате, вычислению 25

{L-2)-го разряда частного.

Аналогично вычисляются (L-3)-й, (L-4)-й,...,(L-J) и разряды частного.

После этого следующий тактовый им- Зо пульс В момент времени и +Т (где

Т - период следования тактовых импульсов, поступающих на синхровходы регистров 1, 2, 6- 10 одновременно) передает на нижнюю часть схемы (стро- З5 ки 3+1,..., L"1)информацию о вычисленных разрядах частного (входы L, 4.-1,..., -5 регистра 10), (J+!)-м частичном делимом (первые входы разряЯОВ с ВторОГО пО К и (J+1) ГО Сум 4Q матора-вычитателя 3),остатке делимого и делителя (первые входы первых разрядов и вторые входы разрядов с . первого по К-й и с (J+1)-ãî по (! -1)-й сумматоров-вычитателей 3), 45 что позволяет вычислить остальные разряды частного. При этом на верхнюю часть схемы (строки 1,...,J) с регистров 1 и 2 поступают новые значения делимого и делителя.

Таким образом, происходит одновре" менное вычисление (L.-J""1) младших разрядов частного, соответствующего зна" чениям делимого и делителя, поступивших на устройство в момент времени

t0, и (J+1) старших разрядов частного, соответствующего значениям делимого и делителя, поступивших на устройство в момент времени to+7. В момент времени t<+2T на выходе регистра 10, являющимся выходом устройства, получают частное, соответствующее значениям делимого и делителя, поступившиь на вход устройства в момент времени

В момент времени t +3Т получают частное, соответствующее входным значениям делимого и делителя в момент времени t +Т и т,д.

Предлагаемое устройство обладает повышенным быстродействием по сравнению с прототипом. Время выполнения

1 операции tS,ï „о, с уменьшается вдвое и определяется по формуле

ЬЫп 0<ñ Ьь1п мс кс где L -. число разрядов частного;

J=E(L/2), а .Е(х) - целая часть числа х;

Буферные регистры, используемые в предлагаемом устройстве, аналогичны его входным и выходным регистрам, в качестве которых можно использовать выпускаемые промышленностью в интегральном исполнении универсальные регистры !ООИР141 - 4-разрядный универсальный сдвиговый регистр, 133ИР1 -4-разрядный универсальный сдвиговый регистр, 133ИР13 -8-разрядный реверсивный сдвиговый регистр, 564ИР9 .-4-разрядный последовательнопараллельный регистр и т.п.

Принципиальная схема устройства для деления 16-разрядного двоичного

- числа на 8-разрядное двоичное число, построенная на основе структурной схемы прототипа и интегральных микросхемах серии !33, имеет максимальное время выполнения операций с,„ =726ьып мокс

750 нс. После введения в устройство буферных регистров, реализованных на

4-разрядных регистрах типа 133ИР1, (У=-4",, е,„м ц"-400-430 нс.

Таким образом, введение буферных регистров, coc гавляющих 124 от общего. объема устройства, позволяет повысить его быстродействие в 1;8 раза.

1022157.

Составитель Г.Жуков

Техред И.Гергель .Корректор О.Билак

Редактор А.Курах филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

Заказ 4045/41 Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий il3035, Москва, Ж-35, Раушская наб., д. 4/5