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

 

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

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

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

PECflYSËÈК а91 а»

З(Я! С F 7 552

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

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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н автеескеа св щатв1ЬОтвм

k i> i:я;. с:!

i4 (21) 3570732/18-24 (22) 02.04.83 (46) 30.08.84. Бюл. ¹ 32 (72) С.А.Волощенко (53) 68! .325(0i88. 8 ) (56) !. Авторское свидетельство СССР № 75814Ф, кл. G Об F 7/38, 1977.

2. Najithia Т .С. Cellular Array

for Kxtraction of Squares and Square

Roots of Binary Numbers.-IEEE Transactions on Computers, чо1. С-21, № 9, рр. 1023-1024(прототип). (54)(57) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ

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

КВАДРАТНОГО КОРНЯ, содержащее стол=бец из М коммутаторов и матрицу суммирующих ячеек из !! строк и Ц +1 столбцов, причем каждый столбец коммутаторов содержит два коммутатора и элемент НЕ, суммирующая ячейка содержит одноразрядный сумматор и коммутатор, первая строка матрицы содержит две суммирующие ячейки, а каждая последующая на одну ячейку больше, чем предыдущая, первые входы одноразрядных сумматоров i --х суммирующих ячеек 6=2,..., и, где !

1 - номер строки)6-й строки(и=2,..., Ц соединены с выходами коммутаторов (ъ +1) -х суммирующих ячеек предыду- . щей строки, первые входы одноразрядных сумматоров последних двух сум" мирующих ячеек всех строк соединены соответственно с входами подкоренного числа устройства, вход перено- . са одноразрядного сумматора i -й суммирующей ячейки соединен с выходом переноса одноразрядного сумматора (i+1)-й суммирующей ячейки этой же строки, первый выход каждого коммутатора столбца соединен с управля-ющими входами коммутаторов всех суммирующих ячеек соответствующей строки, первые входы всех коммутаторов столбца- соединены соответственно с входами аргумента устройства, в каждой суммирующей ячейке первый вход коммутатора соединен с выходом одноразрядного сумматора суммирующей ячейки, первый вход которого соеди-. нен с вторым входом коммутатора суммирующей ячейки, выходы коммутаторов суммирующих ячеек последней строки является соответственно выходами младших разрядов результата возведения числа в квадрат устройства, отличающееся тем, что, с целью сокращения аппаратурных затрат, оно содержит столбец из М-1 корректирующих ячеек, каждая из которых содержит одноразрядный сумматор и коммутатор, выход которого соединен с входом переноса одноразрядного сумматора данной корректирующей ячейки, первые входы одноразрядных сумматоров корректирующих ячеек и --х строк (и=2,К)соединены с выходами переноса одноразрядных сумматоров первых суммирующих ячеек этих же строк матри-цы, выходы переноса одноразрядных сумматоров корректирующих ячеек соединены с выходами результата извлечения квадратного корня устройства, вторыми входами соответствующих коммутаторов столбца.и через .элемент НЕ, этого столбца-с третьими входами этих же коммутаторов, первые входы

d которых соединены с их четвертыми входами, вход задания режима соединен с управляющими входами всех коммутаторов столбца, управляющими;.

11 и первыми входами коммутаторов всех ! корректирующих ячеек и вторыми входами одноразрядных сумматоров предпОследних суммирующих ячеек всех строк, выход переноса одноразрядного. сумматора первой строки соединен с выходом старшего разряда результата извлечения корня устройства, вторым входом первого коммутатора столбца и через элемент НЕ этого столбца соединен с третьим входом этого же коммутатора, первый вход которого соединен со своим четвертым входом, вторые выходы ч коммутаторов столбца(и -.-l,... Й -1) соединены с вторыии входами одноразрядных сумматоров

w -х суммирующих ячеек (гч+! -й строки, вторые входы одноразрядных сумматоров В -х суммирующих ячеек (=1,...,м-2) р -й строки (p=3 !!) соединены с вторыми входами одно" разрядных сумматоров 1 -х суммирующих ячеек (р-1) -й строки, второй вход коммутатора корректирующей ячейки

К-й строки (v.=2,..., N — 1) соединен с выходом переноса одноразрядного сумматора корректирующей ячейки (к +1)-й строки, второй вход коммута.тора корректирующей ячейки последней строки соединен с входом логического нуля устройства, выход коммутатора первой суммирующей ячейки с1,-й стро ки(с =1,..., и -1) соединен с вторым входом одноразрядного сумматора корректирующей ячейки (с +))-й строки, выходы одноразрядных сумматоров корректирующих ячеек являются .соответственно выходами старших разрядов результата возведения числа в, квадрат устройства, входы переносбв одноразрядных сумматоров последних

1 суммирующих ячеек всех строк соеди,нены с входами логического нуля устройства, вторые входы одноразрядных сумматоров последних суммирующих ячеек всех строк соединены с входами логической единицы устройства.

Изобретение относится к вычисли тельной технике и может быть использовано в специализированных вычислителях и высокопроизводительных

3ВМ для однотактного выполнения операций возведения н квадрат и из- 5 влечения квадратного корня целых и дробных двоичных чисел.

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

Недостатком известного устройства является отсутствие возможности 20 извлечения квадратного корня.

Наиболее близким по технической сущности к изобретению является устройство для возведения в квадрат и извлечения квадратного корня, 25 содержащее столбец из ь! управляющих ячеек и усеченную матрицу из М -й ячеек, первая строка матрицы содержит две ячейки, а каждая последующая на две ячейки больше, чем предьдущая строка, соответствующие входы столбца управляющих ячеек подключены к первым входам и первым выходам устройства, входы суммы каждых двух последних ячеек каждой строки подключены К вторым входам устройства, выходы суммы ячеек М-й бтроки подключены к вторым выходам устройства, вход суммы ячеек всех строк, за исключением ячеек 1-й строки, подключен к выходу суммы ячейки предыдущей строки последующего столбца, первый вход каждой ячейки, за исключением ячеек !-й строки, двух последних ячеек каждой строки и ячеек 1-ro столбца, подключен к первому выходу ячейки предьдущей строки предьдущего столбца, вторые и третьи входы ячеек всех строк, а шакже входы и выходы переноса этих же ячеек попарно соединены между собой, причем каждая ячейка содержит элемент ИСКЛЮЧМОЩЕЕ ИЛИ, одноразрядный сумматор и коммутатор, все управляющие ячейки содержат коммутатор. Извлечение квадратного корня в известном устройстве осуществляется по алгоритму с восстановлением остатка, а возведение в квадратна основе формулы о квадрате числа, равного сумме квадратов составляющих его чисел плюс удвоенное произведение каждого. числа на все остальные 1. 21.

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

Цель изобретения — сокращение аппаратурных затрат.

Поставленная цель достигается тем, что матричное устройство для возведения в квадрат и извлечения квадратного корня, содержащее столбец из l4коммутаторов и матрицу суммирующих ячеек из N строк и 11+! столбцов, причем каждый столбец ком-. мутаторов соДержит два коммутатора, и элемент НЕ, суммирующая ячейка содержит одноразрядный сумматор и коммутатор, первая строка матрицы содержит две суммирующие ячейки, а каждая последующая на одну ячейку больше, чем предыдущая, первые входы одноразрядных сумматоров i-х суммирующих ячеек (ъ=2,..., и — 1, где и-номер строки)ь-й строки (и =2,..., м соединены с выходами коммутаторов

6 +1)-х суммирующих ячеек предыдущей строки, первые входы одноразряд" ных сумматоров последних двух суммирующих ячеек всех строк соединены соответственно с входами подкоренного числа устройства, вход переноса одноразрядного сумматора -й суммирующей ячейки соединен с выходом переноса одноразрядного сумматора

И +1)-й суммирующей ячейки этой же строки, первый выход каждого коммутатора столбца соединен с управляющими входами коммутаторов всех суммирующих ячеек соответствующей строки, первые входы всех коммутаторов столбца соединены соответственно с входами аргумента устройства, в каж-. дый суммирующей ячейки первый вход., оммутатора соединен с выходом одно10

