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

, - 1 : Изобретение относится к области вычислительной техники и может быть использовано в специализированных устройствах для автоматической обра ботки информации в реальном масштаб времени. . Известно устройство для извлечения квадратного корня, содержащее регистры сдвига, регистры хранения результатов/ сумматоры, счетчики, генераторы тактовых импульсов 1. Недостатком известного устройства явлйется низкое быстродействие и сложность управления. Наиболее близким по техническому решению данной задачи является устройство, содержащее матрицу из п строк и m столбцов идентичных вычис лительных , разрядные шины входного ксэда, разрядные шины выход ного кода, шину логического нуля и шину логической единицы 2. Недостатком данного устройства является сравнительно неболыиое быстродействие и сложность управления, т.к. в процессе вычисления про изводится пробное вычитание, в зави симости от знака результата которог производятся операции блокировки. передачиинформации между строками матрицы и исключение группы блоков устройства. Целью изобретенияявляетсй .повышение быстродействия. Цель достигается тем, что в устройстве Первые вход вычислительных ячеек двух мпадашх ра:зрядов в каждой строке соединены с соответствующими разрядными шийаг входного ;кода, а первые входы остальных ячеек 1-й строки ( - п) каждого столбца соединены с выходами суМ1ЛЫ вычислительных ячёек того же столбца (i т 1) строки, вторые входы вычислительных ячеек старших разрядов и двух младших разрядов каждой строки соединены с шиной логической единицы, вход переноса всех .вычислительных ячеек, кроме ячеек младаех о рйзряда, в каж дои строке соединен с выходом переноса соседней ячейки младшего разряда в той же строке, вход сигнала переноса вычислительных ячеек младших разрядов всех строк соединен с шиной логического нуля, третьи и четвертые входы всех вычислительных ячеек, кроме ячейки старшего разряда, соединены соответственно с прямым и инверсным выходом переноса вычислительной ячейки старшего разряда той же строки, выходы переноса вычисли тельных ячеек старшего разряда всех строк матрицы соединены с разрядными шинами выходного кода, третий и четвертый входы ячейки старшего разряда первой строки:соединеныс прямыми и инверсными выходами переноса той же ячейки, инверсный выход переноса вычислительной ячейки старшего разряда в j-й строке (J 1,2,3...К) соедине со вторыми входами (j + 1) ячейки строк от J + 1 до К. Другим отличием предлагаемого уст - ройства является то, что в нем кажДая ячейка содержит одноразрядный сумматор и элемент И-ИЛИ, первый вхо которого соединен с выходом;одноразрядного сумматора, второй и третий йходы - с четвертым и третьим входом -ячЕейки соответственно, четвертый . вход соединен с первыми входаьш ячей ки и одноразрядного сумматора, а вы- хдд - с выходом суммы ячейки, прямой и инверсныйвыхода одноразрядного сумматора Соединены-с одноимёнными выходами ячейки, а второй входИ вхо пфенОса одноразрядного .сумматора соединены с одноименными входами, ячейки. . На фиг. 1 представлена блок-схема устройства Для извлечения квадратного корня, а на фиг. 2 - элейёйТНай схема ячейки матрицы. Устройство состоит из; однотипных ячеек , где ,2 ... п-нбмер строки,а j 1,2,..К ;порядковый номер ; ячейки в йт|50ке-. Количество К/ячеек в-первой строке равноДйум, а в остальных строках матрицы . Шины разрядов BxcftHor кода 2f, подключены к первым вйодам двух младших ячеек в каждой стро ке. Шины;раз15ядов выходного кода 3 4 3 f соединены с выходами старших ячеек в каждой строке. Устройство-. содержит также шину 4 логической .еди ницы и шину 5 логического нуля. Ячейки MaT№4 S cocto Tй з 5Диораз рядного комбинационного , сумматор.а б и логического-Элемента И-ИЛИ 7, кото рый в эавйёймостиОТ управляюЬй-п- сигналов, поступающих на входа с и d, или фо:рмирует На вйходе s ячейки результат суммирования слагаемых, поступающих на входыа Ь сумматора, или передает на без йзменёния слагаемое, поступающее на вход Ь, .т.е. разряд подкоренного выражения. Ячейки матричного устройства с индексами i , у которых могут не со держать логического элемента Й-ИЛИ, так как формируемый на выходе в сигнал в дальнейшем ripouecce извлечения квадратного ;корня неиспользуется. Это объйёняётся алгоритмом извлечения ква атного корня и получаемой при.этом структурой матрйчн ого устройства - наклонной матрицей с усечением ячеек в каждой строке. На первую строку матрицы подаются ва старших разряда подкоренного выражения, В результате вычислений на выходе р первой ячейки формируется сигнал переноса, который является первым (старшим) разрядом результата извлечения квадратного корня. Одновременно сигнал переноса с выхода р и инверсный сигнал переноса с выхода р. первой ячейки поступают, соответственно, на вхоДйГd и с ячеек.первой строки матрицы. В результате в оздействия управляющих сигналов Р и р на выходах s ячеек первой строки матрицы получается остаток, который поступает на входы . Ь ячеек второй строки. Одновременно с остатком на вторую строку . матрицы подаются два следующих разряда подкоренного выражения. В первой ячейке второй- строки формируются второй разряд результата извлечения квадратного корня, управляющие сигналы на выходах р и , а на выходах s вырабатывается очередной остаток, который совместно с последующими двумя разрядами подкоренного выражения поступает на вхоячеек третьей строки мат.рицы. В третьей строке матрицы и во всех последующих строках формируются аналогичные сигналы, при этом на каждую последующую строку передается остаток с предыдущей строки матрицы . И сносятсядв-апоследующие разряда йодкорённого выражения.-в процессе вычислений в п-строке матрицыформируется п-раэряд результата извле чёния квадратного корня, а на выхо.дах; .таток результата извлечения квадратного корня. Рассмотрим более.подробно алгоритм извлечения квадратного корня в предлагаемом устройстве. Как бьто отмечено вьгае, в ячейки первой строки матрицы поступают два .старших разряда подкоренного выражения, из которйх йэвлакаэт,ся квадратный корень. Старшие разряды подкоренного выражения могут иметь вид: 00,01,10 и 11. Квадратный корень из первого выражения равен нулю (), а .в .остальных трех случаях единице (а, 1) . Получен иая величина возводится в квадрат и вычитается из старших разрядов.подкоренного выраженияе При а,0 подкоренное выражение не изменяется, а 0, а в остальных случаях из старших разрядов вычитается величина 01 или добавляется 11 (так. как, 11 есть число 01 s дополнительном коде).-При сумйироаанмк старших разрядов под- коренного выражения и числа 11 на : выходе р ячейки старшего разряда сигМал первноса отсутствует () только в одном случае, когда старшие разряда подкоренного выражения равны 00, а в остальнык случаях на выходе появляется единица переноса ()iТаким образом, наличие или отсутстви единицы переноса определяет цифру результата: при первая цифра результата а 1, а при Р 0 , а 0 . В соответствии с этим алгоритмом на входа Ь (Фиг. 1) ячеек первой строки матрицы поступают два старших разряда подкоренного выражения, а на комбинация 11, Наличи единицы переноса на выходе р ячейки старшего(первого) разряда сви детельствует о том, что первая цифра результата равна 1, отсутствие единицы переноса на выходе р ячейки старшего (первого) разряда свидетель ствует о том, что первая цифра результата равна 0. Сигнал р и р с выхода ячейки первого (старшего) разряда поступают, соответственно, на входы d и с обеих ячеек этой же строки ., матрицы и управляют работойлогических элементов: при а.1, , на выходах s ячеек образуют первый остаток В, равный разности между значением старших разрядов подпрккоренного выражения и а , а npi , , на выходах s ячеек появляется первый ост-лток, рав ный значению старших разрядов подко рениого выражения, т.е. при а,0 на .выходах-s ячеек появляются значения первого и второго разрядов под коренного выражения без изменения. Для отыскания второй цифры резуль тата к первому остатку добавляются; две очередные цифры подкоренного выражения (обозначим полученное число. .через А). Найденная ранее цифра результата удваивается и справа от нее приписывается максимально возможная цифра таким образом, чтобы по.лученно выражение, будучи умноженным на эту. цифру, было бы равно или меньше А. Полученная цифра является второй ци$ рой результата. В двоичной системе умножитьчисло на два означает,что. к этому числу справа приписывается нуль. Приписываемая затем справа циф ра может быть О или 1, поэтому выражение, которое вычитается из А, имеет вид Oaj00 или Оа 01. Таким образом, в двоичной системе для определения второй цифры результата достаточно сравнить со значением А, При эт(м, если Оа., то , а на выходе ячейки старшего разряда появляется единица переноса, если же А, то , и единица переноса отсутствует, т.е. при вычислении второй цифры результата наличие или .отсутствие переноса из ячейки старjuiero разряда второй строки матрицы служит указателем значения при , , а при . Для получения второго остатка Bj,, необходимого для вычисления третьей цифры результата, производится вычитание . При Bg A-OOOl, а пр а.1 В,,А-0101, или при а 0 В- А+11И, а при В,,А+1011. В рассматриваемом устройстве при поступлении третьего и четвертого разрядов подкоренного выражения в младшие ячейки второй строки матрицы ячеек этой же строки на входах образуется число А, а на ;йходаха, в зависимости от значения а,, кЬмбинация 1111 или 1011 а.1, то , р 0 и на выходах s. ячеек второй строки матрицы образуется второй остаток, равный В2, если .же а 0, то , и на выходах s ячеек второй строки появится второй остаток, равный величине А. Второй остаток с выхода ячеек BJOрой строки матрицы поступает.на вхо- ды Ь старших ячеек третьей строки матрицы, а на входы Ь младших разрядов ячеек этой же строки поступают следующие два разряда подкорен.ного выражения. ; Процесс вычисления прсл едую1дих цифр результата повторяется аналогично до тех:пор, ttoka не будут обработаны все разряды подкоренного выражения. При 2п-разрядном подкоренном (выражении матрица состоит из ft строк. Общее количсеётвс ячеек в матрице -определяется вырайсёнйем . , (i-«-2 . - . - - V. --, -2 где т- чйслд ячеек и матрице; п -: разряднЬсть результата вь1чис-. ЛеНИЯ.. .:;: .:: - : ::: ..;:., . , .J Устройство и:эвлеч1ения квадратного корня обладает .долйшйм ёыстродействйем, что ЯОЭйЬляет при его использовании в Спёдиайизированных вычислительных устройствах, работающих в реальном масштабе времени, |3 нйчйтельно повысить пропускную спосрбность последних. /- .;:::. .;. / УвелиЧейие быстродействия устройства достИгаеФся за счет того, .что в процессе иёвлечШия квадратного корня количество промежуточных операций сведено до минимума: в каждой строке матрицы обрабатывается одновременно два разряда подкоренного выражения, причем, при обработке двух разрядов подкоренного выражения возможно только одно перек.Пючение управляющим сигналом, который вырабатывается . ячейкой самого старяего разряда (сигнал переноса и инверсный сигнал переноса) этой же строки матрицы, что позволяет обеспечивать работу вычислителя без внешнего устройства управления. Формула изобретения. 1. Устройство для извлечения квадратного корня, содержащее матрицу из п строк и m столбцов идентичных вычислительных ячеек, разрядные шины