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

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

Целью изобретения является повышение быстродействия за счет организации итерационного процесса над аргументами в избыточной системе счисления.

На чертеже представлена функциональная схема устройства.

Устройство содержит первый 1 и второй 2 регистры аргументов, первый 3 и второй 4 регистры результата, сумматор 5 перевода кодов, сумматор 6 аргументов, сумматор 7 результата, первый - седьмой сдвигатели 8-14, шифратор 15 итерационной переменной, дешифратор 16, счетчик 17, тактовый вход 18.

Устройство функционирует следующим образом.

В предлагаемом устройстве процесс вычисления квадратного корня основывается на следующих равенствах. Аргумент хе fl,2 представляется в виде

х 1/Д 1.Ер-2-- ,

где с 6 Ojj; Ерб -1,0,l ;

Р 1, k;

k - разрядность х. Тогда значение функции представится

(1)

1/П l -f Ер- ., (2)

Разделив выражение (2) на (1) и умножив обе части на х, получим

,1X г-fD l-r T

m г

1р х-П fl + Ер- f -

(3)

О О О

о 1

254477

Из (1) получаем также равенство

5

0

5

0

Г

п

Р « 1 L

1 + Е

Р

-(Р-О g .

X

Р

1 .(4)

На основании (3) и (4) процесс вычисления корня квадратного можно представить следующими рекуррентными выражениями:

-1Р-с) -, .5(р-с,1)

-р., 2

х,-Ер--2

X

,

Р

(5) (6)

,„ „-(p-f -c)

yp,,V;Ep-2 .у,

где Р .1,k; Ерб -1 ,0, l ; се 0,l Начальные условия: х х; у х. Результат: ур Хр 2. - Переменные Е и с в (5) и (6) на каждой р-й итерации определяются по значениям старших разрядов Хр таким образом, чтобы первый после запятой разряд Хр в результате выполнения (5) принимал нулевое значение. При этом при заданных начальных условиях переменная х., будет стремиться к значению 2 , а ур - к значению . В табл.1 приведена зависимость значений Е, и с от значений старших разрядов переменной х„.

В табл.1 приняты обозначения: Е , Ер - двоичные переменные для управления направлением тока;

ЕР ЕР-Е;; Е;, Ер ,i5

