Διακριτός μετασχηματισμός Φουριέ: Διαφορά μεταξύ των αναθεωρήσεων

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
ArisKalk (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
ArisKalk (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Γραμμή 378: Γραμμή 378:
== Γενικεύσεις ==
== Γενικεύσεις ==


=== Εκπροσώπηση θεωρία ===
=== Εκπροσώπηση θεωρίας ===
Ο DFT μπορεί να ερμηνευθεί ως το συγκρότημα-valued [[Θεωρία αναπαραστάσεων|εκπροσώπηση θεωρία]] της πεπερασμένης κυκλικής ομάδας. Με άλλα λόγια, μια ακολουθία από ''n'' μιγαδικοί αριθμοί μπορεί να θεωρηθεί ως ένα στοιχείο του ''n''-διαστάσεων χώρο συγκρότημα '''C'''<sup>''n''</sup> ή αντίστοιχα μια συνάρτηση ''f'' από την πεπερασμένη κυκλική ομάδα τάξης ''n'' στο μιγαδικούς αριθμούς, το '''Z'''<sub>''n''</sub> → '''C'''. Οπότε ''η f'' είναι μια συνάρτηση κλάσης σχετικά με την πεπερασμένη κυκλική ομάδα, και έτσι μπορεί να εκφραστεί ως γραμμικός συνδυασμός των αμείωτη χαρακτήρες αυτής της ομάδας, που είναι οι ρίζες της ενότητας.
Ο DFT μπορεί να ερμηνευθεί ως η μιγαδική τιμή [[Θεωρία αναπαραστάσεων|εκπροσώπησης θεωρίας]] της πεπερασμένης κυκλικής ομάδας. Με άλλα λόγια, μια ακολουθία από ''n'' μιγαδικούς αριθμούς μπορεί να θεωρηθεί ως ένα στοιχείο του ''n''-διάστατου χώρου μιγαδικών '''C'''<sup>''n''</sup> ή αντίστοιχα μια συνάρτηση ''f'' από την πεπερασμένη κυκλική ομάδα τάξης ''n'' στους μιγαδικούς αριθμούς, το '''Z'''<sub>''n''</sub> → '''C'''. Οπότε ''η f'' είναι μια συνάρτηση κλάσης σχετικά με την πεπερασμένη κυκλική ομάδα, και έτσι μπορεί να εκφραστεί ως γραμμικός συνδυασμός των αμείωτων χαρακτήρων αυτής της ομάδας, που είναι οι ρίζες της ενότητας.


Από αυτή την άποψη, μπορεί κανείς να γενικεύσει τον DFT για την εκπροσώπηση θεωρία, γενικά, ή πιο στενά για την [[Θεωρία αναπαραστάσεων πεπερασμένων ομάδων|εκπροσώπηση θεωρία των πεπερασμένων ομάδων]].
Από αυτή την άποψη, μπορεί κανείς να γενικεύσει τον DFT για την εκπροσώπηση θεωρίας γενικά, ή πιο ειδικά για την [[Θεωρία αναπαραστάσεων πεπερασμένων ομάδων|εκπροσώπηση θεωρίας των πεπερασμένων ομάδων]].


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


=== Άλλα πεδία ===
=== Άλλα πεδία ===
Πολλές από τις ιδιότητες του DFT εξαρτώνται μόνο από το γεγονός ότι <math>e^{-\frac{2 \pi i}{N}}</math> είναι μια [[Κυκλοτομικό σώμα|πρωτόγονη ρίζα της ενότητας]], μερικές φορές συμβολίζεται <math>\omega_N</math> ή <math>W_N</math> (έτσι ώστε <math>\omega_N^N = 1</math>). Αυτές οι ιδιότητες περιλαμβάνουν την πληρότητα, την καθετότητα, Plancherel/Parseval, περιοδικότητα, shift, συνέλιξη, και unitarity ιδιότητες παραπάνω, καθώς και πολλά FFT αλγόριθμοι. Για το λόγο αυτό, ο διακριτός μετασχηματισμός Fourier μπορεί να οριστεί χρησιμοποιώντας ρίζες της ενότητας σε [[Σώμα (άλγεβρα)|πεδία]] άλλα από των μιγαδικών αριθμών, και τέτοιες γενικεύσεις είναι κοινώς ονομάζεται ''αριθμός της θεωρίας μετατρέπει'' (NTTs) στην περίπτωση των [[Πεπερασμένο σώμα|πεπερασμένων πεδίων]]. Για περισσότερες πληροφορίες, δείτε τον αριθμό της θεωρίας μετατρέψει και διακριτός μετασχηματισμός Fourier (γενικά).
Πολλές από τις ιδιότητες του DFT εξαρτώνται μόνο από το γεγονός ότι <math>e^{-\frac{2 \pi i}{N}}</math> είναι μια [[Κυκλοτομικό σώμα|πρωτόγονη ρίζα της ενότητας]], μερικές φορές συμβολίζεται με <math>\omega_N</math> ή <math>W_N</math> (έτσι ώστε <math>\omega_N^N = 1</math>). Αυτές οι ιδιότητες περιλαμβάνουν την πληρότητα, την καθετότητα, Plancherel/Parseval, περιοδικότητα, αλλαγή, συνέλιξη, και μεμονομές ιδιότητες παραπάνω, καθώς και πολλούς FFT αλγόριθμους. Για το λόγο αυτό, ο διακριτός μετασχηματισμός Fourier μπορεί να οριστεί χρησιμοποιώντας ρίζες της ενότητας σε [[Σώμα (άλγεβρα)|πεδία]] άλλα από των μιγαδικών αριθμών, και τέτοιες γενικεύσεις είναι κοινώς γνωστές ως ''αριθμιτική-θεωρητικοί μετασχηματισμοί'' (NTTs) στην περίπτωση των [[Πεπερασμένο σώμα|πεπερασμένων πεδίων]]. Για περισσότερες πληροφορίες, δείτε τον [[Αριθμητικός-θεωρητικός μετασχηματισμός|αριθμητικό-θεωρητικό μετασχηματισμό]] και τον διακριτό μετασχηματισμό Fourier (γενικά).


=== Άλλα πεπερασμένων ομάδων ===
=== Άλλα πεπερασμένα σύνολα ===
Το πρότυπο DFT πράξεις σε μια ακολουθία ''x''<sub>0</sub>, ''x''<sub>1</sub>, ..., ''x''<sub>''N''&#x2212;1</sub> των μιγαδικών αριθμών, το οποίο μπορεί να θεωρηθεί ως μια συνάρτηση {0, 1, ..., ''N'' &#x2212; 1} → '''C'''. Η πολυδιάστατη DFT πράξεις πολυδιάστατων ακολουθιών, η οποία μπορεί να θεωρηθεί ως λειτουργίες
Το πρότυπο DFT δρα σε μια ακολουθία ''x''<sub>0</sub>, ''x''<sub>1</sub>, ..., ''x''<sub>''N''&#x2212;1</sub> μιγαδικών αριθμών, η οποία μπορεί να θεωρηθεί ως μια συνάρτηση {0, 1, ..., ''N'' &#x2212; 1} → '''C'''. Η πολυδιάστατη DFT δρα σε πολυδιάστατες ακολουθίες, οι οποίες μπορούν να θεωρηθούν ως συναρτήσεις
: <math> \{0, 1, \ldots, N_1-1\} \times \cdots \times \{0, 1, \ldots, N_d-1\} \to \mathbb{C}. </math>
: <math> \{0, 1, \ldots, N_1-1\} \times \cdots \times \{0, 1, \ldots, N_d-1\} \to \mathbb{C}. </math>
Αυτό υποδηλώνει την γενίκευση να Fourier για την αυθαίρετη πεπερασμένων ομάδων, που δρουν στις συναρτήσεις ''G'' → '''C''' , όπου ''η G'' είναι μια πεπερασμένη ομάδα. Σε αυτό το πλαίσιο, το πρότυπο DFT είναι ο μετασχηματισμός Fourier σε μια κυκλική ομάδα, ενώ η πολυδιάστατη DFT είναι ένας μετασχηματισμός Fourier σε άμεσο άθροισμα των κυκλικών ομάδων.
Αυτό υποδηλώνει την γενίκευση σε [[Μετασχηματισμός Φουριέ σε πεπερασμένα σύνολα|μετασχηματισμούς Fourier σε αυθαίρετα πεπερασμένα σύνολα]], που δρουν σε συναρτήσεις ''G'' → '''C''' , όπου ''η G'' είναι μια πεπερασμένη ομάδα. Σε αυτό το πλαίσιο, το πρότυπο DFT είναι ο μετασχηματισμός Fourier σε μια κυκλική ομάδα, ενώ η πολυδιάστατη DFT είναι ένας μετασχηματισμός Fourier σε άμεσο άθροισμα των κυκλικών ομάδων.


== Εναλλακτικές λύσεις ==
== Εναλλακτικές λύσεις ==

Έκδοση από την 21:42, 9 Ιουνίου 2016

Σχέση μεταξύ του (συνεχούς) μετασχηματισμού Fourier και του διακριτού μετασχηματισμού Fourier. Αριστερή στήλη: μία συνεχής συνάρτηση (επάνω) και ο μετασχηματισμός της σε Fourier (κάτω). Κέντρο-αριστερή στήλη: Περιοδική άθροιση της αρχικής συνάρτησης (κορυφή). Μετασχηματισμός Fourier (κάτω μέρος) είναι μηδέν εκτός από τα διακριτά σημεία. Ο αντίστροφος μετασχηματισμός είναι ένα άθροισμα ημιτονοειδών και ονομάζεται σειρά Fourier. Κέντρο-δεξιά στήλη: Η αρχική συνάρτηση διακριτοποιείται (πολλαπλασιάζεται με το Dirac comb ) (κορυφή). O μετασχηματισμός της σε Fourier (κάτω μέρος) είναι μια περιοδική άθροιση (DTFT: Διακριτού-χρόνου μετασχηματισμό Fourier ) του αρχικού μετασχηματισμού της. Δεξιά στήλη: Το DFT(Διακριτός μετασχηματισμός Fourier) (κάτω) υπολογίζει διακριτά δείγματα της συνεχούς DTFT. Ο αντίστροφος DFT (κορυφή) είναι περιοδική άθροιση των αρχικών δειγμάτων. O FFT(γρήγορος μετασχηματισμός Fourier) αλγόριθμος υπολογίζει έναν κύκλο του DFT και το αντίστροφο του είναι ένας κύκλος του αντίστροφου DFT.
Η Απεικόνιση ενός μετασχηματισμού Fourier (πάνω αριστερά) και η περιοδική του άθροιση (DTFT) στην κάτω αριστερή γωνία. Οι φασματικές ακολουθίες (a) επάνω δεξιά και (b) κάτω δεξιά, αντίστοιχα, υπολογίζονται από την (α) ένα κύκλο του περιοδικού αθροίσματος s(t) και (β) ένα κύκλο του περιοδικού αθροίσματος της s(nT) ακολουθίας. Οι αντίστοιχοι τύποι είναι (α) το ολοκλήρωμα της σειρά Fourier και (β) του DFT (διακριτός μετασχηματισμός Fourier) άθροιση. Οι ομοιότητες με το αρχικό μετασχηματισμό, S(f), και η σχετική υπολογιστική ευκολία είναι συχνά το κίνητρο για τον υπολογισμό μιας DFT ακολουθίας.

Στα μαθηματικά, ο διακριτός μετασχηματισμός Fourier (DFT) μετατρέπει μια πεπερασμένη ακολουθία από ίσα διαστήματα δειγμάτων από μια συνάρτηση σε μία λίστα με συντελεστές από ένα πεπερασμένο συνδυασμό ημιτονοειδών μιγαδικών αριθμών, καθορισμένων από τις συχνότητες τους, που έχει τις ίδιες τιμές δείγματος. Αυτό μπορεί να ειπωθεί για τη μετατροπή του δείγματος της συνάρτησης από το αρχικό του πεδίο ορισμού (συχνά το χρόνο ή τη θέση κατά μήκος της γραμμής) στο πεδίο της συχνότητας.

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

Ο DFT είναι ο πιο σημαντικός διακριτός μετασχηματισμός, που χρησιμοποιείται για να εκτελέσει την ανάλυση Fourier σε πολλές πρακτικές εφαρμογές.[1] Στην ψηφιακή επεξεργασία σήματος, η συνάρτηση είναι οποιαδήποτε ποσότητα ή σήμα που ποικίλει με την πάροδο του χρόνου, όπως η πίεση των ηχητικών κυμάτων, ένα σήμα ραδιοφώνου ή ημερήσιες μετρήσεις της θερμοκρασίας, δειγματοληψίες πάνω από ένα πεπερασμένο χρονικό διάστημα (συνήθως ορίζεται από μία συνάρτηση παραθύρου[2]). Στην επεξεργασία εικόνας, τα δείγματα μπορεί να είναι οι τιμές των pixels κατά μήκος της γραμμής ή της στήλης των εικόνων raster. Ο DFT , επίσης, χρησιμοποιείται για την αποτελεσματική επίλυση μερικών διαφορικών εξισώσεων, και για να εκτελέσει άλλες ενέργειες, όπως ο συσχετισμός συναρτήσεων ή ο πολλαπλασιασμός μεγάλων ακεραίων.

Δεδομένου ότι πρόκειται για ένα πεπερασμένο ποσό των δεδομένων, μπορεί να εφαρμοστεί σε υπολογιστές με αριθμητικούς αλγόριθμους ή ακόμα και με ειδικά υλικά. Αυτές οι εφαρμογές συνήθως χρησιμοποιούν αποτελεσματικά τον γρήγορο μετασχηματισμό Fourier (FFT) σε αλγορίθμους;[3] τόσο πολύ, που οι όροι "FFT" και "DFT" συχνά χρησιμοποιούνται εναλλακτικά. Πριν από την τρέχουσα χρήση, το "FFT" μπορεί επίσης να έχει χρησιμοποιηθεί για τον ασαφή όρο "πεπερασμένος μετασχηματισμός Fourier".

Ορισμός

Η ακολουθία των N μιγαδικών αριθμών μετατρέπεται σε μία N-περιοδική ακολουθία μιγαδικών αριθμών:

Λόγω της περιοδικότητας, το σύνηθες πεδίο ορισμού της k υπολογίζεται ότι είναι το [0, N − 1]. Αυτή είναι η περίπτωση ισχύει πάντα, όταν ο DFT υλοποιείται μέσω του αλγόριθμου για τον γρήγορα μετασχηματισμό Fourier(FFT). Αλλά και άλλες κοινές περιοχές είναι το [−N/2, N/2 − 1] (N άρτιος ) και [−(N − 1)/2, (N − 1)/2] (N περιττός), όπως όταν το αριστερό και το δεξί ήμισυ ενός FFT ως αποτέλεσμα μιας ακολουθίας έχουν ανταλλαχθεί.[4]

Ο μετασχηματισμός μερικές φορές συμβολίζεται με το σύμβολο , όπως και ή ή .[note 1]

Eq.1 μπορεί να ερμηνευθεί ή να περιγραφεί με διάφορους τρόπους, για παράδειγμα:

  • Περιγράφει πλήρως τον διακριτού χρόνου μετασχηματισμό Fourier (DTFT) μιας N-περιοδικής ακολουθίας, η οποία περιλαμβάνει μόνο στοιχεία με διακριτή συχνότητα . (Χρησιμοποιώντας τον DTFT με περιοδικά δεδομένα)
  • Μπορεί επίσης να παρέχει ομοιόμορφα κατανεμημένα δείγματα της συνεχούς DTFT μιας πεπερασμένου μήκους ακολουθία. (Δειγματοληψία του DTFT)
  • Είναι η οριζόντια συσχέτιση της εισαγώμενης ακολουθίας xn, και μία μιγαδικά ημιτονοειδής στη συχνότητα k/N. Έτσι λειτουργεί σαν ένα προσαρμοσμένο φίλτρο για αυτή τη συχνότητα.
  • Είναι μία διακριτή αναλογία του τύπου για τους συντελεστές της σειράς Fourier:
η οποίο είναι, επίσης, N-περιοδική. Για πεδίο ορισμού αυτό είναι ο αντίστροφος μετασχηματισμός του Eq.1. Σε αυτή την ερμηνεία, το κάθε είναι ένας μιγαδικός αριθμός που κωδικοποιεί και το εύρος και τη φάση του μια ημιτονοειδή συνιστώσα της συνάρτησης Η ημιτονοειδής συχνότητα είναι k κύκλους ανά N δείγματα. Το εύρος της και η φάση της είναι:
πού atan2 είναι μία μορφή της arctan συνάρτησης.

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

Στη συζήτηση που ακολουθεί οι όροι "ακολουθία" και "διάνυσμα" θα θεωρούνται εναλλάξιμoi.

Χρησιμοποιώντας τον τύπο του Euler, ο DFT τύπος μπορεί να μετατραπεί σε τριγωνομετρικές μορφές που μερικές φορές χρησιμοποιείται στη μηχανική και την επιστήμη των υπολογιστών:

Μετασχηματισμός Fourier:

Αντίστροφος μετασχηματισμός Fourier:

N = αριθμός των δείγματων που έχουμε
n = το τρέχον δείγμα που εξετάζουμε (0, ..., N − 1)
xn = αξία του συμβόλου στο χρόνο n
k = τρέχουσα συχνότητα που εξετάζουμε (0 Hertz έως N-1 Hertz)
Xk = ποσό της συχνότητας k στο σύμβολο (το εύρος και τη φάση, ένας μιγαδικός αριθμός)

Ιδιότητες

Πληρότητα

Ο διακριτός μετασχηματισμός Fourier είναι ένας αντιστρέψιμος, γραμμικός μετασχηματισμός

με το που σημαίνει το σύνολο των μιγαδικών αριθμών. Με άλλα λόγια, για κάθε N > 0, ένα N-διαστάσεων μιγαδικό διάνυσμα έχει ένα DFT και IDFT τα οποία είναι με τη σειρά τους N-διαστάσεων μιγαδικά δiανύσματα.

Καθετότητα

Τα διανύσματα σχηματίζουν μια ορθογώνια βάση πάνω από το σύνολο των N-διαστάσεων μιγαδικών διανυσμάτων:

πού είναι το δέλτα του Kronecker. (Στο τελευταίο βήμα, το άθροισμα είναι ασήμαντο αν , όπου είναι 1+1+⋅⋅⋅=N, και το αντίθετο, είναι μια γεωμετρική σειρά που μπορεί να αθροιστεί αναλυτικώς για να αποκτήσει το μηδέν.) Αυτή η συνθήκη της καθετότητας μπορεί να χρησιμοποιηθεί για να αποκομίσει τον τύπο για την IDFT από τον ορισμό του DFT, και είναι ισοδύναμο με τη μοναδική ιδιότητα παρακάτω.

Το Plancherel θεώρημα και το θεώρημα του Parseval

Αν Xk και Yk είναι το DFTs των xn και yn , αντίστοιχα, τότε το θεώρημα του Parseval παραθέτει:

όπου ο αστερίσκος δηλώνει συζυγή μιγαδικό αριθμό.Το Plancherel θεώρημα είναι μια ειδική περίπτωση από το θεώρημα του Parseval και παραθέτει:

Αυτά τα θεωρήματα είναι επίσης ισοδύναμο με τη μοναδική συνθήκη παρακάτω.

Περιοδικότητα

Η περιοδικότητα μπορεί να αποδειχθεί άμεσα από τον ορισμό:

Ομοίως, μπορεί να αποδειχθεί ότι ο τύπος IDFT οδηγεί σε μια περιοδική επέκταση.

Θεώρημα μετατόπισης

Πολλαπλασιάζοντας με μία γραμμική φάση για κάποιο ακέραιο m αντιστοιχεί σε μια κυκλική μετατόπιση των αποτελεσμάτων : αντικαθίσταται από , όπου ο δείκτης ερμηνεύεται ως αριθμητικό υπόλοιπο(του Νδηλαδή, σε τακτά χρονικά διαστήματα). Ομοίως, μια κυκλική μετατόπιση της εισόδου αντιστοιχεί σε πολλαπλασιασμό του αποτελέσματος από μια γραμμική φάση. Μαθηματικά, αν αντιπροσωπεύει το διάνυσμα x τότε

αν
στη συνέχεια
και

Κυκλική συνέλιξη θεώρημα και συσχέτισή τους θεώρημα

Το θεώρημα της συνέλιξης για το χρονικό-διακριτό μετασχηματισμό Fourier δείχνει ότι συνέλιξη των δύο άπειρων ακολουθιών μπορούν να ληφθούν ως ο αντίστροφος μετασχηματισμός των προϊόντων των ατομικών μετασχηματισμών. Μια σημαντική απλοποίηση προκύπτει όταν οι ακολουθίες έχουν πεπερασμένο μήκος, N. Όσον αφορά το DFT και το αντίστροφο DFT, μπορεί να γραφτεί ως εξής:

που είναι η συνέλιξη της ακολουθίας με μια ακολουθία εκτεταμένη σειρά περιοδικήσ άθροισης:

Ομοίως, η συσχέτισή της και δίνεται από:

Όταν κάθε ακολουθία περιέχει μια σειρά από μηδενικά, μήκους L, L+1 από τα αποτελέσματα των κυκλικών συνελέξεων είναι ισοδύναμα με τις αξίες των Μέθοδοι έχουν αναπτυχθεί επίσης για να χρησιμοποιηθεέ χρησιμοποιήσετε αυτό το ακίνητο ως μέρος μιας αποτελεσματικής διαδικασίας που κατασκευάζει με ένα ή ακολουθία δυνητικά πολύ περισσότερο από την πρακτική μετατρέψει μέγεθος (N). Δύο τέτοιες μέθοδοι είναι που ονομάζεται επικάλυψη-αποθήκευση και επικάλυψη-προσθήκη.[5] Η αποδοτικότητα προκύπτει από το γεγονός ότι μια άμεση αξιολόγηση είτε άθροιση (παραπάνω) απαιτεί από τις επιχειρήσεις για την παραγωγή ακολουθία μήκους N. Μια έμμεση μέθοδο, χρησιμοποιώντας μετασχηματισμούς, μπορούν να επωφεληθούν από την απόδοση του fast Fourier transform (FFT) για να επιτύχει πολύ καλύτερες επιδόσεις. Επιπλέον, οι περιελίξεις μπορούν να χρησιμοποιηθούν για την αποτελεσματική υπολογιστική DFTs μέσω Rader αλγόριθμο FFT και Bluestein είναι αλγόριθμο FFT.

Θεώρημα συνέλιξης δυαδικότητα

Μπορεί, επίσης, να αποδειχθεί ότι:

  που είναι η κυκλική συνέλιξη των και .

Τριγωνομετρικό πολυώνυμο παρεμβολής

Το τριγωνομετρικό πολυώνυμο παρεμβολής

για N ακόμη ,
για N περιττός,

όπου οι συντελεστές του Xk δίνεται από τον DFT της xn ανωτέρω, πληροί τις παρεμβολή τοποθεσία για .

Ακόμα και για N, παρατηρούμε ότι η συχνότητα Nyquist στοιχείο αντιμετωπίζεται ειδικά.

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

Σε αντίθεση, η πιο προφανής τριγωνομετρικό πολυώνυμο παρεμβολής είναι εκείνο στο οποίο οι συχνότητες κυμαίνονται από 0 έως (αντί των περίπου να όπως παραπάνω), παρόμοιο με το inverse DFT φόρμουλα. Αυτή η παρεμβολή δεν δεν ελαχιστοποιήσει την κλίση, και όχι γενικά πραγματική αξία για την πραγματική * η χρήση του είναι ένα κοινό λάθος.

Το ενιαίο DFT

Ένα άλλο τρόπο θεώρησης του DFT είναι να σημειωθεί ότι στην παραπάνω συζήτηση, ο DFT μπορεί να εκφράζεται ως ο DFT matrix, Vandermonde matrix, που εισήγαγε ο Σιλβέστερ το 1867,

πού

είναι μια πρωτόγονη Νιοστή ρίζα της ενότητας.

Το αντίστροφο μετασχηματισμό, στη συνέχεια, δίνεται από το αντίστροφο του παραπάνω πίνακα,

Με ενιαία εξομάλυνση σταθερές , το DFT γίνεται ένα ενιαίο μετασχηματισμού, που ορίζεται από μια ενιαία μήτρα:

όπου det() είναι η ορίζουσα λειτουργία. Η ορίζουσα είναι το γινόμενο των ιδιοτιμών, η οποία είναι πάντα ή όπως περιγράφεται παρακάτω. Σε ένα πραγματικό διανυσματικό χώρο, ένα ενιαίο μετασχηματισμού μπορεί να θεωρηθεί ως απλά ένα άκαμπτο περιστροφή του συστήματος συντεταγμένων, καθώς και όλες τις ιδιότητες ενός στερεού περιστροφής μπορεί να βρεθεί στο ενιαίο DFT.

Η καθετότητα του DFT είναι τώρα εκφράζεται ως orthonormality κατάσταση (η οποία προκύπτει σε πολλούς τομείς των μαθηματικών, όπως περιγράφεται στην ρίζα της ενότητας):

Αν X ορίζεται ως το ενιαίο DFT του διανύσματος x, τότε

και το Plancherel θεώρημα εκφράζεται ως

Αν δείτε το DFT ως ένα μετασχηματισμού συντεταγμένων, η οποία απλώς καθορίζει τις συνιστώσες ενός διανύσματος σε ένα νέο σύστημα συντεταγμένων, τότε η παραπάνω είναι η δήλωση ότι η τελεία γινόμενο των δύο διανυσμάτων διατηρείται κάτω από ένα unitary μετασχηματισμό DFT. Για την ειδική περίπτωση , αυτό σημαίνει ότι το μήκος ενός διανύσματος είναι διατηρημένα, καθώς και—αυτό είναι το θεώρημα του Parseval,

Συνέπεια της κυκλικής συνέλιξης θεώρημα είναι ότι ο DFT matrix F diagonalizes κάθε circulant μήτρα.

Εκφράζοντας την inverse DFT όσον αφορά το DFT

Μια χρήσιμη ιδιότητα του DFT είναι ότι το inverse DFT μπορεί εύκολα να εκφράζεται σε όρους της (προς τα εμπρός) DFT, μέσω διαφόρων γνωστά "κόλπα". (Για παράδειγμα, σε υπολογισμούς, είναι συχνά βολικό να εφαρμόσει ένα fast Fourier transform αντιστοιχεί σε μία κατεύθυνση μετασχηματισμού και, στη συνέχεια, να πάρει την άλλη κατεύθυνση μετασχηματισμού από την πρώτη.)

Πρώτα, μπορούμε να υπολογίσουμε τον αντίστροφο DFT αντιστρέφοντας τις εισόδους (Duhamel et al., 1988):

(Ως συνήθως, οι δείκτες ερμηνεύονται modulo N * έτσι, για να έχουμε .)

Δεύτερον, κάποιος μπορεί επίσης να συζευχθεί το εισόδους και εξόδους:

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

Δηλαδή, το αντίστροφο μετασχηματισμό είναι η ίδια με την προς τα εμπρός μετατρέψει πραγματικά και φανταστικά μέρη αντάλλαξαν τόσο για την εισαγωγή και την παραγωγή, μέχρι την ομαλοποίηση (Duhamel et al., 1988).

Η σύζευξη κόλπο μπορεί επίσης να χρησιμοποιηθεί για να ορίσετε ένα νέο μετασχηματισμό, που σχετίζονται στενά με τον DFT, που είναι involutory—που είναι, που είναι το δικό αντίστροφο. Ειδικότερα, είναι καθαρά δική inverse: . Μια στενά συνδεδεμένη involutory μετασχηματισμού (με το συντελεστή (1+i) /√2) , δεδομένου ότι οι παράγοντες να ακυρώσει το 2. Για την πραγματική εισροές , το πραγματικό μέρος του δεν είναι άλλη από την διακριτού μετασχηματισμού Hartley, η οποία είναι επίσης involutory.

Ιδιοτιμές και ιδιοδιανύσματα

Οι ιδιοτιμές του DFT matrix είναι απλό και γνωστό, ότι τα ιδιοδιανύσματα είναι περίπλοκο, δεν είναι μοναδική, και αποτελούν αντικείμενο της εν εξελίξει έρευνας.

Σκεφτείτε την ενιαία μορφή που ορίζεται ανωτέρω για τον DFT μήκους N, όπου

Η μήτρα αυτή ικανοποιεί το matrix πολυωνυμική εξίσωση:

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

Συνεπώς, οι ιδιοτιμές του είναι η τέταρτη ρίζες της ενότητας: +1, -1, +i, −i.

Δεδομένου ότι υπάρχουν μόνο τέσσερις διακριτές ιδιοτιμές για αυτό το matrix, έχουν κάποια πολλαπλότητα. Η πολλαπλότητα δίνει τον αριθμό των γραμμικά ανεξάρτητων ιδιοδιανυσμάτων που αντιστοιχούν σε κάθε ιδιοτικών. (Σημειώστε ότι υπάρχουν N ανεξάρτητα ιδιοδιανύσματα, μια ενιαία μήτρα δεν είναι ελαττωματικό.)

Το πρόβλημα της πολλαπλότητας λύθηκε με McClellan και Πάρκα (1972), αν και αργότερα φαίνεται να έχουν ισοδύναμη με το πρόβλημα λύθηκε από τον Gauss (Dickinson και Steiglitz, 1982). Το πλήθος εξαρτάται από την τιμή του N modulo 4, και δίνεται από τον ακόλουθο πίνακα:

Οι πολλαπλότητες του ιδιοτιμές λ του ενιαίου DFT matrix U ως συνάρτηση του μετασχηματισμού μέγεθος N (σε σχέση με ένα ακέραιο m).
μέγεθος N λ = +1 λ = -1 λ = - - λ = + -
4m m + 1 m m m − 1
4m + 1 m + 1 m m m
4m + 2 m + 1 m + 1 m m
4m + 3 m + 1 m + 1 m + 1 m

Αναφέρεται διαφορετικά, το χαρακτηριστικό πολυώνυμο του είναι:

Όχι απλό αναλυτικό τύπο για τη γενική ιδιοδιανύσματα είναι γνωστή. Επιπλέον, τα ιδιοδιανύσματα δεν είναι μοναδική, επειδή κάθε γραμμικός συνδυασμός των ιδιοδιανυσμάτων για τις ίδιες ιδιοτιμές είναι, επίσης, ένα ιδιοδιάνυσμα για ιδιοτικών. Διάφοροι ερευνητές έχουν προτείνει διάφορες επιλογές των ιδιοδιανυσμάτων, επιλεγμένα για να ικανοποιήσουν χρήσιμες ιδιότητες, όπως η καθετότητα και να "απλές" μορφές (π. χ., McClellan και Πάρκα, Το 1972, Dickinson και Steiglitz, Το 1982, Grünbaum, Το 1982, Atakishiyev και Wolf, 1997; Candan et al., Το 2000 * Hanna et al., Το 2004 * Gurevich και Hadani, 2008).

Μια απλή προσέγγιση είναι να discretize μια eigenfunction του συνεχούς μετασχηματισμού Fourier, των οποίων η πιο γνωστή είναι η Gaussian συνάρτηση. Από την περιοδική άθροιση της συνάρτησης σημαίνει discretizing το φάσμα συχνοτήτων και διακριτοποίηση περιοδική άθροιση του φάσματος, το discretized και περιοδικά αθροίζονται Gaussian συνάρτηση αποδίδει ένα ιδιοδιάνυσμα του διακριτού μετασχηματισμού:

  • .
Κλειστή μορφή έκφρασης της σειράς δεν είναι γνωστή, αλλά συγκλίνει γρήγορα.

Δύο άλλα απλή κλειστή μορφή αναλυτικών ιδιοδιανύσματα για την ειδική DFT περίοδο N βρέθηκαν Κονγκ, 2008):

Για DFT περίοδο N = 2Λ + 1 = 4Κ +1, όπου K είναι ένας ακέραιος, το ακόλουθο είναι ένα ιδιοδιάνυσμα του DFT:

Για DFT περίοδο N = 2L = 4K, όπου K είναι ένας ακέραιος, το ακόλουθο είναι ένα ιδιοδιάνυσμα του DFT:

Η επιλογή των ιδιοδιανυσμάτων του DFT μήτρα έχει εξελιχθεί σημαντικά κατά τα τελευταία έτη, προκειμένου να καθορίσει ένα διακριτό ανάλογο του κλασματική Fourier transform—DFT matrix μπορούν να ληφθούν για να κλασματική εξουσίες από exponentiating οι ιδιοτιμές (π. χ., Rubio και Santhanam, 2005). Η συνεχής μετασχηματισμός Fourier, το φυσικό ορθογώνια eigenfunctions αποτελούν τον hermite λειτουργίες, έτσι ώστε τα διάφορα διακριτά ανάλογα από αυτά έχουν χρησιμοποιηθεί ως ιδιοδιανύσματα του DFT, όπως ο Kravchuk πολυώνυμα (Atakishiyev και Wolf, 1997). Η "καλύτερη" επιλογή των ιδιοδιανυσμάτων για να ορίσετε μια κλασματικός μετασχηματισμός Fourier διακριτού παραμένει ένα ανοιχτό ερώτημα, όμως.

Η αρχή της αβεβαιότητας

Αν η τυχαία μεταβλητή Xk περιορίζεται από

τότε

μπορεί να θεωρηθεί ότι αντιπροσωπεύει μια διακριτή συνάρτηση μάζας πιθανότητας του n, με μια σχετική συνάρτηση μάζας πιθανότητας κατασκευασμένη από τη μετασχηματισμένη μεταβλητή,

Για την περίπτωση των συνεχών συναρτήσεων και , η απροσδιοριστία του Heisenberg δηλώνει ότι

όπου και είναι οι διακυμάνσεις του και , αντίστοιχα, με την ισότητα να επιτυγχάνεται σε περίπτωση κατάλληλα κανονικοποιημένης κατανομής κατά Gauss. Αν και οι αποκλίσεις μπορεί να ορίζονται αναλόγως για το DFT, μια ανάλογη αρχή της αβεβαιότητας δεν είναι χρήσιμη, διότι η αβεβαιότητα δεν θα μετατόπιση-αμετάβλητης. Ακόμα, μια σημαντική αρχή της αβεβαιότητας έχει εισαχθεί από τους Massar και Spindel.[6]

Ωστόσο, η αβεβαιότητα εντροπίας του Hirschman θα έχει μία χρήσιμη αναλογία για την περίπτωση του DFT.[7] Η αρχή της αβεβαιότητας του Hirschman εκφράζεται με την εντροπία Shannon των δύο συναρτήσεων πιθανότητας.

Στην διακριτή περίπτωση, η εντροπίες Shannon ορίζονται ως

και

και η αρχή της αβεβαιότητας εντροπίας γίνεται[7]

Η ισότητα λαμβάνεται για ίσο με μεταφράσεις και διαμορφώσεις ενός κατάλληλα κανονικοποιημένου Kronecker comb της περιόδου , όπου είναι οποιοσδήποτε ακριβής ακέραιος διαιρέτης του .Η συνάρτηση μάζας πιθανότητας τότε θα είναι ανάλογη με ένα κατάλληλα μεταφρασμένο Kronecker comb της περιόδου .[7]

Υπάρχει, επίσης, μία πολύ γνωστή ντετερμινιστική αρχή της αβεβαιότητας που χρησιμοποιεί το σήμα σπανιότητας (ή ο αριθμός των μη μηδενικών συντελεστών).[8] Ας είναι και ο αριθμός των μη μηδενικών στοιχείων των ακολουθιών χρόνου και συχνότητας αντίστοιχα. Τότε,

Ως άμεση συνέπεια της ανισότητας των αριθμητικών και γεωμετρικών μέσων , πρέπει επίσης . Και οι δύο αρχές αβεβαιότητας έδειξαν να είναι σφιχτές για ειδικά επιλεγμένες ακολουθίες-"φράχτη" (διακριτής ώθησης τραίνα), και έχουν πρακτική εφαρμογή για εφαρμογές ανάκτησης σήματος.[8]

Το πραγματικής-εισόδου DFT

Αν είναι πραγματικοί αριθμοί, όπως συμβαίνει συχνά σε πρακτικές εφαρμογές τότε το DFT υπακούει στη συμμετρία:

  όπου υποδηλώνει συζυγή μιγαδικό.

Έπεται ότι τα X0 και XN/2 είναι πραγματικοί αριθμοί , και το υπόλοιπο του DFT είναι εντελώς καθορισμένο από ακριβώς N/2-1 μιγαδικούς αριθμούς.

Γενικευμένος DFT (μετατοπισμένη και μη-γραμμική φάση)

Είναι δυνατό να μετατοπίσει την δειγματοληψία μετασχηματισμού στο χρόνο και/ή στο πεδίο συχνοτήτων κάποιες πραγματικές μετατοπίσεις α και β, αντίστοιχα. Αυτό είναι μερικές φορές γνωστό ως ένας γενικευμένος DFTGDFT), που ονομάζεται επίσης μετατοπισμένος DFT ή όφσετ DFT, και έχει ανάλογες ιδιότητες με το συνηθισμένο DFT:

