Устройство для извлечения квадратного корня Советский патент 1985 года по МПК G06F7/552 

Изобретение относится к вычислительной технике и может быть исполь зовано в быстродействующих процессорах и специализированных вычислительных устройствах, работающих в реальном масштабе времени с -высокой тактирующей частотой. Целью изобретения является сокра щение аппаратурных затрат. На чертеже приведена структурная схема предлагаемого устройства. Устройств.0 содержит входы 1, на которые подаются разряды входного блок 2 постоянной числа а , .. . ,a2i памяти, выходы 3, с которых снимаются разряды выходного числа р. выходы 4 блока 2 постоянной памяти, с которых снимаются разряды остаточного числа, одноразрядные полные сумматоры 5, элементы 6 слож ния по модулю два, элементы НЕ 7, щину 8 логической единицы, шину 9 логического нуля. Устройство позволяет извлекать квадратный корень из чисел, имеющих 2П двоичных разрядов с представлением результата в виде п-разрядного двоичного числа, при этом разрядность входного числа может быть любой и не ограничивается разрядностью блока постоянной памяти. Пусть подкоренное выражение представлено в прямом двоичном коде в виде числа А, имеющего разрядность 2п, так что выполняется условие : О А 1, а число А О, а , а j, а, ..,а,2„, где aj - младпшй разряд исходного числа. Операция извлечения квадратного корня состоит из п шагов, причем первые m шагов вьтолняются с помощь блока постоянной памяти. 1-и шаг. Сложение а И а С логи ческой единицей. При этом сигнал переноса р. опре деляет первый, старший разряд резул тата, а сигнал суммы q|. является старшим разрядом первого слагаемого второго шага. Производится сложение а, 2-й шаг. Формируется первое слагаемое, старший разряд q формируется при 1-м шаге, второй разряд определяется как иргверсия второго разряда исходного числа (а ), третий разряд первого слагаемого - а,. Второе слагаемое формируется в виде р,О 1. Производится сложение Ч,., 2 3 Р. О 1 РаЧ,. Сигнал переноса р определяет второй разряд результата. 3-й шаг. Первое слагаемое формируется в виде q.g . Второе слагаемое формируется в виде р,,Р2®р, О 1, где pjQp, - сложение по модулю два сигналов р и р . Производится сложение 4,-i a-iSj Р Pj®P, О 1 P i- la-Hvz - - Сигнал переноса р определяет третий разряд результата. 4-й шаг. По аналогии производится сложение Н2-}Яз-Ич-э б г Рз Р50р.рз®р2 01 Р..Н,-4Я4-4Яб-4 в общем случае -для j -го шага следует производить операцию сложения вида , 2-(i-i v{j-i)Hi-( PjH P -l®PlP -,®Pj-70 « li-n-j Hj.j H( Рассмотрим работу устройства в предположении, что . Устройство работает следующим образом. Разряды подкоренного выражения поступают на входы 1, при этом первые 2т старших разрядов поступают на входы блока 2 постоянной памяти в качестве адресных сигналов, С помощью блока 2 постоянной памяти вычисляются первые m шагов алгоритма (для рассматриваемого случая -первые четыре шага алгоритма. С выходов блока 2 постоянной памяти снимается га-разрядный результат, который поступает на первые m шин выходных разрядов 3, (т.е. значения Р|-Р), а с.выходов 4-т-рарядный остаток (т.е. значения Ч

qv4 4s-4 )

(т+1)-й шаг алгоритма совершается с помощью последовательно соединенных сумматоров 5 первой группы, элементов 6 сложения по модули два первой группы и элемента НЕ 7, подключенного к входу а, (я,,) устройI m п

ства.

Аналогично (ra+k)-ff mat алгоритма (,...,n-m) совершается с помощью последовательно соединенных сумматоров 5 k-й группы, элементов 6 сложения по модулю два k-й группы и элемента Н 7, подключенного к входу (а„ +2k-2) устройстftrt

ва.

УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее (n-m) Z групп, где m п, п -:г, Z - разрядность подкоренного числа в двоичном коде, изN(, где k - номер группы) последователь но соединенных одноразрядных, полньк сумматоров, отлийающ ее с я тем, что, с целью сокращения аппаратурных затрат, в него введены блок постоянной памяти, имекщий 2 m входов и 2 m выходов, (n+m-3)(n-m) Tj элементов сложения по модулю два и (n-m) злементов НЕ, причем входы блока постоянной памя ти подключены соответственно к ftep вым 2 m разрядам входа устройства, первый и второй входы N-ro сумматора k-й группы подключены соответственно к