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

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

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

На фиг. 1 представлена блок-схема устройства для вычисления квадратного корня; на фиг. 2 - схема регист-/ ра результата ; на фиг. 3 - схема суммиругаце-вычитающего элемента.

Устройство содержит регистр 1 результата, сумматор-вычитатель 2, состоящий из (п+1) суммирующе-вычи- тающих элементов 3, триггер 4 знака, вход 5 начальной установки и вход 6 синхронизации устройства.

Регистр 1 результата образуют п 1К-триггеров 7, вспомогательный IK- триггер 8, первую 9, вторую 10,

третью 11 и четвертую 12 группу элементов И, первую 13 и вторую 14 группы элементов ИЛИ 13 и 14, элемент НЕ 15, входы 16-18 регистра результата. Суммирутоще-вычитающий элемент 3 содержит D-триггер 19, элементы И 20-27, элементы ИЛИ 28-34, элементы НЕ 35-38, входы 39-45 и выходы 46 и 47.

Вычисление квадратного корня осуществляется следующим образом..

По сигналу начальной установки, поступающему на вход 5 устройства, подкоренное выражение, содержащее п двоичных разрядов, заносится в сумматор-вычитатель 2. В старшем (левом) разряде (п+1) сумматора-вычитателя 2 устанавливается О. В триггер 4 знака записывается О.

О

СП

31501

Одновременно в (п-1)-й разряд регистра 1 результата заносится 1, а в остальные разряды регистра 1 - О На второй информационньш вход 40 слагаемого (вычитаемого) старшего (пч-1)-го суммирующе-вычитающего элемента 3 всегда подан О.

Сначала производится вычисление квадратного корня из старших двух цифр подкоренного вьфажения. Для этого с помощью сумматора-вычитателя 2 производится вычитание содержимого регистра 1 из подкоренного выражения В сумматоре-вычитателе 2 формируется промежуточньм остаток. Значение старшего (п+1)-го суммирующе-вычитающего элемента 3, соответствующее знаку остатка, подается на информационный вход 16 регистра 1 и на информацион- ньй вход триггера 4 знака и по положительному фронту синхроимпульса, поступающего на вход 6 устройства, зписывается в треггер 4 знака и в инверсном коде в п-й разряд регистра 1 (первая цифра корня).

Если остаток положительный в п-й разряд регистра 1. записывается 1, если отрицательный - в данном разряде регистра 1 остается О,

Одновременно в (п-2)-й разряд регистра 1 заносится , Если остаток положительньй в (п-1)-й разряд ре- гистра 1 записывается О, В случае отрицательного остатка в данном разряде регистра 1 остается 1.

По положительному фронту синхроимпульса производится также сдвиг содержимого сумматора-вычитателя 2 н один разряд влево.

Для получения второй цифры корня в зависимости от знака первого промежуточного остатка, записанного в . : . триггере 4 знака,, выполняется сложение или вычитание содержимого регист ра 1 из остатка. Ксли остаток положительный (на выходе триггера 4 знака - О) производится операция вычитания, если отрицательный (на выходе триггера 4 знака - 1) - опе- ращля сложения. В результате в сумматоре-вычитателе 2 формируется новый остаток.

После получения второго промежуточного остатка на вход 6 устройства подается синхроимпульс. В триггер 4 знака заносится знак текущего остатка, а в (п-1)-й разряд регистра 1 - вторая цифра корня. Одновременно про

Q 5 0 5

0

0

5

5

изводится запись 1 в (п-З)-й разряд регистра 1. Если остаток положительный в (п-2)-й разряд регистра 1 заносится О, В случае отрицательного остатка в данном разряде регистра 1 остается 1, Затем определяется третья цифра корня.

Пример, Вычисление квадратного корня из числа 0,101010,

В табл, 1 приведены значения логических сигналов на информационных входах и выходах триггеров 7 и 8 для данного примера.

