Бабочка (БПФ)
Бабочка — элементарный шаг в алгоритме Кули-Тюки (англ. Cooley–Tukey FFT) вычисления быстрого преобразования Фурье.
Время работы шага Бабочка определяет длительность вычисления преобразования Фурье.[1]
В простейшем варианте (Radix-2 butterfly) является двухточечным преобразованием.
Формула для вычисления «Бабочки»:[1]
Обозначения: , – исходные точки; , – точки результата, – комплексный коэффициент.
Для БПФ данных размером , требуется произвести вычислений операции 2-Radix «Бабочка».[1][2][3]
Иногда используются операции бабочка более высокого порядка: Radix-4, Radix-8. Radix-4 является примерно на 20% более эффективным для преобразования Фурье большого количества данных. Операция большего порядка чем 8 практически не используется из-за незначительных приростов производительности и трудностей в реализации (ресурсоемкости).[4][5]
Сходная структура может применяться в реализациях алгоритма Витерби (операция ACS - Add-Compare-Select)[6].
Примечания
Ссылки
- Chapter 12: The Fast Fourier Transform (The Scientist and Engineer's Guide to Digital Signal Processing, By Steven W. Smith); перевод