Фактор вращения

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

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

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

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

Ссылки

• В.М. Джентльмен и Г. Санде, «Быстрые преобразования Фурье — для развлечения и прибыли», Proc. AFIPS 29 , 563–578 (1966). дои : 10.1145/1464291.1464352