Сигнал начальной установки поступает через вход 18 регистра 1 на вход сброса триггера 7 (n-l)-ro разряда, устанавливая на его инверсном выходе 1, и на вход установки 1 триггеров 7 остальных разрядов и триггера 8, устанавливая на их инверсных выходах О.

Одновременно сигнал начальной установки поступает через вход 43 всех суммирующе-вычитающих элементов 3 сумматора-вычитателя 2 на входы элементов ИЛИ 33 и 34, на вторые входы которых через первый информационный вход 39 подаются разряды подкоренного выражения. Значения разрядов подкоренного выражения записываются в триггеры 19 соответствующих суммирующе-вычитакщих элементов 3,

Сигнал начальной установки поступает на вход сброса триггера 4 знака, устанавливая на его выходе О.

Сигнал с выхода триггера 4 знака поступает на управлякщий вход 45 всех суммирующе-вычитающих элементов 3 сумматора-вычитателя 2, По этому сигналу производится вычитание содержимого регистра 1.из подкоренного выражения.

1-и цикл,

Сумматор-вычитатель 2 О 101010

Регистр 1О 010000

Сумматор-вычитатель 2 О 011010

На выходе 46 (п+1)-го суммирующе- вычитающего элемента 3 сумматора-вычитателя 2 присутствует О. На вход 6 синхронизации устройства подается синхроимпульс,

На первый вход п-го элемента И 11 регистра 1 подан сигнал 1, на первый вход остальных элементов И 11 - О, на второй и третий входы всех элементов И 11 - 1. На первый вход (п-2)-го элемента И 12 регистра 1 подан сигнал 1, на первый вход ос5150

тальных элементов Н 12 - О, на второй вход всех элементов И 12 - 1. На первый вход (п-1)-го элемента ИЛИ 13 регистра 1 с выхода п-го элемента И 11 подан сигнал 1, на входы остальных элементов ИЛИ 13 - О. По положительному фронту синхроимпульса, поступающего через вход 17 регистра 1 на динамические такто- вые входы триггеров 7 и 8, на инверсном выходе триггера 7 п-го разряда устанавливается сигнал- 1, являющийся первой цифрой корня, так как на

К-вход этого триггера подана 1 с

выхода п-го элемента И 11, на инверсном выходе триггера 7 (п-1.)-го. разряда О, так как на 1-вход ч .ч-о триггера подана 1 с выход:; ()-r элемента ИЛИ 13, на инверсном E:.-/;;v e триггера 7 (п-2)-го разряда - i так как на К-вход этого триггера л, на 1 с выхода (п-2)-го элемента ИЛИ 14.

Одновременно по положительному фронту синхроимпульса, поступающего через вход А2 всех суммирующе-вычи- тающих элементов 3 сумматора-вычита- теля 2 на динамические тактовые входы триггеров 19, производится сдвиг содержимого сумматора-вычитателя 2 (первого промежуточного остатка) на один разря д влево, так как третий информационный вход 41 i-ro суммирую ще-вычитающего элемента 3 подключен к выходу 46 (i-l)-ro суммирующе-вычи тагацего элемента 3 сумматора-вычитателя 2,

По пoлoжитeльнo гy фронту синхроимпульса в триггер 4 знака записывается О с выхода 46 (п+1)-го сумми- рующе-вычитающего элемента 3 суг-мато ра-вычитателя 2.

Сигнал О с выхода триггера 4 знака поступает на управляющий вход 45 всех суммирующе-вычитакщих элементов 3 сумматора-вычитателя 2. По этому сигналу производится вычитание содержимого регистра 1 из содержимого сумматора-вычитателя 2. 2-й цикл. Сумматор-вычитатель 2 О 110100 Регистр 1О 101000

Сумматор-вычитатель 2 О 001100 На выходе 46 (п+1)-го суммирующе- вычитающего элемента 3 сумматора-вы- читателя 2 присутствует О. На вход 6 синхронизации устройства подается синхроимпульс.

