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

и первыми входами коммутаторов всех корректирующих ячеек и вторыми входами одноразрядных сумматоров предпоследних- суммирующих ячеек всех ; строк, выход переноса одноразрядного сумматора первой строки соединен с выходом старшего разряда результата извлечения корня устройства, вторым входом первого коммутатора столбца и через элемент НЕ этого (й-олбца соединен с третьим входом этого же коммутатора, первый вход которого соединен со своим четвертым входом, вторые выходы коммутаторов столбца {vTif l ,...,, М -1) соединены с вторыми входами одноразрядных сумматоров W-X суммирующих ячеек {irv + -и строки, вторые входы одноразрядных сумматоров С -X суммирующих ячеек (б 1 ,. . ., W-2) р-и строки (,.. .. и) соединены с вторыми входами одноразрядных сумматоров I -X суммирующих ячеек р-0-й строки, второй вход коммутатора корректирующей ячейки

1155

строки (,..., N -1) соединен с выходом переноса одноразрядного сумматора корректирующей ячейки (vc+ 1 -й строки, второй вход коммута-тора корректирующей ячейки последней строки соединен с входом логического нуля устройства, выход коммутатора первой суммирующей ячейки су-и строки о 1,..,, М-1) соединен с вторым входом одноразрядного сумматора корректирующей ячейки ( строки, выходы одноразрядных сумматоров корректирующих ячеек являются соответственно выходами старших разрядов

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

всех строк соединены с

входами логической единицы устройства.

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

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

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

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

Наиболее близким по технической сущности к изобретение является устройство для возведения в квадрат и извлеченияквадратного корня, содержащее столбец из N управляющих ячеек и усеченную матрицу из Ni-M

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

;каждого- числа на все остальные С 21,

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

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

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

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

коммутатора, выходы коммутаторов

/-

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

одноразрядньй сумматор и коммутатор, выход которого соединен с входом переноса одноразрядного сумматора данной корректирующей ячейки, первые входы одноразрядных сумматоров кор5 ректирующих ячеек п -х строк (п

2,...Ы)соединены с выходами переноса одноразрядных сумматоров первых суммирующих ячеек этих же строк матрицы, выходы переноса одноразрядных

Q сумматоров корректирующих ячеек

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

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

соединен с третьим входом этого же коммутатора, первый вход которого д, соединен со своим четвертым входом, - вторые выходы hi коммутаторов столбца 5п 1,...N -1I соединены с вторыми входами одноразрядных сумматоров гп-х суммирующих ячеек ( строки.

вторые входы одноразрядных суммато50

ров D-X суммирующих ячеек (в 1, И-2 р-й строки (,...М)соединены с вторыми Входами одноразрядных

сумматоров В -X суммирующих ячеек 55 (Р-П-Й строки, второй вход коммутатора корректирующей ячейки К-й строки (,...М -П соединен с выходом, переноса одноразрядного сумматора корректирующей ячейки СК+О-й строки,второй вход коммутатора кор ректирующей ячейки последней строки соединен с выходом логического нуля устройства, выход коммутатора первой суммирующей ячейки q -и строки (с 1,... Ы -П соединен с вторым входом одноразрядного сумматора кор ректирующей ячейки (о+П-и строки, выходы одноразрядных су 1маторов корректирующих ячеек являются соответственно выходами старших разрядов результата возведения числа в квадрат устройства, входы переноса одноразрядных сумматоров последних суммирующих ячеек всех строк соединены с входами логического нул устройства,.вторые входы одноразряд ных сумматоров последних суммирующи ячеек всех строк соединены с вх.одам логической единицы устройства. На фиг. 1 приведена структурная схема устройства при на фиг.2 4 - функциональные схемы коммутатор столбца, суммирующей и корректирующей ячеек. ТЛатри ное устройство(фиг. 1) содержит столбец коммутаторов 1, сум мирующие ячейки 2, корректирующие ячейки 3, первые входы 4, вторые входы аргумента 5, выходы результат квадратного корня 6, выходы результата квадрата числа 7, вход 8 управ ления устройством, входы 9 сигнала О, входы 10 сигнала 1. Столбец коммутаторов содержит Сфиг. 2)первый 11 и второй 12 ком- мутаторы, элемент НЕ 13, вход 14 .управления, вход 13 инструм.,информационный вход 16, первый выход 17, выход результата 18, второй выход 19. Суммирующая ячейка 2(фиг. 3)содержит одноразрядный сумматор 20, коммутатор 21, первый 22, второй 23, третий 24 и четвертый 25 входы, первый 26, второй 27, третий 28 и четвертый 29 выходы. Корректирующая ячейка 3(фиг. 4) содержит одноразрядный сумматор 30 и коммутатор 31, первый 32, второй 33, третий 34 и четвертый 35 входы, первый 36 и второй 37 выходы. Управление устройством осуществляется через вход управления 8. При возведении в квадрат на вход 8 подают О, а при извлечении квадратного корня 1. Номера строк и столбцов(фиг, )) возрастают сверху вниз и слева направо. Столбцы в мат рице ячеек изображены диагонально. В зависимости от сигнала на входе В устройство настраивается на выполнение одной или другой операции. Возведение в квадрат в устройстве осуществляется на рещении формулы о квадрате числа, равного сумме квадратов составляющих его чисел плюс удвоенное произведение каждого числа на все остальные. Ниже приведен вывод основной решающей формулы, используемой возредении в квадрат дробных чисел. ХЧ|о...гЛ2|Г.Ы.з2 гм . tM где А -.исходное число; - биты числа А; , N - разрядность кода операнда. Второе из слагаемых выражает удвоенных п роизведений каждого бита числа А на все остальные. Указанное выражение может быть преобразовано к следующему виду: cц.2Mcч2 2i|V.Лif . ., М -1/1-1 -4.| -i « Oir2 - i oq 2 X S Лг2 V«.7 2 Fa . ИЛИ к виду AVo(-2+Jc(,6i.7- i-л . где Hi - код, равный ЧТО для некоторого т, равно C(,Q.... . Данная формула является основной, используемой в устройстве для вычисления квадрата числа. Бе анализ показывает, что для вычисления квадрата Н -разрядного числа, требуется опре челить сумму М слагаемых, причем первое равно pt,-2% а все последующие равны нулю, когда , либо сдвинутому на определенное число разрядов коду B-i прий-, 1 . Сдвиг осуществляется на (л-1 разрядов вправо. Операция извлечения квадратного корня в устройстве выполняется по известному алгоритму извлечения корня с восстановлением остатка, который можно сформулировать и из выражения, используемого для возведения в квадрат. Определение цифр результата в этом алгоритме осуществляется итерационным способом, на основе последо7нательного вычитания из кода операн да слагаемых указанной формулы, предполагая, что очередная цифра результата -j равна I, т..е. на первой итерации вычитателя код 01, на второй , 01 .2 , на третьей. 2 , а на i-и....{., Очевидна прямая аналого.вая в способах формирования d-го слагае: мого при возведении в квадрат и t-го вычитаемого при извлечении квадратного корня. Именно это служи основной для объединения двух противоположных вычислительных операций в едином матричном устройстве. Алгоритм извлечения квадратного корня описывается такой последовательностью . Нулевым остатком Во считать код операнда, присвоить г значение Вычесть из остатка Q i-e вычитаемое. Если результат вычитания , то очередная цифра частного и очередной остаток Qi считать равным Ц, если же , то-2: 0, а остйток восстанавливается путем присвоения QI значения Q-i-лУвеличить i на единицу. , Для вычисления N цифр результат повторить пункты 2 и ЗЫ раз. Устройство работает следующим образом. Для возведения в квадрат на вхрд 8 необходимо подать сигнал нулевого уровня, а на входах 4 устройства до жен существовать нулевой код. Код операнда в ы разрядов подают на вхо ды 5 устройства, причем старший разряд кода поступает на первую управляющую ячейку. Так как на вход 14 коммутаторов 1 нулевой сигнал, то выходы 17 и 19 повторяют информа цию с входа 16. С выходов 17 и 19 сигналы поступают на входы 22 и 24 ячеек 2 и участвуют в формировании кодов Т.-Х слагаемых в соответствии с указанной формулой. В том случае когда -я цифра кода операнда равна 1, в ячейках 2 i-й строки матриц выбирается то плечо коммутатора 21 которое подключено к выходу суммато РЭ 20. Это соответствует суммированию г-го слагаемого с ранее накопленной суммой. Когда же г-я цифра кода операнда равна О, на выходах 2 яЧеек 2 в i-й строке повторяется код, присутствующий на входах 25 этих же ячеек, что эквивалентно сум мированию накопленной суммы с нулевым кодом. Присутствие нулевого сигнала на входах 34 ячеек 3 позволяет организовать между ячейками 3 цепь распространения переноса, нербходимую для суммирования кодов, возникающих на выходах 29 и 27 ячеек 1, 1-го столбца матрицы. Код результата выполнения операции возведения в квадрат формируется на выходах 7 усстройства. Код, формируемый на выходах 6, неинформационный. .Дпя извлечения квадратного корня на входы 8 необходимо подать сигнал единичного уровня, а на входы 4 -2 К1-разрядный код операнда. Так как на входах 14 коммутаторов I присутствует единичный сигнал, то на вьтходы 19 передается прямое значение сигнала с входа 15, а на выход 17 - инверсное. Сигнал с выхода 19 i-й ячейки 1 управляет коммутаторами 21 ячеек 2 ъ-й.строки матрицы, а с выхода 17 - в формировании последующих вычитаемых в следующих итерациях. в знаковом разряде каждого г-го вычитаемого формируется посредством сигнала единичного уровня, поступающего на входы 34 ячеек 3; этот же сигнал обрывает цепь распространения переноса.между ячейками 3. В соответствии с алгоритмом извлечени корня ячейками 3 очередные цифры результата формируются по значению переноса из знаковых разрядов промежуточных кодов 1.; э1и же цифры участвуют в формировании очередных остатков. В том случае, когда г--я цифра результата равна 1 , то восстановление остатка не производится, коммутаторы 21 ячеек 2i -и строки матрицы передают на выходы 29 информацию с выходов сумматоров 20. Когда же 1-я цифра результата равна 0 то осуществляется восстановление остатка путем передачи на выходы 29 ячеек 2 сигналов с входов 25. Результат выполнения операции извлечения квадратного корня формируется на выходах 6 устройства старщие разряды на фиг. 1 расположены вверх5 Окончательный остаток формируется на выходах 7, которые подключены к ячейкам. 2 N-и строки. Затраты на реализацию прототипа равны 3 -(:N-NXicv3,.Wu)

9И

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

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

1if i Н N }f5c+Sk:V 2N-5e (N-1 )3j, 31,

где 3ц - затраты на реализацию инвертора.

Для построения обоих устройств на элементах средней степени интеграции 155 серии при N 16 потребовалось бы у прототипа корпусов у

5/10

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

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

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

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

связанным с уменьшением количества элементов.

(риг.1

Пг V

ybi(| 19 п L

№ 7f-f

.4 ф

JI-

(риг. 2

36

25

22

f

п

жп

7J 1

i2

-Ц

25 tpui.3