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

Изобретение относится к области вычислительной техйики и может быть использовано для аппаратной реализа ции операции вычисления квгшратного корня в универсальных и специализированных вычислителях. Известно устройство для извлечения квадратного корня, содержащее генератор импульсов, схему совпадения, счетчик, группы вентилей и сумматор накапливающего типа. Извле чение квадратного корня в нем осуществляется путем подсчета суммы членов ряда нечетных чисел l Недостатком этого устройства является его низкое быстродействие, определяемое числом циклов вычисления, зависящим от диапазона чисел. Известно устройство для извлечения квадратного корня, содержащее приемный регистр, сумматор, регистр результата, группы элементов И прямого и инверсного кодов 2J . Недостатком этого устройства является его низкое быстродействие, вызванное тем, что при получении од ной цифры результата производится сложение и сдвиг в сумматоре. Известно также устройство для вычисления квадратного корня, содер жащее входной и выходной регистры, . блок управления t3J. Недостатком известного устройства является его низкое быстродействие, обусловленное, во-первых, формированием в каждом такте только одной цифры результата, во-вторых, необходимостью в каждом такте возводить в квадрат числа-, разрядность которых равна разрядности подкоренного выражения. Время вычисления квадратного корня в известном устройстве примерно равно,:-Т .п .С умн. , где п - разрядность подкоренного выражения, f - время возведения в квадрат п-разрядных чисел, пример- : но равное времени умножения. Целью изобретения является увеличение быстродействия- устройства для вычисления квадратного корня. Поставленная цель достигается тем, что ь устройство, содержащее входной и выходной регистры, блок управления, дополнительно введены шифратор, счетчик, формирователь поразрядной суммы, узел умножения и вычит тель, причем первый и второй входышифратора соединены с выходами старших разрядов соответственно входного и выходного регистров, выход шифратора соединен со входом счетчика, выход ко торого соединен со входом выходного регистра, а также с первыми информационными входами формирователя пораз рядной суммы и узла умножения, выходы разрядов выходного регистра соединены со вторым информационным входом формирователя поразрядной суммы, выход которого соединен со вторым информационным входом узла умножения, выход, последнего соединен с первым информационным входом вычитателя, второй информационный вход которого соединен с разрядным выходом входного регистра, а информационный выход вычитателя соединен со входом блока управления и с информационным входом входного регистра, первый, второй, третий и чвтвертый выходы блока управления соединены соответственно с управляющим входом счетчика, управляющими входами входного и выходного регистров и управляющим входом формирователя пор азрядной суммы, причем блок управления содержит первый и второй блоки памяти, элемейт задержки, регистр, дешифратор адреса микрокоманд, генератор тактовых сигналов, дешифратор условий, злемент ИЛИ-НЕ и сдвигающий регистр, причем вход элемента.задерж ки соединен с выходом второго блока гзам.яти, выход элемента задержки соединен со входом регистра, выход которого соединен с информационным входом дешифратора адреса микрокоманд, управляющий вХод которого соединен с выходом генератора тактовых сигналов, выход дешифратора адреса микрокоманд соединен с управляющим входом первой матрицы, первым управляющим входом второй матрицы и первым управляющим входом дешиф- ратора условий, второйуправляющий вход которого соединен с выходом элемента ИЛИ-НЕ, информационный вход которого соединен со входом блока управления, третий управляющий вход дешифратора условий соединен с инфор мационным входом элемента ИЛИ-НЕ, четвертый управляющий вход дешифратора условий соединен с выходом млад шего разряда сдвигающего регистра, выход дешифратора условий соединен со вторым управляющим входом второго блока памяти, первый, второй и тре- тий выходы первого блока памяти соединены соответственно с первым, вто рым и третьим выходами блока управления , четвертый выход первого блока памяти соединен со входом сдвигающего регистра, выход которого соединен с третьим и четвертым выходами блока управления. На фиг. 1 приведена структурная схема устройства для вычисления квадратного корня; на фиг. 2 - функциональная схема шифратора} на фиг. 3 функциональная схема формирователя поразрядной суммы, на фиг. 4 - функциональная схема узла умножения; на фиг. 5 - структурная схема блока управления; на фиг. б - алгоритм работы блока управления; на фиг.7 дешифратор условий. Устройство для вычисления квадратного корня (фиг. 1) содержит входной 1 и вьзходной 2 регистры, блок 3 уп)авления, шифратор 4, счетчик 5, формирователь 6 поразрядной суммы, узел 7 умножения и вычитатель 8, выходы старших разрядов 9 (входит регистр 1), выходы старших разрядов 10 (входит регистр 2), разрядные выходы 11 (регистра 2), информационный вход 12 (регистра 1) . Шифратор (фиг. 2) содержит дешифратор 13 адреса и матрицу 14 запоминающих элементов. Формирователь поразрядной суммы (фиг. 3) содержит К-разрядных групп элементов И 15, группу элементов ИЛИ 16. Узел умножения (фиг. 4) содержит К(п+1)-разрядных комбинационных сумматоров 17, информационные входы сумматоров 18 и 19, управляк щие входы сумматоров 20 и выходы 21. Блок управления (фиг. 5) содержит первый и второй блоки 22 и 23 памяти, элемент 24 задержки, регистр 25, дешифратор 26 адреса микрокоманд, генератор 27 тактовых сигналов, дешифратор 28 условий, элемент ИЛИгНЕ 29, сдвигающий регистр 30, информационный вход блока 31 управления, первый., второй, третий и четвертый выходы .блока 32-35 управления. В устройствах для вычисления квадратного корня входной 1 и выходной 2 регистры реализованы ha 0-триггерах, формирователь 6 поразрядной суммы, узел 7 умножения и вычитатель 8 реализованы в виде комбинационных схем. Синтез шифратора 4 воспроизведен по табл. 1 истинности. Шифратор 4 реализоаан на элементе памяти, имеющем дешифратор адреса. При этом сокращается количествооборудования и: обеспечивается регулярность его струк туры. С помощью шифратора 4 формируется максимально возможное значение очередных К цифр результата на основании содержимого отар1пих разрядов входного регистра 1(d) и выходного регистра 2(х), которое впоследствии,.в случае несовпадения с его точным значением, уточняется в устг ойстве. Для этого строится таблица максимальных значений К цифр результата всех возможных комбинациях значений d и х. Величина х определяется исходя из представления подкоренного выражения D в виде 0( I х.)%ли D (2 Т х.+х.).х .-. 1 л. А 1 11-1 121 :-: где X.- величина К цифр результата, определенных в i-ом такте с учетом их весовой позиции М « - количество тактов, необходимых для определения цифр результата. Для определенности принимаем,что величина подкоренного выражения D является нормализованным числом, т.е. 1/2 «О 1. После окончания i-ro такта формируется остаток d- D - { j; )} , который в свою очел-лредь больше или равен величине j(.j( .Г - + -л «..« - Е N+ - Предположим, что первый вход шифратора 4 соединен с (K+l) старшими разрядами входного регистра 1, а второй вход шифратора 4 соединен с К старшими разрядами выходного регистра 2. С учетом этого неравенство (1) можно преобразовать в следующее эквивалентное неравенство ТТ1Г ( Из неравенства (2) следует, что максимально возможное значение очередных К цифр результата при I 1 могно определить из выражения d + ) X , вычисляя знаwoy; 2 X,, чение только его .К старших разрядов. При 1 1 , Vd-f2- . С учето весовых позиций величин х,--и d в пред лагаемом устройстве и с целью, обеспе чения значения величины х., в пределах Обх,, формулы для определения максимально возможного значения очередных К цифр результата примут вид 1 , 2Vd + 2- , при I .d + 2- : X . 2 при 4

Табл. 1 является таблицей истинности шифратора 4, причем для определенности принято, что К г 4, Значение старших разрядов, поступающих на первый вход шифратора 4 с выхода 9 входного регистра 1, обозначены через d, а на второй вход шифратора 4 с выхода 10 выходного регистра 2 через х , Вес старшего разряда личины d равен 2 1. Так как в каждом такте определения очередных К цифр результата производится сдвиг получившегося остатка по цепг: 12 на К разрядов в сторону старших разрА дов, то целесообразно показать, что содержимое входного регистра 1 в каждом Такте не будет превышать величины, Равной двум. Действительно, если доказать, что выполняется .4. -К условие - ( 2: X О « 2 2 , то подтверждается вышесказанное, т.е., что содержимое входного регистра 1 в каждом такте не превышает величины, равной двум. Так как D .1 , то ьохГ (i/i.+ ) , тогла (51 х. + + 2:)-- (зх.) или 2- 2 I 1 -. 1 .г5 (21х. + ) 22- 5:х. + . Ьч - Полученное неравенство выполняется при всех входящих в него значениях х,-. Значения величин в табл. 1 приведены в десятичной системе счисления. При построении табл. 1 учтено, 1 W is О 1, то X 0,1011. что если Таблица

Продолжение табл.

При расширений разрядности значе,НИИ d и х точность предсказываемых шифратором 4значений возрастает. , Формирователь поразрядной суммы б

(фиг. 3) содержи 2.к.раэрядных групп

элементов И 15, группу элементов ИЛИ 16, причем первый вход каждой группы элементов И 15 соединен с выходом счетчика 5, а второй вход группы элементов И 15 соединен с выходом блока 3 управления и является управляницим входом формирователя 6 поразрядной сумкщ, выход каждой группы элементов и 15 соединен с первым входом группы элементов ИЛИ 16 с учетом их .весомой позиций, второй вход группы элементовИЛИ 16 цепью сдвига 11 соединен с выходом выходного регистра 2, а выходы группы элемен сов ИЛИ 16 являются выходами формирователя 6. С помошью формирователя 6 в i-ом такте формируется значение (. + х/), равное 13-.I ч

удвоенному содержимЬ иу регистра 2

(2;S:i xj.) , поступающему на второй вход

ч -1

группы элементов ИЛИ 16, увеличенное на величину (с;), поступающую с выхода счетчика 5 с учетом весовой йозиции группы из К цифр результата, которые определяются -в данном такте, путем выдачи блоком 3 соответствующего управляющего сигнала на второй вход нужной группы элементов И 15.

Узел 7 умножения реализован, например, по матричному принципу (фиг. 4). Он содержит К (п + 1)-разрядных комбинационных сумматоров 17, сдвинутых друг относительно друга на один разряд, первый вход 18 каждого из которых соединен с информационным выходом формирователя 6, а второй выход 19 каждого сумматора, кроме первого, соединен с выходом эна- чений п старших разрядов предыдущего сумматора 17 (для первого сумматора 17 на его вход 19 подается нуль), управляющий вход 20 каждого сумматора 17 соединен с соответствукадим разрядом выхода Счетчика 5, выход последнего сумматора 17, а также выходы 21 младшего разряда всех остальных сумматоров 17 являются информационным выходом узла 7 умножения. В узле 7 умножения реализован способ умножения с младших разрядов. Если значение на управлякмцем входе 20 сумматора 17 единица, то на первый вход сумматора 17 передается число, поступающее на его вход 18, если нуль, то передаются нули. С помощью

узла 7 умножения формируется произ1-1ведение (2Z х.+ х.)х.

-« Что касается вычитателя 8, то он,

например, реализован по схеме со сквозным либо параллельным распространением займа.

Счетчик 5 представляет собой вычитающий счетчик накапливающего типа и реализован, например, на IКтриггерах по схеме со сквозным либо параллельным распространением займа.

Блок 3 управления реализован по микропрограммному принципу по схеме Уилкса с запоминающимустройством (блоками памяти) микрокоманд в виде двух матриц запоминающих элементов (фиг. 5) .

Блок 3 управления предназначен для реализации алгоритма работы устройства для вычисления квадратного корня, граф-схема (ГСА) которого приведена на фиг. 6. ГСА содержит вершины . На ГСА информация на выходах комбинационных узлов обозначена буквой Л с соответствующей позицией, присвоенной комбинационному узлу.

В блоке 3 управления первый 22 и второй 23 блоки памдти представляют собой постоянные запоминающие устройства (ПЗУ) , выборка из которых осуществляется путем возбуждения с6 ответствуюшей шины. Первый блок 22 памяти представляет собой накопител определенных наборов управляющих сигналов. Выборка необходимого набо ра управляющих сигналов осутествляется путем возбуждения соответствующей шины блока 22 памятч сигналами € выходов дешифратора 26 адреса микрокоманд. Образующиеся на выходах блока 22 памяти сигналы, как сигнал микроопераций, поступают в необходи мые узлы устройства. Блок 3 управле ния формирует четаре микрокоманды, соответствующие операторным вершинам 2, 6, 7, 8 ГСА. Блок 23 памяти предназначен для управления последовательностью выполнения микр команд. Выборка необходимого адреса следующей микрокоманды производится лутем возбуждения соответствукмпей шины блока 23 памяти сигналами с вы хода дешифратора 26 при выполнении микрокоманд, после которых не проверяются условия перехода, и сигналами с выхода дешифратора 28 при выполнении тех микрокоманд, после которых имеются условия перехода. Так, после выполнения микрокоманд, соответствующих вершинам 7 и 8 ГСА,условий перехода нет, а после выполнения микрокоманд,соответствующих вершинам 2 и .i6, производится проверка условий перехода. Сигналы дешифратора 28 возбуждают одну из трех шин блока 23 памяти, соответствующую переходу к выполнению одной из микрокоманд, действия в которых указаны вершинами ГСА. Эти сигнсшы фop lиpyютcя в соответствии со следующими логическими выражениями: Ъ 4 Bji Y,, Л Xj4 .Л Ba8-A% b Y,4AY,5) (Y54AY,5 ), где U , В , В -- сигналы на выходе дешифратора 28 для формирования перехода к вершинам 6, 7, 8 ГСА соответственно/ Y, Y , У - условия перехода, соответствующие верижнам 3, 4, 5 ГСА, сформированные при выполне нии текущей микрокоманды . Условие, соответствующее вершине 3 ГСА и указывающее, что обнаруже нулевой результат вычитания, формируется элементом ИЛИ-НЕ 29. Условие соответствующее вершине 4 ГСА и указывающее, что результат вычитания отрицательное число, определяется состоянием знакового разряда вычитателя 8. Для управления выходным регисЙ- о ром 2, формирователем бив качестве счетчика тактов используется w разрядный сдвигающий регистр 30. В каждом такте работы устройства 9 сдвигающем регистре 30 производится поразрядное продвижение логической единицы. Это позволяет управлять соответствующей группой элементов И формирователя 6 и производить запись информации в нужные К-разрядов регистра 2 (момент записи в регистр 2 определяется сигналом с соответству- jouiero выхода блока 22 па йятиблока 3 управления ). Так как значение логической единицы появится в младшем разряде сдвигающего регистра 30 только в последнем такте, то состояние этого разряда и будет определять последний такт (вершина 5 ГСА). Генератор 27 тактовых сигналов предназначен для задания определенной частоты выборки наборов управляющих сигналов при постоянной длительности тактов. Импульсы с его выхода поступают на дешифратор 26 и в зависимости от кода адреса микрокоманд, находящегося в регистре 25, возбуждают необходимые блоки 22 w 23 памяти. Так как код в регистре 25 должен изменяться только после завершения всех процессов, связанных с выполнением текущей микрокоманды, поэтому коды с выхода второго блока 23 памяти подаются в регистр 25 через элемент 24 задержки, включаемый в каждую разрядную цепь. При работе блока 3 управления по коду адреса микрокоманды, находя- , щемуся в регистре 25, дешифратором 26 выбирается одна из шин блока 22 памяти. При подаче тактовых сигналов от генератора 27 формируются все необходимые управляющие сигналы. Выборка адреса следующей микрокоманды из блока 23 памяти производится дешифратором 26, если после выполняемой команды не выполняется условный переход. Если условный переход выполняется , то по сигналу дешифратора 26 разрешается ангшиз условий пе|)ехода с помощью дешифратора 28 условий . После формирования условий перехода и их анализа дешифра:тором 28 производится выборка адреса следующей микрокоманды из блока 23 памяти. Выбранный адрес записывается в регистр 25 через время, определя7 емое величиной элемента 24 задержки. Устройство для вычисления квгщратного корня работает следующим образом. В исходном состоянии входной регистр 1 содержит под-соренное выражен.ие, а выходной регистр 2 и сдвигающий регистр 30 блока 3 управления содержит нули . В каждом,такте работы устройства определяется К цифр результата. Для этого производятся следующие действия. По содержимому регистра 25 адреса микрокоманды после его дешифрации производится выполнение первой микрокоманды (вершина 2 ГСА). В этой микрокоманде сформированное с помощью шифратора 4 приближенное значение очередных К цифр результата помещается в вычитающий счетчик 5 и продвигается единица в сдвигающем регистре 30 (в пер- ; вом такте единица вдвигается в старший разряд сдвигающего регистра 30), Значение очередных К цифр результата (х ) с выхода счетчика 5, поступающее на первый вход формирователя 6, совместно с содержимым выходного регистра 2, поступающим на второй вход формирователя 6 по цепи сдвига 11 на один разряд в сторону старших

разрядов, используется для фор 1ироi-iванйя величины 2 х .+ х- . С помощью

1:И

узла 7 умножения формируется величи -iна (2Zx,+ х.)х. . которая в вычитаi - 1 1

теле 8 вычитается из содержимого входного регистра 1. Если на выходе вычитателя 8 блоком 3 управления зафиксирован знак минус, то следующая микрокоманда (вершина б ГСА) осуществляет вычитание единицы из счетчика 5, и процесс повторяется. Если на выходе вычитателя 8 зафиксировано положительное число,не равное ную (значение х , находящееся в счет чике 5, является точным значением очередных К цифр результата), и если в младшем разряде сдвигающего Регистра 30 находится нуль (счетчик тактов не равен п/К), то выполняется третья микрокоманда (вершина 7 ГСЛ). В этой микрокоманде значение, поступающее с выхода счетчика 5, записывается в соответствующие К-разрядов выходного регистра 2, а результат вычитания с выхода вычитателя 8 по цепи сдвига 12 на К-разрядов в сторону старших разрядов записывается во входной регистр 1. После этого осуществляется безусловный переход к выполнению первой микрокоманды, (вершина 2 ГСА). Следует отметить, что если при очередном вычитании блоком 3 управления обнаружен нулевой результат или в последнем такте обнаружено в результате вычитания положительное число, то выполняется четвертая микрокоманда (вершина 8 ГСА). Дейстчия, выполняемые в четвертой мик)окоманде, аналогичны действиям, выполняемым в уретьей (микрокоманде, но выполнения четвертой микрокоманды процесс вычисления квадратного корня заканчивается.

Таким образом, предлагаемое устройство для вычисления квадратного корня позволяет сформировать результат за п/К тактов, в то время как известное-за п тактов. Длительность такта в предлагаемом устройстве составляет величину

,(l . гдеСдтч время вычитания чисел/

ICP величина, определяющая

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

Величина рропределяется следу ющим образом. Р

Р

Г Cjy.Wfcp

1 5, 5 . m |,Г

где m - максимальное число шагов,

которое необходимо выполнить в одном такте (1 m : r)t

д m - среднее число шагов, кото рое необходимо выполнить

для получения К цифр результата ;

и.р- число случаев, когда для по лучения К цифр результата

требуется выполнить в среднем шагов.

Поэтому быстродействие предлагаемого

устройства для вычисления квадратно0 го корня возрастает в К ,„ / ,„

(1 + - ) раз в сравнении с известным устройством, где1Гу,д,ц - время возведения в квадрат п разрядных чисел,

5 При этом предполагается, что вычитатель и сумматоры уз-ла умножения реализованы по схеме со сквозным рас.пространением переносаi Чтобы оценить входящие в формулу для расQ чета tcp величины, строится таблица значений величины х при всех возможных комбинациях d и х. Величина определяется исходя из представления формируемого после окончания очередного такта остатка d,,- в ви d. (2.ix,. + х.4. ) С( .

.С учетом всех предложений, принятых ранее при расчете х.,имеем.

X. .+

2(х 2) откуда следует, что величина - 5,2(.2)

ТОЧНО равна х,- , или меньше его. Поd

этому при f 1 .принимаем х , .

W«, 2(

При i 1 Yd , С учетом весовых позиций величин х и d и обеспече ния значений величины xj в пределах

X,- 2 , формулы для определения О «

Я

г VT.

при

Wl i

2( 2)

В табл. 2 приведена таблица значений величин при всех возможных комбинациях d и х . Значения величин 15 приведены в табл. 2 в десятичной системе счисления. При построении табл. 2 учтено, что если 1/2 , то х,„4-|, 0,1011. На основании табл. 1 и 2 определяем т- .i.Т а б. л и ц а 2

Продолжение табл. 2 Эффективность изобретения заключается в сокращении времени вычисления квадратного корня примерно в 7,1 раза. Расчет производится з пред положении, что , тогда tcp 1,5, вычитатель и сумматоры I узла умножения реализованы по схеме со сквозным распространением переноса, а первый вход дешифратора соединен с (К+1 ) старшими разрядами входного регистра, второй вход шифратора соединен с К старшими разрядами ;выходного регистра. Формула изобретения 1. Устройство для вычисления квадратного корня, содержащее входной и выходной регистры, блок управления, отличающееся тем, что, с целью увеличения его быстродействия, в него введены шифратор, счетчик, формирователь поразрядной суммы, узел умножения и вычитатель, причем первый и второй входы шиф- ратора соединены с выходами старших разрядов соответственно входного и выходного регистров, выход шифратора соединен с входом счетчика, выход которого соединен с входом выходного регистра, а также с первыми информационными входами формирователя поразрядной суммы и узла умножения, выходы разрядов выходного регистра соединены со вторым информационным входом формирователя поразрядной суммы, выход которого оединен со рым информационным входом узла умножения, выход последнего соединен с первым информационным входом вычитателя, второй информационный вход которого соединен с разрядным выходом входного регистра, а информаци онный выход вычитателя соединен с входом блока управления и информационным входом входного регистра, первый, второй, третий и-четвертый выходы блока управления соединены соответственно с управляющим входом счетчика, управляющими входами входtjpro и выходного регистров и управля 1ЮЩИМ входом формирователя поразрядной суммы. 2. Устройство по п. 1, о т л ичающееся тем, что блок управления содержит первый и второй блоки памяти, элемент задержки, регистр, дешифратор адреса микрокоманд генератор тактовых сигналов, дешифратор условий, элемент ИЛИ-НЕ, сдвигающий регистр, причем вход элемента задержки соединен с выходок второго блока памяти, выход элемента задержки соединен с входом регистра выход которого соединен с информационным оходом дешифратора адреса микрокоманд, управляющий вход Которого соединен с выходом- генератора такто вых сигналов, выход дешифратора адреса микрокоманд соединен с управля ющим входом первой матрицы, первым управляющим, входом второй матрицы и первым управляющим входом дешифратора условий, второй управляющий вход которого соединен с выходом элемента ИЛИ-НЕ, информационный вход которого соединен с входом блока управления, третий управляющий вход дешифратора условий соединен с информационным входом элемента ИЛИ-НЕ, чет,вертый управляющий вход дешифратора условий соединен с выходом младшего разряда сдвигающего регистра, выход дешифратора условий соединен со вторым управляющим входом второго блока памяти, первый, второй и третий выходы первого блока памяти соединены соответственно с первым, чторым и третьим, выходами блока управления, четвертый выход первого блока памяти соединен с входом сдвигающего регистра, выход которого соединен с третьим и четвертым выходами блока управления. Источники информации, принятые во внимание при экспертизе , 1. Авторское свидетельство СССР. № 394781, кл. G 06 F 7/38, 1973. 2.Панернов А, А..Логические ос;ц.овы ЦВТ. .М. , Советское радио, 1972, с. 253-259. 3.Авторское свидетельство СССР № 611208, кл. G Об F 7/38, 1978 (прототип).

le2-2

Т

Фиг.З

pBZ. Ксчетику5 К ре г. 2 К tpopHupoSamemO

33

55

i

54

П

25

-Tt-

§

2а

-

Jfl

22

2J Рег.1-пр3мренное

Рез.г---0 Рег-ЗО- О

Начало выражение

Pea.l-Z -AB.t Pe8.2-A5г Pe&г

Конец

Фиг. 6

CiitHufl разрешения