Czynnik twiddle'a
Współczynnik twiddle w algorytmach szybkiej transformaty Fouriera (FFT) to dowolny ze stałych współczynników trygonometrycznych , które są mnożone przez dane w trakcie algorytmu. Termin ten został najwyraźniej ukuty przez Gentlemana i Sande'a w 1966 roku i od tego czasu rozpowszechnił się w tysiącach artykułów literatury FFT.
Mówiąc dokładniej, „czynniki twiddle” pierwotnie odnosiły się do stałych multiplikatywnych zespolonych pierwiastka jedności w operacjach motylkowych algorytmu Cooley-Tukey FFT , używanych do rekurencyjnego łączenia mniejszych dyskretnych transformat Fouriera . Pozostaje to najbardziej powszechnym znaczeniem tego terminu, ale może być również używane do dowolnej niezależnej od danych stałej multiplikatywnej w FFT.
Algorytm FFT na czynniki pierwsze to jeden niezwykły przypadek, w którym FFT można wykonać bez czynników twiddle, aczkolwiek tylko dla ograniczonych rozkładów na czynniki rozmiaru transformacji.
Na przykład, W 8 2 jest współczynnikiem twiddle używanym w 8-punktowej radix-2 FFT.
- WM Gentleman i G. Sande, „Szybkie transformaty Fouriera - dla zabawy i zysku”, Proc. AFIPS 29 , 563-578 (1966). doi : 10.1145/1464291.1464352