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

00 00

j;: со

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

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

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

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

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

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

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

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

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

е13814972

функции у , Значение аргумента представляется в виде X 2 -М. По- рядов Р представляется (г+1)-разрядным двоичным дополнительным кодом

., а, где а - знаковый, а,а, ..., а - числовые двоичные разряды. Мантисса М представляется т-разрядым двоичным кодом b,b,j,

Ь, где b,, b, ..., b - числовые Двоичные разряды (мантисса аргумента всегда неотрицательна).

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

М.

М при ар О, М/2 при Зр 1

(1)

Если аргумент X представить в виде

RCO J

X 2- М М„ 2

n(

)

(2)

где

30

(3)

то значение искомой функции У можно определить выражением

у

- 7- -л|Х Poll

-К

о

00 -)к -I

П(1+2 )

где Q Рд/2.

(4) (5)

40

Из выражений (2) и (4) следует

5

М

00

п

()- 1,

У 2«.М,

оо

п

()

Введем следующие обозначения;

Z. М„

(6) (7)

(8)

z;1 п

-)к

(1+2 ,2(9)

55

м: м„- п

1 + 2 )Vi 1,2,

(10)

Выражения (6) и (7) с учетом (9) и (10) могут быть представлены в

виде:

lim Z- 1

Y 2 lim M;.

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

7-i

и

Z.

-j; +

Zj., -t- Zj.,. 2 -t- Z;

.

V , xi . + M . .2 , ,.( (-1

-j;

При вычислении функции У -Jx в соответствии с выражениями (3) и (5) определяется порядок Q результата. Мантисса результата вычисляется с использованием рекуррентных формул (13) и (14). Начальное значение М определяется в соответствии с выражением (1)-, Zg - в соответствии с выражением (8).

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

J; N(Z;., )+,

где N(Z,-., ) - номер старшего нулевого разряда в двоичном представлении числа Z ;., . Признаком окончания операции слу-

жит условие

0,11...1 .

Z,., fl,2,...m (16)

являющееся конечным приближением предельного соотношения (11). Величина М при этом в соответствии с (12) ис- пользуется в качеств е значения мантиссы результата.

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

В исходном состоянии все разряды с первого по (m-t 1)-и регистра 1, используемого для хранения величины Z;, имеют одинаковое (либо нулевое, либо единичное) значение. Вследствие ЭТОГО значение сигнала конца операци на тестом выходе блока управления равно единице, а значение сигнала на первом и втором выходах блока управления равно нулю. На вход 15 устрой) )

to

) )

15

20

25

30

35

)

40

50

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

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

Если значение младшего разряда порядка Bf равно нулю, то код мантиссы, поступивший на первые информационные входы мультиплексоров 6 и 7, проходит на выходы мультиплексоров без преобразования. При единичном значении а, код, поступающий на первые информационные входы мультиплексоров 6 и 7, проходит на выход мультиплексоров со сдвигом на один разряд в сторону младших разрядов. Сформированное на выходе мультиплексоров 6 и 7 приведенное значение мантиссы Мд поступает на информационные входы регистров 1 и 2. Для выполнения вычислений синхронно с одним из тактовых импульсов на вход 16 устройства подается сигнал Пуск, который поступает на управляющий вход регистра 3, осуществляя занесение в регистр 3 значения порядка аргумента Р, а также на первый вход блока 11 управления. По сигналу Пуск на втором выходе блока 11 управления формируется импульс, который поступает на управляющие входы регистров 1 и 2 и осуществляет занесение в регистр 1 величины й о регистр 2 - величины Мд. Значение с выхода регистра 1 поступает на третий вход блока 11 управления, первые входы блоков 8 и 9 сдвига и первый вход сумматора 4. Значение М с выхода регистра 2 поступает на первый вход блока сдвига, первый вход сумматора 5 и второй вход блока 12 формирования результата. На первый вход блока 12 формирования результата с выхода регистра 1 поступает значение порядка Р.

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

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

По коду ZQ на третьем, четвертом

и пятом выходах блока 11 управления формируются (m+1-l) -разрядные коды, содержащие единицу в (J,)-M (j,-1)-M и (2-j;)-M разрядах и нули в остальных разрядах, которые поступают на вторые входы блоков 10, 8 и 9 сдвига соответственно. Значение j определяется в соответствии с выражением (15). Блоки 8 и 9 сдвига осуществляют умножение поступающего на их первые входы кода Z на и 2 соответственно путем сдвига кода Zg нaj,-1и2j, разрядов. Блок 10 сдвига осуществляет умножение кода Мд на 2 путем сдвига кода М на j разрядов

Сумматоры 4 и 5 п роизводят вычисление значений Z и М, в соответстви с выражениями (13) и (14). С выходов сумматоров 4 и 5 коды величин Z,

14976

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

с порядка результата Q в -соответствии с выражениями (3) и (5), а на втором выходе - округленное до га разрядов значение мантиссы результата. Сформированные блоком 12 формирования

10 результата порядок и мантисса результата поступают на выходы 17 и 18 устройства.

Если значения всех т+1 разрядов ZQ одновременно равны единице или.

5 одновременно равны нулю, то вычисления по рекуррентным соотнощениям (13) и (14) не проводятся и в качестве результата используются значения порядка и мантиссы, сформированные

