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

Союз СоветскикСоциалистическихРеспублик оц 66155 О 1 Ы 1 К полнительнОе к авт. сеид-в 18-24. (53)М. КЛ(23) Приоритет -242 96 06 Г 7/3 ствеиныи комитет СССР елей изобретеиий открытий.С. Востриков и Р.Д. Волошина 54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРЛТНОГО КОРНЯ 2 матрицы и исключение группы блоковустройства,Целью изобретения является .повышение быстродействия,Цель достигается тем, что в устройстве йервые входы вычислительных:ячеек двух младших разрядов в каждойстроке соединены с соответствующимиразряднымишинами входного кода, апервые входы остальных ячеек 1-йстроки (1=1 - и) каждого столбца соединены с вйходами суммы вычислительных ячеек того же столбца (1 -, 1)строки, вторые входы вычислительных5 ячеек старших разрядов и двух младших разрядов каждой строки соединеныс шиной логической единицы, вход переноса всех вычислительных ячеек,.кроме ячеек младшего разряда, в каждой строке соединен с выходом переноса соседней ячейки младшего разряда в той же строке, вход сигналапереноса вычислительных ячеек младших разрядов всех строк соединен сшиной логического нуля, третьи ичетвертые входы всех вычислительныхячеек, кроме ячейки старшего разряда,соединены соответственно с прямым иинверсным выходом переноса вычислиО тельнбй ячейки старшего разряда той извлечержащееранениятчики,ов 11) .ойствавие и 2 О Изобретение относится к областивычислительной техники и может бытьиспользовано в специализированныхустройствах для автоматической обработки инФормации в реальном масштабевремени,Известно устройство дляния квадратного корня, содерегистры сдвига, регистры хрезультатов, сумматоры, счегенераторы тактовых импульсНедостатком известного устрявляется низкое быстродейстсложность управления,Наиболее близким по техническомурешению данной задачи является устройство, содержащее матрицу изстрок и ю столбцов идентичных вычислительных ячеек, разрядные шинывходного кода, разрядные шивы выходного кода, шину логического нуля ишину логической единицы (2).Недостатком данного устройстваявляется сравнительно небольшоебыстродейстВие и сложность управления, т.к. в процессе вычисления производятся пробное вычитание, в зависимости от знака результата которогопроизводятся операции блокировки,передачи инФормации между строками екь Иф 17 (53) УДК 681,32же строки, выходы переноса вычислительных ячеек старшего разряда всехстрок матрицы соединены с разряднымишинами выходного кода, третий и четвертый входы ячейки старшего разрядапервой строки соединены с прямыми иинверсными выходами переноса той же 5ячейки, инверсный выход переноса вычислительной ячейки старшего разрядав 3-й строке (3 = 1,2,3 К) соединенсо вторыми входами ( + 1) ячейкистрок от 1+1 до К. 0Другим отличием предлагаемого устройства является то, что в нем каждая ячейка содержит одноразрядныйсумматор и элемент И-ИЛИ, первый входкоторого соединен с выходомодноразряднбго сумматора, второй и третийВходы - с четвертым и третьим входомячейки соответственно, четвертыйвход соединен с первыми входами ячейки и одноразрядного сумматора, а вы-"хбд - с выходом суммы ячейки, прямойи инверсныйвыходы одноразрядногосумматора соединены с одноименнымивыходами ячейки, а второй вход и входпереноса одноразрядного сумматорасоединены с одноименными входамиячейки,На фиг. 1 прецставлена блок-схемаустройства для извлечения квадратного корня, а на фиг. 2 - элементнаясхема ячейки матрйцы, устройствосостоит иэ однотипных ячеек 1;, где3.=1 с 2 .,и-нбмер строки,а) =1,2 Кпорядковый номер ячейки в строке,Количество К ячеек в первой строкеравво двум, а в остальных строках 35матрицы К=1+2. Шины разрядов входногокода 2 + 2 п подключены к первым входам двух младших ячеек в каждой строке. Шины -разрядов выходного кода3 + 3 и соединены с выходами старших 40ячеек в каждой строке, устройствосодержит также шину 4 логической единицы и шину 5 логического нуля,ячейки матрицы состоят из одноразрядного комбинационного сумматора 6 45и логического. элемента И-ИЛИ 7, который в завйсимостиот управляющихсигналов, поступающих на входы си й, или формирует на выходез ячейки результат суммирования 50слагаемых, поступающих на входыаи .",Ьф сумматора,или передает навыход 1 з без изменения слагаемое,поступающее на вход Ь, т.е. разряд подкоренного выражения, Ячейки 55матричного устройства с индексами1,), у которых 1)2 могут не содержать логического элемента И-ИЛИ, таккак формируемый на выходезсигнал в дальнейшем процессе извлечения60квадратного;корня неиспользуется,Это объясняется алгоритмом извлечения квадратного корня и получаемойпри этом структурой матричного устройства - наклонной матрицей с усечением ячеек в каждой строке,На первую строку матрицы подаютсядва старших разряда подкоренного вы-ражения, В результате вычислений навыходе р" первой ячейки формируется сигнал переноса, который являетсяпервым (старшим) разрядом результатаизвлечения квадратного корня, Одновременно сигнал переноса с выходар и инверсный сигнал переноса свыхода р. первой ячейки поступают,соответственно, на входы 1 с)1 ис ячеек первой строки матрицы,В результате воздействия управляющихсигналов р и р на выходах з ячеекпервой строки матрицы получаетсяостаток, который поступает на входы .Ьф ячеек второй строки. Одновременно с остатком на вторую строку .матрицы подаются два следующих разряда подкоренного выражения. В первой ячейке второй: строки формируютсявторой разряд результата извлеченияквадратного корня, управля 1 ощие сигналы на выходах р и р, а навыходах зф вырабатывается очередной остаток, который совместно споследующими двумя разрядами подкоренного выражения поступает на входы "Ь ячеек третьей строки мат.рицы, В третьей строке матрицы и вовсех последующих строках формируются аналогичные сигналы, при этом накаждую последующую строку передаетсяостаток с предыдущей строки матрицыи сносятся два последующие разрядаподкоренного выражения. В процессевычислений в п-строкематрицы формируется и-разряд результата извлечения квадратного корня, а на выходах з-остаток результата извлечения квадратного корня,Рассмотрим более подробно алгоритмизвлечения квадратного корня в предлагаемом устройстве. Как было отмеченовыше, в ячейки первой строкиматрицы поступают два старших разряда подкоренного выражения, иэ которых извлекается квадратный корень.Старшие разряжаю подкоренного выражения могут иметь вид: 00,01,10 и 11.Квадратный корень из первого выражения равен нулю (а=О), а в остальныхтрех случаях единйце (а =1), Полученная величина возводится в квадрати вычитается из старших разрядов под"коренного выражения. При а=О подкоренное выражение не изменяется,аэ =О, а в остальных случаях иэ стар.ших разрядов вычитается величина 01или добавляется 11 (так как, 11 естьчисло 01 в дополнительном коде). Присуммировании старших разрядов под-коренного выражения и числа 11 навыходе р ячейки старшего разрядасигнал переноса отсутствует (р =О)только в одном случае, когда старшиеразряды подкоренного выражения равйы00, а в остальных случаях на выходепоявляется единица переноса (р)=1);Таким образом, наличие или отсутствие единицы переноса определяет цифру результата: при р =1 первая цифра результата а =1, а при р =О, а =О,В соответствии с этим алгоритмом на входы Ь (фиг, 1) ячеек первой строки матрицы поступают два старших 5 разряда подкоренного выражения, а на входы а - комбинация 11, Наличие единицы переноса на выходе р ячейки старшего(первого) разряда свидетельствует о том, что первая цифра (О результата равна 1, отсутствие еди" ницы переноса на выходе рф ячейки старшего (первого) разряда свидетель.ствует о том, что первая цифра результата равна О. 15Сигнал р и р с выхода ячейки первого (старшего) разряда поступают, соответственно, на входы д и с обеих ячеек этой же строки матрицы и управляют работой логичес ких элементов: при а=1, р=1, Р=О на выходах з ячеек образуют первый остаток В 4, равный разности между значением старших разрядов подкоренного выражения и а, а при 25 а=О, р=О, р=1 на выходах з ячеек появляется первый ост-.ток, равный значению старших разрядов падко ренного выражения, т.е. при а 4 =0 на ,выходах з ячеек появляются зна- ЗО чения первого и второго разрядов подкоренного выражения без изменения.Для отыскания второй цифры результата к первому остатку добавляются две очередные цифры подкоренного выражения (обозначим полученное число. ,через А), Найденная ранее цифра ре- зультата удваивается и справа от нее пРиписывается максимально возможная цифра таким образом, чтобы полученное выражение, будучи умноженным на эту цифру, было бы равно или меньше А, Полученная цифра является второй циф-. рой результата. В двоичной системе умножить число на два означает, что к этому числу справа приписывается 45 нуль. Приписываемая затем справа цифра может быть 0 или 1, поэтому выражение, которое вычитается из А, имеет вид Оа 400 или Оа 401. Таким образом, в двоичной системе для определения 50 второй цифры результата достаточно сравнить Оа 401 со значением А. При этом, если Оа, 01А, то а=1, а на выходе ячейки старшего разряда появляется единица переноса, если же 55 Оа 401 А, то а =О, и единица переноса отсутствует, т.е. при вычислении второй цифры результата наличие или отсутствие переноса йз ячейки старшего разряда второй строки матрицы служит указателем значения а. при р=г а=О, а при р=1, а=1, Для полученйя второго оетатка В , необ" ходимого для вычисления третьей цифры результата, производится вычитание В =А-Оа 01. При а =0 В = А, а при 652 44 2 а =1 В =А, или при а=ОсВ =А+1111, а при а=1 В =А+1011,2В расоматриваемом устройстве припоступлении третьего и ,.четвертогоразрядов подкоренного выражения вмладшие ячейки второй строки матрицына входах Ь ячеек этой же строкиобразуется число А, а на Входаха,в зависимости от значения а , комбинация 1111 или 1011Если а:=1, тоР =1, р =0 и на выходах з. ячееквторой строки матрицы образуется второйостаток, равный В , если .же а =О,то р =О, р =1 и яа выходах зячеек второй строки появится второйостаток, равный величине А.Второй остаток с выхода ячеек вТорой строки матрицы поступает на входы Ьф старших ячеек третьей строки матрицы, а на входы фЬф младшихразрядов ячеек этойже строки поступают следующие два разряда подкоренного выражения.Процесс вычисления последующихцифр результата повторяется аналогично до тех.пор, Пока не будут обработаны все разрядй подкоренного выражения. При .2 п-разрядном подкоренном;выражении матрица состоит из и строк.Общее колиФествб ячеек в матрице определяется выражениемЕ= 2+ Е (+21,1=2где ш - число ячеек в матрице;и в . разрядность результата вычис-,ления.Устройство извлечения квадратногокорня обладает большим быстродействйем, что поэволяет при его использовании в специализированных вычислительных устройствах, работающих вреальном Масштабе времени;,значительно повысить пропускную способностьпоследних.Увеличение быстродействия устройства достигается эа счет того, что впроцессе извлечения квадратного корня количество промежуточйых операцийсведено до мйнимума в каждой строкематрицы обрабатывается одновременнодва разряда подкоренного выражения,причем, при обработке двух разрядов,подкоренного выражения возможнотолько одно переключение управляющимсигналом, который вырабатываетсяячейкой самого старшего разряда (сигнал переноса и инверсный сигнал переноса) этой же строки матрицы, чтопозволяет обеспечивать работу вычислителя беэ внешнего устройства управления. Формула изобретения1. Устройство для извлечения квадратного корня, содержащее матрицу из и строк и в столбцов идентичных вычислительных ячеек, разрядные шинывходного кода,разрядные шины выходного кода, шину логиЧеского нуля и шину логической единицы, о т л и ,ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в нем первые входы вычислительных ячеек двух младших разрядов в каждой строке соединены с соответствую.щими разрядными шинами входного кода, а первые входы остальных ячеек -й (1=1-и) строки каждого столбца соединены с выходами суммы Ъйчислительных ячеек того же столбца (1 " 1) строки, вторые входы вычислительных ячеек старших разрядов и двух младших разрядой".каждой строки соединены с шиной логической единицы, вход переноса всех вычислительных ячеек, кроме ячеек младшего разряда в каждойстроке, соединен с выходом переноса соседней ячейки младшего разряда в той же строке, вход сигнала переноса вычислительных ячеек младших разрядов всех строк сведйией"с - шиной логического нуля, третьи и четвертые входывсех вы 4 ислительйях . ячеек, кроме ячейки старшего разрядау соедийены соответственно с пряьым и инверсным выходом переноса вйчисли- тельной ячейки старшего разряда той -же, стрбки, выходы переноса вычислительных ячеек старшего разряда всех строк матрицй соединень 1 с разрядными 1550 8шинами выходногокода, третий и четвертый входы ячейки старшего разрядапервой строки соединены с прямыми иинверсными выходами переноса той жеячейки, инверсный выход переноса вычислительной ячейки старшего разряда 5 в 3-й строке (3=1,2,3 К) соединен со вторыми входами (3+1) ячейкистрок от (3+1) до К.2, Устройство для извлечения квадратного корня по п, 1, о т л и ч а ю щ е е с я тем, что в нем каждаяячейка содержит одноразрядный сумматор и элемент И-ИЛИ, первый входкоторого соединен с выходом одноразрядного сумматора, второй и третийвходы - с четвертым и третьим входомячейки соответственно, четвертыйвход соединен с первыми входами ячейки и одноразрядного сумматора, а выход - с выходом суммы ячейки, прямойи инверсный выходы одноразрядногосумматора соединены с одноименнымивйходамИ ячейки, а,второй вход и входпереноса одноразрядного сумматора соединены с одноименными входами ячейки.Й Источники инФормации, принятые вовнимание при экспертизе1. Авторское свидетельство СССРМ 435805, кл, С Об Р 7/38, 1974.2. Патент Великобритании Р 1323771ЭО кл. 6 4 А,1973.