Устройство для преобразованияфуРьЕ Советский патент 1981 года по МПК G06F17/10 G06F17/14 

вертого сумматоров соединены со входами соответствующих сумматоров-вычитателейВ этом устройстве четыре одновремениых действия умножения выполняются с помощью трех множительных блоков. Такая экономия достигается в результате представления тригонометрических коэффициентов в виде отдельных cos 0 и sin в, а их суммы и разности -(т. е. не в виде ReW и/mir, а в виде ReW- -linW и .

Устройство это имеет асинхронное быстродействие.

Это устройство громоздко и имеет следуюид;ие недостатки;

1)Малый коэффициент использования операционных узлов, входящих в устройство, так как полные программы вычисления функций (спектр мощности, корреляционная функция свертка и т. д.) предусматривают, помимо базовой операции алгоритма БПФ, выполнение таких программ, как сглаживание но Хэммингу, требующее двух суммирующих блоков, разделение вещественных спектров, требующее двух сумматоров-вычитателей, перемножение двух комплексных чисел с сопряжением одного нз чисел (или возведение в квадрат одного комплексного числа), требующее двух множительных блоков, одного сумматора и одноге сумматора-вычитателя.

2)Требует обращения числового ряда (после перемножения комплексов) для выполнения обратного БПФ (ОБПФ) при вычислении корреляционной функции. Т. е. преобразуемый числовой ряд, начиная

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

3)Быстродействие устройства избыточно при работе с двумя двухмодульными ОЗУ по стандартной схеме: ОЗУ в режиме считывания устройства для в режиме записи.

Цель изобретения - упрощение устройства.

Эта цель достигается тем, что в устройство, содержащее два сумматора-вычитателя, сумматор, два блока умнолсеиия, четыре регистра, причем, первые входы первого и второго блоков умножения являются соответственно первым и вторым входами задания коэффициентов устройства, а суммирующий и вычнтаюпхий выходы первого сумматора-вычнтателя подключены ко входам соответственно первого н второго регистров, оно содержит два управляемых инвертора знака, входы которых являются входами знака соответственно вещественной и мнимой частей устройства. Управляющие входы управляемых инверторов знака являются управляющими входами устройства. Выходы управляемых инверторов знака соединены соответственно с первым и вторым входами второго сумматора-вычитателя, третий и четвертый входы которого являготся соответственно входами вещественной и мнимой частей первого числа устройства. Суммирую1ций и вычитающий выходы второго сумматора-вычитателя соединены со вторыми входами соответственио нервого и второго блоков умножения, выходы которых соединены соответственно со входами сумматора, выход которого подключен к первому входу первого сумматора-вычитателя, второй вход которого является входом второго числа устройства, а управляющий вход сумматора является входом задания режима устройства. Вход третьего регистра объедииен со входом первого регистра, а вход четвертого регистра - со входом второго регистра. Тактовые входы регистров являются входами синхронизации устройства.

При этом количество оборудования сокращается на четыре операционных блока (почти вдвое). Кроме того, устройство получается функционально гибче н совершеннее прототипа. Папример, обратное БПФ выполняется с помощью того же оборудования, что и прямое БПФ н в отлнчие от нзвестиых рещений - без дополнительных затрат времени, а коэффициент использования операционных блоков в устройстве возрастает более, чем в 3 раза.

Схема предлагаемого зстройства на фиг. 1, где обозначены блоки 1, 2 умножения, входы 3, 4 задания коэффициентов, сумматор 5, сумматоры-вычитатели б, 7, регистры 8-И, выход 12 суммы сумматоравычитателя 7, выход 13 разности сумматора-вычитателя 7, управляемые 14, 15 инверторы знака, шииы 16, 17 управления инверторами 14, 15 (управляющие входы устройства), знаковая шина 18, и шины 19 вещественной части соответственно первого комплексного числа, щины 20 мнимой части и знаковая 21 шина соответственно первого комплексного числа, шина задания режима 22, шина второго комплексного числа 23 и шины синхронизации 24-27.

Устройство работает следующим образом.

Базовая операция алгоритма выполняется (как и в прототипе) за время основного тактового импульса. Значение времени такта определяется временем считывания операнда из ОЗУ. Время срабатывания АУ в два с лишним раза меньще времени основного такта. Поэтому для АУ такт представлен двумя полутактовыми нмпульсами.