Q

5

,-,

5 п

5

0

На первьй вход (n-l)-ro элемента И 11 .регистра 1 подан сигнал 1, на второй вход остальных элементов И 11 - О, на второй вход всех элементов И 11 - 1, на третий вход п-го элемент.а И 11 с выхода (п-2)-го элемента И 9 подан сигна- 0, на третий вход остальных элементов И 11 - 1. На первый вход (п-З)-го элемента И 12 регистра 1 подан сигнал 1, на первый вход остальных элементов И 12 - О, на второй вход (п-2)-го элемента И 12 с выхода (п-2)-го элемента И 9 подан сигнал О, на второй вход остальных элементов И 12 - 1. На первый вход (п-2)- го элемента ИЛИ 13 регистра 1 с выхода (п-1)-го элемента И 11 подан сигнал 1, на входы остальных элементов ИЛИ 13 - О. По положитель- ijof-fy фронту синхроимпульса, пост паю- щего через вход 17-регистра 1 на динамические тактовые входы триггеров 7 и 8, на инверсном выходе триггера 7 (п-1)-го разряда устанавливается сигнал 1 (вторая цифра корня), на инверсном выходе триггера 7 (п-2)-го разряда - О, на инверсном выходе триггера 7 (п-З)-го разряда - 1, Одновременно производится сдвиг содержимого сумматоря-вычитателя 2 (второй промежуточньй остаток) на один разряд влево и запись О, в триггер 4 знака.

Сигнал О с выхода триггера 4 знака поступает на управляющий вход 45 всех суммирующе-вычитакщих элементов 3 сумматора-вычитателя 2. По этому сигналу производится вычитание содержимого регистра 1 из содержимого сумматор р- кычитателя 2, 3-й- цикл.

Сумматор-вычитатель 2 0 011000 Регистр 1О 110100

Сумматор-вычитатель 2 1 100100

На выходе 46 (п+1)-го суммирующе- вычитающего элемента 3 сумматора-вы- чнтателя 2 присутствует 1. На вход 6 синхронизации устройства подается синхроимпульс.

На инверсном выходе триггера 7 (п-2)-го разряда регистра 1 остается сигнал О (третья цифра корня). На инверсном выходе триггера 7 (п-З)-го разряда остается сигнал 1. На инверсном выходе триггера 7 (п-4)-го разряда устанавливается 1.

Одновременно производится сдвиг содержимого сумматора-вычитателя 2 на один разряд влево и запись 1 с выхода 46 (п+1)-го суммирующе-вычитающего элемента 3 сумматора-вычитателя 2 в триггере 4 знака.

Сигнал 1 с выхода триггера 4 знака поступает на управляющий вход 45 всех суммирующе-вычитающих элементов 3 сумматора-вычитателя 2, По этому сигналу производится сложение содержимого регистра 1 и сумматора- вычитателя 2. 4-й цикл.

Сумматор-вычитатель 2 1 001000 Регистр 1О 110110

Сумматор-Бычитатель 2 1 111110 На выходе 46 (п+1)-го суммирующе- вычитающего элемента 3 сумматора-вы- чнтателя 2 присутствует 1, на вход 6 синхронизации устройства подается синхроимпульс,

На инверсном выходе триггера 7 (п-З)-го разряда регистра 1 устанавливается сигнал О (четвертая цифра корня), На инверсном выходе триггера 7 (п-4)-го разряда остается 1 На инверсном выходе триггера 7 (п-5)-го разряда устанавливается 1

Одновременно производится сдвиг содержимого сумматора-вычитателя 2 на один разряд влево и запись 1 с выхода 46 (п+1)-го суммирукще-вы- читающего элемента 3 сумматора-вычитателя 2 в триггер 4 знака. По этому сигналу производится сложение содержимого регистра 1 и сумматора-вычитателя 2,

5-й цикл, Сумматор-вычитатель 2

