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

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

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

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

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

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

Блок 5 коррекции (фиг. 3) содержит элемент 14.1-l4.M-2 ИЖ, элемент ИПИ-НЕ 15, элемент И 16 н триггер 17.

Блок 4 поразрядного дополнения (фиг. 4) содержит первую 18 и вторую 19 группь элементов НЕ, первый 20 и второй 21 двоичные сумматоры, первую 22 и вторую 23 группы элементов И и нгину 24 двоично-десятичного числа 10 устройства.

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

Двухканальный коммутатор 8 (фиг. 6) содержит девять элементов НЕ 46-54, восемь элементов И 55-62, две группы элементов 10 И-ИЛИ63и64

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

Подкоренное выражение положительно (), представлено в двоично- десятичной системе счисления и содержит М разрядов без учета знакового. В одном такте определяется одна двоично-десятичная цифра М-разрядного квадратного КОРНЯ, получение которой производится по с:;едующему алгоритму

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

Р-ИЧНЫ : цифр квадратного корня на

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

Одновременно определяются девять разностей вида В1 У1-ВО; В2 У2-ВО... В(Р-1)У(Р-1)-ВО, где (ВО) - очередной сдвинутый отрицательный остаток предьщущего такта, плюс приращение

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

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

Выбирается реальный отрицательный

остаток данного такта по знакам полученных разностей В1, В25 ..., В9 и определяется очередная двоично-десятичная цифра квадратного корня.

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

В следующих тактах операции рассмотренного алгоритма повторяются, но количество разрядов в углах с каждым тактом увеличивается. Приведем диаграмму, описывающую получение углов и процесс извлечения квадратного корня. Пусть значение квадратного корня ,658, тогда fflxffl -N 0,432964 - точное значение подкоренного выражения. Округлим это значение до трех цифр ,433.

На дщаграмме вверху изображено образование углов от полученных в предыдущих тактах цифр квадратного корня, причем показаны только углы, суммфование которых с отрицательным

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

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

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

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

Вес О -1 -2

О, 6 5 О, 6 5 О

3 6 3

3 угол

.

N N

О, 4

О, 4

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

1 такт

О О О

1 угол

2 такт

9 О 9 О О

О О 9 8 1

2 угол

23А8314

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

5

В следующих тактах дополнительньй

код получается автоматически.

О

25

О

4 8

4 О

6 4 4 О 4 8

2964 3

2 1

5 6 О О

- прирацение N

3

в

1

6

2

6 9 - приращение и сдвиг /1/ ол. едашща

3 О

2

3 О

3 такт

9 О 9 О

О О

8 8

3 угол

9 О

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

8 8

О О

приращение N и сдвиг

О

6

О

ШЗ-8

0

0

5 5

5

0

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

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

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

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

1. Устройство дпя извлечения квадратного корня,содержащее первый и второй регистры, регистр подкоренного выражения и регистр корня, отличающееся тем, что, с

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

, информационным входам всех блоков суммирования и р Первому и второму информационным входам двухканального коммутатора, выход пифратора подключен к входу первой тетрады регистра корня, выход j-й гдe(, ..., М-1) тетрады регистра корня подключен к входу j-ro дешифратора группы, выходы j-ro дешифратора груп пы подключены к j-му информационному входу блока формирования кратных, k-й выход (где , ..., 9) блока

10

15

25

20

30

35

40

45

50

55

