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

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

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

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

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

В простейшем варианте (Radix-2 butterfly) является двухточечным преобразованием.

Формула для вычисления «Бабочки»:

$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$ вычислений операции 2-Radix «Бабочка».

Иногда используются операции бабочка более высокого порядка: Radix-4, Radix-8. Radix-4 является примерно на 20% более эффективным для преобразования Фурье большого количества данных. Операция большего порядка чем 8 практически не используется из-за незначительных приростов производительности и трудностей в реализации (ресурсоемкости).

Сходная структура может применяться в реализациях алгоритма Витерби (операция ACS - Add-Compare-Select).

Ссылки

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