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

СОЮЗ СОВЕТСНИХШЮЛЮВЦекиипРЕСПУБЛИК зд) С 06 Р 7/552 с входами элементов ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) 1. Авторское свидетельство СССРФ 857981, кл. С 06 Р 7/552, 1979.2. 0 .С. Ма 1 СЬда. Се 11 и 1 аг АггауЕог Ехггасйдоп оГ ЯЧцагез апй БЧпагеКоогз оЕ Вдпагу КпшЬегз. - 1 ЕЕЕ, Тгапз.СошрШ. Чо 1. С, У 9, р. 10231024 (прототип).(54) (57) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В КВАДРАТ И ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее столбец из Ккоммутаторов и матрицу суммирующих ячеек из К строк и К+1 столбцов (К - разрядность входного числа), причем первая строка матрицы содержит две суммирующие ячейки, а каждая последующая на одну ячейку больше, чем предыдущая, -я суммирующая ячейка содержит одноразрядный сумматор и сумматор по модуля два, выход которого соединен с первым входом одноразрядного сумматора, выход переноса которого соединен с входом переноса одноразрядного сумматора (д)-й суммирующей ячейки этой же строки, первый вход сумматора по модулю два -й суммирующей ячейки Е-й строки (1 с=1,2,К), за исключением трех последних ячеек каждой строки, подключен к первому входу сумматора по модулю два д-й суммирующей ячейки (Е)-й строки, входы управления всех коммутатороУ столбца соединены с первым входом задания режима устройства, второй вход одноразрядного сумматора -й суммирующей ячейки Е-й строки соединен с выходом одноразрядного сумматора (+1)-й суммирующей ячейки Ь)-й строки ( 1,2, К, где К - номер строки), о т л и ч а ю - щ е е с я тем, что, с целью сокращения аппаратурных затрат, оно со держит столбец из (К) корректирующих ячеек, строку из К коммутаторов операнда, строку К коммутаторов результата, группу из (К). элементов И, группу из 2 Кэлементов НЕ, два элемента И и два элемента НЕ, причем корректирующая ячейка содержит сумматор и коммутатор, выход которого сое-динен с первым входом сумматора, вход первого элемента НЕ соединен с входом знака числа устрой"тва, вход второго рею элемента НЕ соединен с входом К-го ффффф разряда операнда, первым входом Бер- а вого элемента И и выходом младшего разряда устройства, первые управляющие входы коммутаторов операнда сое- ффффф динены с первым входом второго эле) мента И, первыми входами элементов И ф . группы и первым входом задания режи- Ме ма устройства, которьй соединен с май управляющими входами коммутаторов ре- (;ф зультата, первые входы которых соединены с выходами элементов НЕ группы с первого по К, входы которых соединены соответственно с выходами сумматоров корректирующих ячеек с ф 2-й по (К)-ю и выходами одноразрядных сумматоров двух первых суммирующих ячеек последней строки, выходы одноразрядных сумматоров остальных суммирующих ячеек которой соединены соответственно остальных НЕ группы, вторые входыкоммутаторов результата с 1-го по (М)-й соединены соответственно с первыми входами сумматоров по модулю два д-х суммирующих ячеек (1=1,2, И) последней строки, второй вход И-го коммутатора результата соединен с выходом переноса сумматора (М)-й корректирующей ячейки и первым вхо-. дом коммутатора (И)-й корректирующей ячейки, выход переиоса сумматора 1-й корректирующей ячейки соединен с первым входом коммутатора (1-1)-й корректирующей ячейки и первым входом соответствующего коммутатора столбца, первый вход первого коммутатора столбца соединен с выходом переноса одноразрядного сумматора первой суммирующей ячейки первой строки, выходы одноразрядных сумматоров первых суммирующих ячеек каждой Е-й строки, кроме И-й,соединены с вторыми входами сумматоров соответствующих корректирующих ячеек (1 с+1)-й строки, входы переносов сумматоров которых соединены с выходами переносов одноразрядных сумматоров первых суммирующих ячеек этой же строки, первый выход и-го коммутатора столбца соединен с первым входом сумматора по модулю два и-й суммирующей ячейки (и+1)-й строки (п=1,2,М), второй выход и-го коммутатора соединен с вторым информационным входом коммутатора и-й корректирующей ячейки и вторыми входами сумматоров по модулю два первых суммирующих ячеек (и+1)-й строки, первые входы сумматоров по модулю два последних двух суммирующих ячеек каждой строки соединены с входом логической единицы устройства, вторые входы сумматоров по модулю два двух суммирующих ячеек каждой строки и входы переноса их одноразрядных сумматоров, кроме последнейМячейки 2 строки, соединены с входом логического нуля устройства, вход переноса одноразрядного суммаИтора последней ячейки - строки сое 2динен с выходом первого элемента И, второй вход которого соединен с вторым входом задания режима устройства, выход первого элемента НЕ соединен с вторым входом первого коммутатора столбца и первым входом первого коммутатора операнда, Б-й вход старшего разряда операнда устройства (Б=1,2,И) соединен с первым входом (Б+ 1)-го коммутатора операнда, третьим входом Б-го и вторым входом (Б+1)-го коммутатора столбца и вторым входом соответствующего элемента И группы, вход И-го разряда операнда соединен с вторым входом первого коммутатора операнда, Б-й вход младшего разряда операнда устройства (Б=М+1,2 И) соединен соответственно с вторым входом (Б-И+1)-го коммутатора операнда, вход 2 И-го разряда операнда устройства соединен с вторым входом второго элемента И, выход второго элемента НЕ соединен с вторыми управляющими входами коммутаторов операнда, управляющий вход коммутаторов всех корректирующих ячеек соединен с первым входом задания режима устройства, выходы коммутаторов результата являются соответственно выходами старших разрядов устройства, выходы элементов НЕ группы с И+1 по 2 Иявляются соответственно выходами младших разрядов устройства, вторые входы одноразрядных сумматоров двух последних суммируюИщих ячеек 2 строк, за исключениемИ последней суммирующей ячейки строки, подключены соответственно к выходам элементов И группы, второй вход одноразрядного сумматора последИ ней суммирующей ячейки 2 строкиподключен к выходу первого коммутатора операнда, выходы остальных коммутаторов операнда соответственно подключены к вторым входам одноразрядных сумматоров двух последнихИсуммирующих ячеек вторых 2 строк, второй вход одноразрядного сумматора последней суммирующей ячейки И-й строки подключен к выходу второго элемента И.1 1107Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях и высокопроизводительных ЭВМ для однотактного выполнения операции возведения в квадрат и извлечеч5 ния квадратного корня целых и дробных двоичных чисел, представленных в прямых кодах при извлечении квадратного корня и в дополнительных -10 при возведении в квадрат.Известно устройство для извлечения квадратного корня, содержащее одноразрядные сумматоры, сумматоры по модулю два, элементы ИЛИ, элементы НЕ, дополнительные сумматоры по мо 35 дулю два, элементы И и генератор единиц 1 .Недостаток данного устройства состоит в отсутствии возможности возведения в квадрат.Наиболее близким по технической сущности к изобретению является устройство для возведения в квадрат и извлечения квадратного корня содерЭ25 жащее столбец из 0-1 коммутаторов, матрицу суммирующих ячеек из Н строк и 0+1 столбцов (К-разрядность входного числа), причем первая строка матрицы содержит две суммирующие ячейки,а каждая последующая на одну ячей-, Зп ку больше, чем предыдущая, -я суммирующая ячейка содержит одноразрядный сумматор и сумматор по модулю два, выход которого соединен с первым входом одноразрядного сумматора, выход переноса которого соединен с входом переноса одноразрядного сумматора (з)-й суммирующей ячейки этой же строки, первый вход сумматора по модулю два х-й суммирующей4 О ячейки 1 с-й строки Ос=1,2, , М) за исключением трех последних ячеек каждой строки, подключен к первому входу сумматора по модулю два ь-й суммирующей ячейки Ь)-й строки, 45 входы управления всех коммутаторов столбца соединены с первым входом задания режима устройства, второй вход одноразрядного сумматора -й суммирующей ячейки 1-й строки соеди нен с выходом одноразрядного сумма" тора (1+1)-й суммирующей ячейки (1 с)-й строки (д=1,2, , К, где К - номер строки) 2 .Недостаток известного устройства -55 быстрый рост аппаратурных заграт с увеличением разрядности операндов, выраженный законом суммы членов ариф 119 2метической прогрессии с разностью прогресии, равной двум.Целью изобретения является сокра щение аппаратурных затрат.Поставленная цель достигается тем, что матричное устройство для возведения в квадрат и извлечения квадратного корня, содержащее столбец из Ккоммутаторов и матрицу суммирующих ячеек из И строк и 0+1 столбцов (И - разрядность входного числа), причем первая строка матрицы содержит две суммирующие ячейки, а каждая последующая на одну ячейку больше, чем предыдущая, -я суммирующая ячейка содержит одноразрядный сумматор и сумматор по модулю два, выход которого соединен с первым входом одноразрядного сумматора, выход переноса которого соединен с входом переноса одноразрядного сумматора (-1)-й суммирующей ячейки этой же строки, первый вход сумматора по модулю два 1-й суммирующей ячейки 1 с-й строки (1 с=1,2, , Н), за исключением трех последних ячеек каждой строки, подключен к первому входу сумматора по модулю два -й суммирующей ячейки (Е)-й строки, входы управления всех коммутаторов столбца соединены с первым входом задания режима устройства, второй вход одноразрядного сумматора -й суммирующей ячейки Е-й строки соеди нен с выходом одноразрядного сумматора (1+1)-й. суммирующей ячейкиЬ)-й строки (1=1,2, , К, где К - номер строки), содержит столбец из (И) корректирующих о ячеек, строку из Н коммутаторов операнда,строкуиз Н коммутаторов результата, группу иэ (0-1) элементов И, группу из 2 Иэлементов НЕ, два элемента И и два элемента НЕ, причем корректирующая ячейка содержит сумматор и коммутатор, выход которого соединен с первым входом сумматора, вход первого элемента НЕ соединен с входом знака числа устройства, вход второго элемента НЕ соединен с входом М-го разряда операнда, первым входом первого элемента И и выходом младшегб разряда устройства, первые управляющие входы коммутаторов операнда соединены с первым входом второго элемента И, первыми входами элементов И группы и первым входом задания режима устройства, который соединен с управляющими входами ком(Я-И+1)-го коммутатора операнда,25 вход 2 И-го разряда операнда устройства соединен с вторым входом второгоэлемента И, выход второго элементаНЕ соединен с вторыми управляющимивходами коммутаторов операнда, упЗ 0 равляющий вход коммутаторов всехкорректирующих ячеек соединен с первым входом задания режима устройства, выходы коммутаторов результатаявляются соответственно выходамистарших разрядов устройства, выходыэлементов НЕ группы с И+1 по 2 И.являются соответственно выходами младших разрядов устройства, вторые входы одноразрядных сумматоров двух пос 40 ледних суммирующих ячеек первыхИстрок, за исключением последнейсуммирующей ячейки -- строки, подИ3ключены соответственно к выходам45 элементов И группы, второй вход одноразрядного сумматора последнейЯсуммирующей ячейки строки под-.2ключен к выходу первого коммутатора50 операнда, выходы остальных коммутаторов операнда соответственно подключены к вторым входам одноразрядныхсумматоров двух последних суммируюИщих ячеек вторых строк, второйвход одноразрядного сумматора посф ледней суммирующей ячейки Я-й строкиФподключен к выходу второго элемента И,мутаторов результата, первые входы которых соединены с выходами элементов НЕ группы с первого по И, входы которых соединены соответственно с выходами сумматоров корректирующих ячеек с 2-А по (И)-ю и выходами одноразряднык сумматоров двух первых суммирующих ячеек последней строки, выходы одноразрядных сумматоров суммирующих ячеек которой соединены с входами соответственно остальных .элементов НЕ группы, вторые входы коммутаторов результата с 1-го по (Й"1)-й соединены соответственно с первыми входами сумматоров по модулю два -х суммирующих ячеек (д=1,2,Я) последней строки, второй вход Я-го коммутатора результата соединен с выходом переноса сумматора (Я,-1)-й корректирующей ячейки 20 и первым вхочом коммутатора (И)-й корректирующей ячейки, выход перено.са сумматора 1-й корректирующей ячейки соединен с первым входом коммутатора (1-1)-й корректирующей ячейки и первым входом соответствующего коммутатора столбца, первый :вход первого коммутатора столбца соединен с выходом переноса одноразрядного сумматора первой суммирующей ячейки первой строки, выходы одноразрядных сумматоров первых суммирующих ячеек каждой к-й строки, кроме М-й, соединены с вторыми входами сумматоров соответствующих корректирующих ячеек (1+1)-й строки, входы переносов сумматоров которых соединены с выходами переносов одноразрядных сумматоров первых суммирующих ячеек этой же строки, первый выход п-го коммутатора столбца соединен с первым входом сумматора по модулю два и-й суммирующей ячейки (и+1)-й строки (и 1,2, , Я), второй выход и-го коммутатора, столбца соединен с вторым информационным входом коммутатора и-й корректирующей ячейки и вторыми входами сумматоров по модулю два первых суммирующих ячеек (а+1)-й строких первые входы сумматоров по модулю два последних двух суммирующих ячеек каждой строки соединены с входом логической единицы устройотва, вторые входы сумматоров по модулю два последних двух суммирующих ячеек каждой строки и входыпереноса их одноразрядных сумматоровИкроме последней ячейки 2 строки,соединены с входом логического нуля устройства, вход переноса однс,; зрядного сумматора последней ячейки И2строки соединен с выходом первого элемента И, второй вход которого соединен с вторым входом задания режима устройства, выход перврго элемента НЕ соединен с вторым входом первого коммутатора столбца и первым входом первого коммутатора операнда, Б-й вход старшего разряда операнда устройства (Я 1,2, , И) соедиивторым входом (Я+1)-го коммутаторастолбца и вторым входом соответствующего элемента И группы, вход И-горазряда операнда соединен с вторымвходом первого коммутатора операнда,Я-й вход младшего разряда операнда1107119 5На фиг 1 приведена структурная схема устройства при 0=4; на фиг.2-5- функциональные схемы коммутатора столбца, суммирующей ячейки, корректирующей ячейки и коммутатора опе 5 ранда соответственно.Устройство (фиг. 1) содержит Якоммутаторов 1, суммирующие ячейки,2 матрицы из К строк и Я+1 столбцов, Юкорректирующих ячеек 3, И ком мутаторов операнда 4, Ю коммутаторов 5 результата, первый 6 и второй 7 элементы НЕ, группу из 2 Яэлементов НЕ 8, группу из Мэлементов И 9, первый элемент И 10, второй элемент И 11, вход 12 знака числа устройства, входы 13 старших разрядов операнда устройства, входы 14 младших разрядов операнда устройства, выходы 15 старших разрядов устройства,20 выходы 16 младших разрядов устройства, первый вход 17 задания режима устройства, второй вход 18 задания режима устройства, вход 19 логической единицы, вход 20 логического ну-. 25 ля.Коммутатор 1 (фиг. 2) содержит два одноразрядных коммутатора 21 и 22, первый вход 23, второй вход 24, третий вход 25, вход 26 управления,.ф 30 первый выход 27 и второй выход 28.Суммирующая ячейка 2 (фиг. 3) содержит сумматор по модулю два 29 н одноразрядный сумматор 30, а также первый 31 и второй 32 входы сумматора по модулю два 29, второй вход35 33 и выход 34 переноаа одноразрядного сумматора 30, выход 35 н выход 36, подключенные соответственно к первому и второму выхоДам сумматора 29 по модулю два, выход 37 одно 40 разрядного сумматора и выход 38 переноса одноразрядного сумматора 30,Корректирующая ячейка 3 (фиг. 4) содержит коммутатор 39 и сумматор 40, а также первый 41 и второй 42 входы45 коммутатора 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. 6Управление устройством осуществляется через входы 17 и 18. При возведения в квадрат на входы 17 и 18 подается код "01",а при извлечении квадратного корня - код "10".Номера строк в устройстве возрастают сверху вниз, а столбцов - слева,направо.Работает устройство следующим образом.При возведении в квадрат (на входах 17 и 18 код "01") на входы.13 поступают К разрядов мантиссы а на вход 12 - знак операнда, который представлен в дополнительном коде. Кодовая комбинация на входах 14 в операции не участвует и может принимать произвольное значение. Так как на входе 17 сигнал нулевого уровня, то выходы 27 и 28 коммутаторов 1 (фиг. 2) повторяют значения на входах 24 и 25 соответственно. Элементы И 9 закрыты, поэтому на вторые входы одноразрядных сумматоров соответствующих суммирующих ячеек поступает нулевой код. Сигнал нулевого уровня на входах 45 ячеек 3 (фиг. 4) позволяет сформировать це ьраспространения переносов между одно разрядными сумматорами 40 столбцакорректирующих ячеек 3, Коммутаторы операнда 4 при сигнале нулевого уров- ня на входе 53 (фиг. 5) передают на выход 55 значение сигнала присутствующего на входе 51; при этом элементы И 49 коммутаторов операнда выполняют функции ключевых элементовУ управляемых значением сигнала с входа 54. Единичный сигнал на входеф 18 открывает единичный элемент И 10.Результат выполнения операции формируется на выходах 15 и 16, причем на выходах 15 формируется Ю старших разрядов результата, а на выходах 16 - Я младших разрядов результата. На выходах коммутаторов 5 результата формируются сигналы с их первых входов, которые подключены к выходам инверторов 8.Операция возведения в квадрат в устройстве начинается с преобразования числа А(1, которое выражено дополнительным кодом в Я+1 разрядовв. двоичной системе счисления с цифрами (О, 1) и представленного дробью в виде цю,ас( в равное ему по величине число. А, 1 но пред,11ставленное в двоичной системе счисления с цифрами (-1, +1) в Форме .-1 или +1.Определение цифр числа А( + 1 осуществляется через вспомогагельный код В равный 19 8знаковым разрядом (причем С =0,11),Уформируемое на выходах суммато"овпо модулю два суммирующих ячее 1-йстроки матрицы,Окончательный результат возведения в квадрат получается после обратного преобразования из системы счисления с цифрами (-1, +1) в систему(О, 1), который осуществляется черезинвертирование кода суммы, вычисляемой по формуле (3), а также сдвигапроинвертированного кода на разрядв сторону старших разрядов. Причемсамый младший разряд 2 И-разрядногокода результата непосредственно равенИ-му разряду кода операнда, т,е. о .Код А 1 получается из кода В замег 1 И ной в йоследнем нуле на -1, оставляя нри этом беэ изменения единицы, В устройстве цифра -1 представлена сигналом единичного уровня, а цифра +1- сигналом нулевого уровня.После преобразования иэ системы с цифрами (0,1) в систему (-1, +1), начинается процесс вычисления квадратного корня, Вычисление осуществляется на основе известной формулы о квадрате числа равного сумме квадратов составляющих его чисел плюс удвоенное произведение каждого числа30 на все остальные, причем эта формула применяется к выражению (1).Полуяаемая таким образом итоговая формула имеет видМ : С:К+С, +Е С (3) З 51 ф 1 где С - сумма, код которой используется для обратного преобразования из. системы (-1, +1) в систему (О, 1), получаемая на выходах сумматоров кор 40 ректирующих ячеек 3 и суммирующих ячеек 2 последней строки матрицы; К - корректирующий член, равный Ь 2 " и. формируемый на выходе элечента И 10: Св - нулевая сумма; равй 45Яная, а,22 ф т,е. поразЙ 0 1 4 1 рядной конъюнкции бита 4 кода А( со всеми остальными разрядами этого50 кода, формируемая на выходах комму- таторов операнда 4; С 1 - есть д-е слагаемое, равное Б а, а ."ф; 1 О++О 1112 ( О, где(Б а,а а, )Фа., есть поразрядная сумма по модулю два бита (1"1)-го разряда кода А(0со всеми предшествующими ему битами этого же кода с проинвертированным.При извлечении квадратного корня (на входах 17 и 18 код "10") на входы 13 (фиг. 1) подают И старших разрядов подкоренного выражения, а на входы 14 - И мпадших разрядов. Результат операции формируется на выходах 15 устройства (коммутаторы 5 результата передают информацию со вторых своих входов). Так как на входе 17 сигнал единичного уровня, то выходы 27 и 26 коммутаторов 1 повторяют информацию с входа 23. Сигнал единичного уровня на входе 45 корректирующих ячеек 3 обрывает цепь распространения переносов между сумматорами этих ячеек, на выходах переноса сумматоров которых формируются очередные цифры результата извлечения квадратного корня.Извлечение квадратного корня из 2-разрядного числа осуществляется в устройстве по алгоритму без восстановления остатка, по которому бит и-го разряда результата 2 формируется в зависимости от знака и-го остатка, Определяемого по выражению(4) при и=1-И и причем 1, если О,0; Е где Я 1 - остаток и-й итерации; Г, бит д-го разряда подкоренного выражения (=1-2 И) 2 - бит и-го разряда результата; 2,11- и " разрядный код, равный О,Е 1,2 , Е,9 Е- т.е, операции поразрядной суммы помодулю два п)-го разряда результата со всеми определенными до этогоцифрами, включая и (и)-й разряд. При разрядности операнда И число 5 суммирующих ячеек в устройстве сокращено с И+И до 2 И + 2 М , при3 1 этом суммирующая ячейка известногоустройства содеРжит дополнительныйкоммутатор, который отсутствует всуммирующей ячейке предложенногоустройства. Кроме того, изобретениедает воэможность оперировать с чис"лами обеих знаков, представленных вдополнительных кодах.Тираа 699осударственного комитета СССам изобретений и открытийва, %-35, Раушская наб., д.