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

коммутаторов результата с 1-го по (N-1 ).оединены соответственно с первыми входами сумматоров по модулю два i-x суммирующих ячеек (,2,.,, N-1) последней строки, второй вход N-ro коммутатора результата соединен с выходом переноса сумматора (N-l)-ft корректирующей ячейки и первым вхо-. дом коммутатора (Ы-2)-й корректирующей ячейки, вь&од переноса сумматора j-й корректирующей ячейки соединен с первым входом коммутатора (-1)-й корректирующей ячейки и первым входо соответствующего коммутатора столбца первый вход первого коммутатора столца соединен с выходом переноса одноразрядного сумматора первой суммирующей ячейки первой строки, выходы одноразрядных сумматоров первых суммирующих ячеек каждой k-й строки, кроме ,соединены с вторыми входами сумматоров соответствующих корректирующих ячеек {и+1)-й строки, входы переносов сумматоров которых соединены с выходами переносов одноразрядных сумматоров первых суммирующих ячеек этой же строки, первый выход п-го коммутатора столбца соединен с первым входом сумматора по модулю два п-й суммирующей ячейки (п+1)-й строки (,2, ... N-1), второй выход п-го коммутатора соединен с вторым информационным входом коммутатора п-й корректирующей ячейки и вторыми входами сумматоров по модулю два первых суммирующих ячеек (п+1)-й строки, первые входы сумматоров по модулю два последних двух суммирующих ячеек каждой строки соединены с входом логической единицы устройства, вторые входы сумматоров по модулю два двух суммирующих ячеек каждой строки и входы переноса их одноразрядных сумматоров, кроме последней

N

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

строк, за исключением

щих ячеек

N

последней суммирующей ячейки

строки, подключены соответственно к

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

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

N суммирующих ячеек вторых -я- строк,

