Устройство для извлечения квадратного корня

 

Изобретение относится к цифровой вычислительной технике и может быть использовано в универсальных и специализированных вычислительных системах для аппаратной реализации операции извлечения квадратного корня из чисел, представленных в двоичной системе счисления в форме с фиксированной и плавающей запятой. Цель изобретения - повьппение быстродействия устройства при одновременном повышении точности вычислений и расширении области применения за счет возможности обработки чисел, представленных в форме с плавающей запятой. Поставленная цель достигается тем, что в устройство, содержащее три регистра 1-3, два сумматора 4, 5, три блока сдвига 8, 9, 10, блок управления 11, введены два мультиплексора 6, 7 и блок формирования результата 12. 2 з.п. ф-лы, 5 ил. § сл

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (l9) (11) Ь)) 4 G 06 F 7 552 г Т. . т.cqy

И., „13

ОЛИСАНИЕ ИЗОБРЕТЕНИЯ

6N63)I ..

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITHA

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4119095/24-24 (22) 16.09.86 (46) 15.03.88. Бюл. Ф 10 (71) Московский лесотехнический институт (72) А.Д.Марковский, Г.Г.Меликов, О.И.Пустовойтов, В.Г.Евстигнеев и А.Н.Кошарновский (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1084788, кл. G 06 F 7/552, 1984.

Авторское свидетельство СССР

У 732863, кл. С 06 F 7/552, 1980. (54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ (57) Изобретение относится к цифровой вычислительной технике и может бьггь использовано в универсальных и специализированных вычислительных системах для аппаратной реализации операции извлечения квадратного корня из чисел, представленных в двоичной системе счисления в форме с фиксированной и плавающей запятой.

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

4, 5, три блока сдвига 8, 9, 10, блок управления 11, введены два C мультиплексора 6, 7 и блок формироф вания результата 12. 2 э.п. ф-лы, 5 ил °

С:

1381497

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

Цель изобретения — повышение быстродействия при одновременном повышении точности и расширении области применения за счет возможности обработки чисел, представленных в форме с плавающей запятой.

На фиг.. 1 представлена структурная схема устройства для извлечения квадратного корня; на фиг. 2 - функционалы|ая схема мультиплексора; на 20 фиг. 3 — схема блока сдвига; на фиг. 4 — схема блока управлениями на на фиг. 5 — схема блока формирования результата.

Устройство содержит регистры 1, 2 25 и 3 (см. фиг. 1), первый 4 и второй 5 сумматоры, мультиплексоры 6 и 7, блоки 8, 9 и 10 сдвига, блок 11 управления, блок 12 формирования результата, вход 13 задания порядка, 30 вход 14 задания мантиссы устройства, тактовый вход 15, вход 16 запуска устройства „ выход 17 порядка, выход

18 мантиссы, выход 19 конца операции устройства.

Мультиплексор (см. фиг. 2) содержит m+2 группы элементов И20, m+1 элементов ИЛИ 21, элемент НЕ 22, информационные входы 23 и 24, управляющие входы 25, 26 и выход 27.

Блок сдвига (см. фиг. 3) содержит гп+1-1 групп элементов И 28, из которых i-я группа (i=1,2, ..., m+1-1 содержит гп+1-1 элементов И, тп+1-2 элементов ИЛИ 29 и имеет первый 30 и второй 31 входы и выход 32.

Блок управления (см. фиг. 4) содержит в+2 элементов НЕ 33, два элемента ИЛИ 34, в+2 элементов И 35, первый 36, второй 37 и третий 38 входы, выходы 39-44.

Блок формирования результата (см. фиг. 5) содержит r+m элементов И 45, r+m сумматоров 46 по модулю два, два элемента ИЛИ 47, первый 48 и второй

49 входы, первый 50 и второй 51 вы55 ходы.

В основе работы устройства лежит следующий способ вычисления значений

M при а„= О, М о

М/2 при а„ = 1

Если аргумент Х представить в виде р г, Х= 2 ° М= 2 М = 2 Г1|(1+2 )

К|

| (2) где ри аг О, (3) Р+1 при а„=1;

- j

У = Х =- 2

Q оо | 1< -1 М =2 П(1+2 ) о (4) (5) где Q = Pî/2.

Из выражений (2) и (4) следует (6) (1+2 ) = 1, М П

0 к!

У вЂ” 2 M . П

0 Ic, (7) (1+2 ) Введем следующие обозначения: (8) Z = и — Z П (1+2 ) g i=1,2, ...,(9)

0 Kl (10) Mî П 1+2 ) 1| .=1,2, K=l

Выражения (6) и (7) с учетом (9) и (10) могут быть представлены в виде: функции У = +X. Значение аргумента представляется в виде Х = 2 M. ПоР, рядов Р представляется (г+1) -разрядным двоичным дополнительным кодом а,а,а, ..., а„, где а — знаковый, а,а,, ..., а„ вЂ” числовые двоичные разряды. Мантисса M представляется

m-раэрядым двоичным кодом b,Ü, b где b, Ь, ..., Ъ|„ — числовые двоичные разряды (мантисса аргумента всегда неотрицательна).

Значение результата вычисляется с использованием разложения приведенной мантиссы М аргумента Х на множители вида (1+2 " ) 1381497

lim Z; = 1

Y= 2 lim И,.

Q (12)

Из выражений (9) и (10) можно получить рекуррентные сотношения для вычисления очередных значений Z.; и М,:

-Ji>< -21, Z=Z;,+Z;, ° 2+Z;,2 (1 3) -J

М;=И;,+И;, ° 2 (14) 15

При вычислении функции У = - Х в соответствии с выражениями (3) и (5) определяется порядок Q результата.

Мантисса результата вычисляется с использованием рекуррентных формул (13) и (14). Начальное значение М, определяется в соответствии с выражением (1), 2о — в соответствии с выражением (8).

Очередное значение величины j определяется по формуле

25 (15)

j", = N(Z;,)+1, где N(Z; ) — номер старшего нулевого разряда в двоичном представлении числа Z, Признаком окончания операции служит условие

Zь011...1=12 являющееся конечным приближением предельного соотношения (11). Величина

М при этом в соответствии с (12) ис- 45 пользуется в качестве значения мантиссы результата.

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

В исходном состоянии все разряды с первого по (m+ 1) -й регистра 1, 50 используемого для хранения величины

Z;, имеют одинаковое (либо нулевое, либо единичное) значение. Вследствие этого значение сигнала конца операции на шестом выходе блока управления

55 равно единице, а значение сигнала на первом и втором выходах блока управления равно нулю. На вход 15 устрой" ства, являющийся одновременно первым входом блока управления, непрерывно поступают тактовые импульсы.

При извлечении квадратного корня иэ числа, представленного в форме с плавающей запятой, значения порядка и мантиссы аргумента поступают соответственно на входы 13 и 14 устройства. Код порядка аргумента с входа 13 поступает на информационный вход регистра 3, код мантиссы аргумента на первые информационные входы мультиплексоров 6 и 7. Кроме того, младший разряд кода порядка а„ поступает на первые управляющие входы мультиплексоров 6 и 7.

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

Сформированное на выходе мультиплексоров 6 и 7 приведенное значение мантиссы М поступает на информационные входы регистров 1 и 2. Для выполнения вычислений синхронно с одним из тактовых импульсов на вход 16 устройства подается сигнал "Пуск", который поступает на управляющий вход регистра 3, осуществляя занесение в регистр 3 значения порядка аргумента Р, а также на первый вход блока 11 управления.

По сигналу "Пуск" на втором выходе блока 11 управления формируется импульс, который поступает на управляющие входы регистров 1 и 2 и осуществляет занесение в регистр 1 величины

Z = М и в регистр 2 — величины Мо. о

Значение с выхода регистра 1 поступает на третий вход блока 11 управления, первые входы блоков 8 и 9 сдвига и первый вход сумматора 4.

Значение М с выхода регистра 2 посо тупает на первый вход блока сдвига, первый вход сумматора 5 и второй вход блока 12 формирования результата. На первый вход блока 12 формирования результата с выхода регистра 1 поступает значение порядка P.

Поступление кода Z на третий вход блока 11 управления приводит к к появлению на шестом выходе блока 11

1381497 управления нулевого уровня сигнала, а на первом выходе — единичного уровня. Кроме того, второй ныход блока 11 управления подключается к его второму входу, обеспечивая прохождение очередных тактовых импульсов на управляющие входы регистров 1 и 2.

По коду Z, на третьем, четвертом и пятом выходах блока 11 управления формируются (m+1-1) -разрядные коды, содержащие единицу в (j,)-м (j, — 1) -м

H (2 J;)-м разрядах и нули в остальных разрядах, которые поступают на вторые входы блоков 10, 8 и 9 сдвига соотнетственно. Значение J опреде-! ляется в соответствии с выражением (15). Блоки 8 и 9 сдвига осуществляют умножение поступающего на их !

+ первые входы кода Е на 2 и

2 1 соответственно путем сдвига кода Z íà j -1 и 2 j, разрядов.

Блок 10 сдвига осуществляет умножение кода N на 2 путем сднига кода N, íà J, разрядон 25

Сумматоры 4 и 5 производят вычисление значений 2, и М, в соответствии с выражениями (13) и (14). С выходов сумматоров 4 и 5 коды величин ZI и М, поступают на вторые информацион- 3 ные входы мультиплексоров 6 и 7 соответственно. Наличие единичного сигнала на вторых управляющих входах мультиплексоров 6 и 7 обеспечивает прохождение информации с вторых информационных входов на выходы мультиплексоров, в результате чего коды

Z u M поступают на информационные входы соответственно регистров 1 и 2. С приходом очередного тактового

40 импульса значения Z è М, заносятся в регистры 1 и 2, На этом выполнение первой итерации завершается.

В процессе выполнения второй итерации по значениям Е и М, н устройстве формируются значения Z и Г1, 45 которые заносятся в регистры 1 и 2 очередным тактовым импульсо!1. Итерационный процесс продолжается до тех пор, пока нсе ш+1 старших разрядов числа Z, не станут равными единице.

При этом блок 11 управления формирует на шестом выходе сигнал конца операции, который поступает на выход 19 устройстна и запрещает прохождение тактовых испульсов со своего второго 55 входа на второй выход. На первом вы-. ходе блока управления устанавливается нулевой уронень выходного сигнала.

Г!о окончании процесса вычислений на первом выходе блока 12 формирования результата формируется значение порядка результата Q в соответствии с выражениями (3) и (5), а на втором выходе — округленное до m разрядов значение мантиссы результата, Сформированные блоком 12 формирования результата порядок и мантисса результата поступают на выходы 17 и 18 устройства.

Если значения всех m+1 разрядов

Z одновременно равны единице или одновременно равны нулю, то вычисления по рекуррентным соотношениям (13) и (14) не проводятся и в качестве результата используются значения порядка и мантиссы, сформированные блоком 12 формирования результата по поступившим на его входы значениям

P иГ1,.

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

25 мультиплексора равно нулю, то поступающий на вход 23 код передается на выход 27 беэ преобразования. При единичном значении сигнала на нходе 25 и нулевом значении на входе 26 код, поступающий на вход 23, передается на выход 27 со сдвигом на один разряд в сторону младших раэрядон. При единичном значении сигнала на входе

26 мультиплексора независимо от значения сигнала на входе 25 на выход

27 передается значение кода, поступающего на второй информационный вход 24.

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

1381497

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

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

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

34 проходит на второй выход 39 блока.

Сигнал, поступивший на второй вход

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

40 блока, которому соответствует входной код на (m+1) -разрядном третьем входе 38 блока, содержащий хотя бы один нуль и хотя бы одну единицу.

В этом случае шестой выход 41 блока имеет нулевое значение. Если все разряды третьего входа 38 блока одновременно равны нулю или все разряды третьего выхода 38 одновременно равны единице, то первый выход 40 блока имеет нулевое, а шестой выход 41 — 2p единичное значения. На третьем 42, четвертом 43, пятом 44 выходах блока формируются коды, имеющие единичное значение в (К+1)-м, R-м и (2R+2) ì разрядах Соответственно и нули в 25 остальных разрядах, где R — номер старшего, равного нулю, разряда кода, поступившего на третий вход 38 устройства.

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

35 разряда с последующим подсуммированием значения младшего разряда, сдвигаемого на разрядную сетку, а также сигнала переноса из старшего разряда Возникающего при формирова 40 нии кода, поступающего на второй вход 49 блока, после чего поступает на первый выход 50 блока. Значение младшего разряда кода, поступившего на второй вход 49 блока, суммируется 45 с остальной частью кода, поступившего на второй вход 49, и сформированный новый код поступает на второй выход 51 блока. блоков сдвига подключены соответственно к второму и третьему входам первого сумматора, выход третьего блока сдвига соединен с вторым входом второго сумматора, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия при одновременном повышении точности и расширении области применения за счет обеспечения воэможности обработки чисел, представленных в форме с плавающей запятой, в него введены два мультиплексора и блок формирования результата, причем вход задания мантиссы устройства подключен к первым информационным входам первого и второго мультиплексоров, вторые информационные входы которых соединены с выходами первого и второго сумматоров соответственно, первые и вторые управляющие входы мультиплексоров подключены к входу младшего разряда входа задания порядка устройства и первому выходу блока управления соответственно, второй выход которого соединен с входами разрешения записи первого и второго регистров, информационные входы которых подключены к выходам одноименных мультиплексоров, информационный вход третьего регистра соединен с входом задания порядка устройства, тактовый вход которого подключен к первому входу блока управления и входу разрешения записи третьего регистра, выход которого соединен с первым входом блока формирования результата, первый и второй выходы которого соединены соответственно с выходами порядка и мантиссы результата устройства, а второй вход— с выходом второго регистра и информационным входом третьего блока сдвига, вход сдвига которого и одноименные входы первого и второго блоков сдвига подключены к третьему, четвертому и пятому выходам блока управления, второй вход которого соединен с входом запуска устройства, а третийс информационными входами первого и второго блоков сдвига, шестой выход блока управления является выходом конца операции устройства.

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит m+2 элементов НЕ, два элемента ИЛИ и ш+3 элементов И, причем вход i-го элемента HE (i=1,2, ...,m+1) и i-й вход первого элемен1381497

10 та И подключены к i-му разряду третьего входа блока, выход i-го- элемента HF. соединен с i-входом второго элемента И, выходы первого и второго

5 элементов И подключены к входам первого элемента ИЛИ, выход которого подключен к шестому выходу блока и входу (m+2) -го элемента НЕ, выход которого подключен к первому выходу блока и первому входу третьего элемента И, второй вход которого подключен к второму входу блока, а выход— к первому входу второго элемента ИЛИ, ВтОрОй ВХОД KOToporo сОединен с пер вым входом блока, а выход — с вторым выходом блока, выход j-го элемента НЕ (j=2,3, ..., m+1) соединен с первым входом (j+2) -го элемента И, остальные входы которого соединены с разрядами третьего входа блока, номера которых меньше j, k-й разряд третьего выхода блока (k=1 m+3, m+4

m+1-1) и и-й разряд четвертого выхода блока (п=щ+2, m+3, ..., m+1-1) под- 25 ключены к нулевой шине, 6 -й разряд третьего выхода блока и Ь -й разряд четвертого выхода блока (Ь =3,4, а+2) подключены к выходу (6+1)-го элемента И, второй разряд третьего, первый разряд четвертого и четвертый разряд пятого выходов блока соединены с выходом первого элемента НЕ, первый, второй, третий и q-е разряды пятого выхода блока (q=5>7, m+1-1) подключены к нулевой шине, (q-1) -й разряд пятого выхода блока под ключен к выходу (q-3) /2 элемента И.

3. Устройство по п. 1, о т л ич а ю ш е е с я тем, что блок формирования результата содержит г+ш элементов. И, r+m сумматоров по модулю два и два элемента ИЛИ, причем первый вход i-ro элемента И (i=1,2, r) подключен к выходу первого элемента И, остальные входы — к разрядам с (i-1) -го по (r-1) -й первого входа блока, а выход — к первому входу

i-го сумматора по модулю два, выход которого соединен с (i-1) -м разрядом первого выхода блока„ второй вход первого сумматора по модулю два подключен к нулевому разряду первого входа блока, второй вход j -го сумматора по модулю два (1=2,3.

r+1) подключен к (j 2) -му разряду первого входа блока, первый вход (r+1) -ro сумматора по модулю два подключен к выходу первого элемента

ИЛИ, а выход — к r-му разряду первого выхода блока, выходы R-го элемента И (R=r+1, r+2, ..., г+щ) подключены к разрядам с (R-r) -ro по (m+1) -й второго входа блока, выход

n-ro элемента И (n=r+3, r+4, г+щ) соединен с первым входом (п-1)го сумматора по модулю два, второй вход которого подключен к Pn(r-1)) -му разряду второго входа блока, первый и второй входы (r+m) -ro сумматора по модулю два подключены соответственно к m-му и (m+1)-му разрядам второго входа блока, первый и второй входы первого элемента ИЛИ подключены соответственно к r-му разряду первого входа блока и выходу (г+1) -ro элемента И, первый и второй входы второго элемента ИЛИ подключены соответственно к первому разряду второго входа блока и выходу (r+2) -ro элемента И, а выход — к первому разряду второго выхода блока, выход s-ro сумматора по модулю два (s=r+2

r+3. ..., г+щ) подключен к (s-r) -му

Разряду второго выхода блока.

1381497

1381497 ,0

J0fm ,УО(л

Л/(ет l

31. (mi

Фие. Р! 381497

1381497

Составитель Н. Шелобанова

Редактор И. Рыбченко Техред M.Äèäûê Корректор. С. Шекмар

1184/44 Тирам 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ

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