התמרת פורייה מהירה

התמרת פורייה מהירה (באנגלית: Fast Fourier Transform; בראשי תיבות: FFT) היא אלגוריתם יעיל לחישוב התמרת פורייה בדידה (Discrete Fourier Transform (DFT וההתמרה ההופכית שלה. יש מספר רב של אלגוריתמי FFT הכוללים טווח רחב של ענפים במתמטיקה מאריתמטיקה של מספרים מרוכבים לתורת החבורות ותורת המספרים. ערך זה סוקר את הטכניקות וחלק מתכונותיהן הכלליות.

באופן בסיסי יותר: ניתן לייצג פולינומים באמצעות מקדמים או באמצעות שורשים (המשפט היסודי של אלגברה) - ערכי הפולינום בנקודות, כלומר בשביל לייצג קו ישר (פולינום מדרגה 2) נדרשות שתי נקודות להגדרה חד חד ערכית שלו, לפולינום מדרגיה שניה שלוש וכך הלאה. ייתרון ייצוג באמצעות שורשים הוא הקלות שבה ניתן לבצע כפל פולינומים בצורה יעילה:

עבור ייצוג באמצעות מקדמים נדרשים n^2 פעולות בשביל לבצע את פעולת הכפל.
עבור ייצוג באמצעות שורשים נדרש לבצע הכפלה של כל נק' מפולינום A לפולינום B ולכן מדובר בפועלה לינארית.

FFT מבצע ביעילות את המעבר בין ייצוג פולינום באמצעות מקדמים, לייצוג באמצעות שורשים, מבצע את הכפל בין החלקים ולאחר מכן חוזר לייצוג באמצעות מקדמים באמצעות inverse FFT בשביל להחזיר את התשובה.

DFT ממיר סדרה של ערכים לרכיבים של תדירויות שונות. פעולה זו שימושית בתחומים רבים, אך חישוב ישיר של ההתמרה לפי ההגדרה שלה הוא פעמים רבות איטי מכדי להיות פרקטי. FFT היא שיטה לחשב את אותה תוצאה באופן מהיר יותר. חישוב DFT של N נקודות באופן נאיבי על פי ההגדרה הוא בעל סיבוכיות של $O(N^{2})$ , בעוד של-FFT סיבוכיות $O(N\cdot \log {N})$ . ההבדל במהירות עשוי להיות משמעותי, במיוחד עבור סדרות ארוכות בהן $N$ עשוי להיות סדר גודל של אלפים או מיליונים. זמן החישוב יכול להיות מופחת בכמה סדרי גודל במקרים אלו, והשיפור הוא פרופורציונלי ל- $N/\log {N}$ . שיפור עצום זה הפך אלגוריתמים רבים מבוססי DFT להיות פרקטיים. FFT הם בעלי חשיבות רבה למגוון רחב של אפליקציות החל מעיבוד אותות ספרתי ופתרון משוואות דיפרנציאליות חלקיות לאלגוריתמים למכפלה מהירה של מספרים טבעיים גדולים.

אלגוריתמי FFT הידועים ביותר מבוססים על פקטוריזציה של $N$ , אך ישנם אלגוריתמי FFT בעלי סיבוכיות של $O(N\cdot \log {N})$ לכל $N$ , אפילו עבור $N$ ראשוני.

בנוסף, ניתן להראות באמצעות אלגוריתם ה-FFT אלגוריתם להכפלה של פולינומים מדרגות n ו-m כאשר n>m בסיבוכיות של $O(n\cdot \log {m})$ , אלגוריתם זה שימושי במיוחד במדעי המחשב.

אלגוריתם "radix-2"

התמרת פורייה בדידה מוגדרת כך:

X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}

כאשר k הוא בין $0$ ל- $N-1$ . אלגוריתם FFT נפוץ הוא radix-2 המבצע את החישוב בנפרד על האינדקסים הזוגיים, $x_{2m}\$ ( $x_{0},x_{2},\ldots ,x_{N-2}$ ), והאינדקסים האי-זוגיים $x_{2m+1}\$ ( $x_{1},x_{3},\ldots ,x_{N-1}$ ), ולבסוף משלב את תוצאות החישוב יחד. בצורה זו פועל האלגוריתם באופן רקורסיבי ומתבצע בסיבוכיות $O(N\cdot \log {N})$ . צורת הצגה זו מניחה כי N הוא חזקה של 2.

בשיטה זו מארגנים מחדש את המשוואה לשני חלקים: סכום על האיברים עם האינדקסים הזוגיים $n={2m}$ , וסכום על האיברים האי זוגיים $n={2m+1}$ :

X_{k}=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N}}(2m)k}+\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N}}(2m+1)k}

{\begin{matrix}X_{k}=\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;even-indexed\;part\;of\;} x_{m}}{}+e^{-{\frac {2\pi i}{N}}k}\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;odd-indexed\;part\;of\;} x_{m}}=E_{k}+e^{-{\frac {2\pi i}{N}}k}O_{k}.\end{matrix}}

כעת הסכימה נעשית על N/2 איברים בלבד: הודות לתכונות המחזוריות של DFT, תוצאות $N/2\leq k<N$ מ-DFT באורך N/2 זהות לתוצאות עבור $0\leq k<N/2$ . ניתן להמשיך כך עד להגעה לחזקה ראשונה של שתיים. בהתאם ניתן לחשב את ה-DFT בצורה הבאה: