4.5. Алгоритм быстрого преобразования Фурье

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

Если предположить, что в памяти ЭВМ заранее сформирована таблица значений базисных синусоидальных функций а также справедливо соотношение для времени выполнения операций комплексного сложенияи умноженияв виде неравенствато время вычисленияN комплексных коэффициентов ДПФ приближённо оценивается по формуле

. (4.5.1)

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

Предлагаемый алгоритм быстрого преобразования Фурье (БПФ) обеспечивает существенное снижение временных затрат вычисления коэффициентов ДПФ. Однако применение этого алгоритма возможно только для некоторых значений N; здесь будет рассмотрен вариант алгоритма БПФ для – числа наблюдений, равного целой степени двойки. В основе предлагаемого алгоритма БПФ лежит возможность сведения вычисления ДПФ для N чисел к вычислению двух ДПФ для чисел с проведением дополнительных операций умножения.

Рассмотрим снова выражение для вычисления коэффициентов ДПФ; опустим для дальнейших удобств выкладок множитель который можно будет учесть на последнем шаге:

Разобьём последовательность на две подпоследовательности с чётными и нечётными номерами входных данных:

Коэффициенты ДПФ исходной последовательности могут быть записаны в виде двух сумм,

Сформируем указанные суммы в виде ДПФ размерности

Обозначим коэффициенты ДПФ для введённых чётных и нечётных подпоследовательностей:

Запишем, введя множитель первыекоэффициентов ДПФ

Eсли осуществить сдвиг индекса k на то оставшиеся коэффициенты ДПФ исходной последовательности с номерами отдозаписываются аналогично:

Из приведённого рассмотрения следует, что нахождение ДПФ для последовательности из N чисел свелось к вычислению двух ДПФ для двух подпоследовательностей из чисел иопераций комплексных умножений.

Вычисление ДПФ можно реализовать пошагово. На предпоследнем шаге можно осуществить переход к вычислению ДПФ для подпоследовательностей из чисел через ДПФ для подпоследовательностей изчисел и т.д. Общее число шагов подобного алгоритма составляет значение показателя степени двойки

Проанализировав структуру формул алгоритма вычисления ДПФ из N чисел через вычисление ДПФ для подпоследовательностей из чисел, можно заметить, что алгоритм распадается на последовательность однотипных подалгоритмов. Действительно, выделим типовой подалгоритм

(4.5.2)

Указанный подалгоритм называется «бабочка»; граф «бабочки» – схематическое изображение вычислительных операций, соответствующих (4.5.2) представлен на рис. 4.5.1.

Рис. 4.5.1. Граф операции «бабочка»

Комбинации однотипных «бабочек» при вычислении коэффициентов ДПФ составляет основу алгоритма БПФ. На рис. 4.5.2 представлен в качестве примера граф алгоритма БПФ для состоящий из трёх шагов.

Рис. 4.5.2. Граф алгоритма БПФ для

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

Чтобы предлагаемый алгоритм БПФ начал работать, необходима всего лишь предварительная перетасовка входных данных во временной области. Работу алгоритма перетасовки, в соответствии с разработанным графом рис. 4.5.2, удобно анализировать с правого конца (от конца к началу), что приллюстрировано на диаграмме рис. 4.5.3.

Оценим временные затраты, необходимые для работы алгоритма БПФ. На каждом шаге алгоритма БПФ выполняется операций «бабочка»; в каждой «бабочке» реализуется только одно комплексное умножение, поэтому временные затраты на каждом шаге предлагаемого алгоритма приближённо составляют величинуЧисло шагов в алгоритме БПФ уже было подсчитано ранее; поэтому время вычисленияN коэффициентов дискретного преобразования Фурье по предлагаемому алгоритму БПФ представится следующей оценкой

(4.5.3)

Рис. 4.5.3. Перетасовка входных данных для алгоритма БПФ с

Определим возможный выигрыш во времени по предлагаемому алгоритму БПФ по сравнению с вычислением ДПФ на основе формул (4.5.1) и (4.5.3):

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

Список вопросов для самопроверки к гл. 4

1. В чём состоит формулировка задачи аппроксимации дискретных наблюдений сигналов полигармоническими моделями и каковы особенности её решения?

2. В чём состоят особенности задачи аппроксимации дискретных наблюдений сигналов на основе моделей, линейных по части параметров?

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

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

5. В чём состоит алгоритм вычисления дискретного преобразования Фурье для комплексной синусоиды?

6. В чём состоит определение для разрешающей способности ДПФ?

7. Какие свойства дискретного преобразования Фурье приведены в разд. 4.2?

8. В чём заключается формулировка теоремы Парсеваля для случая непрерывных сигналов?

9. Каким образом реализуется вывод теоремы Парсеваля для случая дискретных сигналов?

10. В чём состоит определение для функции спектральной плотности мощности сигналов (СПМ)?

11. Каким образом реализуется вывод оценки функции СПМ для стационарных эргодических дискретных сигналов?

12. Для каких целей применяются временные окна?

13. Каким образом реализуется алгоритм вычисления оценок параметров сигналов на основе функции СПМ?

14. Каким образом определяется функция взаимной спектральной плотности мощности сигналов (ВСПМ)?

15. Каким образом реализуется алгоритм вычисления оценок разностей фаз на основе функции ВСПМ?

16. Каким образом реализуется алгоритм вычисления оценок передаточных функций линейных систем на основе функции ВСПМ?

17. Каким образом реализуется алгоритм вычисления оценок функции когерентности на основе функций СПМ и ВСПМ?

18. Каким образом реализуется алгоритм быстрого преобразования Фурье (БПФ)?

Список задач к гл. 4

1. Вычислить коэффициенты ДПФ если

для заданных временных дискретных последовательностей:

1)

2)

3)

4)

5)

6)

7)

8)

9. ,

10)

11)

12)

13)

14)

15)

2. Определить характеристики разрешения составляющих двухчастотного сигнала на основе ДПФ

1. Разрешимы ли составляющие сигнала с параметрами:

2. Разрешимы ли составляющие сигнала с параметрами:

3. Для параметров сигнала: какое необходимо задатьN для обеспечения разрешения составляющих?

4. Для параметров сигнала: какой необходимо задать интервал наблюденияNT для обеспечения разрешения составляющих?

5. Для параметров cигнала: и интервала наблюдениякакое минимальное значение частотыможет обеспечить разрешение составляющих?

170