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

СОЮЗ СОВЕТСНИИСОЦИАЛИСТИЧЕСНИРЕСПУБЛИК 9) 7 552 ВЕННЫЙ НОМИТЕТ СССРИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ГОСУД ПО ДЕ гТ,(. л 1 Де 1 ОЛИСАНИЕ ИЗОБРЕТЕНИЯ МБЛ).),ЛЬСТВУ ВТОРСКОМУ иикороич(21) 4119095/24-24(46) 15.03.88. Бюл. У 10 (71) Московский лесотехнический институт(56) Авторское свидетельство СССР У 1084788, кл, С 06 Р 7/552, 1984.Авторское свидетельство СССР У 732863, кл. С 06 Р 7/552, 1980, (54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ(57) Изобретение относится к цифровой вычислительной технике и может бьггь использовано в универсальных и специализированных вычислительных системах для аппаратной реал операции извлечения квадратн ня из чисел, представленных в двной системе счисления в форме сфиксированной и плавающей запятой.Цель изобретения - повышение быстродействия устройства при одновременном повышении точности вычислений ирасширении области применения засчет возможности обработки чисел,представленных в форме с плавающейзапятой. Поставленная цель достигается тем, что в устройство, содержащее три регистра 1-3, два сумматора4, 5, три блока сдвига 8, 9, 10,блок управления 11, введены двамультиплексора 6, 7 и блок формирования результата 12. 2 з.п. ф-лы,1381497 4 оставитель Н. Шелобановаехред М,Дидык Корректор.С. Шекмар ыбченко актор каэ 118 4ного комитета СС одписно Проиэводственно-полиграфическое предприятие Тирам 7 ВНИИПИ Государстве по делам иэобрет 035, Москва, Ж, ний и открытийРаушская наб.,агород, ул. Проектная, 4(10) Устройство относится к цифровойвычислительцой технике. и может быть использовано в универсальных и специализированных вычислительных системах для аппаратной реализации операции извлечения квадратного корня иэчисел, представленных н двоичнойсистеме счисления н форме с фиксированной и плавающей запятой. 10Цель изобретения - повышение быстродействия при одновременном повышении точности и расширении областиприменения за счет возможности обработки чисел, предстанлецных в форме 15с плавающей запятой,На фиг 1 предстанлена структурная схема устройства для извлеченияквадратного корня; ца фиг, 2 -функциоцальцая схема мультиплексора; на 20фиг. 3 - схема блока сдвига; нафиг. 4 - схема блока управления нана фиг. 5 - схема блока формированиярезультата.Устройство содержит регистры 1, 2 25и 3 (см. Фиг, 1), первый 4 и второй 5сумматоры, мультиплексоры 6 и 7,блоки 8, 9 и 10 сдвига, блок 11 управления, блок 12 формирования результата, нход 13 задания порядка, 30вход 14 задания мантиссы устройства,тактовый вход 15, вход 16 запускаустройстваныход 17 порядка, выход18 мантиссы, выход 19 конца операцииустройства.Мультиплексор (см, фиг. 2) содержит ш+2 группы элементов И 20, ш+1элементов ИЛИ 21, элемент НЕ 22, информационные входы 23 и 24, управляющие входы 25, 26 и выход 27,Блок сдвига (см. Фиг. 3) содержити+1-1 групп элементов И 28, из которых д-я группа (=1,2, , в+1-1содержит ш+1-1 элементов И, ш+1-2элементов ИЛИ 29 и имеет первый 30и второй 31 входы и выход 32.Блок управления (см. фиг. 4) содержит в+2 элементов НЕ 33, дваэлемента ИЛИ 34, ш+2 элементов И 35,первый 36, второй 37 и третий 38входы, выходы 39-44.Блок формирования результата (см.фиг. 5) содержит г+ш элементов И 45,г+и сумматоров 46 по модулю два, дваэлемента ИЛИ 47, первый 48 и второй49 входы, первый 50 и второй 51 ны 55ходы.В основе работы устройства лежитследующий способ вычисления значений функции У = 1 Х. Значение аргументапредставляется в виде Х = 2 М. ПоР,рядов Р представляется (г+1) -разрядным двоичным дополнительным кодомаа,а, , а, где а - знаковый,а,а,. , а - числовые двоичныеразряды. Мантисса М представляетсяш-раэрядым двоичным кодом Ь,Ь,Ь где Ь Ь, , Ъ, - числовые Двоичные разряды (мантиссааргумента всегда неотрицательна).Значение результата вычисляетсяс использованием разложения приведенной мантиссы Мо аргумента Х намножители вида (1+2 " ) Если аргумент Х представить в виде Р Р, Р -1 к Х= 2М= 2 М = 2 Г 1(1+2 ) Като значение искомой функции У можноопределить выражением ь оо1 М =2 П (1+2 )о(5) Из выражений (2) и (4) следует Введем следующие обозначения: 2 = 2 П (1+2 )1=1,2, ,(9) о М=М П 1+2 )11=12 к: Выражения (6) и (7) с учетом (9)и (10) могут быть представлены ввиде:(12)5 Из выражений (9) и (10) можно получить рекуррентные сотношения длявычисления очередных значений 2;и М,: 1 О(14) 15 М;=И;, +И;, 2 При вычислении функции У = -Х в соответствии с выражениями (3) и (5) определяется порядок Я результата. Мантисса результата вычисляется с использованием рекуррентных формул (13) и (14). Начальное значение М, определяется в соответствии с выражением (1), 2 - в соответствии с выражением (8).Очередное значение величины 1 определяется по формуле го 25(15)30 3, = М(2 ) +1,где М(2;, ) - номер старшего нулевого разряда в двоичном представлении числа Е,Признаком окончания операции слу. жит условие 35 2 ь 0,111 = 1-2 являющееся конечным приближением предельного соотношения (11). ВеличинаМ при этом в соответствии с (12) используется в качестве значения мантиссы результата.Устройство работает следующимобразом.В исходном состоянии все разрядыс первого по (пн 1) -й регистра 1,50используемого для хранения величины2;, имеют одинаковое (либо нулевое,либо единичное) значение. Вследствиеэтого значение сигнала конца операциина шестом выходе блока управления55равно единице, а значение сигнала напервом и втором выходах блока управления равно нулю. На вход 15 устрой" ства, являющийся одновременно первымвходом блока управления, непрерывнопоступают тактовые импульсы,При извлечении квадратного корняиэ числа, представленного в форме сплавающей запятой, значения порядкаи мантиссы аргумента поступают соответственно на входы 13 и 14 устройства. Код порядка аргумента с входа 13поступает на информационный вход регистра 3, код мантиссы аргументана первые информационные входы мультиплексоров 6 и 7. Кроме того, младший разряд кода порядка а поступаетна первые управляющие входы мультиплексоров 6 и 7.Если значение младшего разрядапорядка а равно нулю, то код мантиссы, поступивший на первые информационные входы мультиплексоров 6 и 7,проходит на выходы мультиплексоровбез преобразования. При единичномзначении акод, поступающий напервые информационные входы мультиплексоров 6 и 7, проходит на выходмультиплексоров со сдвигом на одинразряд в сторону младших разрядов.СФормированное на выходе мультиплексоров 6 и 7 приведенное значение мантиссы М поступает на информационныевходы регистров 1 и 2. Для выполнениявычислений синхронно с одним из тактовых импульсов на вход 16 устройстваподается сигнал "Пуск", который поступает на управляющий вход регистра 3,осуществляя занесение в регистр 3значения порядка аргумента Р, а такжена первый вход блока 11 управления,По сигналу "Пуск" на втором выходеблока 11 управления формируется импульс, который поступает на управляющие входы регистров 1 и 2 и осуществляет занесение в регистр 1 величины2 = М и в регистр 2 - величины М.оЗначение с выхода регистра 1 поступает на третий вход блока 11 управления, первые входы блоков 8 и 9сдвига и первый вход сумматора 4.Значение М с выхода регистра 2 посотупает на первый вход блока сдвига,первый вход сумматора 5 и второй входблока 12 формирования результата. Напервый вход блока 12 формированиярезультата с выхода регистра 1 поступает значение порядка Р.Поступление кода 2 на третийвход блока 11 управления приводит кк появлению на шестом выходе блока 11управления нулевого уровня сигнала, а на первом выходе - единичного уровня. Кроме того, второй ныход блока 11 управления подключается к его второму входу, обеспечивая прохождение очередных тактовых импульсов на управляющие входы регистров 1 и 2.По коду 2, на третьем, четвертом и пятом выходах блока 11 управления формируются (щ+1-1) -разрядные коды, содержащие единицу в (З )-м (1 - 1) -м и (2 3;)-м разрядах и нули в остальных разрядах, которые поступают на вторые входы блоков 10, 8 и 9 сдвига соотнетственно. Значение 3 опреде ляется в соответствии с выражением (15). Блоки 8 и 9 сдвига осуществляют умножение поступающего на ихпервые входы кода 2 на 2 и 2соответственно путем сдвига кода 2, на 3 -1 и 2 3 разрядов. Блок 10 сдвига осуществляет умножение кода М на 2путем сднига кода М, на 1, разрядон 25Сумматоры 4 и 5 производят вычисление значений 2, и М, в соответствии с выражениями (13) и (14), С выходов сумматоров 4 и 5 коды величин 2 и М, поступают на вторые информацион ные входы мультиплексоров 6 и 7 соответственно. Наличие единичного сигнала на вторых управляющих входах мультиплексоров 6 и 7 обеспечивает прохождение информации с вторых информационных входов на выходы мультиплексоров, в результате чего коды 2, и М, поступают на информационные входы соответственно регистров 1 и 2. С приходом очередного тактового40 импульса значения 2,.и М, заносятся в регистры 1 и 2, На этом выполнение первой итерации завершается.В процессе выполнения второй итерации по значениям 2, и М, н устройстве формируются значения 2и М ,45 которые заносятся в регистры 1 и 2 очередным тактовым импульсо 1. Итерационный процесс продолжается до тех пор, пока нсе щ+1 старших разрядов числа 2; не станут равными единице. При этом блок 11 управления формирует на шестом выходе сигнал конца операции, который поступает на выход 19 устройстна и запрещает прохождение тактовых испульсов со своего второго 55 входа на второй выход. На первом вы-. ходе блока управления устанавливается нулевой уронень выходного сигнала. По окончании процесса вычислений на первом выходе блока 12 формирования результата формируется значение порядка результата Я в соответствии с выражениями (3) и (5), а на втором выходе - округленное до щ разрядов значение мантиссы результата, Сформированные блоком 12 формирования результата порядок и мантисса результата поступают на выходы 17 и 18 устройства.Если значения всех щ+1 разрядов 2 одновременно равны единице или одновременно равны нулю, то вычисления по рекуррентным соотношениям (13) и (14) не проводятся и в качестве результата используются значения порядка и мантиссы, сформированные блоком 12 формирования результата по поступившим на его входы значениям Р и Г 1, .Мультиплексор работает следующим образом. При нулевом сигнале на втором управляющем входе 26 на выход 27 мультиплексора передается значение кода, поступающего на его первый информационный вход 23. Если значение сигнала на первом управляющем входе 25 мультиплексора равно нулю, то поступающий на вход 23 код передается на выход 27 беэ преобразования. При единичном значении сигнала на нходе 25 и нулевом значении на входе 26 код, поступающий на вход 23, передается на выход 27 со сдвигом на один разряд в сторону младших раэрядон, При единичном значении сигнала на входе 26 мультиплексора независимо от значения сигнала на входе 25 на выход 27 передается значение кода, поступающего на второй информационный вход 24.Блок сдвига работает следующим образом. На первый вход 30 блока поступает (щ+1-1) -разрядный код, подлежащий сдвигу, на второй нход 31, блока поступает (щ+1) -разрядный код, содержащий единицу в одном иэ разрядов и нули в остальных разрядах. Блок осуществляет сдвиг в сторону младших разрядов кода, поступающего на первый вход 30, на число разрядов, равное номеру разряда кода, поступиншего на второй вход 31 блока, значение которого ранно единице. Освобождакициеся при сдвиге старшие разряды входного кода принимают нулевое значение.15 Формула изобретения 1. Устройство для извлечения квадратного корня, содержащеетри регистра, три блока сдвига, два сумматора, блок управления, причем первые входы первого и второго сумматоров соединены с выходами одноименных регистров, выходы первого и второго Блок управления работает следующим образом. Сигнал, поступивший на первый вход 36 блока, через элемент ИЛИ34 проходит на второй выход 39 блока, Сигнал, поступивший на второй вход37 блока, формирует выходной сигнал на втором выходе 39 блока при наличии единичного уровня на первом выходе40 блока, которому соответствуетвходной код на (в+1) -разрядном третьем входе 38 блока, содержащий хотябы один нуль и хотя бы одну единицу.В этом случае шестой выход 41 блокаимеет нулевое значение. Если всеразряды третьего входа 38 блока одновременно равны нулю или все разрядытретьего выхода 38 одновременно равны единице, то первый выход 40 блокаимеет нулевое, а шестой выход 41 - 2 п единичное значения. На третьем 42, четвертом 43, пятом 44 выходах блока формируются коды, имеющие единичное значение в (К+1)-м, К-м и (2 К+2) -м разрядах Соответственно и нули в 25 остальных разрядах, где К - номер старшего, равного нулю, разряда кода, поступившего на третий вход 38 устройства.Блок фоРмиРования результата ра ботает следующим образом. Поступающий на первый вход 48 блока код делится на два путем его сдвига на один разряд в сторону младших разрядов с сохранением значения старшего35 разряда с последующим подсуммированием значения младшего разряда, сдвигаемого на разрядную сетку, а также сигнала переноса из старшего Разряда Возникающего при формирова 40 нии кода, поступающего на второй вход 49 блока, после чего поступаетна первый выход 50 блока. Значение младшего разряда кода, поступившегона второй вход 49 блока, суммируется 45 с остальной частью кода, поступившего на второй вход 49, и сформированный новый код поступает на второй выход 51 блока. блоков сдвига подключены соответственно к второму и третьему входам первого сумматора, выход третьего блока сдвига соединен с вторым входом второго сумматора, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия при одновременном повышении точности и расширении области применения за счет обеспечения воэможности обработки чисел, представленных в форме с плавающей запятой, в него введены два мультиплексора и блок формирования результата, причем вход задания мантиссы устройства подключен к первым информационным входам первого и второго мультиплексоров, вторые информационные входы которых соединены с выходами первого и второго сумматоров соответственно, первые и вторые управляющие входы мультиплексоров подключены к входу младшего разряда входа задания порядка устройства и первому выходу блока управления соответственно, второй выход которого соединен с входами разрешения записи первого и второго регистров, информационные входы которых подключены к выходам одноименных мультиплексоров, информационный вход третьего регистра соединен с входом задания порядка устройства, тактовый вход которого подключен к первому входу блока управления и входу разрешения записи третьего регистра, выход которого соединен с первым входом блока формирования результата, первый и второй выходы которого соединены соответственно с выходами порядка и мантиссы результата устройства, а второй вход - с выходом второго регистра и информационным входом третьего блока сдвига, вход сдвига которого и одноименные входы первого и второго блоков сдвига подключены к третьему, четвертому и пятому выходам блока управления, второй вход которого соединен с входом запуска устройства, а третийс информационными входами первого и второго блоков сдвига, шестой выход блока управления является выходом конца операции устройства.2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит ш+2 элементов НЕ, два элемента ИЛИ и ш+3 элементов И, причем вход д-го элемента НЕ (д=1,2, ,в+1) и -й вход первого элемен 1381497 10та И подключены к д-му разряду третьего входа блока, выход -го элемента НЕ соединен с д-входом второгоэлемента И, выходы первого и второго5элементов И подключены к входам первого элемента ИЛИ, выход которогоподключен к шестому выходу блока ивходу (а+2) -го элемента НЕ, выходкоторого подключен к первому выходублока и первому входу третьего элемента И, второй вход которого подключен к второму входу блока, а выход -к первому входу второго элемента ИЛИ,Второй ВхОд котОрого соединен с первым входом блока, а выход - с вторымвыходом блока, выход 3-го элемента НЕ(1=2,3, , в+1) соединен с первымвходом (1+2) -го элемента И, остальныевходы которого соединены с Разрядами третьего входа блока, номера которых меньше 1, 1-й разряд третьеговыхода блока (1 с=1, щ+3, ш+4,ш+1-1) и и-й разряд четвертого выходаблока (п=ш+2, ш+3, , ш+1-1) под" 25ключены к нулевой шине, 6 -й разрядтретьего выхода блока и Ь -й разрядчетвертого выхода блока ( Ь =3,4,ш+2) подключены к выходу ( Ь +1)-гоэлемента И, второй разряд третьего,первый разряд четвертого и четвертыйразряд пятого выходов блока соединены с выходом первого элемента НЕ,первый, второй, третий и ц-е разрядыпятого выхода блока (ц=57,ш+1-1) подключены к нулевой шине,(ц) -Й разряд пятого выхода блока подключен к выходу (О) /2 элемента И.3. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок формирования результата содержит г+шэлементов. И, г+ш сумматоров по модулюдва и два элемента ИЛИ, причем первый вход д-го элемента И (1=1,2,г) подключен к выходу первого элемента И, остальные входы - к разрядамс (-1) -го по (г) -й первого входаблока, а выход - к первому входу1-го сумматора по модулю два, выходкоторого соединен с (1-1) -м разрядомпервого выхода блока второй входпервого сумматора по модулю дваподключен к нулевому разряду первоговхода блока, второй вход 1-го сумматора по модулю два (1=2,3.г+1) подключен к (1-2) -му разрядупервого входа блока, первый вход(г+1) -го сумматора по модулю дваподключен к выходу первого элементаИЛИ, а выход - к г-му разряду первого выхода блока, выходы К-го элемента И (К=г+1, г+2, , г+щ) подключены к разрядам с (К-г) -го по(ш+1) -й второго входа блока, выходи-го элемента И (п=г+3, г+4,г+щ) соединен с первым входом (п)го сумматора по модулю два, второйвход которого подключен к 1 п(г)1 -муразряду второго входа блока, первыйи второй входы (г+щ) -го сумматора помодулю два подключены соответственнок ш-му и (ш+1)-му разрядам второговхода блока, первый и второй входыпервого элемента ИЛИ подключены соответственно к г-му разряду первоговхода блока и выходу (г+1) -го элемен.та И, первый и второй входы второгоэлемента ИЛИ подключены соответственно к первому разряду второго входа блока и выходу (г+2) -го элемента И, а выход - к первому разряду второго выхода блока, выход з-го сумматора по модулю два (з=г+2, г+3. , г+щ) подключен к (з-г) -му Разряду второго выхода блока.