Матричное устройство для извлечения квадратного корня Советский патент 1986 года по МПК G06F7/552 

Изобретение относится к вычислительной технике и может быть использовано для однотактного выполнения операции извлечения квадратного корня дробных и целых двоичных чисел в специализированных вычислителях и быстродействующих ЭВМ.

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

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

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

остатков Q| (где k 1, 2N)

по выражению

2-V. Y.n

-(- )

,.,-,к2 + О 11 .

-(к-1)

(1)

при QO О и д О, тогда k-й

Оо

разряд корня равен

1 если Q „ О,

Р

(2)

О

если Q О,

где Q - остаток k-й итерации;

X . - бит i-ro разряда подко- ренного выражения (i 1,2, ..., 2vN); Y . -k - разрядный код, равный

(О у у, , ..., у., )©Vi т.е. операции поразряд- ного ИСКЛЮЧАЩЕЕ ИЛИ (k-l)-ro разряда корня со всеми определенными до этого цифрами.

В предлагаемом устройстве исполь- зовано нескольно иное аналитическое преобразование выражения (1), представляемого в окончательном виде формулой

2 :.Vi V (X,,., х,, 1)-2+ О X

.к

(3)

5

0

0

5

0

5

Q

55

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

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

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

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

Первая, самая старшая цифра корня у , формируется на выходе переноса одноразрядного сумматора 5 1-ой строки. При этом у, равна 1, если любая, из цифр корня X, или Х, равна 1, что обеспечивается присутствием сигнала логической единицы на входе 3 . На выходе суммы одноразрядного сумматора 5 1-ой строки и выходе 1-го элемента НЕ 7 формируется остаток первой итерации Q, , которьй после умножения на коэффициент 2 (что обеспечивается коммутацией строк одноразрядных сумматоров 5), поступает на входы одноразрядных сумматоров второй строки.

Вторая цифра корня у„ формируется на выходе переноса 1-го одноразрядного сумматора 5 второй строки матрицы. При этом, помимо остатка Q (3), в процессе формирования у участвует следующая пара цифр подкоренного выражения х и х, а также код Y равный здесь у - О {где цифра О обеспечивается поступлением сигнала через вход 4). На выходах суммы одноразрядных сумматороа 5 2-ой строки матрицы на выходе 2-го элемента НЕ 7 формируется остаток второй итерации Qj, который после умножения на коэффициент 2 поступает

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

Третья цифра корня у формируется на выходе переноса 1-го одноразрядного сумматора 5 третьей строки матрицы. В процессе формирования у

подкоренн а также код Э у, ). При выполняется

участвуют цифры х.- и х,

6

го выражения, код 2-Q , Y, равньй здесь у (у этом вычисление у, 0 у йа элементе ИСКЛЮЧАНМЦЕЕ ИЛИ 6 3-й строки. На выходах одноразрядных сумматоров 5 третьей строки матрицы формируется остаток 0 третьей итерации.

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

дополнительным кодом. Таким образом на выходах 2 устройство формируется код корня Y.

На фиг. 2 приведены два примера, поясняющих процесс вычисления квад- ратного корня в устройстве. Для операндов, равных /484/1024 и /100/ 1024/, получены корни соответственно /22/32/ и /10/32/. В каждой из итераций осуществляется суммирование двух кодов, в результате чего формируется разряд переноса, отделенный, для наглядности, от остальных точкой, равной очередной цифре корня. Короткими горизонтальными черточками выделены пары цифр подкоренного выражения, анализируемых в данной итерации. Сплошные вертикальные линии указывают на места этих цифр в суммируемых кодах. Пунктирные линии ука- зывают на инвертирование соответствующих разрядов.

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

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

10

t5

20

25

30 35 40 5

0

5

j-я строка (J 3,N) матрицы содержит J-2 элемеятов ИСКЛЮЧАЮЩЕЕ ИЛИ, вход первого слагаемого k-ro одноразряд- ного сумматора (k 1, j - 1) j-й строки матрицы подключен к выходу суммы (k + 1)-го одноразрядного сум матора Cj-1)-й строки матрицы, выход переноса первого одноразрядного сумматора (-1-)-й строки матрицы подключен к входу второго слагаемого пер- . вого одноразрядного сумматора j-й строки матрицы, к первым входам (J-2) элементов ИСКЛЮЧАЮЩЕЕ ИЛИ j-й строки матрицы и к вторым входам J-2 элементов ИСКЛЮЧАЩЕЕ ИЛИ М-й строки матрицы (,N, вход переноса Г-го одноразрядного сумматора i-й строки матрицы (Г 1, 1) подключен к вькоду переноса Cf+l)-ro одноразрядного сумматора той же строки, вход первого слагаемого и вход переноса (i+1)-ro одноразрядного сумматора i-й строки матрицы подключены к (2i-1)-My разряду и к 2i-My разряду информационного входа устройства соответственно, выход первого одноразрядного сумматора i-й строки матрицы подключен к i-му разряду выхода результата устройства, выход р-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ j-й строки матрицы (р 1, j-2) подключен к входу второго слагаемого- (р+1)-го одноразрядного сумматора j-й строки матрицы, вход первого слагаемого i-ro одноразрядного сумматора i-й строки матрицы подключен к выходу элемента НЕ i-й строки матрицы, вход которого подключен к разряду информационного входа устройства (f-i-l), отли- ч ающе е с я тем, что, с целью упрощения устройства, в него введен одноразрядный сумматор первой строки, вход первого слагаемого и вход переноса которого подключены соответственно к первому и второму разрядам информационного входа устройства, а выход суммы - к входу первого слагаемого первого одноразрядного сумматора второй строки матрицы, вход второго слагаемого одноразрядного сумматора дервой строки матрицы подключен к- шине логической единицы .устройства, а выход переноса является первым разрядом выхода результата устройства и подключен к входу второго слагаемого первого одноразрядного сумматора второй строки

512609516

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

9/ 9/ 9/

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

Редактор Т. Парфенова

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

Техред Л.Олейник Корректор А, Тяско

Заказ 5233/50

Тираж 671

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Подписное