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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 2625 11 0 06 Г 7/552 ИСАНИЕ БРЕТЕН АВТОРСКОМУ ТЕЛЬСТВУ ЕЧЕНИЯ сл итс.л ьвано для л,бщем виде (п тельности мо и +2 п+1, влечения кв т го и исла есть цеогда А = В . Если следов ния числа А, точеиич ч АчдТаким образом, стью 5 1, то дл 2 В значение кв до В, ноАе 29 е У (2 В + квадр ное, вател Сущностьэовании с122 "(1+ 1)3 -(2+ 1)4 (3+ 1)5 =(4+1)+1=42+1=93+1 ". 164 + 1 =- 25 и т.д ГОСУДАРСТВЕ ННЫИ КОМИТЕТГ 10 ИЗОБРЕТЕНИЯМ И ОТКРЬПИЯМПРИ ГКНТ СССР(54) УСТРОЙСт ВО ДЛЯ ИЗВЛКВАДРАТНОГО КОРНР(57) Изобретение относится к вычной технике и может быть использ Иэо 5 ретение относится к вычислительной технике, а именно к специальным вычислительным устройствам функционального преобразования информации.Цель изобретения - повышение быстродействия и достоверности вычислений,На фиг, 1 представлена структурная схема устройства; на фиг, 2 - формат числ", из которого производятся вычисления корня и распределение эон в этом формате для адресов каждого блока памяти.Устройство содержит регистры 1 и 2, элемент 3 задержки, блок 4 управления чтением, блоки памяти (ПЗУ) 5 - 10 группы, блок 4 содержит элементы ИЛИ 11-14, дешифра"5 зобретения основана на и едующей закономерности: вычисления квадратного корня е функциональных преобразованиях информации. Цель изобретения - повышение быстродействия и дос 1 оеерности вычисления квадратного корня, Цель достигается введением группы ПЗУ и блока управления чтением с -,оотьетствуюшчми свяэю 1 и. Это позволяет сделать число, из которого извлекается квадратный корень, непосредственным адр:ом ПЭУ, в котором запрограммирован результат, чтч приводит к повышению быстродействия и экономии оборудования.2+1)-й член данной послед но представить как (и + 1) сли считать, что результ дратного корня из цело ое число, то /А = В ать в сторону увеличе с определенного зна В+1, при этомдВ+1 если задаться погрешно я всех чисел от А по А + а атного корня будет величение числа А на величину до 1) не вызывает изменения значения атного корня. Учитывая вышесказанможно написать следующую последоьн ость;= ъ/089 и т,д,В последнем примере, если задаться погрешностью1, значение квадратного корня 32 будет для всех чисел от 1024 до 1088,т.е, 65 значений.Любое целое число А1 в двоичнойсистеме счисления можно представить в видеА = а; Х 2+ аь Х 2" + а 1-1 ХХ 2 а 1 Х 2+аоХ 2,где а = 1, а(ь 1)ао" 0,1, Это число находитсяв промежутке 2А ( 2, Значение квадн 1ратного корня из этого числ/а 61 удетВ Ь/2 Х 2 + Ь/2-1 Х 2 ++ Ь 1 ХХ 2 +Ьо Х 2,где ЬП" 1, ЬИ- , Ьо,1 если - четное,и+В = Ь/ + 1)/2 Х 2 ++ Ь 1 Х 2+ ЬоХ 2 о, где Ь(+ /2. Ьо -0,1, если - нечетное. Если идти в сторону увеличения числа А, то следующее значение корня будет соответствовать В + 1, при этом число А увеличится на 2 В + 1. Умножение на два числа в двоичной системе соответствует сдвигу влево числа на один разряд. Следовательно, если номер старшего разряда числа В был 1/2, то номер старшего разряда числа 2 В, будет ( - + 1). Таким образом, если 1 ГА - В1и идти в сторону увеличения числа А, то значение корня В + 1 будет в том случае, О 1если изменится ( - + 1)-й разряд числа А, при этом погрешность может быть1. Изменения в разрядах младше указанного не вызывают изменения в значении квадратного корня. Следовательно, при извлечении квадратного корня иэ 1-разрядного числа можно не учитывать младшие разряды с 0-го по 1/2-й, Значащие разряды при этом будут с ( - + 1)-го по 1-й, Для Уменьшения погреш 12ности в два раза необходимо сократить в два раза не учитываемую часть числа, т.е. сдвинуты на один разряд вправо границу значащей части, числа при извлечении квадратного корня. Если извлекать квадратный корень из,1-разрядного двоичного числа с погрешностью0,5, можно не учитывать1младшие разряды с О-го по( -- 1)-й и толь 2 5 10 15 20 25 30 35 40 45 50 55 ко изменения в разрядах, начиная с 1/2-го по 1-й влекут изменения в результате квадратного корня.На фиг. 1 изображена блок-схема устройства для извлечения квадратного корня из всех чисел, ограниченных 20-ю двоичными разрядами. В качестве бЛоков памяти (ПЗУ) использована микросхема с организацией памяти 2 К х 8, Блок памяти имеет 11 линий адреса с 0-го по 10-й разряды, й - 10 и 8 линий данных, М - 8, имеется также вход "Разрешение чтения", При отсутствии сигнала на этом входе все 8 линий данных блока памяти находятся в третьем состоянии - состоянии высокого импеданса.Блок 5 памяти программируется для всех чисел от 0 до 2047. Значение квадратного корня из 2047 соответствует 45. Если идти в сторону увеличения чисел, то следующее значение корня будет 46, при этом подкоренное выражение увеличится по сравнению с предыдущим на 45 х 2 + 1 = 91, что соответствует с двоичной системе 1011011 (шесть разрядов, считая с нулевого). Таким образом, следующий блок памяти программируется не с 6-го разряда входного числа, а с 5-го разряда и дальше до полного заполнения адресной части ПЗУ, т,е. по 15-й разряд. Программирование с 5-го разряда, а не с 6-го позволяет получить погрешность результата не более 0,5, ПЗУ 6 охватывает все числа от 2048 до 65535. Значение квадратного корня из 65535 соответствует 256 = 2 . Следующее значение корня 257, при этом подкоренное значение увеличится на 256 х 2+ 1 = 513, т.е. изменение при этом произойдет в 9-м разряде. Следовательно, для получения погрешности не более 0,5 следующее ПЗУ 7 надо программировать не с 9-го разряда, а с 8-го разряда входного числа, и далее до полного заполнения адреса ПЗУ, т,е, по 18-й разряд числа от 65536 по 324287,Корень квадратный иэ 324287 равен 724, Следующее значение 725 будет, если подкоренное значение увеличится на 724 х х 2 + 1 = 1449, т,е. изменение должно произойти в 10-м разряде, а для погрешности не более 0,5 следующее ПЗУ,9 программируется с 9-го разряда входного числа и далее по 19-й разряд.Выбранные ПЗУ имеют 8 линий данных. Поскольку в примере входное число может иметь все 20 разрядов значащих, т.е. логические "1", то с некоторого значения результат извлечения квадратного корня может превысить 8 разрядов. Для этого в устройство введены еще два ПЗУ, ПЗУ 8 по адресной части подключено аналогично ПЗУ 7, а две линии данных предназначены для расшире 1626253ния разрядности результата извлечения корня (8-й и 9-й разряды). ПЗУ 10 работает совместно с ПЗУ 9, а две линии данных используются также для расширения разрядности результата.Устройство работает следующим образом.Двоичный код числа, иэ которого надо извлечь квадратный корень, поступает на информационные входы регистра 1. По сигналу "Запуск", который поступает на управляющий вход регистра 1, этот код записывается в регистр и поступает на адресную часть ПЗУ 5 ПЗУ 10 и блок 4 управления чтенИем. Причем разряды с 0-го по 10-й поступают на ПЗУ 5, разряды с 5-го по 15-й - на ПЗУ 6, разряды с 8-го по 18-й - на ПЗУ 7 и 8 и разряды с 9-го по 19-й - на ПЗУ 9 и 10,Блок 4 управления чтением содержит входные элементы ИЛИ 11 и 12, дешифратор 15 и выходные элементы ИЛИ 14 и 13, Разряды с 11-го по 15-й с выхода регистра 1 через входной элемент ИЛИ 11 блока 4 управления чтением поступают на первый свод дешифратора 15. Разряды с 16-го по 18-й через входной элемент ИЛИ 12 блока 4 управления чтением поступают на второй вход дешифратора 15, а 19-й разряд - на третий вход дешифратора 15. Если в двоичном коде числа отсутствуют логические единицы в разрядах с 11-го по 19-й (фиг. 2), то на входах дешифратора 15 будет код ОООг (0) и на выходе 1 дешифратора 15 вырабатывается сигнал "Разрешение чтения" для ПЗУ 5, который активизирует выходы этого ПЗУ 5, Выходы остальных ПЗУ 6 ПЗУ 10 находятся в состоянии высокого импеданса. Значение квадратного корня, "прошитое" в этом ПЗУ 5, по данному адресу (код числа) с выходов ПЗУ 5 поступает на информационные входы регистра 2. Сигнал "Запуск", задержанный элементом 3 задержки на время выборки ПЗУ, поступает на управляющий вход регистра 2 и двоичный код значения квадратного корня записывается в регистр 2,Если в двоичном коде числа в разрядах с 11-го по 15-й имеется хотя бы одна логическая "1", то эта логическая "1" через входной элемент ИЛИ 11 блока управления чтением поступает на первый вход дешифратора 15 и, при отсутствии логических единиц в разрядах с 16-го по 19-й, на входах дешифратора формируется код 001.На выходе 2 дешифратора 15 вырабатывается сигнал "Разрешение чтения" для ПЗУ 6, который активизирует уже выходы этого ПЗУ 6, Выходы остальных ПЗУ 5, ПЗУ 7ПЗУ 10 находятся в состоянии высокого10 импеданса, Значение квадратного корня, "прошитое" в ПЗУ 6, по коду адреса с его выходов также поступает на информационные входы регистра 2. Если в двоичном коде числа в разрядах с 16-го по 18-й присутствует хотя бы одна логическая "1", а в разряде 19 - логический "0", то эта (эти) логическая "1" через входной элемент ИЛИ 12 блока управления чтением поступает на второйвход дешифратора 15 и на входах дешифратора формируется код 010, если в разрядах с 11-го по 15-й не было логических "1", или 011, если в разрядах с 11-го по 15-й была хотя бы одна логическая "1". При этом либо на выходе 3 дешифратора 15, либо на его выходе 4 вырабатываются сигналы "Разрешение чтения", которые объединяются через выходной элемен 1 ИЛИ 13 и с выхода этого элемента сигнал "Разрешение чтения" активизирует выходы ПЗУ 7 и ПЗУ 8. Использование двух ПЗУ в данном случае обусловлено тем, что разрядность значения квадратного корня иэ 19-разрядного числа может превысить количество линий данных 15 20 25 одного ПЗУ(в данном случае количество линий данных одного ПЗУ составляет 8), Поэтому ПЗУ 8 используется для наращивания данных до 10-ти разрядов; с 0-го по 7-й выходы с ПЗУ 7, а 8- и 9-й разряды - выходы ПЗУ 8 30 35 40 4550 55 Если в 19-м разряде кода числа логическая "1", то на входе дешифратора 15 блока 4 управления чтением устанавливается код 100, если в разрядах с 11-го по 18-й нет ни одной логической "1". При этом на выходе 5 дешифратора 15 вырабатывается сигнал "Разрешение чтения", Если в 19-м разряде кода числа логическая "1" и в разрядах с 11-го по 18-й тоже могут быть логические 1, то на входах дешифратора может быть код 101, сигнал "Разрешение чтения" при этом вырабатывается на 6-м выходе дешифратора 15, код 110 - на 7-м выходе и код 111 - на 8-м выходе дешифратора 15. Эти выходы 5-8 дешифратора 15 объединены выходным элементом ИЛИ 14 блока 4 управления чтением и с выхода элемента ИЛИ 14 сигнал "Разрешение чтения" активизирует выходы ПЗУ 9 и 10. Остальные ПЗУ 5ПЗУ 8 находятся в состоянии высокого импеданса. ПЗУ 10, в данном случае, используется аналогично ПЗУ 8 в предыдущем случае для расширения разрядности значения квадратного корня до 10-ти, Выходы с ПЗУ 9 - это разряды с 0-го по 7-й; 8- и 9-й разряды - с ПЗЧ 10.Для определения величины максимальной разрядности подкоренного выражения и количества ПЗУ в устройстве для извлечения квадратного корня необходимо задаться количеством линий адреса, выбранногоПЗУ. В общем случае, если старший разряд адреса имеет номер й (0,1, М), то такое ПУ можно запрограммировать для всех 2 адресов, т.е, для всехчисел от Одо 2+1 +1 запрограммировать значения их квадратных корней.Если разрядность чисел, иэ которых необходимо извлечь квадратный корень, превышает разрядность адресной части ПЗУ, то следующее, второе, ПЗУ программируется, начиная с й/2 разряда числа и далее по (й/2 + й) разряд, т.е. номер старшего разряда второго ПЗУ будегЗМ/2 разряда числа, из которого извлекается квадратный корень.Следующее, третье ПЗУ будет программироваться, начиная с (Зй/2):2 = Зй/4 разряда числа и старший разряд адреса будет соответствовать с Зй/4 + М - 7 М/4 разряда входного числа.Следующее, четвертое ПЗУ программируется, начиная с 7 й/4:2 - 7 М/8 разряда числа, а старший разряд адреса соответствует 7 М/8+ М .- 15 М/8 разряда числа, и т.д.Таким образом, номер старшего разряда первого ПЗУ - й, второго - Зй/2, третьего - 7 й/4, четвертого 15 М/8 и т.д, В общем виде номера старших разрядов ПЗУ брут описываться выражением йх 2 -1/2 - йх(2-1/2 ), где М, 2, 3,. - количество ПЗУ. Предел этого выражения при М -ф со характеризует максимальную разрядность подкоренного выражения, т.е.11 гп М (2 -1/2 ) =2 М. (1)к-+оследовательно, с помощью ПЗУ можно запрограммировать фунцию квадратного корня для всех чисел, разрядность которых в двоичном коде в два раза превышает разрядность адресной части ПЗУ,Для определения количества ПЗУ, для реализации выражения (1) необходимо решить уравнениейР/2" -, 2 М;2 М - й /2 "2 М - 1;М/2 1;2 =М;1-1" 1 о 9 г М;1 =1+ 1 ояг М (2)Поскольку количество ПЗУ может быть только целым числом, то при вычислении М по выражению (2) результат надо округлить в большую сторону до целого числа, т.е,М 1+ 1 оцг М. Р)Выражение (3) показывает необходимое количество ПЗУ с адресной частью в (й + 1) разрядов (от 0 до й) для реализации функции квадратного корня с погрешностью 0,5 для всех возможных для данного 5 10 15 20 25 30 35 40 45 50 55 случая чисел. Выражение (3) не учитывает тот факт, когда ряэрядность значения квадратного корня может превысить разрядность линий данных ПЗУ, Этот случай зависит от организации памяти ПЗУ,В примере, описанном выше, выбрано ПЗУ с органиэацией памяти 2 К х 8. й - 10. С помощью такого ПЗУ можно реализовать функцию квадратного корня для всех чисел с разрядностью до 2 М = 20, при этом количество ПЗУ будет К1+1 одг 10 = 5 без учета расширения линий данных. Повышение быстродействия в предлагаемом устройстве достигается эа счет применения ПЗУ запрограммированных как функция ква атного корня от значения адреса Д -АТаким образом, время вычислений здесь совпадает с временем выборки ПЗУ и для массовых ПЗУ составляет 100,500 нс.Повышение достоверности обусловлено тем, что в схеме устройства отсутствуют всякого рода счетчики, триггеры и другие элементы, требующие специальных мероприятий по помехозащищенности. Число, из которого извлекается квадратный корень, является непосредственным адресом ПЗУ, в котором запрограммирован результат. Формула изобретения Устройство для извлечения квадратного корня, содержащее первый и второй регистры, управляющий вход последнего из которых подключен к выходу элемента задержки, отл и чаю щеес я тем,что, с целью повышения быстродействия и достоверности вычислений, в него введена группа из шести блоков памяти и блок управления чтением, содержащий дешифратор и четыре элемента Иг 1 И, причем вход запуска устройства подключен к входу элемента задержки и управляющему входу первого регистра, информационный вход которого соединен с информационным входом устройства, а выходы разрядов с нулевого по десятый - с соответствующими адресными входами первого блока памяти, выходы разрядов с пятого по пятнадцатый первого регистра соединены с адресными входами второго блока памяти, выходы разрядов с восьмого по восемнадцатый - с соответствующими адресными входами третьего и четвертого блоков памяти, а выходы разрядов с девятого по девятнадцатый - с соответствующими адресными входами пятого и шестого блоков памяти, разрядные выходы первого, второго, третьего и пятого блоков памяти обьединены между собой и подключены к соответствующим разрядным входам второго регистра, выходы первого ивторого младших разрядов четвертого и ше. стого блоков памяти объединены между собой и подключены к входам двух старших разрядов второго регистра соответственно, выходы разрядов, с одиннадцатого по пятнадцатый первого регистра соединены с входами первого элемента ИЛИ, выходы разрядов с шестнадцатого по восемнадцатый - с входами второго элемента ИЛИ, выходы первого и второго элементов ИЛИ соединены с первым и вторым входами дешифратора соответственно, третий вход которого подключен к выходу девятнадцатого разряда первого регистра, первый и второй выходы дешифратора блока управления чтением соединены с входами разрешения чтения первого и второго блоков памяти 5 соответственно, третий и четвертый выходы - с входами третьего элемента ИЛИ, выход которого подключен к входу разрешения чтения третьего и четвертого блоков памяти, выходы дешифратора с пятого по 10 восьмой соединены с входами четвертогоэлемента ИЛИ, выход которого подключен к входам разрешения чтения пятого и шестого блоков памяти,1626253 едакт ектор няк Заказ 279 Тираж 389 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., 4/5 Производственн ельский комбинат "П