второй вход одноразрядного сумматора последней суммирующей ячейки N-й строки подключен к выходу второго элемента И. 1 Изобретение относится к вычислительной технике и может быть исполь зовано в специализированных вычисли телях и высокопроизводительных ЭВМ для однотактного выполнения операций возведения в квадрат и извлечения квадратного корня целых и дробных двоичных чисел, представленных в прямых кодах при извлечении квадратного корня и в дополнительных при возведении в квадрат. Известно устройство для извлечения квадратного корня, содержащее о норазрядные сумматоры, сумматоры по модулю два, элементы ШШ, элементы НЕ, дополнительные сумматоры по модулю два, элементы И и генератор единиц р . Недостаток данного устройства состоит в отсутствии возможности во ведения в квадрат. Наиболее близким по технической сущности-к изобретению является уст ройство для возведения в квадрат и извлечения квадратного корня, содер жащее столбец из N-1 коммутаторов, матрицу суммирующих ячеек из N стро и N+1 столбцов (N-разрядность входного числа), причем первая строка м рицы содержит две суммирующие ячейки, а каждая последующая на одну ячей ку больше, чем предьщущая, i-я суммирующая ячейка содержит одноразряд ный сумматор и сумматор по модулю два, выход которого соединен с первым входом одноразрядного сумматора выход переноса которсуо соединен с входом переноса одноразрядного сумм тора (1-1)-й суммярзлющей ячейки этой же строки, первый вход сумматора по модулю два i-й суммирующей ячейки k-й строки (,2, ..., N) за исключением трех последних ячеек каждой строки, подключен к первому входу сумматора по модулю два i-й суммирующей ячейки (и-1)-й строки, входы управления всех коммутаторов столбца соединены с первым входом задания режима устройства, второй вход одноразрядного сумматора i-й суммирзпощей ячейки k-й строки соеди нен с выходом одноразрядного сумматора ()-й суммирукяцей ячейки (k-1)-и строки (,2, ..., К-1, где К - номер строки) . Недостаток известного устройства быстрый рост аппаратурных затрат с увеличением разрядности операндов, выраженный законом суммы членов ари 92 метической прогрессии с разностью прогресии, равной двум. Целью изобретения является сокра- щение аппаратурных затрат. Поставленная цель достигается тем, что матричное устройство для возведения в квадрат и извлечения квадратного корня, содержащее из N-1 коммутаторов и матрицу суммирующих ячеек из N строк и N-t-1 столбцов (N - разрядность входного числа), причем первая строка матрицы содержит две суммирующие ячейки, а каждая последующая на одну ячейку больще, чем предьщущая, i-я суммирующая ячейка содержит одноразрядный сумматор и сумматор по модулю два, выход которого соединен с первым входом одноразрядного сумматора, выход переноса которого соединен с входом переноса одноразрядного сумматора (i-1)-й суммирующей ячейки этой же строки, первый вход сумматора по модулю два i-й суммирукяцей ячейки k-й строки (,2, ..., N), за исключением трех последних ячеек каждой строки, подключен к первому входу сумматора по модулю два i-й суммирующей ячейки (k-1)-и строки, входы управления всех коммутаторов столбца соединены с первым входом задания режима устройства, второй вход одноразрядного сумматора i-й суммирующей ячейки k-й строки соединен с выходом одноразрядного сумматора (i+1)-й сзгммирующей ячейки (k-1)-й строки (,2, ..., К-1, где К - номер строки), содержит столбец из (N-1) корректирукяцих о ячеек, строку из N коммутаторов операнда, строку из N коммутаторов результата, группу из (N-1) элементов И, группу из 2N-1 элементов НЕ, два элемента И и два элемента НЕ, причем корректирующая ячейка содержит сумматор и коммутатор, выход которого соединен с первым входом сумматора, вход первого элемента НЕ соединен с входом знака числа устройства, вход второго элемента НЕ соединен с входом N-ro разряда операнда,первым входом первого элемента И и выходом младшегб разряда устройства, первые управляющие входы коммутаторов операнда соединены с первым входом второго элемента И, первыми входами элементов И группы и первым входом задания режима устройства, который соединен с управляющими входами коммутаторов результата, первые входы которых соединены с выходами элементов НЕ группы с первого по N, входы которых соединены соответственно с выходами сумматоров корректир щих ячеек с 2-й по (N-l)-ro и выходами одноразрядных сумматоров двух первых суммирующих ячеек последней стрр ки, выходы одноразрядных сумматоров суммирукмцих ячеек которой соединены с входами соответственно остальных .элементов НЕ группы, вторые входы коммутаторов результата с 1-го по (Ы-1)-й соединены соответственно с первьми входами сумматоров по модулю два 1-х суммирунедих ячеек (,2, ... N-1) последней строки, второй вход N-ro коммутатора результата соединен с выходом переноса сумматора (Н-1)-й корректирукицей ячейки и пеовым вхотом коммутатора (М-2)-й корректирукядей ячейки, выход переноса сумматора корреигтирующей ячейки соединен с первым входом коммутатора (3-1)-й корректирующей ячейки и первым входом соответствующего коммутатора столбца, первый вход первого коммутатора столбца соединён с выходом переноса однораз рядного сумматора первой суммирующей ячейки первой строки, выходы одноразрядных сумматоров первых суммирующих ячеек каждой k-й строки, кро ме N-й, соединены с вторыми входами сумматоров соответствующих корректирукщих ячеек (k+1)-A строки, входы переносов сумматоров которых сое динены с выходами переносов однораз рядных сумматоров первых суммирующи ячеек зТой же строки, первьй выход п-го коммутатора столбца соединен с первым входом су;4матора по модулю два п-й суммирующей ячейки (п+1)-й строки (,2, ..., Kf-t), второй вы ход п-го коммутатора .столбца соединей с вюрым информационным входом коммутатора корректярутацей ячей ки и вторыми входами сумматоров по модулю два первых суммирующих ячеек (п+1)-й строки первые входы сумматоров по модулю два последних двзгх суммирующих ячеек каждой строки сое динены с входом логической единицы устройс-тва, вторые входы сумматоров по модулю два последних двух суммирукяцих ячеек каждой строки и входы переноса их одноразрядных сумматоро кроме последней ячейки -j- строки соединены с входом логического нуля устройства, вход переноса однср.зрядного сумматора последней ячейки -у строки соединен с вьгходом первого элемента И, второй вход которого соединен с вторым входом задания режима устройства, выход первого элемента НЕ соединен с вторым входом первого коммутатора столбца и первым входом первого коммутатора операнда, S-й вход старщего разряда операнда устройства (,2, ..., N-1) соединен с первым входом (S+1)-ro коммутатора операнда, третьим входом S-ro и вторым входом (S+1)-ro коммутатора столбца и вторым входом соответствующего элемента И группы, вход N-ro разряда операнда соединен с вторым входом первого коммутатора операнда, -S-й вход младшего разряда операнда устройства (, .,., 2N-1) соединен соответственно с. вторым входом (S-N+1)-ro коммутатора операнда, вход 2N-ro разряда операнда устройства соединен с вторым входом второго элемента И, выход второго элемента НЕ соединен с вторыми управляющими входами коммутаторов операнда, управляющий вход коммутаторов всех корректирующих ячеек соединен с первым входом задания режима устройства, выходы коммутаторов результата являются соответственно выходами старших разрядов устройства, выходы элементов НЕ группы с N+1 по 2N-1 являются соответственно выходами младших разрядов устройства, вторые входы одноразрядных сумма:торов двух последних суммирующих ячеек первых N „ -J- строк, за исключением последней суммирующей ячейки строки, подключены соответственно к выходам элементов И группы, второй вход одноразрядного сумматора последней суммирующей ячейки строки подключен к выходу первого коммутатора операнда, выходы остальных коммутаторов операнда соответственно подключены к вторым входам одноразрядных сумматоров двух последних суммирующих ячеек вторых -j- строк, второй вход одноразрядного сумматора последней суммирующей ячейки N-й строки подключен к выходу второго элемента И. 51 На фиг. .1 приведена структурная схема устройства при на фиг.2-5 .функциональные схемы коммутатора ; столбца, суммирующей ячейки, корректирующей ячейки и коммутатора oneранда соответственно. Устройство (фиг. 1) содержит N-1 коммутаторов 1, суммирующие ячейки,2 матрицы из N строк и N+1 столбцов, N-1 корректирующих ячеек 3, N коммутаторов операнда 4, N коммутаторов 5 результата, первый 6 и второй 7 элементы НЕ, группу из 2N-1 элементов НЕ 8, группу из N-1 элементов И 9, первый элемент И 10, второй элемент И 11, вход 12 знака числа устройства, входы 13 старших разрядов операнда устройства, входы 14 младших разрядов операнда устройства выходы 15 старших разрядов устройств выходы 16 младших разрядов устройства, первый вход 17 задания режима устройства, второй вход 18 задания режима устройства, вход 19 логической единицы, вход 20 логического нуля. Коммутатор 1 (фиг. 2) содержит два одноразрядных коммутатора 21 и 22, первьй вход 23, второй вход 24, третий вход 25, вход 26 управления, первый выход 27 и второй выход 28. Суммирующая ячейка 2 (фиг. 3) содержит сумматор по модулю два 29 и одноразрядный сумматор 30, а также первьй 31 и второй 32 входы сумматора по модулю два 29, второй вход 33 и выход 34 перенооса одноразрядного сумматора 30, выход 35 и выход 36, подключенные соответственно к первому и второму выходам сумматора 29 по модулю два, выход 37 одно разрядного сумматора и выход 38 переноса одноразрядного сумматора 30, Корректирукйцая ячейка 3 (фиг. 4) содержит коммутатор 39 и сумматор а также первый 41 и второй 42 входы коммутатора 39, второй вход 43 и вх 44 переноса сумматора 40, управляющи вход 45 коммутатора 39, выход 46, г подключенный к второму входу коммутатора 39, выход 47 сумматора 40 и выход 48 переноса сумматора 40. Коммутатор операнда 4 (фиг. 5) содержит элемент И 49 и коммутатор 50, а также первый 51 и второй 52 входы, первый 53 и второй 54 .ттравляющий входы, выход 55 коммутатора операнда, выходы 56 и 57, подключенные соответственно к входам 53 и 54 9 .. 6 Управление устройством осуществляется через входы 17 и 18. При возведения в квадрат на входы 17 и 18 подается код 01,а при извлечении квадратного корня - код 10. Номера строк в устройстве возрастают сверху влиз, а столбцов - слева, направо. Работает устр ойство следующим образом. При возведении в квадрат (на входах 17 и 18 код 01) на входы 13 поступают N разрядов мантиссы, а на вхол 12 - знак операнда, который представлен в дополнительном коде. Кодовая комбинация на входах 14 в операции не участвует и может принимать произвольное значение. Так как на входе 17 сигнал нулевого уровня, то выходы 27 и 28 коммутаторов 1 (фиг. 2) повторяют значения на входах 24 и 25 соответственно. Элементы И 9. за крыты, по этому на вторые входы одноразрядных сумматоров соответствующих С5гммирующих ячеек поступает нулевой код. Сигнал нулевого уровня на входах 45 ячеек 3 (фиг. 4) позволяет сформировать цепь распространения переносов между одно разрядными сумматорами 40 столбца корректирующих ячеек 3. Коммутаторы операнда 4 при сигнале нулевого на входе 53 (фиг. 5) передают на выход 55 значение сигнала присутствующего на входе 51; при этом-элементы И 49 коммутаторов операнда выполняют функции ключевых элементов, управляемых значением сигнала с входа 54. Единичный сигнал на входе 18 открывает единичный элемент И 10. Результат выполнения операции формируется на выходах 15 и 16, причем на выходах 15 формируется N старших разрядов результата, а на выходах 16 - N младщих разрядов результата. На выходах коммутаторов 5 результата формируются сигналы с их первых входов, которые подключены к выходам инверторов 8. Операция возведения в квадрат в устройстве начинается с преобразования числа А, которое выражено дополнительным кодом в N+1 разрядов в двоичной системе счисления с цифрами (0,1) и представленного дробью в виде Од. 01, «2 ... а , в равное ему по величине число: А . . , но представленное в двоичной системе счисления с цифрами (-1, -«-I) в форме 7110 Xct2--2- (1| Ч-1,и) iz-( где N - разрядность мантиссы числа ,ц; цифра числа .j равная . - III -1 или +1. Определение цифр числа А (.|осуществляется через вспомогательный код В равный 2(А,), если (0,Я(2 2 (A(), если А,0. Код 41 получается из кода В заменой в последнем нуле на -1, оставляя при этом без изменения единицы. В устройстве цифра -1 представлена сигналом единичного уровня, а цифра +1сигналом нулевого уровня. После преобразования из системы с цифрами (0,1) в систему (-1, +1), начинается процесс вычисления квадратного корня. Вычисление осуществляется на основе известной формулы о квадрате числа равного квадратов составлякицих его чисел плюс удвоенное произведение каждого числа на все остальные, причем эта формула применяется к всфажению (1). Получаемая таким образом итоговая формула имеет вид N С К + , (3) где С - сумма, код которой используется для обратного преобразования из системы (-1, 4-1) в систему (0,1), получаемая на выходах сумматоров кор ректирующих ячеек 3 и суммирующих ячеек 2 последней строки матрицы; К - корректирующий член, равный А-2 и формируемый на выходе элемента И 10: .Ср - нулевая сумма; равf М-1 N|V,i2-y2 « поразрядной конъюнкции бита в кода со всеми остальными разрядами этого кода, формируемая на выходгих коммутаторов операнда 4; Cj - есть i-e слагаемое, равное Г5ц« а.--.а- ,) (J) cl.,(25-2l , где(,с,, есть поразрядная сумма по модулю два бита (i-l)-ro разряда кода (Q со Bcelbi предществующими ему битаьш этоГо же кода с проинвертированнымзнаковым разрядом (причем G 0,11), формируемое на выходах сумматоров по модулю два суммирующих ячеек i-й строки матрицы. Окончательный результат возведения в квадрат получается после обратного преобразования из системы счисления с цифрами (-1, -И) в систему (0,1), который осуществляется через инвертирование кода суммы, вычислремой по формуле (3), а также сдвига проинв ртированного кода на разряд в сторону старших разрядов. Причем самый младший разряд 2 N-разрядного кода результата непосредственно равен N-му разряду кода операнда, т.е. ч При извлечении квадратного корня (на входах 17 и 18 код 10) на входы 13 (фиг. 1) подают N старших разрядов подкоренного выражения, входы 14 - N младших разрядов. Результат операции формируется на выходах 15 устройства (коммутаторы 5 результата передают информацию со вторых своих входов). Так как на входе 17 сигнал единичного уровня, то выходы 27 и 26 коммутаторов 1 повторяют информацию с входа 23. Сигнал единичного уровня на входе 45 корректирующих ячеек 3 обрывает цепь распространения переносов между сумматорами этих ячеек, на выходах переноса сумматоров которых формируются очередные цифры результата извлечения квадратного корня. Извлечение квадратного корня из 2-разрядного числа осуществляется в устройстве по алгоритму без восстановления остатка, по которому бит п-го разряда результата Z формируется в зависимости от знака п-го остатка, Определяемого по выражению .Q-,,.0 f,,,, . о-(ли} +0.11-2 где Q - остаток п-й итерации; f бит i-ro разряда подкоренного вьфажения 1-2 N) Z - бит п-го разряда результата; L,. - п - разрядный код, равный 0,Z,Zj, ..., ,. , т.е. операции поразрядной суммы по

91107119О

модулю два (n-1)-го разряда результа-этом суммирующая ячейка известного

та со всеми определенными до этогоустройства содержит дополнительный

цифрами, включая и (п-1)-й разряд.KONfMyTaTop, который отсутствует в

При разрядности операнда N число 5устройства. Кроме того, изобретение

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

щено с N+N до

2 N , придополнительных кодах.

суммирующей ячейке предложенного

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

14

Фиг.7 74

Дгг.2

J/ JJo