התמרת פורייה מהירה
אלגוריתם למימוש התמרת פורייה בדידה / ויקיפדיה האנציקלופדיה encyclopedia
התמרת פורייה מהירה (באנגלית: Fast Fourier Transform; בראשי תיבות: FFT) היא אלגוריתם יעיל לחישוב התמרת פורייה בדידה (Discrete Fourier Transform (DFT וההתמרה ההופכית שלה. יש מספר רב של אלגוריתמי FFT הכוללים טווח רחב של ענפים במתמטיקה מאריתמטיקה של מספרים מרוכבים לתורת החבורות ותורת המספרים. ערך זה סוקר את הטכניקות וחלק מתכונותיהן הכלליות.
באופן בסיסי יותר: ניתן לייצג פולינומים באמצעות מקדמים או באמצעות שורשים (המשפט היסודי של אלגברה) - ערכי הפולינום בנקודות, כלומר בשביל לייצג קו ישר (פולינום מדרגה 2) נדרשות שתי נקודות להגדרה חד חד ערכית שלו, לפולינום מדרגיה שניה שלוש וכך הלאה. ייתרון ייצוג באמצעות שורשים הוא הקלות שבה ניתן לבצע כפל פולינומים בצורה יעילה:
- עבור ייצוג באמצעות מקדמים נדרשים n^2 פעולות בשביל לבצע את פעולת הכפל.
- עבור ייצוג באמצעות שורשים נדרש לבצע הכפלה של כל נק' מפולינום A לפולינום B ולכן מדובר בפועלה לינארית.
FFT מבצע ביעילות את המעבר בין ייצוג פולינום באמצעות מקדמים, לייצוג באמצעות שורשים, מבצע את הכפל בין החלקים ולאחר מכן חוזר לייצוג באמצעות מקדמים באמצעות inverse FFT בשביל להחזיר את התשובה.
DFT ממיר סדרה של ערכים לרכיבים של תדירויות שונות. פעולה זו שימושית בתחומים רבים, אך חישוב ישיר של ההתמרה לפי ההגדרה שלה הוא פעמים רבות איטי מכדי להיות פרקטי. FFT היא שיטה לחשב את אותה תוצאה באופן מהיר יותר. חישוב DFT של N נקודות באופן נאיבי על פי ההגדרה הוא בעל סיבוכיות של , בעוד של-FFT סיבוכיות . ההבדל במהירות עשוי להיות משמעותי, במיוחד עבור סדרות ארוכות בהן עשוי להיות סדר גודל של אלפים או מיליונים. זמן החישוב יכול להיות מופחת בכמה סדרי גודל במקרים אלו, והשיפור הוא פרופורציונלי ל-. שיפור עצום זה הפך אלגוריתמים רבים מבוססי DFT להיות פרקטיים. FFT הם בעלי חשיבות רבה למגוון רחב של אפליקציות החל מעיבוד אותות ספרתי ופתרון משוואות דיפרנציאליות חלקיות לאלגוריתמים למכפלה מהירה של מספרים טבעיים גדולים.
אלגוריתמי FFT הידועים ביותר מבוססים על פקטוריזציה של , אך ישנם אלגוריתמי FFT בעלי סיבוכיות של לכל , אפילו עבור ראשוני.
בנוסף, ניתן להראות באמצעות אלגוריתם ה-FFT אלגוריתם להכפלה של פולינומים מדרגות n ו-m כאשר n>m בסיבוכיות של , אלגוריתם זה שימושי במיוחד במדעי המחשב.