Τι Σας Δείχνει Πράγματι η 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. Αυτός είναι ο λόγος που τα τετραγωνικά κύματα ηχούν " buzzy" — περιέχουν ενέργεια υψηλής συχνότητας που δεν περιέχει ημίτονα.
Λευκό θόρυβο παράγει μπάρες περίπου ίσου ύψους παντού. Κάθε συχνότητα είναι παρούσα με ίσες πιθανότητες.
Μια ανθρώπινη φωνή παράγει ένα θεμελιώδες (το γήπεδο που ακούτε) συν διαμορφωτές - αντηχούν κορυφές από το σχήμα της φωνητικής οδού σας που διακρίνονται φωνήεντα.

Τα πρώτα τρία είναι κάτω — κάντε κλικ μεταξύ τους. Τα ύψη είναι οι τύποι, όχι ένα σχέδιο: το ημίτονο είναι 1 στο θεμελιώδες, το τετράγωνο κύμα είναι ακριβώς 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χρονος αλγόριθμος, στην τσέπη σου, τρέχει δισεκατομμύρια φορές την ημέρα.

Δοκίμασε το

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

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

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

Παραπομπές

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

Το FFT του PinePaper είναι μια εφαρμογή Cooley-Tukey radix-2 με το παράθυρο Hann, Hamming και Blackman, καθώς και φίλτρα χαμηλής διέλευσης και υψηλής διέλευσης. Δοκιμάστε το δωρεάν στο [pinepaper.studio/editor] (/editor).