Матричное устройство для возведения в квадрат и извлечения квадратного корня

/ц,.ЗЯБЛА Р;:.,:,ИОАН ЗОБРЕ ЕН АВТОРСТВО ИДЕТЕЛЬСТ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(56) Авторское свидетельство СССРВ 758144, кл. С 06 Р 7/38, 1977,1.С.Ма 3 ь.опа СеПц 1 аг Аггау акогЕхГгасГоп оГ ЯЧцагез апй ЯЧцагезРоома оГ .В 1 пагу ИцшЪегз. - ТЕЕЕТгапз. Сошрцг чо 1. С,рр. 1023-1024, 1972.(54)(57) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯВОЗВЕДЕНИЯ В КВАДРАТ И ИЗВЛЕЧЕНИЯКВАДРАТНОГО КОРНЯ, содержащее М управляющих ячеек и матрицу суммирующих ячеек из И строк и (М + 1) столбцов, о т л и ч а ю щ е е с я тем,что, с целью сокращения затрат обо-,рудования, в него введены (Я - 1)корректирующих ячеек, каждая управляющая ячейка содержит два селектораи элемент НЕ, каждая суммирующаяячейка содержит сумматор и селекто,а каждая корректирующая ячейка содержит сумматор, элемент ИЛИ и элемент 2 И-ИЛИ, причем выход переносасумматора первой суммирующей ячейкипервой строки матрицы подключен квходу элемента НЕ и к первому информационному входу первого селекторапервой управляющей ячейки, выход переноса сумматора 1-й корректируняцейячейки (1 2, 3, , Я) подключенк входу элемента НЕ и к первому информационному входу первого селекторад-й управляющей ячейки, а также к первому входу элемента ИЛИ (х=1) -й корректирющей ячейки, выход переноса суммато"ра суммирующей ячейки первого столб-. ца -й строки подключен к первому и второму входам элемента 2 И-ИЛИ д-йкорректирующей .ячейки, выход первого селектора первой управляющей ячейки подключен к управляющим входам селекторов всех суммирующих ячеек первой строки матрицы, выход первого селектора 1-й управляющей ячейки подключен к третьему входу элемента 2 И-ИЛИ х-й корректирующей ячейки и к управляющим входам селекторов всех суммирующих ячеек 1-й строки матрицы, выход элемента НЕ каждой управляющейячейки подключен к первому информационному входу второго селектора тойже управляющей ячейки, выход второго селектора д-й управляющей ячейки(=1 . Я) подключен к первомуинФормационному входувсех К-х сумми- фавв рующих ячеек (К = /3 + 1/, , Н)3-го столбца матрицы, выход переноса сумматора второй суммирующей ячейки первой строки матрицы подключен квходу переноса сумматора первой сумми рующей ячейки первой строки матрицы, выход переноса сумматора -й(3 = 2 /1 + 1/) суммирующейячейки 1"й строки матрицы подключен к входу переноса сумматора ( В - 1)-й суммирующей ячейки 1-строки матрицы, второй вход элемента ИЛИ -й корректирующей ячейки соединен с четвертым входом элемента 2 И-ИЛИ 1-й корректи-. фр рующей ячейки и подключен к входу за дания режима работы устройства, первый вход элемента ИЛИ (И - 1)-й корректирующей ячейки подключен к входу логического нуля устройства, управляющие входы первого и второго селекторов всех управляющих ячеек подключены к входу задания режима работы1171787 устройства, первый информационныйвход сумматора ш-й суммирующей ячейки (ш - 1 М) ш-й строки матрицыподключен к входу задания режима работы устройства, первый информационный вход сумматора (ш + 1)-й суммирующей ячейки ш-й строки матрицы подключен к входу логической единицыустройства, вход переноса сумматора .(ш + 1)-й суммирующей ячейки ш"й строки матрицы подключен к входу логического нуля устройства, выход сумматора каждой суммирующей ячейки подключен к первому информационному входуселектора той же суммирующей ячейкиматрицы, выход элемента ИЛИ и выходэлемента 2 И-ИЛИ каждой корректирующей ячейки подключены соответственнок первому информационному входу и квходу переноса сумматора той же корректирующей ячейки, второй информационный вход сумматора 1-й корректирующей ячейки подключен к выходу селек"тора -й суммирующей ячейки первогостолбца матрицы, второй информационный вход сумматора и-й (и = 1/1 - 1/) суммирующей ячейки -й строки матрицы соединен с вторым информационным входом селектора той же суммирующей ячейки матрицы и яодключенк выходу селектора соответственннор-й (р = 2 ) суммирующей ячейки ( - 1)-й строки матрицы, вторые Изобретение относится к вычисли.тельной технике и может быть использовано в специализированных вычисли"телях и быстродействующих ЭВМ дляоднотактного выполненйя операций,возведения в квадрат и извлеченияквадратного корня над целыми и дроб.ными двоичными числами.Целью изобретения является сокращение затрат оборудования.На фиг.1 показана функциональнаясхема устройства; на фиг.2 - то же,управляющей ячейки устройства, нафиг.3 - то же, соответственно суммиРукицей и корректирующей ячеек устройства,Устройство содержит управляющиеячейки 1, матрицу 2 суммирующих ячеинформационные входы сумматора ш-й и (ш + 1)-й суммирующих ячеек ш-йстроки матрицы соединены с вторым информационным входом селектора соответственно ш-й и (ш + 1)-й суммирующих ячеек ш-й строки матрицы и являются соответственно (2 ш - 1)-м и(2 ш)-м разрядами первого информационного входа устройства, вторые информационные входы первого и второгоселектров ш-й управляющей ячейки соединены между собой и являются ш-мразрядом второго информационного входа устройства, выход переноса сумматора первой суммирующей ячейки первой строки матрицы является первымразрядом первого информационного выхода устройства, выход переноса сумматора 1-й корректирующей ячейки является ( + 1)-м разрядом первого информационного вьмода устройства, выход сумматора 1-й корректирующейячейки является 1-м разрядом второгоинформационного выхода устройства,выход селектора ш-й суммирующей ячей.ки Б-й строки матрицы является(ш + И - 1)-м разрядом второго информационного выхода устройства, а выход селектора (И + 1)-й суммирующейячейки И-й строки матрицы является (:2 Б)м разрядом второго инфГформационного выхода устройства,ек 3, корректирующие ячейки 4, раз" ряды первого информационного входа5 устройства, разряды второго информационного входа 6 устройства, разряды первого информационного вьмода 7 устройства, разряды второго информационного выхода 8 устройства,вход 9 задания режима работы устрой"ства, вход 10 логического нуля устройства, вход 1 логической единицы устройства.Управляющая ячейка устройства содержит первый 12 и второй 13 селекторы, элемент НЕ 14, входы 15 - 17, выходы 18 - 20.Суммирующая ячейка устройства содержит сумматор 21, селектор 22, входы 23 - 26, выходы 27 - 30.(что для некоторого 1равно аа. 01),25Для вычисления квадрата числа тре-буется определить сумму И слагаемых.Причем первое слагаемое равно а,2 2,а все последующие равны либо нулюдля а, = О, либо коду В, сдвинутому на соответствующее чйсло разрядов.Операция извлечения квадратногокорня в устройстве выполняется поизвестному алгоритму с восстановлением остатка, который можно сформулировать из выражения (1). 35Определение цифр результата в этомалгоритме осуществляется итерационным способом на основе последовательного вычитания из кода операнда слагаемых выражения (1), при этом заранее предполагается, что каждая очередная цифра результата Е равна 1, т.е.на первой итерации вычитается код .01на второй - код . Е,О 2", а на 1-й "код .Е 1 Е,Е,.О 245В способах формирования -го слагаемого при возведении в квадрат и-го вычитаемого при извлечении квадратного корня имеется аналогия. Именно это служит основой для объединения 50противоположных операций в едином мат,ричном устройстве.Устройство работает следующим образом.Для возведения в квадрат на входы 559 подают сигнал нулевого уровня, ана входы 5 устройства - нулевой код.Код операнда в И разрядов подают на 3 1171Корректирующая ячейка устройствасодержит сумматор 31, элемент 2 И-ИЛИ32, элемент ИЛИ 33, входы 34 - 38,выходы 39 - 41,Управление устройством осуществляется через вход 9 задания режима работы устройства. При возведении в квадрат на выход 9 подается значение логического нуля, а при извлечении квадратного корня - логической единицы. ОФормулой, используемой в предлагаемом устройстве, является 787 4входы 6 устройства, причем старший разряд кода поступает на первую управляющую ячейку. Так как на входах 15 ячеек 1 - нулевой сигнал то выходы 18 и 20 повторяют информацию с входа 17 (фиг.2) . С выходов 18 и 20 сигналы поступают на входы 23 и 25 ячеек 3 (фиг.3) и участвуют в формировании кодов -х слагаемых в соответствии с формулой (1). В том случае, когда 1-я цифра кода операнда равная, в ячейках 3 1-й строки матрицы выбирается то плечо селектора 22, которое подключено к выходу сумматора 21. Это соответствует суммированию -го слагаемого с ранее накопленной суммой, Когда .-я цифра операнда равна О, на выходах 30 ячеек 3 в 1-й строке матрицы повторяется код, присутствующий на входах 26 этих же ячеек, что эквивалентно суммированию накопленной ранее суммы с нулевым кодом.Присутствие нулевого сигнала на входе 36 ячеек 4 (фиг.4) позволяет организовать между последними цепь рапространения переноса, которая необ. ходима для суммирования кодов, возникающих на выходах .30 и 28 ячеек 3 первого столбца матрицы. Тот же сигнал на входах 36 ячеек 4 настраивает элементы 2 И-ИЛИ 32 последних на рабо. ту в ключевом режиме, что позволяет преотвратить учет переносов, возникающих на выходах 28 ячеек 3, когда -я цифра кода операнда равна О.Код результата операции возведения в квадрат формируется на выходах 8 устройства (на фиг,1 старшие разряды расположены слева). Код, формируемый на выходах 7; - не информационныйДля извлечения квадратного. корня на входы 9 необходимо подать сигнал единичного уровня, а на входы 5 2 И-разрядный код операнда. Так как на входах 15 ячеек 1 (фиг.2) присутствует единичный сигнал, то на выходы 20 передается прямое значение сигнала с входа 16, а на выход 18 - инверсное. Сигнал с выхода 20 2-й ячейки 1 управляет селекторами 22 ячеек 3 1-й строки матрицы, а сигнал с выхода 18 участвует в формировании кодов, необходимых для выполнения вычитания в следующих итерациях, Логическая единица в знаковом разряде каждого х-го вычитаемого формируется посредством сигнала единичного уровня, 1171787поступающего на входы 36 ячеек 4.Этот же сигнал обрывает цепь распространения переноса между ячейками 4, а также пердопределяет безусловное распространение переносов между суммирующими ячейками 3 -й строки матрицы и -й корректирующей ячейкой, так как элемент 2 И-ИЛИ выполняет роль логического повторителя, 1 ООчередные цифры корня равны значению переноса из знаковых разрядов кодов Ьформируемых на выходах переноса сумматоров 31 корректирующих ячеек 4 и на выходах переноса сумма тора 21 первой суммирующей ячейки первой строки матрицы. Эти цифры участвуют в формировании очередных остатков. Если -я цифра корня равна 1, восстановление остатка не произ 2 О водится и селекторы 22 ячеек 3 -й строки матрицы передают на выходы ЗО информации с выходов сумматоров 21.Если -я цифра корня равна О, осуществляется восстановление остатка 25 путем передачи на выходы 30 ячеек 3 сигналов с входов 26.Результат выполнения операции извлечения квадратного корня формируется на выходах 7 устройства. Окон- ЗО чательный остаток формируется на выходах 8 матрицы. Для реализации известного уст- .ройства, являющегося базовым объек- )35том, требуется3 - (1 Я + И ) (3 + 33 )Н З,где Зс3З, , - затраты на реаллизацию селектора и элемента ИСКЛЮЧА-ЮЩЕЕ ИЛИ ячейки известного устройстОва,Затраты на реализацию предложенного устройства равны 3= (-, И + -,В)(Зс + 3) + 2 Ы 3 ++ (И - 1) (3 + З) + ИЗ,где З, 3, З - затраты на реализацию инвертора управляющей ячейки,элемента ИЛИ и элемента 2 И-ИЛИ корректирующей ячейки.Для построения обоих устройств наэлементах 133 или 155 серии типа ИМЗ,КП 2, ЛН 1, ЛЛ 1, ЛП 5 и ЛР 1 потребуется у известного устройства 3, = 288корпусов, а у предложенного 3 = 146корпусов, т.е. в два раза меньше.В известном устройстве для управления ячейками используются две управляющие цепи, а в предложенном - одна,следовательно, предложенное устройство менее загружено топологически.Время извлечения квадратного корня у известного устройства(2,511 + 0,5 1 )+ 1 хгде 1 - время распространения переноса водноразрядном сумматоре;Гц, - время работы селектора и,элемента ИСКЛЮЧАЮЩЕЕИЛИ.Время извлечения корня у предложенного устройства+ й) + 2 йр+ И(1+ 1 у)где ,- задержки инвертораэлемента ЙЛИ и 2 И-ИЛИ.Время возведения.в квадрат у обоих устройств одинаково и равно 2 М хх й + 2. Сопоставив , и, видно, что 0следовательно, предложенное устройство более быстродействующее.11171787 МО Бут 1 Тираж 710 осударственного комитета СС по делам изобретений и открытий 035, Москва, Ж, Раушская наб,писное каз 4864/4 ВНИИПИ Г д, 4/5 Патент Филиал едактор Л.Гратилл Составитель С.СилаевТехредЛ.Мартяшова Коррек город, ул.Проектна