Τι σας Δείχνει Πράγματι η FFT

Η ερώτηση

Παίξτε μια συγχορδία σε ένα πιάνο — ας πούμε, C και E μαζί. Το αυτί σου ακούει έναν ήχο. Αλλά αυτός ο ήχος είναι δύο συχνότητες υπερεπιβαλλόμενες: 261.6 Hz και 329.6 Hz. Ο κοχλίας σας τους χωρίζει σωματικά — διαφορετικά κύτταρα των μαλλιών αντηχούν σε διαφορετικές συχνότητες, στέλνοντας διακριτά σήματα στον εγκέφαλό σας.

Το Fast Fourier Transform κάνει το ίδιο πράγμα, αλλά με αριθμούς αντί για κύτταρα μαλλιών. Δώστε του ένα σήμα (μια ακολουθία δειγμάτων πλάτους με την πάροδο του χρόνου) και επιστρέφει μια λίστα συχνοτήτων και τις αντοχές τους. Απαντά: ** ποιες συχνότητες υπάρχουν, και πόσο από το καθένα; **

Τι συμβαίνει στην πραγματικότητα

Ένα σήμα που λαμβάνεται με την πάροδο του χρόνου είναι ένας κατάλογος αριθμών: το εύρος σε κάθε σημείο δείγματος. Μια ηχογράφηση 1 δευτερολέπτου στα 44.100 Hz είναι 44.100 αριθμοί. Αυτοί οι αριθμοί περιγράφουν το σήμα στον τομέα ** του χρόνου ** — εύρος ως συνάρτηση του χρόνου.

Το FFT μετατρέπει αυτό στο πεδίο ** συχνοτήτων ** — πλάτος ως συνάρτηση συχνότητας. Ίδια πληροφορία, διαφορετική αναπαράσταση. Όπως η εναλλαγή μεταξύ Καρτεσιανού και πολικών συντεταγμένων: τίποτα δεν δημιουργείται ή καταστρέφεται, μόνο εκ νέου εκφράζεται.

Ο μαθηματικός πυρήνας: κάθε περιοδικό σήμα μπορεί να γραφτεί ως άθροισμα ημίτονων και συνημμένων κυμάτων σε διαφορετικές συχνότητες. Αυτό είναι το θεώρημα του Φουριέ (1807). Το FFT υπολογίζει τους συντελεστές αυτού του αθροίσματος — πόσο από κάθε συχνότητα βρίσκεται στο σήμα.

Γιατί "Γρήγορα"

Ο αφελής τρόπος υπολογισμού ενός μετασχηματισμού Fourier απαιτεί N2 εργασίες για δείγματα N. Για 1024 δείγματα, είναι περίπου 1 εκατομμύριο εγχειρήσεις. Ο αλγόριθμος Cooley-Tukey (1965) το μειώνει σε N·log2(N) — περίπου 10.000 λειτουργίες για την ίδια είσοδο. Ταχύτητα 100x. Για ένα εκατομμύριο δείγματα, η επιτάχυνση είναι 50.000x.

Το κόλπο: χωρίστε το σημείο Ν μεταμορφώνεται σε δύο N/2-σημείο μεταμορφώνεται, αναδρομικά. Αυτό απαιτεί N να είναι μια δύναμη του 2 (ή σας pad με μηδενικά). Κάθε σχισμή έχει το πρόβλημα. Η λειτουργία "butterfly" συνδυάζει τα μισά:

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

Όπου το W είναι σύνθετο εκθετικό (εναλλαγή στο σύνθετο επίπεδο). Τα ίδια δύο υποαποτελέσματα σας δίνουν δύο σημεία εξόδου. Αυτός είναι ο λόγος για τον οποίο ο αλγόριθμος είναι "γρήγορος" — επαναχρησιμοποιεί κάθε υπολογισμό δύο φορές.

Η εφαρμογή του PinePaper είναι ένα εγχειρίδιο Cooley-Tukey radix-2 DIT (αποτίμηση στο χρόνο). 40 γραμμές του JavaScript. Το γράψαμε από το μηδέν αντί να εισάγουμε μια βιβλιοθήκη επειδή θέλαμε οι μαθητές να μπορούν να διαβάζουν την πηγή και να καταλαβαίνουν κάθε γραμμή.

