Fattore Twiddle - Twiddle factor

Un fattore di twiddle , negli algoritmi di trasformata di Fourier veloce (FFT), è uno qualsiasi dei coefficienti costanti trigonometrici che vengono moltiplicati per i dati nel corso dell'algoritmo. Questo termine è stato apparentemente coniato da Gentleman & Sande nel 1966 e da allora si è diffuso in migliaia di articoli della letteratura FFT.

Più specificamente, i "fattori twiddle" si riferivano originariamente alle costanti moltiplicative complesse radice dell'unità nelle operazioni a farfalla dell'algoritmo FFT di Cooley-Tukey , utilizzato per combinare ricorsivamente trasformate discrete di Fourier più piccole . Questo rimane il significato più comune del termine, ma può anche essere usato per qualsiasi costante moltiplicativa indipendente dai dati in una FFT.

L' algoritmo FFT a fattore primo è un caso insolito in cui una FFT può essere eseguita senza fattori di twiddle, anche se solo per fattorizzazioni ristrette della dimensione della trasformata.

Ad esempio, W ₈ ² è un fattore di rotazione utilizzato nella FFT radix-2 a 8 punti.

Riferimenti

• WM Gentleman e G. Sande, "Fast Fourier trasforma—per divertimento e profitto", Proc. AFIPS 29 , 563-578 (1966). doi : 10.1145/1464291.1464352