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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

1sI1s G 06 Г 7/552

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

Г10 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4673712/24 (22) 0 .,04,89 (46) 07.02.91. Бюл. М 5 (72) В.Г. Баранов и А.С. Эред;ке1 ов (53) 681.325(088.8) (56) Авторское свидетельство СССР

N 949654, кл. G 06 F 7/552, 1980.

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

М 11-16662, кл. G 06 7/552. 1983. (54) УСТРОЙСт ВО Д1Я ИЗВЛГЧБНИЧ

КВАДРАТНОГО KOPHP (57) Изобретение относится к вычислительНсА технике и может быть использовано для

Изобретение относится к вычислителb÷ой технике, а именно к специалbным вычислительным устройствам функционального преобразования информации.

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

Устройство содержит регистры 1 и 2, элемент 3 задержки, блок 4 управления чтением, блоки памяти (ПЗУ) 5 — 10 группы, блок

4 содержит элементы ИЛИ 11-14. дешифратор 15.

Сущность изобретения основана на исполэовании следующей закономерности:

12

2 "(1+ 1) = 1 +2х1+1 = 4

3 -(2+1) =2 +2х2+1=9

4 (3+1) -3 +2х3+1 16

5 = (4 + 1)2 = 4 + 2 х 4 + 1 =- 25 и т.д, „„5UÄÄ 1626253 А1 вычисления квадратного корня в функциональных преобразованиях информации.

Цель изобретения — повышение быстродействия и дос1оверности вычисления квадратного корня. Цель достигается введением группы ПЗУ и блока управления чтением с

-.оотьетст вуюшчми свяэя 1и. Это позволяет сделать число, из которого извлекается

K÷,l;IðàòHûé корень, непосредственным адр1...=ом П 1У, в котором запрограммирован результат, чт т приводит к повышению быстродействия и экономии оборудования.

2 ил, В общем виде (и+1)-й член данной последоьательности можно представить как (Il+ 1) =

I

= п + 2и + 1, если считать, что результат извлечения квадратного корня из целого числа есть целое число, то V A = В и тогда A=8 .

Если следовать в сторону увеличения числа А, то с определенного значеиич A+ 4 - В ч 1, при этом 4-28+ 1, Таким образом, если задаться погрешностью 1, то для всех чисел от А по А +

2В значение квадратного корня будет

В. ноеA+2В т1 -Вч1.

Увеличение числа А на величину до (2В + 1) не вызывает изменения значения квадратного корня. Учитывая вышесказанное, можно написать следующую последовательность:

„. 5 = V 25

6 - i/25 + 2 х 5+ 1 = v 36

7- т И+2 х 6 +1 =чт49

1626253

8- v 49+ 2 x 7+1 = 64

32 = 1024

И- 71024+2 х32+1

= 1089 и т.д.

В последнем примере, если задаться погрешностью 1, значение квадратного корня 32 будет для всех чисел от 1024 до 1088, т.е. 65 значений.

Любое целое число А > 1 в двоичной системе счисления можно представить в виде

A = a; X 2 + аь! X 2 + аь!Х

X2 2+ ... +a!X2!+аоХ2о, где а1 = 1, а(ь!)...ào- 0,1. Это число находится в промежутке 2 А < 2 . Значение квад1 !+1 ратного корня из этого числа будет

В-bi/2 Х2 +bi/2-! Х2 +...+Ь!Х

Х2 +ЬоХ2, где Ь!П - 1, Ь!/2-! ... bo-0,1 если 1 — четное, и

1+!

В = Ь + !)/2 х 2 2 + ... + b! x2 + Ьох 2о где baal + /2 „. Ьо - 0,1. если l — нечетное.

Если идти в сторону увеличения числа

А, то следующее значение корня будет соответствовать В + 1, при этом число А увеличится на 2В + 1. Умножение на два числа в двоичной системе соответствует сдвигу влево числа на один разряд. Следовательно, если номер старшего разряда числа В был

I/2, то номер старшего разряда числа 2В, будет (— + 1). Таким образом, если ГД - В

I и идти в сторону увеличения числа А, то значение корня В + 1 будет в том случае, 0 I если изменится (— + 1)-й разряд числа А, при этом погрешность может быть « 1. Изменения в разрядах младше указанного не вызывают изменения в значении квадратного корня. Следовательно, при извлечении квадратного корня иэ 1-разрядного числа можно не учитывать младшие разряды с 0-го по 1/2-й, Значащие разряды при этом будут с (— + 1)-ro no I-й. Для уменьшения погреш1

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

