Устройство для вычисления квадратного корня числа в модулярной системе счисления Советский патент 1987 года по МПК G06F7/552 G06F7/72 

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

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

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

Устройство для вычисления квадратного корня числа в модулярной системе счисления (фиг. 1) содержит вход 1 аргумента, установочный вход 2, тактовый вход 3 устройства, регистр 4 сдвига, первый элемент 5 задержки, первый блок 6 мультиплексоров, блок 7 вычисления интервального индекса числа, блок 8 суммирования вычетов, блок 9 регистров, второй блок 10 мультиплексоров, блок 11 памяти констант, вспомогательный регистр 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 регистров представляет собой цепочку из 2Т+5 последовательно соединенных регистров, где T Illog через TXC обозначено наименьшее целое число не меньше X. Установочный вход первого регистра является установочным входом блока 9 регистров. Через него осуществляется прием модулярного кода (Ы ,оС„. . .о., ) исход-1 ji1ч

3174342

ного числа А.из.диапазона

К-1

« 1Ч.-1

„,рМ -1| используемой модулярной системы счисления.

tn,,

1П„

,т - сисfO

20

ч к

тема попарно взаимно простых модулей, причем tn,2p+k-2, р - фиксиро(t

ванное натуральное число М П т..

И-1 j 1 J

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

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

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

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

Разрядность регистров, входящих в состав блока 9 регистров первого и второго элементов 5,15 задержки и .Q мультиплексоров блоков 6 и 10 составляет Y Jlog m. ,

Блок 8 суммирования вычетов (фиг. 2) по входному модулярному ко45 ЯУ ( ( -к-1 некоторого числа осуществляет формирование за Т тактов вычета Q(A)/Q(A)/ni, где

Q(A) Х2 Q/C-,); (О

50

i: 1

..li-l

Q.:(.) j±...b (2) 1

S - фиксированное натуральное число;

55

m

kS; с4,„-, / , м:;;,/т.;

Ч,к-Г

1, v- 1 I 1 к- 1 1 .(t

M /mj, ,2...k-1 через /X( обозначено ближайшее к X целое число. При четномkво все, а при нечетном kj во все, кроме последнего, элемен3 13

ты 28 памяти по адресам, старшие и младшие разряды которых определяются остатками c,j и fiL -1, записывает

вычет /Q;.,(Vrl. (РСПри k нечетном в последний элемент 28 памяти по адресу «i., записывается константа (Q. , (e K-i)Xm

Блок 7 вычисления интервального индекса числа имеет структуру, полностью аналогичную описанному блоку 8 суммирования вычетов, и по входному модулярному коду (ot ,c/j.. .о1 ) некоторого числа А из диапазона D модулярной системы счисления осуществляет за Т тактов формирование вггчета.

Т(А)

Rj(;

/riRiK)/

/--4-4...-....K-v

/ K-i к ,

C5)

В ячейку блока П памяти констант по адресу, старшие и младшие разряды которого определяются величинами 7(А) и Q(A), записывается набор констант

(В°,.,.,В;, 1, 1„), где С°°) модулярный код начального приближения В квадратного корня из числа А,

,,H,j9iyiX(A).s

где Т(А)

Р S

Т(А) если Т(А)

Т(А)-т если Т (А)

1, - номер масштаба; Sj(Q(A)+T(A) S)/(2pS); IP - номер масштаба; (2р5)

1° ,1,... L-1

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

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

Блок 16 мультиплексоров содержит 23log,L мультиплексов.

Блок 14 масштабирования чисел осуществляет деление входного числа А, заданного модулярным кодом, на константу Sj . Результатом указанной операции является модулярный код чис- ла . В устройстве для вычисления квадратного корня числа в модулярной системе счисления используется известное масштабирующее устрой3

т

т

174344

ство конвейерного типа, быстродействие которого составляет Т/., Т+3 такто при пропускной способности одна операция масштабирования в один такт. г Блок 19 модульных сумматоров реализует операцию сложения над целыми числами из диапазона модулярной системы счисления по основаниям (т ,t.. ...m,),- операнда и результаты пред10 ставляются в модулярном коде,

Блок 21 деления на два (фиГ, 3)

по входному модулярному коду (о1,о1л

...of ) некоторого числа А fe D осуществляет формирование за два такта J5 величины С А/21, представляемой в модулярном коде.

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

i-1

адресом V Ф 2 , где Ф - значе- .., i 1

20 ние младше го разряда цифры модулярного кода входного числа, записывается четность входного числа. В ячейку элемента 32j памяти (i 1, 2...k) по адресу 2ot|+ Ч записывается

25 вычет

/А-1±/

2

Блок 20 сравнения выполняет ана- 30 ЛИЗ на поразрядное совпадение входных модулярных кодов.

Разрядность вспомогательного регистра 12 и кольцевого счетчика 13 составляет 2Т+5 бит. Установочньм эг входом кольцевого счетчика 13 является установочный вход триггера младшего разряда.

В основу работы устройства для вычисления кйадратного корня числа в модуляр- Q ной системе счисления положена итера- .дивная процедура Ньютона - Рафсона, в рамках которой числитель (j+l)-ro приближения квадратного корня исходного числа А/р М ,, где А в D, оп-

ределяется по формуле

В. (В. +А)(В./р М ) J+1 Z JJt

(4)

5

Пусть (В, В,...,В) - модулярный Q код числителя j-ro приближения квадратного корня. Используя аппарат теории чисел и учитывая, что

fВS

1, приближение можно

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

В ;

1

.i с Г р . М р. S

К-1

K-t

+т(вр S) s,(5)

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

f--

L 2 J

А.

J

(6)

где А. - промасштабированное значение числа А на масштаб 2S,

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

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

В. В, что

j-t 1 эквивалентно выполнению равенства

AJ 1ъ./2-.

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

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

5

0

5

5

0

на адресный вход блока 11 памяти констант, на первом выходе которого формируется модулярный код начального приближения значения квадратного корня числа, а на втором и третьем выходах - номера 1 и ., соответствующих масштабов. Блок 14 масштабирования чисел выполняет операцию деления входного числа, поступающего на информационный вход, на масштаб, номер которого подается на вход номера масштаба. Блок 19 модульных сумматоров суммирует, а блок 20 сравнения производит сравнение модулярных кодов , сформированных на выходах блока 14 масштабирования чисел и блока 21 деления на два. Модулярный код суммы с выхода блока 19 модульных сумматоров поступает на вход первого элемента 5 задержки и первый информационный вход первого блока 6 мультиплексоров. Содержимое кольцевого счетчика 13 пересылается во вспомогательный регистр 12 с выполнением операции поразрядной дизъюнкции над их содержимым. В случае единичного сигнала на входе приема кода вспомогательного регистра 12 в последнем формируется результат логического сложения содержимых кольцевого сче тчика 13 и вспомогательного регистра 12. Блок 18 элементов И выполняет операцию логического умножения (поразрядная конъюнкция содержимых кольцевого счетчика 13 и вспомогательного регистра 12, результат которой поступает на входы элемента ИЛИ-НЕ 23, вход которого подключен к второму входу второго элемента И 22. В случае одновре,менного поступления единичных сигналов на входы второго элемента И 22 на выходе 26 устройства появляется сигнал завершения итеративной процедуры (то есть вы5 числение значения квадратного корня) для очередного аргумента, номер которого определяется унитарным кодом, поступающим с выхода кольцевого счетчика 13 на выход 27 устройства. ВыQ численное значение квадратного корня снимается с выхода блока 19 модуль- . ных сумматоров на выход 24 устройства. В случае завершения работы устройства по вычнслению функции квад5 ратного корня от всех входных аргументов соответствующий сигнал появляется на выходе 25 устройства.

На первом такт€; работы устройства в первый регистр блока 9 регист0

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

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

iB% в;,... в;, 1, 1

На (Т+.)м такте работы на управляющие входы блоков 10 и 16 мультиплексоров поступает сигнал &, вследствие чего модулярный код начального приближения ВJ,, поступающий с первого выхода блока 11 памяти констант на второй информационный вход второго блока 10 мультиплексоров, записывается в первый регистр второго элемента 15 задержки, а величина Ij, поступающая с третьего выхода блока 11 памяти констант на второй информационный вход третьего блока 16 мультиплексоров, проходит на вход номера масштаба блока 14 масштабирования чисел, на информационный вход которого с выхода блока 9 регистров поступает величина А.

На (2Т+3)-м такте работы устройства величина В, с выхода второго элемента 15 задержки поступает на вход блока 21 деления на два.

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

В и (j) , которые на (2Т+5)-м такте

поступают на первый и вторые входы блока 19 модульных сумматоров и блока 20 сравнения соответственно. Блок 19 модул-ьных сумматоров находит модулярный код величины В (см. 6)), а а на выходе блока 20 сравнения формируется сигнал « На этом завершается первая итерация вычисления квадратного корня. Появление единичного сигнала на выходе второго элемента И 22 указывает на окончание

итеративного процесса вычисления

квадратного корня аргумента А/р М, . , значение которого равно В и снимается с выхода блока 19 модульных сумматоров, а унитарный код номера вычис- ,

ленного корня поступает на выход 27 устройства. В случае нулевого сигнала на выходе второго элемента И 22 продолжается процесс вычисления квадратного корня.

На (21+6)-м такте работы устройства на управляющий вход первого блока 6 мультиплексоров и на управляющий вход запрещения вьщачи кода (2Т+5)-го регистра блока 9 регистров

поступает сигнал & О, Величина

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

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

9регистров.

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

7вычисления интервального индекса числа и блок 8 суммирования вычетов формируют на своих выходах величины .f(B,) и Q(B) соответственно, которые поступают на адресный вход блока 1 1 памяти констант на (ЗТ+6)-м такте работы устройства.

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

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

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

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

На (4т+8)-м такте работы величина В с выхода второго элемента 15 задержки поступает на вход блока 21 деления на два.

По истечении (4Т+9)-го такта на

выходах блока 14 масштабирования чисел и блока 21 деления на два формируются соответственно величины

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

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

Благодаря конвейерной структуре в устройстве для вычисления квадратного корня в модулярной системе счисления описанная итеративная процедура может выполняться одновременно для 2Т+5 аргументов.

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

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

среднем занимает (21+5) тактов,

где п - число итераций реализуемо

процедуры, т.е. из расчета на одно

функциональное значение быст родействиё устройства составляет п тактов.

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

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

fO

ь г .

t5

31743410

два и элемент ИЛИ-НЕ, причем тактовый вход устройства соединен с входом разрешения сдвига регистра сдвига, выход (2Т-1-5)-го разряда регистра

5 сдвига (Т , k - число модулей системы счисления) соединен с входом запрещения выдачи блока регистров и с управляющим входом первого блока мультиплексоров, выход старшего (ЗТ+6)-го разряда регистра сдвига соединен с управляющими входами второго и третьего блоков мультиплексоров, вход аргумента устройства соединен с установочным входом блока регистров, выход последнего регистра которого соединен с информацион- ; ным входом блока регистров, выход (Т+1)-го регистра которого соединен с информационным входом блока умноже20 ния на масштабный коэффициент, вход номера масштаба которого соединен с выходом третьего блока мультиплексоров, выход блока умножения на масштабный коэффициент соединен с входом первого слагаемого блока модульных сумматоров и с первым входом блока сравнения, второй вход которого соединен с входом второго слагаемого блока модульных сумматоров и с выходом блока деления на два, выход блока модульных сумматоров подключен к входу первого элемента задержки и к первому информационному входу . первого блока мультиплексоров, в-цо 5 рой информационный вход которого подключен к входу аргумента устройства, выход первого блока мультиплексороЁ соединен с входами блока вычисления интервального индекса числа и блока суммирования вычетов, выходы которых подключены соответственно к входам старших и младших разрядов , адреса блока памяти констант, выход первого элемента задержки соединен с первь1м информационным входом второго блока мультиплексоров, второй информационный вход которого, первый и второй информационные входы третьего блока мультиплексоров сое30

40

45

50

55

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

n131

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

гд

28

29

30

29

I

30

29

фиг. 2

Составитель Н. Шелобанова

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

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

ВНИИШ Государственного комитета СССР

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

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

743412

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

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

31

л

29

31

зг

32

сриг.з

КорректорМ. Шароши

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