40 соединен с третьим входом этого же коммутатора, первый вход которого

45 соединен со своим четВертым ВхОдом .вторые выходы п1 коммутаторов столбца

",%=1,... N — 11соединены с вторыми входами одноразрядных сумматоров rn-x суммирующих ячеек (и+1 1-й строки, 50 вторые входы одноразрядных сумматоров 9 --х суммирующих ячеек Я=1, И -2 р-й строки (Р=З,... 1)соединены с

Вторыми Входами одноразрядных сумматоров В -х суммирующих ячеек

55 (p-1) Й стрОки,р ВтОРОй ВХОД кОмму татора корректирующей ячейки К-й строки (К=2,... Я вЂ” 1) соединен с выходом, переноса одноразрядного сумматора корректирующей ячейки (К+1)-й

25 разрядного сумматора, первый вход которого соединен с вторым входом коммутатора, выходы коммутаторов суммирующих ячеек последней строки являются соответственно выходами младших разрядов результата возведения числа в квадрат устройства, содержит столбец из М -1 корректирующих ячеек, причем каждая ячейка содержит одноразрядный сумматор и коммутатор, выход которого соединен с входом переноса одноразрядного сумматора данной корректирующей ячейки первые входы одноразрядных сумматоров корректирующих ячеек и -х строк (n =

=2,...М)соединены с выходами переноса одноразрядных сумматоров первых суммирующих ячеек этих же строк матрицы, выходы переноса одноразрядных сумматоров корректирующих ячеек соединены с выходами результата извлечения квадратного корня устройства, вторыми входами соответствующих коммутаторов столбца и через элемент НЕ этого столбца — с третьими входами этих же коммутаторов, первые входы которых соединены с их четвертыми входами, вход задания режима соединен с управляющими входами всех коммутаторов столбца, управляющими входами всех коммутаторов столбца, управляющими и первыми входами коммутаторов всех корректирующих ячеек и вторыми входами одноразрядных сумматоров предпоследних суммирующих ячеек всех строк, выход переноса одноразрядного сумматора первой строки соединен с выходом старшего разряда результата извлечения корня, вторым входом первого коммутатора столбца и через элемент. НЕ этого столбца

