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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ. КВАДРАТНОГО КОРНЯ, содержащее первый , второй и третий регистры, схе My сравнения, сумматор, блок управления , содержащий генератор импульсов и первьй элемент И, первый.вход которого соединен с выходом генератора импульсов, информационные выходы первого регистра соединены с первой группой входов схемы сравнения , вторая группа входов которой соединена с выходами сумматора и с информационными входами второго регистра, входы первого слагаемого сумматора соединены с выходами треть его регистра, отличающеес я тем, что, с целью повышения быстродействия устройства, в него введены счетчик, группа элементов И, четвертьй и пятый регистры, а в блок управления - первый и второй распределители импульсов, второй и третий элементы И, три элемента ИЛИ, элемент НЕ, триггер, выход которого соединен с вторым входом первого элемента И, выход которого соединен с входом первого распределителя импульсов, выход схемы сравнения соединен с первыми входами элементов И группы, первым входом второго элемента И и входом элемента НЕ, выход которого соединен с первым вxoдo третьего элемента И, выход которого соединен с первым входом первого элемента ИЛИ, с входом разрешения вычитания счетчика и входом синхронизации второго регистра , информационные выходы кото (Л рого соединены с входами второго слагаемого сумматора, второй вход первого элемента ИЛИ соединен с выходом второго элемента ИЛИ и входом сложения счетчика, первый вход вто (Рого элемента Ш1И соединен с выходом второго элемента И, вход синхронизации устройства соединен с входом 4 синхронизации первого регистра и S1 первым входом третьего элемента ИЛИ, выход которого соединен с входом О триггера, первый выход первого Pficч пределителя импульсов соединен с тактовым входом счетчика и входом сдвига на три разряда в сторону мпадг ших разрядов четвертого регистра, второй выход первого распределителя импульсов соединен с вторым входом второго элемента ИЛИ, выход которого соединен с входом разрешения сложения счетчика, вход управления счетом которого соединен с выходом первого элемента ИЛИ, третий выход первого распределителя импульсов

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

СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК

„„SU „„1141407

4(5() 5 06 F 7/552

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВ К

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 364986 1/24-24 (22) 06. 10.83 (46) 23.02.85. Бюл, У 7 (72) В.П.Данчеев и Г.И.Кашалов (71) Московский ордена Ленина и ордена Октябрьской Революции энергетический институт (53) 681.325(088.8) (56) 1. Байков В.P., Селютин С.А.

Вычисление элементарных функций в

ЭКВМ. M., "Радио", 1982, рис. 44, с. 49.

2. Оранский А.N. Аппаратные методы в цифровой вычислительной технике. Минск, БГУ, 1977, рис. 5-11, с. 121 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

КВАДРАТНОГО КОРНЯ, содержащее первый, второй и третий регистры, схеМу сравнения, сумматор, блок управления, содержащий генератор импульсов и первый элемент И, первый. вход которого соединен с выходом генератора импульсов, информационные выходы первого регистра соединены с первой группой входов схемы сравнения, вторая группа входов которой соединена с выходами сумматора и с информационными входами второго регистра, входы первого слагаемого сумматора соединены с выходами треть его регистра, о т л и ч а ю щ е е « с я тем, что, с целью повышения быстродействия устройства, в него введены счетчик, группа элементов

И, четвертый и пятый регистры, а в блок управления — первый и второй распределители импульсов, второй и третий элементы И, три элемента

ИЛИ, элемент НЕ, триггер, выход ко- торого соединен с вторым входом первого элемента И, выход которого соединен с входом первого распределителя импульсов, выход схемы сравнения соединен с первыми входами элементов И группы, первым входом второго элемента И и входом элемента НЕ, выход которого соединеч с первым входом третьего элемента И, выход которого соединен с первым входом первого элемента ИЛИ, с входом разрешения вычитания счетчика и входом синхронизации второго регистра, информационные выходы которого соединены с входами второго слагаемого сумматора, второй вход первого элемента ИЛИ соединен с выходом второго элемента ИЛИ и входом сложения счетчика, первый вход вто рого элемента ИЛИ соединен с выходом второго элемента И, вход синхронизации устройства соединен с входом синхронизации первого регистра и первым входом третьего элемента ИЛИ, выход которого соединен с входом триггера, первый выход первого распределителя импульсов соединен с тактовым входом счетчика и входом сдвига на три разряда в сторону млад-. ших разрядов четвертого регистра, второй выход первого распредеяителя импульсов соединен с вторым входом второго элемента ИЛИ, выход которого соединен с входом разрешения сложения счетчика, вход управления счетом которого соединен с выходом первого элемента ИЛИ, третий выход первого распределителя импульсов

1141407 соединен с входом сдвига на один разряд в сторону старших разрядов четвертого регистра, тактовым входом пятого регистра и входом второго распределителя импульсов, четвертый выход первого распределителя импульсов соединен с вторыми входами второго и третьего элементов И, пятый выход первого распределителя импульсов соединен с тактовым входом третьего регистра, разрядные выходы которого соединены со сдвигом на один разряд в сторону младших с первой группой разрядных входов счетчика, вторая и третья группы разрядных входов счетчика соединены соответственно с прямь|ми и инверсными разрядными выходами четвертого

Изобретение относится к автомати. ке и вычислительной технике и может быть использовано при построении специализированных вычислительных устройств, функциональных преобразователей информации и как специализированный процессор больших ЦВМ.

Известно устройство для вычисления квадратного корня, содержащее три сумматора, счетчик, схему срав- 10 нения, блок вентилей сдвига и три регистра E1), Недостатком устройства является невысокое быстродействие.

Наиболее близким по технической 15 сущности к предлагаемому является устройство для вычисления квадратного корня, содержащее первый, второй и третий регистры, схему срав нения, первый и второй накапливающие сумматоры, блок управления, блок памяти, при этом информационные выходы первого регистра соединены с первой группой входов схемы сравнения, выход которой соединен с 25 первым входом блока управления, с второй группой входов схемы сравнения соединены выходы первого сумматора, которые также соединены с информационными входами второго регистра, входы первого сумматора соединены с информационными выходами третьего регистра, информационрегистра, разрядные выходы счетчика соединены соответственно с информа-, ционными входами третьего регистра, выходы второго распределителя импульсов с первого по k-й (% — разрядность результата) соединены соответственно с вторыми входами элементов И группы, выходы которых соединены соответственно с информационными входами пятого регистра, .в од кода аргумента устройства соединен со сдвигом íà 2 разрядов в сторону старших (e — число разрядов дробной части результата) с информационными входами первого регистра, Ъ-й выход второго распределителя импульсов соединен с вторым входом третьего элемента ИЛИ. ные входы которого соединены с выходаМи второго сумматора, которые также еоединены с информационными входами первого регистра, входы второго сумматора подключены к информационным выходам второго регистра, информационные входы регистра второго накапливающего сумматора соединены с входом кода аргумента, а также с выходами первого сумматора, первый выход блока памяти подключен к второму входу блока управления, а второй выход блока памяти — к информационным входам второго регистра, вход блока памяти соединен с первым выходом блока управления, второй выход которого соединен с входом синхронизации второго регистра, к тактирующему входу второго сумматора подключен третий выход блока управления, четвертый выход которого соединен с входом синхронизации третьего регистра, пятый выход блока управления подключен к тактирующему входу первого суммато ра, к третьему входу схемы сравнения подключен шестой выход блока управления, седьмой выход которого соединен с входом синхронизации первого регистра (2j.

Недостатком известного устройства является сравнительно невысокое быстродействие.

1141

30 е

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

Поставленная цель достигается тем, что в устройство для вычисления квадратного корня, содержащее первый» второй и третий регистры,,схему сравнения, сумматор, блок управления, содержащий генератор импульсов и первый элемент И, первый вход которого соединен с выходом генератора импульсов, информационные выходы первого регистра †.с первой группой входов схемы сравнения, вторая группа входов которой соединена с выходами сумматора и с информационными входами второго регистра, входы первого слагаемого сумматора— с выходами третьего регистра, введены счетчик, группа элементов И, четвертый и пятый регистры, а в блок управления — первый и второй распределители импульсов, второй и третий элементы И, три элемента ИЛИ, элемент НЕ» триггер, выход которого соединен с вторым входом первого элемента И, выход которого соединен с входом первого распределителя импульсов, выход схемы сравнения — с первыми входами элементов И группы, первым входом второго элемента И и входом элемента НЕ, выход которого соединен с первым входом третьего элемента И, выход которого соединен с первым входом первого элемента

ИЛИ, с входом разрешения вычитания счетчика и входом синхронизации 35 второго регистра, информационные выходы которого соединены с входами второго слагаемого сумматора, второй вход первого элемента ИЛИ вЂ” с выходом второго элемента ИЛИ и вхо- 40 дом сложения счетчика, первый вход второго элемента ИЛИ вЂ” с выходом второго элемента И, вход синхронизации устройства — с входом синхронизации первого регистра и первым вхо- дом третьего элемента ИЛИ, выход которого соединен с входом триггера, первый выход первого распределителя импульсов — с тактовым входом счетчика и входом сдвига на три раз- о ряда в сторону младших разрядов четвертого регистра, второй выход первого распределителя импульсов— с вторым входом второго элемента ; выход которого соединен с входом 55 разрешения сложения счетчика, вход управления которого. соединен с выходом первого элемента ИЛИ, третий

407 выход первого распределителя импульсов — с входом сдвига на один разряд в сторону старших разрядов четвертого регистра, тактовым входом пятого регистра и входом второго распределителя импульсов, четвертый выход первого распределителя импульсов — с вторыми входами второго и третьего элементов И, пятый выход первого распределителя импульсов с тактовым входом третьего регист ра» разрядные выходы которого соеди» нены со сдвигом на один разряд в сторону младших с первой группой разряд-, ных входов счетчика, вторая и третья группы разрядных входов счетчика— соответственно с прямыми и инверсными разрядными выходами четвертого регистра, разрядные выходы счетчика — соответственно с информационными входами третьего регистра, выходы второго распределителя импульсов с первого по 4-й (k — разрядность результата) — соответственно с вто-рыми входами элементов И группы, выходы которых соединены соответственно с информационными входами пятого регистра, вход кода аргумента устройства — со сдвигом íà 2m разрядов в сторону старших (m — число разрядов дробной части результата) с информационными входами первого регистра, 1 — и выход второго распределителя импульсов — с вторым входом третьего элемента ИЛИ.

На фиг. 1 представлена структурная схема предлагаемого устройства, на фиг. 2 — функциональная схема блока управления; на фиг. 3 — два разряда счетчика 6; на фиг. 4 — фрагмент двоичного представления функции 7 = VX, Устройство (фиг. 1) содержит регистр 1, схему 2 сравнения, сумматор 3, регистры 4 и 5, счетчик 6, регистр 7 сдвига, блок 8 управления, группу элементов И 9, регистр 10, вход 11 синхросигнала и вход 12 кода аргумента.

Функциональная схема блока 8 управления содержит генератор 13 тактовых импульсов, элементы ИЛИ 14-16, триггер 17, элемент НЕ 18, элементы

И 19-21, распределители 22 и 23 импульсов.

Функциональная схема двух разрядов счетчика 6 содержит триггеры

1141407

24 и 25, элементы 2И-ИЛИ 26 и 27, элементы И-НЕ 28-33.

Принцип работы устройства базируется на следующих положениях.

1 ° В двоичном представлении функции У = ГХ % -разрядным числом разность S; = L>(j + 1) — 1 „.(j)

= С = const

1 У где rn 7< 1 — число дробных разрядов

L;(j) — j-й интервал постоянства 1-го разряда, равный длине j --го участка изменения аргумента, на котором 1 — и разряд принимает только единичное или только нулевое значение.

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

<;, (2 i l = i-; l i )j 2 S; / 8;

Co l (1! . „(21-1-5;/4;

4. „(г>+1) =,,,(г;1 s,./+, Со1 где L;(j), Ь (j) — соответственно нулевой и единичный интервалы постоянства

1-ro разряда, на которых 1-й разряд принимает (Ol голько нулевое (на L,(j) или только единичное (на Ь (3) значение.

C 1 ° Определение того, какому интервалу постоянства Аункции — единичному или нулевому в каждом разряде двоичного представления Аункции Y

Ф, полученном при дискретности изменения аргумента ЬХ „ = 2

-Я6Ъ принадлежит значение аргумента Х, „ =

= Х 2 2", дает возможность сАормировать значения всех разрядов функции

Y. Данное определение реализуется при помощи сравнения Х,„ с текущим значением суммы интервалов постоянства Аункции У = ЧХ

3тек

5цМ„,„=.> причем результат на выходе схемы 2 сравнения

11, если SUM 4 Хм „, 1О !О, если SUN > Х„, В схеме устройства, представленной на Аиг. 1, сравнение SUM c

no+

Х„,„ выполняется в схеме 2 сравнения, вычисление текущего значения

15 SUM„,„ осуществляется в сумматоре 3, вычисление интервалов постоянства— в счетчике 6, формирование и хранение разности S. интервалов постоянст1 ва реализуется в регистре 7 сдвига, 20 результат Y = 1 Х формируется в регистре 10.

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

В исходном состоянии в регистре

5 и счетчике 6 записан код первого интервала постоянства старшего разряда двоичного представления Аункции Y = 7Х L, (1) = 2 + в ре30 гистре 7 записан код разности S1, =

= L „, (2) — L 1, (1) = 2 -" остальные все регистры и триггер обнулены.

По синхросигналу с входа 11 код аргумента Х с входа 12 записывается

И в регистр 1. Так.как запись происходит со сдвигом за счет жесткой связи на 2m разрядов в сторону старших, то в регистре оказывается код

Х, = Х.2 . Синхросигнал с входа

40 11 поступает также на второй вход блока 8 управления, в котором синхросигнал проходит элемент ИЛИ 14 и переключает в "1" триггер 17. Сигнал логической "1" с прямого выхода триггера 17 открывает элемент И 19, и тактовые импульсы с генератора 13 тактовых импульсов начинают поступать на вход распределителя 22 импульсов, который коммутирует их на пять направлений. Первый тактовый импульс с распределителя 22 импульсов поступает на первый выход блока

8 управления и далее на вход разрешения приема инАормации счетчика 6 и на вход управления сдвигом регистра 7, при этом в счетчике 6 осуществляется прием инАормации с ре-. гистра 5 со сдвигом за счет жесткой

11414

7 связи на один разряд в сторону младших, а в регистре 7 вЂ,сдвиг его содержимого на. три разряда в сторону младших. Второй тактовый импульс с второго выхода распределителя 22 импульсов поступает на второй вход элемента ИЛИ 15, выход которого яв07 8 ней i-й элемент И. Сигнал с выхода

i-го элемента И группы элементов И ". записывается в 1-й разряд регистра 10 результата вычисления Аункции

Y = VX на вход синхронизации которого поступает тактовый импульс с третьего выхода блока 8 управления °

25 импульсами, в сумматоре 3 вычисляет- З0 ся текущее значение суммы интервалов постоянства, для этого код текущего интервала постоянства из регистра 5 складывается с предыдущим значением ЯУИ„ „, находящимся в регист" ре 4. Полученное значение БУМ

35 сравнивается в схеме 2 сравнения с (КОДОМ X p* °

45 на вход распределителя 23 импульсов, 50

55 ляется вторым выходом блока 8 управления, кроме того, сигнал с выхода элемента ИЛИ 15 поступает на второй вход элемента ИЛИ 16 и с его выхода на шестой выход блока 8 управления.

С второго выхода блока 8 управления тактовый импульс поступает на вход разрешения сложения счетчика 6. Одновременно с шестого выхода блока

8 управл ния сигнал логической "1" поступает на вход управления счетом счетчика 6, на первую группу разрядных входов которого подан код с прямых выходов разрядов регистра 7 содержащий одну "1", а на третью группу разрядных входов счетчика 6 подан код с инверсных выходов разрядов регистра 7. В счетчике 6 реализуется сложение его содержимого с кодом регистра 7. Одновременно с выполнением операций, синхронизируемых первым и вторым тактовыми

Если $11И, Х,„, то это значит, что в -м разряде двоичного представления Аункции У = -VX данному значению агрумента Х соответствует единичный интервал постоянства, в противном случае — нулевой. Результат сравнения со схемы 2 сравнения поступает на первую группу входов группы элементов И 9. Третий тактовый импульс поступает с третьего выхода распределителя 22 импульсов который коммутирует входные импульсы на к направлений, которые представляют собой %-разрядный седьмой выход блока 8 управления. Ход с седьмоro выхода блока 8 управления, соцержащий одну "1" в i -м разряде, оступает на вторую группу входов группы элементов И 9 и открывает в

f5

Сравнения в схеме 2 сравнения и запись значений разрядов Аункции Y =

= Х в регистр 10 осуществляются, начиная со старших разрядов. Тактовый импульс с третьего выхода блока

8 управления также поступает на вход управления сдвигом регистра 7 и осуществляет сдвиг его содержимого на один. разряд в сторону старших.

Четвертый тактовый импульс с четвертого выхода распределителя 22 импульсов поступает на второй вход элемента И 21, на первый вход которого поступает инвертированное на элементе HE l8 значение сигнала с выхода схемы 2 сравнения.

Если на выходе схемы 2 сравнения логический "0", то элемент И 21 оказывается открыт, и четвертый тактовый импульс проходит на четвертый выход блока 8 управления и далее на вход разрешения вычитания счетчика 6, кроме того, через элемент

ИЛИ 16 четвертый тактовый импульс поступает на шестой выход блока 8 .управления и далее на вход управле- . ния счетом счетчика 6. В счетчике 6, реализуется операция вычитания, в результате которой в счетчике 6 оказывается код (2j — 1) -го интервала постоянства следующего (— 1)-го разряда — r.-,„(2q — 1) .

Если на выходе схемы 2 сравнения логическая "1", то элемент И 21 закрыт, а элемент И 20 открыт, и чет вертый тактовый импульс через открытый элемент И 20 поступает на первый вход элемента ИЛИ 15, выход которого является вторым выходом блока 8 управления. С второго выхода блока 8 управления четвертый тактовый импульс поступает на вход разрешения сложения счетчика 6. Кроме того, четвертый тактовый импульс поступает с выхода элемента ИЛИ 15 на второй вход элемента ИЛИ 16 и с

его выхода, который является шестым выходом блока 8 управления, на вход управления счетом счетчика 6. В счетчике 6 реализуется операция сло9 1 жения, в результате которой в счетчике оказывается код (2j + 1)-ro интервала постоянства следующеГо (i — 1)-го разряда — L; „ (2j + 1).

Пятый тактовый импульс поступает с пятого выхода блока 8 управления на вход синхронизации регистра 5 °

В регистр 5 переписывается код вычисленного текущего интервала постоянства со счетчика б.

Таким образом, одна итерация вычислительного процесса выполняется за пять тактов. Вычислительный процесс состоит из итераций,на каждой из которых формируется значение одного разряда функции 1 = Х . Вычислительный процесс заканчивается, когда на последнем выходе распределителя 23 импульсов появляется тактовый импульс, по переднему фронту . которого в регистре 10 формируется значение младшего разряда, а пп заднему — триггер 17 переключается в "0" и закрывает элемент И 19.

Счетчик б работает следующим образом.

Запись информации регистра 5 в счетчик б происходит как обычно по

RS-входам, управляемыми нулями, и тактируется в счетчике б сигналом с первого выхода блока 8 управления при помощи элементов И-НЕ 29-32, при этом на J, 4 †âõî подается логический "0" с выходов элементов

И-НЕ 28 и 33. Управление реверсом также осуществляется обычным образом, открывая сигналами с четвертого или второго выхода блока 8 управления соответствующий элемент

И в элементе 2И-ИЛИ 26 и коммутируя на счетный вход триггера 25 прямой или инверсный выход триггера 24.

При выполнении операции сложения (вычитания) в счетчике б код с инверсных выходов разрядов регистра

7, содержащий единственный "0" в (i + 1)-м разряде, закрывает первый элемент И в элементе 2И-ИЛИ 27, на второй вход которого подключен выход элемента 2И-ИЛИ 26, а единственная "1", содержащаяся в (i+1)-м разряде кода, поступающего с прямых выходов разрядов регистра 7, через второй элемент И в элементе 2И-ИЛИ, открытый сигналом логической "1", с шестого выхода блока 8 управления поступает на счетный вход триггера

25 (i > 1)-го разряда счетчика 6.

141407 10 Таким образом, в счетчике 6 реализу ется операция сложения (вычитания).

Регистр 10 выполнен на счетных триггерах, срабатывающих по переднему фронту сигнала, на счетные входы которых подключены выходы группы элементов И 9.

В известном устройстве вычислительный процесс разбит на два этапа.

На первом этапе выполняются подготовительные вычисления, которые используют операции записи в регистр (время выполнения операции t>„ ), чтения из блока памяти (t

Время выполнения первого этапа

Т =ma {t;t ) ° 1С +ax{t,(t at<); нт.ба+,дк)I ьп (11

На втором этапе в известном устройстве реализуется непосредственное вычисление квадратного корня, при этом еще используются операции сравнения кодов (t, ) и сдвига (с ). Время выполнения второго этайа где 1t — разрядность результата.

Общее время вычисления квадратного корня составляет

35 Т =Т +Т . (31 оБ

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

40 составит

Т =k(max{(t + ).t ),„, „{

45 где t — время выполнения операсч ции сложения на счетчике.

Сравнивая выражения (2) и (4), видим, что временные затраты по вычислению квадратного корня в предлагаемом устройстве примерно равны временным затратам второго этапа вычислительного процесса в известном устройстве. Учитывая, что Т„ "- Т, делаем вывод: быстродействие предлагаемого устройства примерно в два раза вьппе чем известного при увеличении аппаратнык затрат на 10Х.

1141407 12 в повышении быстродействия устройст- ва примерно в два раза при увеличении аппаратных; затрат на 10Х °

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

10 при увеличении аппаратных затрат на 10Х представляет собой сушественный технический эффект.

Точность вычисления квадратного корня в предлагаемом устройстве соответствует точности вычисления

B известном устройстве. Например, при вычислении квадратного корня из Х = 0,3645 получен результат Y =

= 0,6035156 (разрядность дробной части выбрана равной 12, как и в известном устройстве), тогда как истинное значение квадратного корня

Y = 0,603738. Погрешность вычисления составила 0 037Х. Отметим, что погрешность вычисления квадратного корня в предлагаемом устройстве обус-

: ловлена только лишь ограниченной разряд.15 ностью представления результата.

Положительный технико-экономичес", кий эффект изобретения заключается

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

1141407

Фиг.2

1141407

4с

Ф

l1

Ъ

1. с

Юу

4 4 ч

Ю 4

Cv! с

Ъ+

I с

ff с ( )

И с

Гч

Ъ l

If l

З ч

I (4с

vj

P едак тор В . Данк о

Заказ 496/36

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

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

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

Ф

II tt илиал ППП Патент, г. Ужгород, ул. Проектная, 4

I) с (г

11

- с

-1с

Ъ.4

Составитель А.Казанский

Техред M.Kóçüìà Корректор M.Äåè÷èê,