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

ц 1015380 СОЮЗ СОВЕТСНИХПВЗМЛНТЮЕЮИРЕСПУБЛИН 6 Г 7/55 ПИСАНИЕ ИЭОБРЕТЕНИ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 3Ю ГОСУДАРСТВЕННЬ 1 Й НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И (ЛНРЫТИЙ(21) 336092 Р 18.-24(53) 681325 (088.8)56) 1, Авторское свидетельство СССРУ 661550, кл. 6 06 Г 7/552, 19792,;Лебедев И. В. идр. Метод из,влечения квадратного корня в цифровой вычислительной .машине, Сб"Вопросы вычислительной математики и вычислительной техники". Под ред. Л. А. Люстерника, "ИАШГИЗ"1963, с. 75-178(прототип) .(54)(57)АУСТРОйСТВО ДЛЯ ВЦЧИСЛКНИЯ КВАДРАТНОГО КОРНЯ, содержащее рЕгистры подкоренного числа и результата, . регистр сдвига, сумматор, причем первый вход первого сумматора соедич нен с выходом регйстра,подкоренного числа, о т л и ч а ю щ е е с я тем, что, с целью .повышения быстродействия, .в него введены сумматоры, вычитатели, группа элементов И-ИЛИ, группы элементов ИЛИ, блок формирования цифр результата и коммутатор, причем пер вый выход первого сумматора соединен с первыми входами второго сумматора и первого вычитателя, первый выход второго сумматора соединен с первыьм входами третьего сумматора и второго вычитателя, первый выход первого вычитателя соединен с первыми входами четвертого сумматора и третьего вычитателя, первые выходы третьего и четвертого сумматоров, второго и третьего вычитателей соединены с информационными входами коммутатора,выход которого соединен с входом ре-. гистра подкоренного числа, первый входы группы элементов И-ИЛИ и первой, второй, третьей, четвертой, пятой и шестой групп элементов ИЛЙ соединены с выходом регистра результата, а вторые входы соединены с выходом регистра сдвига, выход группы элементов И-ИЛИ .соединен с вторым входом первого сумматора, выходы первой, второй, третьей, четвертой, пятой и вестой групп элементов ИЛИ соединены с вторыми входами соответственно второго, третьего и четвертого сумматоров и первого, второго и третьего вычитателей, выход знакового разряда регистра подкоренного числа соединен с четвертым входом группыэлемен.тов И-ИЛИ. и третьим входом первого сумматора, вторые выходы первого, второго, третьего и четвертогосуммато"ров и первого, второго. и третьего вычитателей.соединены с первым, вто- вава рым, третьим, четвертым, пятым, шес 4 тым и седьмым входами блока формиро- рава вания цифр результата, первый, вто(д рой и третий выходы которого соединены с первым, вторым и третьим упра- р вляющими входами регистра результата, а четвертый, пятый,вестой и седьмой выходы блока формирования цифр результата соединены с первым, вторым, третьим и четвертым управляющими входами коммутатора, четвертый управляющий вход регистра результата соединен с выходом регистра сдвига, информационные входы регистров подкоренногочисле, результата, сдвига соединены с информационным входом устройства.2. Устройство по и, 1, о т л и ч а ю щ е е с я тем, что в нем блок Формирования цифр результата содержит элементы И, элемент ИЛИ, элемент чИ-ИЛИ.,причем первые прямые входы первого, второго и первые инверсные входы третьего и четвертого элементов И соединены с первым входом блока формирования цифр результата, второй прямой вход. первого и второй инверсный вход второго элемента И соединены с вторым входом блока формирования цифр результата, второй прямой вход третьего элемента И и второй инверсный вход четвертого элемента И соединены с третьим входом блока формирования цифр результата, первый вход блока Формирования цифр результата соединен с его первым выходом, первый вход элемента ИЛИ. соединен с выходом второго элемента И,1015380второй вход элемента ИЛИ соединен свыходом четвертого элемента И, выходэлемента ИЛИ является вторым выходом блока формирования цифр результата, выходы первого, второго,третьего и четвертого элементов И соединены соответственно с первым, вторым, третьим, четвертым входами элемента 1 И-ИЛИ , пятый, шестой, седьмой,)восьмой входы которого соединены соответственно с четвертым, пятым, шестым и седьмым входами блока формирования цифр результата, выход элемента ЙИ-ИЛИ является третьим выходом блока формирования цифр результата, выходы первого, третьего, второго и четвертого элемен тов И являются соответственночетвертым, пятым, шестйм и седьмым выходами блока формированияцифр результата.Изобретение относится к вычислительной технике и может быть использовано в универсальных и специализированных арифметических устройствах для быстрого вычисления квадратного корня из двоичного числа,Известно устройство для вычисле ния квадратного корня, выполненное в виде матрицы из и строк и е столбцов 1, 10Основным недостатком данного устройства является его низкая эффективность, особенно при больших значениях и, так как увеличение быстродействия достигается за счет значительного увеличения количества используемого оборудования,Наиболее близким по технической сущности к предлагаемому являетсяустройство для вычисления квадратного 20 корня, содержащее регистры подкоренного числа и результата, сдвигающий регистр, сумматор-.вычитатель, две группы вентилей коррекции, причем первый и второй входы сумматора-вычи тателя соединены с выходами регистров соответственно подкоренногочисла и результата, а выход соединен с входом регистра подкоренногочисла, выход сдвигающего регистра со- З 0 единен соответствующим образом черезпервую и вторую группы вентилей коррекции с входами регистра результата,выход знакового разряда регистра подкоренного числа соединен с управляющим входом сумматора-вычитателя, управляющиЬ входы регистров подкоренного числа и результата, а такжесдвигающего регистра соединены с входами устройства, 8 данном устройстве реализован алгоритм вычисленияквадратного корня без восстановления остатка 2 3Недостатком известного устройства является низкое быстродействие,вызванное в первую очередь формирова нием в каждом цикле его работы только одной двоичной цифры результата.Цель изобретения - повышение быстродействия устройства дпя вычисления квадратного корня путем одновременного Формирования в .цикле нескольких двоичных цифр результата.Поставленная цель достигаетсятем, что в устройство дпя вычисленияквадратного корня, содержащее регистрподкоренного числа и результата, регистр сдвига, сумматор, причем первый вход первого сумматора соединен свыходом регистра подкоренного числа,,элементов И-ИЛИ, группы элементовИЛИ, Ьлок формирования цифр результа"та и коммутатор, причем первый выход первого сумматора соединен с пер 3выми входами второго сумматора ипервого вычитателя, первый выход второго сумматора соединен с первымивходами третьего сумматора и второго вычитателя, первый выход первоговычитателя соединен с первыми входами четвертого сумматора и третьего вычитателя, первые выходы третьего:ичетвертого сумматоров, второго и третьего вычитателей соединены с информационными входами коммутатора,выход которого соединен с входом регистра подкоренного числа, первые входы группы элементов И-ИЛИ и первой,второй, третьей, четвертой, пятойи шестой групп элементов ИЛИ соединены с выходом регистра результата,а вторые входы соединены с выходомрегистра сдвига, выход группы элементов И-ИЛИ соединен с вторым вхо 23дом первого сумматора, выходы первой,второй, третьей, четвертой, пятой ишестой групп элементов ИЛИ соединеныс вторыми входами соответственно второго, третьего, четвертого сумматоров и первого, второго и третьего вычитаталей; выход знакового разрядарегистра подкоренного числа соединен. с третьим входом группы элементов ИИЛИ.и третьим входом первого сумматора, вторые выходы пе)свого, второго,третьего и четвертого сумматоров ипервого, второго и третьего вычитателей соединены с первым, вторым, третьим, четвертым, пятым, шестым иседьмым входами блока Формирования, цифр результата, первый, второй итретий выходы которого соединены спервым, вторым и третьим управляющимивходами регистра результата, а четвертый, пятый, шестой и седьмой фвыходы, блока формирования цифр результата соединены с первым, вторым,третьим и четвертым управляющимивходами коммутатора, четвертый управляющий вход регистра результата ффсоединен с выходом регистра сдвига, информационные входы регистровподкоренного числа, результата, сдвига соединены с информационным входомустройства.ЯБлок Формирования цифр результатасодержит элементы И, элемент ИЛИ, элемент 4 И-ИЛИ, причем первые прямые 380 4входы первого, второго и первые инверсные входы третьего и четрертого элементов И соединены с первым входом блока формирования цифр результата, второй прямой вход первого и второй инверсный вход второго элемента И соединены с вторым входом блока формирования цифр результата, второй прямой вход третьего элемента И и второй инверсный вход четвертого элемента И соединены с третьим входом Ьлока формирования цифр результата, первый вход Ьлока формирования ,циФр результата соединен с его пер,вым выходом, первый вход элемента ИЛИ соединен с выходом второго элемента И, второй вход элемента ИЛИ соединен с выходом четвертого элементаИ, выход элемента ИЛИ является вторымвыходом блока формирования цифр результата, выходы первого, второго,третьего и четвертого элементов И соединены соответственно с первым, вторым, третьим и четвертым входамиэлемента 4 И-ИЛИ, пятый, шестой,седьмой, восьмой входы которого соединены соответственно с четвертым, пятым, шестым и седьмым входами блока формирования цифр результата, выход элемента 4 И-ИЛИ является третьим входом блока формирования цифррезультата, выходы первого, третьего, второго и четвертого элементов И являются соответственно четвертым, гятым, шестым и седьмым выходамиблока формирования цифр результата,На фиг. 1 изображена структурнаясхема предлагаемого устройства длявычисления квадратного корня рассмат.- ривается случай, когда число одновременно формируемых двоичных цифр ре-. зультата К равно трем); на Фиг. 2 показан для этого же случая один из возможных вариантов функциональной схемы блока Формирования цифр результата; на Фиг. 3 -функциональная схема-го разряда коммутатора;.на Фиг, 4 и 5 г функциональные схемы группы элементов И-ИЛИ и одной группы элементов ИЛИ,Устройство для вычисления квадратного корня содержит (фиг.1) регистры 1 и 2 соответственно подкоренного числа и результаты, регистр 3 сдвига, первый 4, второй 5, третий б и четвертый 7 сумматоры, первый 8, второй 9 и третий 10 еычитатели, группу 11 элементов И-ИЛИ, первую 12,вторую 13, третью 14, четвертую 15, пятую 16 и шестую 17 группы элемен10153тов ИЛИ, коммутатор .18, блок 19 формирования цифр результата и вход 20устройства,Выходы 1-28 являются выходамизнаковых разрядов. регистра подко-ренного числа, сумматоров и вычитателей, выход 29 - блока формирования цифр результата,Блок формирования цифр результата (фиг.2) содержит элементы И 30, 10элемент ИЛИ 31, элемент 4 И-ИЛИ 32,Схема 1- го разряда коммутатора(фиг. 3) содержит элементы И 33,элемент ИЛИ 34.Группа элементов И-ИЛИ (фиг. 4) содержит элементы И 35,элементы ИЛИ 36.Группа элементов ИЛИ (фиг.5) содержит элементы ИЛИ 37,Блок 19 формирования цифр результата выполняет две функции; 20Во-первых, формирует сигналы, управляющие работой коммутатора 18,Во-вторых, формирует три двоичные цифры результата в соответствиис алгоритмом вычисления квадратного корня без восстановления остатка, формирование сигналов у+, у,у, у управляющих работой коммутатора 1 Ь, а также формирование цифр.результата Гэ, Г 2, 1 осуществляет- Звся в узле 19 в соответствии. со следующими логическими выражениями:(0 22 26 ЭЗ1 22 Ф 2 9 10 3 6 2 Фф 2-1+"ох 28Зсь, например, через уфоЬозначенуправляющий сигнал, под действиемкоторого коммутатор. 18 осуществляет выборку результата, сформированного на выходе сумматора с порядковым номером 7 на фиг. 1, х.1 обозР 43начает логическую переменную,соответствующую значению знакового разрядарегистра 1 подкоренного числа 1,ес-,ли в регистре 1 хранится.отрицательное число, то х, 1, в противном случае х =О), Г, Е соответЮственно младшая и старшая двоичная цифра результата из трех формируемых в одном цикле цифр.На Фиг, 2 приведена функциональная схема узла 19 Формирования цифр ффрезультата, раЬотающая в соответствиис приведенными выше логическими выражениями,80 6На фиг. 3 показана функциональная схема 1 -го разряда коммутатора 18, где,например, К " обозначает значение разности на выходе 1.го разряда вычитателя с порядковым номером 9 на фиг. 1. Если же в устройстве используются сумматоры Ьез распространения переносов, то 1 -й разряд коммутатора 18 должен включать две такие схемы.Группы 12-17 элементов ИЛИ содержат в определенных разрядах элементы ИЛИ (по. одному элементу на раз . ряд), Группы же элементов И-ИЛИ содержат в определенных разрядах элемент ИЛИ или элементы И и ИЛИ.На фиг, 4 показана Функциональная схема группы 11 элементов И-ИЛИ, на фиг, 5 - функциональная схема группы 13 элементов ИЛИ (другие группы элементов ИЛИ строятся подобным образом).Устройство для вычисления квадратного корня раЬотает следующим .образом.В исходном состоянии в регистре 1 хранится и-разрядное число х (для определенности Ьудем предполагать, что подкоренное число М есть правиль.- ная нормализованная дроЬь, причем только положительная), регистр 2 ре" зультата обнулен, в первом разряде сдвигающего регистра 3 записана еди; ница разрядность сдвигающего регистра 3 может Ьыть выбрана равной числу циклов раЬоты устройства для вычисления квадратного корня из и-разрядного двоичного числа, Ьудем считать, что число циклов работы устройства равно и/3, а следовательно и в=п/3).В первом цикле раЬоты устройства сумматор 4, управляемый сигналом х =О, работает как вычитатель. Так как регистр 2 результата обнулен, то результаты, формируемые на выходах группы 11 элементов И-ИЛИ и групп 12-17 элементов,ИЛИ определяются только информацией, которую вводит соответствующим образом в эти группы в соответствии с алгоритмом вычисления квадратного корня без восстанов" ления остатка единица, хранимая в первом разрядесдвигающего регистра 3, Ниже приведены эти результаты на выходах групп 11-17 (результаты расположены подобно тому, как разме-, щены группы 11-17 на структурной схеме устройства фиг. 1)Сумматор 4, а также сумматоры 5"7 и вычитатели 8-10 практически начинают работать одйовременно. С их помощью на выходах сУмматоров 6 и 7 вычитатев лей 9 и 10 Формируются результаты при. всех возможных путях развитйя вычи тательного процесса определения трех наиболее старших двоичных циФр результата у.,у 2, у по алгоритму вычис 13 ,ления квадратного корня без восстанов.ления остатка. Очевидно, что в сдном цикле определения трех двоичных цифр, результата только один из этих четы- рек результатов может быть правиль- ЗВ ный выбор правильного результата. осуществляется, с помощью управля ющих сигналов у р:у ту у 9 у,)По ис течении времени, равного прймерно времени суммирования двух и-раэряд- фф ных двоичных чисел, коммутатор 18 вы-бирает в качестве первого остатка результат либо одного иэ сумматоров 6. и 7, либо одного из вычитателей 9 и 10, который .с разрешениясигйала на .ЗФ входе 20 устройства записывается в ре,гистр 1 со сдвигом влево на один дво;- ичный разряд. Здесь можно отметить,что при .записи в регистр 1 очередного остатка щ сдвигом его влево на . ЗЭ ,один двоичный разряд возможно .искажение знака остатка. Поэтому в регистре 1 результата необходимо предусмотреть кроме и основных разрядов два дополнительных знаковых раэря- фв :да (один из этих дополнигельных разрядов и будет хранить,истйнное значение знака очередного остатка). Одно- . временно с выборкой коммутатором 18 одного из четырех результатов на вы ходах сумматоров б и 7 и вычитатева режим работы сумматора 4 зависит(если х =О) (если х=1) О О,М 1101 в трет ра 3 з яде сДвигающегединица. и В остальном работ ром цикле аналоги ства в первом цикл выполнения в реги второй остаток, в руется результат м ра исаи устроистна работее. В резултр 1 запирегистреф у 1 У 2 ЪУ а во вто- устройьтате егор ываетсяформиууу.р0 Послгистреный двои 0,01.1 0,101 0,0011 0,0101 0,1011 0,1101 . з лей 9 и 10,и записью его в качестве очередного остатка в регистр 1,в Ьлоке 19 формируются три двоичные цифры результата Г С 2 3 Фкоторые записываются с разрешенйясигнала на входе 20 устройства в тринаиболее старшие разряды регистра 2в качестве трех наиболее старшихцифр результата. ), У. У . (номераразрядов регистра 2, в которые должны быть записаны три очередных цифрырезультата, однозначно определяет единица в регистре 3). Одновременно с записью трех цифр результата в регистр 2, в регистре 5 осуществляется сдвиг единицы во второй разряд(это возможно, так как предполагается, что используются в устройстве синхронные двухтактные триггеры). Во втором цикле работы устройст-. от знака первого остатка, хранимого в регистре 1 подкоренного числа (если этот. остаток положительный, . то сумматор 4 работает как вычитатель, в противном случае как сумматор). Результаты, формируемые во втором цикле на выходах группы 11. элементов И-ИНИ и групп 12-17 элементов ИНИ определяются не толькоинформацией, которую вводит соответствующим образом в эти группы в соЬтветствии с алгоритмом вычисленияквадратного корня без восстановления остатка единица, хранимая вовтором разряде сдвигающего регистра 3, но и информацией .регистра 2результата (результат на выходегруппы 11 элементов И-ИЛИ зависит ещеи от значения знакового разрядарегистра 1 подкоренного числа)Подобно тому как делалось ранее, нижеприведены эти результаты на выходахгрупп 11-17.01 у у у 01 выполнения и/3 циклов в реЬудет сформирован и-разрядный код результата. Выдвигаемая в (и/3)-м цикле работы устройства единица из последнего разряда сдвигающего регистра 3 указываетна окончание операции. Разумеется,101538010что число циклов работы устройстваможет Ьыть определенным оЬразом увеличено, если этого потреЬует точность вычисление.1015380 Яподн рмр.вМ ,. региетро 8 еРю рю яреМ ревиетрф И Я И 7-0 И 9-и ректор С,Шекмар. Власенко едак аж 70 б Подмого комитета СССРний и открытийРаушская наб. д. В/5 Тир ВНИИПИ Государствен по делам изобрет 3035, Москва, Ж, Заказ 3217 Проектн горо И 8.й ИИ Х.й Филиал ППП "Патент". Составитель Г. ЛопатТехред С.Мигунова ЮмФми,мФаФуеиееюреЯ