Ο Μετασχηματισμός Φουριέ εμφανίζεται συχνά στη φυσική και στα μαθηματικά, κάτι που σημαίνει ότι έχει και πολλές καθημερινές χρήσεις.
Με λίγα λόγια, ο Μετασχηματισμός Φουριέ παίρνει ένα σήμα εισόδου, συχνά στο πεδίο του χρόνου ή του χώρου, και το μετασχηματίζει στο πεδίο των συχνοτήτων.
Και πιο συγκεκριμένα, με ένα σήμα εισόδου που αποτελείται από ένα μείγμα (δηλαδή υπέρθεση) διαφορετικών συχνοτήτων, ο μετασχηματισμός ξεχωρίζει τις επιμέρους συχνότητες και δείχνει τη σχετική ισχύ τους.
Αυτό κάνει τον μετασχηματισμό βασικό εργαλείο στην επεξεργασία σήματος (π.χ. φιλτράρισμα, συμπίεση κ.λπ.) και σε πολλές εφαρμογές της επιστήμης δεδομένων.
Επομένως, χρησιμοποιείται ίσως πιο ευρέως απ' ό,τι θα φανταζόταν κανείς με την πρώτη ματιά, κάτι που τον κάνει και χαρακτηριστικό παράδειγμα εκεί όπου οι φανταστικοί αριθμοί γίνονται απαραίτητοι, δεδομένου ότι η έξοδος του Μετασχηματισμού Φουριέ είναι γενικά ένας μιγαδικός αριθμός.
Ενώ ο Μετασχηματισμός Φουριέ έχει μια ολοκληρωτική διατύπωση, εμείς δουλεύουμε ψηφιακά, οπότε μας ενδιαφέρει η διακριτή εκδοχή.
Η παραγωγή του μετασχηματισμού ξεπερνά το πλαίσιο αυτής της άσκησης, αλλά ο ευθύς διακριτός μετασχηματισμός (προς το πεδίο των συχνοτήτων) έχει την εξής μορφή:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
Εδώ, το άθροισμα διατρέχει το n, και το N είναι ο αριθμός των δειγμάτων, το k η συχνότητα, το i η φανταστική μονάδα και το xₙ ένα μεμονωμένο δείγμα.
Αν και εξαιρετικά χρήσιμος, ο Μετασχηματισμός Φουριέ, όταν υλοποιηθεί αφελώς, είναι κάπως αργός (O(n²)).
Ο Γρήγορος Μετασχηματισμός Φουριέ (FFT) είναι ένας αλγόριθμος που τον επιταχύνει δραστικά.
Αυτό γίνεται συνήθως μέσω μιας στρατηγικής διαίρει και βασίλευε, η οποία εκμεταλλεύεται κάποιες συμμετρίες στη διατύπωση και καταλήγει σε ασυμπτωτική πολυπλοκότητα O(Nlog(N)).
Αυτή η επιτάχυνση βελτιώνει σε μεγάλο βαθμό την πρακτικότητα και το φάσμα των εφαρμογών που ταιριάζουν στον μετασχηματισμό.