Πιο συχνά,χρησιμοποιούνται μετατοπίσεις (μισό δείγμα).Ενώ ο συνήθης DFT αντιστοιχεί σε ένα περιοδικό σήμα τόσο σε χρόνο όσο και στο πεδίο συχνοτήτων , για παράγει ένα σήμα που είναι αντι-περιοδικό στο πεδίο της συχνότητας () και αντίστροφα, για .Έτσι, η συγκεκριμένη περίπτωση είναι γνωστή ως ένας περίεργου χρόνου περίεργης συχνότητας διακριτός μετασχηματισμός Fourier (ή O2DFT).Έτσι οι μετατοπίσεις μετασχηματισμών χρησιμοποιούνται πιο συχνά για συμμετρικά δεδομένα, για να αντιπροσωπεύουν διαφορετικών ορίων συμμετρίες και για πραγματικά συμμετρικά δεδομένα που αντιστοιχούν σε διαφορετικές μορφές του διακριτού μετασχηματισμού συνημιτόνου και ημιτόνου.

Μια άλλη ενδιαφέρουσα επιλογή είναι , η οποία ονομάζεται επίκεντρο DFTCDFT). Το επίκεντρο DFT έχει την χρήσιμη ιδιότητα ότι, όταν το N είναι πολλαπλάσιο του τέσσερα,και οι τέσσερις ιδιοτιμές του (βλ. παραπάνω) έχουν ίσες πολλαπλότητες (Rubio και Santhanam, 2005)[9]

