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

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

Иллюстрации

Показать все

Реферат

 

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

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (! 9) (11) (s))e С 06 F 7 552

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

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

Г

I ф ц () Щ ) р»

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ii3 .

k АВТОРСНОМУ СВИДЕТЕЛЬСТВУ, ииид;р.-,, (21) 3700908/24-24 (22) 15.02.84 (46) 07.08.85, Бюл. Ф 29 (72) С.А.Волошенко (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 758144, кл. G 06 F 7/38, 1977.

7.С.Maj ithia. . Cellular Array fîr

Extraction of Squares and Squares

Pouts of .Binary Numbers. — ТЕЕЕ

Trans. Comput., vol. С-21, рр. 1023-1024, 1972. (54) (57) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ

ВОЗВЕДЕНИЯ В КВАДРАТ И ИЗВЛЕЧЕНИЯ

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

i-й управляющей ячейки, а также к первому входу элемента ИЛИ (i=1) -й корректир ющей ячейки, выход переноса суммато" ра суммирующей ячейки первого столб-. ца i-й строки подключен к первому и второму входам элемента 2И-ИЛИ i-й корректирующей:ячейки, выход первого селектора первой управляющей ячейки подключен к управляющим входам селекторов всех суммирующих ячеек первой строки матрицы, выход первого селектора ).-й управляющей ячейки подключен к третьему входу элемента 2И-ИЛИ

i-й корректирующей ячейки и к управляющим входам селекторов всех суммирующих ячеек i-й строки матрицы, выход элемента НЕ каждой управляющей ячейки подключен к первому информационному входу второго селектора той g же управляющей ячейки, выход второго селектора д-й управляющей ячейки (j.=1,..., N-1) подключен к первому информационному входу всех К-х суммирующих ячеек (К = /j + 1/, ..., N)

j-го столбца матрицы, выход переноса сумматора второй суммирующей ячейки первой строки матрицы подключен к входу переноса сумматора первой сумми рующей ячейки первой строки матрицы, выход переноса сумматбра (-й (g = 2,..., /i + 1/) суммирующей ячейки i"É строки матрицы подключен к входу переноса сумматора (8 — 1)-й суммирующей ячейки i-строки матрицы, второй вход элемента HJIH i-й корректирующей ячейки соединен с четвертым входом элемента 2И-ИЛИ i-й корректи-. «р», рующей ячейки и подключен к входу за-дания режима работы устройства, первый вход элемента HJIH (N — 1)-й корректирующей ячейки подключен к входу логического нуля устройства, управляющие входы первого и второго селекторов всех управляющих ячеек подклю-! чены к входу задания режима работы

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

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

O однотактного выполнения операций .возведения в квадрат и извлечения квадратного корня над целыми и дробными двоичными числами.

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

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

Устройство содержит управляющие ячейки 1, матрицу 2 суммирующих ячеинформационные входы сумматора m-й и (m + 1)-й суммирующих ячеек m-й строки матрицы соединены с вторым информационным входом селектора соответственно m-й и (m + 1)-й суммирующих ячеек m-й строки матрицы и являются соответственно (2m — 1)-м и (2m)-м разрядами первого информационного входа устройства, вторые информационные входы первого и второго селектров ш-й управляющей ячейки соединены между собой и являются m-м разрядом второго информационного входа устройства, выход переноса сумматора первой суммирующей ячейки первой строки матрицы является первым разрядом первого информационного выхода устройства, выход переноса сумматора j-й корректирующей ячейки является (j + 1)-м разрядом первого информационного вьмода устройства, выход сумматора j-й корректирующей ячейки является j-м разрядом второго информационного выхода устройства, выход селектора m-й суммирующей ячейки N-й строки матрицы является (m + N — 1)-м разрядом второго инфор. мационного выхода устройства, а выход селектора (И + 1)-й суммирующей ячейки N-й строки матрицы является (:2И}м разрядом второго ирфГ формационного выхода устройства, ек 3, корректирующие ячейки 4, разряды первого информационного входа

5 устройства, разряды второго информационного входа 6 устройства, разряды первого информационного вьмода

7 устройства разряды второго информационного выхода 8 устройства, вход 9 задания режима работы устройства, вход 10 логического нуля устройства, вход 11 логической единицы устройства.

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

Суммирующая ячейка устройства содержит сумматор 21, селектор 22, входы 23 - 26, выходы 27 — 30.

A = a,2г+ а,- В; 2 " (1)

1=г 15 где А исходное число; биты-числа А; разрядность кода операнда; а

20

" . -1-1 код, равный а1. 2 + 2

1=i

В

1 (что для некоторого равно а ... а. 01).

1-1 Z5

Для вычисления квадрата числа тре- буется определить сумму N слагаемых.

Причем первое слагаемое равно а,2 г, а все последующие равны либо нулю для а, = О, либо коду В1, сдвинутому на соответствующее чйсло разрядов.

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

Определение цифр результата в этом алгоритме осуществляется итерационным спосббом на основе последовательного вычитания из кода операнда слагаемых выражения (1), при этом зара- 40 нее предполагается, что каждая очеред. ная цифра результата Z равна 1, т.е.

1 на первой итерации вычитается код .01 на второй — код . Z 01-2", а на i-йкод ° Z,Z,......Zi 1ut 2 " ".

В способах формирования i-го слагаемого при возведении в квадрат и

i-ro вычитаемого при извлечении квадратного корня имеется аналогия. Именно это служит основой для объединения 50 противоположных операций в едином мат. ричном устройстве.

Устройство работает следующим образом.

Для возведения в квадрат на входы

9 подают сигнал нулевого уровня, а на входы 5 устройства — нулевой код.

Код операнда в N разрядов подают на

3 1171

Корректирующая ячейка устройства содержит сумматор 31, элемент 2И-ИЛИ

32, элемент ИЛИ 33, входы 34 — 38, выходы 39 — 41.

Управление устройством осуществля- 5 ется через вход 9 задания режима рабо ты устройства. При возведении в квадрат на выход 9 подается значение логического нуля, а при извлечении квад. ратного корня — логической единицы. 1О

Формулой, используемой в предлагаемом устройстве, является

787 4 входы 6 устройства, причем старший разряд кода поступает на первую управляющую ячейку. Так как на входах 15 ячеек 1 — нулевой сигнал то выходы

18 и 20 повторяют информацию с входа

17 (фиг.2) . С выходов 18 и 20 сигналы поступают на входы 23 и 25 ячеек

3 (фиг.3) и участвуют в формировании кодов i-х слагаемых в соответствии с формулой (1). В том случае, когда

i-я цифра кода операнда равна11, в ячейках 3 1.-й строки матрицы выбирается то плечо селектора 22, которое подключено к выходу сумматора 21. Это соответствует суммированию а.-го слагаемого с ранее накопленной суммой.

Когда i-я цифра операнда равна О, на выходах 30 ячеек 3 в i-й строке матрицы повторяется код, присутствующий на входах 26 этих же ячеек, что эквивалентно суммированию накопленной ранее суммы с нулевым кодом.

Присутствие нулевого сигнала на входе 36 ячеек 4 (фиг.4) позволяет организовать между последними цепь рапространения переноса, которая необходима для суммирования кодов, возникающих на выходах .30 и 28 ячеек 3 первого столбца матрицы. Тот же сигнал на входах 36 ячеек 4 настраивает (элементы 2И-ИЛИ 32 последних на работу в ключевом режиме, что позволяет преотвратить учет переносов, возникающих на выходах 28 ячеек 3, когда

i-я цифра кода операнда равна О.

Код результата операции возведения в квадрат формируется на выходах

8 устройства (на фиг,1 старшие разряды расположены слева). Код, формируемый на выходах 7; — не информационный °

Для извлечения квадратного. корня на входы 9 необходимо подать сигнал единичного уровня, а на входы 5

2 N-разрядный код операнда. Так как на входах 15 ячеек 1 (фиг.2) присутствует единичный сигнал, то на выходы 20 передается прямое значение сигнала с входа 16, а на выход 18 — инверсное. Сигнал с выхода 20 i-й ячейки 1 управляет селекторами 22 ячеек

3 i-й строки матрицы, а сигнал с выхода 18 участвует в формировании кодов, необходимых для выполнения вычитания в следующих итерациях . Логическая единица в знаковом разряде каждого i-го вычитаемого формируется посредством сигнала единичного уровня, 1171787 поступающего на входы 36 ячеек 4.

Этот же сигнал обрывает цепь распространения переноса между ячейками 4, а также пердопределяет безусловное распространение переносов между суммирующими ячейками 3 i-й строки матрицы и i-й корректирующей ячейкой, так как элемент 2И-ИЛИ выполняет роль логического повторителя. 10

Очередные цифры корня равны значению переноса из знаковых разрядов кодов L,,ôîðìèðóåìûõ на выходах переноса сумматоров 31 корректирующих ячеек 4 и на выходах переноса сумматора 21 первой суммирующей ячейки первой строки матрицы. Эти цифры участвуют в формировании очередных остатков. Если i-я цифра корня равна 1, восстановление остатка не произ 20 водится и селекторы 22 ячеек 3 i-й строки матрицы передают на выходы 30 информации с выходов сумматоров 21.

Если i-я цифра корня равна О, осуществляется восстановление остатка 25 путем передачи на выходы 30 ячеек 3 сигналов с входов 26.

Результат выполнения операции извлечения квадратного корня формируе "ся на выходах 7 устройства. Окон- 30 чательный остаток формируется на выходах 8 матрицы.

Для реализации известного уст- . ройства, являющегося базовым объек 35 том, требуется

3„(N + N ) (3 + З iЗ ) Н 3y, где Зс, 3„, 3„„„„, — затраты на реа лизацию селектора и элемента ИСКЛЮЧА-

ЮЩЕЕ ИЛИ ячейки известного устройстIQ ва.

Затраты на реализацию предложенного устройства равны

3 = (-. N+ -,N )(3, + 3„) + 2.N 3,+

+ (N — 1) (Зили+ З и) + N3Ä где 3„, 3„„„, 3 — затраты на реализацию инвертора управляющей ячейки, элемента ИЛИ и элемента 2И-ИЛИ корректирующей ячейки.

Для построения обоих устройств на элементах 133 или 155 серии типа ИМЗ, КП2, ЛН1, ЛЛ1, ЛП5 и ЛР1 потребует- . ся у известного устройства 3, = 288 корпусов, а у предложенного 3„ = 146 корпусов, т.е. в два раза меньше.

В известном устройстве для управления ячейками используются две управ. ляющие цепи, а в предложенном — одна, следовательно, предложенное устройство менее загружено топологически.

Время извлечения квадратного корня у известного устройства (2,5 N + 0,5 N ) + N x где tp — время распространения переноса в одноразрядном сум маторе; к Гиск..или время p o bi лектора и.элемента ИСКЛЮЧАЮЩЕЕ.

ИЛИ .

Время извлечения корня у предложенного устройства (0,5 N + 0,5 N )tp + N(t +

+ tat) + 2 tp + И(или + tgu ) s где „„и, t 2 — задержки инвертора элемента ЙЛИ и 2И-ИЛИ.

Время возведения.в квадрат у обоих устройств одинаково и равно 2 N x х tp + 2t Сопоставив t() и „, видно, что t > t„ следовательно, предложенное устройство более быстродействующее.

1 171787

Составитель С.Силаев

ТехредЛ.Мартяшова Корректор В.Бутяга

Редактор Л.Гратилло

Заказ 4864/41 Тираж 710

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

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

Подписное

Филиал ППП "Патент", r.Óà oðîä, ул.Проектная, 4