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

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее регистры подкоренного числа и результата, регистр сдвига, сумматор, причем первый вход первого сумматора соедип : нен с выходом регистра.подкоренного Числа, отличающееся тем, что, с целью повышения быстродействия, .в него введены сумматоры, вычитатели, группа элементов И-ИЛИ, группы элементЬв ИЛИ, блок формирования цифр результата и KOMMytaTop, причем первый выход первого сумматора соединен с первыми входами Второго сумматора и первого вычитателя,пе:рвый выход второго сумматора соединен с первыми входами третьего сумматора и второго вычитателя, первый выход первого вычитателя соединён с первыми входами четвертого сумматора и третьего вычитателя, первые выходы третьего и четвертого сумматоров, второго и третьего вычиtaтeлeй соединены с информационными входами коммутатора. выход которого соединен с входом ре гистра подкоренного чйсла, первые входы группы элементов И-ИЛИ- и первой , второй, третьей, четвертой, пятой и шестой групп элементов ИЛИ соединены с выходом регистра результата, а вторые входы соединены с выходом регистра сдвига, группы элементов И-ИЛИ соединен с вторым входом первого сумматора, выходы первой, второй, третьей, четвертой, пятой и шестой групп элементов ИЛИ соединены с вторыми входами соответственно второго, третьего и четвертого сумматоров и первого, второго и третьего вычитателей, выход знакового разря§ да регистра подкоренного адсла соединен с четвертым входом группы элементов И-ИЛИ и третьим входом первого сумматора, вторые выходы п1ервого, второго , третьего и четвертого суммато ров и первого, второго и третьего вычитателей соединены с первым, вторым , третьим,, четвертым, пятым, тым и седьмым входами блока формирования цифр результата, первый, ВТО- t СП рой и третий выходы которого соедисо нены с первым, вт(ым и третьим упра00 вляющими входами регистра результата , а четвертый,пятый,шестой и седьмой выходы блока формирования цифр результата соединены с первым,вторым третьим и четвертым управляющими входа «1 кон мутатора , четвертый управляющий вход регистра результата соединен с выходом регистра сдвига, информационные входы регистров подкоренного числа , результата, сдвига соединены с информационным входом устройства .

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

Йз

РЕСПУБЛИН

3f50 С, 06 F 7Л52

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

4-i

ОПИСАНИЕ ИЗОБРЕТЕНИЙ ::::::: —:::::::-;:.::3

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3360925/18.-24 (22) 08. 12.81 (46) 30.04.83. М. Ю 16 (72) Г. П. Лопато и Я. А. Шостак (71) Минский радиотехнический инсти- тут (53) 681..325 (088.8) (56) 1. Авторское свидетельство СССР

N 661550, кл. G 06 F 7/552, 1979 °

2..Лебедев И. В. и др. Метод из,влечения квадратного корня в цифровой вычислительной .машине. Сб.."Вопросы вычислительной математики и вычислительной техники". Под ред. Л. А. Люстерника, "ИАШГИЗ",,1963, с. 175-178 (прототип) . (54)(57)аЬСТРОИСТВО ДЛЯ ВЫЧИСЛКНИЯ

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

nepsoro сумматора, выходы первой, второй, третьей, четвертой, пятой и вестой групп элементов ИЛИ соединены с вторыми входами соответственно второго, третьего и четвертого сумматоров и первого, второго и третьего вычитателей, выход знакового разря- Я . да регистра подкоренного числа соединен с четвертым входом группы элемен.тов И-ИЛИ. и третьим входом первого сумматора, вторые выходы первого, второго, третьего и четвертогосуммато"ров и первого, второго. и третьего

ВЫЧИтатЕЛЕй .СОВДИНЕНЫ С ПЕРВЫМ, ВтО- МиеЬ рым, третьим, четвертым, пятым, вес 4 тым и седьиым входами блока формиро- вечеа вания цифр результата, первый, вто ф11 рой и третий выходы которого соединены с первым, вторым и третьим управляющими.входами регистра резул тата, а четвертыи,пятый,шестой и седьмой выходы блока формирования цифр результата соединены с первым, вторым,третьии и четвертым управляющиии входами коммутатора, четвертый управляющий вход регистра результата соединен с выходом регистра сдвига, информационные входы регистров- подкоренногочисле, результата, сдвига соединены с информационным входом устройства.

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

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

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

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

Наиболее близким по технической сущности K предлагаемому является устройство для вычисления квадратного 20 корня, содержащее регистры подкоренного числа и результата, сдвигающий регистр, сумматор-.вычитатель, две группы вентилей коррекции, причем первый и второй входы сумматора-вычи- 25 тателя соединены с выходами регистров соответственно подкоренного числа и результата, а выход соединен с входом регистра подкоренного числа, выход сдвигающего регистра со- З0 единен соответствующим образом через первую и вторую группы вентилей коррекции с входами регистра результата, выход знакового разряда регистра подкоренного числа соединен с управляюВ щим входом сумматора-вычитателя, управляющиЬ входы регистров подкоренного числа и результата, а также сдвигающего регистра соединены с входами устройства, 8 данном устройстве реализован алгоритм вычисления квадратного корня без восстановления остатка 2 .1.

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

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

Поставленная цель достигается тем, что в устройство дпя вычисления квадратного корня, содержащее регистр подкоренного числа и результата, регистр сдвига, сумматор, причем первый вход первого сумматора соединен с выходом регистра подкоренного числа, 3 1015 введены сумматоры, вычитатели, группа ,элементов И-ИЛИ, группы элементов

ИЛИ, Ьлок формирования цифр результа" та и коммутатор, причем первый выход первого сумматора соединен с пер3 выми входами второго сумматора и первого вычитателя, первый выход второго сумматора соединен с первыми входами третьего сумматора и второго вычитателя, первый выход первого вычитателя соединен с первыми входами четвертого сумматора и третьего вычитателя, первые выходы третьего:и четвертого сумматоров, второго и третьего вычитателей соединены с информационными ° входами коммутатора, выход которого соединен с входом регистра подкоренного числа, первые входы группы элементов И-ИЛИ и первой, второй, третьей, четвертой, пятой и шестой групп элементов ИЛИ соединены с выходом регистра результата, а вторые входы соединены с выходом регистра сдвига, выход группь элементов И-ИЛИ соединен с вторым вхо25 дом первого сумматора, выходы первой, второй, третьей, четвертой, пятой и шестой групп элементов ИЛИ соединены с вторыми входами cooTBGTOTBGHHQ BToрого, третьего, четвертого сумматоров и первого, второго и третьего вычитаталей; выход знакового разряда регистра подкоренного числа соединен . с третьим входом группы элементов ИИЛИ.и третьим входом первого сумматора, вторые выходы первого, второго, третьего и четвертого сумматоров и первого, второго и третьего вычитателей соединены с первым,. вторым, третьим, четвертым, пятым, шестым и седьмым входами блока формирования, цифр результата, первый, второй и третий выходы которого соединены с первым, вторым и третьим управляющими входами регистра результата, а четвертый, пятый, шестой и седьмой выходы .блока формирования цифр результата соединены с первым, вторым, третьим и четвертым управляющими входами коммутатора, четвертый управляющий вход регистра результата соединен с выходом регистра сдвига, информационные входы регистров подкоренного числа, результата, сдвига соединены с информационным входом устройства.

Ы

Блок формирования цифр результата содержит элементы И, элемент ИЛИ, элемент 4И-ИЛИ, причем первые прямые

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

ИЛИ соединен с выходом второго элемента И, второй вход элемента ИЛИ соединен с выходом четвертого элемента

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

На фиг. 1 изображена структурная схема предлагаемого устройства для вычисления квадратного корня (рассмат.ривается случай, когда число одновременно формируемых двоичных цифр ре-. зультата К равно трем); на фиг. 2 показан для этого же случая один из возможных вариантов функциональной схемы блока формирования цифр результата; на фиг. 3 -функциональная схема -ro разряда коммутатора;.на фиг. 4 и 5 r функциональные схемы группы элементов

И-ИЛИ и одной группы элементов ИЛИ.

Устройство для вычисления квадратного корня содержит (фиг.1) регистры 1 и 2 соответственно подкоренного числа и результаты, регистр

3 сдвига, первый 4, второй 5, третий б и четвертый сумматоры, первый 8, второй 9 и третий 10 вычитатели, группу 11 элементов И-ИЛИ, первую 12, вторую 13, третью 14 четвертую 15, пятую 16 и шестую 17 группы элемен10153 тов ИЛИ, коммутатор .18, блок 19 формирования цифр результата и вход 20 устройства.

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

Блок формирования цифр результата (фиг.2) содержит элементы И 30, 10 элемент ИЛИ 31, элемент 4И-ИЛИ 32.

Схема i- го разряда коммутатора (Фиг. 3) содержит элементы И 33, элемент ИЛИ 34.

Группа элементов И-ИЛИ (фиг. 4) содер- 13 жит элементы И 35, элементы ИЛИ 36.

Группа элементов ИЛИ (фиг.5) со- держит элементы ИЛИ 37.

Блок 19 формирования цифр результата выполняет две функции; 20

Во-первых, формирует сигналы, управляющие работой коммутатора 18, Во-вторых, формирует три двоичные цифры результата в соответствии с алгоритмом вычисления квадрат- 15 ного корня без восстановления остатка. Формирование сигналов у», у, у, у„ управляющих работой коммутатора 1Ь, а также формирование цифр результата f >, f2, f осуществляет- З0 ся в узле 19 в соответствии. со следующими логическими выражениями: =х x; >» =x х

6 22 23 7 22 2Ь 9 22 2Э

У" =х х ( 0 22 26 ЭЗ

"э З "6М

9 21 qo 28

30ecb, например, через y% обозначе управляющий сигнал, под действием которого коммутатор. 18 осуществляет выборку результата, сформированного на выходе сумматора с порядковым номером / на фиг. 1, х обоз/ 43 начает логическую переменную,соответствующую значению знакового разряда регистра l подкоренного числа 1,ес-. ,,ли в регистре l хранится.отрицательное число, то х „ 1, в противном случае х =О), Г, Е.< соответ$0 ственно младшая и старшая двоичная цифра результата из трех формируемых в одном цикле цифр.