Ο όρος GDFT χρησιμοποιείται επίσης για τη μη-γραμμική φάση των επεκτάσεων του DFT. Ως εκ τούτου,η GDFT μέθοδος παρέχει μια γενίκευση για σταθερού πλάτους ορθογώνιους μετασχηματισμούς μπλοκ συμπεριλαμβανομένων των γραμμικών και μη-γραμμικών τύπων φάσης.Το GDFT είναι ένα πλαίσιο για τη βελτίωση των ιδιοτήτων του χρόνου και του πεδίου της συχνότητας του παραδοσιακού DFT, π. χ. αυτόματη/διασταύρωση-συσχέτιση, με την προσθήκη της κατάλληλα σχεδιασμένης λειτουργίας μορφοποίησης φάσης (μη-γραμμική, σε γενικές γραμμές) στις αρχικές λειτουργίες γραμμικής φάσης (Akansu και Agirman-Tosun, 2010).η[10]

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

Πολυδιάστατος DFT

Το συνηθισμένο DFT μετατρέπει μια μονοδιάστατη ακολουθία ή σειρά που είναι μια συνάρτηση με ακριβώς μία διακριτή μεταβλητή n. Ο πολυδιάστατος DFT ενός πολυδιάστατου πίνακα που είναι συνάρτηση των d διακριτών κεταβλητών για σε , ορίζεται από:

