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

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

2.Устройство поп. 1, отличаю 4 е е с я тем, что блок формирования сигнала удвоения содержит два узла приоритета, группу элементов И и элемент ИЛИ, примем пер-, вая группа входов блока соединена

с входами первого узла приоритета, вторая группа входов блока соединена с входами второго узла приоритета, одноимённые выходы первого и второго узлов приоритета соединены с входами соответствующих элементов И группы,-выходы которых соединены с входами элемента ИЛИ, выход которого является выходом блока.

3.Устройство по п. 1, о т л и чающееся тем, что блок формирования вычитаемого содержит элементы И, ИЛИ, сумматоры по модулю два, причем выходы элементов И t-й группы соединены с входами 1-го элемента ИЛИ ( 1,...,rt -1; п - количество управляющих входов; М Ш4-1; Ш- разрядность результата ), первый управляющий вход блока подключен к входу первого элемента ИЛИ, j-й управляющий вход блока (j 2,...,И -1) соединен с первым входом (J -с)-го элемента И группы ( 1,..., ,П-2 ), первым входом (j-1 )-го сумматора по модулю два и вхоДом (j -t-l го зтгемента ИЛИ,п -и управляющий вход блока соединен с первыми входами ( г -i)-x элементов И i-x группсоответственно и первым входом (n-l)-ro сумматора по модулю два,Е -и информационный вход блока (e ti-1 подклчен к вторым входам(ц- )-х элементов

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

.Устройство по п, 1, о т л и чающееся тем, что блок формирования слагаемых содержит k вычислительных узлов (1 - количество слагаемых ), каждый из которых содержит элементы И и ИЛИ, причем входы каждого элемента И первой группы соединены с последующим информационным входом соответствующей группы входов блока и последующим управляющим входом блока, выход каждого элемента И первой группы соединен с первыми входами соответствующих элементов ИЛИ первой и второй групп, второй вход каждого элемента ИЛИ первой группы соединен с выходом последующего элемента ИЛИ

первой группы и первым входом последующего элемента И второй группы,

третий вход первого элемента ИЛИ первой группы соединен с первым управляющим входом блока, второй вход каждого элемента И второй группы соединен с соответствующим информационным входом соответствующей группы, выходы первого и второго элементов И второй rpjflinM соединены соответственно с первым и вторым выходами данного вычислительного узла, выходы элементов И с третьего по р-й (р-разрядность слагаемых ) соединены с вторыми входами элементов ИЛИ второй группы с первого по {р-2|-й, выходы элементов ИЛИ второй группы являют- . ся последующими выходами данного вычислительного узла блока.

1

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

Известно ycfpoйcтвo для извлечения квадратного корня, содержащее два счетчика, элементы И и счетный триггер, дешифратор нуля и элемент задержки причем первый и второй входы пер- вого элемента И соединены соответственно с входом устройства и с выходом счетного триггера, а выход СО счетным входом первого счетчика 1 о Недостатком известного устройства являются ограниченные функциональные возможности, определяемые те что в устройстве извлекается корень квадратный только одного числа. Наиболее близким ,к предлагаемому является устройство для извлечени квадратного корня, содержащее (п-1) cyMMafopoB группу сумматоров по модулю два, группу элементов ИЛИ, группу элементов НЕ, (п-2) дополнительные группы из () сум маторов по модулю два в каждой и группу из fn-2).элементов И, причем выход каждого.)-го (j 1,2,...,п-|-н1) одноразрядного сумматора () го сумматора (1 1,2,...,п-1) соеди нен с первым входом (j s 1)-го одноразрядного сумматора 1-го сумматора, а второй вход первого одноразрядного сумматора i-го сумматора соединен с выходом переноса первого одноразрядного сумматора (1+1)-й группы 2. Недостатком известного устройства являются ограниченные функциональные возможности из-за того, что в устрой стве не извлекается корень из суммы квадратов операндов. Цель изобретения - расширение фун цйональных возможностей путем извлечения квадратного корня из.суммы ква .ратов операндов. Указанная цель достигается тем, что устройство для извлечения квадратного корня, содержащее два сумматора и элемент ИЛИ, содержит блок формирования слагаемых, сумматор-вы читатель, два регистра сдвига, распределитель импульсов, 6jioK формиро|вания вычитаемого, блок формирования сигнала удвоения, блок анализа, причем входы операндов устройства со единены с группами информационных входов блока формирования слагаемых, выходы блока формирования слагаемых и выход первого регистра сдвига соединены с входами первого сумматора, выходы разрядов которого соедине ны с первой группой входов блока формирования сигнала удвоения и первой группой информационных входов сумматора-вычитателя, выходы перено;са первого сумматора соеди«ены с входами элемента- ИЛИ, выход второго сумматора соединен с выходом устройства и с информационными входами , второго регисГра сдвига и блока формирования вычитаемого, выходы которого соединены с второй группой входов блока формирования сигнала удвоения и с второй группой информационных входов сумматора-вычитателя, выходы разрядов которого соединены с входами разрядов первого регистра сдвига, управляющий вход которого соединен с первым управляющим входом устройства и входом распределителя импульсов, выходы которого соединены с управляющими входами блока формирования слагаемых и блока формирования вычитаемого, второй управляющий вход устройства соединен с управляющим входом второго регистра сдвига, при этом блок анализа содержит триггер, сумматор по модулю два, элемент И, элемент ИЛИ, выход блока формирования сигнала удвбения соединен с первым управляющим входом сумматора-вычитателя и первыми входами элемента И и сумматора по модулю два блока анализа, выход элемента ИЛИ соединен с входом младшего разряда .второго сумматора и первым входом элемента ИЛИ блока анализа, выход триггера блока анализа соединен с вторыми входами сумматора по модулю два и элементов И и ИЛИ блока анализа, выход переноса сумматора-вычитателя соединен с первым входом триггера блока анализа, поугой вход которого подключен к первому управляющему входу устройства, выход элемента И блока анализа соединен с входом младшего разряда второго сумматора, выход сумматора по моду/Ж) два блока анализа соединен с входом младшего разряда второго регистра сдвига, выход элемента ИЛИ блока анализа соединен с вторым управляющим входом сумматора-вычитателя. Блок формирования сигнала удвоения содержит два узла приоритета, группу элементов И и элемент ИЛИ, причем первая группа входов блока соедин ена с входами первого узла приоритета, вторая группа входов блока соединена с входами второго узла приоритета, одноименные выходы первого и второго .узлов приоритета соединены с входами соответствующих элементов И группы, выходы которых соединены с входами элемента ИЛИ, выход которого является выходом блока. Блок формирования вычитаемого со,держит элементы Я, ИЛИ, сумматоры по модулю два, причем выходы элементов И i-й группы соединены с входами 1-го элемента ИЛИ (i 1,..., п-1; п - количество управляющих входов; п m+t; m - разрядность результата), первый управляющий вход Ьлока подключен к входу первого элемента ИЛИ, J-й управляющий вход блока (j 2,.. п-1) соединен с первым входом (j-q)го элемента И q-й группы (q 1,..., п-2), первым входом (j-l)-ro суммато ра по модулю два и входом (j+l)-ro элемента ИЛИ, п-й управляющий вход блока соединен с первыми входами (n-i)-x элементов И 1-х групп соответственно и первым входом (п-1)-го сумматора подмодулю два, -й информационный вход блока ( п-1) подключен к вторым входам (п- Е) -х элементов И групп с первой по 2-ю, выход первого элемента И каждой группы подключен к второму входу соответствующего сумматора по.модулю два, выход которого соединен с входоА последующего элемента ИЛИ, первый выхо блока соединен с шиной нулевого си1- нала, выходы блока с второго по {п+1)-й соединены с выходами элементов ИЛИ с первого поп-и соответственно, (п+2)-й выход блока подключен к h-му управляющему входу бло ка. Блок формирования слагаемых содер жит к вычислительных узлов (к - коли чество слагаемых ), каждый из которых содержит группы И и ИЛИ, причем входы каждого элемента И первой группы соединены с последующим информационным входом соответствующей группы вхо дов блока и последующим управляющим входом блока, выход каждого эгжмента И первой группы соединен с пеовым входами соответствующих элементов ИЛ j epвoй и второй групп, второй вход ка ого элемента ИЛИ первой группы соединен с выходом последующего элемента ИЛИ первой и nepBisiM входом последующего элемента И второй группы, третий вход первого элемента ИЛИ первой группы соединен с первым управляющим входом блока, второй вход каждого элемента И второй группы соединен с соответствующим информацион ным входом соответствующей группы, в ходы первого и второго элементов И второй группы соединены соответствен но- с первым И вторым выходами данного вычислительного узла, вы :оды э/ieментов И с третьего по р-й 1 р - разрядность слагаемых )соединены с вто108« рыми входами элементов ИЛИ втррой группы с первого по (р-2 )-й, выходы элементов ИЛИ второй группы являются последующими выходами данного вычислительного узла блока. На фиг, 1 представлена схема устройства для извлечения квадратного корня для случая, когда на фиг. 2 - схема блока анализа; на фиг. 3 - схема блока формирования рычитаемого; на фиг, Л - схема блока формирования сигнала удвоения; на фиг. 5 - схема К-го вычислительного узла блока формирования слагаемых. Устройство для извлечения квадратного корня содержит два сумматора 1;. и 1л, элемент ИЛИ 2, блок 3 анализа, сумматор-вычитатель , дварегистра сдвига, распределитель 6 импульсов, блок 7 формирования вычитаемого, блок 8 формирования сигнала удвоения, блок 9 формирования слагаемых, К входных шин 10 j (j 1,2,...,n), выходную шину (выход) 11, первый управляющий вход 12 и второй управляющий вход 13. Блок 9 формирования слагаемых выполнен, например, из к-вычислительных узлов 1А. Блок 7 формирования вычитаемого выполнен, например, из элементов И 15.i элементов ИЛИ 16 и сумматора 17 по модулю два. Выходы элементов И 15 1-й группы соединены с входами 1-го элемента ИЛИ 16 (1 1 ,2;...,п-1, П-- количество управляющих входов). Первый, управляющий вход блока 7 формирования вычитаемого подключен к входу первого элемента ИЛИ 16, J-й управляющий вход блока. 7 (j 2,3,..., n-i) соединен с первым входом (l-q)го элемента;И 15 q-й группы (q 1,2,,..,п-2), первым входом (j-1)го сумматора 17 по модулю два и входом (j +1)-го элемента ИЛИ 16, п-й управляющий вход блока 7 соединен с первыми входами (п-1) элементов И 15 i-x групп соответственно и первым входом (п -t.)ro сумматора 17 по модулю два. Каждый 2-й информационный вход блока (2 п-1) подключен ко вторым входам (п-Е)-х элементов И 15 групп с первой по В-ю. Выход первого элемента И 15 каждой группы подключен к второму входу соответствующего сумматора 17 по модулю два, выход которого соединен с входом последующего элемента ИЛИ 16. Первый выход блока формирования вычитаемого 7 соединен с шиной нулевого сигнала,выходы блока формирования вычитаемого 7 с второго по (п+1)-й соединены с выходами элементов ИЛИ 16 с первого по п-й соответственно, а (п+2)-й выход блока 7 тюдключен к п-му управляющему входу. Блок 8 формирования сигнала удвоения выполнен например, в виде двух узлов приоритета 18, 182 группы элементов И 19 и элемента-ИЛИ 20,причем первая груп-. па входов соединена с входами первого узла приоритета , вторая группа входов соединена с входами второго узла приоритета 182- Одноименные входы первого 18 и второго 18 узлов приоритета соединены с входами .соответствующих.элементов И 19.-выходы которых подключены к входам эле мента ИЛИ 20, выход которого является вы ходом блока. Каждый К-й вычислительный узел Т (К - количество слагаемых) блока 9 формирования Слагаемых выполнен,- например, в виде элементов И 2Т и элементов ИЛИ 22, причем входы каждого элемента И 21 первой группы соединены с последующими информационными входами соответствующей группы входов блока 9 и последующим управляющим входом этого блока. Выход каждого элемента И .21 первой группы вычислительного узла 14. соединен, с первыми входами соответствующих элементов ИЛИ 22 первой и второй групп, второй вход каждого элемента ИЛИ 22 первой группы соединен с выходом последующего элемента ИЛИ 22 первой группы и первым входом последующего элемента И 21 второй группы. Третий вход первого элемента ИЛИ 22 первой группы соединен с Ъервым управля .ющим входом блока 9 второй вход каж дого элемента И 21 второй Группы соединен с соответствующим информационным входом соответствующей групГ1Ы. Выходы первого и второго элементов -И 21 второй группы соединены соответственно с первым и вторым вы.ходами данного вычислительного узла И, Выходы элементов И 21 с третьего по р-й {р - разрядность слагаемых ) соединены с вторыми входами элементов ИЛИ 22 второй группы с первого по (р-2 )-й, а выходы элементов ИЛИ 22 второй группы являются последующими выходами данного вычислительного Узла блока 9.Входы шины 10J операндов устройства для извлечения квадратного корня {фиг. 1 78 соединены с группами информамионных входов соответствующих вычислитель ных узлов 14 блока 9 формирования слагаемых, выход которого и выход первого регистра 5 сдвига соединены с входами первого сумматора Ц, выходы разрядов которого соединены с первой группой входов блока 8 формирования сигнала удвоения ипервой группой информационных входов сумматора-вычитателя Ц. Выходы переноса первого сумматора 1 соединены с входами элемента ИЛИ 2. Выход второго сумматора 1j соединен с выходной шиной 11 устройства и с информационными входами второго регистра S сдви га и блока 7 формирования вычитаемого, выхопы KOTODoro соепинены с ВТО- . рой группой входов блока 8 формирования сигнала удвоения и.с второй группой информационных входов сумматоравычитателя k. Выходы разрядов сумматора-вычитателя k соединены с входами разрядов первого регистра 5 сдвига, управляющий вход которого соединен с первым управляющим входом 12 устройства и входом распределителя 6 импульсов, выходы которого соединены с управляющими входами блока 9 формирования слагаемых и блока 7 формирования вычитаемого. Второй управляющий вход 13 устройства соединен с управляющим входом второго регистра 5 сдвига. Блок 3 анализа содержит триггер 23, сумматор 2 по модулю два, элемент И 25 и элемент ИЛИ 26. Выход блока 8 формирования сигнала удвоения соединен с пер- , вым-управлякмцим входом суммат6ра-вы- читателя и первыми входами элемента И 25 и сумматора 24 по модулю два блока 3 анализа. Выход элемента ИЛИ 2 соединен с входом младшего разряда второго сумматора 1 и первым входом элемента ИЛИ 26 блока 3 анализа. Выход триггера 23 блока 3 анализа соединен с вторыми входами сумматора .24 по модулю, два и элементов И 25 и ИЛИ 26 блока 3 анализа. Выход переноса сумматора-вычитателя 4 соединен с первым входом триггера 23 блока 3 анализа, другой вход которого подключен к первому управляющему входу 12 устройства. Выход элемента И 25 блока 3 анализа соединен с входом младшего разряда второго сумматора . Выход сумматора 24 по модутво два, блока 3 анализа соединен с входом младщёго разряда второго регистра З сдвига, а выход элемента ИЛИ 26 блока 3 .ана 1015378лиза соединен с вторым управляющим входом сумматора-вычктателя Ц. Работу устройства для извлечения квадратного корня при реализации,, представленной х + ;с|+.. . s и записанной в,разрядной форме. j +... о (1)) поясним на конкретном примере, /. где

