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

устройства, первый информационный вход сумматора т-й суммирующей ячейки (т 1,. . ., N) т-й строки матрицы подключен к входу задания режима работы устройства, первый информационный вход сумматора (т + 1)-и суммирующей ячейки т-й строки матрицы подключен к входу логической единицы устройства, вход переноса сумматора (т + 1)-й суммирующей ячейки т-й строки матрицы подключен к входу логического нуля устройства, выход сумматора каждой суммирующей ячейки подключен к первому информационному входу селектора той же суммирующей ячейки матрицы, выход элемента.ИЛИ и выход элемента 2И-ИЛИ каждой корректирзгющей ячейки подключены соответственно к первому информационному входу и к входу переноса сумматора той же корректирующей ячейки, второй информационный вход сумматора j-й корректирющей ячейки подключен к выходу селектора j-й суммирующей ячейки первого столбца матрицы, второй информационный вход сумматора п-й (п 1,.. ., /i -1/) суммирующей ячейки i-й строки матрицы соединен с вторым информационным входом селектора той же суммирующей ячейки матрицы и нодключен к выходу селектора соответственнно ;р-й (р 2,. .., i) суммирующей ячейки (i - 1)-й строки матрицы, вторые

информационные входы сумматора т-й и (ш + 1)-и суммирующих ячеек т-й строки матрицы соединены с вторым информационным входом селектора соответственно т-й и (т + 1)-й суммирующих ячеек т-й строки матрицы и являются соответственно (2т - 1)-м и (2т)-м разрядами первого информационного входа устройства, вторые информационные входы первого и второго селектров т-й управляющей ячейки соединены между собой и являются т-м разрядом второго информационного входа устройства, выход переноса сумматора первой суммирующей ячейки первой строки матрицы является первым разрядом.первого информационного выхс да устройства, выход переноса сумматора j-йкорректирующей ячейки является (J + 1)-м разрядом первого информационного выхода устройства, выход сумматора j-й корректирующей ячейки является j-м разрядом второго информационного выхода устройства, выход селектора т-й суммирующей ячейки N-Й строки матрицы является (т + N - 1)-м разрядом второго информационного выхода устройства, а выход селектора (N + 1)-й суммирующей ячейки JN-й строки матрицы является (:2N)-M разрядом второго информационного выхода устройства.

МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В КВАДРАТ И ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее N управляющих ячеек и матрицу суммирующих ячеек из N строк и (N + 1) столбцов, отличающееся тем, что, с целью сокращения затрат оборудования, в него введены (N - 1) корректирующих ячеек, каждая управлякщая ячейка содержит два селектора и элемент НЕ, каждая сз ммирующая ячейка содержит сумматор и селектор), а каждая корректирунмцая ячейка содержит сумматор, элемент ИЛИ и элемент 2И-ИЛИ, причем выход переноса сумматора первой суммирующей ячейки первой строки матрицы подключен к входу элемента НЕ и к первому информационному входу первого селектора первой управляющей ячейки, выход переноса сумматора i-й корректирукмцей ячейки

I

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях и быстродействующих ЭВМ для однотактного выполнения операций .возведения в квадрат и извлечения квадратного корня над целыми и дробными двоичными числами.

Целью изобретения является сокращение затрат оборудования.

На фиг.1 показана функциональная схема устройства; на фиг.2 - то же, управляющей ячейки устройства на фиг.З - то же, соответственно суммирующей и корректирующей ячеек устройства.

Устройство содержит управляющие ячейки 1, матрицу 2 суммирующих ячеек 3, корректирующие ячейки 4, разряды первого информационного входа 5 устройства, разряды второго информационного входа 6 устройства, разряды первого информационного выхода 7 устройства, разряды второго информационного выхода 8 устройства, вход 9 задания режима работы устройства, вход 10 логического нуля устройства, вход 11 логической единицы устройства.

Управляющая ячейка устройства содержит первый 12 и второй 13 селекторы, элемент НЕ 14, входы 15 - 17, выходы 18-20.

