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

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

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

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

1,

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

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

Основным недостатком известного устройства является низкая эффективность, особенно при болыяих значеВИЯХ разрядности обрабатываемой информации, так как увеличение быстродействия достигается за счет значительного увеличения количества используемого оборудования.

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

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

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

( Цель изобретения - повьшение быстродействия устройства для извле чения квадратного корня путем одновременного формирования в цикле нескольких двоичных цифр результата Поставленная цель достигается тем, что, в устройство для извлечения квадратного корня, содержащее регистр подкоренного числа и регист результата, сдвигающий регистр,первьй вычитатель,. причем выход регист ра подкоренного числа соединен с первым входом первого вычитателя, управляющие записью входы регистров подкоренного числа, регистра результата, сдвигающего регистра соединены с входом записи устройств введены второй, третий, четвертый, пятьй, шестой, седьмой вычитатели, семь групп элементов ИЛИ, блок формирования цифр результата и коммута тор, причем выход регистра подкоренного числа соединен с первыми входами второго и четвертого вычита телей, выход первого вычитателя соединен с первыми входами третьего и шестого вычитателей, .вьпсод второг вычитателя соединен с первым входом пятого вычитателя, выход третьего вьмитателя соединен с первым входом седьмого вьиитателя, выходы регистр подкоренного числа и вычитателей с первого, по седьмой соединены соответственно с входами с первого по восьмой коммутатора, выход которого соединен с входом регистра подкорен ного числа, первый и вторые входы всех групп элементов ИЛИ соединены с выходами соответственно регистра рез.ультата и сдвигающего регистра, выходы групп элементов ИЛИ, с первой по седьмую, соединены с вторыми входами соответствующих вычитате лей с первого по седьмой, выходы знаковых разрядов всех вычитателей соединены соответственно с входами с первого по седьмой блока формирования цифр результата, первая группа выходов которого соединена соответственно с управляющими входами коммутатора, а вторая группа соответственно с информационными входами регистра результата, второй управляющий вход записи которого соединен с выходом сдвигающего регистра, причем блок формирования ци результата содержит первый, второй, третий, четвертьй, пятый, шестой, седьмой, восьмой элементы И и эле8лменты ИЛИ с первого по третий,причем первьй вход блока формирования цифр соединен с первыми инверсными входами первого, третьего, шестого, седьмого элементов И, первьгми прямыми входами второго, четвертого, пятого, восьмого элементов И, второй вход блока формирования цифр соединен с вторыми инверсными входами второго,; пятого элементов И и вторыми прямыми входами четвертого, восьмого элементов И, третий вход блока формирования цифр соединен с вторыми инверсными входами третьего, седьмого, элементов И, вторыми прямыми входами первого, шестого элементов И,четвер тьй вход блока формирования цифр соединен с третьим инверсным входом четвертого элемента И и третьим прямым входом восьмого элемента И, пятьй вход блока формирования цифр соединен с третьим инверсным входом пятого элемента И и третьим прямым входом второго элемента И, шестой вход блока формирования цифр соединен с третьим инверсным входом шестого элемента И и третьим прямым входом первого элемента И, седьмой вход блока формирования цифр соединен с третьим инверсным входом седьмого элемента И и третьим прямым входом третьего элемента И, первая группа выходов блока форм1фования цифр является выходами соответствзпо щих элементов И с первого по восьмой, первьй, второй, третий, четвертый входы первого элемента ИЛИ соединены соответственно .с выходами второго, третьего, шестого, седьмого элементов И, первый, второй, третий, четвертьй входы второго элемента ИЛИ соединены соответственно с выходами третьего, второго, седьмого,пятого элементов И, первый, второй, третий, четвертый входы третьего элемента ИЛИ соединены соответственно с выходами пятого, шестого, четвертого, седьмого элементов И, вторая группа выходов блока формирог вания цифр является выходами элементов ИЖ с первого по третий. На фиг.1 изображена структурная схема предлагаемого устройства (рассматривается случай, когда число одновременно формируемых в цикле двоичных 1щфр результата равно трем); на фиг.2 и 3 - функциональные схемы двух узлов элементов ИЛИ; на фиг.4 - один из возМожных вариантов функциональной схе мы блока формирования цифр результата-, на фиг.5 - функциональная схема -t-ro разряда коммутатора. Устройство (фиг.1) содержит первый 1 , второй 2, третий 3, четвертый 4, пятый 5, шестой 6 и седьмой вычитатели, группы 8-14 элементов ИЛИ,коммутатор 15,. блок 16 формирования цифр результата, регистры 17 и 18 соответственно подкоренного числа и результата, сдвигающий регистр 19, вход 20 Устройства и выходы 21-27 знаковых разрядов вычитателей 1-7 соответственно. Группы 8-14 элементов ИЛИ предназначены для формирования значений вычитаемого вьгаитателей 1-7 при всевозможных путях развития вычисли

Для второго цикла:

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

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

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

01, 001, 101, 0001, 0101, 1001 и 1101. Номера разрядов регистра 18 результата, к значениям которых осуществляется присовокупление значений указанных двоичных кодов, однозначно определяются положением единицы, хранимой в сдвигающем регистре 19 устройства (в первом цикле работы устройства эта единица находится в первом разряде сдвигающего регистра, далее она продвигается на одну позицию в каждом цикле в направлении последнего разряда регистра). На фиг.2 и 3 в качестве примера приведены фрагменты функциональных схем соответственно группы 8 элементов ИЛИ и группы 14 элементов ИЛИ (функциональные схемы других rpjnrin элементов ИЛИ устройства могут быть разрательного процесса оиределения трех двоичных цифр результата по алгоритму извлечения квадратного корня с восстановлением остатка, причем эти значения зависят не только от вычитателей, на вход вычитаемого которых они поступают, но и от порядкового номера цикла определения очередных трех двоичных цифр результата. Ниже приведены значения вычитаемых, формируемых на выходах групп 8-14 элементов ИЛИ для первых трех циклов вычислений устройства (значения вычитаемых расположены подобно тому, как размещены соответствующие группы 8-14 элементов ИЛИ на структурной схеме устройства фиг.1). Для первого цикла ботаны подобным образом с-учетом приведенных вьппе диаграмм) . Блок 16 формирования цифр резул тата выполняет две функции: формирует сигналы Y,Y;,YJ,Y,Y,Y,Y и Y управляющие работой коммутатора, а также формирует три двоичные цифры результата f, fj з соответствии с алгоритмом извлечен квадратного корня с восстановление остатка. Формирование указанных зш ляющих сигналов и цифр результата может осуществляться в соответстви со следующими логическими вьфажениями: X х ; X X : 2 21 22 iS 1 2 23 26 Y s V 5 1 24 5 21 22 25V - X -f X 17 21 22 Y x X -x -, 3 21 23 27 - Y ,.Y, где Y - управляющий сигнал, под действием которого коммутатор 15 осуществляет выборку результата, сформированного на выходе вьиитателя 7 на фиг.1; х - логическая переменная, соответствующая значению знаковог разряда вычитателя 1 (если на вых де вычитателя 1 сформирована отри 1, В цательная разность, то Противном случае х. 0) f 1 ,f2 - соответственно старшая и младшая цифры результата из трех формируемых в одном цикле вы числений двоичных цифр, На фиг.4 приведена функциональ схема блока 16 формирования цифр результата, работающая в соответствии с приведенными выше логичес кими вьражениями. С помощью коммутатора 15 осуще ствляется выборка в качестве очередного остатка либо значения раз ности одного из вычитателей 1-7, либо значения содерж1 мого регистр 17 подкоренного числа. Управление этой выборкой производится под действием соответствующих сигнало .. П,,посту 088 паю1Щ х на управляющие входы ко1« утатора 15 с первой группы выходов блока 16 формирования цифр результата. На фиг.5 показана функциональная схема i-ro разряда коммутатора 15, где, например, К - зна-. чение разности на выходе 1-го разряда вычитателя с порядковым номером 5 на фиг.1. Устройство работает следующим образе. В исходном состоянии в регистре 17 подкоренного числа хранится п-разрядное двоичное число х (в принципе число х может быть как целым, так и дробньм, однако в дальнейшем для определенности будем предполагать, что оно есть правильная нормализованная двоичная дробь, при- чем только положительная),регистр 18 результата обнулен, в первом разряде сдвигающего регистра 19 записана единица (разрядность ni сдвиганщего регистра может быть выбрана равной числу циклов работы устройства для извлечения квадратного корня из п-разрядного двоичного числа, будем считать, что число циклов работы устройства равно п/3,а следовагельно, и tn V3). Во всех циклах устройство работает одинаковьм образом, поэтому более подробно рассмотрим его работу только в одном, i-M цикле (1 1 i (п) К началу i-ro цикла в регистре 18 результата сформированы 3(i-1) старших двоичных цифр результата, а в i-M разряде сдвигакмцего регистра 19 хранится единица. По содержимому регистра 18 результата и с учетом единицы, хранимой в i-M разряде сдвигающего регистра 19, на выходах групп 8-14 элементов ИЛИ формируются вычитаемые, значения которых поступают на вторые входы соответствующих вычитателей 1-7, после этого все вычитатели практически начинают работать одновременно и на их выходах формируются результаты при всех возможных путях развития вычислительного процесса определения очередных трех двоичных цифр результата по алгоритму извлечения квадратного корня с восстановлением остатка. Очевидно, что в одном цикле определения трех двоичных цифр результата только один из этих восьми результатор может быть правильным (выбор пра-вильного результата производится с помощью управляющих сигналов Y,Y, V V V V V ijt V V TTr Mr rotioubiH ) По истечении vif V Y 3 Ч 5 6 . времени, равного примерно времени суммирования двух и-разрядных двоичных чисел, коммутатор 15 выбирает в качестве очередного остатка результат либо одного из вычитателей 1-7, либо содержимое регистра 17 под коренного числа, который с разрешени сигнала на входе 20 устройства записьшается в регистр 17 со сдвигом вле во на один двоичный разряд. Одновременно с выборкой коммутатором 15 од- 5

ного из восьми результатов и записью в качестве очередного остатка в регистр 17 в блоке 16 формируются три двоичные цифры результата ,(,к ,, которые с разрешения того же сигнала на входе 20 устройства записываются в разряды 1+3(1-1), 2+3(1-1)1 и 3+3(i-1) регистра 18 результата в качестве трех очередных цифр результата (i-t|, S 2+3 (i-l) и Y 3-3 (1-1) (номера разрядов регистра 18, в которые должны быть запи.саны три очередных цифры результата однозначно определяет единица в -м разряде сдвигающего регистра IQ) Параллельно с записью очередного остатка и- очередных цифр результата в регистры соответственно 17 и 18 в

Первьй цикл определения цифр результата 1

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

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

0,100111. - 0,01 810 регистре 19 осуществляется сдвиг единицы в (1+1)-йего разряд (это возможно, так как предполагается, что в устройстве используются синхронные двухтактные триггеры). На этом j-й цикл работы устройства по определению очередных трех двоичных цифр результата заканчивается. После выполнения п/3 циклов в регистре 18 будет сформирован п-разрядный двоичный, код результата Y, Вьщвигаемая в (п/3)-м цикле работы устройства единица из последнего разряда сдвигающего регистра 19 ука11Аналогично может быть разработано устройство для извлечения квадратного корня из двоичного числа, в каждом цикле которого формируется две или больше чем три двоичные циф ры результата. Однако с увеличением числа К одновременно формируемых в цикле двоичных цифр результата резко возрастает объем используемого в устройстве оборудования. Так, например, уже при К 5 в устрой8стве необходимо использовать тридцать один вычитатель и-тридцать один узел элементов ИЛИ. Кроме того, несколько усложняется коммутатор и узел формирования цифр результата. Поэтому представляют практический интерес, по-видимому, устройства для извлечения квадратного корня, формирующие в одном цикле не более шести двоичных цифр результата.

dttfoffu f)a3pjiffof pftvcm a /У

fS

oJ-a

St/xo n оЛ pajfl ffoS pettffm/w y

tgf /tt «Лг /w4jJ u tsfa ггЛгг

S