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

 

Изобретение относится к вычислительной технике и может быть использовано для однотактного вьптолк - ния операции извлечения квадратного корня дробных и целых чисел в спецпроцессорах . Устройство содержит матрицу одноразрядных сумматоров, элементы ИСКЛЮЧАКИЦЕЕ ШШ, элементы НЕ с соответствующими связями. Цель изобретения - упрощение устройства достигается сокращением аппаратурных затрат. Устройство работает по алгоритму извлечения квадратного корня без восстановления остатка. 2 ил. ю О) со СП

А1

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

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

РЕСПУБЛИН

„.SU„,, 1260951 (5!) 4 G 06 F 7/552

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ (21) 3905061/24-24 (22) 18.04.85 (46) 30.09.86. Вюл. Р 36 (72) С.А.Волощенко (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 773617, кл. G 06 F 7/38, 1978.

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

В 857981, кл. С 06 F 7/552, 1979. (54) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ (57) Изобретение относится к вычислительной технике и может быть использовано для однотактного выполлзния операции извлечения квадратного корня дробных и целых чисел в спецпроцессорах. Устройство содержит матрицу одноразрядных сумматоров, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы

HE с соответствующими связями. Цель изобретения — упрощение устройства достигается сокращением аппаратурных затрат. Устройство работает по алгоритму извлечения квадратного корня без восстановления остатка. 2 ил.

1?60951 (3) Изобретение относится к вычислительной технике и может быть исполь+ О X

RK -(К-1) + О Х х 2 + К- 1 9К

Q = 2 0„1+ ук, - (к-1)

+0112 у. зовано для однотактного выполнения операции извлечения квадратного корня дробных и целых двоичных чисел в специализированных вычислителях и быстродействующих 3ВМ.

Цель изобретения — упрощение устройства на основе сокращения аппаратурных затрат.

На фиг. 1 приведена структурная схема устройства при N=5 на фиг. 2— примеры, поясняющие процесс вычисления квадратного корня в устройстве °

Общим для предлагаемого устройства и прототипа является использование алгоритма извлечения квадратного корня без восстановления остатка. Применительно к дробным двоичным числам вычисление N-разрядного корня У, связанного с подкоренным выражением Х и окончательным остатком

Q формулой Y = Х вЂ” Q, сводится к итерационному определению очередных остатков Я (где k = 1, 2, ..., N) по выражению приЯ =О и Y =О, тогдаk-й разряд корня равен

1 если Я ) О, (2)

