Устройство для быстрого действительного преобразования Фурье Советский патент 1989 года по МПК G06F15/332 

1

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

отсчетов входного сигнала в частотную последовательность.

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

На фиг. 1 показана структурная схема устройства; на фиг. 2 - граф

алгоритма быстрого преобразования Фурье (БПФ), реализованный в устройстве; на фиг. 3 - временные диаграммы работы устройства.

Устройство содержит синхронизатор 1, счетчик 2 адреса блок 3 постоянной памяти, счетчик 4 адреса, входной регистр 5, регистр 6, входной регистр 7, блок 8 памяти, умножитель 9, первый 10 и второй 11 мультиплексоры, первый 12 и второй 13 сумматоры,тре- 1 тий мультиплексор 14, информационные I вход 15 и выход 16.

( Граф алгоритма БПФ (фиг. 2) приве- 1 ден для исходного, массива длиной в ; 16 значений. На фиг. 2 обозначены

входная последовательность 17, выход- ; ная последовательность 18 коэффици- еитов Фурье, операции 19, применяе- 1 мые в алгоритме.

Рассмотрим работу устройства,Вы- i полнение БПФ в нем включает три эта- I па: вход исходной информации, вычис- 1 ление коэффициентов Фурье и вывод результатов преобразования.

На этапе ввода используются тольк синхронизатор 1, счетчик 4, блок 8 памяти и мультиплексор 14, По сигналам синхронизатора 1 счетчик 4 адреса формирует и передает на блок 8 памяти последовательность адресов, по которым в него записывается исходная информация, поступающая через мультиплексор 14 с входа 15,

Этап вычисления коэффициентов Фурье включает несколько шагов, На первом шаге в соответствии с алгоритмом выполняются операции сложения и вычитания отсчетов. Синхронизатор 1 .передает в счетчик 4 сигнал, по кото рому в последнем формируется и передается на блок 8 памяти код адреса первого операнда, представляющего собой некоторый i-й входной отсчет (i 0, 1,..,, N/2 - 1). Считанный из блока 8 памяти операнд фиксируется в первом входном регистре 5, С выхода последнего цифровой код поступает на входы первого 12 и второго 13 сумматоров. На счетчике 4 по сигналу синхронизатора 1 формируется код адреса второго операнда, являющегося (i + N/2)-M входным отсчетом С выхода блока 8 оперативной памяти значение операнда поступает на входной регистр 7 и фиксируется в нем. Отсюда цифровой код попадает на вход мультиплексоров 10 и 11. На управляющие входы последних с синхронизатора

10

15

25

40

23544

1 поступает сигнал, вызывающий передачу этой информации на входы первого 12 и второго 13 сумматоров. Сумматор 12 осуществляет сложение операндов, поступающих на его входы, а сумматор 13 - вычитание второго операнда из первого, С выходов сумматоров 12 и 13 результаты поступают соответственно на входы мультиплексора 14, По сигналам с синхронизатора 1 эти данные последовательно передаются в блок 8 памяти и фиксируются по адресам операндов, считанных из него в начале выполнения шага. Аналогичным путем происходит обработка остальных пар отсчетов на первом шаге алгоритма.

Выполнение второго шага включает только операции сложения-вычитания 20 и происходит в целом подобно первому шагу. Однако в данном случае иными являются коды адресов, задаваемые по командам синхронизатора 1 из счетчика 4 в блок 8 памяти (в данном случае из блока 8 памяти в соответствии с алгоритмом, так же, как и на предыдущем шаге, выбираются такие пары операндов, над которыми надо производить операций сложения и вычитания). Кроме того, на данном шаге присутствуют операнды, над которыми не требуется производить какие-либо преобразования (с номерами N/2 и 3N/4). Эти отсчеты не считываются из блока 35 8 и не подвергаются обработке.

30

0

Третий и последующий шаги алгоритма содержат операции не только ело- жения-вычитания, но и умножения на тригонометрические весовые коэффициенты. Третий шаг включают два под- шага. Выполнение первого из них, содержащего только операции сложения- вычитания, в целом подобно отработке 5 первого и второго шага преобразования. Функционирование устройства на втором подшаге происходит следующим образом. По сигналам с синхронизатора 1 счетчик 4 последовательно фо.рмирует коды ад15есов, по которым из блока 8 памяти считывается очередная пара операндов, которая записывается во входные регистры 5 и 7 (считываемые операнды А и В выбираются такими, над которыми должна быть выполнена пара операций вида А+СВ и А-СВ, где С - весовой коэффициент; для представленного на фиг, 2 алгоритма при N 16 это отсчеты с но0

5

мерами 8 и 10, 9 и 11,12 и 1А, 13 и 15). Одновременно по сигналу из синхронизатора счетчик 2 адреса формирует и передает на блок 3 постоянной памяти код адреса, по которому из него считьгеается и фиксируется в регистре 6 значение соответствующего весового коэффициента (в том случае, когда по алгоритму требуется умножение на удвоенный весовой коэффициент, такое удвоенное значение и хранится в блоке 3 постоянной памяти). С выхода регистра 6 код коэффициента передается на вход первого сомножителя умножителя 9, на вход второго сомножителя которого с выхода регистра 7 поступает значение второго операнда. Результаты умножения через мультиПоследующие шаги вплоть До (n-l)-ro подобны третьему шагу алгоритма и выполняются в целом аналогично описанному (но с другими значениями весовых коэффициентов и операндов).

10

15

Последний, п-й шаг алгоритма содержит операции сложения-вычитания и сложения-вычитания с умножением. Первые выполняются аналогично отработке таких операций на первом шаге, а вторые - на третьем шаге. После окончания п-го шага преобразования, являющегося последним на этапе вычисления коэффициентов Фурье в блоке 8 оперативной памяти получают набор искомых значений, порядок следования которых отличается от нор|Г СЗУЛО1 ею у .f - J

плексоры 10 и 11, управляемые синхро-20 мального вследствие специфики алгонизатором 1, поступают на вторые входы сумматоров 12 и 13, на первые входы которых подается код операнда с выхода первого входного регистра 5. В сумматоре 12 происходит сложение, а в сумматоре 13 - вычитание операндов. Результаты из сумматоров 12 и 13 через мультиплексор t4 передаются в блок 8 оперативной памяти и фиксируются в нем. Аналогично выполняется обработка и остальных пар операндов. На этом заканчивается отработка устройства третьего шага алгоритма.

ритма,

Вьщача результатов и восстановление требуемого порядка следования

25 выходных отсчетов осуществляются на этапе вывода. Здесь счетчик по сигналам с синхронизатора 1 формирует коды адресов в порядке, обеспечивающем считывание из блока 8 и вьщачу

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

N/2

1

.

Последующие шаги вплоть До (n-l)-ro подобны третьему шагу алгоритма и выполняются в целом аналогично описанному (но с другими значениями весовых коэффициентов и операндов).

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

мального вследствие специфики алгоритма,

Вьщача результатов и восстановление требуемого порядка следования

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

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

N/2

1

.

ы т- Г т

L efflJL&.st.JL€..---J«-C ««J «

«te.;

«J