1 111100

+

о 110011 о 101111

Регистр 1

Сумматор-вычитатель 2

На выходе. 46 (п+1)-го суммирующе- вычитающего элемента 3 сумматора-вычитателя 2 присутствует О, На вход 6 синхронизации устройства подается синхроимпульс,

На инверс ном выходе триггера 7 (п-4)-го-разряда регистра 1 устанавливается 1 (пятая цифра корня). На инверсном выходе триггера 7 (п-5)-го разряда устанавливается О. На инверсном выходе вспомогательного триггера 8 устанавливается 1,

Одновременно производится сдвиг содержимого сумматора-вычитателя 2 на один разряд влево и запись О в

010518

триггер 4 знака. По этому сигналу производится вычитание содержимого регистра 1 из содержимого сумматора- вычитателя 2.

В младшем (п-5)-м (для данного примера) суммирующе-вычитающем элементе 3 сумматора-вычитателя 2 присутствует 1, так как на вход 44 переноса (заема) этого элемента подан сигнал 1 с инверсного выхода вспомогательного триггера 8 регистра 1.

6-й цикл,

Сумматор-вычитатель 2 1 011110

10

5

0

5

0

5

0

5

5

0

Регистр 1О 1100101

Сумматор-вычитатель 2 О 101011 На выходе 46 (п+1)-го суммирующе- вычитающего элемента 3 сумматора-вычитателя 2 присутствует О. На вход синхронизации 6 устройства подается синхроимпульс.

На инверсном выходе триггера 7 (п-5)-го разряда регистра 1 устанавливается 1 (шестая цифра корня). Одновременно производится сдвиг содержимого сумматора-вычитателя 2 на один разряд влево и запись О в триггер 4 знака.

На инверсных выходах триггеров 7 регистра 1 установлен код: О 110011 (результат вычисления квадратного корня).

I

Работа i-ro суммирующе-вычитающего элемента 3 сумматора-вычитателя 2 производится в соответствии с табл. 2, В табл, 2 приняты следующие обозначения: А - первое слагаемое (уменьшаемое) - сигнал на выходе триггера 19 i-ro суммирующе-вычитаю- щего элемента 3, В - второе слагаемое (вычитаемое) - сигнал на втором информационном входе 40 i-ro сумми- рующе-вычитанщего элемента 3, С - сумма (разность) - сигнал на выходе 46 i-ro суммирующе-вычитающего элемента 3, Н - сигнал переноса (заема) предьщущего (i-1)-ro сумми- рующе-вычитакщего элемента 3 - сигнал на входе 44 i-ro.суммирующе-вычитающего элемента 3; А; - сигнал переноса (заема) для следующего (i+1)-ro суммируклце-вычитающего элемента 3 - сигнал на выходе 47 i-ro суммирующе- вычитающего элемента 3, Выбор операции (сложение или вычитание) произво- . дится по управляющему входу 45 суммирующе-вычитающего элемента 3,

При начальной записи подкоренного вьфажения в сумматор-вычитатель 2 i-я цифра вводится с первого информационного входа 39 i-ro суммирующе- вычитакщего элемента 3 при поступлении сигнала начальной установки на вход 43 суммирующе-вычитающего элемента 3,

Для организации сдвига содержимого сумматора-вычитателя 2 на один разряд влево цифра, соответствующая (1-1)-му разряду, с вьгхода 46 (i-l)-r суммирующе-вь читающего элемента 3 подается на третий информационный вход 41 i-ro суммирующе-вычитающего элемента 3, а сигнал синхронизации поступает на вход 43 всех суммирующе- вычитающих элементов 3,

o

5

0