όπου ως ανωτέρω και το δ δείκτες εξόδου με τιμές από . Αυτό είναι πιο συμπαγώς εκφράσμένο σε διανυσματική μορφή, όπου ορίζουμε και ως d-διαστάσεων διανύσματατα των δεικτών από 0 μέχρι , το οποίο ορίζουμε ως :

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

Το αντίστροφο του πολυδιάστατου DFT , ανάλογα με την μονοδιάστατη περίπτωση, δίνεται από:

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

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

Ένας αλγόριθμος για τον υπολογισμό ενός μονοδιάστατου DFT είναι συνεπώς επαρκές για τον αποτελεσματικό υπολογισμό ενός πολυδιάστατου DFT. Αυτή η προσέγγιση είναι γνωστή ως αλγόριθμος γραμμή-στήλη. Υπάρχουν επίσης εγγενώς πολυδιάστατοι FFT αλγόριθμοι.

Πραγματικής-εισόδου πολυδιάστατοι DFT

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

όπου το αστέρι και πάλι δηλώνει σύνθεση μιγαδικών και ο -ος δείκτης ερμηνεύεται και πάλι με modulo (για ).

Εφαρμογές

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

Φασματική ανάλυση

Όταν ο DFT χρησιμοποιείται για σημειακή φασματική ανάλυση, η ακολουθία συνήθως αντιπροσωπεύει ένα πεπερασμένο σύνολο ομοιόμορφα κατανεμημένων χρονικών δειγμάτων κάποιου σήματος , όπου t είναι ο χρόνος. Η μετατροπή από το συνεχή χρόνο σε δείγματα (διακριτός χρόνος) αλλάζει το υποκείμενο μετασχηματισμός Fourier του x(t) σε ένα διακριτού χρόνου μετασχηματισμό Fourier (DTFT), το οποίο συνήθως συνεπάγεται ένα είδος παραμόρφωσης που λέγεται aliasing.Η επιλογή κατάλληλου δείγματος ρυθμού (βλέπε Nyquist rate) είναι το κλειδί για την ελαχιστοποίηση αυτής της στρέβλωσης. Επίσης, η μετατροπή από μία πολύ μεγάλη (ή άπειρη) ακολουθία σε ένα διαχειρίσιμο μέγεθος συνεπάγεται ένα είδος παραμόρφωσης που ονομάζεται διαρροή, η οποία εκδηλώνεται ως απώλεια λεπτομέρειας.κ.α. ψήφισμα) του DTFT. Η επιλογή κατάλληλου μήκους υπο-ακολουθίας είναι το κύριο κλειδί για την ελαχιστοποίηση αυού του αποτελέσματος. Όταν τα διαθέσιμα δεδομένα (και ο χρόνος για να το επεξεργαστεί) είναι περισσότερα από το ποσό που απαιτείται για να επιτευχθεί η επιθυμητή ανάλυση συχνότητας, μια βασική τεχνική είναι να εκτελέσετε πολλούς DFTs, για παράδειγμα, για να δημιουργήσετε ένα φασματογράφημα. Αν το επιθυμητό αποτέλεσμα είναι ένα φάσμα ισχύος και ο θόρυβος ή η τυχαιότητα παρουσιάζονται στα δεδομένα, κατά μέσο όρο το μέγεθος των συστατικών των πολλαπλών DFTs είναι μια χρήσιμη διαδικασία για τη μείωση της διασποράς του φάσματος (που ονομάζεται επίσης ένα περιοδόγραμμα σε αυτό το πλαίσιο) . Δύο παραδείγματα τέτοιων τεχνικών είναι η Welch μέθοδος και η μέθοδος Bartlett, το γενικό αντικείμενο της εκτίμησης του φάσματος ισχύος ενός θορυβώδες σήματος ονομάζεται φασματική εκτίμηση.

