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

А 1 СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 19) (11 6 Г 7/5 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ ОПИСАН К АВТОРСКОМ ЛЬС(54) УСТРОЙСТВО ДЛЯРАТНОГО КОРНЯ(57) Изобретение овычислительной тех ЗВЛЕЧЕНИЯ КВАДносится к облас ики. Цель изобр(088.8)М.А. Арифметика цифроНаука, 1969, с. 537,тения - увеличение быстродействия.Устройство работает в системе счисления с натуральным основанием Р 2.Цикл извлечения квадратного корнясостоит из М тактов. В каждом тактеопределяется одна Р-ичная цифра корня. Для ее определения одновременновычисляется Рразностей предыдущего остатка и приращения подкоренного выражения с каждым из "углов",получаемых для используемой системысчисления. По знакам вычисленных разностей определяется очередная цифраквадратного корня и очередной остаток. 3 з.п. ф-лы, 6 ил.123 ч 831 Составитель С. СилаевТекред М.Ходаничказ 2986/ аж б 71 Прственного комитета СССРобретений и открытийЖ, Раушская наб., д. 4/ одписно ВНИИ п Ужгород, ул, Проектная оизво нно-полиграфичес едприятие дактор Е. Коп Ти НИ Госуд делам и Москва,ректор Г. РешетникИзобретение относится к вычислительной технике и предназначено дляизвлечения квадратного корня из чисел, представленных в двоично-десятичной системе.Цель изобретения - увеличениебыстродействия.На Фиг. 1 изображена структурнаясхема устройства для извлеченияквадратного корня; на фиг. 2 - схемаблока суммирования; на фиг. 3 - схема блока коррекции; на фиг, 4 - схемаблока поразрядного дополнения; нафиг, 5 - схема шифратора; на фиг.бсхема двухканального коммутатора.Устройство (фиг, 1) содержит регистр 1 корня, регистр 2 подкоренного выражения, Мдешифраторов 3.1,3,2, , 3, М, блок 4 поразрядного дополнения, блок 5 коррекции,блок 6 формирования кратных, девятьблоков 7,1-7,9 суммирования, двухканальный коммутатор 8, шифратор 9,первый 10 и второй 11 регистры.Блок 7 суммирования (фиг, 2) содержит М одноразрядных двоично-десятичных сумматоров 12.1. . ., 12.1,узел 13 формирования опережающегопереноса, шину 14 логического нуляустройства,Блок 5 коРРекции (Фиг, 3) содержит элемент 14.1-14.МИЛИ, элемент ИЛИ-НЕ 15, элемент И 16 и триггер 17.Блок 4 поразрядного дополнения(Фиг. 4) содержит первую 18 и вторую19 группы элементов НЕ, первый 20и второй 21 двоичные сумматоры,первую 22 и вторую 23 группы элементов И и шину 24 двоично-десятичногочисла 10 устройства.Шифратор 9 (фиг, 5) содержит элементы НЕ 25-33, элементы И 34-41,элементы ИЛИ 42-45,Двухканальный коммутатор 8(фиг, 6) содержит девять элементовНЕ 46-54, восемь элементов И 55-62,две группы элементов 10 И-ИЛИ 63 и 64Рассмотрим работу устройства.Подкоренное выражение положительно (ОИ 1), представлено в двоичнодесятичной системе счисления и содержит М разрядов без учета знакового, В одном такте определяется одна двоично-десятичная цифра М-разрядного квадратного корня, получение которой производится по седующему алгоритму. Одновременно вычисляются девятьположительных углов", где каждый"угол" представляет собой удвоенноепроизведение всех ранее полученныхР - ичных цифр квадратного корня насоответствующую данному "углу" цифрумножитель из ряда 1, 2, , 9 с учетом весов плюс произведение цифрымножителя на саму себя, с учетом веса.1 О Одновременно определяются девятьразностей вида В 1=У 1-ВО; В 2=У 2-ВОВ(Р)=У(Р) -ВО, где (ВО) - очередной сдвинутый отрицательный остатокпредыдущего такта, плюс приращение15 М, У 1, У 2, , У(Р) - соответствующие положительные углы".Определяются знаки полученный разностей В 1, В 2 В 9,Выбирается реальный отрицательный20 остаток данного такта по знакам полученных разностей В 1, В 2, , В 9 иопределяется очередная двоично-десятичная цифра квадратного корняОсуществляется смещение полученно 25 го реального отрицательного остаткана два разряда влево, запись в двамладших разряда приращения подкоренного выражения.В следующих тактах операции рассмотренного алгоритма повторяются,но количество разрядов в "углах" скаждым тактом увеличивается. Приведем диаграмму, описывающую получение "углов" и процесс извлеченияквадратного корня, Пусть значениеквадратного корня Ш=0,658, тогда/ШхШ=:И =-0,432964 - точное значениеподкоренного выражения. Округлимэто значение до трех цифр 3=0,433.Па диаграмме вверху изображено образование углов от полученных в предыдущих тактах цифр квадратного корня, причем показаны только "углы",суммирование которых с отрицательнымостатком предыдущего такта дает ре -альпый отрицательный остаток данного такта. Внизу диаграммы изображенпроцесс извлечения квадратного корня,Первый тактом подкоренное выражение Н записывается в регистр 2 (фиг. 1), одновременно с этим регистр 1 обнуляется, регистр 10 и триггер 17 блока 5 обнуляется, а в каждый двоично-десятичный разряд регистра 11 записываются цифры девять.Два старших значащих разряда подкоренного выражения подаются на входы блока 4, в котором образуется их1 "угол" 9 9 9 ОО О О 2 такт 9 9 8 2 6 9 - приращение и сдвиг О, /1/Дол. единица О О 1 2 "угол" Э О 2 5 3 О 3 12348 дополнение до старшей цифры используемой системы счисления, т,е. до 9-ти. Полученные дополнения с выходов блока 4 подаются на входы, двух младших разрядов блоков суммирования. На аналогичные входы остальных разрядов блоков суммирования сВес О -1 -2 -3 31выходов регистров 10 и 11 подаютсясоответственно цифры О и 9 для получения дополнительного кода отрицательного приращения И. В следующих тактах дополнительныйкод получается автоматически,12348319 9 9 8 8 5О 0 0 0 1 Ш 2=5 3 такт 9 8 8 5 0 0 - приращение И и 0 О 1 0 сдвиг 3 нуголн 4 8 4 О б 4 4 О 9 8 7 9 б 40 1 2 О О ШзВ каждом такте к сдвинутому на два двоично-десятичных разряда влево очередному остатку в два младших разряда записывается значение дополнения приращения И, значит в такте30 при подаче младшего разряда М в младший разряд нужно подавать дополнительную единицу, причем в тот разряд, который является младшим разрядом, если все остальные разряды справа равны нулю. Дополнительную единицу вырабатывает блок 5 коррекции (фиг,3), В регистре 2 с каждым тактом подкоренное выражение сдвигается на два двоично-десятичных разряда влево, справа в регистр 2 записываются нули.40 На входы блока 5 подаются все разряды 2, кроме старших. В том такте, в котором на входах блока коррекции будут все нули, на его выходе появляется корректирующая единица, которая подается в младшие разряды блоков суммирования. Триггер 17 (Фиг. 3) включается в единицу, которая подается на вход блокировки блока 4 (фиг. 4), чем блокируются его выходы. После первого такта в регистре 1 записаны все нули, поэтому на выходах дешифраторов 3 группы сигналов нет. В первом такте в блоках .1, 7.2, , 79 в соответствии с диаг раммой происходит суммирование положительных значений "углов" первого такта 01, 04, , 81 со значениями двух старших разрядов подкоренноговыражения, представленных как дополнения. Полученные суммы в виде двухдвоично-десятичных чисел поразрядныхсумм и переносов с. выходов блоков7.1-7.9 подаются на соответствующиевходы двухканального коммутатора 8,На выходах переноса блоков суммирования образуются значения опережающих переносов, которые подаются навходы,цешифратора 9 и на входы управления двухканального коммутатора 8,где по ним определяются очереднаяцифра корня и реальный остаток данного такта. Вторым тактом в регистр 1записывается значение цифры корня свыходом шифратора 9. В регистры 10и 11 записывается значение реального остатка данного такта, подкоренное выражение в регистре 2 сдвигается влево на два двоично-десятичныхразрядаЗначение первой цифры корняподается из первого разряда регистра 1 на входы дешифратора 3.1 группы, и на его выходе, соответствующем цифре, появляется сигнал, который поступает по соответствующейшине на соответствующий вход блока б Формирования кратных.На соответствующих входах блоковсуммирования образуются значения вторых углов" соответственно для каждой из цифр-множителей 1, 2.9.Полученные "углы" суммируются нлодноразрядных двоично-десятичных сумматорах, соответствующих данным цифрам блоков суммирования со сдвинутым на два разряда влево предыдущим 5 остатком и приращением подкоренного выражения. По полученным остаткам на выходах блоков суммирования образуются опережающие переносы и остатки в виде двух чисел. По значениям 10 опережающих переносов определяется вторая цифра корня на шифраторе 9 и реальный остаток второго такта на выходах коммутатора 8. В следующих тактах все действия повторяются по аналогии с первым и вторым тактами до получения всех цифр квадратного ,корня.Формула изобретения 201. Устройство для извлеченияквадратного корня, содержащее первыйи второй регистры, регистр подкоренного выражения и регистр корня,о т л и ч а ю щ е е с я тем, что, с,целью увеличения быстродействия,устройство содержит группу из (М)дешифраторов, где М - разрядность аргумента, блок формирования кратных,девять блоков суммирования, шифратор,двухканальный коммутатор, блок поразрядного .дополнения и блок коррекции,причем выходы первой и второй тетрады подкоренного выражения подключенысоответственно к первому и второмуинформационным входам блока поразрядного дополнения, выход х-й (где =3,М) тетрады регистра подкоренного выражения подключен к (х)-муинформационному входу блока коррек 40ции, выход блокирующего сигнала блока коррекции подключен к входу блокировки блока поразрядного дополнения, первый и второй выходы блокапоразрядного дополнения подключены45соответственно к первому и второму,информационным входам всех блоковсуммирования и к йервому и второмуинформационным входам двухканальногокоммутатора, выход шифратора под 50ключен к входу первой тетрады регистра корня, выход 3-й где(1=1,М) тетрады регистра корняподключен к входу 3-го дешифраторагруппы, выходы 1-го дешифратора груп пы подключены к 1-му информационному входу блока формирования кратных,К-й выход (где 1 с=2, , 9) блока формирования кратных подключен ктретьему информационному входу к-гоблока суммирования, %+8)-й выходблока Формирования кратных подключен к четвертому информационномувходу Е-го блока суммирования, третий информационный вход первого блока суммирования подключен к шине логического нуля устройства, старшие(М) тетрады четвертого информационного входа первого блока суммирования подключены к выходам старших(М)-тетрад регистра корня, младшаятетрада четвертого информационноговхода первого блока суммированияподключена к шине двоично-десятичного числа "1" устройства, выход переноса -го (где 1=1. . .9) блока суммирования подключен к -му входушифратора и к 1,-му управляющему входу двухканального коммутатора, первый выход 1-го блока суммированияподключен к (+2)-му информационному входу двухканального коммутатора,второй выход -го блока суммированияподключен к (+11)-му информационномувходу двухканального коммутатора,выход первого регистра подключен кпятым информационным входам всех блоков суммирования и к двадцать первомуинформационному входу двухканальногокоммутатрра, выход второго регистраподключен к шестым информационнымвходам всех блоков суммирования ик двадцать второму информационномувходу двухканального коммутатора,выход корректирующей единицы блокакоррекции подключен к седьмым информационным входам всех блоков суммирования и к двадцать третьему информационному входу двухканального коммутатора, первый выход двухканальногокоммутатора подключен к информационному входу первого регистра, а второй выход " к информацинному входувторого регистра, причем блок поразрядного дополнения содержит первуюи вторую группы элементов НЕ, первыйи второй двоичные сумматоры, первуюи вторую группы элементов И, причемвыходы элементов НЕ первой группыподключены к первой группе входовпервого двоичного сумматора, выходыэлементов НЕ второй группы подключены к первой группе входов второго,двоичного сумматора, вторые группывходов первого и второго двоичныхсумматоров подключены к шине двоично 1234831 10десятичного числа 10 устройства, выходы первого двоичного сумматора подключены к первым входам элементов И первой группы, выходы второго двоичного сумматора подключен к первым входам элементов И второй группы, входы первой группы элементов НЕ являются первым информационным входом блока поразрядного дополнения, входы 1 О второй группы элементов НЕ являются вторым информационным входом блока порязрадного дополнения, вторые входы элементов И первой и второй групп соединены между собой и являются входом блокировки блока поразрядного дополнения, выходы первой и второй грул элементов И являются соответственно первым и вторым выходами блока поразрядного дополнения, блок кор О рекции содержит группу из (М) элементов ИЛИ, элемент ИЛИ-НЕ, элемент И и триггер, причем выход (х)-го элемента ИЛИ группы подключен к (х)-му входу элемента ИЛИ-НЕ, выход элемен та ИЛИ-НЕ подключен к первому входу элемента И и к входу установки триггера, входы (х)-го элемента ИЛИ группы являются (х)-м информационным входом блока коррекции, инверсный выход триггера подключен к второму входу элемента И и является выходом блокирующего сигнала блока коррекции, выход элемента И является выходом корректирующей единицы бло 1 ка коррекции. 2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок суммирования содержит М одноразрядных двоично-десятичных сумматоров и узел формирования опережающего переноса, причем выходы переносов одноразрядных двоично-десятичных сумматоров подключены к соответствующим разрядам первого входа узла формирования 45 опережающего переноса и являются первым выходом блока суммирования, выходы суммы одноразрядных двоичнодесятичных сумматоров подключены к соответствующим разрядам второго вхо О да узла формирования опережающего переноса и являются вторым выходом блока суммирования, выход узла опережающего переноса является выходом переноса блока суммирования, первый 55 вход первого одноразрядного двоично-десятичного сумматора является седьмым информационным входом блока суммирования, второй вход первого одноразрядного двоично-десятичного сумматора является первым информационным входом блока суммирования, третий вход первого одноразрядного двоично-десятичного сумматора является первой тетрадой четвертого информационного входа блока суммирования, четвертый, пятый и шестой входы первого и первый и второй входы второго одноразряднах двоичнодесятичных сумматоров подключены к шине логического нуля устройства, третий вход второго одноразрядного двоично-десятичного сумматора явля". ется вторым иформационы хдм блока суммирования, четвертый вход второго одноразрядного двоично-десятичного сумматора является первой тетрадой третьего информационного входа блока суммирования, пятый и шестой входы г-го (г=2, , М) одноразрядного двоично-десятичного сумматера являются г-й тетрадой четвертого информационного входа блока суммирования, третий и четвертый входы -го одноразрядного двоично-десятичного сумматора являются (1-1)-й тетрадой третьего входа блока суммирования, первый информационный вход -гб одноразрядного двоична" десятичного сумматора является (-2)-й тетрадой пятого информационного входа блока суммирования, второй вход х-го одноразрядного двоична-десятичного сумматора является (х)-й тетрадой шестого информационного входа блока суммирования.3, Устройство по п.1, о т л и - ч а ю щ е е с я тем, что шифратор содержит девять элементов НЕ, восемь элементов И и четыре элемента ИЛИ, причем выходы первого, второго, восьмого элементов НЕ шифратора подключены к первым входам соответственно первого, второго, , восьмого элементов И шифратора, выход первогФ элемента И шифратора подключен к первому входу первого элемента ИЛИ шифратора, выход второго элемента И шифратора подключен к первому входу второго элемента ИЛИ шифратора, выход третьего элемента И шифратора подключен к вторым входам первого и второго элементов ИЛИ шифратора, выход четвертого элемента И шифратора подключен к первому входу третьего элемента ИЛИ шифратора, 1234831 12выход пятого элемента И шифратораподключен к третьему входу первого иквторому входу третьего элементов ИЛИшифратора, выход шестого элемента Ишифратора подключен к третьим входамвторого и третьего элементов ИЛИшифратора, выход седьмого элемента Ишифратора подключен к четвертым входам первого, второго и третьего эле Оментов ИЛИ шифратора, выход восьмогоэлемента И шифратора подключен к первому входу четвертого элемента ИЛИшифратора, выход девятого элемента НЕшифратора подключен к пятому входу 15первого и к второму входу четвертогоэлементов ИЛИ шифратора, вход первого элемента НЕ шифратора являетсяпервым входом шифратора, вход Е-гоэлемента НЕ шифратора соединен с , 20вторым входом Й)-го элемента Ишифратора и является Е-м входом шифратора, выходы первого, второго,третьего и четвертого элементов ИЛИшифратора являются выходом шифратора. 4. Устройство по п.1, о т л и -ч а ю щ е е с я тем, что двухканальный коммутатор содержит девять эле- З 0ментов НЕ, восемь элементов И и двегруппы по (4.М) элементов 10 И-ИЛИ,причем выходы первого, второго,восьмого элементов НЕ двухканальногокоммутатора подключены к первым входам соответственно первого, второго,восьмого элементов И двухканального коммутатора, первые входывсех элементов 10 И-ИЛИ обеих группобъединены между собой и соединены свходом первого элемента НЕ двухканального коммутатора, выход р-го (гдер=1, , 8) элемента И двухканального коммутатора подключен к (р+1)-мвходам всех элементов О И-ИЛИ обеих 15групп, десятые входы всех элементов10 И-ИЛИ обеих групп подключены к выходу девятого элемента НЕ двухканального коммутатора, -й вход г-го (гдег=1, , (4.Ч) элемента 1 О И-ИЛИпервой группы является г-и двоичнымразрядом (1+2)-го информационного входа двухканальног о коммутатора,(4.Ч - 16) элемента 10 И в И первойгруппы является Й-м двоичным разрядом двадцать первого информационноговхода двухканального коммутатора,двадцатые входы (4,М)-го, (4.М)-го, , (4.М)-го элементов10 И-ИЛИ первой группы подключенык шине логического нуля устройства,двадцатый вход (4.М)-го элемента 10 И-ИЛИ первой группы являетсядвадцать третьим информационным входом двухканального коммутатора,двадцатый вход д-го элемента 10 И-ИЛИвторой группы является Й-и двоичнымразрядом двадцать второго информационногс входа двухканального коммутатора, двадцатые входы (4.М)-го,(4.М)-го (4-М)-го и (4.М)-гоэлементов 10 И-ИЛИ второй группыявляются соответственно первым, вторым, третьим И четвертым двоичнымиразрядами первого информационноговхода двухканального коммутатора,двадцатые входы (4.М)-го, (4.М)-го, (4.М 9)-го и (4.М - 8)-го элементов 10 И-ИЛИ являются соответственно первым, вторым, третьим ичетвертым двоичными разрядами второго информационного входа двухканального коммутатора, вход Е-го элементаНЕ двухканального коммутатора соединен с вторым входом (Ь)-го элемента И двухканального коммутатора и является 1-м управляющим входом двухканального коммутатора, вход первого элемента НЕ двухканального коммутатора является первым управляющимвходом двухканального коммутатора,выход г-го элемента 10 И-ИЛИ первойгруппы является г-м двоичным разрядом первого выхода двухканальногокоммутатора, выход г-го элемента10 И-ИЛИ второй группы является г-мдвоичным разрядом второго выходадвухканального коммутатора.