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

Союз СоветскихСоциалистическихРеспублик ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и 924702(22) Заявлено 210279 (21) 2728410/18-24 Р 11 М. Кп. з с присоединением заявки МЭ(23) Приоритет 0 06 Р 7/552 Государственный комитет СССР но делам изобретений и открытийОпубликовано 3004.82, Бюллетень Ио 16 Дата опубликования описания 30.04.82(54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГОКОРНЯ Изобретение относится к автомати" ке и вычислительной технике и может быть использовано в универсальных или специализированных вычислителях для извлечения квадратного корня.Известно устройство для извлечения квадратного корня, содержащее приемный регистр, регистр корня, эле" мент И, распределитель импульсов и управляемый генератор импульсов (1),Недостатком известного устройства является низкое быстродействие.Известно устройство для извлечения квадратного корня, содержащее сумматор, счетчик, элемент И и гене ратор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом знакового разряда сумматора, а выход элемента И соединен со входами младших разрядов счетчика и сумматора (2).Недостатком известных устройств является низкое быстродействие.Действительно, пусть разрядность 25 используемых в устройстве сумматора .и счетчика равна п и в соответст" венно (значения параметров п и в выбираются исходя из значения максимальной величины, нз которого не обходимо извлекать квадратный корень). В дальнейшем будем предполагать, что между параметрами и и щ выполняется соотношение и = 2 щ. Тогда максимальное и минимальное время формирования результата в известном устройстве примерно равноТтрн (2 1) "сдТ 1= "с где Се, - время сложения и-разрядных чисел.Предполагая, что появление каждого значения результата извлечения квадратного корня равновероятномож" но определить среднее время извлечения квадратного корня в известном устройстве, Онб примерно равно(Т с + Тив)/2 = 2 Пусть щ = 8, тогда Т си ,128 Со.Цель изобретения - увеличение быстродействия устройства для нзвле" чения квадратного корня., Ноставлениая цель достигается тем, что в устройство для извлечения квадратного корня, содержащее сумматор, счетчик, элемент И и генератор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом знакового разряда сумматора, а выход - с входами младших разрядов счетчика и сум 9247021 О матора, введен шифратор, первый вход и выход которого соединены соответственно с выходом и входом старших раз. рядов сумматора, второй выход шифратора соединен с входом старших разрядов счетчика управляющий вход 5 устройства соединен с управляющими входами счетчика и сумматора, а также с третьим входом элемента И, выход счетчика соединен с входом сумматора.На фиг. 1 приведена блок-схема предлагаемого устройства для извлечения квадратного корня; на фиг. 2 структурная схема узла извлечения квадратного корня; на Фиг. 3 - функ циональная схема ячейки, используемой на иг. 2.Устройство (фиг. 1) содержит сумматор 1, счетчик 2, шифратор 3, эле" мент И 4 и генератор 5 импульсов, выход которого соединен с первым вхо-; дом элемента И 4, второй вход которого соединен с выходом б знакового разряда сумматора 1, а третий вход - с управляющим входом 7 устройства, который также соединен с управляющими входами сумматора 1 и счетчи" ка 2, выход элемента И 4 соединен со вхОдами младших разрядов счетчика 2 и сумматора 1, выход счетчика 2 соединен со входом сумматора 1, вход шифратора 3 соединен с выходом 8 значений 2 к старших разрядов сумматора 1, а его выход 9 со входом 2 К старших разрядов сумматора 1, выход 10 соединен со входом ), старших разря дов счетчика 2.В предлагаемом устройстве используется сумматор 1 накапливающего типа. Счетчик 2 и сумматор 1 реализованы на двухтактных синхронных 40 Т-триггерах с асинхронными установочными входами. Здесь также предполагается, что вход шифратора 3 соеди" нен с инверсными выходами 2 К старших разрядов сумматора 1 (знаковый разряд сумматора в указанные 2 Е старших разрядов не входит), а выходы 9 и 10 шифратора 3 соединены с асинхронными установочными входами соответствующих разрядов сумматоРа 1 и счетчик 2, причем значение остатка на выходе 9 шифратора 3 Формируется в обратном коде. Выход 1-го разряда счетчика 2 (О с 1 с в - 1) с весом 2 соединен со счетным входом (Т-входом) (1 + 1)-го разряда сумматора 1 с весом 2 , т.е. содер" жимое счетчика 2 передается в сум" матор 1 с сдвигом на один разряд в сторону старших разрядов. Выход элемента И 4 соединен с счетнымвходом О-го разряда счетчика 2, а также с счетным входом 0-го разряда сумматора 1Хотя. цепи синхрониза" ции на чертеже и не показаны, одна" ко они обязятельно подразумеващтся. 65 На фиг. 2 в качестве примера при"ведена однородная ячеечная струк"тура блока 3.Блок 3 содержит матрицу определенный образом связанных ячеек 11 иинверторы 12. В узле реализован алгоритм извлечения квадратного корняс восстановлением остатков, С цельюиллюстрации протекания вычислительного процесса в блоке 3 рассмотренконкретный числовой пример извлече.ния квадратного корня иэ целого числа х = 10101100. Получившиеся приэтом результат у и остаток 2 соответственно равны 1101 и 00000011.С помощью нижней группы инверторов12 Формируется обратный код остатка2, равный 11111100. На структуре указаны значения наиболее характерныхвходов и выходов ячеек для рассматриваемого примера.На фиг. 3 приведена функциональная схема блока 11, используемогов качестве основного в блоке 3. Этотблок имеет входы А, В, С,Р и выходыР 0 . й Я, причем (1 = Р, В = В,+ А.Р -(В С + ВС) + АР.Если Р =О, то Я = А минс (ВаллисЕсли Р 1, то Я А,Этот блок фактически является управляемым вычитателем-передатчиком,если ее управляющий вход Р = О, ячей.1 ка работает как одноразрядный двоичный вычитатель, в противном случаеона транзитно передает значение сигнала со входа А на выход Я.Устройство работает следующимобразом,В исходном состоянии счетчик 2 обнулен, в сумматоре 1 хранится обратный код числа, из которого необходимо извлечь квадратный корень (в знаковом разряде сумматора хранитсяединица), элемент И 4 не пропускаетимпульсы, поступающие на его первойвход с выхода генератора 5 импульсов,так как на его третий вход поступает запрещающий сигнал с входа 7 устройства. С помощью блока 3 определяется значение К старших разрядоврезультата, которое с выхода 10блока 3 записывается через установочные входы 1 старших разрядов счетчика в счетчик 2. Значение же остатка в обратном коде с выхода 9 блока3 через установочные входы 2 Е стар.ших разрядов сумматора записываетсяв сумматор 1. Запись значений результата и остатка в счетчик 2 исумматор 1 производится с разрешения сигнала, поступающего наих управляющие входы с входа 7 устройст. -ва. После записи остатка в старшиеразряды сумматора 1 производится пре.образование содержимого сумматора вдополнительный код путем добавления единицу в его младший разряд.На этом этап предсказания значениякорня заканчивается. Далее процессизвлечения квадратного корня (если при предсказании не получен точный результат) основан на хорошо.известном представлении извлекаемогочисла в ниде суммы членов ряда последовательных нечетных чисел. С разрешения .сигнала, поступающего натретий вход элемента И 4, импульсы свыхода генератора 5 через элемент И4 поступают на входы младших разрядов счетчика 2 и сумматора 1, приэтом прибавление импульса в О-й разряд сумматора в 1-м такте осуществляется одновременно с прибавлением в 15сумматор содержимого счетчика, полученного к -му такту. Процесс извле"чения квадратного корня заканчи"вается как только в знаковом разряде сумматора 1 появится ноль, , 20так как элемент И 4 закрываетсяпод действием нулевого сигнала наего втором входе. Рассмотрим на примере извлечениеквадратного корня в предлагаемомустройстве. Для определенности примем, что и = 16, а = 8, )с = 4. Пустьчисло х, из которого необходимо извлечь квадратный корень, равно1010110001000100. Тогда в исходномсостоянии в сумматоре будет находиться код зо = 1.0101001110111011, а всчетчике код 2 о = 00000000,На этапе предсказания значениякорня на вход блока 3 с инверсныхвосьми выходов старших разрядов сум"матора поступает код 10101100, т.е.фактически значение восьми старшихразрядов числа х, после чего на выходе 9 блока 3 формируется остаток 40в обратном коде, равный 11111100,который записывается в старшие разряды сумматора 1, а на выходе 10формируется результат,равный 1101(фиг. 2), который записывается.в 45старшие разряды счетчика 2,.Далеесодержимое сумматора преобразуется вдополнительный код путем добавленияединицы в младший разряд сумматора,после чего содержимое сумматора исчетчика соответственно равно у =1.1111110010111100, 2 1 = 11010000.На этом первый этап предсказания корня заканчивается. На втором этапепотребуется выполнить еще два шага,В первом шаге к содержимому суммато"ра,прибавляется величина 2 2+ 1,а также единица в младший разрядсчетчика. После чего содержимое счетчика и сумматора соответственно равноу 1 = 1.1111111001011101,21= 1101000160Во втором шаге к содержимому сумма-.тора прибавляется величина 2 211+ 1а к содержимому счетчика - единицав младший разряд. Тогда у = 1=0.0000000000000000, 2= 11010010,и 5 процесс извлечения квадратного кор ня заканчивается.Таким образом, в предлагаемом устройстве извлечение квадратного корня из числа х : 1010110001000100 произведено на три шага, длительность каждого из которых примерно равна времени сложения 16-разрядных чисел. В известном же устройстве иэ.влечение корня из этого же числа потребовало бы выполнения 210 таких же по длительности шагов.Таким образом, изобретение позволяет существенно увеличить скорость извлечения квадратного корня,. Действительно, если в известном устройстве среднее время извлечения квадратного корня равно 2 ф" " Гс , то в предлагаемом оно составляет величину, примерно равную 2 -С,рт.е. среднее время извлечения квадратно,го корня в предлагаемом устройстве, в 2 раэ меньше в сравнении с прототипом. Пусть Е = 4, щ = 8, и = 16, тогда предлагаемое устройство в 16 раз быстрее, чем известное, Объем же дополнительно введенного оборудо" вания незначительный и равен примерно оборудованию 16-разрядного ком. бинационного сумматора со сквозным переносом (фиг, 2 и 3).Технико-экономическое Преимущество предлагаемого устройства состоит в существенном увеличении быстродействия известного устройства. Так, например, если ю = 8 и Е = 4, то быстродействие предлагаемого устройства примерно в 16.раз выше, чем быстродействие известного устройства, Объем же дополнительного оборудования незначительный и равен примерно оборудованию 16-разрядного сумматора со сквозным переносом.Формула изобретенияУстройство для извлечения квадратного корня, содержащее сумматор, счетчик, элемент И и генератор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом знакового разряда сумматора, а выходс входами младших разрядов счетчика и сумматора, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введен шифратор, первый вход и выход которого соединены соответственно с выходом и входом старших разрядов сумматора, второй выход шифратора соединен с входом старших разрядов счетчика, управляющий вход устройства соединен с управляющими входами счетчика и сумматора а также с третьим входом924702 ент",роектная,4 лиалУжгор элемента И, выход счетчика соединенс входом сумматора.Источники информации,принятые во внимание при экспертизе 1,Авторское свидетельство СССР Р 362297, кл. 6 06 Р 7/52,. 1969.2. Авторское свидетельство СССР 9 394781, кл. О 06 Р 7/38, 1971