tfe{0,l3 - переменная номера итерации, при Р при ,k

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

Таблица 1

о 1 о

1 о 1

о о о о о о

о о о о о о

В предлагаемом устройстве на каж- 55цифрами -1,0,1, любое k - раздом шаге итераций переменные х ирядное число я , 2 в этой

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

системе счислений с основанием 2 ив виде

Продолжение табл.1

X i: (к - Xp) 2 , (7)

где Хрб (OH положительная цифра

р-го разряда;

,l3 - отрицательная цифра р-го разряда.

В предлагаемом устройстве первый 1 и второй 2 регистры аргумента, первый 3 и второй 4 регистры результата предназначены для хранения соответственно положительных Хр и ур и отрицательных х и у р разрядных цифр аргумента VP и результата ур каждой итерации. Каждый регистр содержит k + 1 двоичных триггеров (k триггеров для хранения дробной части переменной р 1,k и один триггер для целой части переменной).

В табл.2 приведено соответствие между цифрами Yр, Хр и Yp, Хр и значение разряда знакоразрядной переменной YP ,Хр .

Таблица 2

0

1

0

1

0

1 -1

0

Сумматор 5 перевода кодов предназначен для преобразования результата вычислений из избыточной системы счисления в двоичную, которое представляет собой сложение с распространением переноса положительной и отрицательной частей переменной у, .

Знакоразрядные сумматоры 6 и 7 предназначены для выполнения алгебраического сложения в соответствии с равенствами (5) и (6) над числами в избыточной системе сложения счисления .

Сдвигатели 9 и 13 предназначены для параллельного сдвига содержимого регистров 1 и 2 на (р-с) разрядов

вправо, сдвигатели 8 и 14 - для сдвига содержимого регистров 3 и 4 на (p-c-t-1) разрядов вправо, сдвигатели 10 и 12 - для параллельного сдвига содержимого регистров 1 и 2 на 2 (р- ) разрядов вправо. Сдвигатель 14 предназначен для сдвига на один разряд (при с 1) влево унитарного параллельного кода номера итерации р

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

сдвигателями. Шифратор 15 итерационной переменной предназначен для реализации логической функции, представленной табл.1, т.е. для определения по старшим разрядам Хо и

рации р управляющих

Ер на каждом итерационном шаге.Шифра- тор 15 реализует следующие логические функции:

c {fx ;x ;x x x v xtx ;x;x x vcfx xTx x;

(8)

fep x x x vxJx7x;vx|x XjX:,v X ;

(9)

ip п номеру ите- сигналов с. Ер,

X, X,

vx,-X5x;x-vx7XjX,,

,v

(10)

Шифратор итерационных переменных 15 выполнен на логических элементах И и ИЛИ. Значения переменных х , у , Х, А2 , X, , К, поступают на вход шифратора 15 с регистров 1,2, а переменная (f на второй вход с дешифратора 16.

Счетчик 17 предназначен для счета номера р итерации, т.е. количества тактовых импульсов посупивших по тактовому входу 18 устройства. Дешифра - тор 16 преобразует позиционньй код р в унитарный.

Перед началом вычисления в регистры 1 и 3 заносятся в двоичной, неизбыточной системе счисления начальные условия X, X, у, X. Далее производится выполнение k итераций в соот- ветствяя с уравнения (5) и (6).

На каждой итерации в устройстве вьшолняются следующие операции. В счетчике 17 тактов производится прибавление единицы по тактовому входу 18, в дешифраторе код номера итерации р дешифруется и поступает на входы четвертого сдвигателя 11, одно7

временно в шифраторе итерационной переменной 15 по старшим разрядам регистров 1 и 2 формируются значения переменных с, Ej, Ер, которые поступают затем на вход признака величины сдвига четвертого сдвигателя 11 и входы кода операции сумматоров 6,7, на выходе четвертого сдвигател 11 формируется значение величины сдвига р-с, которое поступает на входы признака величины сдвига сдвигателей 8,9 JО,12,13,14, на выходах которых формируются соответствующие части системы уравнения (5) и (6).

Затем в сумматорах 6 и 7 про- .изводится алгебраическое сложение в соответствии с равенствами (5) и (6) . В результате на выходах сумматоров 6 и 7 формируются переменные 1/2 Jt Ур41 избыточной двоичной системе счисления, которые записываются соответственно в регистрах 1,2 со сдвигом на один разряд влево и в гистрах 3,4. При этом значение переменных X, , Уо заменяются на их новые

значения х

pti

Ур.

вычисленные в

1

данной итерации.

После выполнения k

итерации в ре-|Гистрах 3,4 хранится результат вычисле-30 зультата, выход четвертого сдвигате- ний у i, представленный в избыточля соединен с входами признака вели- чины сдвига первого, второго, третьего, пятого, шестого и седьмого сдвигателей, информационные входы пятого и шестого сдвигателей соединены с выходом второго регистра аргументов, выходы третьего, пятого и шестого сдвигателей соединены соответственно с третьим, четвертым и пятым информационными входами сум 1атора аргументов, шестой информационный вход которого соединен с выходом второго регистра аргументов, второй,третий и четвертый информационные входы сум- матора результата соединены соответственно с выходами второго регистра результата, первого и седьмого сдвигателей, выходы старших разрядов первого и второго регистров аргументов соединены с входами значения разрядов шифратора итерационной переменной, второй информационный вход сумматора перевода кодов и информационный вход седьмого сдвигателя соединены с. выходом второгоiрегистра результата.

ной системе счисления. Преобразование результата в обычную двоичную систему производится на сумматоре 5 сложением отрицательной и положитель- ной частей числа у с распростране нием переносов.

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

40

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

выход первого регистра результата

j tO

15

20254477 8

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

30 зультата, выход четвертого сдвигате-

зультата, выход четвертого сдвигате-

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

1

19

Редактор Н.Слободяник

Составитель С.Куликоэ

Техред Л.Сердюкова Корректор В.Бутяга

Заказ 4721/52Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4

Изобретение может быть использовано в быстродействующих ЦВМ и при построении специализированных автономных процессоров высокой производительности. Устройство позволяет повысить быстродействие вычисления квадратного корня за счет выполнения над аргументами, представленными в . избыточной двоичной системе счисления. Применение знакоразрядных сумматоров дпя выполнения операции над аргументами обеспечивает повышение быстродействия. Устройство содержит первый и второй регистры аргументов, первый и второй регистры результата, сумматор перевода кодов, сумматор аргументов, сумматор результата, первый, второй, третий, четвертый и пятый, шестой, седьмой сдвигатели, шифратор итерационной переменной, дешифратор, счетчик, тактовый вход. 1 ил. 2 табл. (Л ел -t