Изобретение относится к вычислительной технике и-ориентировано на использование в быстродействующих специализированных вычислителях, системах цифровой обработки сигналов и в системах автоматики для аппаратурной реализации операции вычисления квадратного корня от аргументов, представленных в модулярной системе счисления.
Целью изобретения является повышение быстродействия.
На фиг. 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
сриг.з
КорректорМ. Шароши
название | год | авторы | номер документа |
---|---|---|---|
Устройство для умножения чисел в модулярной системе счисления | 1986 |
|
SU1368878A1 |
Устройство для умножения чисел в модулярной системе счисления | 1986 |
|
SU1352483A1 |
Устройство для сложения и вычитания чисел с плавающей запятой | 1986 |
|
SU1411742A1 |
Арифметическое устройство в модулярной системе счисления | 1987 |
|
SU1432517A1 |
Устройство для умножения комплексных чисел в модулярной системе счисления | 1985 |
|
SU1280625A1 |
Устройство для умножения чисел в модулярной системе счисления с плавающей запятой | 1986 |
|
SU1411741A1 |
Устройство для вычисления экспоненциальной функции в модулярной системе счисления | 1985 |
|
SU1317433A1 |
Устройство для умножения комплексных чисел в модулярном коде | 1985 |
|
SU1330631A1 |
Устройство для умножения чисел в модулярной системе счисления | 1989 |
|
SU1667065A1 |
Устройство для умножения чисел | 1986 |
|
SU1325475A1 |
Изобретение относится к вычислительной технике и ориентировано на использование в быстродействующих : специализированных вычислителях, системах цифровой обработки сигналов и в различных системах автоматики для аппаратурной реализации операции вычисления квадратного корня числа в модулярной системе счисления. Цель изобретения состоит в повышении быстродействия . Поставленная цель достигается тем, что в устройство,.содержащее регистр 4 сдвига, блоки 6, 10 мультиплексоров, блок 8 суммирования вычетов, блок 11 памяти констант, вспомогательный регистр 12, кольцевой счетчик 13, блок 14 масштабирования, блок 18 элементов И, введены элементы 5, 15 задержки, блок 7 вычисления интервального индекса числа, блок 9 регистров, блок 16 мультиплексоров, элементы И 17, 22, блок 19 модульных сумматоров, блок 20 сравнения, блок 21 деления на два, элемент ИЛИ-НЕ 23 с соответствующими связями. 3 ил. (Л 9 4 СО 4
Устройство для вычисления квадратного корня | 1981 |
|
SU1027718A1 |
Приспособление для точного наложения листов бумаги при снятии оттисков | 1922 |
|
SU6A1 |
Устройство для вычисления функций в модулярном коде | 1985 |
|
SU1278839A1 |
Приспособление для точного наложения листов бумаги при снятии оттисков | 1922 |
|
SU6A1 |
Авторы
Даты
1987-06-15—Публикация
1985-11-25—Подача