ДПФ в вещественной и комплексной формах.

⇐ ПредыдущаяСтр 5 из 6Следующая ⇒

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

,	(2.30)
,	(2.31)

Последние формулы получаются из (2.16) - (2.20). Имеем:

Вводя комплексные амплитуды для и соотношениями

, , получим

(2.32)

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

.
Используя периодичность спектра , можно в (2.32) сменить пределы суммирования и получить (2.31). Выражение (2.30) следует из (2.17) – (2.20), т.к. .
Из (2.31) и (2.32) следует, что для ДПФ в комплексной форме достаточно одной программы, т.к. прямое и обратное ДПФ различаются лишь знаком в экспоненте и множителем , а не видом формул.

Количество операций в ДПФ.

Оценим количество операций по (2.31). Операцией будем считать умножение на комплексную экспоненту, т.е. . Операции здесь очень сложные, т.к. вычисляется через , , а , через полиномы.
Имеем слагаемых для вычисления одной гармоники по (2.31) и поэтому для вычисления одной гармоники нужно операций. Так как всего вычисляется гармоник , то прямое ДПФ требует примерно операций, т.е. сложность алгоритма ДПФ . Это означает, что при увеличении в 10 раз, количество операций увеличится в 100 раз.

БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ (БПФ)

Понятие о БПФ

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

Основу БПФ составляют 4 идеи:

1. Спектр ДПФ – периодический, .
2. Спектр ДПФ легко вычисляется в случае , когда имеется только одна гармоника и по (14.7)
3. Выбирается , где – целая степень, т.е. количество отсчетов не может быть произвольным целым числом. Например, при имеем .
4. Спектр исходной последовательности несложно найти по спектрам расщепленных последовательностей. При каждом расщеплении от одного массива из отсчетов переходят к двум массивам из отсчетов каждый.

Вычисление спектра объединенной последовательности по спектрам расщепленных.

Пусть на периоде T имеем два сигнала и , , каждый из которых содержит N/2 точек и имеет безразмерный шаг дискретизации . Из этих двух сигналов, объединяя их в виде “гребенки”, получаем объединенную последовательность , , состоящую из отсчетов. При таком объединении для четных при имеем , для нечетных при имеем . Например, , , , и т.д. Для объединенного сигнала получается шаг .

Рассматриваемые сигналы даны на рисунке 2.6

Рис. 2.6 Две расщепленных и объединенная последовательности отсчетов.

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

	(2.33)
	(2.34)
	(2.35)

Здесь суммы по вычисляются по точкам и по этому появляются множители 2 перед суммой и в показателе степени. Количество гармоник в (2.33 – 2.34) равно , а в (2.35) оно равно . Покажем, как спектр можно вычислить по спектрам и :

(2.36)

т.е. , .

При выводе вместо отсчетов с четными номерами подставлены значения , а вместо отсчетов c нечетными номерами – значения . Формулу (2.36) можно применять для , т.к. спектры и содержат гармоник. Но учитывая их периодичность: , а также равенство , получаем для гармоник с номерами

(2.37)

Формулы (2.36-2.37) составляют суть алгоритма “бабочка”, т.к. для его иллюстрации используют рисунок, похожий на бабочку.

Рис.2.7 Иллюстрация к алгоритму “бабочка”.

Алгоритм БПФ

Дан массив из отсчетов сигнала, причем .

1. Расщепляем его многократно на четные и нечетные последовательности до получения последовательностей из одного отсчета в каждой, см. рис 13.3.

Рис.2.8 Расщепление последовательностей.

На рис. 2.8 значение дает количество отсчетов в каждой из расщепленных последовательностей. Всего уровней расщепления , т.е. расщепляем раз. Будем считать, что – это новый массив точек. В нем порядок следования точек отличен от исходного, т.е. , где , а индекс вычисляется по .
Оказывается, что преобразование дает обратный битовый порядок, например, .
Для получаем следующее преобразования индексов:

Столь простое преобразование можно не учитывать при оценках времени работы алгоритма.

2. Так как при , т.е. при одном отсчете на периоде, спектр равен самому отсчету, то на последнем уровне расщепления ( ) спектры всех последовательностей известны. Всего имеем спектров, каждый из которых состоит только из нулевой гармоники ( ), т.е. среднее значение.

3. Объединение последовательностей, т.е. обратный ход.
При каждом объединении используются формулы для вычисления спектра (13.4-13.5). Вычисления завершаются после получения спектра из гармоник для исходной последовательности уровня .

⇐ Предыдущая 1 2 3 456 Следующая ⇒