WikiSort.ru - Не сортированное

Бабочка — элементарный шаг в алгоритме быстрого преобразования Фурье Кули-Тюки (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].

Примечания

Ссылки

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.