FFT

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

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

אלגוריתמי FFT הידועים ביותר מבוססים על פקטוריזציה של , אך ישנם אלגוריתמי FFT בעלי סיבוכיות של לכל , אפילו עבור ראשוני.

בנוסף, ניתן להראות באמצעות אלגוריתם ה-FFT אלגוריתם להכפלה של פולינומים מדרגות n ו-m כאשר n>m בסיבוכיות של , אלגוריתם זה שימושי במיוחד במדעי המחשב.

radix 2

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

כאשר k הוא בין ל-. אלגוריתם FFT נפוץ הוא radix-2 המבצע את החישוב בנפרד על האינדקסים הזוגיים, (), והאינדקסים האי-זוגיים (), ולבסוף משלב את תוצאות החישוב יחד. בצורה זו פועל האלגוריתם באופן רקורסיבי ומתבצע בסיבוכיות . צורת הצגה זו מניחה כי N הוא חזקה של 2.

בשיטה זו מארגנים מחדש את המשוואה לשני חלקים: סכום על האיברים עם האינדקסים הזוגיים , וסכום על האיברים האי זוגיים :

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

קישורים חיצוניים

  • FFT, באתר MathWorld (באנגלית)   המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0