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

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

Цель изобретения - повышение быстродействия .

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

Устройство (фиг.1) содержит регистры 1-3, сумматоры 4 и 5, мультиплексоры 6 и 7, блоки сдвига 8-10, блок 11 управления, блок 12 формиро-i вания результата, сумматоры 13 и 14

по модулю два, вход 15 задания порядка аргумента, вход 16 задания мантиссы аргумента, вход 17 запуска устройства, тактовый вход 18 устройства, выходы 19 и 20 порядка и мантиссы результата, выход 21 признака конца операции.

Блок сдвига (фиг.2) содержит элементы И 22, элементы ИЛИ 23, входы 24-26, выход 27,

Блок управления (фиг.З) содержит элементы НЕ 28, элементы ИЛИ 29, элементы И 30-33, вход 34, выходы 35-40,

В основе работы устройства лежит следующий способ вычисления значений функции )х. Значение аргумента представляется в виде . Порядок Р представляется (г+1)-разрядным дополнительным кодом a0aj a... аг, где

а0 - знаковый, а а(,,аг числовые двоичные разряды. Мантисса

СП

4j

СП

-vJ

-vl

315

М представляется (п+1)-разрядным дво

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

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

М

I М при Эр-0

М/2

при

(О

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

+ Ј,2-JVZ

к-1

где К 1

Р при Р+1 при

241 Jr

(3)

4 ,

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

у -P-2P /5jMF 2Q.nCI+r.2Jk

) , (4)

К 1

-,

Где Q Р /2

(5) 30

Вычисление мантиссы результата производится с использованием итефац рнных формул

Zk4, z + e

г . к. кk -

.-(jk+0

мкч. + ЈЛ,, 2 Ј. sgn (1 - ZK)

(6)

Порядок Q результата определяется и соответствии с выражениями (3) и (5). Начальные значения К, и г, определяются в соответствии с выражениями

М,2,М.

Значение j при выполнении К-ой итерации выбирается равным номеру старшего нулевого (единичного) разряда дробной части кода ZK при z 1 ), если zK(j) Ј z( + l) и на йдиницу меньше номера j старшего нулевого (единичного) разряда дробной части кода zx , если z(j)z(c () где 2(О - значение f -го двоичного разряда кода Zy,

Значение j задается в устройстве унитарным m-разрядным двоичным кодом 1К содержащим единицу в разряде и нули в остальных разрядах. Величина irtSrn+l определяется требуемой точно

774

стыо вычислений, Логическое уравнение , определяющее значение О-го разряда Т.„( р ejj ,2,. «т j ), имеет вид

Мр) я(р-Н)лЈ z(i) + 1)А г(р+2)Л& z(i), (7)

где z(p)(p)®2),(OJ

Признаком окончания операции служит- условие /1-2 5.,/ 0.00.. . V 1

- o-W. I 1 - I х. -/ , 1 э /.

3 S e l,2,...n(2+l)J.

(8)

5

0

5

0

5

0

45 JQ

5

Величина М5+ при этом используется в качестве мантиссы результата.

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

В исходном состоянии разряды с первого по m-й (V+1)-разрядного регистра 1, используемого для хранения величины ZK, имеют одинаковое (либо нулевое, либо единичное),значение. Вследствие этого, значение признака Конец операции на третьем выходе блока 11 управления равно единице, а значе- ние сигналов на первом и втором выхо.- дах блока 1 управления равно нулю.

На вход 18 устройства непрерывно поступают тактовые импульсы (ТИ). На вход 15 и вход 16 устройства посту™ пают значения порядка и мантиссы аргумента соответственно. Код порядка аргумента со входа 15 поступает на информационный вход третьего 3 регистра, код мантиссы аргумента - на первые информационные входы первого

6и второго 7 мультиплексоров. Младший разряд кода порядка а поступает на первые управляющие входы первого 6 и второго 7 мультиплексоров.

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

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

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

Для выполнения вычислений синхронно с одним из ТИ на вход 17 VCT- ройства подается сигнал Пуск, который поступает на вход блока 1) управления, а также на вход разрешения записи третьего 3 регистра, осуществляя занесение на третий регистр 3 значения порядка аргумента р. По сигналу Пуск на первом выходе блока 11 управления формируется сигнал Занесение, который поступает на входы разрешения записи первого 1 и второго 2 регистров и осуществляет занесение в первый регистр 1 величины z, M и

