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

Овз СОВЕТСНИ ОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 191 01) ОСУДАРСТВЕННЫЙ НОМИТ О ДЕЛАМ ИЗОБРЕТЕНИЙ И СССРКРЫТИЙ 1 ффф- й ПИСАНИЕ ИЗОБРЕТЕНИЯАВТОРСКОМУ СВИДЕТЕЛЬСТВУ ия СС СССР 77технимации/ ев:ис, 59(71) Киевский институт инженгражданской авиации им. 60"л(56) Авторское свидетельствоР 553622, кл, 6 06 Г 15/32,Введение в кибернетическуку: Обработка физической инфПод ред. Б.Н. Малиновского.Наукова Думка, 1979, с, 156,(54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ(57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств имашин. Цель изобретения - повьпиениебыстродействия - достигается благодаря введению в устройство, содержащее сумматор 19, блок 23 начальногоприближения, блок управления 1, логический элемент И 17, группы 27, 28элементов И, элементы задержки 2-4 и1399732 управляющий триггер 11, сумматоров20-22, регистра приращений 26, второго и третьего блоков 24 и 25 начального приближения, третьей группы 29элементов И, блока 30 преобразования Изобретение относится к вычислитльной технике и может быть использ вано при построении специализирован.х вычислительных устройств и машин. 5Цель изобретения - повышение быстр действия устройства.На Фиг. 1 представлена блок-схемап едлагаемого устройства; на фиг.2-5 -с емы блока управления, блока преобр зования приближенного значения,вдорого.и третьего блоков начальногоприближения элемента 2 ИИЛИ"НЕ иэ 1 емента И второго и третьего блоковн 1 чального приближения; на Фиг.6 ц 7 - 5сКемы соединения элементов третьейгруппы элементов И,Па Фиг. 1 обозначены блок 1 управ- "л ния, спервого по восьмой элементы2 9 задержки, элемент НЕ 10, с перво г по пятый управляющие триггеры111-15, элемент ИЛИ 16, первый 17 нв арой 18 элементы И; с первого почетвертый сумматоры 19-22, блоки23-25 начального. приближения, регистр 2526 приращений, первая, вторая, и третья группы 27-29 элементов И и блок30 преобразования приближенных знаЧенпй.Блок управления содержит (Фиг, 2) 30регистр 31 команд, дешифратор 32 коМанд, заторможенный мультивибратор33, счетчик 34, многовходовый элемент ИЛИ 35 и многовходовый элементИ 36. Блок 30 (фиг, 3) образуют двегруппы элементов НЕ 37 и три группы11, 11) элементов И 38, вторыевходы которых объединены в одну входиую шину блока 30.Блоки 24 и 25 включают (Фиг. 4)Элемент 39 задержки, элементы НЕ 40,Элемент 2 ИИЛИ-НЕ 41, элемент И 42,Элементы 43 и 44 постоянной памяти 45".лементы 41 и 42 содержат (фиг, 5)элемент ИЛИ 46, элемент НЕ 47 и элементы И 48. В качестве элементов 43и 44 блоков 24 и 25 можно использовать, например, ПЗУ серии Е 155-РЕЗ,в которые предварительно занесенывходные значения согласно таблице.В таблице символом + обозначено состояние О М 1, т.е. для этого случаязначение 0 на входе 1 ПЗУ РЕЗ определяет 1 на выходах А, В и С независимо от значени",;, поступающих на входы 10-13,Блок 29 (фиг. 6) содержит схемы49 сдвига числа на заданное числоразрядов, Для рассматриваемого примера.= 1,2. 8. Каждая схема 49;(для примера= 5) содержит элементы И 50 (Фиг. 7),1 редлагаемое устройство работаетследующим образом.В начале операции извлечения квадратного корня значение подкорениойвеличины в дополнительном коде заносится в сумматор 19,Команда извлечения квадратногокорня записана в регистре 31 блока 1.С выходов регистра 31 управляющийсигнал через дешифратор 32 поступаетна вход заторможенного мультивибратора 33, выходные импульсы которогопоступают на вход счетчика 34. Насчетчике 34 перед началом операциизаписано число, определяющее длитель.ность первого управляющего сигнала,Импульсы от мультивибратора 33 посту"лают на вход счетчика 34, уменьшаясодержимое счетчика на единицу прикаждом поступлении. Выходы всех разрядов счетчика 34 через многовходовый элемент ИЗБ 35 объединены в однууправляющую шину. На выходе элемента ИЛИ 35 единичныйсигнал сохраняетсядо тех пор, пока содержащееся в счетэ 13997чике значение превышает нуль, т.е.пока хотя бы один из его разрядов содержит .единицу. Этот сигнал, поступая на вход 2 элемента И 36 опредеф5ляет длительность прохождения черезэлемент И 36 управляющего сигнала свыхода дешифратора 32.В начале операции извлечения квадратного корня управляющие триггеры О11-15 находятся в состоянии "0". Управляющий сигнал с выхода блока 1 поступает на счетный вход триггера 12и на первый счетный вход триггера 11,переводя их в состояние "1 , Поскольку триггер 13 в это время находитсяв состоянии "0", то с выхода элементаНЕ 10 на третий вход элемента И 18поступает сигнал "1". На,первый ивторой входы элемента И 18 сигналы 20поступают с выходов блока 1 и триггера 12. Одновременно с выходов блока 1и триггера 11 сигналы поступают навторой и первый входы элемента И 17.На выходах элементов И 18 и 17 появляются управляющие сигналы У 1 и У 2соответственно.Управляющий сигнал У 1 поступаетна вход блока 23 и разрешает прохождение через него сигнала "1" с самого ЗОстаршего разряда сумматора 19, который находится в нулевом состоянии.Поскольку в сумматоре 19 записан дополнительный код подкоренной величиныУ, то на выходах 1-15 блока 23 (2 -235соответственно) появляется значение1Е(у), равное старшей цифровой единицепрямого кода у. С выходов блока 23значение Е(у) поступает на вторыевходы элементов И 27 в качестве первого приближения подкоренной величины у. Кроме того, сигнал с выходаблока 23 поступает на вход триггера13, переводя его в состояние "1",поэтому на входах элемента И 18 появ 45ляется сигнал "0", определяющий конецдействия сигнала У 1. На первые входыэлементов И 27 поступает сигнал У 2с выхода элемента 2 задержки, разре",шая прохождение значения Е(у) в сум 50матор 19, где оно суммируется с дополнительным кодом подкоренной величины у. При этом результат лу на выходах сумматора 19 определяется какду = Е(у) " у. Одновременно с величиной Е(у) с выходов блока 23 на входы.второго 20 и третьего 21 сумматоровпоступает значение х, которое составляет первое приближение вычисляемого 324квадратного корня х = Д:(у). Г выходов сумматоров 20 и 19 величины х и Ьу поступает на первь 1 е и вторые входы элементов И 29, на третьи входы которых с выхода элемента 4 задержки поступает управляющий сигнал УЗ. Выходным значением группы 29 элементовЬИ является значение Ьх = ;-., ко 2 Е 7 х) торое является поправкой величины х. Его знак определяется знаком величины х. Коррекция величины х как х , = =х, + Лх; осуществляется в сумматоре 21,навторые входы которого поступает значение 6 х с выходов элементов И 29 (на первые входы сумматора 21 в этот момент ничего не поступает), С выходов сумматора 21 и регистра 26 значения х и х поступают на входь 1 блоков 24 и 25. Одновременно на другие входы этих блоков поступает управляющий сигнал У 4 от элемента 5 задержки, который позволяет прохождение значения Е(х), равного старшей цифровой единице прямого кода значения х, на вход сумматора 20 (сумматор 20 предварительно обнуляется). Сигнал У 4 разрешает прохождение величины Б(6 х) с выхода блока 25 на вход блока 30, на другие входы которого поступает значение х с выхода сумматора 21. Одновременно на вход блока 30 поступает управляющий сигнал У 5, разрешающий прохождение величины х, сдвинутой влево на 2 Е(Ьх) разрядов, на вход сумматора 19, на выходах которого формируется очередное значение Ьу.Сигнал от блока 1 через элемент 3 задержки переводит управляющий триг гер 1 из состояния "0" в состояние "1". Триггер 15 при этом остается в состоянии 0. Требуемая длительность задержки управляющего сигнала элементом 3 задержки определяется исходя из условий одновременности появления управляющего сигнала УЗ на выходах блоков 16 и 4. С выходов блоха 25 сигнал проходит через элемент 7 задержки и изменяет состояние триггеров 14 и 15 с "1" и 0" на "0" и "1" соответственно. При каждой последующей итерации вопределении величин Ьх, х и Ьу состояние триггеров 14 и 15 изменяется на противоположное, определяя управляющий сигнал новой итерации либо с выхода триггера 14, либо с выхода триггера1399732 6А,. -259Ьхл25 х 2 32 15. Время 1 каждой итерации при вычислении квадратного корня с помощью предлагаемого устройства определяется сдвигом числа, выделением старшей единицы и двумя сложениями и, следовательно, не намного превышает времяитерации при вычислении с помощью известного устройства ( - э - 1,5).г, . 1 ОПри каждой итерации очередное зна-. чение у определяется согласно выра- жению.у =Ьу;. 2 Е (Ьх; ) х;+1 Ь х )В этом выражении значение 2 Е(х;)х+ +ф(йх;) определяется блоком 30 в котром умножение величин х; и Ьх заменяется сдвигом значения х на Е Ьх) разрядов. Добавление единичного значения Е(Ьх;)" практически не увеличивает задержку сигнала блоком 30. Параллельно с вычислениями вновь полученное значение Ь у; сравнивается в 2 Б блоке 30 с предельным минимальным значением (контрольным) Ьу, поступающим Через вход 1 устройства. При удовлетворении условия Ьу; Ьузначение Квадратного корня с выхода сумматора 30 21 передается на вход устройства через элементы И группы 28, на входы которых поступает разрешающий сигналвыхода сумматора 22. Для определения квадратного корня с помощью пред-, лагаемого устройства его начальноеЗБ приближение, получаемое на выходе блока 23, уточняется согласно выражеНию х =- т:(, причем приращение Ьх- 2 Е(х)40 является многоразрядным значением и определяется в блоке 29.П р и м е р. Извлечение квадратноГо корня из десятичного целого числа.Пусть у -": 2045, Требуется определить х = 1 ЧИтерации"1. У,=Е(у)=Е(2045)=2; х, =4 у, =Яц БО 48 е ББ Е(ах,) = У;=У"Чь= 2045 - 1024 = 1021; ау, 1021Ьх,= .= - -" 16. 2 бх, 2 32 г.х,=х,+Ьх, =32+16у = Ьу, - 2 СЬх,)х,259; 3. х =х+х= 48 - 4= 44,Для определения величины х = 44 от у =: 2045 с помощью известного устройства требуется не 3, а 13 итераций.,Формула изобретения Устройство для извлечения квадрат- ного корня содержащее блок управления, первый сумматор, первый блок начального приближения, первый элемент И первый вход которого соединен с выходом первого управляющего триггера; первый, второй и третий элементы задержки, первую и вторую группы элементов И, первые и вторые входы элементов И первой из которых подключены к выходам первого элемента задержки и первого блока начального приближе" ния, информационный вход которого соединен с выхо;,ом первого сумматора, первый вход которого подключен к выходам элементов И первой группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй, третий и четвертый сумматоры, регистр приращений, второй и третий блоки начального приближения, третья группа элементов И, блок преобразования приближенных значсний, второй, третий, четвертый и пятый управляющие триггеры, с четвертого по восьмой элементы задержки, элемент НЕ, причем выход блока управления подключен к второму входу первого и первому входу второго зле ментов И, к первому входу первого управляющего триггера, к входам второго элемента задержки и второго уп-. равляющего триггера, выход которого соединен с вторым входом второго элемента И, третий вход которого подключен к выходу элемента НЕ, вход которого соединен с выходом третьего управляющего триггера, вход которого и первые входы второго и третьего суммаоров подключены к выходу первого блока начального приближения, управляющий вход которого соединен с выходом второго элемента И, выход первого элемента И через первый элемент задержки подключен к входу тре",тьего элемента задержки, выход которого и выход элемента ИЛИ соединеныО О О О О О О О О О ОО О О О ОО О О с первыми входами элементов И третьейгруппы и через чтвертый элема: в :г в :адержки с управляющими входами второго и третьего блоков начального приближения и входом пятого элемента задержки, выход которого соединен суправляющим входом блока преобразования приближенных значений, первый ивторой информационные входы которого Оподключены соответственно к выходамтретьео сумматора и третьего блоканачального приближения, выход последнего из которых через шестой элементзадержки соединен с вторым входом 15первого, первым .входом четвертого ивходом пятого управляющих триггеров,выходы двух госледних из которыхсоответственно через седьмой и восьмой элементы задержки подключены к 20первому и второму входам элементаИЛИ, второй вход четвертого управляющего триггера соединен с выходомвторого элемента задержки, первый ивторой входы элементов И второй груп" 25пы соединены с выходами соответственно четвертого и третьего сумматоров,Вхсды блока 43 , Выходи бло 51/г э 2 1 1 Л1 ыхзд последнего из которых и выход регистра приращений подключены к инсормационньм входам второго и третье;"о блоков начального гриближения, вход регистра приращений и второй вход третьего сумматора соединены с выходами элементов И третьей группы, вторые входы элементов И которой первый вход четвертого сумма-:ора под". ключены к выходу первого сумматора. а третьи входы соединены с выходом второго сумматора, второй вход которого соединен с выходом второго блока началЬного приближения, второй и третий входы первого сумматора подключены соответственно к входу задания аргумента устройства и выходу блока преобразования приолиженных значений, второй и третий входы четвертого сумматора соединены с входом задания минимального значения функции устройства. и выходом первого блока начальных приближений соответственно, выходы элементов И второй группы являются выходом устройства.1399732 оды блока ходы блока д ЕЗ ы ПЗУ Р 12 11 14 А. В О 1 О,О О 33 коды блока 4 З5 11 ыходы ПЗУ РЕТ.Ь Входы ПЗУ РКЗ 13 12 11399732 риг.7Составитель Д,СингхТехред С. Сердюкова 1(оррект едактор Л.Ог Заказ 2666/48 Проиэводствецно-полиграФическое предприятие, г. Ужгород, ул, Проектная, 4 Тираж 704 ВИИИПИ Государственног по делам изобретений 13035, Москва, Ж, РауПодписноекомитета СССРи открытийская цаб., д. 4/5