формирования кратных подключен к третьему информационному входу k-ro блока суммирования, (k+8)-fi выход блока формирования кратных подключен к четвертому информационному входу k-ro блока суммирования, третий информационный вход первого блока суммирования подключен к шине логического нуля устройства, старшие (М-1) тетрады четвертого информационного входа первого блока суммирования подключены к выходам старших (М-1)-тетрад регистра корня, младшая тетрада четвертого информационного входа первого б.пока суммирования подключена к шине двоично-десятичного числа 1 устройства, выход переноса (где 1 1,...,9) блока сум- мирования подключен к входу шифратора и к t-му управляющему входу двухканального коммутатора, первый выход t-ro блока суммирования подключен к ((+2)-му информационному входу двухканального коммутатора, второй выход f-ro блока суммирования подключен к (+11)-му информационному входу двухканального коммутатора, выход первого регистра подключен к пятым информационным входам всех блоков суммирования и к двадцать первому информационному входу двухканального коммутатрра, выход второго регистра подключен к шестым информационным входам всех блоков суммирования и к двадцать второму информационному входу двухканального коммутатора, выход корректирующей единицы блока коррекции подключен к седьмым информационным входам всех блоков суммирования и к двадцать третьему информационному входу двухканального коммутатора, первый выход двухканального коммутатора подключен к информационному входу первого регистра, а второй выход - к информацинному входу второго регистра, причем блок поразрядного дополнения содержит первую и вторую группы элементов НЕ, первый и второй двоичные сумматоры, первую и вторую группы элементов И, причем вьгходы элементов НЕ первой группы подключены к первой группе входов первого двоичного сумматора, выходы элементов НЕ второй группы подключены к первой группе входов второго. двоичного сумматора, вторые группы входов первого и второго двоичных сумматоров подключены к шине двоичнодесятичного числа 10 устройства, выходы первого двоичного сумматора под ключ1ны к первым входам элементов И первой группы, выходы второго двоич- ного сумматора подключен к первым входам элементов И второй группы, входы первой группы элементов НЕ являются первым информационным входом блока поразрядного дополнения, входы второй группы элементов НЕ являются вторым информационным входом блока порязрадного дополнения, вторые входы элементов И первой и второй групп соединены между собой и являются входом блокировки блока поразрядного дополнения, выходы первой и второй гру.ш элементов И являются соответственно первым и вторым выходами блока поразрядного дополнения, блок кор- рекции содержит группу из (М-2) элементов ИЛИ, элемент ИЛИ-НЕ, элемент и триггер, причем выход (1-2)-го элемента ИЩ группы подключен к (1-2)-м входу элемента ИЛИ-НЕ, выход злемен- та ИЛИ-НЕ подключен к первому входу элемента И и к входу установки триггера, входы (i-2)-ro элемента ИЛИ группы являются (-2)-м информационным входом блока коррекции, инверс- ный выход триггера подключен к второму входу элемента И и является выходом блокирующего сигнала блока коррекции, выход элемента И является выходом корректирующей единицы блока коррек1щи.

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

J j 0 5 о

5

С 0 5

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

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

„элементов/И шифратора, выход первого элемента И шифратора подключен к первому входу первого элемента ТИ пшфратора, выход второго элемента И шифратора подключен к первому входу второго элемента ИЛИ шифратора, выход третьего элемента И пшфратора подключен к вторым входам первого и второго элементов ИЛИ шифратора, выход четвертого элемента И шифратора подключен к первому входу третьего элемента ИЛИ шифратора.

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

4. Устройство по п.1, отличающееся тем, что двухканаль- ньй коммутатор содержит девять эле- ментов НЕ, восемь элементов И и две группы по (4.М-8) элементов 10 И-ИЛИ причем выходы первого, второго, ..., восьмого элементов НЕ двухкакального коммутатора подключены к первым вхо- дам соответственно первого, второго, ..., восьмого элементов И двухка- нального коммутатора, первые входы всех элементов 10 И-ИЛИ обеих групп объединены между собой и соединены с входом первого элемента НЕ двухка- нального коммутатора, выход р-го (где , ..., 8) элемента И двухканально- го коммутатора подключен к (р+1)-м входам всех элементов 10 И-ШШ обеих групп, десятые входы всех элементов 10 И-ИЛИ обеих групп подключены к выходу девятого элемента НЕ двухканаль- ного коммутатора, t-й вход г-го (где , ..., (4.М-8) элемента 10 И-ИПИ первой группы является г-м двоичным разрядом (1+2)-го информационного

входа двухканально о коммутатора, 1 -й вход г-го элемента 10 И-ИЛИ второй группы является г-м двоичным разрядом (t+11)-ro информационного входа двухканального коммутатора, двадцатый вход d-ro (где , ..., (4.V-16) элемента 10 первой группы является d-м двоичным разрядом двадцать первого информационног входа двухканального коммутатора, двадцатые входы (4.М-15)-го, (4.М- -14)-го, ..., (4.М-9)-го элементов 10 И-ИЛИ первой группы подключены к шине логического нуля устройства, двадцатый вход (4.М-8)-го элемента 10 И-ИЛИ первой группы является двадцать третьим информационным входом двухканального коммутатора, двадцатый вход d-ro элемента 10 И-ИЛ второй группы является d-м двоичным разрядом двадцать второго информационного входа двухканального коммутатора, двадцатые входы (4.М-15)-го, (4.М-14)-го (4-М-13)-го и (4.М-12)-г элементов 10 И-ИЛИ второй группы являются соответственно первым, вторым, третьим и четвертым двоичными разрядами первого информационного входа двзгхканального коммутатора, двадцатые входы (4.М-11)-го, (4.М- -10)-го, (4.)-го и (4.М-8)-го элементов 10 И-ИЛИ являются соответственно первым., вторым, третьим и четвертым двоичными разрядами второго информационного входа двухканального коммутатора, вход k-ro элемента НЕ двухканального коммутатора соединен с вторым входом (k-l)-ro элемента И двухканального коммутатора и является k-M управляющим входом двухканального коммутатора, вход первого элемента НЕ двухканального коммутатора является первым управляюпщм входом двухканального коммутатора, выход г-го элемента 10 И-ИЛИ первой группы является г-м двоичным разря- ДО.М первого выхода двухканального коммутатора, выход г-го элемента 10 И-ИЛИ второй группы является г-м двоичным разрядом второго выхода двухка;нального коммутатора.

I I LW

W.w-2 11 -..,, I. I

. V

. «Ыд to

i(as

«a

on

to (U

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

.Редактор E. Копча

Составитель С. Силаев Текред М.Ходанич i

Заказ 2986/51 Тираж 671 , Подписное ВНИИПИ Государственного комитета СССР

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

- -..-.-- -- - -„-„.-. - -„иш .

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

Корректор Г. Решетник