О если Q (О, где Q — остаток k-й итерации; х, — бит i-ro разряда подко1 ренного выражения (i

1 2, ..., 2 N)

Y . -k — разрядный код, равный к-j (О у у ° ° у„1)@у

1 т.е. ойерации поразрядного ИСКЛЮЧАЮЩЕЕ ИЛИ (k-1)-го разряда корня со всеми определенными до этого цифрами, В предлагаемом устройстве использовано нескольно иное аналитическое преобразование выражения (1), представляемого в окончательном виде формулой

Q =2, 1 +Y +

К -К-1

+ (Х +Х +1) 2 +

Матричное устройство для извлечения квадратного корня (фиг. 1) содержит разряды 1 .информационного входа, на которые поступает подкоренное выражение Х, выходы 2 разрядов результата устройства, на которых формируется корень У, шину 3 логической единицы, шину 4 логического нуля, одноразрядные сумматоры 5, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 6, элементы НЕ 7.

Номера строк в устройстве (фиг. 1) возрастают сверху вниз, а элементов в строках и номеров разрядных входов — слева направо.

Устройство работает следующим образом.

На входы 1 поступает 2 N-разрядный код подкоренного выражения Х, разряды которого попарно, начиная со старших разрядов, поступают для анализа и вычисления очередных остатков в строки одноразрядных сумматоров 5 матрицы.

Первая. самая старшая цифра корня у, формируется на выходе переноса

1 одноразрядного сумматора 5 1-ой строки. При этом у, равна 1, если любая. из цифр корня Х, или Х равна 1, что обеспечивается присутствием сигнала логической единицы на входе 3. На выходе суммы одноразрядного сумматора 5 1-ой строки и выходе

1-ro элемента НЕ 7 формируется остаток первой итерации Q который после умножения на коэффициент 2 (что обеспечивается коммутацией строк одноразрядных сумматоров 5), поступает на входы одноразрядных сумматоров второй строки. !

BTopsH цифра KopHB g формируется на выходе переноса 1-го одноразрядного сумматора 5 второй строки матрицы. При этом, помимо остатка (3), в процессе формирования у участвует следующая пара цифр подкоренного выражения х и х, а также код У, равный здесь у,- О (где цифра О обеспечивается поступлением сигнала через вход 4). На выходах суммы одноразрядных сумматороа 5

2-ой строки матрицы на выходе 2-го элемента НЕ 7 формируется остаток второй итерации Q, который после умножения на коэффициент 2 поступает

1 26005 1

3 на входы одноразрядных сумматоров 5 третьей строки.

Третья цифра корня у формирует я

"3 на выходе переноса 1-ro одноразрядного сумматора 5 третьей строки мат- 5 рицы. В процессе формирования у участвуют цифры х> и х подкоренноб го выражения, код 2 Q, а также код

Y, равный здесь у (у Я у ). При ! этом вычисление у, 9 у выполняется на элементе ИСКЛЮЧАЮЩЕЕ ИЛИ 6 3-й строки. На выходах одноразрядных сумматоров 5 трет ей строки матрицы формируется остаток 0 третьей ите3 рации. г5

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

На фиг. 2 приведены два примера, поясняющих процесс вычисления квад- 30 ратного корня в устройстве. Для операндов, равных /484/1024 и /100/

1024/, получены корни соответственно

/22/32/ и /10/32/. В каждой из итераций осуществляется суммирование двух кодов, в результате чего формируется разряд переноса, отделенный, . для наглядности, от остальных точкой, равной очередной цифре корня.

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

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

Матричное устройство для извле4 чения квадратного корня, содержащее матрицу из N 1 строк одноразрядных сумматоров, где N-разрядность выходного кода, по д + 1 одноразрядных у сумматоров в i-й строке (i=2,N) матрицы, причем каждая -я строка матрицы содержит элемент НЕ, а каждая

1-я строка (! = З,Й) матрицы содержит

j -2 э.не ментов ИСКЛ10ЧАЮ111ЕЕ ИЛИ, вход гтервого слагаемого k-го одноразрядного сумматора (k =- 1, j — 1) 1-й строки матрицы подключен к выходу суммы (k + 1) — го одноразрядного сумматора (j- 1) — и строки матрицы, выход переноса первого одноразрядного сумг матора (! — 1.)-й строки матрицы подключен к входу второго слагаемого первого одноразрядного сумматора j-й строки матрицы, к первым входам (j 2) элементов ИСКЛЮЧАЮЩЕЕ ИЛИ j-й строки матрицы и к вторым входам

j 2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ M-й строки матрицы (M=j+1,N, вход переноса f-ro одноразрядного сумматора

i-й строки матрицы (г = 1, i) подключен к выходу переноса (г+1) ro одноразрядного сумматора той же строки, вход первого слагаемого и вход переноса (i+1)-rn одноразрядного сумматора i-й строки матрицы подключены к (2i-1)-му разряду и к 2i-му разряду информационного входа устройства соответственно, выход первого одноразрядного сумматора i-й строки матрицы подключен к i-му разряду выхода результата устройства, выход р-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ

j-й строки матрицы (р = 1, j-2) подключен к входу второго слагаемого(р+1)-го одноразрядного сумматора !

-й строки матрицы, вход первого слагаемого i-го одноразрядного сумматора i-й строки матрицы подключен к выходу элемента НЕ i-й строки матрицы, вход которого подключен к

2f.†ìó разряду информационного входа устройства (f =- i — t), о т л ич а ю щ е е с я тем, что, с целью упрощения устройства, в него введен одноразрядный сумматор первой строки, вход первого слагаемого и вход переноса которого подключены соответственно к первому и второму разрядам информационного входа устройства, а выход суммы — к входу первого слагаемого первого одноразрядного сумматора второй строки матрицы, вход второго слагаемого одноразрядного сумматора первой строки матрицы подключен к.шине логической единицы устройства, а выход переноса является первым разрядом выхода результата устройства и подключен к входу второго слагаемого первого одноразрядного сумматора второй строки

1260951 матрицы и к второму входу первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ j-й строки, входы вторых слагаемых i-го и (i + 1)-го одноразрядных сумматоров

Фи а.1. 000t t 00100 Операнды

0100

oft

1-я итерация

Я-я urnepaöèÿ.1-я илерация

1,0010

0t 01

0 t01

Ф-я итерация

3- Ф итерация

101001

0 tDt00t

0t0t

010 t

Результат

f 010

Фиг. 2

° t0tt0

Составитель Д .Хан-Магомедов

Техред Л.Олейник Корректор A. Тяско Редактор

Т. Парфенова

Заказ 5233/5С

Тираж 671

Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная. 4!.1

1. 00000

oooo

i-й строки матрицы подключены к шинам логического нуля и логической единицы устройства соответственно.

gtg

10t

000 0