מה בעצם FFT מראה לך

השאלה

שחקו בפסנתר – תגידו, C ו-E ביחד. האוזן שומעת צליל אחד. אבל צליל זה הוא שני תדרים סופר-מוסמכים: 261.6 Hz ו 329.6 הרץ. ה- cochlea שלך מפריד אותם פיזית - תאי שיער שונים מהדהדים בתדרים שונים, ושולחים אותות נפרדים למוח שלך.

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

מה בעצם קורה

אות המדגם לאורך זמן הוא רשימה של מספרים: האמפולדה בכל נקודת דגימה. שיא של 1 שניות ב 44,100 הרץ הוא 44,100 מספרים. מספרים אלה מתארים את האות ב- **Time domain - amplitude כתפקוד של זמן.

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

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

למה "פחד"

הדרך התמימה לשנות את הארבעה דורשת N2 פעולות עבור דגימות N. עבור 1024 דגימות, מדובר על מיליון פעולות. אלגוריתם Cooley-Tukey (1965) מקטין את זה ל-Nlog2(N) - כ-10,000 פעולות לאותה קלט. מהירות של 100x עבור מיליון דגימות, המהירות היא 50,000x.

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

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

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

יישום PinePaper הוא ספר לימוד Cooley-Tukey Radix-2 DIT (התמדה בזמן). 40 שורות של JavaScript כתבנו אותו מאפס ולא לייבא ספריה כי רצינו שתלמידים יוכלו לקרוא את המקור ולהבין כל קו.

מה זה Bars

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

• • גל חטא טהור מייצר בר גבוה אחד בתדירותו ולא משהו אחר.
• • גל ריבועי מייצר ברים ביסודו וכל נזק מוזר (3rd, 5th, 7th...), ירידה של 1/n. לכן גלים רבועים נשמעים "מבוזים" - הם מכילים אנרגיה גבוהה שחטאים טהורים לא.
• • רעש לבן* מייצר ברים בגובה שווה בכל מקום. כל תדירות קיימת בהסתברות שווה.
• • קול אנושי** מייצר יסוד (הכרזה שאתה שומע) בתוספת צורות - פסגות חוזרות מן הצורה של מערכת הקול שלך שמבדילה נדרים.

צילום: Why the Edges Matter

יש לתפוס. ה-FFT מניח שהאות חוזר לנצח. אבל הדגימה שלנו סופית – היא מתחילה ונפסקת. אם האות לא קורה באפס בשני נקודות הקצה, הקיצוץ הפתאומי יוצר תוכן מלאכותי גבוה. שם הסרטון: spectral Legionage.

התיקון: להכפיל את האות על ידי הפונקציה window אשר מקלים בצורה חלקה עד אפס בשוליים. חלונות משותפים:

• Hann (פעמון אקוסטי): מטרה כללית טובה, מאבד כמה החלטות תדירות
• Hamming: דומה להאן אבל לא מגיע אפס בקצהים, מעט יותר טוב דיכוי צדולי
• • Blackman**: הצרה העיקרית, דיכוי הצד הטוב יותר, מפסידה יותר ברזולוציה של תדירות

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

היכן חי ה-FFT

אתה אינטראקציה עם תוצאות FFT כל הזמן:

• *MP3 ו- AAC דחיסה: להפוך את אודיו לתחום התדר, תדרי דיסקרד מתחת לסף השמיעה, דחוסים את מה שנשאר. השינוי הוא הבסיס כולו של דחיסת אודיו אבודה.
• ** JPEG דחיסה**: גרסת 2D (DCT) הופכת 8×8 בלוקים פיקסל למתחת תדירות, המהווה רכיבים גבוהים. זו הסיבה ש-JPEG פריטים מופיעים כבלוקים.
• WiFi ו- 5G: מ-DM encoding מחלק נתונים על פני מספר רב של תת-קרנים. ה-FFT ממיר בין זמן-דומיין לבין סמלי נתונים של תדירות-דומיין.
• MRI הדמיה: האות הגולמי מסורק MRI נמצא בחלל התדר. FFT הפוכה משחזר את התמונה המרחבית. כל MRI שאי פעם ראיתם הוא שינוי פורייה הפוך.
• Shazam: חישוב spectrogram (FFT over Siding חלונות), תמצית שיא, תואם את התבנית נגד מסד נתונים. ה-FFT הוא הצעד הראשון בהכרה בכל שיר.

אלגוריתם בן 60, בכיס שלך, רץ מיליארדי פעמים ביום.

המונחים:function-plot

נסה את זה

פתח PinePaper, בחר את גנרטור Analyzer Spectrum. ליצור גל מרובע תראו את הסורגים – תראו את ההמוניות המוזרות נופלות בשעה 1/n. מעבר לראיית - עכשיו כולם הרמוניים נוכחים, נופלים כמו 1/n. מעבר לרעש - ספקטרום שטוח, כל תדירות סבירה באותה מידה.

לשנות את תפקוד החלון. צפה כיצד האן מחלק את הספקטרום בעלות של שיאים רחבים יותר. Switch to Blackman - פסגות צרות יותר, אך נמוך יותר.

אתה לא קורא על ה-FFT. אתם מודדים אותות ומתבוננים במה שהשינוי מגלה. זה ההבדל בין ידע והבנה.

הפניות

• בריגהם, א.או. (1988) The Fast Fourier Transform and its Applications בית קברות.
• Cooley, J.W & Tukey, J.W. (1965) Algorithm for the Machine Calculation of Complex Fourier Series מתמטיקה של Computation, 19(90), 297-301.
• פורייה, ג'יי (1822) "Théorie Pirytique de la chaleur" פריז: פילין דיוט.
• האריס, F.J. (1978) על השימוש של Windows for Harmonic Analysis with the Discrete Fourier Transform. * אישור של IEEE*, 66(1), 51-83.
• Oppenheim, A.V & Shafer, R.W. (2009) * עיבוד אותות בזמן אמת (3rd ed). בית קברות.
• שאנון, C.E (1949) תקשורת בנוכחות רעש • תוצאות של IRE*, 37(1), 10-21.
• סמית', S.W. (1997) המדריך של המדען והמהנדס לעיבוד אותות דיגיטליים* פרסום טכני בקליפורניה.
• וואנג, א', et al. (2003) חיפוש אודיו תעשייתי-Strength Audio Algorithm תוצאות של ISMIR 2003 * (אלגוריתם טביעות אצבע של שאזאם)
• וולאס, ג'ק (1991) ה-JPEG עדיין מדמיין את הסטנדרט. * תקשורת של ACM*, 34(4), 3044.

---

*PinePaper's FFT הוא יישום Cooley-Tukey RFx-2 עם האן, Hamming, ו- Blackman Windowing, בתוספת מסננים נמוכים וגבוהים. נסו אותו בחינם ב- pinepaper.סטודיו/editor