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

 

Союз Советскик

Социалистических

Республик (11166155О(61) ДополнительнОе к авт. сеид-ву— (22) Заявлено 15.11,76 (21) 2420969/18-24 с присоединением заявки Ио— (23) Приоритет—

Опубликовано 05.05.79. Бюллетекь Ио 17 (51)М. Кл.

G 06 F 7/38

Государственный комитет

СССР ио делам изобретеиий и открытий (53) УДК 681.325. (088. 8) дата опфликоваиия описаиив 080579 (72) Авторы изобретен и я

Н.С. Востриков и Р.Д. Волошина (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРЛТНОГО КОРНЯ

Изобретение относится к области вычислительной техники и может быть использовано в специализированных устройствах для автоматической обработки информации в реальном масштабе времени.

Известно устройство для извлечения квадратного корня, содержаще@ регистры сдвига, регистры хранения результатов, сумматоры, счетчики, генераторы тактовых импульсов fl).

Недостатком известного устройства является низкое быстродействие и сложность управления.

Наиболее близким по техническому решению данной задачи является устройство, содержащее матрицу из строк и m столбцов идентичных вычислительных ячеек, разрядные шины входного кода, разрядные шины выходного кода, шину логического нуля и шину логической единицы (21.

Недостатком данного устройства является сравнительно небольшое быстродейстВие и сложность управления, т.к. в процессе вычисления производится пробное вычитание, в зависимости от знака результата которого производятся операции блокировки, передачи информации между строками

2 матрицы и исключение группы блоков устройства.

Целью изобретения является .повышение быстродействия.

Цель достигается тем, что в устройстве йервые входы вычислительных: ячеек двух младших разрядов в каждой строке соединены с соответствующими разрядными шинами входного кода, а первые входы остальных ячеек i-й строки (i=1 и) каждого столбца соединены с вйходами суммы вычислительных ячеек того же столбца (i -, l) строки, вторые входы вычислительных

>5 ячеек старших разрядов и двух младших разрядов каждой строки соединены с шиной логической единицы, вход переноса всех, вычислительных ячеек, .кроме ячеек младшего разряда, в каждой строке соединен с выходом переноса соседней ячейки младшего разряда в той же строке, вход сигнала переноса вычислительных ячеек младших разрядов всех строк соединен с шиной логического нуля, третьи и четвертые входы всех вычислительных ячеек, кроме ячейки старшего разряда, соединены соответственно с прямым и инверсным выходом переноса вычисли30 тельной ячейки старшего разряда той бб1550 же строки, выходы переноса вычисли тельных ячеек старшего разряда всех строк матрицы соединены с разрядными шинами ныходного кода, третий и четвертый входы ячейки старшего разряда первой строки соединены с прямыми и инверсными выходами переноса той же 5 ячейки, инверсный выход переноса вычислительной ячейки старшего разряда в j-й строке (j = 1,2,3... K) соединен со вторыми входами (j + 1) ячейки строк от j+l до К. l0

Другим отличием предлагаемого устройства является то, что в нем каждая ячейка содержит одноразрядный сумМатор и элемент И-ИЛИ, первый вход которого соединен с выходом однораз- )5 ряднбго сумматора, второй и третий

Входы — с четвертым и третьим входом ячейки соответственно, четвертый вход соединен с первыми входами ячейки и одноразрядного сумматора, а вы"ход — -с выходом суммы ячейки, прямой и инверсный ныходы одноразрядного сумматора соединены с одноименными выходами ячейки, а второй вход и вход переноса одноразрядного сумматора соединены с одноименными входами ячейки.

На фиг. 1 прецстанлена блок-схема устройства для извлечения квадратного корня, а на фиг. 2 — элементная схема ячейки матрйцы. Устройстно состоит иэ однотипных ячеек 1;, где

i=1,2... n-нбмер строки,a j =1,2...Êпорядковый номер ячейки в строке.

Количество К ячеек н первой строке равно двум, а в остальных строках 36 матрицы K=i+2 Шины разрядов входного кода 2 + 2 и подключены к первым йхо4 дам двух младших ячеек в каждой строке. Шины -разрядов выходного кода

3„—: Зп соединены с выходами стаРших 40 ячеек н каждой строке. Устройство.. содержит также шину 4 логической. единицы и шину 5 логического нуля.

Ячейки матрицы состоят из одноразрядного комбинационного. сумматора 6 и логического. элемента И-ИЛИ 7, кото рый в завйсимости от управляющих сигналов, поступающих на входы с и d, или формирует на выходе s ячейки результат суммирования 50 слагаемых, поступающих на входы а и .,b сумматора, или передает на выход s без изменения слагаемое, поступающее на вход Ь, т.е. разряд подкоренного выражения. Ячейки матричного устройства с индексами у которых 1 2„могут не содер жать логического элемента И-ИЛИ, так как формируемый на выходе з сигнал в дальнейшем процессе иэнлечения

60 квадратного;корня не используется.

Это объясняется алгоритмом извлечения квадратного корня и получаемой при этом структурой матричного устройства — наклонной матрицей с усечением ячеек в каждой строке. 65

На первую строку матрицы подаются дна старших разряда подкоренного вы- ражения. В результате вычислений на выходе р " первой ячейки формируется сигнал переноса, который является первым (старшим) разрядом результата извлечения квадратного корня. Одновременно сигнал переноса с выхода р и инверсный сигнал переноса с выхода р . первой ячейки поступают, соответственно, на входИ d и c ячеек первой строки матрицы.

В результате воздействия управляющих сигналов р и р на выходах s ячеек первой строки матрицы получается остаток, который поступает на входы Ь ячеек второй строки. Одновременно с остатком на вторую строку . матрицы подаются два следующих раз ряда подкоренного выражения. В llepной ячейке второй : строки формируются второй разряд результата извлечения квадратного корня, управляющие сигр выходах s вырабатывается очередной остаток, который совместно с последующими двумя разрядами подкоренного выражения поступает на входы "Ь ячеек третьей строки мат.рицы. В третьей строке матрицы и во всех последующих строках формируются аналогичные сигналы, при этом на каждую последующую строку передается остаток с предыдущей строки матрицы и сносятся два последующие разряда подкоренного выражения. Б процессе вычислений н и-строке матрицы формируется и-разряд результата извлечения квадратного корня, а на выходах в -остаток результата извлечения квадратного корня, Рассмотрим более подробно алгоритм извлечения квадратного корня н предлагаемом устройстве. Как было отмечено выше, в ячейки первой строки матрицы поступают дна старших разряда подкоренного выражения, иэ которых извлекается квадратный корень.

Старшие разряжаю подкоренного выражения могут иметь нид: 00,01,10 и 11, Квадратный корень из первого выражения равен нулю {а,(=0.), а н остальных трех случаях единйце (a =1) . Полученная величина возводится в квадрат и вычитается из старших разрядов подкоренного выражения. При а =0 подкоренное выражение не изменяется, аэ =О, а в остальных случаях иэ старУ ших разрядон вычитается величина 01 или добавляется 11 (так как, 11 есть число 01 н дополнительном коде). Прй суммировании старших разрядов под- коренного ныражения и числа 11 на выходе р ячейки старшего разряда сигнал переноса отсутствует (р =О) только в одном случае, когда старшие разряды подкоренного выражения равйы

00, а н остальных случаях на выходе появляется единица переноса (p =1) ."

661550

Таким образом, наличие или отсутствие единицы переноса определяет цифру результата: при p„ =l первая цифра результата а =1, а при р =О, а =О.

В соответствии с этим алгоритмом на входы b (фиг. 1) ячеек первой строки матрицы поступают два старших 5 разряда подкоренного выражения, а на входы а — комбинация 11. Наличие единицы переноса на выходе р ячейки старшего (первого) разряда свидетельствует о том, что первая цифра <О результата равна 1, отсутствие единицы переноса на выходе р ячейки старшего (первого) разряда свидетельствует о том, что первая цифра результата равна О. 15

Сигнал р и р с выхода ячейки первого (старшего) разряда поступают, соответственно, на входы d и с обеих ячеек этой же строки

/ матрицы и управляют работой логических элементов: при а =1, p=l, p=0 на выходах s ячеек образуют первый остаток В, равный разности между значением старших разрядов подкоренного выражения и а, а при 25 а„=О, р=О, р=l на выходах s ячеек появляется первый ост-.ток, равный значению старших разрядов падко ренного выражения, т.е. при а =О на ,выходах s ячеек появляются зна- 10 чения первого и второго разрядов подкоренного выражения без изменения.

Для отыскания второй цифры результата к первому остатку добавляются две очередные цифры подкоренного выражения (обозначим полученное число. ,через А) . Найденная ранее цифра результата удваивается и справа от нее приписывается максимально возможная цифра таким образом, чтобы полученное выражение, будучи умноженным на эту цифру, было бы равно или меньше А, Полученная цифра является второй циф-. рой результата. В двоичной системе умножить число на два означает, что к этому числу справа приписывается 45 нуль. Приписываемая затем справа цифра может быть 0 или 1, поэтому выражение, которое вычитается из А, имеет вид Оа 00 или Оа 01. Таким образом, в двоичной системе для определения 50 второй цифры результата достаточно сравнить Оа 01 со значением A. При этом, если Оа, 01 < А, то а =1, а на выходе ячейки старшего разряда появляется единица переноса, если же 55

Оа 01 >А, то а =Î, и единица переноса отсутствует, т.е. при вычислении второй цифры результата наличие или отсутствие переноса из ячейки старшего разряда второй строки матрицы служит указателем значения а>. при р2 О, а2 О, a npH 2 1, а2 полученйя второго оетатка В, необ" ходимого для вычисления третьей цифры результата, производится вычитание

В2=А-Оа401 . При а,=о В2= А-0001. а при 65 а =1 В.=A-0101, или при а„=О с

В2=А+1111 а при а =1 Вт=А+1011

В расСматриваемом устройстве при поступлении третьего и,. четвертого разрядов подкоренного выражения в младшие ячейки второй строки матрицы на входах Ь ячеек этой же строки образуется число А, а на Входах а, в зависимости от значения а, комбинация 1111 или 1011 ° Если а:=1, то р =1, р =0 и на выходах s ячеек второй строки матрицы образуется второй остаток, равный В, если .же а =О, то p =0 р =1 и яа выходах s ячеек второй строки появится второй. остаток, равный величине A.

Второй остаток с выхода ячеек второй строки матрицы поступает на входы Ь старших ячеек третьей строки матрицы, а на входы Ь младших разрядов ячеек этой же строки поступают следующие два разряда подкоренного выражения.

Процесс вычисления последующих цифр результата повторяется аналогично до тех пор, Пока не будут обработаны все разрядй подкоренного выражения. При 2п-разрядном подкоренном

;выражении матрица состоит из и строк.

Общее колиФествО ячеек в матрице определяется выраженйем

П

W= 2+ Ж (1+21, 1=2 где m — - число ячеек в матрице;

n â€, разрядность результата вычис-, ления.

Устройство извлечения квадратного корня обладает большим быстродействйем, что поэволяет при его использовании в специализированных вычислительных устройствах, работающих в реальном масштабе времени,,значительно повысить пропускную способность последних.

Увеличение быстродействия устройства достигается эа счет того, что в процессе извлечеиия квадратного корня количество промежуточйых операций сведено до мйнймумас в каждой строке матрицы обрабатывается одновременно два разряда подкоренного выражения, причем, при обработке двух разрядов ,подкоренного выражения возможно только одно переключение управляющим сигналом, который вырабатывается ячейкой самого старшего разряда (сигнал переноса и инверсный сигнал переноса) этой же строки матрицы, что позволяет обеспечивать работу вычислителя беэ внешнего устройства управления.

Формула изобретения

1. Устройство для извлечения квадратного корня, содержащее матрицу из и строк и m столбцов идентичных вычислительных ячеек, разрядные шины входного кода, разрядные шины выходного кода, шину логиЧеского нуля и шину логической единицы, о т л и ,ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в нем первые входы вычислительных ячеек двух младших разрядов в каждой строке соединены с соответствующими разрядными шинами входного кода, а первые входы остальных ячеек

i-й (i=1-n) строки каждого столбца соединены с выходами суммы Ъйчислительных ячеек того же столбца (i " 1) строки, вторые входы вычислительных ячеек старших разрядов и двух младших разрядой".каждой строки соединены с шиной логической единицы, вход переноса всех вычислительных ячеек, кроме ячеек младшего разряда в каждой строке, соединен с выходом переноса соседней ячейки младшего разряда в той же строке, вход сигнала переноса вычислительных ячеек младших разрядов всех строк соединен с шиной логического нуля, третьи и четвертые входы всех вы4ислительйяЫ . ячеек, кроме ячейки старшего разрядау соедийены соответственно с пряьым и инверсным выходом переноса вйчислительной ячейки старшего разряда той †же . строки, выходы переноса вычислительных ячеек старшего разряда всех строк матрицй соединены с разрядными

1.550 8 шинами выходного кода, третий и четвертый входы ячейки старшего разряда первой строки соединены с прямыми и инверсными выходами переноса той же ячейки, инверсный выход переноса вычислительной ячейки старшего разряда в j-й строке (3=1,2,3.....К) cîåäèнен со вторыми входами (j+1) ячейки строк от (j+1) до К.

2. Устройство для извлечения квадратного корня по п. 1, о т л и ч а ю1р щ е е с я тем, что в нем каждая ячейка содержит одноразрядный сумматор и элемент И-ИЛИ, первый вход которого соединен с выходом одноразрядного сумматора, второй и третий входы — с четвертым и третьим входом ячейки соответственно, четвертый вход соединен с первыми входами ячейки и одноразрядного сумматора, а выход — с выходом суммы ячейки, прямой и инверсный выходы одноразрядного сумматора соединены с одноименными вйходамИ ячейки, а,второй вход и вход переноса одноразрядного сумматора соединены с одноименными входами ячейки. й> Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

М 435805, кл. G Об F 7/38, 1974.

2. Патент Великобритании 91323771

30 кл. G 4 А,1973.