משתמש:Cumulus/ארגז חול FFT

התמרת פורייה מהירה (FFT) היא כינוי לאלגוריתם יעיל המשמש לחישוב התמרת פורייה בזמן בדיד (DFT) וההתמרה ההפוכה לה. התמרות כאלו הן בעלות חשיבות רבה במגוון תחומים של מתמטיקה יישומית החל בעיבוד אותות דיגיטליים וכלה בפתרון משוואות דיפרנציאליות חלקיות וחישוב מהיר של מכפלות בין שלמים גדולים. המאמר מתאר מספר אלגוריתמים. ראה התמרת פורייה למידע אודות התכונות והיישומים של ההתמרה.

יהיו x₀, ...., x_N-1 מספרים מרוכבים אזי התמרת פורייה לאותות בזמן בדיד מוגדרת על ידי:

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{2\pi i \over N}nk}\qquad k=0,\dots ,N-1.$