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

(Л

с

Изобретение относится к вычислительной технике и может быть использовано в универсальных и специализированных вычислительных системах для аппаратной ре- ализации операции извлечения квадратного корня из суммы квадратов. Целью изобретения является сокращение аппаратурных затрат. Устройство содержит блок 1 управления, сумматоры 2.1-2.6 по модулю два, мультиплексоры 3.1-8.3, регистры 4 1-4.3, сдвигателиб 1-5.5, сумматоры 6 1, 62 и 7 1 з п ф-лы, 3 ил.

Ю

/;

sj

СЛ

«Д

ч

СЛ

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

.

ализации операции вида U vx + у в формате с фиксированной запятой.

Цель изобретения - сокращение аппаратурных затрат.

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

Устройство содержит блок 1 управления, шесть сумматоров 2 по модулю два, три мультиплексора 3, три регистра 4, пять сдвигателей 5, два трехвходовых сумматора 6, двухвходовый сумматор 7, имеет четыре входа 8-11 и два выхода 12 и 13.

Блок управления включает в себя узел 14 формирования управляющих сигналов, два узла 15 выбора старшей единицы, мультиплексор 16, сдвигатель 17, два сумматора 18 по модулю два, вентильную схему 19, элемент НЕ 20, узел 21 формирования управляющих кодов сдвига, а также имеет первый 10, второй 11, третий 22, четвертый 23 и пятый 24 входы, первый 12, второй 25, третий 26, четвертый 27, пятый 28, шестой 29, седьмой 30 и восьмой 31 выходы.

Узел формирования управляющих сигналов содержит девять элементов И 32 и пять элементов ИЛИ 33 и имеет первый 34, второй 10, третий 35, четвертый 11, пятый 36, шестой 37 и седьмой 38 входы, а также первый 12, второй 25, третий 26, четвертый 39, пятый 27, шестой 28 и седьмой 29 выходы.

Работа устройства основана на использовании итерационного алгоритма вычисления модуля комплексного числа, реализующего мультипликативный метод вычислений,

Устройство производит вычисление модуля комплексного числа Z x+ yi, ,1, ,1, т.е. выполнение операции U

Р+7

(1)

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

Вычисление значения U производится в два этапа. На первом этапеУ КЈ {1,2,. ..q} вычисления выполняются с использованием рекуррентных соотношений: ak: ak-i-Sk.bk-i.2-Jk-ak-i.2-(2Jk42) (2)

bk: bk-H-Sk.ak-i.2 J -bk-l.2(2jk+2); (3) Ck: ck-i+ck-i.,(4)

Начальные значения переменных определяются соотношениями .Sgny;(5)

.Sgnx;(6)

.(7)

Значение Sk определяется на первом этапе вычислений знаком операнда ak 1:

Sk Sgnak-i 1-2.ak-i(0)(8)

Значение величины jk на первом этапе вычислений определяется разностью номе ров старшего единичного (нулевого) разря- да кода ak-i при положительном (отрицательном) значении величины ak-i и старшего единичного разряда кода bk-i в соответствии с выражениями:

jik: mln{j G No) bk-i(j)- 1);(9)

J2k: mln0e ДО) аыОЬамШ (10) Jk: max{0.j2k-Jik}(11)

Первый этап вычислений продолжается до тех пор, пока в результате выполнения очередной q-й итерации не будет выполнено условие

|aq| 2Л(12)

где m -мультипликативная разрядность вычислений, m if.

Второй этап вычислений реализует вы- числения с использованием рекуррентных соотношений Vk6{q+1, q+2t}

bk: bk-i+Sk.bk-i.(13)

ck: Ck-l+ Sk.Ck-l.(14)

На втором этапе вычислений значение Sk определяется значением старшего (нулевого) разряда кода переменной см в соответствии с выражением