20 блоком 12 формирования результата по поступившим на его входы значениям Р и М„ .

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

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

и М, поступают на вторые информацион- п сигнала на первом управляющем входе

ные входы мультиплексоров 6 и 7 соответственно. Наличие единичного сигнала на вторых управляющих входах мультиплексоров 6 и 7 обеспечивает прохождение информации с вторых информационных входов на выходы муль типлексоров, в результате чего коды Z, и М, поступают на информационные входы соответственно регистров 1 и 2. С приходом очередного тактового импульса значения Z,.и К, заносятся в регистры 1 и 2, На зтом выполнение первой итерации завершается.

В процессе выполнения второй итерации по значениям Z, и М , н устройстве формируются значения 7, и М, которые заносятся в регистры 1 и 2 очередным тактовым импульсол}. Итерационный процесс продолжается до тех пор, пока все т+1 старших разрядов числа Z; не станут равными единице. При этом блок 11 управления формирует на шестом выходе сигнал конца операции, который поступает на выход 19 устройства и запрещает прохождение тактопьпс испульсов со своего второго входа на второй выход. На первом выходе блока управления устанавливается нулевой уровень выходного сигнала.

35

40

45

50

55

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

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

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

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

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

п сигнала на первом управляющем входе

35

40

45

50

55

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

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

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

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

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

7

Блок управления работает следующ образом. Сигнал, поступивший на первый вход 36 блока, через элемент ИЛ 34 проходит на второй выход 39 блок Сигнал, поступивший на второй вход 37 блока, формирует выходной сигнал на втором выходе 39 блока при налич единичного уровня на первом выходе 40 блока, которому соответствует входной код на (m+l)-разрядном третьем входе 38 блока, содержащий хот бы один нуль и хотя бы одну единицу В этом случае шестой выход 41 блока имеет нулевое значение. Если все разряды третьего входа 38 блока одновременно равны нулю или все разря третьего выхода 38 одновременно равны единице, то первый выход 40 блок имеет нулевое, а шестой выход 41 - единичное значения. На третьем 42, четвертом 43, пятом 44 выходах блок формируются коды, имеющие единичное значение в (R+1)-M, R-м и (2К+2)-м разрядах Соответственно и нули в остальных разрядах, где R - номер старшего, равного нулю, разряда кода, поступившего на третий вход 38 устройства.

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

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

8

10

15

20

5

0

5

0

5

0

5

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

9138149710

та И подключены к i-му разряду тре- вый вход i-ro элемента И (,2, ..., тьего входа блока, выход i-ro элемента НЕ соединен с i-входом второго элемента И, выходы первого и второго элементов И подключены к входам первого элемента ИЛИ, выход которого подключен к шестому выходу блока и входу (m-i-2) -го элемента НЕ, выход которого подключен к первому выходу Q первого сумматора по модулю два блока и первому входу третьего эле- подключен к нулевому разряду первого мента И, второй вход которого подклю- входа блока, второй вход j-ro сумма- чен к второму входу блока, а выход - тора по модулю два (,3. ., к первому входу второго элемента ИЛИ, г+1) подключен к (j-2)-My разряду второй вход которого соединен с пер- ., первого входа блока, первый вход вым входом блока, а выход - с вторым выходом блока, выход j-ro элемента НЕ

(,3, ..., га+1) соединен с первым

входом (j-t-2)-ro элемента И, остальные

входы которого соединены с разря- 20 (, г+2, ..., г+щ) подклю- дами третьего входа блока, номера ко- чены к разрядам с (R-r) -го по

торых меньше j, k-й разряд третьего

выхода блока (, m+3, m+4, ,..,

m+1-1) и n-й разряд четвертого выхода

блока (п т11+2, ш+3, .,., ) под- 25 ° сумматора по модулю два, второй

ключены к нулевой шине, и-и разряд вход которого подключен к n(r-1)J-My

третьего выхода блока и Л -и разряд

четвертого выхода блока (,4, ...,

т+2) подключены к выходу ()-го

элемента И, второй разряд третьего,

первый разряд четвертого и четвертый

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

разряду второго входа блока, первый и второй входы (г+га) -го сумматора по модулю два подключены соответственно к т-му и (п1+1)-му разрядам второго входа блока, первый и второй входы первого элемента ИЛИ подключены соответственно к г-му разряду первого входа блока и выходу (г+О-го элемента И, первый и второй входы второго элемента ИЛИ подключены соответственно к первому разряду второго входа блока и выходу (г+2) -го элемента И, а выход - к первому разряду второго выхода блока, выход s-ro сумматора по модулю два (, г+З, ..., r+nv) подключен к (s-r) -му разряду второго выхода блока.

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

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

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

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

разряду второго входа блока, первый и второй входы (г+га) -го сумматора по модулю два подключены соответственно к т-му и (п1+1)-му разрядам второго входа блока, первый и второй входы первого элемента ИЛИ подключены соответственно к г-му разряду первого входа блока и выходу (г+О-го элемента И, первый и второй входы второго элемента ИЛИ подключены соответственно к первому разряду второго входа блока и выходу (г+2) -го элемента И, а выход - к первому разряду второго выхода блока, выход s-ro сумматора по модулю два (, г+З, ..., r+nv) подключен к (s-r) -му разряду второго выхода блока.

1ГЧ771 /

ut.Z

Фиг.З

фиг,.