На фиг.. 2 приведена функциональная схема узла 19 Формирования цифр результата, раЬотающая в соответствии с приведенными выше логическими выражениями, 80

На фиг. 3 показана функциональ« ная схема i -ro разряда коммутатора

18, где,например, К " обозначает значение разности на выходе 1-го разряда вычитателя с порядковым номером

9 на фиг. t. Если же в устройстве используются сумматоры Ьез распространения переносов, то 1 -й разряд коммутатора 18 должен включать две такие схемы.

Группы 12-17 элементов ИЛИ содержат в определенных разрядах элементы ИЛИ (по. одному элементу на раз ряд), Группы же элементов И-ИЛИ содержат в определенных разрядах элемент ИЛИ или элементы И и ИЛИ.

На фиг. 4 показана функциональная схема группы 11 элементов И-ИЛИ, на фиг. 5 - функциональная схема группы 13 элементов ИЛИ (другие группы элементов ИЛИ строятся подобным образом).

Устройство для вычисления квадратного корня раЬотает следующим .образом.

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

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

m=n/3).

В первом цикле раЬоты устройства сумматор 4, управляемый сигналом х „=О, работает как вычитатель. Так как регистр 2 результата обнулен, то результаты, формируемые на выходах группы 11 элементов И-ИЛИ и групп