(1-Ck-iH-2ck-i(0).(15)

Старший нулевой разряд кода сы определяет значение целой части операнда сы, который всегда положителен.

Значение величины jk на втором этапе вычислений определяется номером старше- го нулевого (единичного) разряда дробной части кода ck-i при сы 1 (ck-i 1) в соответствии с выражением

{JEINJ Ck-iQh см(0)}(16)

Второй этап вычислений продолжается до тех пор, пока в результате выполнения очередной t-й итерации не будет выполнено условие

I1-ct| 2 m(17)

По окончании вычислений значение операнда bt используется в качестве результата U.

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

В исходном состоянии признак Конец операции, поступающий с первого выхода блока 1 управления на выход 12 устройства, имеет единичное значение. На входы 8 и 9 устройства поступают значения аргументов у и х соответственно.

При поступлении в устройство коды аргументов дополняются нулями до V числовых разрядов (V - вычислительная разрядность, обеспечивающая заданную величину погрешности при усечении чисел, сдвигаемых за пределы разрядной сетки V т). На вход 11 устройства непрерывно поступают тактовые импульсы (ТИ). Первый и второй сумматоры 2 по модулю два осуществляют поразрядное суммирование значений у и х, поступающих на их первые входы, с поступившими на их вторые входы знаковыми разрядами указанных переменныху{0) и х(0), формируя значения а0 и bo согласно (2) и (3) соответственно. Начальное значение поступает на информационный вход третьего мультиплексора 3. Единичный уровень признака Конец операции, поступая с первого выхода блока 1 управления на управляющие входы первого, второго и третьего мультиплексоров 3, обеспечивает прохождение информации с вторых информационных входов мультиплексоров 3 на их выходы и далее на информационные входы первого, второго и третьего регистров 4 соответственно.

Для начала вычислений синхронно с одним из ТИ на вход 10 устройства подается сигнал Пуск, поступающий на первый вход блока 1 управления. Блок 1 управления по сигналу Пуск формирует сигнал Занесение 1 на своем втором и сигнал Занесение 2 на своем третьем выходе.

Сигнал Занесение 1, поступающий на вход занесения первого регистра 4, и сигнал Занесение 2, поступающий на входы занесения второго и третьего регистров 4, обес- печивает занесение в регистры 4 сформированных на их информационных входах начальных значений переменных. С выходов регистров 4 информация поступает на соответствующие входы блока 1 управле- ния.

Если значение переменной ао равно нулю, признак Конец операции сохраняет единичное значение и вычисления не производятся. Значение Ь0 в этом случае поступает на выход 13 устройства в качестве результата вычислений. При отличных от ну

ля значениях геременных а0 и Ь0 признак Конец операции принимает нулевое значение и в устройстве начинается первый этап вычислений.

На первом этапе вычислений при выполнении k-й итерации УкЈ{1,2,...,q} на вторые входы третьего и четвертого, второй вход пятого и второй вход шестого сумматоров 2 по модулю два с четвертого, пятого и шестого выходов блока 1 управления поступают сигналы Инверсия 1, Инверсия 2 и Инверсия 3 соответственно, значения которых определяются таблицей.

15

20

На первые входы третьего и пятого сумматоров 2 по модулю два поступает код Ьы с выхода второго регистра 4, на первый вход четвертого сумматора 2 по модулю два - код ak-1 с инверсного выхода первого регистра

4, на первый вход шестого сумматора 2 по модулю два - код см с выхода третьего регистра 4. Третий, четвертый, пятый и шестой сумматоры 2 по модулю два осуществляют поразрядное суммирование кодов,

поступивших на их первые входы с соответствующими переменными, поступившими на их вторые входы.

Результаты суммирования с выходов третьего, четвертого, пятого и шестого сумматоров 2 по модулю два поступают на первые входы первого, третьего и четвертого, пятого сдвигателей 5 соответственно.

На первый вход второго сдвигателя 5 поступает код аы с инверсного выхода первого регистра 4. На вторые входы первого и третьего сдвигателей 5 с седьмого выхода блока 1 управления поступает т-разрядный унитарный двоич ный код , содержащий единицу в jk-м разряде и нули в остальных

разрядах. На вторые входы второго, четвертого и пятого сдвигателей 5 с восьмого выхода блока 1 управления поступает m-разрядный унитарный код №. содержащий единицу в (2.jk+2)-M разряде и нули в

остальных разрядах. Сдвигатели 5 осуществляют сдвиг в сторону младших разрядов кодов, поступающих на их первые входы, на число разрядов, соответствующее номеру единичного разряда в унитарных кодах, поступающих на их вторые входы.

Трехвходовые сумматоры 6 и двухвхо довый сумматор 7 осуществляют сложение кодов, поступивших на их входы.

Информация с выходов первого и второго трехвходовых сумматоров 6 и двухвхо- довог о сумматора 7 поступает на первые информационные входы первого, второго и третьего мультиплексоров 3 соответственно. При нулевом значении признака Конец операции, поступающего на управляющие входы мультиплексоров 3, информация с их первых информационных входов проходит на информационные входы соответствующих регистров 4.

С приходом очередного ТИ на втором, третьем выходах блока 1 управления формируются единичные значения сигналов Занесение 1 и Занесение 2 соответственно, которые, поступая на входы разрешения записи регистров 4, осуществляют занесение в первый, второй и третий регистры 4 вычисленных значений ak, bk и ci соответственно.

Итерационный процесс первого этапа продолжается до тех пор, пока в результате выполнения очередной q-й итерации значе- ния всех m старших числовых разрядов кода aq, поступающего с выхода первого регистра 4 на четвертый вход блока i управления не станут равными нулю, после чего устройство переходит к второму этапу вычислений.

На втором этапе вычислений при выполнении k-й итерации Vke{q+ 1,g+2tj налич

нулевого кода на седьмом выходе блока 1 управления обеспечивает формирование нулевого кода на вторых входах трехвходо- вых сумматоров 6. Сигналы Инверсия 1, Инверсия 2 и Инверсия 3 формируются на четвертом, пятом и шестом выходах согласно таблице. В процессе вычисления сформированные значения переменных bk и Ck. определенные согласно соотношениям (13) и (14), поступают на информационные входы второго и третьего регистров 4 и заносятся в указанные регистры сигналом Занесение 2. Сигнал Занесение вто- ром этапе сохраняет нулевое значение, вследствие чего на первом регистре 4 сохраняется значение , полученное на первом этапе вычислений.

Итерационный процесс второго этапа продолжается до тех пор, пока в результате выполнения очередной t-й итерации все m старших разрядов дробной части кода , поступающего с выхода третьего регистра 4 на третий вход блока 1 управления, не ста- нут равными единице. В этом случае на первом выходе блока 1 управления будет сформировано единичное значение признака Конец операции, которое поступает на выход 12 устройства,

Значение bt поступает с выхода второго регистра 4 на выход 13 устройства в качестве результата операции U.

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

В исходном состоянии на входы 22 и 24 поступают коды и , полученные в результате выполнения предыдущей операции. На выходе 12 блока формируется единичное значение признака Конец операции. На вход 11 блока поступают ТИ.

Сигнал Пуск, поступая на вход 10 блока, проходит на второй вход узла 14, в результате чего на втором и третьем выходах узла 14 формируются единичные значение сигналов Занесение 1 и Занесение 2, поступающие на выходы 25 и 26 блока соответственно. При выполнении k-й итерации ke{1,2,...,q} на входы 22-24 блока поступают (т+1)-разрядные коды операндов сы , ak-1 и bk-1, содержащие знаковый и т старших числовых разрядов кодов сы, аы и bk-1 соответственно. Первый сумматор 18 по модулю два осуществляет поразрядное суммирование m числовых разрядов поступающего на его второй вход кода Ck-1 с переменной, поступающей на его первый вход и представляющей собой инверсию стара его (нулевого) разряда кода сы. На первый вход второго сумматора 18 по модулю два поступает прямое значение старшего (нулевого) разряда кода аы, и сумматор 18.2 по модулю два осуществляет аналогичную операцию с кодом ak-i . Старшие (нулевые) разряды кодов аы и сы поступают, кроме того, на шестой и седьмой входы узле 14 соответственно. На первый, третий и пятый входы узла 14 соответственно поступает информация с входа 24 блока, а также с выходов первого и второго сумматоров 18 по модулю два. Узел 14 на своих первом, втором, третьем, пятом, шестом и седьмом выходах формирует признак Конец операции, сигналы Занесение 1, Занесение 2, Инверсия 1, Инверсия 2 и Инверсия 3, которые поступают на первый 12, второй 25, третий 26, четвертый 27, пятый 28 и шестой 29 выходы блока соответственно.

На четвертом выходе узла 14 формируется признак Номер этапа На первом этапе вычислений единичное значение признака Номер этапа разрешает прохождение информации через вентильную схему 19, а также с второго информационного входа мультиплексора 16 на его выход.

Первый и второй узлы 15 формируют на своих выходах унитарные коды tek и hk, содержащие единицу в разрядах J2k и J2k соответственно и нули в остальных разрядах согласно выражениям (10) и (9). Сдвигатель

17 осуществляет сдвиг в сторону старших разрядов кода hk, поступающего на его первый вход, на величину jik, значение которой определяется кодом lik, формируя на своем выходе унитарный код Ik, имеющий единич- ное значение в разряде jk согласно (11). С выхода сдвигателя 17 информация поступает на первый вход узла 21, на второй вход которого поступает значение признака Номер этапа. С выходов узла 21 на выход 30 блока поступает унитарный v-разрядный код Г k, содержащий единицу в разряде с номером ji и нули в остальных разрядах, а на выходах 31 блока - унитарный v-разрядный код l 2V. содержащий единицу в (2-jk+2)- м разряде и нули в остальных разрядах.

На втором этапе вычислений нулевое значение признака Номер этапа блокирует прохождение информации через вентильную схему 19. а также обеспечивает прохождение информации с первого информационного входа мультиплексора 16 на вход первого узла 15, который формирует на первом входе сдвигателя 17 унитарный код согласно выражению (16). На второй вход сдвигателя 17 поступает нулевой код, в результате чего код с первого входа сдвигателя 17 поступает на его выход и на первый вход узла 21 без преобразований

На первом выходе узла 21 на втором этапе вычислений формируется код P1V имеющий нулевое значение во всех разрядах. На втором выходе узла 21 формируется код г , имеющий единичное значение в jk-м разряде, определенном согласно (16), и нулевые значения в остальных разрядах

Узел формирования управляющих сигналов работает следующим образом. В исходном состоянии на выходе 11 узла формируется единичное значение признака Конец операции.

Сигнал Пуск, поступающий с входа 10 узла на первый вход второго и третьего элементов ИЛИ 33, формирует сигналы Занесение 1 и Занесение 2 на выходах второго и третьего элементов ИЛИ 33, являющихся одновременно выходами 25 и 26 узла соответственно. В случае одновременного равенства нулю кодов, поступающих на входы 34 и 36 узла, на выходе второго элемента И 32 формируется единичное значение сигнала, которое поступает на первый вход первого элемента ИЛИ 33 и обеспечивает сохранение единичного значение признака Конец операции на выходе 12 узла. Если коды поступающие на входы 34 и 36 узла, отличны от нуля, то на выходах второго и четвертого элементов И 32 формируются сигналы нулевого уровня и на выходе 12 узла признак Конец операции принимает

нулевое значение Одновременно нулевой сигнал на выходе первого элемента ИЛИ 33, поступая на инверсный вход пятого элемента И 32, разрешает прохождение ТИ с входа 11 узла через элементы И 32 5 и ИЛИ 33.3 на выход 26 узла в качестве сигнала Занесение 2 и далее через элементы И 32.9 и ИЛИ 33.2 на выход узла в качестве сигнала Занесение 1.

Код, поступающий на вход четвертого элемента ИЛИ 33 с входа 36 узла, формирует на выходе 39 узла признак Номер этапа Единичное значение признака Номер этапа, поступая на первый вход девятого элемента И 32, обеспечивает единичное значение сигнала Занесение 1 на выходе 25 узла Поступающие на входы 37 и 38 узла сигналы совместно с сигналом с выхода четвертого элемента ИЛИ 33 формируют на выходах 27 - 29 узла сигналы Инверсия 1, Инверсия 2 и Инверсия 3 соответственно согласно таблице 1. Формирование сигналов узлом продолжается до тех пор, пока на вход 36 узла не поступит нулевой код, означающий конец первого этапа вычислений, и на вход 35 одновременно с этим также поступает нулевой код. В этом случае на выходе четвертого элемента И 32 будет сформировано единичное значение сигнала, которое через первый элемент ИЛИ 33 поступает на выход 12 узла в качестве признака Конец операции и одновременно запрещает прохождение ТИ с входа 12 узла через пятый элемент И 32 на выходы 25 и 26 узла.

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

пятый и шестой сумматоры по модулю два, с первого по пятый сдвигатели, второй и третий сумматоры, причем входы разрядов первого аргумента устройства соединены с входами соответствующих разрядов первого слагаемого первого сумматора по модулю два,-вход второго слагаемого и выход которого соединены соответственно с входом знакового разряда первого аргумента уст- ройства и с вторым информационным входом первого мультиплексора, управляющий вход которого соединен с управляющими входами второго и третьего мультиплексоров и с первым выходом блока управления, третий выход которого соединен с входом разрешения записи третьего разряда, информационный вход которого соединен с выходом третьего мультиплексора, первый информационный вход которого соединен с выходом третьего сумматора, вход первого слагаемого которого соединен с выходом третьего регистра, с входом первого слагаемого шестого сумматора по модулю два и с первым входом условия блока управления, второй оход условия которого соединен с прямым выходом первого регистра и с входом первого слагаемого первого сумматора, вход второго слагаемого которого соединен с выходом первого сдвигателя, информационный вход которого соединен с выходом третьего сумматора по модулю два, входы разрядов второго аргумента устройства соединены с входами соответствующих разрядов первого слагаемого второго сумматора по модулю два, вход второго слагаемого которого соединен с входом знакового разряда второго аргумента устройства, выходы второго сумматора и второго сумматора по модулю два соединены соответственно с первым и вторым информационными входами второго мультиплексора, выход которого соединен с информационным входом второго регистра, выход которого соединен с входами первого слагаемого второго сумматора и пятого сумматора по модулю два, с третьим входом условия блока управления и является выходом результата устройства, вход логический единицы которого соединен с вторым информационным входом третьего Мультиплексора, инверсный выход первого регистра - с информационным входом второго сдвигателя и с входом первого слагаемого четвертого сумматора по модулю два. вход второго слагаемого и выход которого соединены соответственно с четвертым выходом блока управления и с информационным входом третьего сдвигателя, выход которого соединен с входом второго слагаемого второго сумматора, вход третьего слагаемого которого соединен с выходом четвертого сдвигателя, им формационный вход которого соединен с выходом пятого сумматора по модулю два, вход второго слагаемого которого соединен

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

5 управления - с входами задания величины, сдвига второго, четвертого и пятого сдвигателей, выход второго сдвигателя - с входом третьего слагаемого первого сумматора 2, Устройство по п. 1,отличающее0 с я тем, что блок управления содержит первый и второй узлы выбора старшей единицы, мультиплексор, сдвигатель, первый и второй сумматоры по модулю два, группу элементов И, элемент НЕ, коммутатор и

5 узел формирования управляющих сигналов, содержащий с первого по третий элементы И, с первого по шестой элементы запрета, с первого по пятый элементы ИЛИ. причем вход запуска блока управления соединен с

0 первыми входами второго и третьего элементов ИЛИ узла формирования управляющих сигналов, тактовый вход блока управления - с информационным входом третьего элемента запрета узла формирова5 ния управляющих сигналов, знаковый разряд первого входа условия блока управления - с входом элемента НЕ и с информационными входами пятого и шестого элементов запрета узла формирования

0 управления сигналов, выход элемента НЕ соединен с входом первого слагаемого первого сумматора по модулю два, входы разрядов второго слагаемого которого соединены с разрядами первого входа усло5 вия блока управления, знаковый разряд второго входа условия которого соединен с входом первого слагаемого сумматора по модулю два, с управляющим входом четвертого элемзнта запрета узла формирования

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

5 модулю два, выход четвертого элемента ИЛИ узла формирования управляющих сигналов соединен с управляющими входами первого, второго, пятого и шестого элементов запрета, с первым входом третьего элемента И, с информационным входом

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

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

Фиг.2

Фиг.З