1 младшие разряды с 0-го по (— — 1)-й и толь2

55 ко изменения в разрядах, начиная с I/2-го по 1-й влекут изменения в результате квадратного корня.

На фиг. 1 изображена блок-схема устройства для извлечения квадратного корня из всех чисел, ограниченных 20-ю двоичными разрядами. В качестве бЛоков памяти (ПЗУ) использована микросхема с организацией памяти 2К х 8, блок памяти имеет 11 линий адреса с 0-го по 10-й разряды, N - 10 и 8 линий данных, M - 8, имеется также вход

"Разрешение чтения". При отсутствии сигнала на этом входе все 8 линий данных блока памяти находятся в третьем состоянии— состоянии высокого импеданса.

Блок 5 памяти программируется для всех чисел от 0 до 2047. Значение квадратного корня из 2047 соответствует 45. Если идти в сторону увеличения чисел, то следующее значение корня будет 46, при этом подкоренное выражение увеличится по сравнению с предыдущим на 45 х 2 + 1 = 91, что соответствует с двоичной системе

1011011 (шесть разрядов, считая с нулевого). Таким образом, следующий блок памяти программируется не с 6-го разряда входного числа, а с 5-ro разряда и дальше до полного заполнения адресной части ПЗУ, т.е. по

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

25

ПЗУ 8

