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

(50 4 ИЗОБРЕТЕН ОПИС темах ци в раэлич об те ки сигналов и втоматики для х сис мах ой реалиэа вадратного системе с ппаратур исления и операции в орня числа в сления. Цель повышении бы модулярно изобретен я состои сОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Научно-исследовательский институт прикладных физических проблемим. А. Н. Севченко(56) Авторское свидетельство СССРВ 1027718, кл, С 6 Р 7/552, 1981,Авторское свидетельство СССРУ 1278839, кл. С 06 Г 7/552,14.06;85.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТНОГО КОРНЯ ЧИСЛА В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ(57) Изобретение относится к вычислительной технике и ориентировано наиспользование в быстродействующихспециализированных вычислителях, систродеиствияПоставленная цель достигается тем, что в устройствосодержащее регистр 4 сдвига, блоки 6, 10мультиплексоров, блок 8 суммированиявычетов, блок 11 памяти констант,вспомогательный регистр 12, кольцевойсчетчик 13, блок 14 масштабирования,блок 18 элементов И, введены элементы 5, 15 задержки, блок 7 вычисленияинтервального индекса числа, блок 9регистров, блок 16 мультиплексоров,элементы И 17, 22, блок 19 модульныхсумматоров, блок 20 сравнения, блок21 деления на два, элемент ИЛИ-НЕ 23с соответствующими связями. 3 ил.1 13Изобретение относится к вычислительной технике и ориентировано наиспользование в быстродействующихспециализированных вычислителях, системах цифровой обработки сигналов ив системах автоматики для аппаратурной реализации операции вычисленияквадратного корня от аргументов,представленных в модулярной системесчисления.Целью изобретения является повышение быстродействия.На фиг, 1 приведена структурнаясхема предлагаемого устройства длявычисления квадратного корня числав модулярной системе счисления; нафиг, 2 - схема блока суммирования вы.четов; на фиг. 3 - схема блока деления на два,Устройство для вычисления квадратного корня числа в модулярнойсистеме счисления (фиг. 1) содержитвход 1 аргумента, установочный вход2, тактовый вход 3 устройства, регистр 4 сдвига, первый элемент 5задержки, первый блок 6 мультиплексоров, блок 7 вычисления интервального индекса числа, блок 8 суммирования вычетов, блок 9 регистров, второй блок 10 мультиплексоров, блок 11памяти констант, вспомогательныйрегистр 12, кольцевой счетчик 13,блок 14 масштабирования чисел, второй элемент 15 задержки, третий блок16 мультиплексоров, первый элементИ 17, блок 18 элементов И, блок. 19модульных сумматоров, блок 20 сравнения, блок 21 деления на два, второй элемент И 22, элемент ИЛИ-НЕ 23,выходы устройства: 24 результата,25 окончания операции, 26 окончаниявычисления квадратного корня и 27номера вычисленного квадратного корня,Блок 8 суммирования вычетов(фиг, 2) содержит элементы 28 памяти, регистры 29 и сумматоры 30 помодулю.Блок 21 деления на два (фиг. 3)содержит элементы 31 и 32 памяти,Блок 9 регистров представляет собой цепочку из 2 Т+5 последовательносоединенных регистров, где Т=31 о 1;через 1 Х( обозначено наименьшеецелое число не меньше Х, Установочный вход первого регистра являетсяустановочным входом блока 9 регистров, Через него осуществляется приеммодулярного кода (с,Ы, Ы.) исход 17434 50 ного числа А.из,диапазона 0=(-рМрМ -11 используемой модулярнойк-системы счисления , в , в.в - си стема попарно взаимно простых модулей , причем в), 2 р +1- 2 , р - фиксированное натуральное число М = П ви.- 1 1: 1Информационный вход первого регистраявля е т ся информационным входом блока 9 регистров и подключен к выходупоследнего ( 2 Т +5 ) - г о регистра блока. 9 регистров . Выход ( Т+ 1 ) -го регистрасоединен с входом блока 1 4 ма сштаби"рованияУправляющий вход запрещениявыдачи ( 2 Т+5 ) -го регистра являетсяуправляющим входом блока 9 регистровРазрядность регистра 4 сдвига составля ет ( ЗТ+6 ) бит . Регистр 4 накаждом такте работы устройства вЫпол;няе т сдвиг содержимого на один бит ,Выход ( 2 Т+5 ) - го триггера регистра 4сдвига и выход ( ЗТ+ 6 ) - г о триггерастаршего р аэряда регистра 4 сдвигаподключены к управляющему входу пер 25 вого блока 6 мультиплексоров и к управляющимм входам второго и третьегоблоков 1 0 и 1 6 мультиплексоров соответств енн о .Первый элемент 5 задержки представля е т собой цепочку и з ( Т+ 1 ) последовательно соединенных регистров .Второй элемент 1 5 задержки аналогично первому элементу 5 задержкипр едс тавля е т собой цепочку и з ( Т + 1,)35последовательно соединенных регистров.Разрядность регистров, входящихв состав блока 9 регистров, первогои второго элементов 5,15 задержки и40 мультиплексоров блоков 6 и 10 составнляет1 об в.1,Блок 8 суммирования вычетов(фиг, 2) по входному модулярному ко 45 ду (Ы,мК , ) некоторого числаАЮ осуществляет формирование за Ттактов вычета Я(А)=/0(А)/л, гдек-0(А) = Х Л;(;) 1 (1)=М /в;, 1=1,21 счерез ( Х( обоК значено ближайшее к Х целое число.При четном 1 во все, а при нечетномво все, кроме последнего, элемен5 13Используя формулы (4) и (5), получаем модифицированную процедуру вычисления квадратного корня исходного числа В. =+ А. 4+1 2 3(6) где А, - промасштабированное значение числа А на масштаб 28В качестве начального приближенияквадратного корня исходного числавыбирается величина В,.Итеративная процедура вычисленияквадратного корня завершается, есливыполняется равенство В. =В , что1+эквивалентно выполнению равенстваА д 1.В /2,Устройство для вычисления квадратного корня числа в модулярной системе счисления работает следующим образомеПо сигналу, подаваемому на установочный вход 2 устройства, происходит занесение соответствующей информации в регистр 4 сдвига и кольцевой счетчик 13, а именно: во всеразряды регистра 4 сдвига и младшийразряд кольцевого счетчика 13 записываются единицы. Сигналы, поступающие с выходов регистра 4 сдвига и выхода блока 20 сравнения, являютсяуправляющими сигналами. На каждомтакте работы устройства сигнал 6сформированный на выходе (2 Т+5) триггера регистра 4 сдвига, подается науправляющий вход первого блока 6мультиплексоров и вход выдачи кодаблока 9 регистров; сигнал б , сформированный на выходе последйеготриггера регистра 4 сдвига, поступает на управляющие входы блоков 10и 16 мультиплексоров; сигнал 6зсформированный на выходе блока 20сравнения, поступает на первый входвторого элемента И 22 и вход приемакода вспомогательного регистра 12.В зависимости от значений управляющихсигналов б6 и б производятсяф3действия, обеспечивающие поступлениетребуемой информации на входы блока 7 вычисления интервального индекса числа, блока 8 суммирования вычетов, блока 14 масштабирования чисел и блока 21 деления на два, атакже формирование содержимого вспомогательного регистра 12, Информация, снимаемая с выходов блока 7 вычисления интервального индекса и блока 8 суммирования вычетов, поступает17434 6 5 10 15 20 25 30 35 40 50 55 на адресный вход блока 11 памяти констант, на первом выходе которогоформируется модулярный код начальногоприближения значения квадратного корня числа, а на втором и третьем выходах - номера 1 и 1, соответствующих масштабов. Блок 14 масштабирования чисел выполняет операцию делениявходного числа, поступающего на информационный вход, на масштаб, номер которого подается на вход номерамасштаба. Блок 19 модульных сумматоров суммирует, а блок 20 сравненияпроизводит сравнение модулярных кодов, сформированных на выходах блока14 масштабирования чисел и блока 21деления на два, Модулярный код суммыс выхода блока 19 модульных сумматоров поступает на вход первого элемента 5 задержки и первый информационный вход первого блока 6 мультиплексоров. Содержимое кольцевого счетчика 13 пересылается во вспомогательныйрегистр 12 с выполнением операциипоразрядной дизъюнкции над их содержимым. В случае единичного сигналана входе приема кода вспомогательного регистра 12 в последнем формируется результат логического сложениясодержимых кольцевого счетчика 13 ивспомогательного регистра 12. Блок18 элементов И выполняет операциюлогического умножения (поразряднаяконъюнкция 7 содержимых кольцевогосчетчика 13 и вспомогательного регистра 12, результат которой поступает на входы элемента ИЛИ-НЕ 23,вход которого подключен к второмувходу второго элемента И 22. В случае одновременного поступления единичных сигналов на входы второгоэлемента И 22 на выходе 26 устройства появляется сигнал завершенияитеративной процедуры (то есть вычисление значения квадратного корня)для очередного аргумента, номер которого определяется унитарным кодом,поступающим с выхода кольцевого счетчика 13 на выход 27 устройства. Вычисленное значение квадратного корняснимается с выхода блока 19 модульных сумматоров на выход 24 устройства, В случае завершения работы устройства по вычислению функции квадратного корня от всех входных аргументов соответствующий сигнал появляется на выходе 25 устройства,На первом такте работы устройства в первый регистр блока 9 регист 13 ров с входа 1 аргумента устройства поступает модулярный код числителя А значения А/р Маргумента, который также поступает на второй информационный вход блока 6 мультиплексоров, на управляющий вход которого поступает сигнал о =1, вслед 9 ствие чего с выхода блока 6 мультиплексоров величина А поступает на входы блока 7 вычисления интервального индекса числа и блока 8 суммирования вычетов.По истечении Т-го такта на выходах блока 7 вычисления интервального индекса и блока 8 суммирования вычетов формируатся соответственно вычеты Ф(А) и С(А) (см. (1) и (3, которые на (Т+1)-м такте работы устройства подаются на адресный вход блока 1 1 памяти констант, в результате чего на его входы поступает набор констант На (Т+2)-м такте работы на управляющие входы блоков 10 и 16 мультиплексоров поступает сигнал б =1,вследствие чего модулярный код начального приближения В , поступающийс первого выхода блока 11 памяти констант на второй информационный входвторого блока 10 мультиплексоров,записывается в первый регистр второго элемента 15 задержки, а величина1 , поступающая с третьего выходаблока 1 1 памяти констант на второйинформационный вход третьего блока16 мультиплексоров, проходит на входномера масштаба блока 14 масштабирования чисел, на информационный входкоторого с выхода блока 9 регистровпоступает величина А,На (2 Т+3)-м такте работы устройства величина В, с выхода второгоэлемента 15 задержки поступает навход блока 21 деления на два.По истечении(2 Т+4)-го такта навыходах блока 14 масштабирования чисел и блока 21 деления на два формилруются соответственно величины Аикоторые на (2 Т+5)-м тактеВо2поступают на первый и вторые входыблока 19 модульных сумматоров и блока 20 сравнения соответственно, Блок19 модульных сумматоров находит модулярный код величины В (см, 6, а1а на выходе блока 20 сравнения формируется сигнал бз, На этом завер 17434 8шается первая итерация вычисленияквадратного корня. Появление единичного сигнала на выходе второго элемента И 22 указывает на окончаниеитеративного процесса вычисленияквадратного корня аргумента А/р М9значение которого равно В, и снимается с выхода блока 19 модульных сумматоров, а унитарный код номера вычис ленного корня поступает на выход 27устройства. В случае нулевого сигнала на выходе второго элемента И 22продолжается процесс вычисления квадратного корня.15 На (2 Т+6)-м такте работы устройства на управляющий вход первого бло -ка 6 мультиплексоров и на управляющий вход запрещения выдачи кода(2 Т+5)-го регистра блока 9 регистровпоступает сигнал б; = О. ВеличинаВ с выхода блока 19 модульных сумма 1торов поступает на вход первого элемента 5 задержки и через первый блок6 мультиплексоров - на входы блока 7 25 вычисления интервального индекса числа и блока 8 суммирования вычетов, авеличина А с выхода блока 9 регистровзаписывается в первый регистр блока9 регистров,30 По истечении (ЗТ+5)-го такта блок7 вычисления интервального индексачисла и блок 8 суммирования вычетовформируют на своих выходах величинылТ(В,) и Я(В) соответственно, которые поступают на адресный вход блока 11 памяти констант на (ЗТ+6)-мтакте работы устройства.На (ЗТ+7)-м такте на управляющиевходы блоков 10 и 16 мультиплексоров 40 поступает сигнал В = О, вследствиечего величина В с выхода первого1элемента 5 задержки через второй блок10 мультиплексоров проходит на входвторого элемента 15 задержки, а ве 45 личина 1 через блок 16 мультиплексоров поступает на вход номера масштаба блока 14 масштабирования чисел.На информационный вход блока 14 масштабирования чисел с выхода блока 9 50 регистров поступает величина А.На (ЬТ+8)-м такте работы величинаВ с выхода второго элемента 15 за 1держки поступает на вход блока 21деления на два.55По истечении (4 Т+9)-го такта навыходах блока 14 масштабированиячисел и блока 21 деления на два формируются соответственно величины,л ВА, и 1 -, которые на (4 Т+1 О)-мтакте работы устройства поступаютна первые и вторые входы блока 19модульных сумматоров и блока 20сравнения соответственно, Блок 21модульных сумматоров находит модулярный код величины В (см. (6), ана выходе блока 20 сравнения формируется сигнал б, На этом завершаетзся вторая итерация вычисления квадратного корня,Итеративный процесс вычисленияквадратного корня продолжается дотех пор, пока на выходе 26 устройства не появится сигнал завершения итеративной процедуры.Благодаря конвейерной структурев устройстве для вычисления квадратного корня в модулярной системе20счисления описанная итеративная процедура может выполняться одновременно для 2 Т+5 аргументовПосле появления единичного сигнала на выходе 25 устройства может бытьначато вычисление функции квадратного корня от новых(2 Т+5) аргументов.При работе устройства в конвейерном режиме формирование 2 Т+5 Функциональных (квадратных корней) всреднем занимает (2 Т+5) тактов,где и - число итераций реализуемсяпроцедуры, т.е. из расчета на однофункциональное значение быстродействие устройства составляет п тактов,Формула изобретенияУстройство для вычисления квадратного корня числа в модулярной систе 40 ме счисления, содержащее регистр сдвига, два блока мультиплексоров, блок суммирования вычетов, блок памяти констант, вспомогательный регистр, кольцевой счетчик, блок умножения на масштабный коэффициент и45 блок элементов И, причем установочный вход устройства соединен с установочными входами регистра сдвига и кольцевого счетчика, счетный вход которого соединен с тактовым входом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок регистров, два элемента задержки, блок вычисления интервального индекса, третий блок мультиплексоров, два элемента И, блок модульных сумматоров, блок сравнения, блок деления на 34 10два и элемент ИЛИ-НЕ, причем тактовый вход устройства соединен с входом разрешения сдвига регистра сдви" га, выход (2 Т+5)-го разряда регистра сдвига (Т = 1 ор 1:(, 1 - число модулей системы счисления) соединен с входом запрещения выдачи блока регистров и с управляющим входом первого блока мультиплексоров, выход старшего (ЗТ+6)-го разряда регистра сдвига соединен с управляющими входами второго и третьего блоков мультиплексоров, вход аргумента устройства соединен с установочным входом блока регистров, выход последнего регистра которого соединен с информационным входом блока регистров, выход (Т+1)-го регистра которого соединен с информационным входом блока умиоже" ния на масштабный коэффициент, вход номера масштаба которого соединен с выходом третьего блока мультиплексоров, выход блока умножения на масштабный коэффициент соединен с входом первого слагаемого блока модульных. сумматоров и с первым входом блока сравнения, второй вход которого соединен с входом второго слагаемого блока модульных сумматоров и с выходом блока деления на два, выход блока модульных сумматоров подключен к входу первого элемента задержки и к первому информационному входу . первого блока мультиплексоров, второйинформационный вход которого подключен к входу аргумента устройства, . выход первого блока мультиплексоров соединен с входами блока вычисления интервального индекса числа и блока суммирования вычетов, выходы которых подклюЧены соответственно к входам старших и младших разрядов, адреса блока памяти констант, выход первого элемента задержки соединен с первым информационным входом второго блока мультиплексоров, второй информационный вход которого, первый и второй информационные входы третьего блока мультиплексоров соединены соответственно с выходами блока памяти констант, выход второго блока мультиплексоров соединен с входом второго элемента задержки, выход которого соединен с входом блока деления на два, разрядный выход вспомогательного регистра соединен с входами первого элемента И и с первым входом блока элементов И,/Редактор А. Маковс в екторМ, Ша Заказ 2425/44ВНИИ Подписное Тираж 672 ПИ Государственного по делам изобретений 35, Москва, Ж, Раушмитета СС Открытий ая наб., д5 изводственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4 11 131 второй вход которого соединен с информационным входом вспомогательного регистра и с разрядным выходом кольцевого счетчика, выход блока сравнения соединен с входом разрешения приема вспомогательного регистра и с первым входом второго элемента И, второй вход которого соединен с выходом элемента ИЛИ-НЕ, входы которо 7434 12го соединены с разрядным, выходомблока элементов И, выходы блока модульных сумматоров, первого и второго элементов И, кольцевого счетчикаявляются. соответственно выходами результата, окончания операции, окончания вычисления квадратного корняи номера вычисленного квадратногокорня устройства,