- разрядные век-;

торы, представляющие собой разрядное изображение х i, оС и О |

Обозначим в выражении (2) векторы

разрядные матрицы,представляющие собой 15 разрядное изображение X/ и оС при п « 3Запишем выражение С1 ) в развернутом виде для случая, когда п

.. . . л .. ,

. . 1

0

3 О

4 О

(,

о

8 о

(31

и j

и векторы

Ч

.

и

45 Каждый Е-ый разряд oL(,2,...,п) искомого вектора определяется

ПО выражению

1 о6 fi при(3):

(ej 10 , , ,

где г - значение переноса из старt I ri« v I %«|

шего разряда вектора x), определяемого на основании выражения

;,v{,,;.(,,v(,).v(,,

-{Z),v(.,Vvu,V(2,v(2,v(2)g(0) v(,(vfiV-(3J.v(,,| .Шрн/ 5f(e5(M).() 1 2 ) ,э,...,п (4) величина, принимающая значения Г 9-12-2 ,Чг-г) ,(Mlo 5) g 2,3,..., n При реализации вычислений в соответствии с (З)(5) возможен также один из двух случаев., Если при t-й реализации выражения (4) оказалось, мто et О, а при последующей реализации (А) (тоесть 6+1) значение переноса из старшего разряда в выражении () век тора JtfHL U)V2;i«-( ...f% равное единице, то аринимается, что о1. 1 и вычислительный процесс продолжается аналогично {3)(5). Если в результате. Е.-ГО вычисления по выражению (t)ei 1. а при последующей (Ё+1)-ой реализации по выражению П) вектор. ,. + .:. больше или равен удвоенному вектору (РЙ) ; т.е. выполняется неравенствоз ЧИ2Й е(,(И ТО далее выражение Cf) реализуется с удвоенным вектором , значение ot считается равным нулю, а к значений оС 1 добавляется еще единица. В основу критерия выполнения выражения (6} при (й+1 )-й реа лизации выражения (З) положено следующее: с 1, а также равенство ед нице любого старшего разряда (начиная с первого )dl(lt 1,2,...,В) при.равенстве единице m-го разряда вектора Устройство работает следующим образом. В исходном состоянии регистры 5, и триггер 23 блока 3 анализа находят ся в нулевом состоянии. С первого вы хода распределителя 6 импульсов подается единичный сигнал на первый разряд управляющего входа каждого вы числительного узла блока 9 формирования слагаемых и первый разряд управляющего входа блока 7 формирова 7812 ния вычитаемого. При подаче на пер- вую 10, вторую 102 каждую j-ю 10J . входные шины устройства соответственно первого Х, второго Х2 и j -го векторов в схеме проходит переходной процесс, после окончания которого на выходе каждого j-ro вычислительного узла 1 блока 9 формирования слагаемых образуются значения векторов v(2| v/-iii. Г X | поступающие на вход первого сумматора 1, а на выходе блока 7 формирования вычитаемого образуется значение вектоо.а i , поступаюсцее на второй вход сумматора-вычитателя ч. В первом сумматоре 1- реализуется сумма векторрв 1, с его выхода поступающая на первый вход сумматора-вычитателя Ц, в котором по выражению (} определяется значение век51 , поступающее на вход первотораго регистра 5:,, а на выходе переноса старшего разряда сумматора-вычитателя k по выражению (3) образуется значение старшего разряда искомого вектора (ft .поступающее на вход триггера 23 блока 3 анализа.После этого на первый управляющий вход 12 подается импульс, по переднему фронту которого реализуется запись в триггер 23 блока 3 анализа значения , запись в перрый регистр 5 значения вектора х и добавление к содержимому распределителя 6 импульсов очередной единицы,а по заднему фронту импульса реализуется сдвиг информации в сторону старших разрядов на один разряд в первом регистре 5. Благодаря этоку с второго выхода распределителя 6 импульсов поступает единичный сигнал на второй разряд управляющих входов блоков 9 формирования слагаемых и вычитаемого 7. При этом с выхода каждого j-ro вычисг. тельного узла 1 блока 9 формирования слагаемых снимаются векторы , Ч ,. ..,, поступающие на входы первого сумматора Ц ,на( вход которого поступает значение вектора, х а с выхода элемента ИЛИ 26 |блока 3 анализа в соответствии с (5) поступает сигнал V сложения или 1 вычитания на второй управляющий вход сумматора-вычитателя k и в устройстве снова идет переходной процесс. В это же время через промежуток Т, равный времени суммирования во втором сумматоре 1„ после подачи первого импульса на второй управляющий вход 13 подается второй импульс, по переднему фронту которого значение 13 . xif с выхода сумматора 2 по модулю два блока 3 анализа записывается в младший(п+1)-и разряд второго ре- j гистра 52, а по заднему фронту peaлизуется в нем сдвиг информации на один разряд в сторону старших разрядов. После окончания переходного процесса в устройстве на управляющие входы 12. и 13 подается очередная пара импульсов, после чего процесс продолжается аналогично вышеописанному о Таким образом, после по дачи на управляющие входы 12 и 13 И пар импульсов во втором регистре 5 2 соответственно на выходе 1 Г устройства образуются значе ния разрядов искомого вектора о(.. Если в результате поступления на уп равляющие входы 12 и 1311 пар импул сов значение ч. О, а после окончания переходного процесса оказывается, что на одном из выходов переноса старшего;разряда первого сумма тора 1 образовался единичный сиг нал, ,то он-через элемент ИЛИ 2 поступает на вход младшего разряда второго сумматора In, благодаря чем oL становится равным единице, кроме того, этот сигнал через элемент ИЛИ 26 блока 3 анализа поступает на второй управляющий вход сумматора-вычитателя k, настраивая его тем самым в соответствии с { 5 ) на вычитание. Далее вычислительный про цесс продолжается аналогично вышеописанному. Если в результате пост;у ления И пар импульсов значение оС -1 а после окончания переходного процесса оказывается, что значениет-г разряда(tn 1,2, ...,б первого сумматора Ц равно единице при условии, что значение т-го. разряда оС искомого вектора также равно единице при равенстве нулю значений всех предшествующих разрядов, т.е.о1 0 ... , то в этом случае на выходе блока 8 формирования 78 сигнала удвоения образуется единичный сигнал, поступающий на первые входы элементов И 25 сумматора 2 пр модулю два блока 3 анализа 3 и управляющий вход сумматора-вычитате- ля k. Благодаря этому вектор поступающий из выхода блока 7 формирования вычитаемого на второй вход , сумматора-вычитателя , сдвигается в нем в сторону старших разрядов на . один разряд а выражение (f ) реализуется соответственно с удвоенным вектором При этом, если на выходе переноса старшего разрядасумматора-вычитателя образуется единичный сигнал, то он после подачи первого импульса на первый управляю-щий вход 12 очерёдной пары импульсов поступает через первый вход и выход элемента И 25 блока 3 анализа на вход младшего разряда вто|эого сумматора 1 и суммируется с его содержимым. В этом случае к значению добавляется единица, очередное значениесС о, а на выходе элемента ИЛИ 26 блока 3 анализа образует,ся единичный сигнал, настраивающий сумнатор-вычитатель k на вычитание. Если на выходе перенбса старшего разряда сумматора-вычитателя образовался нулевой сигнал, то после поступг ления первого импульса на выходах элементов И 25, ИЛИ 26 и сумматора 2 по модулю два блока 3 анализа образуются соответственно нулевой, ёди ничный .и нулевой сигналы, что сортветствуето, 1, к значению оС ничего не добавляется, а сумматорвычитатель k настраивается на сложение. После этого вычислительный процесс продолжается аналогично вышеописанному. По сравнению с прототипом данное устройство имеет более широкие функциональные возможности, так как позволяет вычислять квадратный корень из суммы квадратов операндов.

«e. i

0 fs у /Ji

we.j

Ё

f

I

futA

Фи9.5