Τι σημαίνουν αυτά τα μπαρ

Όταν βλέπετε έναν αναλυτή φάσματος — μπάρες να πηδούν στη μουσική — κάθε μπάρα αντιπροσωπεύει έναν κάδο συχνοτήτων. Το ύψος είναι το μέγεθος (δύναμη) αυτής της συχνότητας στο τρέχον σήμα.

• **Ένα καθαρό ημίτονο κύμα ** παράγει ένα ψηλό μπαρ στη συχνότητά του και τίποτα άλλο.
• **Ένα τετράγωνο κύμα ** παράγει μπάρες στη θεμελιώδη και κάθε παράξενη αρμονική (3η, 5η, 7η...), μειώνεται ως 1/n. Αυτός είναι ο λόγος που τα τετραγωνικά κύματα ηχούν " ασφυκτικά" — περιέχουν ενέργεια υψηλής συχνότητας που τα καθαρά ημίτονα όχι.
• **Λευκό θόρυβο ** παράγει μπάρες περίπου ίσου ύψους παντού. Κάθε συχνότητα είναι παρούσα με ίσες πιθανότητες.
• **Μια ανθρώπινη φωνή ** παράγει ένα θεμελιώδες (το βήμα που ακούτε) συν φορμά — αντηχούν κορυφές από το σχήμα της φωνητικής σας οδού που διακρίνουν φωνήεντα.

Παράθυρο: Γιατί οι άκρες έχουν σημασία

Υπάρχει μια παγίδα. Η FFT υποθέτει ότι το σήμα επαναλαμβάνεται για πάντα. Αλλά το δείγμα μας είναι πεπερασμένο — αρχίζει και σταματά. Αν το σήμα δεν είναι στο μηδέν και στα δύο τελικά σημεία, η απότομη αποκοπή δημιουργεί τεχνητό περιεχόμενο υψηλής συχνότητας. Αυτό ονομάζεται **φασματική διαρροή **.

Η διόρθωση: πολλαπλασιάστε το σήμα με μια λειτουργία window ** που ταλαντεύεται ομαλά προς μηδέν στις άκρες. Κοινά παράθυρα:

• **Hann ** (κώλος της καφεΐνης): καλός γενικός σκοπός, χάνει κάποια ανάλυση συχνότητας
• **Hamming **: παρόμοια με Hann αλλά δεν φτάνει μηδέν στις άκρες, ελαφρώς καλύτερη καταστολή του πλευρικού λοβού
• Blackman: στενότερος κύριος λοβός, καλύτερη καταστολή του πλευρικού λοβού, χάνει περισσότερη ανάλυση συχνότητας

Η επιλογή είναι πάντα μια ανταλλαγή μεταξύ ανάλυσης συχνότητας (πόσο ακριβώς μπορείτε να προσδιορίσετε μια συχνότητα) και φασματική διαρροή (πόσο η ενέργεια αιμορραγεί σε γειτονικούς κάδους). Δεν υπάρχει τέλειο παράθυρο. Αυτό είναι συνέπεια της αρχής της αβεβαιότητας — δεν μπορείτε να έχετε αυθαίρετα ακριβή γνώση τόσο του χρόνου όσο και της συχνότητας ταυτόχρονα.

Όπου ζει το FFT

Αλληλεπιδράσεις με τα αποτελέσματα FFT συνεχώς:

• MP3 και συμπίεση AAC: μετατροπή ήχου σε τομέα συχνότητας, απόρριψη συχνοτήτων κάτω από το όριο ακοής, συμπίεση ό, τι απομένει. Το transform είναι ολόκληρη η βάση της απώλειας συμπίεσης ήχου.
• ** JPEG συμπίεση **: η 2D έκδοση (DCT) μετατρέπει 8×8 pixel μπλοκ σε τομέα συχνότητας, quantizes υψηλής συχνότητας συστατικά. Γι' αυτό τα τεχνουργήματα JPEG εμφανίζονται ως μπλοκ.
• WiFi και 5G: OFDM κωδικοποίηση χωρίζει τα δεδομένα σε πολλές υπομεταφορείς συχνότητας. Η FFT μετατρέπει μεταξύ της μετάδοσης χρόνου-domain και των συμβόλων δεδομένων συχνότητας-domain.
• **MRI απεικόνιση **: το ακατέργαστο σήμα από έναν ανιχνευτή μαγνητικής τομογραφίας είναι σε χώρο συχνότητας. Το αντίστροφο FFT ανακατασκευάζει τη χωρική εικόνα. Κυριολεκτικά: κάθε μαγνητική που έχετε δει είναι μια αντίστροφη μεταμόρφωση Fourier.
• **Shazam **: υπολογίζει το φασματογράφημα (FFT πάνω από συρόμενα παράθυρα), αποσπάσματα κορυφές, ταιριάζει με το μοτίβο σε μια βάση δεδομένων. Το FFT είναι το πρώτο βήμα στην αναγνώριση κάθε τραγουδιού.

Ένας 60χρονος αλγόριθμος, στην τσέπη σου, τρέχει δισεκατομμύρια φορές την ημέρα.

{{widget: function- plot}

Δοκίμασε το

Ανοίξτε PinePaper, επιλέξτε τη γεννήτρια Spectrum Analyzer. Δημιουργήστε ένα τετράγωνο κύμα. Κοιτάξτε τα κάγκελα — θα δείτε τις περίεργες αρμονικές να πέφτουν ως 1/n. Αλλάξτε σε πριονωτό — τώρα όλες οι αρμονικές είναι παρούσες, πέφτοντας ως 1/n. Αλλαγή σε θόρυβο — επίπεδο φάσμα, κάθε συχνότητα εξίσου πιθανό.

Αλλαγή λειτουργίας παραθύρου. Παρακολουθήστε πώς Hann λειαίνει το φάσμα στο κόστος των ευρύτερων κορυφών. Αλλάξτε σε Blackman — στενότερες κορυφές, αλλά κάτω πλευρικούς λοβούς.

Δεν διαβάζεις για το FFT. Μετράς τα σήματα και παρατηρείς τι αποκαλύπτει το μετασχηματισμό. Αυτή είναι η διαφορά μεταξύ γνώσης και κατανόησης.

Παραπομπές

• Μπρίγκαμ, Ε.Ο. (1988). * Το γρήγορο Fourier Transform και οι εφαρμογές του*. Στο Πρέντις Χολ.
• Cooley, J.W. & Tukey, J.W. (1965). Αλγόριθμος για τον υπολογισμό της μηχανής του Complex Fourier Series. * Μαθηματικά της Υπολογιστικής*, 19(90), 297-301.
• Φουριέ, Ι. (1822). * Théorie analytique de la chaleur*. Παρίσι: Firmin Didot.
• Harris, F.J. (1978). Για τη χρήση των Windows για Harmonic Analysis με το Discrete Fourier Transform. Διαδικασίες του ΙΕΕΕΕ, 66(1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). Discrete-Time Signal Processing (3rd ed.). Στο Πρέντις Χολ.
• Σάνον, Κ.Χ. (1949). Επικοινωνία στην Παρουσία του Θόρυβου. 37(1), 10-21.
• Smith, S.W. (1997). Ο Οδηγός Επιστήμονας και Μηχανικού για την Επεξεργασία Ψηφιακού Σήματος. Τεχνικές Εκδόσεις Καλιφόρνιας.
• Wang, A., et al. (2003). Ένας βιομηχανικός-ενισχυμένος αλγόριθμος αναζήτησης ήχου. Διαδικασίες του ISMIR 2003. (Ο αλγόριθμος δακτυλικών αποτυπωμάτων του Shazam.)
• Wallace, G.K. (1991). Το πρότυπο συμπίεσης JPEG Standard. Επικοινωνίες της ACM, 34(4), 30-44.

---

• PinePaper FFT είναι ένα Cooley-Tukey radix-2 υλοποίηση με Hann, Hamming, και Blackman windowing, συν χαμηλής διέλευσης και υψηλής διέλευσης φίλτρα. Δοκιμάστε δωρεάν στο pinepaper.studio/editor.*