мирующе-вычитающих элементов являются входами подкоренного вьфажения устройства, первый и второй информационные входы (п+1)-го суммирующе- вычитакяцего элемента подключены к : входу логического нуля устройства, вход начальной установки которого соединен с входами начальной установки регистра результата, суммирующе- вычитающих элементов И, R-входом триггера знака, вход синхронизации устройства соединен с входами синхронизации регистра результата, сумми- руклце-вычитающих элементов и триггера знака,инверсные выходы п триггеров подключены к вторым информационным входам одноименных суммирующе-вычитающих элементов, выход f-ro суммирующе-вычитающего элеме тта (f

Изобретение относится к вычислительной технике и служит для аппаратурной реализации операции вычисления квадратного корня. Цель изобретения - повышение быстродействия - достигается тем, что в устройство введен триггер знака, а в регистр результата - N-1 элементов И второй группы, N элементов И третьей группы, N-2 элементов И четвертой группы, N-1 элементов ИЛИ первой группы, N-2 элементов ИЛИ второй группы и элемент НЕ. При этом уменьшается длительность каждого цикла вычисления за счет исключения такта записи промежуточного остатка из сумматора в регистр сдвига. 1 з.п. ф-лы, 3 ил. 2 табл.

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

установки регистра результата, С-вхо-.- выход (п-1)-го триггера соединен с

ды всех триггеров которого подключены к входу синхронизации регистра результата, отличающееся тем, что, с целью повышения быстродействия, в него введен триггер знака, сумматор-вычитатель содержит (п+1) суммирующе-вычитающих элемента, а в регистр результата введены (n-t)-и элемент И второй группы, п элементов И третьей группы, (п-2)-и элемента И четвертой группы, (п-1)-й элемент

ИЛИ первой группы, (п-2)-и элемент ИЛИ второй группы и элемент НЕ, причем первые информационные входы сум50

55

первым входом п-гр элемента И трет группы и с первым входом (п-2)-го элемента И четвертой группы, инверс ный выход первого триггера подключе к первым входам вторых элементов И второй и третьей групц., инверсный выход вспомогательного триггера под ключен к первым входам первых элеме тов И второй и третьей групп, выход р-го элемента И первой группы ( р 1,, . , п-3) подулючен к второму входу р-го элемента И четвертой гру пы и третьим входам (р+2)-х элемент И второй и третьей групп, выход

.-j

n) соединен с третьим ин5

0

5

0

формационным входом (f+1)-ro суммирующе-вычитающего элемента, третий информационный вход первого суммирую- щего-вычитакщего элемента подключен к входу логического нуля устройства, выход (п+,1)-го суммирующе-вычитающего элемента подключен к информационному входу регистра результата и D-входу триггера,знака, выход которого соединен с управляющими входами всех суммирующе-вычи акщих элементов, вход заема h-ro суммирующе-вычитающего элемента (h 2, ..., n+ l) подключен к выходу заема (h-1)-ro суммирующе-вычитающего элемента, вход заема первого из которых подключен к инверсному выходу вспомогательного триггера регистра результата, инверсный выход 1-го триггера (1 2, ..., п-2) подключен к первым входам (1+1)-х элементов И второй и третьей групп и первому входу (1-1)-го элемента И четвертой группы, инверсный

0

5

первым входом п-гр элемента И третьей группы и с первым входом (п-2)-го элемента И четвертой группы, инверсный выход первого триггера подключен к первым входам вторых элементов И второй и третьей групц., инверсный выход вспомогательного триггера подключен к первым входам первых элементов И второй и третьей групп, выход р-го элемента И первой группы ( р 1,, . , п-3) подулючен к второму входу р-го элемента И четвертой группы и третьим входам (р+2)-х элементов И второй и третьей групп, выход

11130

