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

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

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

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

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

${\displaystyle Y_{1}=X_{1}+X_{2}\cdot W}$

${\displaystyle Y_{2}=X_{1}-X_{2}\cdot W}$

Обозначения: ${\displaystyle X_{1}}$, ${\displaystyle X_{2}}$ – исходные точки; ${\displaystyle Y_{1}}$, ${\displaystyle Y_{2}}$ – точки результата, ${\displaystyle W}$ – комплексный коэффициент.

Для БПФ данных размером ${\displaystyle 2^{k}=N}$, требуется произвести ${\displaystyle N\cdot \log _{2}N}$ вычислений операции 2-Radix «Бабочка».^[1][2][3]

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

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