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

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в устройство для вычисления квадратного корня, содержащее регистр подкоренного числа и результата, регистр сдвига, сумматор, причем первый вход первого сумматора соединен с выходом регистра подкоренного числа. 31 введены сумматоры, вычитатели, групп элементов И-ИЛИ, группы элементов ИЛИ, блок формирования цифр результа та и коммутатор, причем первый выход первого сумматора соединен с пер выми входами .второго сумматора и первого вычитателя, первый выход вто рого сумматора соединен с первыми входами третьего сумматора и второго вычитателя, первый выход первого вычитателя соединен с первыми входами четвертого сумматора и третьего в читателя, первые выходы третьего и четвертрго сумматоров, второго и тре тьего вычитателей соединены с инфор мационными-входами коммутатора, выход которого соединен с входом регистра подкоренного числа, первые вх ды группы элементов И-ИЛИ и первой, второй, третьей, четвертой, пятой и шестой групп элементов ИЛИ соединены с выходом регистра результата, а вторые входы соединены с выходом регистра сдвига, выход группу элемен тов И-ИЛИ соединен с вторым эхо- , дом первого сумматора, выходы первой второй, третьей, четвертой, пятой и шестой групп элементов ИЛИ соединены с вторыми входами соответственно вто рого, третьего, четвертого сумматоров и первого, второго и третьего вы читателей; выход знакового разряда регистра подкоренного числа соединен .с третьим входом группы элементов ИИЛИ и третьим входом первого суммато ра, вторые выходьл , второго, третьего и четвертого сумматоров и первого, второго и третьего вычитате лей соединены с первым, вторым, третьим, четвертым, пятым, шестым и седьмым входами блока формирования .цифр результата, первый, второй и третий выходы которого соединены с первым, вторым.и третьим управляющим входами регистра результата, а четВЫХОДЫ .блока формирования цифр результата соединены с первым, вторым, третьим и.четвертым управляющими вxoдa и коммутатора, четвертый управляющий вход регистра результата соединен с выходом регистра сдвига, информационные входы регистров . подкоренного числа, результата, сдви га соединены с информационным входом устройства. Блок формирования цифр результата содержит элементы И, элемент ИЛИ, эл мент АИ-ИЛИ, причем первые прямые 80 входы первого, второго и первые инверсные входы третьего и четрертого элементов И соединены с первым входом блока формирования цифр результата, второй прямой вход первого и второй инверсный вход второго элемента И соединены с вторым входом блока формирования цифр результата, второй прямой вход третьего элемента И и второй инверсный вход четвертого элемента И соединены с третьим входом блока формирования цифр результата, первый вход блока формирования цифр результата соединен с его перi вым выходом, первый вход элемента ИЛИ соединен с выходом второго элемента И, второй вход элемента ИЛИ соединен с выходом четвертого элемента И, выход элемента ИЛИ является вторым выходом блока формирования цифр результата, выходы первого, второго, третьего и четвертого элементов И соединены соответственно с первым вторым, третьим и четвертым входами элемента И-ИЛИ, пятый шестой, седьмой, восьмой входы которого соединены соответственно с четвертым, пятым, шестым и седьмым входами блока формирования цифр результата, выход элемента И-ИЛИ является третьим входом блока формирования цифр результата, выходы первого, третьего второго и четвертого элементов И являются соответственно четвертым, пя- . блока формирования цифр результатаНа фиг. 1 изображена структурная схема предлагаемого устройства для вычисления квадратного корня (рассматривается случай, когда число одновременно формируемых двоичных цифр ре-. зультата К равно трем) ; на фиг. 2 показан для этого же случая один из возножных вариантов функциональной схемы блока формирования цифр результата; на фиг. 3 -функциональная схема i -го разряда коммутатора; .на фиг. i и 5 г функциональные схемы группы элементов И-ИШ и одной группы элементов ИЛИ. Устройство для вычисления квадратного корня содержит (фиг.1) регистры 1 и 2 соответственно подкоренного числа и результаты, регистр 3 сдвига, первый , второй 5 , третий 6 и четвертый 7 сумматоры, первый 8, второй 9 и третий 10 вычитатели, группу 11 элементов И-ИЛИ, первую 12, вторую 13, третью I, четвертую , пятую 16 и шестую 17 группы элемен5тов или, коммутатор 18, блок мирования цифр результата и вход 20 устройства. Выходы 1-28 являются выходами знаковых разрядов.регистра подко- ренного числа, сумматоров и вычитателей, выход 29 - блока формирования цифр результата. Блок формирования цифр результата (фиг.2) содержит элементы И 30, элемент ИЛИ 31, элемент И-ИЯИ 32. Схема -го разряда коммутатора (фиг. 3) содержит элементы И 33, элемент ИЛИ . Группа элементовИ-ИЛИ (фиг.) соде иит элементы И 35«элементы ИЛИ Зб. Группа элементов ИЛИ (фиг.5) содержит элементы ИЛИ 37 Блок 19 формирования цифр результата выполняет две функции; Во-первых, формирует сигналы, управляющие работой коммутатора 18. Во-вторых, формирует три двоичные цифры результата в соответствии с алгоритмом вычисления квадратного корня без восстановления остатка . Формирование сигналов у, у, у, у управляющих работой коммутатора Itt, а также формирование цифр результата f, f2, f-j осуществляется в узле 19 в соответствии со следующими логическими выражениями: X/ V V 7 22 26 J -J jc 10 - f х f 1 (, )(-, у. . 9 21 Ю 28 Здесь, например, через у обозначен управляющий сигнал, под действием которого коммутатор 18 осуществляет выборку результата, сформированного на выходе сумматора,с поряд ковым номером 7 на фиг. 1, X2-iObo3начает логическую переменную,соотве ствующую значению знакового разряда регистра 1 подкоренного числа (ее-. ,/1и в регистре 1 хранится. отрицательное число, то Ч 1, в противном случае Si 3, Т соответственно младшая и старшая двоичная цифра результата из трех формируемых а одном цикле цифр. На фиг. 2 приведена функциональная схема узла 19 формирования цифр результата, работающая в соответств с приведенными выше логическими выр жениями. 19 фор- На фиг. 3 показана функциомаль10153806ная схема i -го разряда коммутатора 18, где (Например, R обозначает значение разности на выходе г-го разряда вычитателя с порядковым номером 9 на фиг. 1. Если же в устройстве используются сумматоры без распространения переносов, то i -и разряд коммутатора 18 должен включать две такие схемь), Группы 12-17 элементов ИЛИ содёржат в определенных разрядах элементы ИЛИ (по одному элементу на разряд) . Группы же элементов И-ИЛИ содержат в определенных разрядах элемент ИЛИ или элементы И и ИЛИ. На фиг. А показана функциональная схема группы 11 элементов И-ИЛИ, на фиг. 5 - функциональная схема группы 13 элементов ИЛИ (другие группы элементов ИЛИ строятся подобным образом) . Устройство для вычисления квадратного корня работает следующим образом. В исходном состоянии в регистре 1 хранится п-разрядное число х (для определенности будем предполагать, что подкоренное число X есть правиль Эя нормализованная дробь, причем только положительная) , регистр 2 ре-зультата обнулен, в первом разряде сдвигающего регистра 3 записана еди-: ница (разрядность сдвигающего регистра 3 может быть выбрана равной числу циклов работы устройства для вычисления квадратного корня из п-раз. рядного двоичного числа, будем считать, что число циклов работы устройства равно п/3, а следовательно и ). В первом цикле работы устройства сумматор Ц, управляемый сигналом х,0, работает как вычитатель. Так . как регистр 2 результата обнулен, то результаты, формируемые на выходах группы 11 элементов И-ИЛИ и групп , 12-17 элементов.ИЛИ определяются только информацией, которую ввЬдит соответствующим образом в эти группы в соответствии ,с алгоритмом вычисления квадратного корня без восстановления остатка единица, хранимая в первом разрядесдвигающего регистра 3. .Ниже приведены эти результаты на выходах групп 11-17 (результаты расположены подобно тому, как разме- . щены группы 11-17 на структурной схеме устройства фиг. 1) o,uon 0,0101 0,1011 0,1101 Сумматор k, a также с;умматоры 5-7 и вычитатели 8-10 практически начинают работать одновременно. G vix помощью на выходах сумматоров 6 и 7 вычитате лей 9 и 10 формиргуются результаты пр всех возможных путях развития вычи тательного процесса определения т0ех наи6о1;1ев старших двоичных цифр резул тата y-j,Уд, УЗ по алгоритму вычис ления квадратного без восстано ления остатка. Очевидно, что в сдном цикле определения трех двоичных диф результата только один из этих четы.рёх результатов может быть правильный (выбор правильного результата осуществляется,с помощью управля- . ющих сигналов у, у, у, у).. По и течении времени, равного примерно времени суммирования двух п-разрядных двоичных чисел, коммутатор 18 вы бирает в качестве первого остатка ре зультат либо одного из сумматоров $ и 7, либо одного из вы««(тателей 9 и to, который с разрешения сигнала на входе 20 устройства записывается в ре гйстр 1 со сдвигом влево на один дво ичный разряд. Здесь можно отметить, чтопри .записи в регистр 1 очередного остг|тка сд сдвигом его влево на двоичный разряд возможно искажение знака остатка. Поэтому в регистре 1 результата необходимо предусмотреть кроме п основных разрядов два дополнительных знаковых разряда (один из этих дополнительных разря дов и Ъудет хранить ;Истйнное значение знака очередного остатка).Одновременно с выборкой коммутатором 18 одногоиз результатов на выходах сумматоров 6 и 7 и вычитате0,y :fJVjOOi-i

Q. 0,4, OplVa® O.

В остальном работа устройства во втором цикле аналогична работе устройства в первом цикле. В результате его выполнения-в регистр 1 записывается второй остаток, в регистре 2 формируется результат О,

а в третьем разряде сдвигающего регистра 3 записана единица.

После выполнения п/3 циклов в регистре 2 будет сформирован п-разрядный двоичный код результата. Выдвилей 9 и 10.и записью его в качестве очередного остатка в регистр1, в блоке 19 формируются три двоичные цифры результата f, f, fj которые записываются с разрешения сигнала на входе 20 устройства в три наиболее старшие разряды регистра 2 в качестве трех наиболее старших цифр результата у .УМ У. (номера разрядов регистра 2, в котйрые должны быть записаны три очередных цифры результата, однозначно определяет единица в регистре J). Одновременно с записью трех цифр результата в регистр 2, в регистре 3 осуществляется сдвиг единицы фо второй разряд (это во.змржн6, так как предполагается, что используются в устройстве синхр1онные двухтактные триггеры). Во втором цикле работы устройства режим работы сумматора 4зависит от знака первого остатка, хранимого в регистре 1 подкоренного числа (если этот остаток положительный, то сумматор k работает как вычитатель, в противном случае ка;к сумматор). Результаты, формируемые во втором цикле на выходах группы I1. элементов Й-ШШ и групп 12-17 элементов И11И определяются не только информацией, которую вводит соответствующим образом в эти группы в соЬтветс-твии с алгоритмом вычисления квадратного корня без восстановления остатка единица, хранимая во втором разряде сдвигающего регистра З, но и информацией регистра 2 результата (результат на выходе группы 11 элементов И-ИЛИ зависит еще и от значения знакового разряда регистра 1 подкоренного числа). Подобно тому как делалось ранее, ниже приведены эти результаты на выходах групп 11-17.. . Т 0,у, (если 1)

9101538010

гаемая в (n/:j)-M цикле работы уст- что число циклов работы ycfportcTsa роиства единица из последнего разря- может Ьыть определенным образом уведа сдвигающего регистра 3 указывает личено. если этого потребует точна окончание операции. Разумеется, ность вычисления

Я

(риг.З

j jyaf/fff

АаоЛг foitfjtfpf ,. регистра I

futeftt petvemfttE

. tlut.S

вмхв(Уы ,peapffae frtuemjut}