Τελική πηγή παραμόρφωσης (ή ίσως την ψευδαίσθηση) είναι ο DFT ο ίδιος, επειδή είναι απλά μια διακριτή δειγματοληψία του DTFT, η οποία είναι μια συνάρτηση συνεχής στο πεδίο της συχνότητας. Αυτό μπορεί να αντιμετωπιστεί με την αύξηση της ανάλυσης του DFT. Η διαδικασία αυτή απεικονίζεται στη Δειγματοληψία του DTFT.

  • Η διαδικασία είναι μερικές φορές αναφέρεται ως zero-padding, η οποία είναι μια συγκεκριμένη εφαρμογή που χρησιμοποιείται σε συνδυασμό με τον αλγόριθμο fast Fourier transform (FFT). Η αναποτελεσματικότητα της εκτέλεσης πολλαπλασιασμών και προσθέσεων με το μηδενικής τιμής "δείγματα" είναι περισσότερη από ότι αντισταθμίζεται από την εγγενή αποτελεσματικότητα του FFT.
  • Όπως έχει ήδη σημειωθεί, η διαρροή επιβάλλει ένα όριο για την εγγενή ανάλυση του DTFT. Έτσι, υπάρχει ένα πρακτικό όριο για τα οφέλη που μπορούν να προκύψουν από έναν λεπτόκοκκο DFT.

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

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

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

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

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

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

