FFT — Ο Γρήγορος Μετασχηματισμός Fourier απλά

Το FFT, ή γρήγορος μετασχηματισμός Fourier, είναι ένας γρήγορος τρόπος για να υπολογίσουμε τον διακριτό μετασχηματισμό Fourier (DFT). Αν ξεκινήσετε με ισαπέχοντα δείγματα, το DFT δείχνει πόσο από κάθε διακριτό μοτίβο συχνότητας εμφανίζεται σε αυτά τα δείγματα.

Το σημαντικό σημείο είναι ότι το FFT δεν αλλάζει το αποτέλεσμα. Δίνει τις ίδιες τιμές DFT με τον άμεσο τύπο, αλλά φτάνει εκεί με πολύ λιγότερη επαναλαμβανόμενη δουλειά.

Το FFT με μία πρόταση

Το FFT είναι ένας ταχύτερος αλγόριθμος για τους ίδιους αριθμούς στο πεδίο συχνοτήτων που ορίζει ήδη το DFT.

Τι μετρά το DFT

Έστω ότι έχετε δείγματα $x_0, x_1, \dots, x_{N-1}$. Το DFT παράγει αριθμούς $X_0, X_1, \dots, X_{N-1}$ που ορίζονται από

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Κάθε $X_k$ μετρά πόσο έντονα ταιριάζουν τα δεδομένα με ένα διακριτό μοτίβο συχνότητας.

Αν τα δείγματα είναι ισαπέχοντα με ρυθμό δειγματοληψίας $f_s$, τότε τα γειτονικά bins συχνοτήτων απέχουν κατά

$$\frac{f_s}{N}$$

Αυτή η συνθήκη έχει σημασία. Χωρίς γνωστό ρυθμό δειγματοληψίας, εξακολουθείτε να έχετε bins του DFT, αλλά δεν μπορείτε να τα χαρακτηρίσετε ως φυσικές συχνότητες όπως τα hertz.

Γιατί το FFT είναι ταχύτερο

Το FFT είναι μια οικογένεια αλγορίθμων για αποδοτικό υπολογισμό του DFT. Το βασικό τέχνασμα είναι να επαναχρησιμοποιεί τη δομή στους μιγαδικούς εκθετικούς παράγοντες αντί να επανυπολογίζει σχεδόν ίδιες αθροίσεις από την αρχή.

Η πιο εύκολη εκδοχή για να την οπτικοποιήσετε είναι το radix-2 FFT. Λειτουργεί πιο φυσικά όταν το $N$ είναι δύναμη του $2$, και χωρίζει έναν μετασχηματισμό μήκους $N$ σε δύο μετασχηματισμούς μήκους $N/2$ πριν συνδυάσει τα αποτελέσματα.

Για το άμεσο DFT, ο αριθμός των πράξεων αυξάνεται της τάξης του $N^2$. Για τις συνηθισμένες μεθόδους FFT, πέφτει περίπου στο $N \log N$.

Αυτό το χάσμα εξηγεί γιατί τα FFT έχουν σημασία στην πράξη. Για μικρές εισόδους, και οι δύο μέθοδοι μπορεί να φαίνονται αποδεκτές. Για μεγάλες εισόδους, το FFT είναι εντυπωσιακά ταχύτερο.

Πώς το FFT χωρίζει τη δουλειά

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

Ένας τυπικός διαχωρισμός είναι:

1. Βάλτε τα δείγματα με άρτιους δείκτες σε μία λίστα.
2. Βάλτε τα δείγματα με περιττούς δείκτες σε μία άλλη λίστα.
3. Υπολογίστε μικρότερους μετασχηματισμούς σε αυτές τις λίστες.
4. Συνδυάστε τα δύο μισά.

Αυτό είναι η μέθοδος διαίρει και βασίλευε εφαρμοσμένη στην ανάλυση συχνοτήτων.

Παράδειγμα FFT 4 σημείων

Πάρτε το σήμα 4 σημείων

$$x = [1, 0, 1, 0]$$

Αυτό το μοτίβο εναλλάσσεται μεταξύ $1$ και $0$, οπότε περιμένουμε κάποια δομή συχνοτήτων αντί για ένα εντελώς επίπεδο αποτέλεσμα.

Χωρίστε το σε άρτιους και περιττούς δείκτες:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

Το DFT 2 σημείων του άρτιου μέρους είναι

$$E = [2, 0]$$

και το DFT 2 σημείων του περιττού μέρους είναι

$$O = [0, 0]$$

Για ένα FFT 4 σημείων, το βήμα συνδυασμού είναι

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

όπου

$$W_4 = e^{-i 2 \pi / 4}$$

Επειδή $O_k = 0$, ο συνδυασμός είναι ιδιαίτερα απλός:

$$X = [2, 0, 2, 0]$$

Τώρα ερμηνεύστε το αποτέλεσμα.

Το $X_0 = 2$ είναι ο όρος μηδενικής συχνότητας, άρα αντανακλά τη μη μηδενική μέση τιμή των δειγμάτων. Η μη μηδενική τιμή στο $X_2$ αποτυπώνει το εναλλασσόμενο μέρος του μοτίβου σε αυτή την περίπτωση 4 σημείων. Αν αφαιρέσετε πρώτα τη μέση τιμή, ο όρος $X_0$ εξαφανίζεται και το εναλλασσόμενο συστατικό ξεχωρίζει πιο καθαρά.

Αυτό το παράδειγμα είναι μικρό, αλλά η ιδέα κλιμακώνεται: λύνουμε μικρότερους μετασχηματισμούς και μετά τους συνδυάζουμε, αντί να ξαναχτίζουμε κάθε φορά ολόκληρο το άθροισμα.

Συνηθισμένα λάθη στο FFT

Να θεωρείτε το FFT και το DFT διαφορετικά αποτελέσματα

Δεν είναι. Το FFT είναι μια ταχύτερη μέθοδος υπολογισμού του DFT.

Να διαβάζετε τα bins ως φυσικές συχνότητες πολύ νωρίς

Οι θέσεις των bins γίνονται φυσικές συχνότητες μόνο όταν είναι γνωστή η απόσταση μεταξύ των δειγμάτων. Αν ο ρυθμός δειγματοληψίας είναι $f_s$, τότε η απόσταση των bins είναι $f_s/N$ για ισαπέχοντα δείγματα.

Να υποθέτετε ότι το zero-padding προσθέτει νέα πληροφορία

Το zero-padding μπορεί να κάνει ένα φάσμα να φαίνεται πιο ομαλό, επειδή δειγματοληπτεί πιο λεπτά τον υποκείμενο μετασχηματισμό, αλλά δεν προσθέτει νέα μετρημένα δεδομένα.

Να αγνοείτε την προετοιμασία του σήματος

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

Πού χρησιμοποιείται το FFT

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

Ο λόγος είναι πρακτικός: πολλές πράξεις γίνονται ευκολότερες ή ταχύτερες αφού περάσουμε από το πεδίο δειγμάτων στο πεδίο συχνοτήτων.

Δοκιμάστε μια παρόμοια περίπτωση

Πάρτε $8$ ισαπέχοντα δείγματα ενός ημιτόνου σε μία πλήρη περίοδο και υπολογίστε το DFT με αριθμομηχανή ή script. Έπειτα προσθέστε μια σταθερή μετατόπιση και συγκρίνετε τη νέα έξοδο. Η μεγαλύτερη τιμή στο $X_0$ είναι ένας απλός τρόπος να δείτε τι διαχωρίζει το FFT.