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

 

Изобретение относится к области вычислительной техники. Цель изобретения - увеличение быстродействия. Устройство работает в системе счисления с натуральным основанием . Цикл извлечения квадратного корня состоит из М тактов. В каждом такте определяется одна Р-ичная цифра корня . Для ее определения одновременно вычисляется Р-1 разностей предыдущего остатка и приращения подкоренного выражения с каждым из углов, получаемых для используемой системы счисления. По знакам вычисленных разностей определяется очередная 1Ц1фра квадратного корня и очередной остаток . 3 э.п. ф-лы, 6 ил.

А1

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

COlLHAЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (11) (5I) 4 G 06 F 7/552

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

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

Е с

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

К АВТОРСКОМУ(СВИДЕТЕЛЬСТВУ (21) 378 1951/24-24 (22) 16.08.84 (46) 30.05.86. Бкл. № 20 (72) А.Ю. Глазачев (53) о81.325(088.8) (56) Карцев М.А. Арифметика цифровых машин. М.: Наука, 1969, с. 537, рис. 5-6.

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

¹ 560224, кл . G 06 F 7/552, 1973. (54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ (57) Изобретение относится к области вычислительной техники. Цель изобретения — увеличение быстродействия.

Устройство работает в системе счисления с натуральным основанием Р>2.

Цикл извлечения квадратного корня состоит из M тактов. В каждом такте определяется одна Р-ичная цифра корня. Для ее определения одновременно вычисляется P-1 разностей предыдущего остатка и приращения подкоренного выражения с каждым из "углов", получаемых для используемой системы счисления. По знакам вычисленных разностей определяется очередная цифра квадратного корня и очередной остаток. 3 s.ï. ф-лы, 6 ил.

1234831

Изобретение относится к вычислительной технике и предназначено для извлечения квадратного корня из чисел, представленных в двоично †десятичной системе.

Цель изобретения — увеличение быстродействия.

На фиг. 1 изображена структурная схема устройства для извлечения квадратного корня; на фиг. 2 — схема блока суммирования; на фиг. 3 — схема блока коррекции; на фиг. 4 . — схема блока поразрядного дополнения; на фиг. 5 — схема шифратора; на фиг.6 схема двухканального коммутатора.

Устройство (фиг. I) содержит регистр 1 корня, регистр 2 подкоренно— го выражения, M-1 дешифраторов 3.1, 3.2, ..., 3, M-1, блок 4 поразрядного дополнения, блок 5 коррекции, блок 6 формирования кратных, девять блоков 7.1-7.9 суммирования, двухканальный коммутатор 8, шифратор 9, первый 10 и второй 11 регистры.

Блок 7 суммирования (фиг. 2) содержит М одноразрядных двоично-десятичных сумматоров 12.1. . ., 12.i узел 13 формирования опережающего переноса, шину 14 логического нуля устройства.

Блок 5 коррекции (фиг 3) содержит элемент 14.1-14.M-2 ИЛИ, элемент ИЛИ-HE 15, элемент И 16 и триггер 17.

Блок 4 поразрядного дополнения (фиг. 4) содержит первую 18 и вторую

19 группы элементов НЕ, первый 20 и второй 21 двоичные сумматоры, первую 22 и вторую 23 группы элементов И и шину 24 двоично-десятичного числа 10 устройства.

Шифратор 9 (фиг. 5) содержит элементы НЕ 25-33, элементы И 34-4l, элементы ИЛИ 42-45.

Двухканальный коммутатор 8 (фиг. 6) содержит девять элементов

НЕ 46-54, восемь элементов И 55-62, две группы элементов 10 И-ИЛИ 63 и 64

Рассмотрим работу устройства.

Подкоренное выражение положительно (ОьИ 1), представлено в двоичнодесятичной системе счисления и содержит M разрядов без учета знакового.

В одном такте определяется одна двоично-десятичная цифра М-разрядного квадратного корня, получение которой производится по с;;едующему алгоритму.

Одновременно вычисляются девять положительных углов", где каждый

"угол" представляет собой удвоенное произведение всех ранее полученных

Р— ичных цифр квадратного корня на соответствующую данному "углу" цифрумножитель из ряда i, 2, ..., 9 с учетом весов плюс произведение цифрымножителя на саму себя, с учетом веса.

1О Одновременно определяются девять разностей вида В1 У1-ВО; В2=У2-ВО...

В(P- 1)=У(Р-1) -ВО, где (ВО) — очередной сдвинутый отрицательный остаток предыдущего такта, плюс приращение

15 М, У1, У2, ..., У(Р-1) — соответствующие положительные углы".

Определяются знаки полученный разностей В1, В2, ..., В9.

Рыбирается реальный отрицательный щ остаток данного такта по знакам полученных разностей Bi, В2, ..., В9 и определяется очередная двоично-деся— тичная цифра квадратного корня °

Осуществляется смещение полученно25 го реального отрицательного остатка на два разряда влево, запись в два младших разряда приращения подкоренного выражения.

В следующих тактах операции pacgp смотренного алгоритма повторяются, но количество разрядов в "углах" с каждым тактом увеличивается. Приведем диаграмму, описывающую получение "углов" и процесс извлечения квадратного корня. Пусть значение квадратного корня Ш=0,658, тогда

ШхШ=-N =-0,432964 — точное значение подкоренного выражения. Округлим это значение до трех цифр N=0,433.

Па диаграмме вверху изображено обра— зование углов от полученных в пре— дыдущих тактах цифр квадратного корня, причем показаны только "углы", суммирование которых с отрицательным остатком предыдущего такта дает ре— альпый отрицательный остаток данного такта. Внизу диаграммы изображен процесс извлечения квадратного корня, Первый тактом подкоренное выражение N записывается в регистр 2 (фиг ° 1).„ одновременно с этим регистр 1 обнуляется, регистр 10 и триггер I7 блока 5 обнуляется, а в каждый двоично-десятичный разряд регистра 11 записываются цифры девять.

Два старших значащих разряда подкоренного выражения подаются на входы блока 4, в котором образуется их

О, 6 5 8

О, 6 5 8

1 "угол"

3 6

2 "угол"

3 О

2 5

3 О

3 "угол"

4 8

4 О

6 4

4 О

4 8

О, 4 3 2 9 6 4

О, 4 3 3

Номера разрядов М

6 5 4 3 2

1 такт

9 5 6 — нри0 О 0 ращение N

9 9 9

0 О О

3 6

9. 8 2

1 "угол"

9 9 9

О О О 0

2 такт

9 9 8

2 6 9 — приращение и сдвиг

О, /1/

Дол. единица

О О 1

2 "угол"

Э 0

2 5

3 О

3 12348 дополнение до старшей цифры используемой системы счисления, т.е. до

9-ти. Полученные дополнения с выходов блока 4 подаются на входы. двух младших разрядов блоков суммирования. На аналогичные входы остальных разрядов блоков суммирования с

Вес О -1 -2 -3

31 .1 выходов регистров 10 и 11 подаются соответственно цифры О и 9 для получения дополнительного кода отрицательного приращения N.

В следующих тактах дополнительный код получается автоматически.

1234831

9 9 9 8 8 5

0 0 0 0 1

Ш2=5

3 такт

9 8 8 5 0 0 — приращение N u

0 0 1 0 сдвиг

3 угол

4 8

4 0 б 4

4 0

9 8 7 9 6 4

0 1 2 0 0

В каждом такте к сдвинутому на два двоично-десятичных разряда влево очередному остатку в два младших разряда записывается значение дополнения приращения N, значит в такте

30 при подаче младшего разряда N в младший разряд нужно подавать дополнительную единицу, причем в тот разряд, который является младшим разрядом, если все остальные разряды справа равны нулю. Дополнительную единицу вырабатывает блок 5 коррекции (фиг.3).

В регистре 2 с каждым тактом подкоренное выражение сдвигается на два двоично-десятичных разряда влево, справа в регистр 2 записываются нули.4О

На входы блока 5 подаются все разряды 2, кроме старших. В том такте, в котором на входах блока коррекции будут все нули, на его выходе появляется корректирующая единица, которая подается в младшие разряды блоков суммирования. Триггер 17 (фиг. 3) включается в единицу, которая подается на вход блокировки блока 4 (фиг. 4), чем блокируются его выходы. После первого такта в регистре 1 записаны все нули, поэтому на выходах дешифраторов 3 группы сигналов нет. В первом такте в блоках ?.1, 7.2, ..., 7 ° 9 в соответствии с диаг- 5 раммой происходит суммирование положительных значений "углов" первого такта 01, 04, ..., 81 со значениями двух старших разрядов подкоренного выражения, представленных как дополнения. Полученные суммы в виде двух двоично-десятичных чисел поразрядных сумм и переносов с. выходов блоков

7.1-7.9 подаются на соответствующие входы двухканального коммутатора 8.

На выходах переноса блоков суммирования образуются значения опережающих переносов, которые подаются на входы,цешифратора 9 и на входы управления двухканального коммутатора 8, где по ним определяются очередная цифра корня и реальный остаток дан— ного такта. Вторым тактом в регистр 1 записывается значение цифры корня с выходом шифратора 9. В регистры 10 и 11 записывается значение реального остатка данного такта, подкоренное выражение в регистре 2 сдвигается влево на два двоично-десятичных разряда..Значение первой цифры корня подается из первого разряда регистра 1 на входы дешифратора 3.1 группы, и на его выходе, соответствующем цифре, появляется сигнал, который поступает по соответствующей шине на соответствующий вход блока б формирования кратных.

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

Полученные "углы" суммируются нл

1234831 одноразрядных двоично-десятичных сумматорах, соответствующих данным цифрам блоков суммирования со сдвинутым на два разряда влево предыдущим 5 остатком и приращением подкоренного выражения. По полученным остаткам на выходах блоков суммирования образуются опережающие переносы и остатки в виде двух чисел. По значениям 10 опережающих переносов определяется вторая цифра корня на шифраторе 9 и реальный остаток второго такта на выходах коммутатора 8. В следующих тактах все действия повторяются по аналогии с первым и вторым тактами до получения всех цифр квадратного ,корня.

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

1. Устройство для извлечения квадратного корня, содержащее первый и второй регистры, регистр подкоренного выражения и регистр корня, о т л и ч а ю щ е е с я тем, что, с ,целью увеличения быстродействия, устройство содержит группу из (М-1) дешифраторов, где M — разрядность аргумента, блок формирования кратных, девять блоков суммирования, шифратор, двухканальный коммутатор, блок поразрядного .дополнения и блок коррекции, причем выходы первой и второй тетрады подкоренного выражения подключены соответственно к первому и второму информационным входам блока поразрядного дополнения, выход i-й (где i=3, М) тетрады регистра подкоренного выражения подключен к (i-2)-му информационному входу блока коррек40 ции, выход блокирующего сигнала блока коррекции подключен к входу блокировки .блока поразрядного дополнения, первый и второй выходы блока поразрядного дополнения подключены

45 соответственно к первому и второму ,информационным входам всех блоков суммирования и к йервому и второму информационным входам двухканального коммутатора, выход шифратора под50 ключен к входу первой тетрады регистра корня, выход j-й где(1=1, М-1) тетрады регистра корня подключен к входу j-го дешифратора группы, выходы j-го дешифратора груп-55 пы подключены к j -му информационному входу блока формирования кратных, k-й выход (где k=2, ..., 9) блока формирования кратных подключен к третьему информационному входу k-ro блока суммирования, (k+8) é выход блока формирования кратных подключен к четвертому информационному входу k-ro блока суммирования, третий информационный вход первого блока суммирования подключен к шине логического нуля устройства, старшие (М-1) тетрады четвертого информационного входа первого блока суммирования подключены к выходам старших (М-1)-тетрад регистра корня, младшая тетрада четвертого информационного входа первого блока суммирования подключена к шине двоично-десятичного числа "1" устройства, выход переноса (— го (где 1=1,...,9) блока суммирования подключен к -му входу шифратора и к f. — ìó управляющему входу двухканального коммутатора, пер вый выход f-ro блока суммирования подключен к ((+2)-му информационному входу двухканального коммутатора, I второй выход (-го блока суммирования подключен к ()+11)-му информационному входу двухканального коммутатора, выход первого регистра подключен к пятым информационным входам всех блоков суммирования и к двадцать первому информационному входу двухканального коммутатрра, выход второго регистра подключен к шестым информационным входам всех блоков суммирования и к двадцать второму информационному входу двухканального коммутатора, выход корректирующей единицы блока коррекции подключен к седьмым информационным входам всех блоков суммирования и к двадцать третьему информационному входу двухканального коммутатора, первый выход двухканального коммутатора подключен к информационному входу первого регистра, а второй выход - к информацинному входу второго регистра, причем блок поразрядного дополнения содержит первую и вторую группы элементов НЕ, первый и второй двоичные сумматоры, первую и вторую группы элементов И, причем выходы элементов НЕ первой группы подключены к первой группе входов первого двоичного сумматора, выходы элементов HE второй группы подключены к первой группе входов второго. двоичного сумматора, вторые группы входов первого и второго двоичных сумматоров подключены к шине двоично t234831

)О десятичного числа 10 устройства, выходы первого двоичного сумматора подключены к первым входам элементов И первой группы, выходы второго двоичного сумматора подключен к первым входам элементов И второй группы, входы первой группы элементов НЕ являются первым информационным входом блока поразрядного дополнения, входы второй группы элементов НЕ являются вторым информационным входом блока порязрадного дополнения, вторые входы элементов И первой и второй групп соединены между собой и являются входом блокировки блока поразрядного дополнения, выходы первой и второй гру сп элементов И являются соответственно первым и вторым выходами блока поразрядного дополнения, блок кор- 2б рекции содержит группу из (М-2) элементов ИЛИ, элемент ИЛИ-НЕ, элемент И и триггер, причем выход (i-2)-го элемента ИЛИ группы подключен к (i-2)-му входу элемента ИЛИ-НЕ, выход элемента ИЛИ-НЕ подключен к первому входу элемента И и к входу установки триггера, входы (i-2)-ro элемента ИЛИ группы являются (i-2)-м информационным входом блока коррекции, инверсный выход триггера подключен к второму входу элемента И и является выходом блокирующего сигнала блока коррекции, выход элемента И является выходом корректирующей единицы бло-! ка коррекции.

2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок суммирования содержит N одноразрядных двоично-десятичных сумматоров и узел формирования опережающего переноса, причем выходы переносов одноразрядных двоично-десятичных сумматоров подключены к соответствующим разрядам первого входа узла формирования 45 опережающего переноса и являются первым выходом блока суммирования, выходы суммы одноразрядных двоичнодесятичных сумматоров подключены к соответствующим разрядам второго вхо- 50 да узла формирования опережающего переноса и являются вторым выходом блока суммирования, выход узла опережающего переноса является выходом переноса блока суммирования, первый 55 вход первого одноразрядного двоично-десятичного сумматора является седьмым информационным входом блока суммирования, второй вход первого одноразрядного двоично-десятичного сумматора является первым информационным входом блока суммирования, третий вход первого одноразрядного двоично-десятичного сумматора является первой тетрадой четвертого информационного входа блока суммирования, четвертый, пятый и шестой входы первого и первый и второй входы второго одноразряднах двоичнодесятичных сумматоров подключены к шине логического нуля устройства, третий вход второго одноразрядного двоично-десятичного сумматора явля-. ется вторым информационным входом блока суммирования, четвертый вход второго одноразрядного двоично-десятичного сумматора является первой тетрадой третьего информационного входа блока суммирования, пятый и шестой входы г-го (z=2, ..., М) одноразрядного двоично-десятичного сумматера являются z-й тетрадой четвертого информационного входа блока суммирования, третий и четвертый входы i-го одноразрядного двоично-десятичного сумматора являются (i-i)-й тетрадой третьего входа блока суммирования, первый информационный вход i-гб одноразрядного двоична" десятичного сумматора является (i-2)-й тетрадой пятого информационного входа блока суммирования, второй вход i-ro одноразрядного двоична-десятичного сумматора является (i-1)-й тетрадой шестого информационного входа блока суммирования.

3. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что шифратор содержит девять элементов НЕ, восемь элементов И и четыре элемента ИЛИ, причем выходы первого, второго, восьмого элементов НЕ шифратора подключены к первым входам соответственно первого, второго, ..., восьмого элементов И шифратора, выход первогф элемента И шифратора подключен к первому входу первого элемента ИЛИ шифратора, выход второго элемента И шифратора подключен к первому входу второго элемента ИЛИ шифратора, выход третьего элемента И шифратора подключен к вторым входам первого и второго элементов ИЛИ шифратора, выход четвертого элемента И шифратора подключен к первому входу третьего элемента ИЛИ шифратора, 1234831

12 выход пятого элемента И шифратора подключен к третьему входу первого ик второму входу третьего элементов ИЛИ шифратора, выход шестого элемента И шифратора подключен к треЪьим входам второго и третьего элементов ИЛИ шифратора, выход седьмого элемента И шифратора подключен к четвертым входам первого, второго и третьего эле- 1О ментов ИЛИ шифратора, выход восьмого элемента И шифратора подклю..ен к первому входу четвертого элемента ИЛИ шифратора, выход девятого элемента НЕ шифратора подключен к пятому входу 15 первого и к второму входу четвертого элементов ИЛИ шифратора, вход первого элемента НЕ шифратора является первым входом шифратора, вход k-го элемента НЕ шифратора соединен с, 20 вторым входом (k-1)-ro элемента И шифратора и является k- ì входом шифратора, выходы первого, второго, третьего и четвертого элементов ИЛИ шифратора являются выходом шифра- 25 тора.

4. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что двухканальный коммутатор содержит девять эле- З0 ментов НЕ, восемь элементов И и две группы по (4.M-8) элементов 10 И-ИЛИ, причем выходы первого, второго, восьмого элементов НЕ двухканального коммутатора подключены к первым вхо- 5 дам соответственно первого, второго, восьмого элементов И двухканального коммутатора, первые входы всех элементов 10 И-ИЛИ обеих групп объединены между собой и соединены с 40 входом первого элемента НЕ двухканального коммутатора, выход р-го (где р=1, ..., 8) элемента И двухканального коммутатора подключен к (р+1)-м входам всех элементов !О И-ИЛИ обеих групп, десятые входы всех элементов

10 И-ИЛИ обеих групп подключены к выходу девятого элемента НЕ двухканального коммутатора, 1,-й вход r-ro (где

r=1, ..., (4.M-8) элемента 1О И-ИЛИ первой группы является г-м двоичным разрядом (1+2)-ro информационного входа двухканальног о коммутатора, f-й вход r ãî элемента 10 И-ИЛИ второй группы является r-м двоичным разрядом (1 +11)-ro информационного входа двухканального коммутатора, двадцатый вход d-го (где d=1, (4.V — 16) элемента 10 И вЂ И первой группы является d ì двоичным разрядом двадцать первого информационного входа двухканального коммутатора, двадцатые входы (4.M-15)-ro, (4.M-14)-ro, ..., (4.M-9)-го элементов

10 И-ИЛИ первой группы подключены к шине логического нуля устройства, двадцатый вход (4.M-8)-го элемента 10 И-ИЛИ первой группы является двадцать третьим информационным входом двухканального коммутатора, двадцатый вход d-го элемента 10 И-ИЛИ второй группы является d-и двоичным разрядом двадцать второго информационногс входа двухканального коммутатора, двадцатые входы (4.М-15)-го, (4.M-14)-го (4-M-13)-го и (4.M-12)-ro элементов 10 И-ИЛИ второй группы являются соответственно первым, вторым, третьим И четвертым двоичными разрядами первого информационного входа двухканального коммутатора, двадцатые входы (4.М-11)-го, (4.M-10)-го, (4.M9)-ro и (4.M — 8)-го элементов 10 И-ИЛИ являются соответственно первым, вторым, третьим и четвертым двоичными разрядами второго информационного входа двухканального коммутатора, вход k-го элемента

HE двухканального коммутатора соединен с вторым входом (k-1)-ro элемента И двухканального коммутатора и является k-м управляющим входом двухканального коммутатора, вход первого элемента НЕ двухканального коммутатора является первым управляющим входом двухканального коммутатора, выход r-ro элемента 10 И-ИЛИ первой группы является r-м двоичным разрядом первого выхода двухканального коммутатора, выход r-ro элемента

10 И-ИЛИ второй группы является r-м двоичным разрядом второго выхода двухканального коммутатора.

1234831

2 234831

1=34831

Составитель С. Силаев

Текред М.Ходанич

Корректор Г. Решетник. Редактор Е. Копча

Заказ 2986/51

Тираж б71 Подписное

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

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

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