ДПФ в вещественной и комплексной формах.
В предшествующих разделах использованы вещественные коэффициенты
,
,
,
. Для математических преобразований удобнее вместо 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 перед суммой и в показателе степени. Количество гармоник в (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). Вычисления завершаются после получения спектра
из
гармоник для исходной последовательности уровня
.
Популярное: