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

 

Изобретение относится к вычислительной технике и ориентировано на использование в быстродействующих : специализированных вычислителях, системах цифровой обработки сигналов и в различных системах автоматики для аппаратурной реализации операции вычисления квадратного корня числа в модулярной системе счисления. Цель изобретения состоит в повышении быстродействия . Поставленная цель достигается тем, что в устройство,.содержащее регистр 4 сдвига, блоки 6, 10 мультиплексоров, блок 8 суммирования вычетов, блок 11 памяти констант, вспомогательный регистр 12, кольцевой счетчик 13, блок 14 масштабирования, блок 18 элементов И, введены элементы 5, 15 задержки, блок 7 вычисления интервального индекса числа, блок 9 регистров, блок 16 мультиплексоров, элементы И 17, 22, блок 19 модульных сумматоров, блок 20 сравнения, блок 21 деления на два, элемент ИЛИ-НЕ 23 с соответствующими связями. 3 ил. (Л 9 4 СО 4

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) (50 4 G 6 F 2

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

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

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

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3982848/24-24 (22) 25. 11. 85 (46) 15.06.87. Бюл. Ф 22 (71) Научно-исследовательский институт прикладных физических проблем им. А. Н. Севченко (72) А. А. Коляда, В. М, Амербаев, В. К. Кравцов и М. Ю. Селянинов (53) 681.3(088.8) (56) Авторское свидетельство СССР

Р 1027718, кл. G 6 F 7/552, 1981.

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

У 1278839, кл. G 06 F 7/552, 14.06;85. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТНОГО КОРНЯ ЧИСЛА В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ (57) Изобретение относится к вычислительной технике и ориентировано на использование в быстродействующих специализированных вычислителях, системах цифровой обработки сигналов и в различных системах автоматики для аппаратурной реализации операции вычисления квадратного корня числа в модулярной системе счисления. Цель изобретения состоит в повышении быстродействия ° Поставленная цель достигается тем, что в устройство,,содержащее регистр 4 сдвига, блоки 6, 10 мультиплексоров, блок 8 суммирования вычетов, блок 11 памяти констант, вспомогательный регистр 12, кольцевой счетчик 13, блок 14 масштабирования, блок 18 элементов И, введены элементы 5, 15 задержки, блок 7 вычисления интервального индекса числа, блок 9 регистров, блок 16 мультиплексоров, элементы И 17, 22, блок 19 модульных сумматоров, блок 20 сравнения, блок

21 деления на два, элемент ИЛИ-HE 23 с соответствующими связями. 3 ил.

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

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

На фиг. 1 приведена структурная схема предлагаемого устройства для вычисления квадратного корня числа в модулярной системе счисления; на фиг. 2 — схема блока суммирования вычетов; на фиг. 3 - схема блока деления на два, Устройство для вычисления квадратного корня числа в модулярной системе счисления (фиг. I) содержит вход 1 аргумента, установочный нход

2, тактовый вход 3 устройства, регистр 4 сдвига, первый элемент 5 задержки, первый блок 6 мультиплексоров, блок 7 вычисления интервального индекса числа, блок 8 суммирования вычетов, блок 9 регистров, второй блок 10 мультиплексоров, блок ll памяти констант, вспомогательный регистр 12, кольцевой счетчик 13, блок 14 масштабирования чисел, второй элемент 15 задержки, третий блок

16 мультиплексоров, первый элемент

И 17, блок 18 элементов И, блок 19 модульных сумматоров, блок 20 сравнения, блок 21 деления на два, второй элемент И 22, элемент ИЛИ-НЕ 23, выходы устройства: 24 результата, 25 окончания операции, 26 окончания вычисления квадратного корня и 27 номера вычисленного квадратного корня.

Блок 8 суммирования вычетов (фиг, 2) содержит элементы 28 памяти, регистры 29 и сумматоры 30 по модулю.

Блок 21 деления на два (фиг. 3) содержит элементы 31 и 32 памяти, Блок 9 регистров представляет собой цепочку из 2T+5 последовательно соединенных регистров, где T=llog k(; через 1 Х (обозначено наименьшее целое число не меньше Х, Установочный вход первого регистра является установочным входом блока 9 регистров. Через него осуществляется прием модулярного кода (d oc. ° ° .Ы.„) исходl 7434 2

50 ного числа А.из,диапазона D=(-ðÌ ...pM -1) используемой модулярной

К-1 системы счисления, m m ...m — система попарно взаимно простых модулей, причем mÄ >,2p+k-2, р — фиксированное натуральное число И = П m„..

)=

Информационный вход первого регистра является информационным входом блока 9 регистров и подключен к выходу последнего (2T+5)-ro регистра блока .9 регистров. Выход (Т+1)-ro регистра соединен с входом блока 14 масштаби" рования ° Управляющий вход запрещения выдачи (2T+5)-ro регистра является управляющим входом блока 9 регистров

Разрядность регистра 4 сдвига составляет (ЗТ+6) бит. Регистр 4 на каждом такте работы устройства вЫпол; няет сдвиг содержимого на один бит, Выход (2T+5)-ro триггера регистра 4 сдвига и выход (ЗТ+6)-ro триггера старшего разряда регистра 4 сдвига подключены к чправляющему входу пер25 ного блока 6 мультиплексоров и к управляющим входам второго и третьего блоков 10 и !6 мультиплексоров соответственно.

Первый элемент 5 задержки представляет собой цепочку из (Т+1) последовательно соединенных регистров.

Второй элемент 15 задержки аналогично первому элементу 5 задержки представляет собой цепочку из (T+1.)

35 последовательно соединенных регистров.

Разрядность регистров, входящих в состав блока 9 регистров, первого и нторого элементов 5,15 задержки и

40 мультиплексорон блоков 6 и 10 составК ляет Q ging m. f ..

Блок 8 суммирования вычетов (фиг. 2) по входному модулярному ко45 ду (о „,ы ...с,, ) некоторого числа

АЮ осуществляет формирование за Т тактов вычета q(A)=/q(A)/ë, где

К-1

q(A) = 7 q,(<;); (1)

i=1

Ч.,(, =("-. - 1 (2)

Я вЂ” фиксированное натуральное число;

=M /mi i I 2.. ° k-1 через Х1 обок- значено ближайшее к Х целое число.

При четном k но нсе, а при нечетном но нсе, кроме последнего, элемен17434 4 ство конвейерного типа, быстродействие которого составляет Т, =Т+3 такто припропускной способностиодна операция масштабирования в один такт.

Блок 19 модульных сумматоров реализует операцию сложения над целыми числами из диапазона модулярной системы счисления по основаниям (m ...m ), операнды и результаты предl0 ставляются в модулярном коде.

Блок 21 деления на два (фиг. 3) по входному модулярному коду (о(,о ...о1 ) некоторого числа А E D ocy ществляет формирование за два такта величины ГА/23, представляемой в модулярном коде.

В ячейку элемента 31 памяти с

i-1 адресом, 4 2, где М вЂ” значе1 1

=1 ние младшего разряда i-й цифры модулярного кода входного числа, записывается четность входного числа. В у i=1,2 к-ъ

i,Ê-1 /

11ъ 1

В ячейку блока 11 памяти констант по адресу, старшие и младшие разряды которого определяются величинами q (А) 25 и q(A), записывается набор констант о о о о (a,,...,В„, 1, 1 ), где (a,,...,a )модулярный код начального приближе" ния В, квадратного корня из числа А.

С 1 К-1

/- — : — -/

2 о(.

J где Т(А) Т(А)-m если Т(А) > р;

I, — номер масштаба;

Я = Я(А)+Т (А) S) / (2pS)

1, — номер масштаба;

S =В / (2pS) о

1, 1.C/C,1,... 1.-1j

L — число масштабов, на которые ориентирован блок 14 масштабирования чисел.

Модулярный код начального приближения Во снимается с первого выхода 45 блока ll памяти констант, на второй и третий выходы которого поступают величины 1 и 1, соответственно.

Блок 16 мультиплексоров содержит

211о8 Ь Г мультиплексов, 50

Блок 14 масштабирования чисел осуществляет деление входного числа А, заданного модулярным кодом, на константу Б . Результатом указанной операции является модулярный код чис-55 ла А/Б jj. В устройстве для вычисления квадратного корня числа в модулярной системе счисления используется известное масштабирующее устрой(4) +Т(В ) S) = S„

3 !3 ты 28 памяти по адресам, старшие и младшие разряды которых определяются остатками ; и d „. -1, записывает вычет /g,. (ос ; вЂ, 1)+g - (сС -)/

При k нечетном в последний элемент

28 памяти по адресу о(к, записывается константа (1! (Ы„,))

Блок 7 вычисления интервального индекса числа имеет структуру, полностью аналогичную описанному блоку

8 суммирования вычетов, и по входномУ модУлЯРномУ кодУ (Ы,о1 ...Ы „ ) некоторого числа А из диайазона D модулярной системысчисления осуществляеэ за Т тактов формирование вычета.

К с

Т (А) / R; (Ы;)/гк й,(Ф!)

С5>

/ м„, k 1

Т(А) если Т(А) с р, ячеику элемента 32 J памяти (x = 1, 2...k) по адресу 2+;+ М записывается вычет

Блок 20 сравнения выполняет анализ на поразрядное совпадение входных модулярных кодов, Разрядность вспомогательного регистра 12 и кольцевого счетчика 13 составляет 2T+5 бит. Установочным входом кольцевого счетчика 13 является установочный вход триггера младшего разряда, В основу работы устройства для вычисления квадратного корня числа в модулярной системе счисления положена итеративная процедура Ньютона — Рафсона, в рамках которой числитель (j+1)-ro приближения квадратного корня исходного числа А/р М,, где А c D, определяется по формуле

В = — (В +А) (В. /p . М,)

Пусть (В, В,...,В,) — модулярный

Ю ° ° ° 1 К код числителя j ão ïðèáëèæåíèÿ квадратного корня ° Используя аппарат теории чисел и учитывая, что (В S), < 1, приближение можно

m1 записать в виде

К-1

В 1 с — ГВ,-1 81 (С вЂ” — -1+

5 13

Используя формулы (4) и (5), получаем модифицированную процедуру вычисления квадратного корня исходного числа в л

В. = -- + А. + 2 J (6) где А, — промасштабированное значеJ ние числа А на масштаб 28

В качестве начального приближения квадратного корня исходного числа выбирается величина В,.

Итеративная процедура вычисления квадратного корня завершается, если выполняется равенство В. =В, что

)+ 1 эквивалентно выполнению равенства

А. = (В /2J.

Устройство для вычисления квадратного корня числа в модулярной системе счисления работает следующим образом

По сигналу, подаваемому на установочный вход 2 устройства, происходит занесение соответствующей информации в регистр 4 сдвига и кольцевой счетчик 13, а именно: во все разряды регистра 4 сдвига и младший разряд кольцевого счетчика 13 записываются единицы. Сигналы, поступающие с выходов регистра 4 сдвига и выхода блока 20 сравнения, являются управляющими сигналами. На каждом такте работы устройства сигнал 6,, сформированный на выходе (2T+5) триггера регистра 4 сдвига, подается на управляющий вход первого блока 6 мультиплексоров и вход выдачи кода блока 9 регистров; сигнал б, сформированный на выходе последйего триггера регистра 4 сдвига, поступает на управляющие входы блоков 10 и 16 мультиплексоров; сигнал 6 з сформированный на выходе блока 20 сравнения, поступает на первый вход второго элемента И 22 и вход приема кода вспомогательного регистра 12.

В зависимости от значений управляющих сигналов Q, G и 5 производятся Ф 2 3 действия, обеспечивающие поступление требуемой информации на входы блока 7 вычисления интервального индекса числа, блока 8 суммирования вычетов, блока 14 масштабирования чисел и блока 21 деления на два, а также формирование содержимого вспомогательного регистра 12, Информация, снимаемая с выходов блока 7 вычисления интервального индекса и блока 8 суммирования вычетов, поступает

17434 6

f0

l5

55 на адресный вход блока 11 памяти констант, на первом выходе которого формируется модулярный код начального приближения значения квадратного корня числа, а на втором и третьем выходах — номера 1 и 1, соответствующих масштабов. Блок 14 масштабирования чисел выполняет операцию деления входного числа, поступающего на информационный вход, на масштаб, номер которого подается на вход номера масштаба. Блок 19 модульных сумматоров суммирует, а блок 20 сравнения производит сравнение модулярных кодов, сформированных на выходах блока

14 масштабирования чисел и блока 21 деления на два. Модулярный код суммы с выхода блока 19 модульных сумматоров поступает на вход первого элемента 5 задержки и первый информационный вход первого блока 6 мультиплексоров. Содержимое кольцевого счетчика 13 пересылается во вспомогательный регистр 12 с выполнением операции поразрядной дизъюнкции над их содержимым. В случае единичного сигнала на входе приема кода вспомогательного регистра 12 в последнем формируется результат логического сложения содержимых кольцевого счетчика 13 и вспомогательного регистра 12. Блок

l8 элементов И выполняет операцию логического умножения (поразрядная конъюнкция7 содержимых кольцевого счетчика 13 и вспомогательного регистра 12, результат которой поступает на входы элемента ИЛИ-HE 23, вход которого подключен к второму входу второго элемента И 22. B случае одновременного поступления единичных сигналов на входы второго элемента И 22 на выходе 26 устройства появляется сигнал завершения итеративной процедуры (то есть вычисление значения квадратного корня) для очередного аргумента, номер которого определяется унитарным кодом, поступающим с выхода кольцевого счетчика 13 на выход 27 устройства. Вычисленное значение квадратного корня снимается с выхода блока 19 модульных сумматоров на выход 24 устройства. В случае завершения работы устройства по вычислению функции квадратного корня от всех входных аргументов соответствующий сигнал появляется на выходе 25 устройства, На первом такте работы устройства в первый регистр блока 9 регист7 13 ров с входа 1 аргумента устройства поступает модулярный код числителя

А значения А/р М„ „ аргумента, который также поступает на второй информационный вход блока 6 мультиплексоров, на управляющий вход которого поступает сигнал & =1, вследФ ствие чего с выхода блока 6 мультиплексоров величина А поступает на входы блока 7 вычисления интервального индекса числа и блока 8 суммирования вычетов.

По истечении Т-ro такта на выходах блока 7 вычисления интервального индекса и блока 8 суммирования вычетов формируются соответственно вычеты Ф(А) и g(A) (см. (1) и (3)), которые на (Т+1)-м такте работы устройства подаются на адресный вход блока 1 1 памяти констант, в результате чего на его входы поступает набор констант

На (Т+2)-м такте работы на управляющие входы блоков 10 и 16 мультиплексоров поступает сигнал G =1, вследствие чего модулярный код начального приближения В, поступающий с первого выхода блока 11 памяти констант на второй информационный вход второго блока 10 мультиплексоров, записывается в первый регистр второго элемента 15 задержки, а величина

1, поступающая с третьего выхода блока 1 1 памяти констант на второй информационный вход третьего блока

16 мультиплексоров, проходит на вход номера масштаба блока 14 масштабирования чисел, на информационный вход которого с выхода блока 9 регистров поступает величина А, На (2T+3)-м такте работы устройства величина В, с выхода второго элемента 15 задержки поступает на вход блока 21 деления на два.

По истечении(2Т+4)-го такта на выходах блока 14 масштабирования чисел и блока 21 деления на два формил руются соответственно величины А и (--) которые на (2T+5)-м такте

Во

I поступают на первый и вторые входы блока 19 модульных сумматоров и блока 20 сравнения соответственно. Блок

19 модульных сумматоров находит модулярный код величины В (см, 6)), а

1 а на выходе блока 20 сравнения формируется сигнал G, Ha этом завер1 7434 8 шается первая итерация вычисления квадратного корня. Появление единичного сигнала на выходе второго элемента И 22 указывает на окончание итеративного процесса вычисления квадратного корня аргумента А/р M> ., значение которого равно В, и снимается с выхода блока 19 модульных сумматоров, а унитарный код номера вычисленного корня поступает на выход 27 устройства. В случае нулевого сигнала на выходе второго элемента И 22 продолжается процесс вычисления квадратного корня.

f5 На (2T+6)-м такте работы устройства на управляющий вход первого бло—

KR 6 мультиплексоров и на управляющий вход запрещения выдачи кода (2T+5)-го регистра блока 9 регистров поступает сигнал 6; = О. Величина

В с выхода блока 19 модульных сумма1 торов поступает на вход первого элемента 5 задержки и через первый блок

6 мультиплексоров — на входы блока 7

25 вычисления интервального индекса числа и блока 8 суммирования вычетов, а величина А с выхода блока 9 регистров записывается в первый регистр блока

9 регистров.

30 По истечении (ЗТ+5)-ro такта блок

7 вычисления интервального индекса числа и блок 8 суммирования вычетов формируют на своих выходах величины л

na,) и Я(В „) соответственно, которые поступают на адресный вход блока 11 памяти констант на (3T+6)-м такте работы устройства.

На (ЗТ+7)-м такте на управляющие входы блоков 10 и 16 мультиплексоров

40 поступает сигнал & = О, вследствие чего величина В с выхода первого

1 элемента 5 задержки через второй блок

10 мультиплексоров проходит на вход второго элемента 15 задержки, а ве45 личина 1 через блок 16 мультиплексоров поступает на вход номера масштаба блока 14 масштабирования чисел.

На информационный вход блока 14 масштабирования чисел с выхода блока 9

5р регистров поступает величина А.

На (4Т+8)-м такте работы величина

В с выхода второго элемента 15 за1 держки поступает на вход блока 21 деления на два.

По истечении (4Т+9)-ro такта на выходах блока 14 масштабирования чисел и блока 21 деления на два формируются соответственно величины

131 74 .л В

А и (-" f, которые на (4Т+1О)-м такте работы устройства поступают на первые и вторые входы блока 19 модульных сумматоров и блока 20 сравнения соответственно, Блок 21 модульных сумматоров находит модулярный код величины В (см. (6), а на выходе блока 20 сравнения формируется сигнал O, На этом завершаетз ся вторая итерация вычисления квадратного корня.

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

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

20 счисления описанная итеративная процедура может выполняться одновременно для 2T+5 аргументов °

После появления единичного сигнала на выходе 25 устройства может быть начато вычисление функции квадратного корня от новых(2Т+5) аргументов.

При работе устройства в конвейерном режиме формирование 2T+5 функциональных (квадратных корней) в среднем занимает (2Т+5) тактов, где и - число итераций реализуемся процедуры, т.е. из расчета на одно функциональное значение быстродействие устройства составляет п тактов, Формула изобретения

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

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

34 10 два и элемент ИЛИ-НЕ, причем тактовый вход устройства соединен с входом разрешения сдвига регистра сдвига, выход (2Т+5)-ro разряда регистра сдвига (Т = 1ор 1:(, k — число модулей системы счисления) соединен с входом запрещения выдачи блока регистров и с управляющим входом первого блока мультиплексоров, выход старшего (3T+6)-го разряда регистра сдвига соединен с управляющими входами второго и третьего блоков мультиплексоров, вход аргумента устройства соединен с установочным входом блока регистров, выход последнего регистра которого соединен с информационным входом блока регистров, выход (Т+1)-го регистра которого соединен с информационным входом блока умножения на масштабный коэффициент, вход номера масштаба которого соединен с выходом третьего блока мультиплексоров, выход блока умножения на масштабный коэффициент соединен с входом первого слагаемого блока модульных. сумматоров и с первым входом блока сравнения, второй вход которого соединен с входом второго слагаемого блока модульных сумматоров и с выходом блока деления на два, выход блока модульных сумматоров подключен к входу первого элемента задержки и к первому информационному входу . первого блока мультиплексоров, второй информационный вход которого подключен к входу аргумента устройства, . выход первого блока мультиплексоров . соединен с входами блока вычисления интервального индекса числа и блока суммирования вычетов, выходы которых подклюЧены соответственно к входам старших и младших разрядов, адреса блока памяти констант, выход первого элемента задержки соединен с первым информационным входом второго блока мультиплексоров, второй информационный вход которого, первый и второй информационные входы третьего блока мультиплексоров соединены соответственно с выходами блока памяти констант, выход второго блока мультиплексоров соединен с входом второго элемента задержки, выход которого соединен с входом блока деления на два, разрядный выход вспомогательного регистра соединен с входами первого элемента И и с первым входом блока элементов И, Составитель Н. Шело баиов а

Редактор А. Маковская Техред В. Кадар Корректор М, Шароши

Заказ 2425/44 Тираж 672 Подписное

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

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

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

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