Суммирующая ячейка устройства содержит сумматор 21, селектор 22, входа 23 - 26, вькоды 27 - 30. 3 Корректирующая ячейка устройства содержит сумматор 31, элемент 2И-ИЛИ 32, элемент ИЛИ 33, входы 3.4 - 38, выходы 39 - 41. Управление устройством осуществля ется через вход 9 задания режима раб ты устройства. При возведении в квад рат на вьрсод 9 подается значение логического нуля, а при извлечении ква ратного корня - логической единицы. Формулой, используемой в предлагаемом устройстве, является. А а, 2. а- В,. 1--2 где А - исходное число; а - биты-числа А; N - разрядность кода операнда;-1 , . . В. - код, равный Га)- 2 + 2 (что для некоторого i равно а ... a..,U1) . Для вычисления квадрата числа тре буется определить сумму N слагаемых. Причем первое слагаемое равно а,2, а все последующие равны либо нулю для а. 0, либо коду В, сдвинутому на соответствующее число разрядов Операция извлечения квадратного корня в устройстве выполняется по известному алгоритму с восстановлением остатка, который можно сформулировать из выражения (1). Определение цифр результата в это алгоритме осуществляется итерационным способом на основе последователь ного вычитания из кода операнда слагаемых вьгражения (1), при зтом заранее предполагается, что каждая очере ная цифра результата Z равна 1, т.е на первой итерации вычитается код .0 на второй - код .Z,, а на i-Й код ..,.Z- Ot-2 В способах формирования i-ro слагаемого при возведении в квадрат и i-ro вычитаемого при извлечении квад ратного корня имеется аналогия. Имен но это служит основой для объединени противоположных операций в едином ма ричном устройстве. Устройство работает следующим образом. Для возведения в квадрат на входы 9 подают сигнал нулевого уровня, а на входы 5 устройства - нулевой код. Код операнда в N разрядов подают на 874 входы 6 устройства, причем старший разряд кода поступает на первую управляющую ячейку. Так как на входах 15 ячеек 1 - нулевой сигнал, то выходы 18 и 20 повторяют информацию с входа 17 (фиг.2). С выходов 18 и 20 сигналы поступают на входы 23 и 25 ячеек 3 (фиг.З) и участвуют в формировании кодов i-x слагаемых в соответствии с формулой (1). В том случае, когда i-я цифра кода операнда равная 1, в ячейках 3 i-й строки матрицы выбирается то плечо селектора 22, которое подключено к выходу сумматора 21. Это соответствует суммированию i-ro слагаемого с ранее накопленной суммой. Когда i-я цифра операнда равна О, на выходах 30 ячеек 3 в i-й строке матрицы повторяется код, присутствующий на входах 26 этих же ячеек, что эквивалентно суммированию накопленной ранее суммы с нулевым кодом. Присутствие нулевого сигнала на входе 36 ячеек 4 (фиг.4) позволяет организовать между последними цепь рапространения переноса, которая необходима для суммирования кодов, возникающих на выходах .30 и 28 ячеек 3 первого столбца матрицы. Тот же сигнал на входах 36 ячеек 4 настраивает элементы 2И-Ш1И 32 последних на работу в ключевом режиме, что позволяет преотвратить учет переносов, возникающих на выходах 28 ячеек 3, когда i-я цифра кода операнда равна 0. Код результата операции возведения в квадрат формируется на выходах 8 устройства (на фиг,1 старшие разряды расположены слева). Код, формируемый на выходах 7, - не информационный. Для извлечения квадратного корня на входы 9 необходимо подать сигнал единичного уровня, а на входы 5 2N-разрядный код операнда. Так как на входах 15 ячеек 1 (фиг.2) присутствует единичный сигнал, то на выходы 20 передается прямое значение сигнала с входа 16, а на выход 18 - инверсное. Сигнал с выхода 20 i-й ячейки 1 управляет селекторами 22 ячеек 3 i-й строки матрицы, а сигнал с выхода 18 участвует в формировании коов, необходимых для выполнения вычитания в следующих итерациях. Логическая единица в знаковом разряде каждого i-ro вычитаемого формируется посредством сигнала единичного уровня. поступающего на входы. 36 ячеек 4. Этот же сигнал.обрывает цепь распространения переноса между ячейками 4, а также пердопределяет безусловное распространение переносов мезкду суммирующими ячейками 3 i-й строки матрицы и i-й корректирующей ячейкой, так как элемент 2И-Ш1И вьшолняет роль логического повторителя. Очередные цифры корня равны значению переноса из знаковых разрядов кодов Lj,формируемых на выходах переноса сумматоров 31 корректир.ующих ячеек 4 и на выходах переноса сумматора 21 первой суммирующей ячейки первой строки матрицы. Эти цифры участвуют в формировании очередных остатков. Если i-я цифра корня равна 1, восстановление остатка не прои водится и селекторы 22 ячеек 3 i-й строки матрицы передают на выходы 3 информации с выходов сумматоров 21. Если i-я цифра корня равна О, осуществляется восстановление остатка путем передачи на выходы 30 ячеек 3 сигналов с входов 26. Результат выполнения операции из влечения квадратного корня формируе ся на выходах 7 устройства. Окончательный остаток формируется на вы ходах 8 матрицы. Для реализации известного усТ- . ройства, являющегося базовым рбъектом, требуется Зо (N + N)(3e + .MAu)N3 где 3с, 3, Звдк.или - затраты на реаГ лизацию селектора и элемента ИСКЛЮ ЮЩЕЕ ИЛИ ячейки известного устройст ва. Затраты на реализацию предложеннрго устройства равны 3, (N + iN)(3c + 3J -f. 2-N-3 + (N - 1)-(3„,+ Зг + ЫЗи, где 3, , Згм - затраты на реаизацию инвертора управляющей ячейки, элемента ШШ и элемента 2И-ИЛИ корректирующей ячейки. Для построения обоих устройств на элементах 133 или 155 серии типа ИМЗ, КП2, ЛН1, ЛЛ1, ЛП5 и ЛР1 потребуется у известного устройства 3 288 корпусов, а у предложенного 3 146 корпусов, т.е. в два раза меньше. В известном устройстве для управления ячейками используются две управляющие цепи, а в предложенном - одна, следовательно, предложенное устройство менее загружено топологически. Время извлечения квадратного корня у известного устройства t (2V5.-N +0,5 N) tp + N X ( t + VK.,,,), где tp - время распространения переноса в одноразрядном сум маторе; к иск,.мли время работы селектора и.элемента ИСКЛЮЧАЮЩЕЕ. ИЛИ. Время извлечения корня у предложенного устройства t (0,5 N + 0,5.N)tp + N(t + + tj + 2 tp + N(t,+ tjj, где , t - задержки инвертора элемента ИЛИ и 2И-ШШ. . Время Возведения.в квадрат у обоих устройств одинаково и равно 2 N х X tp + 2t. Сопоставив t и t.:| , видно, что tg t следовательно, предложенное устройство более быстродействующее . I

f-o

Фиг, 7