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

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

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

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

${\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 «Бабочка».

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

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

Примечания

Ссылки

• (The Scientist and Engineer's Guide to Digital Signal Processing, By Steven W. Smith);