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

השאלה

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

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

מה בעצם קורה

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

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

הליבה המתמטית: כל אות תקופתי ניתן לכתוב כסכום של גלים חטאים וקוסטין בתדרים שונים. זהו המשפט של פורייה (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. זו הסיבה לכך שגלי ריבוע נשמעים "ברוכים" הם מכילים אנרגיה גבוהה שחטאים טהורים לא.
• • רעש לבן* מייצר ברים בגובה שווה בכל מקום. כל תדירות קיימת בהסתברות שווה.
• • קול אנושי* מייצר יסוד (הכרזה שאתה שומע) בתוספת טפסים - פסגות חוזרות מן הצורה של מערכת הקול שלך אשר להבחין נדרלים.

שלושת הראשונים למטה - לחץ ביניהם. הגבהים הם הנוסחאות, לא ציור: החטא הוא 1 ביסודו, גל הריבוע הוא בדיוק 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, בכיס שלך, רץ מיליארדי פעמים ביום.

נסה את זה

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

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

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

הפניות

• בריגהם, א. (1988). The Fast Fourier Transform and its Applications. בית קברות.
• Cooley, J.W. טוקי, J.W. (1965). Algorithm for the Machine Calculation of Complex Fourier Series. מתמטיקה של Computation, 19(90), 297-301.
• פורייה, J. (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. שריפר, R.W. (2009). * עיבוד אותות בזמן אמת (3rd ed). בית קברות.
• שאנון, C.E. (1949). תקשורת בנוכחות רעש. • תוצאות של IRE*, 37(1), 10-21.
• סמית, S.W. (1997). המדריך של המדען והמהנדס לעיבוד אותות דיגיטליים*. פרסום טכני בקליפורניה.
• וואנג, א. (2003). חיפוש אודיו תעשייתי-Strength Audio Algorithm. תוצאות של ISMIR 2003 *. (אלגוריתם טביעות אצבע של שאזאם)
• וואלאס, G.K. (1991). JPEG עדיין תמונה סטנדרטית של קומפרסון. * תקשורת של ACM*, 34(4), 3044.

---

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