Устройство для поворота вектора Советский патент 1984 года по МПК G06F7/544 

сдвига соединены с вторыми информационными входами соответственно первого, второго, третьего, шестого, восьмого,десятого, седьмого, девя. того и одиннадцатого комбинационных сумматоров-вычитателер, входы синхронизации второго, третьего,х четвертого и пятого D -триггеров соединены с первым выходом дешифратора, второй, третий и четвертый выходы де шифратора соединены с входами синхро низации соответственно шестого, седьмого и восьмого и -триггеров, единичные выходы второго и третьего D-триггеров соединены с управляющими входами соответственно второго и третьего комбинационных суммаТороввычитателей, выход третьего комбинационного сумматора-вычитателя соединен с единич;иым входом четвертого D-триггера, единичный вход пятого Э-триггера соединен с выходом старше го разряда первого регистра сдвига, единичный выход пятого 1 -триггера соединен с единичным входом шестого В-триггера, единичные входы седьмого и восьмогоD-триггеров соединены с выходами младших разрядов соответственно четвертого и пятого регистров сдвига, единичный выход шестого -триггера соединен с. управляющим входами четвертого и пятого комбинационных сумматоров-вычитателей, единичный выход седьмого)-триггера соединен с управляющими входами шестого и седьмого комбинационных сумматоров-вьгчитателей, единичный выход : восьмого D-триггера соединен с управляющими входами восьмого и девятр 85 го комбинационных сумматоров-вычитателей, единичный выход четвертого)триггера соединен с управлякнцими входами десятого и одиннадцатого комбинационных сумматоров-вычитателей, первые информационные входы четверого и пятого комбинационных сумматоров-вычитателей соединены с входом первого операнда устройства, вход второго операнда которого соединен с вторыми информационными входами четвертого и пятого комбинационных1 сумматоров-вычитателей, единичный ,, вход первогоD-триггера и информационный вход первого регистра сдвига соединены с входом третьего операнда устройства, адресные входы постоянных запоминающих блоков второй группы соединены с выходом двоичного счетчика, выходы данных первого, второго и третьего постоянных запоминающих блоков второй группы соединены с входами синхронизации соответственно девятого и десятого, одиннадцатого и двенадцатого, тринадцатого и четырнадцатого -триггеров, единичные выходы девятого, десятого, одиннадцатого, двенадцатого, тринадцатого и четырнадцатого D-триггеров соединены с первыми информаци,онными входами соответственно седьмого, шестого, девятого, восьмого, одиннадцатого и десятого комбинационных сумматоров-вычитателей, выходы десятого и одиннадцатого комбинационных сумматоров-вычитателей соедиI . -л . , нены соответственно с первой и второй шинами выходных данных ройства .

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

Известно устройство поворота вектора, работаняцее по методу Волдёра (цифра за цифрой), содержащее регистры сдвига, сдвигатели и сумматоры. Входы регистров сдвига соединены с шинами входных и выходных данных и с выходами сумматоров, выходы регистров сдвига соединены с входами сумматоров и сдвигателей, выходы сдвигателей соединены с входами сумматоров. Сдвигатели предназначены для осуществления операции умножения операндов .на числа , где « - целое 03

Наиболее близким по технической

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

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

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

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