ступают на вторые выходы третьего 10, первого 8 и второго 9 блоков сдвига соответственно (значение jt определяется в соответствии с приведенным в выше алгоритмом). Первый 8, второй 9, и третий 10 блоки сдвига осуществляют

умножение поступающего на их первые 2-j,

;го, на их первые . 2 f2jV2) и 2-0,-м)

10

15

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

Код z( поступает на второй вход второго 9 блока сдвига с выхода перво го регистра 1, С выхода второго регистра 2 значение К, поступает на второй вход блока 12 формирования результата, на первый вход которого с выхода третьего регистра 3 поступает значение порядка.

Первый 4 и второй 5 сумматоры производят вычисление значении z,

и К,

1 # во второй 2 регистр - величины М,М.

Если значение мантиссы аргумента М не равно нулю (единице), то процесс вычислений реализуется следующим образом При выполнении первой итерации 20 значение z, (О) равное нулю при Ј,1 и единице при f,-l, поступает с выхода первого регистра 1 на первые входы первого 13 и второго 14 сумматоров по модулю два, на вторые входы ко- 25 согласно выражениям (6). С выходов торых с выходов первого 1 и второго 2 первого 4 и второго 5 сумматоров регистрда поступают значения М и zf чение величин г„ и М2 поступают на соответственно. Первый 13 и второй 14 вторые информационные входы первого сумматоры по модулю два производят по- 6 и второго 7 мультиплексоров соот- разрядное суммирование по модулю два 30 ветственно. Наличие единичного значения сигнала Выбор входа на вторых управляющих входах первого 6 и второго 7 мультиплексоров обеспечивает прохождение информации с вторых информационных входов на выходы мультиплексоров, в результате чего коды z2 и 112. поступают на информационные входы первого 1 и второго 2 регисткодов М, и г соответственно с кодом Zij(O), формируя на своих выходах значения Ј(М, и ,

С выхода первого 13 сумматора по модулю два значение поступает на первый вход первого блока 8 сдвига и на третий вход блока 11 управления. С выхода второго сумматора 14 по модулю два значение Ј М1 поступает на первый вход третьего блока 3 О сдвига.

Поступление отличного от нуля (единицы) кода Ј«z на третий вход блока 11 управления приводит к появлению на третьем выходе блока 11 управления нулевого уровня признака Конец операции, а на втором выходе - единичного уровня сигнала Выбор входа. Кроме того, первый выход блока 11 управления подключается к его второму входу, обеспечивая прохождение очередных ТИ на входы разрешения записи первого 1 и второго 2 регистров.

По коду z j на четвертом, пятом и шестой выходах блока 11 управления

35

ров соответственно. С приходом оче- ,д редкого ТИ значения z и К заносятся в первый 1 и второй 2 регистры соответственно о На этом выполнение nept-- вой итерации завершается.

В процессе выполнения второй ите- дс рации по значениям z г и М2 в устройстве аналогично описанному выше формируются значения zg и И,, которые будут занесены в первый 1 и второй 2 регистры соответственно очеред- ,„ ным ТИ, Следующие итерации выполняют аналогично.

Итерационный процесс продолжается до тех пор, пока в результате вы полнения очередной S-ой итерации все m старших числовых разрядов числа

формируется (щ + 1 -разрядные коды, со- fg+1 z 5-нне станут одновременно равны- держащие единицу в ( ( ми единице. При этом блок II управле- и (2jj+2)-M разряде соответственно и

ния запрещает прохождение ТИ со своего второго входа на первый выход и

нули в остапьных разрядах, которые по5177

ступают на вторые выходы третьего 10, первого 8 и второго 9 блоков сдвига соответственно (значение jt определяется в соответствии с приведенным вы- выше алгоритмом). Первый 8, второй 9, и третий 10 блоки сдвига осуществляют

умножение поступающего на их первые 2-j,

;го, на их первые . 2 f2jV2) и 2-0,-м)

10

15

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

Код z( поступает на второй вход второго 9 блока сдвига с выхода первого регистра 1, С выхода второго ре2025 согласно выражениям (6). С выходов первого 4 и второго 5 сумматоров чение величин г„ и М2 поступают на вторые информационные входы первого 6 и второго 7 мультиплексоров соот- 30 ветственно. Наличие единичного значения сигнала Выбор входа на вторых управляющих входах первого 6 и второго 7 мультиплексоров обеспечивает прохождение информации с вторых информационных входов на выходы мультиплексоров, в результате чего коды z2 и 112. поступают на информационные входы первого 1 и второго 2 регистгистра 2 значение К, поступает на второй вход блока 12 формирования результата, на первый вход которого с выхода третьего регистра 3 поступает значение порядка.

Первый 4 и второй 5 сумматоры просогласно выражениям (6). С выходов первого 4 и второго 5 сумматоров чение величин г„ и М2 поступают на вторые информационные входы первого 6 и второго 7 мультиплексоров соот- ветственно. Наличие единичного значения сигнала Выбор входа на вторых управляющих входах первого 6 и второго 7 мультиплексоров обеспечивает прохождение информации с вторых информационных входов на выходы мультиплексоров, в результате чего коды z2 и 112. поступают на информационные входы первого 1 и второго 2 регистизводят вычисление значении z,

и К,

согласно выражениям (6). С выходов первого 4 и второго 5 сумматоров зна чение величин г„ и М2 поступают на вторые информационные входы первого 6 и второго 7 мультиплексоров соот- ветственно. Наличие единичного значе ния сигнала Выбор входа на вторых управляющих входах первого 6 и второго 7 мультиплексоров обеспечивает прохождение информации с вторых информационных входов на выходы мультиплексоров, в результате чего коды z2 и 112. поступают на информационные входы первого 1 и второго 2 регист2025 30

35

ров соответственно. С приходом оче- редкого ТИ значения z и К заносятся в первый 1 и второй 2 регистры соответственно о На этом выполнение nept-- вой итерации завершается.

В процессе выполнения второй ите- рации по значениям z г и М2 в устройстве аналогично описанному выше формируются значения zg и И,, которые будут занесены в первый 1 и второй 2 регистры соответственно очеред- ным ТИ, Следующие итерации выполняют аналогично.

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

g+1 z 5-нне станут одновременно равны- ми единице. При этом блок II управле-

ния запрещает прохождение ТИ со своего второго входа на первый выход и

71575177

формирует на третьем выходе единичное значение признака Конец операции и на втором выходе - нулевое значение сигнала Выбор входа.

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

10

и через инверторы 28 - на входы второго элемента И 33 четвертой группы. Если все m старших разрядов кода, поступающего на третий вход 34 блока, равны единице (нулю), то на выходе первого (второго) элемента И 33 чет вертой группы формируется единичный сигнал, который проходит через (т+1)-ый элемент ИЛИ 29 и поступает на -третий выход 21 блока в качестве сигнала Конец операции.

При наличии хотя бы одной единицы и хотя бы одного нуля одновременно

рования результата порядок и мантисса (5 в m старших разрядов третьего 34 вхо30

результата поступают на выходы 19 и 20 20 устройства.

Если при начале вычислений значения всех m разрядов г равно единице или значение всех т разрядов z, 7g равно нулю, то значение признака нец операции на выходе 21 устройст- йа остается равным единице и вычислений по формулам (6) не производится. В качестве результата используются 25 значения порядка и мантиссы, сформированные блоком 12 формирования результата по поступившим на его входы

/ Ц,

Значениям Р и М .

Блоки 8-10 сдвига работают следующим образом.

На первый 24 вход блока поступает V-разрядный информационный код, на второй вход 25 блока - (V-1 разрядный управляющий код, имеющий единицу в i-ом разряде (1в ,2...,V-l|) и нули в остальных„ Единичный разряд управляющего кода поступает на вторые входы j-x элементов И 22 каж- Дой j-ой группы (j 6 Јl,2,...,Vj, ), на первые входы которых поступают (j-i)-bie разряды информационного кода (при i j) или значение сигнала с третьего входа 26 блока (). В результате входной информационный код сдвигается на i разрядов вправо и освобождающиеся разряды заполняются значением, поступившим на третий 26 вход блока.

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

Сигнал Пуск, поступая на первый вход 17 блока, проходит через m-й элемент ИЛИ 29 и далее на первый 35 выда блока сигнал Конец операции на третьем выходе 21 блока имеет нулевое значение, а на выходе (ш+2)-го элемента НЕ 28 - единичное значение которое поступает на второй выход 36 блока, а также на второй вход третьего элемента И 33 четвертой группы, разрешая прохождение через третий элемент И 33 четвертой группы ТИ, поступающих с второго входа 18 блока. С выхода третьего элемента И 33 четвертой группы ТИ через m-ый элемент ИЛИ 29 поступают на первый выход 35 блока в качестве сигналов Занесение

Единичное значение Ј -го разряда кода j на выходе ()-го элемента И 30 первой группы (,3, ...ml ) формируется при наличии еди3S ничных значений во всех разрядах, номер которых меньше и нулевого значения в сГ-ом разряде кода, поступившего на третий вход 34 блока. При 9 1 единичное значение 1-го разря4Q да кода j формируется первым элементом НЕ 28,

Единичное значение р-го разряда (реЈ 1,2,..,, ) кода j $ формируется на выходе р -го элемента ИЛИ

45 29 при равенстве нулю (р+1)-го и (р +2)-го разрядов кода, поступающего на третий вход 34 блока с использованием О-го элемента И 31 второй группы, и при равенстве нулю р -го и единице (П +1)то разрядов кода, поступающего на третий 34 вход блока с использованием р-го элемента И 32 третьей группы, Единичное значение т-го разряда кода j формируется эле-

50

ход блока в качестве сигнала Занесе- gg ментом И 32 третьей группы. Остальние. Старшие m разрядов поступающего на третий вход 34 блока (т+1 разрядного кода передаются на входы первого элемента И 33 четвертой группы

ные разряды кода j принимают нулевое значение„

По коду, поступившему на третий вход 34 блока, на четвертом 37, пя8

и через инверторы 28 - на входы второго элемента И 33 четвертой группы. Если все m старших разрядов кода, поступающего на третий вход 34 блока, равны единице (нулю), то на выходе первого (второго) элемента И 33 чет вертой группы формируется единичный сигнал, который проходит через (т+1)-ый элемент ИЛИ 29 и поступает на -третий выход 21 блока в качестве сигнала Конец операции.

При наличии хотя бы одной единицы и хотя бы одного нуля одновременно

да блока сигнал Конец операции на третьем выходе 21 блока имеет нулевое значение, а на выходе (ш+2)-го элемента НЕ 28 - единичное значение которое поступает на второй выход 36 блока, а также на второй вход третьего элемента И 33 четвертой группы, разрешая прохождение через третий элемент И 33 четвертой группы ТИ, поступающих с второго входа 18 блока. С выхода третьего элемента И 33 четвертой группы ТИ через m-ый элемент ИЛИ 29 поступают на первый выход 35 блока в качестве сигналов За

несение

Единичное значение Ј -го разряда кода j на выходе ()-го элемента И 30 первой группы (,3, ...ml ) формируется при наличии единичных значений во всех разрядах, номер которых меньше и нулевого значения в сГ-ом разряде кода, поступившего на третий вход 34 блока. При 9 1 единичное значение 1-го разряда кода j формируется первым элементом НЕ 28,

Единичное значение р-го разряда (реЈ 1,2,..,, ) кода j $ формируется на выходе р -го элемента ИЛИ

29 при равенстве нулю (р+1)-го и (р +2)-го разрядов кода, поступающего на третий вход 34 блока с использованием О-го элемента И 31 второй группы, и при равенстве нулю р -го и единице (П +1)то разрядов кода, поступающего на третий 34 вход блока с использованием р-го элемента И 32 третьей группы, Единичное значение т-го разряда кода j формируется эле-

ментом И 32 третьей группы. Остальные разряды кода j принимают нулевое значение„

По коду, поступившему на третий вход 34 блока, на четвертом 37, пя915751

том 38 и шестом 39 выходах блока формируются коды, имеющие единичное значение в (р + 1)-м р -м и (2-0 + 2)-м

эс

5

разрядах соответственно и нули в ос -тальных разрядах.

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

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

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

77

10

5

0

5

0

5

5

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

фиг. 2

Г70

/0о

Ф - - - -

&37. 37v-f

Зв.т W.m+1

F38.r+2

. V-2 40.V-1

Фигз

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

28. т 1