WikiDer > Фактор Twiddle

А фактор вращения, в быстрое преобразование Фурье (БПФ) любой из тригонометрический постоянные коэффициенты, которые умножаются на данные в процессе работы алгоритма. Этот термин, по-видимому, был введен Джентльманом и Сандэ в 1966 году и с тех пор получил широкое распространение в тысячах статей, посвященных БПФ.

Более конкретно, «факторы вращения» первоначально относились к корень единства сложный мультипликативные константы в бабочка операции Алгоритм Кули – Тьюки БПФ, привыкший рекурсивно объединить меньшие дискретные преобразования Фурье. Это остается наиболее распространенным значением термина, но его также можно использовать для любой независимой от данных мультипликативной константы в БПФ.

В алгоритм БПФ с простым коэффициентом Это один необычный случай, когда БПФ может выполняться без факторов вращения, хотя и только для ограниченных факторизаций размера преобразования.

Например, W₈² - коэффициент скручивания, используемый в 8-точечном БПФ с основанием 2.

Рекомендации

• W. M. Gentleman и G. Sande, "Быстрые преобразования Фурье - для удовольствия и выгоды", Proc. AFIPS 29, 563–578 (1966). Дои:10.1145/1464291.1464352