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

 

УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ : КВАДРАТНОГО КОРНЯ, содержащее регистр подкоренного числа и регистр результата, сдвигающий регистр, первьй вьиитатель, причем выход регистра подкоренного числа соединен с первьм входом первого вычитателя, . . управляющие записью входы регистров подкоренного числа, регистра результата , сдвигающего регистра соединены с входом записи устройства, отличающееся тем, что, с целью повьппения быстродействия за счет формирования в одном цикле вычислений нескольких двоичных цифр результата, в него введены второй, третий, четвертый, пятьй, шестой, седьмой вычитатели, семь групп элементов ИЛИ, блок формирования цифр результата и коммутатор, причем выход регистра подкоренного числа соединен с первьзми входами второго и четвертого вычитателей, выход первого вычитателя соединен с первыми входами третьего и шестого вычитателей , выход второго вычитателя соединен с первым входом пятого вычитателя, выход третьего вычитателя соединен с первым входом седьмого вьиитателя, выходы регистра подкоренного числа и вычитателей с первого по седьмой соединены соответственно с входами с первого по восьмой коммутатора, выход которого соединен с входом регистра подкоренного числа, первые и вторые входы всех групп элементов ИЛИ соединены с выходами соответственно регистра результата и сдвигающего регистра, а выходы групп элементов ИЛИ, с первой по седьмую, соединены с вторыми входами соответствующих вычитателей с .первого по седьмой, выходы знаковых разрядов всех вычитателей соединены соответственно с входами с первого по седьмой блока формирования цифр результата, первая группа выходов которого соединена соответственно с управляющими входами коммутатора , а вторая группа - соответственно с информационными входами регистра результата, второй управляющий вход записи которого соединен с выходом сдвигающего регистра, причем блок формирования цифр результата содержит первый, второй третий, четвертый, пятый, шестой, седьмой, восьмой элементы И и элементы ИЛИ с первого по третий,причем первый вход блока формирования цифр соединен с первыми инверсными входами первого, третьего, шестого, седьмого элементов И, первыми прямыми входами второго, четвертого , пятого, восьмого элементов И, второй вход блока формирования цифр соединен с вторыми инверсными

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

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

РЕСПУБЛИК

Зи G 06 F 71552

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3393543/18-24 (22) 15.02.82 (46) 15. 12.84. Бюл. ¹ 46 (72) Г.П. Лопато и А.А. Шостак (71) Минский радиотехнический институт (53) 681.325 (088.8) (56) 1. Матричное устройство для извлечения корня. Экспресс-информация. Вычислительная техника, 1980, ¹ 5.

2. Корцев M.À. Арифметика цифровых машин. M. "Наука", 1969, с. 536-542 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ

КВАДРАТНОГО КОРНЯ, содержащее регистр подкоренного числа и регистр результата, сдвигающий регистр, первый вычитатель, причем выход регистра подкоренного числа соединен с первым входом первого вычитателя, управляющие записью входы регистров подкоренного числа, регистра результата, сдвигающего регистра соединены с входом записи устройства, отличающееся тем, что, с целью повышения быстродействия за счет формирования в одном цикле вычислений нескольких двоичных цифр результата, в него введены второй, третий, четвертый„ пятый, шестой, седьмой вычитатели, семь групп элементов ИЛИ, блок формирования цифр результата и коммутатор, причем выход регистра подкоренного числа соединен с первьии входами второго и четвертого вычитателей, выход первого вычитателя соединен с первыми входами третьего и шестого вычитателей, выход второго вычитателя

„„SU„„1129608 А соединен с первым входом пятого вычитателя, выход третьего вычитателя соединен с первым входом седьмого

:вычитателя, выходы регистра подкоренного числа и вычитателей с первого по седьмой соединены соответственно с входами с первого по вось мой коммутатора, выход которого соединен с входом регистра подкоренного числа, первые и вторые входы всех групп элементов ИЛИ соединены с выходами соответственно регистра

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

1129608