При выполнении прямого БПФ в течение первого полутакта па входы сумматора-вычитателя 6 поступает первое комплексное число (KeBi+IinBi ) с прямыми знаками своих вещественной и мнимой частей. Модуль вещественной части Re В j подается на шины 19, знак вещественной части следует по шине 18, к шинам 20 и 21 подключены соответственно модуль 1т В i и знак мнимой части. На шипу 3 подается тригонометрический множитель (ReWi + + ImWI ), на шину 4 - тригонометрический множитель (ReWi - 1т W i ), на шину задания 22 режима подается сигнал задания режима суммирования сумматору 5 (нулевой потепциал). По шине 23 второго комплексного числа (ReAi + ImAi ) поступает его вещественная часть ReAi. На шины синхронизации 24 и 25 подается сигнал разрешения записи информации п регистры 8 и 9. На шинах 26 и 27 при этом существует сигнал запрета. В результате имеем на суммирующем выходе сумматора 6 (этот выход иодключеи ко второму входу блока умножения: (ReBi +ImBi) на вычитающем выходе блока 6 (подключен ко второму входу блока 2) - (Re Bf-

-ImBi }. На выходе блока 1 имеем (ReWi+ ImWi) X (ReBf -f/mBj),Ha выходе блока 2 - (ReW. - lmWi (

-JmBi), на выходе сумматора 5-2 (ReWiReBi+ ImWi /mB; ), т. e. сумму этих произведений. Выражение в скобках есть правая часть выражения (3). Полученный результат подается на второй вход сумматора-вычнтателя 7 со сдвигом вправо на один двоичный разряд, т. е. в виде (ReWi ReВ +JmWi ImBi } Так как на его первом входе существует ReAr,

то на суммирующем выходе получим ReAi + на вычитающем (ReBi -f 1) в соответствии с выражениями (1) и (2). Эти числа запишутся в регистры 8 и 9 соответственно.

В течение второго полутакта на входы сумматора-вычитателя 6 по-прежнему подается первое комплексное число с прямым знаком мнимой части, но с инверсным знаком вещественной части. На шину задания 22 режима подается сигнал задания режима вычитания сумматору 5 (единичный потенциал), а на шину 23 иоступает мнимая часть /тЛ, второго комилексного числа. В результате имеем на суммирующем выходе сумматора 6 (-ReBi-i- ImBi ), на вычитающем выходе сумматора 6 (-ReB/-/тВ; ), на выходе блока 1 - (ReWi+ ImWi) (-ReBi + В; ),на выходе блока 2.

- (ReWi - (-ReBi-ImBi ), на выходе сумматора 5 - разность этих двух произведений

(ReWi + ImWi ) (-ReBi + ImBj } - (ReW, - ImWi) (-ReB.- ImBi (ReWiImBi - ImWiR-eBi),

Выражение в скобках есть иравая часть выражения (4). Полученный результат подается па второй вход сумматора-вычитателя 7 со сдвигом вираво на один двоичный разряд, т. е- в виде (ReWi/mB - - ImW/ReBf ). Так как на его первом входе существует ImAi, то на суммирующем выходе получим 1тА, а на вычитающем - (ImBi+ 1) в соответствии с выражениями (1) и (2). Эти числа запишутся в регистры 10 и 11 соответственно, так как на втором полутакте на шины синхронизации 26 и 27 подается сигиал разрешения записи информации, а на шинах 24 и 25 в это время суи1,ествует заирет.

При выполнении обратного БПФ в течение первого полутакта иа входы сумматора-вычитателя 6 поступает первое комплексное число с прямым знаком веи;ественной части и инверсным знаком мнимой части, а в течение второго полутакта обе части комплексного числа проходят иа входы сумматора-вычитателя 6 с прямыми зпаками. Все остальное идентично прямому БПФ. В этом случае после первого полутакта иа выходе сумматора 5 имеем 2(ReWiReBi - ImWilmBi), а после второго полутакта - 2 (ReWi ImB- + -rlmWiReBi ). Выражения в скобках есть соответственно вещественная и мнимая части произведения первого комплексного

числа В{ на комплексный тригонометрический сомножитель Wt с положительным показателем степени. Таким образом, для выполнения обратного БПФ не требуется обращать числовой ряд исходных чисел. Поэтому предложенное устройство обладает принципиальным преимуществом перед прототипом: обратное БПФ выполняется тем же оборудованием и без дополнительных затрат времени.

На фиг. 2 показана схема управляемого инвентора 15 знака (инвенторы 14 и 15 идентичны) собранного на элементах И-НБ 28-32 (Шеффера). Знаковая шина 21 является входной, и иа нее подается потенциал знака чисел- Если на шину 17 уиравленпя подан «нуль, то элемент 31 закрыт, а элемент 29 открыт через элемент 30. Потенциал знака дважды инвертируется проходя по цепи: шина 21, элемент 29, элемент 32, выход, поэтому значение его не меняется, т. е. инвертор 15 пропускает прямой знак. Если же на шину 17 управления подана «единица, то запирается элемент 29 и отпирается элемент 31, потенциал знака следует по цепи: шина 21, элемент 28, элемент 31, элемент 32, выход, т. е. в итоге он инвертируется.

Предложенное устройство работает как и прототип в паре с двумя ОЗУ (каждое ОЗУ двухмодульное). Схема их объединения в систему показана на фиг. 3. Первое

ОЗУ 33 в течение всей итерации иаходится в режиме считывания. Устройство 34 для БПФ обрабатывает поступающие на его

:

ВХОД пары операндов Л; и S и передает

результаты обработки: Ai.L и на запись в ОЗУ 35, находящемся в течение всего времени итерации в режиме занесения. Режимы ОЗУ задаются по щинам управления 36 и 37. При смене итерации БПФ цикла ОЗУ 33 и 35 работают в противоположных режима.х.

Сравнительные диаграммы работы прототипа и предложенного устройства показаны соответственно на фиг. 4 и фиг. 5.

Время Tg.o базовой операции для прототипа, если включать сюда время Тсч считывания время Тпр преобразования и время Тзап записи, составляет 2,5 мкс (для определенности считаем Тсч Тзап 2тпр 1 мкс). Но при этом начала базовых операций отстоят на временной осп друг от друга на 1 мкс. Например, для первых трех базовых операций (фиг. 4а, б, е) это моменты времени, t, t}.., ts, т. е. поток пар операндов следует с частотой 1 мгц, что и определяется частотой ОЗУ (фиг. 4, г). Но при этом устройство для БПФ - прототип участвует в работе половину всего времени цикла. На фиг. 4, д видно, что работает оно например, от t до /2, а от 2 ДО 3 бездействует. Затем от t до t4 работает и от t до t вновь бездействует и т. д.

При использовании предложенного устройства время базовой операции соответственно составляет 3 мкс. Начала базовых операций отстоят друг от друга также на 1 мкс. Например, для первых трех базовых операций (фиг. 5, а, ж, з) это моменты времени to, ti, ts, как и у прототипа. Т. е. поток пар операндов следует с той же частотой 1 МГЦ, определяемой частотой ОЗУ (фиг. 5, и) и как видно по эпюре на фиг. 5 к предложенное устройство работает безостановочно, что повышает коэффициент использования оборудования вдвое, т. е. в общей сложности более, чем в 6 раз.

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

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

два управляемых инвертора знака, входы которых являются входами знака соответственно веп1ественной и миимой частеС: устройства, а управляюп;ие входы управляемых инверторов знака являются управляющими входами устройства, выходы управляемых инверторов знака соедппены соответственно с первым п вторым входами второго сумматора-вычитателя, третий и четвертый входы которого являются соответственно входами веществеппой и мнимой частей первого числа устройства, суммирующий и вычитаюпцгй выходы второго сумматора-вычптателя соединены со вторыми входами соответственно первого и

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

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

1- Авторское свидетельство СССР № 480079 кл. G 06 F 15/34, 1975.

2.Авторское свидетельство СССР 421994, кл. G 06 F 15/34, 1974.

3.Беидат Д. Ж., Пирсон Л. Измерение и анализ случайных процессов. М., «Мир,

1974 (прототип).

iS

3S

Фиг. 2

ФигЗ

fjg

P-f/v . Ц

Фа г4

Tso

ГЧ:КИКУр/ /7

I I

и TI,Щрг г1ЩщЩЩ

ts и ts ts

t7 Фиг.5