Устройство для деления чисел на константу 2 @ + 1

 

Изобретение относится к вычислительной технике и позволяет выполнять деление чисел на константу 2 +1 в последовательном коде с заданной точностью. Цепью изобретения является повышение быстродействия устройства. Устройство содержит сумматор 2.1 итриггерЗЛ, которые вычитают в дополнительном коде из делимого А, задержанноS гона регистре 1.1 на f тактов его же величину , поданную для этого через элемент НЕ 6. что обеспечивает домножение делимого А на величину (2 - 1). При этом единичный сигнал переноса, вырабатываемый по окончанию описанной операции, устраняется путем сброса триггера 3.1 на соответствующем такте сигналом, формируемым счетчиком 4 и дешифратором 5. Последующие сумматоры группы 2, триггеры группы 3 и регистры группы 1 домножают полученный результат на ряд величин: (2 + 1), (24 + 1) и т.д. Сумматор 2.I и триггер 3.1 складывают предыдущий результат, поступающий непосредственно и задерживаемый на регистре 1.1 на 2м тактов, домножая тем самым предыдущий результат на величину (22i + величину X А/2+1, задержанную на 2 тактов.2 ил. СО с

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

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

РЕСПУБЛИК

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

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

ПРИ ГКНТ СССР

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

908.

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

1 (21) 4816024/24 (22) 17.04.90 (46) 07.07.92. Бюл. М 25 (71) Одесский политехнический институт (72) А.В.Дрозд, Е,Л.Полин, Е.В.Беликова и

Ю.В.Дрозд (53) 681.325(088,8)

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

М 710040, кл. G 06 F 7/52, 1975. . Авторское свидетельство СССР

N l658149, кл. 6 06 F 7/52, 1989. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ЧИСЕЛ . НА КОНСТАНТУ 2+1 (57) Изобретение относится к вычислительной технике и позволяет выполнять деление чисел на константу 2+1 в последовательном коде с заданной точностью. Целью изобретения является повышение быстродействия устройства. Устройство содержит сумматор

2;1 и триггер 3. t, которые вычитают в дополнительном коде из делимого А,,задержанноУ,, SU 1746379А1 (51)5 G 06 F 7/52

d го на регистре 1.1 íà fтактов его же величину, поданную для этого через элемент НЕ 6, что обеспечивает домножение делимого А на величину (2 — 1). При этом единичный

1 сигнал переноса, вырабатываемый Ilo окончанию описанной операции, устраняется путем сброса триггера 3.1 на соответствующем такте сигналом, формируемым счетчи.ком 4 и дешифратором 5. Последующие сумматоры группы 2, триггеры группы 3 и регистры группы 1 домножают полученный результат на ряд величин: (2 + 1), (2 + 1) и т.д. Сумматор 2Л и триггер З.i складывают предыдущий результат, поступающий непосредственно и задерживаемый на регистре 1.1 на 2 f тактов, домножая тем самым предыдущий результат на величину(2 +

+1).. Это определяет на выходе устройства результат A(2 — 1) 2 + 1 (2 + 1)... (22 t +

1);..(22" +1 ) = А/2 + 1 (2 " + 1), т.е. искомую величину Х = A/2+1, задержанную на 2 тактов. 2 ил.

1746379

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

Известно устройство для деления, содержащее сумматор, регистр делимого, ре-, гистр делителя и матрицу умножения.

Недостатком устройства является его сложность.

Известно устройство для деления чисел на константу 2 + 1, содержащее первый сумматор, регистр делимого, промежуточный регистр, группу элементов И, счетчик, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИНЕ, группу элементов НЕ, причем и-разрядный информационный вход регистра делимого является входом делимого. устройства, а выходы и-разрядного регистра делимого соединены с соответствующими входами первой группы входов сумматора, младшие выходы сумматора. соединены с первыми входами соответствующих элементов И группы, выходы которых являются выходами остатка устрбйства, выходы сумматора 1+1, 1+2,...,п соединены с информационными входами промежуточного регистра, i-й выход промежуточного регистра, I = 1, n— - (+1, соединен с входом соответствующего элемента НЕ группы, выход которого соединен с I-м входом второй группы входов сумматора, первый выход промежуточного регистра соединен с вторым входом эле.мента ИСКЛЮЧАЮЩЕЕ ИЛИ. ((+1)-й выход сумматора соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого является старшим выходом остатка устройства и соединен с первым входом элемента И-НЕ, первый выход сумматора соединен с вторым входом элемента И-НЕ, выход счетчика соединен с входом разрешения счета счетчика и третим инверсным.входом элемента И-НЕ, выход которого соединен с входом разрешения приема и ромежуточного регистра и с вторыми входами элементов И группы, синхровход промежуточного регистра объединен с аычитающим входом счетчика и является тактовым входом устройства, вход сброса промежуточного регистра объединен с входом установки .счетчика и синхроаходом регистра делимого и является входом запуска устройства, входы и-K+1,...,n второй группы входов сумматора и вход переноса сумматора подключены к единичной шине, старшие выходы сумматора (+1,...,п являются выходами частного устройства.

Недостатком устройства является его низкое быстродействие, обусловлэнноэ большей продолжительностью такта работы устройства.. Цель изобретения — повышение быстродействия устройства.

Указанная цель достигается тем, что в устройство, содержащее группу суммато5 ров, группу триггеров, группу регистров, счетчик и элемент НЕ, причем вход делимого устройства соединен с информационным входом первого регистра группы, выход 1-ro регистра группы (где I - 1, 2,...,r, r — точность

10 вычисления результата) соединен с первым входом i-го сумматора группы. выход переноса которого соединен с информационным . входом I-ro триггера группы, выход элемента НЕ соединен с вторым входом первого

15 сумматора группы, вход начальной установ- . ки устройства соединен с входом сброса

j-го триггера (где j-2,...,,r) группы и входом. сброса счетчика, вход синхронизации которого соединен с входом синхронизации I-ro

20 триггера группы и тактовым входом устройства, введены дешифратор, причем вход элемента НЕ .соединен с входом делимого устройства, выход суммы I-го сумматора группы соединен с информационным вхо25 дом {!+1)-го регистра группы и с вторым входом (I+1)-ro сумматора группы, выход; I-го триггера группы соединен с третим входом

I-го сумматора группы, входы установки и сброса первого триггера группы соединены

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

35 устройства. тактовый вход которого соединен с синхровходами регистров группы. выход суммы r-ro сумматора группы соединен с выходом результата устройства, На фиг.1 приведена структурная схема;

40 на фиг,2 — временные диаграммы, иллюстрирующие работу устройства.

Устройство содержит регистры.

1.1,...,1.r, сумматоры 2.1,....2.r триггера

3.1,...,3.r, счетчик 4, дешифратор 5, элемент

45 НЕ 6, вход 9 начальной установки, вход 7 устройства, тактовый вход 8, выход 10 устройства, причем информационный вход регистра 1 1 и вход элемента НЕ 6объединены между собой и являются входом 7 устройст50 .ва, вход установки счетчика 4 объединен с входами сброса регистров 1 1,...,1.r, с входом установки триггера 3.1 и с входами сброса триггеров 3.2....,3,r и является входом 9 начальной установки, счетный вход: счетчика 4 объединен с синхровходами ре55 гистров 1.1,...,1 г и с синхровходами триггеров 3.1,...,3,г и является тактовым входом 8 устройстВВ, Эъзход 8лэмЭитэ НЕ 6 соэдинэн с первым входом сумматора 2.1, выход регистра 1 1 соединен с вторым входом сумма- .

1746379 тора 2.1, К выходов счетчика, К = )log2 (n + f+ мационный вход регистра 1.1. Регистр 1.1

+ 1)(. соединены.c соответствующими вхо- является регистром сдвига с разрядностью дами дешифратора 5, (и+ )-й выход которого k и задерживает делимое А MB 1тактов. С его соединен с входом сброса триггера 3.1, вы- выхода задержанное делимое А поступает ход которогосоединенстретимвходомсум- 5 на второй вход сумматора 2.1. Последний матора 2.1, выход переноса которого выполняет операцию вычитания в дополниподключен к информационному входу триг- тельном коде с учетом переносов, запомигера 3.1, первый вход сумматора 2Л обьеди- наемых на триггере 3.1. Единичный сигнал нен с информационным входом регистра 1Л переноса с выхода переноса сумматора 2,1, и подключен к выходу суммы сумматоры 2 j 10 вырабатываемый по окончанию .операции — 1, = 2,г, выход регистра 1,! соединен с вычитания не заносится в триггер 3.1, обнувторым входом сумматора 2,i, выход пере- ляемый по входу сброса сигналом с (n+g-го носа которого соединен с информационным выхода дешифратора, который формирует входом триггера З.i, выход которого соеди- его под действием соответствующего кода нен с третим входом сумматора 2.!, выход 15 на выходе счетчика4. На выходесуммы гумсуммы сумматора 2.r является выходом 10 матора 21 формируется величина А(2"-1). устройства, Полученная величина. поступает поразрядПолучение искомого частного Х можно но, начиная с младших разрядов; на первый описать уравнением вход сумматора 2.2 и на информационный

А/(2 + 1) =Х, (1) 20 вход регистра 1.2. Регистр 1.2 является реили

6 гистром сдвига с разрядностью 2, С его

А=.2 Х+Х- (2) выхода величина А(2-1) с задержкой 2f поОтсюда следует, что частное Х совпада- ступает на второй вход сумматора 2.2, котоетс делимым, сдвинутым на (двоичных раз- . рый осуществляет сложение величины рядов в сторону младших разрядов, и при 25 А(2-1), поданной непосредственно и задерЕ этом имеет место погрешность; которая on- жанной на 21 тактов с .учетом переносов. ределяется значением Х, Эта величина тем задержанных на один такт для учета в слеменьше, чем больше величина сдвига, т.е. дующем такте на триггере 3.2. При этом на коэффициент при Х в формуле(2). Эту вели- выходе суммь сумматора 2.2 формируется чину сдвига можно увеличить умножая пра- 30 величина А(2 — 1)(2 + 1), Эта величина повую и левую части равенства на величину 2 ступает на следующую часть схемы, состав1 — 1. Тогда в правой части будет иметь место ленную как и предыдущая из регистра, Й выражение 2 — 1. Дальнейшее увеличение сумматора и триггера, имеющих номера сокоэффициента достигается умножением, ответственно 1.3, 2.3, 3,3 и в два раза больправой и левой части на величину 2 + 1, 35 шую разрядность регистра 1,3, т.е. 4f

2! далее на величину 2 + 1, вплоть до умноже- - разрядов.

2r-1l ния на реличи !у 2 + . . Таких частей в устройстве (r — 1), где r

А(2 — 1)(2 +1)...(2 " +1) =(2 — 1)Х, (3) определяет необходимуюточность-ю вычисгде r — количество описанных домножений, лений, причем на вход i-й части устройства дающих в правой части выражения величи- 40 поступает величина Т = А(2 - 1)(22 + ну (2" — 1)Х, что определяет (2 (— и — 1) +1)...(2 +1) с выхода суммы сумматора точных разрядов результата. 2.1-1 (i-1)-й части устройства, !-я часть устУстройство вычисляет частное от деле- ройства составлена из регистра 1.i, суммания величины А на константу 2 + 1, путем тора 2.i, триггера З.i, причем регистр 1Л определения выражения, стоящего в пра- 45 имеет разрядность в два раза большую, чем вой части формулы (3). регистр 1.!-1, т,е. 2 t разрядов, В начальный момент времени на вход Величина Т поступает на первый вход начальной установки поступает сигнал НУ, сумматора 2.! непосредственно и на его втосбрасывающий в нулевое состояние регист- рой вход через регистр 1Л, задерживающий ры 1.1-1.r, триггера 3.2-3.r и счетчик 4 и величину Т на 2 "(тактов. При этом суммаустанавливает в единицу триггер 3 1. 50 тор 2Л вычисляет их сумму в последовательНатактовыйвходустройства поступают ном коде с учетом .переносов, синхроимпульсы ТИ типа меандр, тактиру- задерживаемых на триггере ЗЛ, равную веющие работу устройства, Они подаются на личине Т(2 " + 1). Таким образом. последсинхровходы. регистров 1.1-1.r, триггеров няя r-я часть схемы аналогично формирует 3.1-3 г и HB счетный вход счетчика.. 55 на выходе суммы сумматора 2.r величину R

На вход устройства поступает делимое - А(2 — 1)(2 + 1)...(2 " + 1), равную (2 " —

А в последовательном коде, начиная с млад- 1)Х, т.е. искомую величину Х, сдвинутую (заших разрядов. Оно подается через элемент держанную) на 2Чразрядов с погрешностью

НЕ6на первый входсумматора2.1иинфор- в и младших разрядах, равной Х.

1746379

S 9 З i S 6 7 В 0 Со мкэл. 4

Вы/ э л. з

8r

9 S .В S 6 Р d

/ К б /

ВЫГ.ЭЛ.9.1

Р/ PS Pd Рэ РГ rd РР ГВ РР

Яй ГВ Sd ХХ Sd S/ $8 SS В/Ф

$/ /Л $$ Sv Cd SC Si ГР 9 $/О

P/ PS РВ A fs o P i РВ Р.9 Aî P Рэл Р9 Рл

1 1 эМЙ

$ /

Выл.эл И

Ж 9 .9 S f 92 9 l S / S 9 $ э $Ъ $5i S iC Sid Sid /Ъ

Фиг. 2

Составитель А.Дрозд

Техред M.Ìîðråíòàë

Редактор Н,Химчук

Корректор M.Ìàêñèìèøèíåö

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

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

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

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

Результатом вычислений принимается (2" — 1)f+ r — 1 старших разрядов из общего количества разрядов (2" — 1)(+ r + и — 1 получаемой суммы на выходе сумматора 2.r, т,е. и младших разрядов игнорируется. 5

По сравнению с прототипом предлагаемое устройство обладает более высоким быстродействием. Действительно. в прототипе вычисление результата производится за (п/1+ 1) тактов, причем продолжи- 10 тельность каждого такта тп определяется задержкой и-разрядного сумматора, которую можно оценить в задержках одноразрядных сумматоров величиной п. Тогда время Тп получения результата для прототи- 15 па определяется как Tn = (n/f+ 1) rn - n /(+

2/

+п.

В предлагаемом устройстве вычисляется L = (2" — 1)f + г+ n — 1 разрядов, на что тратится Lтактов,,Для получения и точных 20 разрядов L должна быть равна 2п (так как и младших разрядов игнорируется). Таким образом, результат в предлагаемом устройстве может быть получен за время Т 2n t; где т — продолжительность такта работы уст- 25 ройства, оцениваемого как время задержки одного одноразрядного сумматора, т.е. Т2п. Иэ этого следует. что Тп/Т = и/2(+ 1/2 и при f «n имеет место значительный выигрыш в быстродействии. 30

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

Устррйство для деления чисел на константу 2 + 1, содержащее группу сумматоров, группу триггеров,. группу регистров, 35 счетчик и элемент НЕ, причем вход делимого устройства соединен с информационным входом первого регистра группы, выход I-ro регистра группы(гдеi -1,2,...,r, г — точность вычисления результата) соединен с первым входом 1-ro сумматора группы, выход переноса которого соединен с информационным входом i-ro триггера группы, выход элемента НЕ соединен с вторым входом первого сумматора группы, вход начальной установки устройства соединен с входом сброса

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

1-го сумматора группы, входы установки и сброса первого триггера группы соединены соответственно с входом начальной установки устройства и выходом дешифратора. входы которого соединены с выходами счетчика, входы сброса регистров группы соединены с входом начальной установки устройства. тактовый вход которого соединен с синхровходами регистров группы, выход суммы r-ro сумматора группы соединен с выходом результата устройства.