Διακριτός μετασχηματισμός Φουριέ

Εφαρμογές

Ο DFT έχει ευρεία χρήση σε πολλούς τομείς.Εδώ απλά δίνονται μερικά σκίτσα σαν παραδείγματα παρακάτω (βλέπε επίσης τις αναφορές στο τέλος). Όλες οι εφαρμογές του DFT εξαρτώνται σε μεγάλο βαθμό από τη διαθεσιμότητα ενός γρήγορου αλγόριθμου για τον υπολογισμό DFTs και των αντίστροφων,ενός ταχύ μετασχηματισμού Φουριέ.

Φίλτρο τράπεζα

Δείτε τράπεζες φίλτρου FFT  και Δειγματοληψία του DTFT.

Συμπίεση δεδομένων

Το πεδίο της ψηφιακής επεξεργασίας σήματος βασίζεται σε μεγάλο βαθμό σε δραστηριότητες στο πεδίο των συχνοτήτων (για παράδειγμα στον μετασχηματισμό Fourier). Για παράδειγμα, αρκετές μέθοδοι συμπίεσης εικόνας και ήχου με απώλειες απασχολούν τον διακριτό μετασχηματισμό Fourier: το σήμα κόβεται σε μικρά τμήματα , το καθένα είναι μετασχηματισμένο , και τότε οι συντελεστές υψηλής συχνότητας Fourier, οι οποίοι υποτίθεται ότι είναι δυσδιάκριτοι, απορρίπτονται. Το πρόγραμμα αποσυμπίεσης υπολογίζει τον αντίστροφο μετασχηματισμό με βάση αυτό το μειωμένο αριθμό συντελεστών Fourier . (Εφαρμογές συμπίεσης συχνά χρησιμοποιούν μια εξειδικευμένη μορφή του DFT, το διακριτό μετασχηματισμό συνημιτόνου ή μερικές φορές τον τροποποιημένο διακριτό μετασχηματισμό συνημιτόνου.) Κάποιοι σχετικά πρόσφατοι αλγόριθμοι συμπίεσης, ωστόσο, χρησιμοποιούν κυμάτιους μετασχηματισμούς, οι οποίοι δίνουν έναν πιο ομοιόμορφο συμβιβασμό μεταξύ του χρόνου και του πεδίου συχνοτήτων από εκείνους που λαμβάνονται με τεμαχισμό των δεδομένων σε τμήματα και μετασχηματίζοντας κάθε τμήμα. Στην περίπτωση JPEG2000, αυτό αποφεύγει τα ψεύτικα χαρακτηριστικά της εικόνας που εμφανίζονται όταν οι εικόνες είναι εξαιρετικά συμπιεσμένες με το αρχικό JPEG.

Μερικές διαφορικές εξισώσεις

Οι διακριτοί μετασχηματισμοί Φουριέ χρησιμοποιούνται συχνά για την επίλυση μερικών διαφορικών εξισώσεων, όπου και πάλι ο DFT χρησιμοποιείται ως προσέγγιση για τη σειρά Fourier (που ανακτάται στο όριο άπειρο N). Το πλεονέκτημα αυτής της προσέγγισης είναι ότι επεκτείνει το σήμα σε εκθετική συνάρτηση μιγαδικών εⁱⁿˣ, η οποία είναι ιδιοσυνάρτηση διαφορικών: d/dx eⁱⁿˣ = σ eⁱⁿˣ. Έτσι, στην αναπαράσταση Fourier , η παραγώγιση είναι απλή—απλά πολλαπλασιάστε με i n. (Σημειώστε, ωστόσο, ότι η επιλογή του n δεν είναι μοναδική . Για να είναι η μέθοδος συγκλίνουσα, μια επιλογή παρόμοια με εκείνη στο τριγωνομετρικό τμήμα παρεμβολής παραπάνω θα πρέπει να χρησιμοποιείται.) Μια γραμμική διαφορική εξίσωση με σταθερούς συντελεστές μετατρέπεται σε μια εύκολα επιλύσιμη αλγεβρική εξίσωση. Ένα, στη συνέχεια, χρησιμοποιεί το αντίστροφο DFT για να μετατρέψει το αποτέλεσμα πίσω στη κανονική διαστηματική αναπαράσταση. Η προσέγγιση αυτή ονομάζεται φασματική μέθοδος.

Πολλαπλασιασμός μεγάλων ακεραίων

Ο πιο γρήγορος γνωστός αλγόριθμος για τον πολλαπλασιασμό των πολύ μεγάλων ακεραίων χρησιμοποιεί την μέθοδο πολλαπλασιασμού πολυωνύμων που περιγράφεται παραπάνω.Οι ακέραιοι μπορούν να αντιμετωπιστεί ως η τιμή ενός πολυωνύμου δίνοντας τιμή ειδικά στον αριθμό της βάσης, με τους συντελεστές του πολυωνύμου να αντιστοιχούν στα ψηφία σε αυτή τη βάση. Μετά τον πολλαπλασιασμό πολυωνύμων ,ένα βήμα σχετικά χαμηλής πολυπλοκότητας μεταφοράς-διάδοσης ολοκληρώνει τον πολλαπλασιασμό.

Συνέλιξη

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

Εκπροσώπηση θεωρίας

(Για περισσότερες λεπτομέρειες σε αυτό το θέμα,δείτε θεωρία αναπαράστασης των πεπερασμένων ομάδων και διακριτός μετασχηματισμός Φουριέ)
Ο DFT μπορεί να ερμηνευθεί ως η μιγαδική τιμή θεωρίας αναπαράστασης της πεπερασμένης κυκλικής ομάδας. Με άλλα λόγια, μια ακολουθία από n μιγαδικούς αριθμούς μπορεί να θεωρηθεί ως ένα στοιχείο του n-διάστατου χώρου μιγαδικών Cⁿ ή αντίστοιχα μια συνάρτηση f από την πεπερασμένη κυκλική ομάδα τάξης n στους μιγαδικούς αριθμούς, το Zₙ → C. Οπότε η f είναι μια συνάρτηση κλάσης σχετικά με την πεπερασμένη κυκλική ομάδα, και έτσι μπορεί να εκφραστεί ως γραμμικός συνδυασμός των αμείωτων χαρακτήρων αυτής της ομάδας, που είναι οι ρίζες της ενότητας.
Από αυτή την άποψη, μπορεί κανείς να γενικεύσει τον DFT για την εκπροσώπηση θεωρίας γενικά, ή πιο ειδικά για την θεωρία αναπαράστασης των πεπερασμένων ομάδων.
Ακόμα πιο συγκεκριμένα, μπορεί κανείς να γενικεύσει το DFT είτε αλλάζοντας τον στόχο (παίρνει τιμές σε ένα πεδίο, εκτός από το μιγαδικοί αριθμοί), ή το πεδίο τιμών (ομάδα άλλη από μια πεπερασμένη κυκλική ομάδα), όπως περιγράφεται στη συνέχεια.