Πολλαπλασιασμός πολυωνύμων.

Έστω ότι θέλουμε να υπολογίσουμε το γινόμενο πολυώνυμο γ(x) = a(x) · b(x). Η κανονική έκφραση γινομένου για τους συντελεστές του c περιλαμβάνει μια γραμμική (άκυκλη) συνέλιξη, όπου οι δείκτες δεν "εκτυλίσσονται γύρω". Αυτό μπορεί να ξαναγραφεί ως μια κυκλική συνέλιξη παίρνοντας τους διανυσματικούς συντελεστές για a(x) και b(x) με το σταθερό όρο πρώτα, μετά την προσάρτηση μηδενικών έτσι ώστε οι διανυσματικοί συντελεστές a και b που προκύπτον να έχουν διάσταση d > deg(a(x)) + deg(b(x)). Στη συνέχεια,

Όπου c είναι το διάνυσμα των συντελεστών του c(x), και η πράξη συνέλιξη ορίζεται έτσι

Αλλά η συνέλιξη γίνεται πολλαπλασιασμός μέσω του DFT:

Εδώ το γινόμενο διανυσμάτων προκύπτει στοιχειωδώς. Έτσι, οι συντελεστές του πολυωνυμικού γινομένου c(x) είναι οι όροι 0, ..., deg(a(x)) + deg(b(x)) του συντελεστή διάνυσμα