1 1 I 155 ° строки, второй вход коммутатора корректирующей ячейки последней строки соединен с выходом логического нуля устройства, выход коммутатора первой суммирующей ячейки (j "й строки 5 (С =1,... и -1) соединен,с вторым входом одноразрядного сумматора корректирующей ячейки ((),+!) -й строки, выходы одноразрядных сумматоров корректирующих ячеек являются соответственно выходами старших разрядов результата возведения числа в квадрат устройства, входы переноса одноразрядных сумматоров последних суммирующих ячеек всех строк I5 соединены с входами логического нуля устройства,.вторые входы одноразрядных сумматоров последних суммирующих ячеек всех строк соединены с входами логической единицы устройства. 20

На фиг. I приведена структурная схема устройства при !4 =4; на фиг.2 "

4 — функциональные схемы коммутатора столбца, суммирующей и корректирую" щей ячеек. 25

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

"0", входы 10 сигнала "1".

Столбец коммутаторов содержит (фиг. 2)первый 11 и второй 12 коммутаторы, элемент НЕ 13, вход 14 .управления, вход 15 инструм.,информационный вход lб, первый выход 17, выход результата 18, второй выход

19.

Суммирующая ячейка 2 (фиг. 3) со-, держит одноразрядный сумматор 20, коммутатор 21 первый 22, второй

23, третий 24 и четвертый 25 входы, 45 первый 26, второй 27, третий 28 и четвертый 29 выходы.

Корректирующая ячейка 3 (фиг. 4) содержит одноразрядный сумматор 30 и коммутатор 31, первый 32, второй

33, третий 34 и четвертый 35 входы, первый 36 и второй 37 выходы.

Управление. устройством осуществляется через вход управления 8.

При возведении в квадрат на вход

8 подают. "0, а при извлечении

11 И

55 квадратного корня "l". Номера строк и столбцов(фиг. !}возрастают сверху вниз и слева направо. Столбцы в мат. рице ячеек изображены диагонально.

В зависимости от сигнала на входе

8 устройство настраивается на выполнение одной или другой операции.

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

Ниже приведен вывод основной решающей формулы, используемой при возведении в квадрат дробных чисел., А "-(Xa(2 ) =1х;г «DKeыо g и j«I где А -, исходное число;

4И - биты числа А, Й вЂ” разрядность кода операнда.

Второе из слагаемых выражает

I удвоенных произведений каждого бита числа А на все остальные. Ука" заииое;выражение может быть преобразовано к следующему виду: у и р ис4 (с+1

+ =%2.ЕсцГ "ЕХАЙ .Аф

1.2 L-.g j«(54 ((-» + с 12 . Есц.2 (, Ек 2»-сц2

«9 3«» или к виду

А - С(» 2 УС(„В!. 2-

1 2

И где В :- код, равный, с(Я 42

Р» что для некоторого ъ равно

as (:4С)Х." A4H .

Данная формула является основной, используемой в устройстве для вычисления квадрата числа. Ее анализ показывает, что для вычисления квадрата К -разрядного числа, требуется опре (елить сумму Й слагаемых, причем первое равно:!01„.2", а все последующие равны нулю, когда С(,=0, либо сдвинутому на определенное число разрядов коду В1 приС»;=1. Сдвиг осуществляется на (-1 разрядов вправо.

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

Определение цифр результата в этом алгоритме осуществляется итера- ционным способом, на основе последо11!1l

7 вательного вычитания из кода операн- . да слагаемых указанной формулы, предполагая, что очередная цифра результата 7.. равна 1, т.,е. на первой итерации вычитателя код 01, на второй +„ 01.2, на третьей.ЪЪ

0l .2, а на ъ-й ЪД Е;», 01 ° 2

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

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

Алгоритм извлечения квадратного корня описывается такой последовательностью.

Нулевым остатком Во считать код операнда, присвоить l. значение 1, 2р

Вычесть из остатка Я!„ ъ-е вычитаемое. Если результат вычитания

Lz r0 то очередная цифра частного

Ki =i и очередной остаток Ql считать равным 1.-, если же 4>O,то Ki =О, à 25 остаток восстанавливается путем присвоения 2(значения И - .

Увеличить i, на единицу.

Для вычисления !! цифр результата повторить пункты 2 и 3!! раз. !

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

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

8 необходимо подать сигнал нулевого уровня, а на входах 4 устройства должен существовать нулевой код. Код операнда в м разрядов подают на входы 5 устройства, причем старший разряд кода поступает на первую 40 управляющую ячейку. Так как на входах 14 коммутаторов 1 нулевой сигнал, то выходы 17 и 19 повторяют информацию с входа 16. С выходов 17 и 19 сигналы поступают на входы 22 и 24 ячеек 2 и участвуют в формировании кодов Ъ-х слагаемых в соответствии с укаэанной формулой. В том случае, когда -я цифра кода операнда равна 1, в ячеиках 2 1;й строки матрицы . 50 выбирается то плечо коммутатора 21, которое подключено к выходу сумматора 20. Это соответствует суммированию i --ro слагаемого с ранее накопленной суммой. Когда же ъ-я цифра кода операнда равна О, на выходах 29 яЧеек 2 в -й строке повторяется код, присутствующий на входах 25 этих же ячеек, что эквивалентно сум55 мированию накопленной суммы с нуле- вым кодом.

Присутствие нулевого сигнала на входах 34 ячеек 3 позволяет организовать между ячейками 3 цепь распространения переноса, необходимую для суммирования кодов, возникающих на выходах 29 и 27 ячеек 1, 1-го столбца матрицы. Код результата выполнения операции возведения в квадрат формируется на выходах 7 усстройства. Код, формируемый на выходах 6, неинформационный.

Для извлечения квадратного корня на входы 8 необходимо подать сигнал единичного уровня, а на входы 4 -2 м-разрядный код операнда. Так как на входах 14 коммутаторов 1 присутствует единичный сигнал, то на выходы 19 передается прямое значение сигнала с входа 15, а на выход

17 — инверсное. Сигнал с выхода 19

1.-й ячейки 1 управляет коммутаторами 21 ячеек 2 ъ-й .строки матрицы, а с выхода 17 — в формировании последующих вычитаемых в следующих итерациях."1" в знаковом разряде каждого i-го вычитаемого формируется посредством сигнала единичного уровня, поступающего на входы 34 ячеек 3; этот же сигнал обрывает цепь распространения переноса. между ячейками 3.

В соответствии с алгоритмом извлечения корня ячейками 3 очередные цифры результата формируются по значению переноса из знаковых разрядов промежуточных кодов !.1; эти же цифры участвуют в формировании очередных остатков. В том случае, когда ъ-я цифра результата равна 1, то восстановление остатка не производится, коммутаторы 21 ячеек 2 -й строки матрицы передают на выходы 29 информацию с выходов сумматоров 20.

Когда же i, — ÿ цифра результата равна

О, то осуществляется восстановление остатка путем передачи на выходы 29 ячеек 2 сигналов с входов 25.

Результат выполнения операции извлечения квадратного корня формируется на выходах 6 устройства (старшие разряды на фиг. 1 расположены вверху

Окончательный остаток формируется на выходах 7, которые подключены к ячейкам. 2 и -й строки.

Затраты на реализацию прототипа равны а.=(1- )(S .3...S««.»>) .

9 ll где 3 3 3„, „,„- затраты на реализацию одноразрядного сумматора,коммутатора и элемента ИСКПЮЧАЮЩЕЕ ИЛИ.

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

3 =(И+э и Ье+3 }2ЬРЬк (МИ +H3g где Зп " затраты на реализацию инвертора.

Для построения обоих устройств на элементах средней степени интеграции 155 серии при 11=16 потребовалось бы у прототипа ЗА=288 корпусов, 11155 i

1О а у предложенного устройства 3j=l42 корпуса. Следовательно, предложенное устройство в два раза экономичнее прототипа.

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

Таким образом уменьшена связность

10 ячеек между собой по цепям управления.

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

37

Составитель А.Казанский

Редактор О.Колесникова ТехредЛ.Мартяшова Корректор М.Максимишинец

Заказ 6311/39 Тираж 698 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная,4