Устройство для извлечения квадратного корня
УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее счет } 13 Mb4llOi.;,A чик и накапливающий сумматор, отличающееся тем, что, с целью повышения точности, в него введен блок памяти, адресные входы которого соединены с разрядными выходами счетчика, a информационные выходы - с информационными входами накапливающего сумматора, выход переполнения которого соединен со счетным входом двоичного счетчика и входом установки начального кода накапливающего сумматора, тактируюпа1й вход суммирования которого соединен с входом устройства.
СОЮЗ GOBETCHHX
СОЦИАЛИСТИЧЕСКИХ
РЕСПУВ ЛИК зсю С 06 F 7 552
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
Il0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПЪЙ (21) 2931234/18-24 (22) 28. 05. 80 (46) 23.06.84 Вюл. У 23 (72) Е.И.Филатов (71) Новосибирский электротехнический институт (53) 681.325 (088.8) (56) 1. Авторское свидетельство СССР
N- 641449, кл. С 06 F 7/552, 1976.
2. Авторское свидетельство СССР
Р 4134 79, кл. G 06 F 7/552, t 972 (прототип) . (54) (57) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ
КВАДРАТНОГО КОРНЯ, содержащее счетчик и накапливающий сумматор, о т личающееся тем, что, с целью повышения точности, в него введен блок памяти, адресные входы которого соединены с раэрядными выходами счетчика, а информационные выходы — с информационными входами накапливающего сумматора, выход переполнения которого соединен со счетным входом двоичного счетчика и входом установки начального кода накапливающего сумматора, тактирующий вход суммирования которого соединен с входом устройства.
1099318
Изобретение относится к цифровой вычислительной технике и может быть использовано в вычислительных и информационо-измерительных устрoHcTвах.
Известно устройство для извлечения квадратного корня, работа которого осуществляется за два цикла.
Во время первого цикла на устройство поступает число 1, представленное в число-импульсном коде, и определяет- 10 ся целая часть результата вычислений с недостатком, По окончании поступления числа g устройство переходит ко второму циклу, во время кото" рого по значению остатка аргумента 15 с помощью кусочно-линейной интерполяции определяется приближенное зназначение дробной части результата вычислений f1) .
Недостатками данного устройства 20 является сложность и низкое быстродействие.
Наиболее близким по технической сущности к предлагаемому является устройство, содержащее счетчик, на- 25 капливающий сумматор, генератор . импульсов, схему совпадения и две группы схем считывания, при этом прямые выходы всех разрядов счетчи" ка через первую группу схем считы- 30 вания подсоединены к выходам устройства, а через вторую группу схем считывания †. к информационным входам накапливающего сумматора, выход переполнения которого соединен с общим тактирующим входом схем считывания первой группы, а выход знакового разряда — с первым входом схемы совпадения, второй вход которой соединен с выходом генератора-импуль- 40 сов, а выход — со счетным входом счетчика и общим тактирующим входом схем считывания второй группы, входы установки начального кода накапливающего сумматора подсоединены к входам уст- 45 ройства. Данное, устройство обеспечивает целочисленное извлечение квадратного корня Ф из произвольного числа .п1„ с абсолютной погрешностью, максимальное значение которой равно
" (- Ь .
Недостатком данного устройства является погрешность, составляющая по-. ловину младшего разряда целочислен" ного результата вычислений.
Цель изобретения — повьппение точности устройства.
Указанная цель достигается тем, что в устройство для извлечения квадратного корня, содержащее счетчик и накапливающий сумматор, введен блок памяти, адресные входы которого соединены с разрядными выходами счетчика, а информационные выходыс информационными входами накапливающего сумматора, выход переполнения которого соединен со счетным входом двоичного счетчика и входом установки начального кода накапливающего сумматора, тактирующий вход суммирования которого соединен с входом устройства.
На фиг. 1 представлена структурная схема устройства; на фиг. 2— графики, поясняющие принцип его работы.
Устройство содержит счетчик 1, блок 2 памяти, накапливающий сумматор 3, вход 4. При этом выходы разрядов счетчика 1 подсоединены к адресным входам блока 2 памяти. Информационные выходы блока 2 памяти соединены с информационными входами накапливающего сумматора 3. Тактирующий вход суммирования сумматора 3 соединен с входом 4 устройства. Выход переполнения сумматора 3 соединен со счетным входом счетчика 1 и входом установки начального кода сумматора 3.
В основу алгоритма работы устройства положены следующие соображения.
На фиг. 2 представлены кривая а,. соответствующая истинному значению функции Ф = ", график б, задающий кусочно-линейное .приближение данной функции, и кусочно-ступенчатая ломаная в, описывающая поведение кусочно-линейного приближения при целочцсленйых значениях аргумента.
Как следует из соотношения
{ () =т +2т 1 (1), очередные целочисленные значения аргументов, при которых формируются целочисленные значения функции, различаются на величину 2Ь+1, что при%,„= О, 1, 2, 3, 4... дает ряд нечетных чисел 1,3,5,7,9... . Если при очередных значениях и заклю ) 9 ченных в интервале между значениями которым соответствуют целочисленные зпачения tm, задавать функМ ции hl приращения, равные, l(2m,+1) 1099318 4 о -2 +1=2(2 -1)+1 2 ° 2Р, t МОКС glhogq
) ° следовательно, абсолютная погрешность достигает величины
2 2 iP 2-8 Р то будет формироваться кусочно ступенчатая функция (график Ь на фиг. 2 являющаяся дискретным аналогом кусочно-линейного приближения (график о на фиг. 2) . Так, например, на интервале изменения аргумента от 1 до
4 необходимо значению функции зада- . вать приращения — на интервале от .«г э
4 до 9- и т.д. Для формирования обратных значений нечетных чисел целе- 1О сообразнее использовать блок памяти табличного принципа действия на основе ПЗУ или комбинационных логических устройств с "зашитой" функци ей преобразования. Потребную инфор- 15 мационную емкость блока памяти определяют следующим образом.
Если максимально возможное значение числа tl равно N, т.е. динами20 ческий диапазон аргумента составляет
)log N (= К двоичных разрядов, гдето — ближайшее большее целое число, то число адресных входов блока памяти равно числу разрядов счетчика целой части функции т „ а именно
= p Разрядность выходных
Во< и
2 слоев блока памяти определяется требуемой погрешностью вычисления. Наиболее типична ситуация, при которой приведенную погрешность результата вычислений необходимо иметь равной или близкой к приведенной погрешности задания аргумента. Число значащих разрядов функции принимают при З5 этом равным числу значащих разрядов аргумента. В данном случае это приводит к необходимости иметь дробную часть результата извлечения квадратного корня с числом разрядов, рав- 40 ным 1 0ф 1 1 J — — (= К-р . и
Log é
-(-г) абсолютной погрешностью < 2
Определяют общее число разрядов накапливающего сумматора, обеспечи- 45 вающее данную погрешность определения дробной части. Обозначают его равным Е, чему соответствует абсолютная погрешность задания слагае" мых = 2 . Приращения функции 1п с блока памяти поступают на младшие разряды сумматора. Как известно, при многократном суммировании равноточных чисел абсолютная погрешность возРастает в q раз, где q — . 55 число суммирований. При извлечении квадратного корня по указанному алгоритму
Требуют, чтобы эта погрешность не превышала величины 2 (Р, т.е.
2 " « 2 " р, откуда Р > К +1.
Таким образом, при равенстве числа. разрядов аргумента и функции накапливающий сумматор должен иметь не менее (К+1) разрядов, из которых (К-p) разрядов отводится для дробГ ной части результата вычислений.
Если учесть, что максимально возможное число, подаваемое на накапливающий сумматор, равно 1/g,,которое в двоичном представлении имеет старшую значащую цифру во втором разряде после запятой, то число значащих разрядов выходного слова блока памяти достаточно иметь равным 3 -1=К, т.е. равным разрядности аргумента. Необходимая информационная емкость Х блока памяти составляет при этом 2 K — разрядных слов. Так, например, при
К = 8, P = 4, 3 = 16 8 = 123 бит, а при K= 16,Р=8, J = 256 16
= 4096 бит, что соответственно в
16 или 256 раз меньше, чем при использовании чисто табличных методов вычисления с такой же приведенной погрешностью и не представляет трудностей для практической реализации на современной микроэлектронной элементной базе.
Помимо инструментальной составляющей погрешности, обусловленной ограниченной разрядностью представления результата вычислений, при кусочно-линейной интерполяции имеет место и методическая составляющая погрешности. Для ее оценки уравнение аппроксимирующей кусочно-линейной функции Для каждого < -ro участка интерполяции имеет следующий вид. ъ-в „ п ц „- пц п „- пц.
Откуда при п ; Ф <, имеем
М, °
Методическая погрешность интерполяции, аналитическое выражение для которой имеет вид
1099318
1 ама1= . и- —, т -4n, (3)
2 ъ,;.+1 2щ,„; < имеет отрицательный знак и достигает а на каждом -ом участке интерполяции своего максимального по модулю значения, равного
45! а метмдкс - (2,,) при и (+pi 0 61 г 1О макс (4)
Как показывает анализ, при вычислении функции с приведенной погрешностью равной погрешности за- 15 дания аргумента, уже на интервалах
Я"- 1 1 интерполяции с номерами >
8 гик(а 2И - 1) — максимально аоамокное число участков интерполяции, 20 методическая составляющая погрешности уменьшается настолько, что выходит за пределы разрядной сетки. Так, например, при k = 8 уже на втором участке интерполяции (от Н„ = 4 до 25
11;+ = 9) методическую погрешность можйо не, учитывать, при k = 16 методическая погрешность уходит за пределы разрядной сетки на участках интерполяции, начиная с 32-го и да- gp лее. В любом случае практически
63 на — динамического диапазона воз. 64 можных значений аргумента влиянием методической погрешности можно пре небречь. При равенстве числа значащих разрядов аргумента и функции приведенная погрешность вычислений данного устройства по сравнению с
В K/2 прототипом уменьшается в2 )2
2 — 1 раз . Так, например, при, кд
k =8ипри К = 16вынгрышв точности составляет соответственно
8 и 128 раз.
Устройство для извлечения квадратного корня работает следующим образом.
В исходном положении все разряды счетчика 1 установлены в нулевое, а все разряды накапливающего сумматора 3 - в единичное состояние.
На выходах блока памяти присутствует код, содержащий во всех разрядах единицы. Число, из которого извлекается квадратный корень, подается
55 в число-импульсном коде на вход 4 устройства. При поступлении первого импульса на тактирующий вход суммирования накапливающего сумматора, он переполняется и импульс переполнения передается на счетчик 1. В счетчике устанавливается код коэффициента наклона первого участка интерполяции. Импульс переполнения поступает также на вход установки начального кода сумматора. Начальный код сумматора содержит нулевые значения во всех разрядах, отведенных для дробной части результата вычис . лений и единичные значения во всех остальных разрядах. Начальная предустановка сумматора необходима для обеспечения его переполнения при поступлении последнего на данном интервале приращения функции с одновременным сохранением в заданных пределах максимальной приведенной погрешности вычислений. По мере поступления последующих импульсов входного кода к начальному содержимому сумматора добавляются коды, формируемые блоком 2 памяти на первом участке интерполяции и равные " пока не сформируется второе переполнение. Код счетчика 1 становится равным двум, на выходе блока 2 памяти устанавливается код, равный /g, в сумматоре 3 устанавливается значение начального кода и при поступлении последующих импульсов входной последовательности формируются значения результата вычислений на втором участ ке интерполяции. В дальнейшем работа устройства осуществляется аналогично. Периодическая установка начального кода в накапливающем сумматоре при достижении аргументом значения очередного узла интерполяции исключает накопление инструментальной погрешности. В (М вЂ” P) старших разрядах сумматора формируются достоверные значащие цифры дробной части результата вычислений, а в счетчике формируется код целой части.
Технико-экономический эффект от использования предлагаемого изобретения заключается в roM что благода" ря сочетанию итерационного алгоритма вычисления целой части результата с таблично-алгоритмическим принципом формирования его дробной части существенно повышается точность устройства при сравнительно небольших дополнительных аппаратурных затратах.
1099318
Фий Z
Составитель В.Зеиенков
Редактор И.Касарда Техред A.Ач Корректор А.ТЯско
Заказ 4373/40 Тирам 699 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д, 4/5
Филиал ППП "Патент", r. Умгород, ул. Проектная, 4
