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

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

Иллюстрации

Показать все

Реферат

 

Союз Советских

Социалистических

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

<и924702 (61) Дополнительное к авт. свид-ау (22) Заявлено 210279 (2) ) 2728410/18-24 р М g> з с присоединением заявки М

Э (23) Приоритет

G 06 F 7/552

Государственный комитет

СССР ио делам изобретений и открытий

tS3) УДК681. 325 (088.8) Опубликовано 3004.82. Бюллетень Ио 16

Дата опубликования описания 30.04.82

{72) Автор изобретения

A.A.Øîñòàê (71) Заявитель "

Минский радиотехнический институт (54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО

КОРНЯ

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

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

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

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

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

Действительно, пусть разрядность 25 используемых в устройстве сумматора .и счетчика равна п и m соответственно (значения параметров и и в выбираются исходя из значения максимальной величины, из которого не- 30 обходимо извлекать квадратный корень). В дальнейшем будем предполагать, что между параметрами и и m выполняется соотношение и = 2 m.

Тогда максимальное и минимальное время формирования результата в известном устройстве примерно равно Ттц -(2 1) "gp,. ° >mjn= cn где Сел — время сложения и-разрядных чисел.

Предполагая, что появление каждого значения результата извлечения квадратного корня равновероятно мож"

„I но определить среднее время извлечения квадратного корня -в известном устройстве. Онб примерно равно

Т„ (Т „„+ Т„;,)/2 = 2

Пусть m = 8, тогда Т си,128 слЦель изобретения — увеличение быстродействия устройства для извлечения квадратного корня., Поставленная цель достигается тем, что в устройство для извлечения квадратного корня, содержащее сумматор, счетчик, элемент И и генератор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом знакового разряда сумматора, а. выход — с входами младших разрядов счетчика и сум924702

65 матора, введен шифратор, первый вход и выход которого соединены соответственно с выходом и входом старших разрядов сумматора, второй выход шифратора соединен с входом старших разрядов счетчика управляющий вход 5 устройства соединен с управляющими входами счетчика и сумматора, а также с третьим входом элемента И, выход счетчика соединен с входом сумматора.

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

Устройство (фиг. 1) содержит сумматор 1, счетчик 2, шифратор 3, элемент И 4 и генератор 5 импульсов, вы-20 ход которого соединен с первым вхо-; дом элемента И 4, второй вход которого соединен с выходом 6 знакового разряда сумматора 1, а третий вход— с управляющим входом 7 устройства, который также соединен с управляющими входами сумматора 1 и счетчи" ка 2, выход элемента И 4 соединен со вхОдами младших разрядов счетчика

2 и сумматора 1, выход счетчика 2 соединен со входом сумматора 1, вход шифратора 3 соединен с выходом 8 значений 2k старших разрядов сумматора

1, а его выход 9 со входом 2 k старших разрядов сумматора 1, выход 10 соединен со входом k старших разря- 35 дов счетчика 2.

В предлагаемом устройстве используется сумматор 1 накапливающего типа. Счетчик 2 и сумматор 1 реализованы на двухтактных синхронных 40

Т-триггерах с асинхронными установочными входами. Здесь также предполагается, что вход шИфратора 3 соединен с инверсными выходами 2 k.старших разрядов сумматора 1 (знаковый разряд сумматора в указанные 2 k старших разрядов не входит), а выходы 9 и 10 шифратора 3 соединены с асинхронными установочными входами соответствующих разрядов сумматоРа

1 и счетчик 2, причем значение остатка на выходе 9 шифратора 3 формируется в обратном коде. Выход i-го разряда счетчика 2 (О с i i m — 1) с весом 2 соединен со счетным входом (T-входом) (i + 1)-го разряда сумматора 1 с весом 2" ", т.е. содер" жимое счетчика 2 передается в сумматор 1 с сдвигом на один разряд в сторону старших разрядов. Выход элемента И 4 соединен с счетным входом О-го разряда счетчика 2, а также с счетным входом О-го разряда сумматора 1 ° Хотя. цепи синхронизации на чертеже и не показаны, однаКо они обязятельно подразумеващтся.

Иа Фиг. 2 в качестве примера прведена однородная ячеечная структура блока 3.

Блок 3 содержит матрицу определенный образом связанных ячеек 11 и инверторы 12. В узле реализован алгоритм извлечения квадратного корня с восстановлением остатков. С целью иллюстрации протекания вычислительного процесса в блоке 3 рассмотрен конкретный числовой пример извлече.ния квадратного корня иэ целого числа х = 10101100. Получившиеся при этом результат у и остаток Z соответственно равны 1101 и 00000011.

С помощью нижней группы инверторов

12 формируется обратный код остатка

Z, равный 11111100. На структуре указаны значения наиболее характерных входов и выходов ячеек для рассматриваемого примера.

На фиг. 3 приведена функциональная схема блока 11, используемого в качестве основного в блоке 3. Этот блок имеет входы А, В, C,D и выходы

P,Q . R, S, причем (1 = Р, R = B,,P=A ° (B+C)+B C; S = A (B С + ВС) +

+ A- D - (В -С + BC) + AD.

Если В =О, то Я = A мин с (В ю С), Если D =1 то S = А, Этот блок фактически является управляемым вычитателем-передатчиком, если ее управляющий вход D = О, ячей ка работает как одноразрядный двоичный вычитатель, в противном случае она транзитно передает значение сигнала со входа A на выход S. устройство работает следующим образом.

В исходном состоянии счетчик 2 обнулен, в сумматоре 1 хранится обратный код числа, из которого необходимо извлечь квадратный корень (в знаковом разряде сумматора хранится единица), элемент И 4 не пропускает импульсы, поступающие на его первый вход с выхода генератора 5 импульсов, так как íà его третий вход поступает запрещающий сигнал с входа 7 устройства. С помощью блока 3 определяется значение k старших разрядов результата, которое с выхода 10 блока 3 записывается через установочные входы k старших разрядов счетчика в счетчик 2. Значение же остатка в обратном коде с выхода 9 блока

3 через установочные входы 2 k старших разрядов сумматора записывается в сумматор 1. Запись значений результата и остатка в счетчик 2 и сумматор 1 производится с разрешения сигнала, поступающего на их управляющие входы с входа 7 устройст.— ва. После записи остатка в старшие разряды сумматора 1 производится преобразование содержимого сумматора в дополнительный код путем добавле. 924702 ния единицу в его младший разряд.

На этом этап предсказания значения корня заканчивается. Далее процесс извлечения квадратного корня (если при предсказании не получен точный результат) основан на хорошо.известном представлении извлекаемого числа в ниде суммы членов ряда последовательных нечетных чисел. С разрешения .сигнала, поступающего на третий вход элемента И 4, импульсы с выхода генератора 5 через элемент И

4 поступают на входы младших разрядов счетчика 2 и сумматора 1, при этом прибавление импульса в О-й разряд сумматора в i-м такте осуществля ется одновременно с прибавлением в И сумматор содержимого счетчика, полученного к i-му такту. Процесс извлечения квадратного корня заканчи= вается как только в знаковом разряде сумматора 1 появится ноль,, 20 так как элемент И 4 закрывается под действием нулевого сигнала на его втором входе.

Рассмотрим на примере извлечение квадратного корня в предлагаемом устройстве. Для определенности примем, что n = 16, m = 8, k = 4. Пусгь число х, из которого необходимо извлечь квадратный корень, равно

1010l10001000100. Тогда в исходном состоянии в сумматоре будет находиться код v0 = 1.0101001110111011, а в счетчике код 2 О = 00000000.

На этапе предсказания значения корня на вход блока 3 с инверсных восьми выходов старших разрядов сумматора поступает код 10101100, т.е. фактически значение восьми старших разрядов числа х, после чего на выходе 9 блока 3 формируется остаток 40 в обратном коде, равный 11111100, который записывается в старшие разряды сумматора 1, а на выходе 10 формируется результат, равный 1101 (фиг. 2), который записывается.в 45 старшие разряды счетчика 2..Далее содержимое сумматора преобразуется в дополнительный код путем добавления единицы в младший разряд сумматора, после чего содержимое сумматора и счетчика соответственно равно у =

1.1111110010111100, 2 g = 11010000.

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

В первом шаге к содержимому сумматора.прибавляется величина 2. Z „ + 1, а также единица в младший разряд счетчика. После чего содержимое счетчика и сумматора соответственно равно у1 = 1.1111111001011101,2 1= 11010001. ф0

Во втором шаге к содержимому сумма-. тора прибавляется величина 2 Z + 1 а к содержимому счетчика - единица в младший разряд. Тогда уЕ =

=0.0000000000000000, Е = 11010010,и 65 процесс извлечения квадратного корня заканчивается.

Таким образом, в предлагаемом устройстве извлечение квадратного корня из числа х = 1010110001000100 произведено на три шага, длительность каждого из которых примерно равна времени сложения 16-разрядных чисел. В известном же устройстве извлечение корня из этого же числа потребовало бы выполнения 210 таких же по длительности шагов.

Таким образом, изобретение позволяет существенно увеличить скорость извлечения квадратного корня.. Действительно, если в известном устройстве среднее время извлечения квадратного корня равно 2 " "- ГСА, то в предлагаемом оно составляет величину, примерно равную 2 -,„р,,т.е. среднее время извлечения квадратно.го корня в предлагаемом устройстве, в 2 раэ меньше в сравнении с прототипом. Пусть k = 4, m = 8, n = 16, тогда предлагаемое устройство в

16 раз быстрее, чем известное. Объем же дополнительно введенного оборудования незначительный и равен примерно оборудованию 16-разрядного комбинационного сумматора со сквозным переносом (фиг. 2 и 3).

Технико-эконоМическое Преимущество предлагаемого устройства состоит в существенном увеличении быстродействия известного устройства. Так например, если m - =8 и k = 4, то быстродействие предлагаемого устройства примерно в 16.раз выше, чем быстродействие известного устройства, Объем же дополнительного оборудования незначительный и равен примерно оборудованию 16-разрядного сумматора со сквозным переносом.

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

Устройство для извлечения квадратного корня, содержащее сумматор, счетчик, элемент И и генератор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом знакового разряда сумматора, а выходс входами младших разрядов счетчика и сумматора, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введен шифратор, первый вход и выход которого соединены соответственно с выходом и входом старших разрядов сумматора, второй выход шифратора соединен с входом старших разрядов счетчика, управляющий вход устройства соединен с управляющими входами счетчика и сумматора„ а также с третьим входом

924702 элемента И, выход счетчика соединен с входом сумматора.

Источники информации, принятые во внимание при экспертизе

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

Р 362297, кл. G 06 F 7/52,. 1969.

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

9 394781, кл. G 06 F 7/38, 1971

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