Т (1 +t входами второго, пятого элементов И и вторыми прямыми входами четвертого, восьмого элементов И, третии вход блока формирования цифр соединен с вторыми инверсными входами третьего, седьмого элементов И, вторыми прямыми входами первого, шестого элементов И, четвертый вход блока формирования цифр соединен с третьим инверсным входом четвертого элемента И и третьим прямым входом восьмого элемента И, пятый вход блока формирования цифр соединен с третьим инверсным входом пятого элемента И и третьим прямым входом второго элемента И, шестой вход блока формирования цифр соединен с третьим инверсным входом шестого элемента И и третьим прямым входом первого элемента И, седьмой вход блока фор— мирования цифр соединен с третьим

Ф

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

Известно однотактное устройство для извлечения квадратного корня, выполненное в виде матрицы определенным образом соединенных одно- 10 разрядных двоичных сумматоров-вычитателей или вьиитателей (1 ).

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

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

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

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

1129

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

Поставленная цель достигается тем, что, в устройство для извлечения квадратного корня, содержащее регистр подкоренного числа и регистр результата сдвигающИй регистр перФ

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

25 и шестого вычитателей, выход второговычитателя соединен с первым входом пятого вычитателя, выход третьего вычитателя соединен с первым входом седьмого вычитателя, выходы регистра подкоренного числа и вычитателей с первого по седьмой соединены соответственно с входами с первого по восьмой коммутатора, выход которого соединен с входом регистра подкорен- 35 ного числа, первый и вторые входы всех групп элементов ИЛИ соединены с выходами соответственно регистра результата и сдвигающего регистра, а выходы групп элементов ИЛИ, с пер= 4о вой по седьмую, соединены с вторыми входами соответствующих вычитателей с первого по седьмой, выходы знаковых разрядов всех вычитателей соединены соответственно с входами 45 с первого по седьмой блока формирования цифр результата, первая груп-. .па выходов которого соединена соответственно с управляющими входами коммутатора, а вторая группа- 50 соответственно с информационными входами регистра результата, второй управляющий вход записи которого соединен с выходом сдвигающего регистра, причем блок формирования цифр55 результата содержит первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой элементы И и эле608 4 менты ИЛИ с первого по третий, причем первый вход блока формирования цифр соединен с первыми инверсными входами первого, третьего, шестого, седьмого элементов И, первыми прямыми входами второго, четвертого, пятого, восьмого элементов И, второй вход блока формирования цифр соединен с вторыми инверсными входами второго,, пятого элементов И и вторыми прямыми входами четвертого, восьмого элементов И, третий вход блока формирования цифр соединен с вторыми инверсными входами третьего, седьмого., элементов И, вторыми прямыми входами первого, шестого элементов И,четвер тый вход блока формирования цифр соединен с третьим инверсным входом четвертого элемента И и третьим прямым входом восьмого элемента И, пятый вход блока формирования цифр соединен с третьим инверсным входом пятого элемента И и третьим прямым входом второго элемента И, шестой вход блока формирования цифр соединен с третьим инверсным входом шестого элемента И и третьим прямым входом первого элемента И, седьмой вход блока формирования цифр соеди- нен с третьим инверсным входом седьмого элемента И и третьим прямым входом третьего элемента И, первая группа выходов блока формирования цифр является выходами соответствую- щих элементов И с первого по восьмой, первый, второй, третий, четвертый входы первого элемента ИЛИ соединены соответственно .с выходами второго, третьего, шестого, седьмого элементов И, первый, второй, третий, четвертый входы второго элемента ИЛИ соединены соответственно с выходами третьего, второго, седьмого,пятого элементов И, первый, второй, третий, четвертый входы третьего элемента ИЛИ соединены соответственно с выходами пятого, шестого, четвертого, седьмого элементов И, вторая группа выходов блока формиро", вания цифр является выходами элементов ИЛИ с первого по третий.

На фиг. 1 изображена структурная схема предлагаемого устройства (рассматривается случай, когда число одновременно формируемых в цикле двоичных цифр результата равно трем); на фиг.2 и 3 — функциональные схемы двух узлов элементов ИЛИ„ на фиг.4 — один из воз29608 тельного процесса определения трех двоичных цифр результата по алгоритму извлечения квадратного корня с восстановлением остатка, причем эти значения зависят не только от вычитателей, на вход вычитаемого которых они поступают, но и от порядкового номера цикла определения очередных трех двоичных цифр результата. Ниже приведены значения вычитаемых, формируемых на выходах групп 8-14 элементов ИЛИ для первых трех циклов вычислений устройства (значения вычитаемых расположены подобно тому, как размещены соответствующие группы 8-14 элементов ИЛИ на структурной схеме устройства фиг.1).

Для первого цикла

101

001 г — — ч

0001 0101

Лпя второго цикла: .

YY (0.1

1 2 3

1001 1101

YY (001

2 3

YYY)01

2 3

Y„Y2Y 0001 Y Y Y 0101 Y Y Y 1001 . (((1101

23 12 3 123 для третьего цикла

YY. Y01

1 2

Y (...Y 101

2 6

YY., Y Oo1

Y Y,... (0001 (Y ...Y 0101

12" 6 < 2" Ь где У1Y27 - три наиболее старшие двоичные цифры результата, сформированные в первом цикле вычислений устройства и хранимые к началу его второго цикла соответственно в первом, втором третьем разрядах регистра 18 результата;

Y Y

Из приведенных диаграмм видно, что группы 8-14 элементов ИЛИ фактически осуществляют присовокупление 5 к значениям определенных нулевых разрядов регистра 18 результата значений двоичных кодов. соответственно

S 11 можных вариантов функциональной схемы блока формирования цифр резуль тата; на фиг.5 — функциональная схема 1-ro разряда коммутатора.

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

17 и 18 соответственно подкоренного числа и результата, сдвигающий регистр 19, вход 20 устройства и выходы 21-27 знаковых разрядов вычитателей 1-7 соответственно.

Группы 8-14 элементов ИЛИ предназначены для формирования значений вычитаемого вычитателей 1-7 при всевозможных путях развития вычислиО. (Y Y6100 Y Y Y 1101

01, 001, 101, 0001, 0101, 1001 и

1101, Номера разрядов регистра 18 результата, к значениям которых осуществляется присовокупление значений указанных двоичных кодов, однозначно определяются положением единицы, хранимой в сдвигающем регистре 19 устройства (в первом цикле работы устройства эта единица находится в первом разряде сдвигающего регистра, далее она продвигается на одну позицию в каждом цикле в направлении последнего разряда регистра). На фиг.2 и 3 в качестве примера приведены фрагменты функциональных схем соответственно группы 8 элементов ИЛИ и группы 14 элементов ИЛИ (функциональные схемы других групп элементов ИЛИ устройства могут быть разра7 1129608 8 ботаны подобным образом с-учетом приведенных выше диаграмм).

Блок t6 формирования цифр результата выполняет две функции: формирует сигналы 7» Y* Y+ Y+ Y» Y» Y»

М 1 ю 2 ° 3 41 5 Ь 7 и Y óïðàâëÿþùèå работой коммутатора, а также формирует три двоичные цифры результата Е„, f и в соответствии с алгоритмом извлечения квадратного корня с восстановлением остатка. Формирование указанных упра ляющих сигнапов и цифр результата может осуществляться в соответствии со следующими логическими выражениями:

»

Y =х х х

1 21 23 2Ь ("=Х Х Х

2 21 22 5

=Х Х х

»

4 21 22 24

Y =Х Х Х

5 21 22 26

Y%

6 21 23 2Ь где Y+, — управля ций сигнал под действием которого коммутатор 15 осуществляет выборку результата, сформированного на выходе вьиитателя 7 на фиг.1;

x — логическая переменная, соответствующая значению знакового разряда вычитателя 1 (если на выходе.вычитателя 1 сформирована отрицательная разность, то х21= 1, B противном случае х2, = 0)

Х 1,f — соответственно старшая и младшая цифры результата из трех формируемых в одном цикле вычислений двоичных цифр.

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

С помощью коммутатора 15 осуществляется выборка в качестве очередного остатка либо значения разности одного иэ вычитателей 1-7, либо значения содержимого регистра

17 подкоренного числа. Управление этой выборкой производится поц действием соответствующих сигналов 1 », (» » Y Y+ и Y посту1 2 3 4 5 $ 7 17) 50

У =х х х ; (» =х +х +х

21 23 27 17 21 22 2$ 4

Y =X Х Х

3 21 23 27

10 в15

45 пающих на управляющие входы коммутатора 15 с первой группы выходов блока !6 формирования цифр результата. На фиг.5 показана функциональная схема t-ro разряда коммутатора 15, где, капример, Р— зна-. чение разности на выходе i-ro разряда вычитателя с порядковым номером

5 на фиг.1.

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

В исходном состоянии в регистре

17 подкоренного числа хранитсяь-разрядное двоичное число х (в принципе число х может быть как целым, гак и дробным, однако в дальнейшем для определенности будем предполагать, что оно есть правильная нормализованная двоичная дробь, причем только положительная), регистр 18 результата обнулен, в первом разряде сдвнгающего регистра 19 записана единица (разрядно ть rn сдвигающего регистра может быть выбрана равной числу циклов работы устройства для извлечения квадратного корня иэ к-разрядного двоичного числа, будем считать, что число циклов работы устройства равно и /З,а следовээельно, и m = /3).

Во всех циклах устройство работает одинаковым образом, поэтому более подробно рассмотрим его работу только в одном, i-м цикле (1 (i («x )

К началу i-го цикла в регистре 18 результата сформированы 3(i-1) старших двоичных цифр результата, а в

1-м разряде сдвигакнцего регистра 19 хранится единица. По содержимому регистра 18 результата и с учетом единицы, хранимой в .1-M разряде сдвигающего регистра 19, на выходах групп 8-14 элементов ИЛИ формируются вьиитаемые, значения которых поступают на вторые входы соответствующих вычитателей 1-7, после этого все вычитатели практически начинают работать одновременно и на их выходах формируются результаты при всех воз, можных путях развития вычислительного процесса определения очередных трех двоичных цифр результата по алгоритму извлечения квадратного корня с восстановлением остатка.

Очевидно, что в одном цикле определения трех двоичных цифр результата только один из этих восьми результатов может быть правильным (выбор пра=

О, 100111

0,01

О, 010111 — О, 101110

О, 101

1 001110

О, 001

1, 000110

0,001100

О, 0101

1, 111000

;. О, 011100 о 0001

t,o»ooo

i 011 о |оо о,ttt

1000

О, 011000 о 110о1

1,1оо11о

1, 001100 о 110101

0,010111

0,011000

О 1101001

1,1000111

О, 110000 о 110001

1, 111111 . 1, 111110 о ttootot

1,0010111

-1,100000

0,11ОО001

0,101110

О, 1101111

1,1101111

0 1011111

1, 0111110

9 11296 випьного результата производится с . помощью управляющих сигналов Y„, У», Y+ Y» »Y» Y" Y»и Y» ) По истечении

3 41 51 6 . 1 17 времени, равного примерно времени суммирования двух я-разрядных двоичных чисел, коммутатор 15 выбирает в качестве очередного остатка результат либо одного из вычитателей

1-7, либо содержимое регистра 17 под- ip коренного числа, который с разрешения сигнала на входе 20 устройства записывается в регистр 17 со сдвигом влево на один двоичный разряд. Одновременно с выборкой коммутатором 15 од, ного из восьми результатов и записью в качестве очередного остатка в регистр 17 в блоке 16 формируются три двоичные цифры результата f„,f и f, которые с разрешения того же сигнала 2р на входе 20 устройства записываются . в разряды (1+3(1-1)), (2+3(1-1)) и (3+3(i-1)) регистра 18 результата в качестве трех очередных цифр результата V(i+3 (1- 1j, YP+

Y(3+9(i-1)1 (номера разрядов регистра 18, в которые должны быть запи,саны три очередных цифры результата однозначно определяет единица в

1-м разряде сдвигающего регистра 19). З,1

Параллельно с записью очередного остатка и очередных цифр результата в регистры соответственно 17 и 18 в

Первый цикл определения цифр результата (1, 1;О) Второй циклопределения цифр результата (О, О, I) 08 10 регистре 19 осуществляется сдвиг единицы в (t +1)-й его разряд (это возможно, так как предполагается, что в устройстве используются синхронные двухтактные триггеры). На этом 1«-й цикл работы устройства по определению очередных трех двоичных цифр результата заканчивается.

После выполнения н /3 циклов в регистре 18 будет сформирован и -разрядный двоичный.код результата У, Выдвигаемая в (ь/3)-м цикле работы устройства единица из последнего разряда сдвигающего регистра 19 указывает на окончание операции. Разумеется, что число циклов работы устройства может быть определенным образом увеличено, если этого потребует точность вычисления.

Рассмотрим пример, более детально поясняющий принцип работы и структурные особенности устройства. Пусть н = 6 и х= 0,100111 (результат должен быть равен О, 1 1 0001) . Ниже приведено пространственно-числовое изображение процесса извлечения квадратного корня из числа у в предлагаемом устройстве. В нем вычисления расположены подобно тому, как размещены вычитатели 1-7 на структурной схеме устройства на фиг. 1.

11 11

Аналогично может быть разработано устройство для извлечения квадратного корня иэ двоичного числа, в каждом цикле которого формируется две или больше чем три двоичные цифры результата. Однако с увеличением числа k одновременно формируемых в цикле двоичных цифр результата резко возрастает объем используемого в устройстве оборудования. Так, например, уже при К = 5 в устрой29608

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

5 узел формирования цифр результата.

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

1129608 й

Ф

Оияоди раэрюдо6 рсеистра rd

Лаиб рдуиЯв/ ,оипм- . ,аа 1/

Алка Аг ра.гагА / роимрп fg

1 1 29608

ir a as aO as ae. u и и4г Ъ 44 4 4ФЪ4 4ф 4 Ат

Ф r ю

Ьб б4

+i i8

f г г и Ур п юг Х

Щ. Заказ 9454/39 аж 698 Подписное

Фискал ППП "Патент", г. Ужгород, ул. Проектвав, 4