55 ния разрядности результата извлечения корня (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 будет код 00(h (О) и на выходе 1 дешифратора 15 вырабатывается сигнал "Разрешение чтения" для ПЗУ

5, который активизирует выходы этого ПЗУ

5. Выходы остальных ПЗУ 6...ПЗУ 10 находятся в состоянии высокого импеданса.

Значение квадратного корня, "прошитое" в этом ПЗУ 5, по данному адресу (код числа) с выходов ПЗУ 5 поступает на информационные входы регистра 2. Сигнал "Запуск", задержанный элементом 3 задержки на время выборки ПЗУ, поступает на управляющий вход регистра 2 и двоичный код значения квадратного корня записывается в регистр

2.

Если в двоичном коде числа в разрядах с 11-ro по 15-й имеется хотя бы одна логическая "1", то эта логическая "1" через входной элемент ИЛИ 11 блока управления чтением поступает на первый вход дешифратора 15 и, при отсутствии логических единиц в разрядах с 1 -ro по 19-й, на входах дешифратора формируется код 001.

На выходе 2 дешифратора 15 вырабатывается сигнал "Разрешение чтения" для

ПЗУ 6, который активизирует уже выходы этого ПЗУ 6. Выходы остальных ПЗУ 5, ПЗУ

7 ... ПЗУ 10 находятся в состоянии высокого импеданса, Значение квадратного корня, "прошитое" в ПЗУ 6, по коду адреса с его выходов также поступает на информационные входы регистра 2. Если в двоичном коде числа в разрядах с 16-ro по 18-й присутствует хотя бы одна логическая "1", а в разряде

19 — логический "0", то эта (эти) логическая

"1" через входной элемент ИЛИ 12 блока управления чтением поступает на второй вход дешифратора 15 и на входах дешифратора формируется код 010, если в разрядах с 11-го по 15-й не было логических "1", или

011, если в разрядах с 11-го по 15-й была хотя бы одна логическая "1". При этом либо на выходе 3 дешифратора 15, либо на его выходе 4 вырабатываются сигналы "Разрешение чтения", которые объединяются через выходной элемен ИЛИ 13 и с выхода этого элемента сигнал "Разрешение чтения" активизирует выходы ПЗУ 7 и ПЗУ 8. Использование двух ПЗУ в данном случае обусловлено тем, что разрядность значения квадратного корня иэ 19-разрядного числа может превысить количество линий данных одного ПЗУ (в данном случае количество линий данных одного ПЗУ составляет 8), Поэтому ПЗУ 8 используется для наращивания данных до 10-ти разрядов; с 0-го по 7-й выходы с ПЗУ 7, а 8- и 9-й разряды — выходы

Если в 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- и S-й разряды — с ПЗЧ 10.

Для определения величины максимальной разрядности подкоренного выражения и количества ПЗУ в устройстве для извлечения квадратного корня необходимо задаться количеством линий адреса, выбранного

1626253

ПЗУ. В общем случае, если старший разряд адреса имеет номер N (0,1, ...N), то такое

ПЗУ можно запрограммировать для всех

2 адресов, т.е, для всех чисел от 0 до 2

+1 +1 запрограммировать значения их квадратных корней.

Если разрядность чисел, иэ которых необходимо извлечь квадратный корень, превышает разрядность адресной части ПЗУ, то следующее, второе, ПЗУ программируется, начиная-с N/2 разряда числа и далее по (N/2 + N) разряд, т.е. номер старшего разряда второго ПЗУ будег3N/2 разряда числа, из которого извлекается квадратный корень.

Следующее, третье ПЗУ будет программироваться, начиная с (3N/2):2 = 3N/4 разряда числа и старший разряд адреса будет соответствовать с 3N/4+ N - 7N/4 разряда входного числа.

Следующее, четвертое ПЗУ программируется, начиная с 7N/4:2 - 7N/8 разряда числа, а старший разряд адреса соответствует 7N/8 + N ..- -15М/8 разряда числа, и т.д.

Таким образом, номер старшего разряда первого ПЗУ вЂ” N, второго — 3N/2, третьего — 7N/4, четвертого 15N/8-и т.д, В общем виде номера старших разрядов ПЗУ будут описываться выражением Nx2 -1/2

- Nx(2-1/2 1), где k - 1, 2, 3..., — количество

ПЗУ. Предел этого выражения при k - ao характеризует максимальную разрядность подкоренного выражения, т.е.

lcm N(2-1/2 ) =2N, (1) к -+ 00 следовательно, с помощью ПЗУ можно запрограммировать фунцию квадратного корня для всех чисел, разрядность которых в двоичном коде в два раза превышает разрядность адресной части ПЗУ, Ддя определения количества ПЗУ, для реализации выражения (1) необходимо решить уравнение

N(2 — 1/21 1 -, 2N — 1;

2N — N /2- 1 -2N — 1;

М/2 1;

2 =N;

k-1- logs Й;

k =1+ logs N (2)

Поскольку количество ПЗУ может быть только целым числом, то при вычислении k по выражению (2) результат надо округлить в большую сторону до целого числа, т.е.

k 1+ logz N. (3)

Выражение (3) показывает необходимое количество ПЗУ с адресной частью в (N + 1) разрядов (от 0 до N) для реализации функции квадратного корня с погрешностью « 0,5 для всех возможных для данного

55 случая чисел. Выражение (3) не учитывает тот факт, когда ряэрядность значения квадратного корня может превысить разрядность линий данных ПЗУ. Этот случай зависит от организации памяти ПЗУ.

В примере, описанном выше, выбрано

ПЗУ с органиэацией памяти 2Кх 8. N -10. С помощью такого ПЗУ можно реализовать функцию квадратного корня для всех чисел с разрядностью до 2N = 20, при этом количество ПЗУ будет k «> 1+ logz 10 = 5 без учета расширения линий данных. Повышение быстродействия в предлагаемом устройстве достигается эа счет применения ПЗУ запрограммированных как функция ква атного корня от значения адреса Д - I A l

Таким образом, время вычислений здесь совпадает с временем выборки ПЗУ и для массовых ПЗУ составляет 100„,500 нс.

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

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

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

1626253

10 второго младших разрядов четвертого и ше- стого блоков памяти объединены между собой и подключены к входам двух старших разрядов второго регистра соответственно, выходы разрядов, с одиннадцатого по пятнадцатый первого регистра соединены с входами первого элемента ИЛИ, выходы разрядов с шестнадцатого по восемнадцатый — с входами второго элемента ИЛИ, выходы первого и второго элементов ИЛИ соединены с первым и вторым входами дешифратора соответственно, третий вход которого подключен к выходу девятнадцатого разряда первого регистра, первый и второй выходы дешифратора блока управления чтением соединены с входами разрешения чтения первого и второго блоков памяти

5 соответственно, третий и четвертый выходы — с входами третьего элемента ИЛИ, выход которого подключен к входу разрешения чтения третьего и четвертого блоков памяти, выходы дешифратора с пятого по

10 восьмой соединены с входами четвертого элемента ИЛИ, выход которого подключен к входам разрешения чтения пятого и шестого блоков памяти, 1626253

Составитель А.Баранов

Техред М.Моргентал Корректор В.Гирняк

Редактор Е.Папп

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 279 Тираж 389 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5