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

Пусть ДПФ принимает вид

Представим данную сумму произведений, как две суммы: одна для чётных n, другая для нечётных n:

Заменяя индексы суммирования на n=2r – для четных и n=2r+1 – для нечетных n, получим

Заметим, что

Тогда

Следовательно,

Отметим, что для всех соответствующие коэффициенты Фурье X₁ (k), X₂ (k) получаются путём их периодического продолжения.

В соответствии с выражением (2.45) для вычисления N -точечного ДПФ требуется операций.

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

Рассмотрим граф преобразования (2.45) для размерности N =8 (рис. 2.39).

Рис. 2.39. Графическое отображение алгоритма (2.45) и варианты выполнения операции “бабочка”.

Слева представлено графическое отображение алгоритма, справа – варианты выполнения операции «бабочка».

Представленный граф наглядно отображает алгоритм вычислений, при котором для вычисления N -точечного ДПФ необходимо log₂N итераций, каждая из которых требует N/2 операций «бабочка».

Поскольку каждая операция «бабочка» в представленном виде требует две операции умножения, то общее число операций будет N*log₂N. Оценим эффективность алгоритма БПФ как отношение числа операций обычного ДПФ к числу операций заданного алгоритма.

Можно показать, что имеет место следующая связь между комплексными коэффициентами операции «бабочка»

Это позволяет сократить число операций в 2 раза, т.о.

2.4.5. Быстрая свёртка на основе алгоритма БПФ

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

Алгоритм двойного преобразования Фурье для вычисления быстрой свёртки включает в себя следующие операции:

1. Секционирование входной последовательности x (n)

2. Прямое ДПФ

3. Перемножение дискретных спектров

4. Обратное ДПФ

5. Сохранение в памяти правильно вычисленных отсчётов

Оценим затраты и вычислительную эффективность:

Рис. 2.40. Графическая иллюстрация алгоритма секционирования.

Алгоритм двойного преобразования относится к блочным алгоритмам обработки, т.е. вычисляется одновременно N отсчётов сигнала (рис. 2.40). Это требует увеличения памяти данных и приводит к дополнительной задержке как минимум на длину импульсной характеристики.

Дата добавления: 2014-01-04