Устройство для деления чисел на константу 2 @ + 1 Советский патент 1992 года по МПК G06F7/52 

VI О СО

ч ю

Изобретение относится к вычислительной технике и позволяет выполнять деление чисел на константу 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 ил. СО с

ти

Фиг.1

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

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

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

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

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

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

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

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

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

триггера группы и тактовым входом устройства, введены дешифратор, причем вход элемента НЕ соединен с входом делимого устройства, выход суммы 1-го сумматора группы соединен с информационным входом (1+1}то регистра группы и с вторым входом (1+1}-го сумматора группы, выход 1-го триггера группы соединен с третим входом 1-го сумматора группы, входы установки и сброса первого триггера группы соединены

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

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

На фиг.1 приведена структурная схема;

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

Устройство содержит регистры 1.1,...,1.г, сумматоры 2.1.....2.Г триггера 3.13.г, счетчик 4, дешифратор 5, элемент

НЕ 6, вход 9 начальной установки, вход 7 устройства, тактовый вход 8, выход 10 устройства, причем информационный вход регистра 1.1 и вход элемента НЕ 6объединены между собой и являются входом 7 устройства, вход установки счетчика 4 объединен с входами сброса регистров 1.11.г, с входом установки триггера 3.1 и с входами сброса триггеров 3.23.г и является входом 9 начальной установки, счетный вход счетчика А объединен с синхровходами ре5 гистров 1.11.г и с синхровходами триггеров 3.13.г и является тактовым входом 8

устройства, выход элемента НЕ б соединен с первым входом сумматора 2.1, выход регисура 1.1 соединен с вторым входом сумматора 2.1. К выходов счетчика, К log2 (п + + IX. соединены-с соответствующими входами дешифратора 5, (n+Q-й выход которого соединен с входом сброса триггера 3.1, выход которого соединен с третим входом сум- матора 2.1, выход переноса которого подключен к информационному входу триггера 3.1, первый вход сумматора 2.1 объединен с информационным входом регистра 1.1 и подключен к выходу суммы сумматоры 2J - 1, I 2,г, выход регистра 1,1 соединен с вторым входом сумматора 2,1, выход переноса которого соединен с информационным входом триггера 3.1, выход которого соединен с третим входом сумматора 2.1, выход суммы сумматора 2.г является выходом 10 устройства.

Получение искомого частного X можно описать уравнением

или

А/(2Г+ 1) - X, А 2f.X + X .

(1)

(2)

Отсюда следует, что частное X совпадает с делимым, сдвинутым на двоичных разрядов в сторону младших разрядов, и при этом имеет место погрешность, которая определяется значением X. Эта величина тем меньше, чем больше величина сдвига, т.е. коэффициент при X в формуле (2). Эту величину сдвига можно увеличить умножая пра- вую и левую части равенства на величину 2 - 1. Тогда в правой части будет иметь место выражение 2 - 1. Дальнейшее увеличение коэффициента достигается умножением правой и левой части на величину 22 + 1, далее на величину 2 + 1, вплоть до умножения на величину 22г + 1.

A(2l- 1X22t+ 1)...(22Mt + 1) (2Zf- 1)X, (3) где г - количество описанных домножений, дающих в правой части выражения величину (2м - 1)Х, что определяет (2Г1 - п - 1) точных разрядов результата.

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

В начальный момент времени на вход начальной установки поступает сигнал НУ, сбрасывающий в нулевое состояние регистры 1.1-1.г, триггера 3.2-3.г и счетчик 4 и устанавливает в единицу триггер 3.1.

На тактовый вход устройства поступают синхроимпульсы ТИ типа меандр, тактирующие работу устройства. Они подаются на синхровходы, регистров 1.1-1.г, триггеров 3.1-З.г и на счетный вход счетчика,

На вход устройства поступает делимое А в последовательном коде, начиная с младших разрядов. Оно подается через элемент НЕ 6 на первый вход сумматора 2.1 и инфор

10

15

0

5 0

0

5

5

0

5

мационный вход регистра 1.1. Регистр 1.1 является регистром сдвига с разрядностью t и задерживает делимое А на tтактов. С его выхода задержанное делимое А поступает на второй вход сумматора 2.1. Последний выполняет операцию вычитания в дополнительном коде с учетом переносов, запоминаемых на триггере 3.1. Единичный сигнал переноса с выхода переноса сумматора 2.1, вырабатываемый по окончанию операции вычитания не заносится в триггер 3.1, обнуляемый по входу сброса сигналом с (n+f)-ro выхода дешифратора, который формирует его под действием соответствующего кода на выходе счетчика 4. На выходе суммы сумматора 2.1 формируется величина А(2М). Полученная величина поступает поразрядно, начиная с младших разрядов, на первый вход сумматора 2.2 и на информационный вход регистра 1.2. Регистр 1.2 является регистром сдвига с разрядностью 2f. С его выхода величина А(2 -1) с задержкой 21 поступает на второй вход сумматора 2.2, который осуществляет сложение величины А(2 -1), поданной непосредственно и задержанной на 21 тактов с учетом переносов, задержанных на один такт для учета в следующем такте на триггере 3.2. При этом на выходе суммы сумматора 2.2 формируется величина А(2С- 1X2 + 1). Эта величина поступает на следующую часть схемы, составленную как и предыдущая из регистра, сумматора и триггера, имеющих номера соответственно 1.3, 2.3, 3.3 и в два раза большую разрядность регистра 1,3, т.е. At разрядов.

Таких частей в устройстве (г-1), где г определяет необходимую точность ю вычислений, причем на вход 1-й части устройства поступает величина Т А(2 - 1)(2 + +1)...(22 +1) с выхода суммы сумматора 2.1-1 0-1)-й части устройства, 1-я часть устройства составлена из регистра 1.1, сумматора 2.1, триггера 3.1. причем регистр 1. имеет разрядность в два раза большую, чем регистр 1.1-1, т.е. 2Н ч разрядов.

Величина Т поступает на первый вход сумматора 2.1 непосредственно и на его второй вход через регистр 1.1, задерживающий величину Т на 2м тактов. При этом сумматор 2.1 вычисляет их сумму в последовательном коде с учетом переносов, задерживаемых на триггере 3.1. равную величине Т(22М + 1). Таким образом, последняя r-я часть схемы аналогично формирует на выходе СУММЫ сумматора 2.г величину R A(2f- lX2Zt + 1)...(22Mt+ 1), равную (22rf- 1)Х, т.е. искомую величину X, сдвинутую (задержанную) на 2ГЈ разрядов с погрешностью в п младших разрядах, равной X.

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

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

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

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

Устройство для деления чисел на константу 2+1, содержащее группу сумматоров, группу триггеров, группу регистров.

«у

П

счетчик и элемент НЕ, причем вход делимого устройства соединен с информационным входом первого регистра группы, выход 1-го регистра группы (где 1 1,2г. г - точность

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

сумматора группы, вход начальной установки устройства соединен с входом сброса J -го триггера (где J 2.....Р) группы и входом сброса счетчика, вход синхронизации которого соединен с входом синхронизации 1-го

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

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

с выходом результата устройства.