FFT

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

התמרת פורייה מהירהאנגלית Fast Fourier Transform‏ (FFT)) היא אלגוריתם יעיל לחישוב התמרת פורייה בדידה ((Discrete Fourier Transform (DFT) וההתמרה ההופכית שלה. יש מספר רב של אלגוריתמי 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 ראשוני.

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 בצורה הבאה:


\begin{matrix} X_k & =
& \left\{
\begin{matrix}
E_k + e^{-\frac{2\pi i}{N}k} O_k & \mbox{if } k < N/2 \\ \\
E_{k-N/2} - e^{-\frac{2\pi i}{N} (k-N/2)} O_{k-N/2} & \mbox{if }
k \geq N/2. \end{matrix} \right. \end{matrix}
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.