Με έναν ταχύ μετασχηματισμό Φουριέ, ο αλγόριθμος που προκύπτει παίρνει O (N log N) αριθμητικές πράξεις. Λόγω της απλότητας και της ταχύτητας, ο Couley-Tukey ΤΜΦ αλγόριθμος , ο οποίος περιορίζεται σε σύνθετα μεγέθη, συχνά επιλέγεται για το πράξη του μετασχηματισμού . Σε αυτή την περίπτωση, το d θα πρέπει να επιλέγεται ως ο μικρότερος ακέραιος που είναι μεγαλύτερος από το άθροισμα των εισόδων βαθμών πολυωνύμων που είναι παραγωγίσιμοι στις πρώτες παραγώγους (π. χ. 2, 3, και 5, ανάλογα με την υλοποίηση FFT).

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

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

Συνέλιξη

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

Κάποια διακριτός μετασχηματισμός Fourier ζεύγη

Some DFT pairs
Note
Shift theorem
Real DFT
from the geometric progression formula
from the binomial theorem
is a rectangular window function of W points centered on n=0, where W is an odd integer, and is a sinc-like function (specifically, is a Dirichlet kernel)
Discretization and periodic summation of the scaled Gaussian functions for . Since either or is larger than one and thus warrants fast convergence of one of the two series, for large you may choose to compute the frequency spectrum and convert to the time domain using the discrete Fourier transform.

Γενικεύσεις

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

Ο DFT μπορεί να ερμηνευθεί ως η μιγαδική τιμή εκπροσώπησης θεωρίας της πεπερασμένης κυκλικής ομάδας. Με άλλα λόγια, μια ακολουθία από n μιγαδικούς αριθμούς μπορεί να θεωρηθεί ως ένα στοιχείο του n-διάστατου χώρου μιγαδικών Cn ή αντίστοιχα μια συνάρτηση f από την πεπερασμένη κυκλική ομάδα τάξης n στους μιγαδικούς αριθμούς, το ZnC. Οπότε η f είναι μια συνάρτηση κλάσης σχετικά με την πεπερασμένη κυκλική ομάδα, και έτσι μπορεί να εκφραστεί ως γραμμικός συνδυασμός των αμείωτων χαρακτήρων αυτής της ομάδας, που είναι οι ρίζες της ενότητας.

Από αυτή την άποψη, μπορεί κανείς να γενικεύσει τον DFT για την εκπροσώπηση θεωρίας γενικά, ή πιο ειδικά για την εκπροσώπηση θεωρίας των πεπερασμένων ομάδων.

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

Άλλα πεδία

Πολλές από τις ιδιότητες του DFT εξαρτώνται μόνο από το γεγονός ότι είναι μια πρωτόγονη ρίζα της ενότητας, μερικές φορές συμβολίζεται με ή (έτσι ώστε ). Αυτές οι ιδιότητες περιλαμβάνουν την πληρότητα, την καθετότητα, Plancherel/Parseval, περιοδικότητα, αλλαγή, συνέλιξη, και μεμονομές ιδιότητες παραπάνω, καθώς και πολλούς FFT αλγόριθμους. Για το λόγο αυτό, ο διακριτός μετασχηματισμός Fourier μπορεί να οριστεί χρησιμοποιώντας ρίζες της ενότητας σε πεδία άλλα από των μιγαδικών αριθμών, και τέτοιες γενικεύσεις είναι κοινώς γνωστές ως αριθμιτική-θεωρητικοί μετασχηματισμοί (NTTs) στην περίπτωση των πεπερασμένων πεδίων. Για περισσότερες πληροφορίες, δείτε τον αριθμητικό-θεωρητικό μετασχηματισμό και τον διακριτό μετασχηματισμό Fourier (γενικά).

Άλλα πεπερασμένα σύνολα

Το πρότυπο DFT δρα σε μια ακολουθία x0, x1, ..., xN−1 μιγαδικών αριθμών, η οποία μπορεί να θεωρηθεί ως μια συνάρτηση {0, 1, ..., N − 1} → C. Η πολυδιάστατη DFT δρα σε πολυδιάστατες ακολουθίες, οι οποίες μπορούν να θεωρηθούν ως συναρτήσεις

Αυτό υποδηλώνει την γενίκευση σε μετασχηματισμούς Fourier σε αυθαίρετα πεπερασμένα σύνολα, που δρουν σε συναρτήσεις GC , όπου η G είναι μια πεπερασμένη ομάδα. Σε αυτό το πλαίσιο, το πρότυπο DFT είναι ο μετασχηματισμός Fourier σε μια κυκλική ομάδα, ενώ η πολυδιάστατη DFT είναι ένας μετασχηματισμός Fourier σε άμεσο άθροισμα των κυκλικών ομάδων.

Εναλλακτικές λύσεις

Υπάρχουν διάφορες εναλλακτικές λύσεις για τον DFT για διάφορες εφαρμογές, εξέχουσα μεταξύ των οποίων είναι κυματίδια. Το αναλογικό του DFT είναι η discrete wavelet transform (DWT). Από την άποψη του χρόνου–ανάλυση συχνότητας, ένα βασικό περιορισμό του μετασχηματισμού Fourier είναι ότι δεν περιλαμβάνει καταλύματος πληροφορίες, μόνο συχνότητας πληροφορίες, και έτσι έχει δυσκολία στην αντιπροσωπεύουν μεταβατικά φαινόμενα. Όπως κυματίδια έχουν θέση, καθώς και η συχνότητα, είναι καλύτερα σε θέση να αντιπροσωπεύουν τοποθεσία, σε βάρος μεγαλύτερη δυσκολία που αντιπροσωπεύει τη συχνότητα. Για λεπτομέρειες, ανατρέξτε σύγκριση των discrete wavelet transform, με το διακριτό μετασχηματισμό Fourier.

