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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 6 Р 755 ПИСАНИЕ ИЗОБРЕТЕНИ с Бюл. В 46о и А.А. Шосдиотехническ акч 88.8 ое устройс я. Экспрес ьная техни длянформа,цифроА. Арифметик "Наука", 196 тотип). шес лементов И, первывторого, четвертоо элементов И,ого, седьмогорямыми входами го, пятого, восьмовторой вход блокацифр соединен с вт ормированиярыми инверсными ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ Н АВТОРСКОМУ СВИДЕТЕЛЬСТ(54) (57) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее регистр подкоренного числа и регистр результата, сдвигающий регистр, первый вычитатель, причем выход ре гистра подкоренного числа соединен с первым входом первого вычитателя, управляющие записью входы регистров подкоренного числа, регистра результата, сдвигающего регистра соединены с входом записи устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия за счет формирования в одном цикле вычислений нескольких двоичных цифр результата, в него введены второй, третий, четвертый пятый, шестой, седьмой вычитатели, семь групп элементов ИЛИ, блок формирования цифр результата и коммутатор, причем выход регистра подкоренного числа соединен с первьии входами второго и четвертого вычитателей, выход первого вычитателя соединен с первыми входами третьего и шестого вычитателей, выход второго вычитателя.ЯО 1129608 А ен с первым входом пятог вычитателя, выход третьего вычитателя соединен с первым входом седьмого вычитателя, выходы регистра подкоренного числа и вычитателей с первого по седьмой соединены соответственно с входами с первого по вось". мой коммутатора, выход которого соединен с входом регистра подкоренного числа, первые и вторые входы всех групп элементов ИЛИ соединены с выходами соответственно регистра ; результата и сдвигающего регистра, а выходы групп элементов ИЛИ, с первой по седьмую, соединены с вторыми входами соответствующих вычитателейс первого по седьмой, выходы знаковых разрядов всех вычитателей соединены соответственно с входами с первого по седьмой блока формирования Се цифр результата, первая группа выходов которого соединена соответственно с управляющими входами комму татора, а вторая группа - соответ. ственно с информационными входами регистра результата, второй управляющий вход записи которого соедин с выходом сдвигающего регистра,причем блок формирования цифр результата содержит первый, второйтретий, четвертый, пятый, шестой,седьмой, восьмой элементы И и элементы ИЛИ с первого по третий,причем первый вход блока формирования цифр соединен с первыми инверсными входами первого, третьего,1129608 Т "1 +Ф входами второго, пятого элементор И ивторыми прямыми входами четвертого,восьмого элементов И, третии входблока формирования цифр соединенс вторыми инверсными входами третьего, седьмого элементов И, вторымипрямыми входами первого, шестогоэлементов И, четвертый вход блокаформирования цифр соединен с третьим инверсным входом четвертого элемента И и третьим прямым входомвосьмого элемента И, пятый входблока формирования цифр соединенс третьим инверсным входом пятогоэлемента И и третьим прямым входомвторого элемента И, шестой вход блокаформирования цифр соединен с третьиминверсным входом шестого элемента Ии третьим прямым входом первогоэлемента И, седьмой вход блока формирования цифр соединен с третьим 1ФИзобретение относится к вычислительной технике и может быть использовано в универсальных и специализированных арифметических устройствах для быстрого извлечения квадратного 5 корня из двоичного числаИзвестно однотактное устройство для извлечения квадратного корня, выполненное в виде матрицы определенным образом соединенных одно разрядных двоичных сумматоров-вычитателей или вьиитателей 1 3.Основным недостатком известного устройства является низкая эффектив-, ность, особенно при больших значе ниях разрядности обрабатываемой информации, так как увеличение быстродействия достигается за счет значительного увеличения количества используемого оборудования. 20Наиболее близким по технической сущности к изобретению является устройство для извлечения квадратного корня, содержащее регистры подкоренного числа и результата, 25 сдвигающий регистр, вычитатель,причем первый и второй входы вьиитателя соединены с выходами регистров соответственно подкоренного числа и результата, а его выход соединен с З 0 инверсным входом седьмого элемента Ии третьим прямым входом третьего элемента И, первая группа выходов блокаформирования цифр является выходамисоответствующих эпементов И с первого по восьмой, первый, второй,третий, четвертый входы первогоэлемента ИЛИ соединены соответственно с выходами второго, третьего,шестого, седьмого элементов И,первый,второй, третий, четвертый входывторого элемента ИЛИ соединены соответственно с выходами третьего,второго, седьмого, пятого элементов И, первый, второй, третий, четвертый входы третьего элемента ИЛИсоединены соответственно с выходами пятого, шестого, четвертого,седьмого элементов И,вторая группа выходовблока формирования цифр является выходами элементов ИЛИ с перввого по третий. 2входом регистра подкоренного числа, управляющие входы регистров подкоренного числа, управляющие входы регистров подкоренного числа и результата, а также сдвигающего регистра соединены с входом устройства. В данном устройстве фактически реализован алгоритм извлечения квадратного корня с восстановлением остатка, так как в регистр подкоренного числа в качестве очередного остатка записывается только положительная разность, сформированная на выходе вычитателя (запись же отрицательной разности в регистр подкоренного числа блокируется,а в качестве очередного остатка используется значение предыдущего остатка) 23Недостатком известного устройства является низкое быстродействие, вызванное в первую очередь формированием в каждом цикле его работы только одной двоичной цифры результата. Извлечение квадратного корня из и -разрядного двоичного числа осуществляется в нем за время,примерно равное1129 3Цель изобретения - повышение быстродействия устройства для извлечения квадратного корйя путем одновременного формирования в цикле нескольких двоичных цифр результата.Поставленная цель достигается тем, что, в устройство для извлечения квадратного корня, содержащее регистр подкоренного числа и регистр результата сдвигающИй регистр перФ10 вый вычитательпричем выход регистра подкоренного числа соединен с первым входом первого вычитателя, управляющие записью входы регистров подкоренного числа, регистра результата, сдвигающего регистра соединены с входом записи устройства, введены второй, третий, четвертый, пятый, шестой, седьмой вычитатели, семь групп элементов ИЛИ, блок формирования цифр результата и коммутатор, причем выход регистра подкоренного числа соединен с первыми входами второго и четвертого вычитателей, выход первого вычитателя соединен с первыми входами третьего25 и шестого вычитателей, выход второго. вычитателя соединен с первым входом пятого вычитателя, выход третьего вычитателя соединен с первым входом седьмого вычитателя, выходы регистра подкоренного числа и вычитателей с первого по седьмой соединены соответственно с входами с первого по восьмой коммутатора, выход которого соединен с входом регистра подкорен ного числа, первый и вторые входы всех групп элементов ИЛИ соединены с выходами соответственно регистра результата и сдвигающего регистра, а выходы групп элементов ИЛИ, с пер= 40 вой по седьмую, соединены с вторыми входами соответствующих вычитателей с первого по седьмой, выходы знаковых разрядов всех вычитателей соединены соответственно с входами 45 с первого по седьмой блока формирования цифр результата, первая груп-. па выходов которого соединена соответственно с управляющими входами коммутатора, а вторая группа - 50 соответственно с информационными входами регистра результата, второй управляющий вход записи которого соединен с выходом сдвигающего регистра, причем блок формирования цифр 55 результата содержит первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой элементы И и эле 608 4 менты ИЛИ с первого по третий, причем первый вход блока формирования цифр соединен с первыми инверсными входами первого, трЕтьего, шестого, седьмого элементов И, первыми прямыми входами второго, четвертого, пятого, восьмого элементов И, второй вход блока формирования цифр соединен с вторыми инверсными входами второго пятого элементов И и вторыми прямымй входами четвертого, восьмого элементов И, третий вход блока формирования цифр соединен с вторыми инверсными входами третьего, седьмого, элементов И, вторыми прямыми входами первого, шестого элементов И,четвер тый вход блока формирования цифр соединен с третьим инверсным входом четвертого элемента И и третьим прямым входом восьмого элемента И, пятый вход блока формирования цифр соединен с третьим инверсным входом пятого элемента И и третьим прямым входом второго элемента И, шестой вход блока формирования цифр соединен с третьим инверсным входом шестого элемента И и третьим прямым входом первого элемента И, седьмой вход блока формирования цифр соеди- нен с третьим инверсным входомседьмого элемента И и третьим прямымвходом третьего элемента И, первая группа выходов блока формирования цифр является выходами соответствующих элементов И с первого по восьмой, первый, второй, третий, четвертый входы первого элемента ИЛИ соединены соответственно .с выходами второго, третьего, шестого, седьмого элементов И, первый, второй, третий, четвертый входы второго элемента ИЛИ соединены соответственно с выходами третьего, второго, седьмого,пятого элементов И, первый, второй, третий, четвертый входы третьего элемента ИЛИ соединены соответственно с выходами пятого, шестого, четвертого, седьмого элементов И, вторая группа выходов блока формиро", вания цифр является выходами элементов ИЛИ с первого по третий.На фиг. 1 изображена структурная схема предлагаемого устройства (рассматривается случай, когда число одновременно формируемых в цикле двоичных цифр результата равно трем); на фиг.2 и 3 - функциональные схемы двух узлов элементов ИЛИ на фиг.4 - один из воз29608 тельного процесса определения трехдвоичных цифр результата по алгоритму извлечения квадратного корняс восстановлением остатка, причемэти значения зависят не только отвычитателей, на вход вычитаемого которых они поступают, но и от порядкового номера цикла определенияочередных трех двоичных цифр результата. Ниже приведены значения вычитаемых, формируемых на выходахгрупп 8-14 элементов ИЛИ для первыхтрех циклов вычислений устройства(значения вычитаемых расположеныподобно тому, как размещены соответствующие группы 8-14 элементов ИЛИ на структурной схеме устройства фиг.1).Для первого цикла1 101 001 г -- ч 0001 0101 Для второго цикла: . УУУ 01 12 31001 1101 У У У ОО 1 г 3 УУУ 101 12 З УУ У ООО 1 УУУ ИО 1 .УУУ 1001 .УУУ 1101 123 12 3 123 Для третьего цикла УУ. У 01 1 гУ У У 101 12 6 УУ У ОО 1 У У У 0001 У У ".У 010112" 6 12 6 где 71727 - три наиболее старшие двоичные цифры результата, сформированные в первом цикле вычислений устройства и хранимые к началу его второго цикла соответственно в первом, втором третьем разрядах регистра 18 результата;1 776 - три двоичные цифры результата, сформированные во втором цикле вычислений и хранимые к началу третьего цикла вычислений соответственно в четвертом, пятом и шестом разрядах регистра 18 результата.Из приведенных диаграмм видно, что группы 8-14 элементов ИЛИ фактически осуществляют присовокупление 55 к значениям определенных нулевых разрядов регистра 18 результата значений двоичных кодов. соответственно 3 11 можных вариантов функциональной схемы блока формирования цифр результата; на фиг.5 - функциональная схема 1-го разряда коммутатора,Устройство (фиг. 1) содержит первый 1, второй 2, третий 3, четвертый 4, пятый 5, шестой 6 и седьмой 7 вычитатели, группы 8-14 элементов ИЛИ,коммутатор 15,. блок 16 формирования цифр результата, регистры 17 и 18 соответственно подкоренного числа и результата, сдвигающий регистр 19, вход 20 устройства и выходы 21-27 знаковых разрядов вычитателей 1-7 соответственно.Группы 8-14 элементов ИЛИ предназначены для формирования значений вычитаемого вычитателей 1-7 при всевозможных путях развития вычислиО. У У,.У 1001 УУ У И 01 01, 001, 101, 0001, 0101, 1001 и 1101, Номера разрядов регистра 18 результата, к значениям которых осуществляется присовокупление значений указанных двоичных кодов, однозначно определяются положением единицы, хранимой в сдвигающем регистре 19 устройства (в первом цикле работы устройства эта единица находится в первом разряде сдвигающего регистра, далее она продвигается на одну позицию в каждом цикле в направлении последнего разряда регистра). На фиг.2 и 3 в качестве примера приведены фрагменты функциональных схем соответственно группы 8 элементов ИЛИ и группы 14 элементов ИЛИ (функциональные схемы других групп элементов ИЛИ устройства могут быть разра7 1129608 8 ботаны подобным образом с-учетомприведенных выше диаграмм).Блок 16 формирования цифр реэуль"тата выполняет две функции: формирует сигналы У+ У У 7 У уф уфМ 11 2 31 41 у Ьи 7 управляющие работой коммутатора, а также формирует три двоичные цифры результата Е, Е ивсоответствии с алгоритмом извлеченияквадратного корня с восстановлениемостатка. Формирование указанных упраляющих сигнапов и цифр результатаможет осуществляться в соответствиисо следующими логическими выражениями:=х х хФ 4 24 22 241 = Х Х Х 5 21 22 26ук 6 21 гэ гьгде У - управляющий сигнал, поддействием которого коммутатор 15осуществляет выборку результата,сформированного на выходе вьиитателя 7 на фиг.1;х - логическая переменная,соответствующая значению знаковогоразряда вычитателя 1 (если на выходе.вычитателя 1 сформирована отрицательная разность, то хг,= 1, впротивном случае х= О),Е,Еэ - соответственно старшая и младшая цифры результата изтрех формируемых в одном цикле вычислений двоичных цифр.На фиг.4 приведена функциональнаясхема блока 16 формирования цифррезультата, работающая в соответствии с приведенными выше логическими выражениями,С помощью коммутатора 15 осуществляется выборка в качестве очередного остатка либо значения разности одного иэ вычитателей 1-7,либо значения содержимого регистра17 подкоренного числа. Управлениеэтой выборкой производится поцдействием соответствующих сигналову+ у% уф уф у У У" и У посту 1 2 3 4 5 6 50 У :х х х ; У+ =х +х +х21 гз гч 17 21 22 2441 = х Х ХЭ 21 23 27 5 10 в 1 20 25 30 35 40 45 пающих на управляющие входы коммута. тора 15 с первой группы выходов блока 6 формирования цифр результата. На фиг.5 показана функциональная схема 1-го разряда коммутатора 15, где, капример, Р - зна-. чение разности на выходе 1-го разряда вычитателя с порядковым номером 5 на фиг.1.Устройство работает следующим образом.В исходном состоянии в регистре 17 подкоренного числа хранитсяь-разрядное двоичное число х (в принципе число х может быть как целым, гак и дробным, однако в дальнейшем для определенности будем предполагать, что оно есть правильная нормализованная двоичная дробь, причем только положительная), регистр 18 результата обнулен, в первом разряде сдвнгающего регистра 19 записана единица (разрядно ть т сдвигающего регистра может быть выбрана равной числу циклов работы устройства для извлечения квадратного корня иэ к-разрядного двоичного числа, будем считать, что число циклов работы устройства равно о /З,а следовэзельно, и т = ф 93).Во всех циклах устройство работает одинаковым образом, поэтому более подробно рассмотрим его работу только в одном, 1-м цикле (1 ( 1 с ю ) К началу 1-го цикла в регистре 18 результата сформированы 3(1-1) старших двоичных цифр результата, а в 1-м разряде сдвигакнцего регистра 19 хранится единица, По содержимому регистра 18 результата и с учетом единицы, хранимой в 1-м разряде сдвигающего регистра 19, на выходах групп 8-14 элементов ИЛИ формируются вьиитаемые, значения которых поступают на вторые входы соответствующих вычитателей 1-7, после этого все вычитатели практически начинают работать одновременно и на их выходах формируются результаты при всех воз, можных путях развития вычислительного процесса определения очередных трех двоичных цифр результата по алгоритму извлечения квадратного корня с восстановлением остатка.Очевидно, что в одном цикле определения трех двоичных цифр результата только один из этих восьми результатов может быть правильным (выбор пра-., 1101111 0,1011111 10111 111110 9 11296 випьного результата производится с. помощью управляющих сигналов У, у, У У У" 1 и У ) По истечении 3 Ф 51 6 , 1 17времени, равного примерно времени суммирования двух п-разрядных двоичных чисел, коммутатор 15 выбирает в качестве очередного остатка результат либо одного из вычитателей 1-7, либо содержимое регистра 17 под О коренного числа, который с разрешения сигнала на входе 20 устройства запи" сывается в регистр 17 со сдвигом влево на один двоичный разряд. Одновременно с выборкой коммутатором 15 од, ного из восьми результатов и записью в качестве очередного остатка в регистр 17 в блоке 16 формируются три двоичные цифры результата ,Е и Е 5, которые с разрешения того же сигнала 2 р на входе 20 устройства записываются . в разряды 1+3(1-1)Д, 12+3(1-1)Д и 3+3(1-1)3 регистра 18 результата в качестве трех очередных цифр результата ф+5 (1-11.3, Ч г+З(1-1 Ц и 25 139.(1-1)1 (номера разрядов регистра 18, в которые должны быть запи,саны три очередных цифры результата однозначно определяет единица в1-м разряде сдвигающего регистра 19). З) Параллельно с записью очередного бстатка и очередных цифр результата в регистры соответственно 17 и 18 вПервый циклопределения цифр результата(О, 0,1) 08 10регистре 19 осуществляется сдвигединицы в (1+1)-йего разряд (этовозможно, так как предполагается,что в устройстве используются синхронные двухтактные триггеры). Наэтом 1-й цикл работы устройствапо определению очередных трехдвоичных цифр результата заканчивается,После выполнения в/3 циклов врегистре 18 будет сформирован о -разрядный двоичный.код результата У,Выдвигаемая в (ь/3)-м цикле работыустройства единица из последнегоразряда сдвигающего регистра 19 указывает на окончание операции. Разумеется, что число циклов работыустройства может быть определеннымобразом увеличено, если этого потребует точность вычисления.Рассмотрим пример, более детальнопоясняющий принцип работы и структурные особенности устройства. Пустьн = 6 и х= 0,100111 (результатдолжен быть равен 0,110001). Нижеприведено пространственно-числовоеизображение процесса извлеченияквадратного корня из числа Х впредлагаемом устройстве. В нем вычисления расположены подобно тому,как размещены вычитатели 1-7 наструктурной схеме устройства нафиг. 1.11 11Аналогично может быть разработано устройство для извлечения квадратного корня иэ двоичного числа, в каждом цикле которого формируется . две или больше чем три двоичные цифры результата. Однако с увеличением числа 1 одновременно формируемых в цикле двоичных цифр результата резко возрастает объем используемого в устройстве оборудования. Так, например, уже при К = 5 в устрой 29608 12 стве необходимо использовать тридцать один вычитатель и тридцать одинузел элементов ИЛИ, Кроме того, несколько усложняется коммутатор и5 узел формирования цифр результата,Поэтому представляют практическийинтерес, по-видимому, устройствадля извлечения квадратного корня,формирующие в одном цикле не более шести двоичных цифр результата,1129608а 1 са О Ц гт О аиа УуирДю ХяМа Мм 4 ф Дг47 иФ фУ Ур гг и Щ. Заказ 9698 Подаиса , 3 п нал ППП "Патемт", Уагород, ул. Прое