Бабочка (БПФ)

У этого термина существуют и другие значения, см. Бабочка (значения).

Диаграмма потока данных соединяет входы x (слева) с выходами y (справа) для «бабочки» алгоритма БПФ. Диаграмма напоминает бабочку (на рисунке приводится бабочка Морфо)

БПФ по основанию 2 с прореживанием по времени разбивает ДПФ размерности N на два ДПФ размерности N/2 c последующим объединяющим шагом, состоящим из множественных операций "бабочка".

Бабочка — элементарный шаг в алгоритме быстрого преобразования Фурье Кули-Тюки (Cooley–Tukey FFT (англ.)русск.).

Является двухточечным преобразованием, время работы которого определяет длительность вычисления преобразования Фурье.^[1]

Формула для вычисления "Бабочки":^[1]

$Y_1 = X_1 + X_2 \cdot W$

$Y_2 = X_1 - X_2 \cdot W$

Обозначения: $X_1$, $X_2$ – исходные точки; $Y_1$, $Y_2$ – точки результата, W – комплексный коэффициент.

Для БПФ данных размером $2^k = N$, требуется произвести $N \cdot log_2 N$ вычислений операции "Бабочка".^[1][2]

Примечания

1. ↑ ^{1 2 3} Реализация целочисленного БПФ на процессорах с архитектурой ARM // Схемотехника №3 март 2001
2. ↑ Л. Рабинер и Б. Гоулд "Теория и применение цифровой обработки сигналов".

Ссылки

• Chapter 12: The Fast Fourier Transform (The Scientist and Engineer's Guide to Digital Signal Processing, By Steven W. Smith); перевод

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.