Δείτε επίσης

  • Companion matrix
  • DFT matrix
  • Fast Fourier transform
  • FFTPACK
  • FFTW
  • Γενικεύσεις του Pauli μήτρες
  • Λίστα Fourier που σχετίζονται με το μετατρέπει
  • Πολυδιάστατη μετατρέψει
  • Ο ζακ μετατρέψει

Σημειώσεις

  1. As a linear transformation on a finite-dimensional vector space, the DFT expression can also be written in terms of a DFT matrix; when scaled appropriately it becomes a unitary matrix and the Xk can thus be viewed as coefficients of x in an orthonormal basis.

Παραπομπές

  1. Strang, Gilbert (May–June 1994). «Wavelets». American Scientist 82 (3): 253. http://www.jstor.org/stable/29775194. Ανακτήθηκε στις 8 October 2013. «This is the most important numerical algorithm of our lifetime...». 
  2. Sahidullah, Md.; Saha, Goutam (Feb 2013). «A Novel Windowing Technique for Efficient Computation of MFCC for Speaker Recognition». IEEE Signal Processing Letters 20 (2): 149–152. doi:10.1109/LSP.2012.2235067. Bibcode2013ISPL...20..149S. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6387265&isnumber=6380557. 
  3. Cooley et al., 1969
  4. «Shift zero-frequency component to center of spectrum – MATLAB fftshift». http://www.mathworks.com/. Natick, MA 01760: The MathWorks, Inc. Ανακτήθηκε στις 10 Μαρτίου 2014.  Εξωτερικός σύνδεσμος στο |work= (βοήθεια)
  5. T. G. Stockham, Jr., "High-speed convolution and correlation," in 1966 Proc.
  6. Massar, S.; Spindel, P. (2008). «Uncertainty Relation for the Discrete Fourier Transform». Physical Review Letters 100 (19). doi:10.1103/PhysRevLett.100.190401. Bibcode2008PhRvL.100s0401M. 
  7. 7,0 7,1 7,2 DeBrunner, Victor; Havlicek, Joseph P.; Przebinda, Tomasz; Özaydin, Murad (2005). «Entropy-Based Uncertainty Measures for , and With a Hirschman Optimal Transform for ». IEEE Transactions on Signal Processing 53 (8): 2690. doi:10.1109/TSP.2005.850329. Bibcode2005ITSP...53.2690D. http://redwood.berkeley.edu/w/images/9/95/2002-26.pdf. Ανακτήθηκε στις 2011-06-23. 
  8. 8,0 8,1 Donoho, D.L.; Stark, P.B (1989). «Uncertainty principles and signal recovery». SIAM Journal on Applied Mathematics 49 (3): 906–931. doi:10.1137/0149053. 
  9. Santhanam, Balu; Santhanam, Thalanayar S. "Discrete Gauss-Hermite functions and eigenvectors of the centered discrete Fourier transform", Proceedings of the 32nd IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2007, SPTM-P12.4), vol.
  10. Akansu, Ali N.; Agirman-Tosun, Handan "Generalized Discrete Fourier Transform With Nonlinear Phase", IEEE Transactions on Signal Processing, vol. 58, no. 9, pp. 4547-4556, Sept. 2010.

Βιβλιογραφία

  • Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 0-13-307505-2. 
  • Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R. (1999). Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. ISBN 0-13-754920-2. CS1 maint: Πολλαπλές ονομασίες: authors list (link) CS1 maint: Multiple names: authors list (link)
  • Smith, Steven W. (1999). «Chapter 8: The Discrete Fourier Transform». The Scientist and Engineer's Guide to Digital Signal Processing (Second έκδοση). San Diego, Calif.: California Technical Publishing. ISBN 0-9660176-3-3. 
  • Cormen, Thomas H.· Charles E. Leiserson· Ronald L. Rivest· Clifford Stein (2001). «Chapter 30: Polynomials and the FFT». Introduction to Algorithms (Second έκδοση). MIT Press and McGraw-Hill. σελίδες 822–848. ISBN 0-262-03293-7.  esp. section 30.2: The DFT and FFT, pp. 830–838.
  • P. Duhamel; B. Piron; J. M. Etcheto (1988). «On computing the inverse DFT». IEEE Trans. Acoust., Speech and Sig. Processing 36 (2): 285–286. doi:10.1109/29.1519. 
  • J. H. McClellan; T. W. Parks (1972). «Eigenvalues and eigenvectors of the discrete Fourier transformation». IEEE Trans. Audio Electroacoust. 20 (1): 66–74. doi:10.1109/TAU.1972.1162342. 
  • Bradley W. Dickinson; Kenneth Steiglitz (1982). «Eigenvectors and functions of the discrete Fourier transform». IEEE Trans. Acoust., Speech and Sig. Processing 30 (1): 25–31. doi:10.1109/TASSP.1982.1163843.  (Note that this paper has an apparent typo in its table of the eigenvalue multiplicities: the +i/−i columns are interchanged. The correct table can be found in McClellan and Parks, 1972, and is easily confirmed numerically.)
  • F. A. Grünbaum (1982). «The eigenvectors of the discrete Fourier transform». J. Math. Anal. Appl. 88 (2): 355–363. doi:10.1016/0022-247X(82)90199-8. 
  • Natig M. Atakishiyev; Kurt Bernardo Wolf (1997). «Fractional Fourier-Kravchuk transform». J. Opt. Soc. Am. A 14 (7): 1467–1477. doi:10.1364/JOSAA.14.001467. Bibcode1997JOSAA..14.1467A. 
  • C. Candan; M. A. Kutay; H. M.Ozaktas (2000). «The discrete fractional Fourier transform». IEEE Trans. on Signal Processing 48 (5): 1329–1337. doi:10.1109/78.839980. Bibcode2000ITSP...48.1329C. 
  • Magdy Tawfik Hanna, Nabila Philip Attalla Seif, and Waleed Abd El Maguid Ahmed (2004). «Hermite-Gaussian-like eigenvectors of the discrete Fourier transform matrix based on the singular-value decomposition of its orthogonal projection matrices». IEEE Trans. Circ. Syst. I 51 (11): 2245–2254. doi:10.1109/TCSI.2004.836850.  CS1 maint: Multiple names: authors list (link)
  • Shamgar Gurevich; Ronny Hadani (2009). «On the diagonalization of the discrete Fourier transform». Applied and Computational Harmonic Analysis 27 (1): 87–99. doi:10.1016/j.acha.2008.11.003. preprint at. 
  • Shamgar Gurevich; Ronny Hadani; Nir Sochen (2008). «The finite harmonic oscillator and its applications to sequences, communication and radar». IEEE Transactions on Information Theory 54 (9): 4239–4253. doi:10.1109/TIT.2008.926440. preprint at. 
  • Juan G. Vargas-Rubio; Balu Santhanam (2005). «On the multiangle centered discrete fractional Fourier transform». IEEE Sig. Proc. Lett. 12 (4): 273–276. doi:10.1109/LSP.2005.843762. Bibcode2005ISPL...12..273V. 
  • J. Cooley, P. Lewis, and P. Welch (1969). «The finite Fourier transform». IEEE Trans. Audio Electroacoustics 17 (2): 77–85. doi:10.1109/TAU.1969.1162036.  CS1 maint: Multiple names: authors list (link)
  • F.N. Kong (2008). «Analytic Expressions of Two Discrete Hermite-Gaussian Signals». IEEE Trans. Circuits and Systems –II: Express Briefs. 55 (1): 56–60. doi:10.1109/TCSII.2007.909865. 

Εξωτερικοί σύνδεσμοι