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

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

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

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

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

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

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

Т„с,г;()-Гсд.; f где сгА - время сложения п-разрядных чисел,

Предполагая, что появление каждого значения результата извлечения квадратного корня равновероятноi можно определить среднее время извлечения квадратного корня в известном устройстве. Оно примерно равно

ТСР (Ттм+ Twin)/2 2 --rtv Пусть m 8, тогда Т ср « ,128 tt..

Цель изобретения - увеличение

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

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

25 счетчик, элемент И и генератор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом знакового разряда сумматора, а выход - с вхо30дами младших разрядов счетчика и суълматора, введен шифратор, первый вхо и выход которого соединены соответс венно с выходом и входом старших ра рядов сумматора, второй выход шифра тора соединен с входом старших раз рядов счетчика управляющий вход устройства соединен с управляющими входами счетчика и сумматора, а так же с третьим входом элемента И, выход счетчика соединен с входом сумматора . На фиг. 1 приведена блок-схема предлагаемого устройства для извлечения квадратного корня; на фиг. 2 структурная схема узла извлечения квадратного корня; на фиг. 3 - функ циональная схема ячейки , используемой . 2. Устройство (фиг. 1) содержит сумматор 1, счетчик 2, шифратор 3, эле мент И 4 и генератор 5 импульсов, вы ход которого соединен с первым входом элемента И 4, второй вход которого соединен с выходом б знакового разряда сумматора 1, а третий вход с управляющим входом 7 устройства, который также соединен с управляющими входами сумматора 1 и счетчика 2, выход элемента И 4 соединен со входами младших разрядов счетчика 2 и сумматора 1, выход счетчика 2 соединен со входом сумматора 1, ехо шифратора 3 соединен с выходом 8 зн чений 2k старших разрядов сумматора 1, а его выход 9 со входом 2k стар ших разрядов сумматора 1, выход 10 соединен со входом k старших разря дов счетчика 2. В предлагаемом устройстве исполь зуется сумматор 1 накапливающего типа. Счетчик 2 и сумматор 1 реализованы на двухтактных синхроннЕДХ Т-триггерах с асинхронньами установо ными входами. Здесь также предполагается , что вход шифратора 3 соединен с инверсными выходами 2-К.старших разрядов сумматора 1 (знаковый разряд сумматора в указанные 2«k старших разрядов не входит), а выходы 9 и 10 шифратора 3 соединены с асинхронными установочными входами соответствующих разрядов сумматора 1 и счетчик 2, причем значение оста ка на выходе 9 шифратора 3 формиру ется te обратном коде. Выход i-ro разряда, счетчика 2 (О i т - 1) с весом 2 соединен со счетным входом (Т-входом) (i + 1).-го разряда сумматЬра 1 с весом 2 Т.е. содержимкэе счетчика 2 передается в сумматор 1 с сдвигом на один разряд в сторону старших разрядов. Выход элемента,И 4 соединен с счетным входом О-го разряда счетчика 2, а также с счетным входом разряда сумматора 1. Хотя, цепи синхронизации на чертеже и не показаны, однако они обязательно подразумева1Ч ТСЯ. На фиг. 2 в качестве примера приведена однородная ячеечная структура блока 3. Блок 3 содержит матрицу определенным образом связанных ячеек Ни инверторы 12. В узле реализован алгоритм извлечения квадратного корня с восстановлением остатков. С целью иллюстрации протекания вычислительного процесса в блоке 3 рассмотрен конкретный числовой пример извлечения квадратного корня из целого числа х 10101100. Получившиеся при этом результат у и остаток Z соот- ветственно равны. 1101 и 00000011. С помощью нижней группы инверторов 12 формируется обратный код остатка 2, равный 11111100. На структуре указаны значения наиболее характерных входов и выходов ячеек для рассматриваемого примера. На фиг. 3 приведена функциональная схема блока 11, используемого в качестве основного в блоке 3. Этот блок имеет входы А, в, C,D и выходы P,Q . R, S, причем Q о, R В, .(В+С)+В-С; S А- (ВС + ВС) + + А-Ь -(В-С + ВС) + A-D. ЕСЛИ D 0, то S AMMHVC (Вплк,с С). Если D 1, то S Ад Этот блок фактически является управляемым вычитателём-передатчиком, если ее управляющий вход , ячей;ка работает как одноразрядный двоичный вычитатель, в противном случае она транзитно передает значение сигнала со входа А на выход S. Устройство работает следующим образом. В исходном состоянии счетчик 2 об.нулен, в сумматоре 1 хранитх:;я обратный код числа/ из которого необходимо извлечь квадратный корень (в знаковом разряде сумматора хранится единица), элемент И 4 не пропускает импульсы, поступающие на его первый вход с выхода генератора 5 импульсов, так как на его третий вход поступает запрещающий сигнал с входа 7 устройства. С помощью блока 3 определяется значение k старших разрядов результата, которое с выхода 10 блока 3 записывается через установочные входы k старших разрядов счетчика в счетчик 2. Значение же остатка в обратном коде с выхода 9 блока 3 через установочные входы 2-k старших разрядов сумматора записывается в сумматор 1. Запись значений результата и остатка в счетчик 2 и сумматор 1 производится с разрешения сигнала, поступающего наих управлягацие входа с входа 7 устройства. После записи остатка в старшие разряды сумматора 1 производится преобразование содержимого сумматора в дополнительный код путем добавления единищл в его младший разряд. На этом этап предсказания значения корня заканчивается. Далее процесс извлечения квадратного корня (если при предсказании не получен точный результат) основан на хорошо из вестном представлении извлекаемого числа в ниде суммы членов ряда последовательных нечетных чисел. С раз решения сигнала, поступающего на третий вход элемента И 4, импульсы выхода генератора Ь через элемент И 4 поступают на входы младших разря дов счетчика 2 и сумматора 1, при этом прибавление импульса в 0-й раз ряд сумматора в 1-м такте осуществл ется одновременно с прибавлением в сумматор содержимого счетчика, полу ченного к i-му такту. Процесс извле чения квадратного корня заканчи вается как только в знаковом разряде сумматора 1 появится ноль, так как элемент И 4 закрывается под действием нулевого сигнала на его втором входе. Рассмотрим на примере извлечение квадратного корня в предлагаемом устройстве. Для определенности примем/ что п 1&, m 8, k 4. Пуст число X/ из которого необходимо извлечь квадратный корень, равно 1010110001000100. Тогда в исходном состоянии в сумматоре будет находит ся код 40 1.0101001110111011/ а в счетчике код ZQ 00000000. На этапе предсказания значения корня на вход блока 3 с инверсных восьми выходов старяаих разрядов сум матора поступает код 10101100, т.е. фактически значение восьми старших разрядов числа- х, после чего на выходе 9 блока 3 формируется остаток в обратном коде, равный 11111100, который записывается в старшие разряды сумматора 1, а на выходе 10 формируется результат, равный 1101 (фиг. 2), который записывается.в старшие разряды счетчика 2.-Далее содержимое сумматора преобразуется в дополнительный код путем добавления единицы в младший разряд сумматора после чего содержимое сумматора и счетчика соответственно равно у 1.1111110010111100, Zi 11010000 На этом первый этап предсказания кор ня заканчивается. На втором этапе потребуется выполнить еще два шага. В первом шаге к содержимому сумматора прибавляется величина 2-- Z + 1, а также единица в младший разряд счетчика. После чего содержимое счет чика и сумматора соответственно равн у 1.1111111001011101,2 11010001 Во втором шаге к содержимому сумматора прибавляется величина 22ц4 If а к содержимому счетчика - единица в младший разряд. Тогда Уд 0.0000000000000000, Z 11010010 ,и процесс извлечения квадратного Kop-i ня заканчивается. Таким образом, в предлагаемом устройстве извлечение квадратного корня из числа х s. 1010110001000100 произведено на три шага, длительность каждого из которых примерно равна времени сложения 16-разрядных чисел. В известном же устройстве извлечение корня из этого же числа потребовало бы выполнения 210 таких же по длительности шагов. Таким образом, изобретение позволяет существенно увеличить скорость извлечения квадратного корня.. Действительно, если в известном устройстве среднее время извлечения квадратного корня равно 2 -Сс,л то в предлагаемом оно составляет величину, примерно равную 2 -Ссл ,т.е. среднее время извлечения квадратно.го корня в предлагаемом устройстве, в 2 раз меньше в сравнении с прототипом . Пусть , , тогда предлагаемое устройство в 16 раз быстрее, чем известное. Объем же дополнительно введенного оборудования незначительный и равен примерно оборудованию 16-разрядного комбинационного сумматора со сквозным переносом (фиг, 2 и 3). Технико-экономическое преимущество предлагаемого устройства состоит в существенном увеличении быстродействия известного устройства. Так, например, если и , то быстродействие предлагаемого устройства примерно в 16.раз выше, чем быстродействие известного устройства, Объем же дополнительного оборудования незначительный и равен примерно оборудованию 16-разрядного сумматора со сквозным переносом. Формула изобретения Устройство для извлечения квадратного корня, содержащее сумматор, счетчик, элемент И и генератор импульсов, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом знакового разряда сумматора, а выход с входами младших разрядов счетчика и сумматора, отличающееся тем, что, с целью повышения быстродействия, в него введен шифратор, первый вход и выход которого соединены соответственно с выходом и входом старших разрядов сумматора, второй выход шифратора соединен с входом старших разрядов счетчика, управляющий вход устройства соединен с управляющими входами счетчика и сумматора,, а та.кже с третьим входом

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

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

Ди.О

1.Авторское свидетельство СССР № 362297, кл. G 06 F 7/52,. 1969.

2. Авторское свидетельство СССР № 394781, кл. G 06 F 7/38, 1971

.