п-2)-го элемента И первой группы оединен с вторым входом (п-2)-го лемента И четвертой группы к, третьим входом п-го элемента И третьей группы, третий вход второго элемента И второй группы соединен с третьим входом второго элемента И третьей группы и подключен к прямому выходу вспомогательного триггера, информационный вход регистра результата соединен с вторыми входами всех элементов И второй группы и входом элемента НЕ, выход которого подключен к вторым входам всех элементов И,третьей группы, выход q-ro эле мента И второй группы (q 1, ..., п-1) подключен к второму входу q-ro элемента ИЛИ первой группы, выход которого соединен с 1-входом q-ro триггера, выход элемента И третьей группы (г 2, ,.,, п-2) подключен к первому входу (r-l)-ro элемента ИЛИ первой группы и второму входу г-го элемента ИЛИ второй группы, выход первого элемента И третьей группы подключен к второму входу первого элемента ИЛИ второй группы, выход (п-1)-го элемента И третьей группы соединен с первым входом (п-2)-го элемента ИЛИ первой группы и К-входом (п-1)-го триггера, выход п-го элемента И третьей .группы подключен к первому входу (п-1)-го элемента -ИЛИ первой группы и К-вхо- ду п-го триггера, 1-вход п-го триггера подключен к входу логического нуля устройства, выход W-ro элемента И четвертой группы (W 1, ... п-2) соединен с первым входом W-ro элемента ИЛИ второй группы, выход которого подключен к К-му входу W-ro триггера, S-вход п-го триггера соединен с входом начальной установки регистра результата,

мента ИЛИ и является входом начальной установки i-roсуммирующе-вычитающего элемента, а выход подключен к S-входу D-триггера, R-вход которого подключен к выходу шестого элемента И.ПИ, D-вход и С-вход триггера являют- ел соответственно третьим информационным входом и входом синхронизации i-ro суммирующе-вычитающего элемента, а выход подключен к первым входам третьего и первого элементов И соответственно, второй вход первого из которых соединен с первым входом вто- рого элемента И и является вторым информационным входом i-ro суммирующе- вычитающего элемента, а выход подключен к входу первого элемента НЕ и первому входу второго элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И и входу второго элемента НЕ, а выход - к первому входу восьмого элемента И, второй вход которого объединен с входом третьего элемента НЕ и является управляющим входом i-ro суммирующе-вы- читающего; элемента, а выход подключен к первому входу пятого элемента РШИ, второй вход которого соединен с вы- ходом седьмого элемента И, а выход

является выходом заема i-ro суммирую- ще-вычитающего элемента, выход первого элемента НЕ соединен с вторыми входами первого и второго элементов И, выход первого элемента И соединен с первым входом третьего элемента ИЛИ, второй вход которого подключен к выходу второго элемента И и первому входу первого элемента ИЛИ, вы- R которого соединен с первым входом седьмого элемента И второй вход которого подключен к выходу третьего элемента НЕ, вход заема i-ro суммирующе-вычитающего элемента соединен

с первыми входами четвертого и пятого элементов И, второй вход первого из которых объединен с первым входом шестого элемента И и подключен к выходу третьего элемента ИЛИ, выход второго элемента НЕ соединен с вторыми входами пятого и шестого элементов И, выход первого из которых подключен к второму входу первого элемента ИЛИ и первому входу четвертого элемента ИЛИ, второй вход которого подключен к выходу шестого элемента И, а выход - является выходом i-re суммирующе-вычитающего элемента.

- - ОО ОО о

О ОО ОО - -.-г

t

О ОО ОО ОО О| О ОО г- ОО r-j

О ОО - - ОО - I

ОО ОО - ОО о

ОО . ОО

О- ОО ОО ОО о

- ОО - ОО 01

--о - - ОО ОО.О

ОО ОО ОО О1

ОО ОО ОО ОО о

о-- ОО ОО ОО о

о ОО ОО ОО О|

I I

о-- ОО ОО ОО о

т- о - -о о ОО ОО ОО ОО о

о-- ОО ОО ОО о

ОООО ОО ОО ОО ОО о

--г-. ОО ОО ОО ОО ОО о

--0 -о - о -о

in vO I

15

1501051

Вход rrodrtopf ffoeo ebipa tteHUA о

16

Табли.ца2

фаёЛ

фие.З