группу постоянных запоминающих блоков, дешифратор, первый, второй и третий комбинационные сумматоры-вычитатели и первьй D-триггер , вькод генератора тактовых импульсов соединен со счетным входом двоичного счетчика и с тактовыми входами первого, второго и третьего регистров сдвига, выход двоичного счетчика соединен с адресными входами постоянных запоминающих блоков первой группы и с информационным входом дешифратора,, первьй выход дешифратора соединен с входом синхронизации первогоD-триггера, выход старшего разряда первого регистра сдвига соединен с первым информа-t ционным входом первого комбинационного сумматора-вычитателя, второй информационный вход комбинационного сумматора-вычитателя соединен с выходом данных первого постоянног о запоминающего блока первой группы, единичный выход первого D-триггера соединен с управляющим входом первого комбинационного сумматора-вычитателя, дополнительно введены четвертый, пятый, шестой, седьмой, восьмой и девятый регистры сдвига, с четвертого по одиннадцатый комбинационные сугматоры-вычитатели, с второго по четырнадцатыйD-триггеры, вторую группу постоянных запоминающих блоков, причем первые информационные входы второго и пятого комбинационных сумматоров-вычитателей соединены соответственно с выходами данных второго и третьего постоян- ных запоминающих блоков первой груп,пы, выходы первого, второго, четвертого, пятого, шестого, седьмого, восьмого и десятого комбинационньк сумматоров-вычитателей соединены с информационными входами соответственно второго, третьего. Четвертого, седьмого, пятого, шестого и девятого регистров сдвига и с информационными входами соответственно второго, третьего, девятого, десятого, одиннадцатого, двенадцатого,тринадцатого и четырнадцатого) -триггеров, тактовые входы четвертого, пятого, шестого, седьмого восьмого и девятого регистров сдвига соединены с выходом генератора тактовых импульсов, выходы старших разрядов первого, второго, третьего, четвертого, пятого, шестого, седьмого- восьмого и девятого регистров сдвига соединены с вторыми информационными входами соответственно первого, второго, третьего, шестого, восьмого десятого, седьмого, девятого и одиннадцатого комбинационных сумматоров-вьгчитателей, входы синхро низации второго, третьего, четвертого и пятогоD-триггеров соединены с первым выходом дешифратора, второй, третий и четвертый выходы дешифратора соединены с входами синхронизадаи соответственно шестого, седь мого и восьмого }-триггеров, единичные выходы второго и третьего 3 -триг геров соединены с управляющими входами соответственно второго и третье го комбина1щонньк сумматоров-вычитателей, выход третьего комбинационного сумматора-вычитателя соединен с единичным входом четвертого33-триг гера, единичный вход пятого О-тригге ра соединен с выходом старшего разрядапервого регистра сдвига, единичньй выход пятого О-триггера соединен с единичным входом шестого)-триггера, единичные входы седьмого и восьмого Р-триггеров соединены с выходами младших разрядов соответственно четвертого и пятого регистров сдвига, единичный выход шестого -триггера соединен, с- управляющими входами четвертого и пятого комбинационных сумматоров-вычитателей, единичный выход седьмого 1 -триггера соединен с управ ляющими входами шестого и седьмого комбинационных сумматоров-вьгчитателей, единичный выход восьмого)-триг гера соединен с управляющими входами восьмого и девятого комбинационных сумматоров-вычитателей, единичный выход четвертого)-триггера соединен с управляющими входами десятого и с одиннадцатого комбинационных суммато ров-вычитателей,первые информационные входы четвертого и пятого комбинацион ных сумматоров-вычитателей соединены с входом первого операнда устройства вход второго операнда которого соеди йен с вторыми информационными входа ми четвертого и пятого комбинационных сумматоров-вычитателей, единичный вход первого 2-триггера и информационный вход первого регистру сдвига соединены с входом третьего операнда устройства, адресные входы постоянных запоминакицих блоков второй группы соединены с выходом дво:ичного счетчика,ВЫХОДЫ данных первоРо, второго и третьего постоянных за поминающих блоков второй группы соединены с входами синхронизации соответственно девятого и десятого, одиннадцатого и двенадцатого, тринадцатого и четырнадцатого) -триггеров единичные выходы девятого, десятого, одиннадцатого, двенадцатого, три- надцатого и четырнадцатого)-триггеров соединены с первыми информационными входами соответственно седьмого, шестого, девятого, восьмого, v одиннадцатого и десятого комбинационных сумматоров-вычитателей, выходы десятого и одиннадцатого комбинационных сумматоров-вьгчитателей соединены с шинами выходных данных. На фиг. 1 представлена функциональная схема устройства на фиг. 2 временная диаграьжа его работы. Устройство содержит генератор 1 тактовых импульсов, двоичный счетчик 2, с первого по девятый регистры 3-11 сдвига, первую и вторую группы постоянных запоминающих блоков 12 и 13, дешифрзатор 14, с первого по восьмой) -триггеры 15-22 и с девятого по четырнадцатыйD-триггеры ЗА-39, с первого по одиннадцатый комбинационные суммато1 ы-вьиитатели 23-33, входы 40-42 первого, второго и третьего операндов, первый и второй выходы 43 и 44 данных. Поворот вектора комплексного числа осуществляется согласно алгоритму цифра за цифрой оледуюпщм образом. Пусть вектор числа (3 поворачивается на угол ей.Результатом поворота являете вектор числа В X. + iVv. f / П координаты которого вычисляются по итерационной процедуре. а; sign Z;, Х,, Xjv a.Y;2:; Y;., Yj- a-X.2-, . Z. г; -a. arctg2- Для n -разрядного комплексного числа процедура повторяется 1т раз (при требовании сохраненияточности до младшего разряда числа). Начальные условия: О, 0 -об. Для реализации соотношений (1) {4J требуются устройства, выполняюие сложение,, вычитание, сдвиг (умножение на 2) и постоя«рое запоинающее устройство(ПЗУ), зузаняее значения функцииorclg 2. При реаизации операций (1)-(4) посредстом устройства-прототипа для повоота одного вектора комплексного числа требуется l(b+1) тактовых импульсов, где п- разрядность числа. Для обработки N чисел требуются временные затраты, соответствукяцие И.пх (И+1) тактовым импульсам. Структура 5 предлагаемого устройства позволяет сократить временные затраты на обработку массивов комплексных слов за счет одновременной обработки п слов. Структура устройства рассчита- to на на разрядность вещественной и МНИМОЙ.частей обрабатываемого слова П 4 (без учета знакового разряда) и может быть расширена для обработки слов произвольной разрядности. 5

Устройство работает следукнцим образом.

Генератор 1 формирует тактовые импульсы, управлякире работой регистров 3-11 сдвига. Эти импульсы посту-. 2о пают на счетньй вход двоичного счетчика 2. Коэффициент пересчета счетчика равен пяти (в общем случае Н+1). Выходы разрядов счетчика соединены с адресными входами блоков 12, где 25 хранятся значения величины circtg 2, arctg 2, arct 2 (в общем случае до aicig2). На информационный вход регистра 3, начиная с момента времени -tj,, последовательно во времени роступают разряды числа 2д -об. Порядок поступления устанавливается от младших разрядов к старпшм.Разрядность регистров 3, 4 й5 сдвига равна 5 (в общем случае И +1). В момент времени .(фиг. 2) по истечении п+1 тактовых импульсов число ZQ оказьтаётся полностью записанным в регистре 3, В этот момент по команде с дешифратора 14, поступающей через каждые п+1 тактовых импульсов, старший (знаковый) разряд числа Zo фиксируется в 3) - триггере 15. Выход 3)-триггера соединен с управлякицим входом комбинационного сумматора-вычитателя (КСВ) 23 и, в зависимости от зафиксированного бита а,, в продолжении следующих h+1 тактов осуществляется сложение с числом Zg или вычитание из него в соответствии с выражением (4) величины(гс 2 поразрядно поступающей из блоков 12 от младших разрядов к старшим. К моменту времени tj в регистре 4 формируется код числа 2 (S 0 arct 2 . Его старщий (знаковый) разряд ац сируется в триггере 16 и далее выполняются аналогичные операций. В момент времени в триггере 17 фиксируется знак а, а в момент времени i-y в триггере 18 фиксируется знак а. При этом остальные разряды числа ZaHe фиксируются, так как при л 4 нет необходимости в его запомина- ,

НИИ.

Поступление кодов вещественной части (XQ) и мнимой части (У) комплексного числа, подвергаемого операции поворота вектора, в КСВ 26 и 27 начинается в момент времени tj через 11 тактов (в общем случае через П +ь-ь2/2 тактов) после начала приема числа 7о (момент времени т-о ) К моменту времени i«c дешифратора 14 на триггер 20 приходит сигнал, разрешающий запись в него бита 5ign2o. Бит а представляет собой старший (знаковый) разряд числа Zj, , который к моменту ij записан в D -триггере 19. Бит BQ сохраняется в триггере 20 в продолжениеп+1 тактов, необходимых для осуществления операций (2) и (3) нзд rt-разрядным числом. Операции (2) и (3) для осуществляются в КСВ 26 и 27, а результаты этих операций в продолжение h +1 тактов после момента t последовательно проходят регистры 6 и 9, имеющие по два разряда,

В продолжение такта, следующего за моментом i на выходе первого блока 13 появляется сигнал логического .нуля, препятствукяций записи младших разрядов чисел и У, в D-триггеры 34 и 35 соответственно. В продолжение следующих п тактов на выходе первого блока 13 форми руется сигнал логической единищ), разрешающей запись в триггеры 34 и 35. В результате на КСВ 28 и 29 с триггеров 35 и 34 соответственно в продолжениеп +1 тактов начиная с момента BpeMeHiit, поступают коды чисел Ч, 2 и Х . На друг 1гие входы КСВ 28 и 29 в это время, поступают соответственно коды чисел X, и Y) из регистров 6 и 9, и КСВ осуществляют оператдии (2) и (3) для j 1. К моменту i на управлякяди входы КСВ 29 и 30 приходит знак Сц с выхода и-триггера 21. Знак СЦ фиксируется в триггере 21 из третьего, считая от младшего, разряда в момент времени i4(фиг. 2) и хранится в триггере в продолжение следующих и+1 тактов. В продолжение h+1 тактов после момента t коды чисел Y поступают в трехразрядные регистры 7 и 10 сдвига. На вьЕКоде второго блока 13 в продолжение двух тактов, следующих за моментом , формируется сигнал л гического нуля, а в продолжение следующих П-1 тактов - сигнал логической единицы. С триггеров 37 и 36 на КСВ 30 и 31 соответственно, начиная с момента i , в продолжение п ч-1 тактов поступают коды чисел Х., 2 и Х 2 На другие входы КСВ 30 и 31 в это время поступают из регистров 7 и 10 коды чисел Xj и Vj соответственно. Знак й- фиксируется в триггере 22. С выходов КСВ 30 и 31 в продолжение itf+l тактов с момента tg в четырехразрядные регистры 8 и 11 сдвига поступают коды Х и V . На выходе третьего блока 13 сигна логического нуля формируется в продолжение следунщих 1-2 тактов. Начиная с момента f с выходовD-триггеров 39 и 38 на входы КСВ 32 и 33 в продолжение n+l тактов поступают коды чисел Y 52 и )} 2 . Из регистров 8 и 11 на другие входы КСВ 32 и 33 в это время поступают коды . Знак а фиксируется в О-триггере 18 в тот же момент времени с, когда он появляется на выходе КСВ 25 (фиг. 2). На выходы данных в продолжениеИ4-1 тактов с момента t поступают коды вещественной ( Х) и мнимой 1 - - 4 частей результата вычислений. До момента времени 17 ™1ьгаание результатов вычислений не производится. Разряды входных данных следующего обрабатываемого вектора начинают поступать в устройство непосредственно по окончании поступления входных данных предьщущего вектора. Обозначим i v - / Z - -, их соответственно Х, Уд и Разряды с поступают в регистр 3 момента tt по момент tj . Разряды Хс, и УО поступают на КСБ 26 и с момента tg с задержкой по отношению к раз Т,д нап. тактов. Результат рядам г (фиг.2) поступаю вычисления Х- и У на выходы данных в продолжение Л+1 (ч-актов, начиная с момента ig , непо-:. средственно по окончании поступления разрядов предыдушего числа Аналогичным образом обрабатьшают слово Х и Уд (фиг. 2). Затраты времени на обработку одного слова соответствуют (n+l) тактов, а затраты на обработку N слов - (h+t) + (W-1)x(ii + 1) (n+1)x x(tH-N) тактов. Таким образом, время на обработку N слов, начиная с N 2 ,j П 2, уменьшается по сравнению с известным устройством на Интервал, соответствующий (N-1)n -N- и тактовым импульсам (, i Nn(nHV(n4|(ntNb(. Итак, для реализации устройства, обрабатывающего И-разрядные комплексные числа, в схеме обработки Z(регистры 3, 4 и 5, комбинационные сумматоры-вычитатели 23, 24 и 25,13 -триггеры 15, 16, 17 и 18) требуется (1-1 блоков, содержащих регистр сдвига комбинационный сумматор-вычитатель и 3)-триггер, соединенные так, как соединены между собой регистр 3, комбинационный сумматор-вычитатель 23 и триггер 15. Регистры в этом случае содержат поП+1 разрядов. На выходе схемы находится регистр 18, соединенный с выходом комбинационного сумма тора-вычитате ля последнего блока (фиг. 1). В схеме обработки Х,- и У; (регистры 6-11, КСВ 26-33, D -тригге--: ры 19-22, 34-39) в общем случае содержится ц -1 блоков, включающих два регистра сдвига, два КСВ и не менее трех О-триггеров, соединенных так, как соединены регистры 6 и 9, КСВ 26. и 27, триггеры 19, 20, 34 и 35 на фиг.1. При этом для блока, осуществляющего 1 -ю итерацию, л- 1,2 .. ., (п-1), регистры, соответствующие регистрам 6 и 9, содержат по i +1 разрядов, число Р-триггеров в цепи, соответствующей последовательности триггеров 19 и 20, определяется тем фактом, что знак CL.,t должен быть задержан по отношению к времени его появления в младших разрядах регистров из схемы обработки 2 (регистры 3, 4 и 5 на фиг. 1, моменты времени i , , 5 на-фиг. 2) )/2 тактов (соответственно промежуткам времени .-i ,, . 2). Тактирование триггеров, соответствующих триггеру 19jосуществляется через каждые тактов, а триггера, соответствующего триггеру 20 - в момент поступления нового слова на КСВ, соответствукщий КСВ 26 и 27 (момент i на фиг. 2). Функции и связи генератора 1, счетчика 2, блоков 12 и 13, дешифратора 14, выходных КСВ 32 и 33 не зависят от разрядности обрабатываемых слов. Счетчик 2 имеет коэффициент пересчета, равный И+1f блоки 12 и 13 - числ одноразр5щных выходовjравное п-1, де шифратор 14 предназначен для декоди.рования чисел от О до rV . Устройство предполагает меньшие аппаратурные затраты, чём тривиальное использование блоков, аналогичных устройству-прототипу, для паралг лельной обработки И разрядов. Для реализацииповорота вокруг вектора 4-разрядного кo плeкcнoгo числа в предложенном устройстве требуется 4.7 D-триггеров (используемых в составе регистров сдвига и автономно), а при использовании четырех блоков уст ройства-прототипа - 64 О-триггера. В общем случае для п блоков устройства-прототипа требуется Зл + 4il . ( D-TpHrrepa,a в предложенном устройстве - не более 5п. -Таким образом при больших разрядностях экономия ап паратурных затрат на элементы памяти составляет около одной трети. Кроме того, устройство не содержит муль типлексоров, что позволяет не только сократить аппаратурные затраты, но и повысить быстродействие за счет исключения временных .затрат на операцию умножения на 2, реализуемую . мультиплексорами прототипа. В прототипе период тактовых импульсов гдеьмрГ задержка мультиплексора; задержка КСВ, - задержка регистра. В предложенном;, устройствес + При реализации .устройства на серии К155 быстродействие за счет устранения мультиплексоров BOJpacTaeT приблизительно в 1,3 раза. Использование предложенного устройства позволяет повысить быстродействие арифметических устройств, реали- зунщих алгоритмы Волдера (цифра за цифрой) Отношение времени вычислений в известном устройстве ко времени вычислений в предлагаемом устройстве составляет Vn /()уГде Я - разрядность; N- число слов. Например, при обработке 1000 4-разредных слов предложенное устройство работает приблизительно в 4 раза быстрее известного, при обработке 1000 10-разрядных слов - приблизительно в 10 pai3. Устройство может быть использовано в процессорах быстрого йреобразования Фурье, а также для реализации вычисления элементарных функций. За базовый объект принято арифметическое устройство спектроанализатора 8о1аг1гоп 1510 фирмы Schlunberger (БЭС), осуществляющее обра:ботку 1024 10-разрядных слов в реальном масштабе времени в диапазо не частот 0-2,56 кГц. Использование предложенного устройства позволЛ ет производить обработку в 12,9 раз быстрее, что, в свою очередь, позволяет расширить частотный диапазон входных цифровых сигналов до 33 кГц. Экономическая эффективность изобретения заключается в повьш1ении быстродействия.

Фи2.1 to ii t2 is 11111 i 11 i 11 I 111 i 11 I

is iif te

Mill 11 I It I I t I r

x . t

v/ i 111111 I i 1111 M

a y ...УП

AQ/-. 1

..ff i I I M i И « 1 7.2 7 is, i I i I 11 111 111111 I