12-17 элементов.ИЛИ определяются только информацией, которую вводит соответствующим образом в эти группы в соответствии с алгоритмом вычисления квадратного корня без восстановления остатка единица, хранимая в первом разряде сдвигающего регистра 3, Ниже приведены эти результаты на выходах групп 11-17 (результаты расположены подобно тому, как разме-, щены группы 11-17 на структурной схеме устройства фиг. 1) 1015380 8

0,01 (если х „"=О) (если х =1) O i 3 М f ООИ

0,У„ М 00<1 од 2 э.ии

11 01

0,01.1 0,101

1 —

0 0101 0 1011 О, 1101 . э Сумматор 4, а также сумматоры 5-7 и вычитатели 8-10 практически начинают работать одйовременно. С их помощью на выходах сумматоров 6 и 7 вычитате-! в лей 9 и 10 формируются результаты при всех возможных путях развитйя вычи тательного процесса определения трех наиболее- старших двоичных цифр результата у.,y>, y> no алгоритму вычис1$ ,ления квадратного корня без восстанов.ления остатка. Очевидно, что в сдном цикле определения трех двоичных цифр. результата только один из этих четы- рех результатов может быть правильный (выбор правильного результата осуществляется-, с помощью управляющих сигналов У :У, у9.. У 1О). По истечении времени, равного прймерно времени суммирования двух и-разрядных двоичных чисел, коммутатор 18 вы- бирает в качестве первого остатка ре- . зультат либо одного иэ сумматоров 6. и 7, либо одного из вычитателей 9 и

10, который .с разрешения сигйала на .ЗЕ входе 20 устройства записывается в ре, гистр 1 со сдвигом влево на один дво».-,, ичный разряд. Здесь можно отметить, 4То при .записи в регистр 1 очередного остатка щ сдвигом его влево на . М ,один двоичный разряд возможно .иска:жение знака остатка. Поэтому в регистре 1 результата необходимо предусмотреть кроме и основных разрядов два дополнительных знаковых раэря- Е

:да (один из этих дополнигельных разрядов и будет хранить,.истинное значеwe знака очередного остатка). Одно- . . временно с выборкой коммутатором 18 одного из четырех результатов на вы- 4з ходах сумматоров б и 7 и вычитатеВ остальном работа устройства во втором цикле аналогична работе устройства в первом цикле. В результате его выполнения в регистр 1 записывается второй остаток, в регистре 2 формируется результат О, у у у у у у, .. Я, лей 9 и 10.и записью его в качестве очередного остатка в регистр 1, в блоке 19 формируются три двоичные цифры результата f„, f, Г которые записываются с разрешенйя сигнала на входе 20 устройства в три наиболее старшие разряды регистра 2 в качестве трех наиболее старших цифр результата у, уь. у . (номера разрядов регистра 2, в которые должны быть записаны три очередных цифры результата, однозначно определяет единица в регистре 3). Одновременно с записью трех цифр результата в регистр 2, в регистре 5 осуществляется сдвиг единицы во второй разряд (это возможно, так как предполагается, что используются в устройстве синхронные двухтактные триггеры).

Во втором цикле работы устройства режим работы сумматора 4 зависит от знака первого остатка, хранимого в регистре 1 подкоренного числа (если этот. остаток положительный, . то сумматор 4 работает как вычитатель, в противном случае как суммаtop). Результаты, формируемые во втором цикле на выходах группы 11. элементов И=ИЛИ и групп 12-17 злементов ИНИ определяются не только информацией, которую вводит соответствующим образом в эти группы в соответствии с алгоритмом вычисления квадратного корня без восстановления остатка единица, хранимая во втором разряде сдвигающего регистра 3, но и информацией .регистра 2 результата (результат на выходе группы 11 элементов И-ИЛИ зависит еще и от значения знакового разряда регистра 1 подкоренного числа). Подобно тому как делалось ранее, ниже приведены эти результаты на выходах групп 11-17.

„ 0 1yi уа у 01 илй-Оууу И а в третьем разряде сдвигающего регистра 3 записана единица.

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

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

1015380

1015380

И 8-й ИИ S-й

bimah pr ярма/ ргсжюю 2

Составитель Г. Лопато

Техред С.йигунова Корректор С.Шекмар

Редактор А. Власенко

Тираж 70б Подвесное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Иосква, Ж-35, Раушская наб., д. 4/5

Заказ 3217/46

Филиал ППП "Патент"., г. Ужгород, ул. Проектная, 4 РтРадэВ Региетро g

И 2-ФИ И Я И 7-й Иf-и Я-и и 8sngN .

-й pnzpwuiwf ,т pteuewyatЯ