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

καμία σύνοψη επεξεργασίας
[http://web.njit.edu/~akansu/PAPERS/AkansuIEEE-TSP2010.pdf "''Generalized Discrete Fourier Transform With Nonlinear Phase''"], IEEE ''Transactions on Signal Processing'', vol. 58, no. 9, pp. 4547-4556, Sept. 2010.</ref>
 
Ο διακριτός μετασχηματισμός Fourier μπορεί να θεωρηθεί ως μια ειδική περίπτωση του z[[Μετασχηματισμός-Z|μετασχηματισμού-z]], με τιμές στον μοναδιαίο κύκλο του μιγαδικού επιπέδου.Περισσότερο γενικοί z-μετασχηματισμοί αντιστοιχούν στις μετατοπίσεις μιγαδικών ''α'' και ''β'' ανωτέρω.
 
== Πολυδιάστατος DFT ==
Το συνηθισμένο DFT μετατρέπει μια μονοδιάστατη ακολουθία ή [[Πίνακας (μαθηματικά)|σειρά]] <math>x_n</math> που είναι μια συνάρτηση με ακριβώς μία διακριτή μεταβλητή n. Ο πολυδιάστατος DFT ενός πολυδιάστατου πίνακα <math>x_{n_1, n_2, \dots, n_d}</math> που είναι συνάρτηση των ''d'' διακριτών κεταβλητώνμεταβλητών <math>n_\ell = 0, 1, \dots, N_\ell-1</math> για <math>\ell</math> σε <math>1, 2, \dots, d</math> , ορίζεται από:
: <math>X_{k_1, k_2, \dots, k_d} = \sum_{n_1=0}^{N_1-1} \left(\omega_{N_1}^{~k_1 n_1} \sum_{n_2=0}^{N_2-1} \left( \omega_{N_2}^{~k_2 n_2} \cdots \sum_{n_d=0}^{N_d-1} \omega_{N_d}^{~k_d n_d}\cdot x_{n_1, n_2, \dots, n_d} \right) \right) \, , </math>
όπου <math>\omega_{N_\ell} = \exp(-2\pi i/N_\ell)</math> ως ανωτέρω και το ''δ'' δείκτες εξόδου με τιμές από <math>k_\ell = 0, 1, \dots, N_\ell-1</math>. Αυτό είναι πιο συμπαγώς εκφράσμένο σε [[Διανυσματικός χώρος|διανυσματική]] μορφή, όπου ορίζουμε <math>\mathbf{n} = (n_1, n_2, \dots, n_d)</math> και <math>\mathbf{k} = (k_1, k_2, \dots, k_d)</math> ως ''d''-διαστάσεων διανύσματαταδιανύσματα των δεικτών από 0 μέχρι <math>\mathbf{N} - 1</math>, το οποίο ορίζουμε ως <math>\mathbf{N} - 1 = (N_1 - 1, N_2 - 1, \dots, N_d - 1)</math>:
: <math>X_\mathbf{k} = \sum_{\mathbf{n}=\mathbf{0}}^{\mathbf{N}-1} e^{-2\pi i \mathbf{k} \cdot (\mathbf{n} / \mathbf{N})} x_\mathbf{n} \, ,</math>
όπου η διαίρεση <math>\mathbf{n} / \mathbf{N}</math> ορίζεται ως <math>\mathbf{n} / \mathbf{N} = (n_1/N_1, \dots, n_d/N_d)</math> να είναι ο μετασχηματισμός φουριέΦουριέ, και το άθροισμα εκφράζει το σύνολο των ένθετων αθροίσεων παραπάνω.
 
Το αντίστροφο του πολυδιάστατου DFT , ανάλογα με την μονοδιάστατη περίπτωση, δίνεται από:
: <math>x_\mathbf{n} = \frac{1}{\prod_{\ell=1}^d N_\ell} \sum_{\mathbf{k}=\mathbf{0}}^{\mathbf{N}-1} e^{2\pi i \mathbf{n} \cdot (\mathbf{k} / \mathbf{N})} X_\mathbf{k} \, .</math>
Όπως ο μονοδιάστατος DFT εκφράζει την τιμή εισόδου <math>x_n</math> ως υπέρθεση των ημιτονοειδών, ο πολυδιάστατος DFT εκφράζει την τιμή εισόδου ως υπέρθεση των [[Επίπεδο κύμα|επίπεδων κυμάτων]], ή πολυδιάστατα ημιτονοειδή. Η κατεύθυνση της ταλάντωσης στο χώρο είναι <math>\mathbf{k} / \mathbf{N}</math>. Τα πλάτη είναι <math>X_\mathbf{k}</math>. Αυτή η αποσύνθεση είναι μεγάλης σημασίας για τα πάντα, από την [[ψηφιακή επεξεργασία εικόνας]] (δύο διαστάσεων) ως την επίλυση [[Μερική διαφορική εξίσωση|μερικών διαφορικών εξισώσεων]]. Η λύση χωρίζεται σε επίπεδα κύματα.
 
Ο πολυδιάστατος DFT μπορεί να υπολογιστεί από την [[Σύνθεση συνάρτησης|σύνθεση]] μιας ακολουθίας μονοδιάστατων DFTs κατά μήκος κάθε διάστασης. Στη δισδιάστατη περίπτωση <math>x_{n_1,n_2}</math> η <math>N_1</math> ανεξαρτήτως DFTs των σειρών (δηλ.δηλαδή, κατά μήκος <math>n_2</math>), υπολογίζεται πρώτα για να σχηματίσει έναν νέο πίνακα <math>y_{n_1,k_2}</math>. Στη συνέχεια, η <math>N_2</math> ανεξαρτήτως DFTs του ''y'' κατά μήκος των στηλών (κατά μήκος <math>n_1</math>) υπολογίζεται για να διαμορφώσει το τελικό αποτέλεσμα <math>X_{k_1,k_2}</math>. Εναλλακτικά, οι στήλες μπορεί να υπολογιστούν πρώτα και στη συνέχεια οι σειρές. Η σειρά δεν έχει σημασία, επειδή οι ένθετες αθροίσεις παραπάνω [[Αντιμεταθετική ιδιότητα|αντιμετατίθενται.]]
 
Ένας αλγόριθμος για τον υπολογισμό ενός μονοδιάστατου DFT είναι συνεπώς επαρκές για τον αποτελεσματικό υπολογισμό ενός πολυδιάστατου DFT. Αυτή η προσέγγιση είναι γνωστή ως αλγόριθμος γραμμή-στήλη. Υπάρχουν επίσης εγγενώς [[Ταχείς Μετασχηματισμοί Φουριέ|πολυδιάστατοι FFT αλγόριθμοι]].
 
== Εφαρμογές ==
Ο DFT έχει ευρεία χρήση σε πολλούς τομείς.Εδώ απλά δίνονται μερικά σκίτσα σαν παραδείγματα παρακάτω (βλέπε επίσης τις αναφορές στο τέλος). Όλες οι εφαρμογές του DFT εξαρτώνται σε μεγάλο βαθμό από τη διαθεσιμότητα ενός γρήγορου αλγόριθμου για τον υπολογισμό DFTs και των αντιστρόφωναντίστροφων,ενός fast[[Ταχύς FourierΜετασχηματισμός transformΦουριέ|ταχύ μετασχηματισμού Φουριέ]].
 
=== Φασματική ανάλυση ===
Όταν ο DFT χρησιμοποιείται για [[Ανάλυση Φουριέ|σημειακή φασματική ανάλυση]], η <math>\{x_n\}\,</math> ακολουθία συνήθως αντιπροσωπεύει ένα πεπερασμένο σύνολο ομοιόμορφα κατανεμημένων χρονικών δειγμάτων κάποιου σήματος <math>x(t)\,</math>, όπου ''t'' είναι ο χρόνος. Η μετατροπή από το συνεχή χρόνο σε δείγματα (διακριτός χρόνος) αλλάζει το υποκείμενο [[Μετασχηματισμός Φουριέ|μετασχηματισμός Fourier]] του x(t) σε ένα [[Διακριτού χρόνου μετασχηματισμός Fourier|διακριτού χρόνου μετασχηματισμό Fourier]] (DTFT), το οποίο συνήθως συνεπάγεται ένα είδος παραμόρφωσης που λέγεται [[aliasing]].Η επιλογή κατάλληλου δείγματος ρυθμού (βλέπε ''Nyquist rate'') είναι το κλειδί για την ελαχιστοποίηση αυτής της στρέβλωσης. Επίσης, η μετατροπή από μία πολύ μεγάλη (ή άπειρη) ακολουθία σε ένα διαχειρίσιμο μέγεθος συνεπάγεται ένα είδος παραμόρφωσης που ονομάζεται ''[[Φασματική Διαρροή|διαρροή]]'', η οποία εκδηλώνεται ως απώλεια λεπτομέρειας.κ.α. ψήφισμα) του DTFT. Η επιλογή κατάλληλου μήκους υπο-ακολουθίας είναι το κύριο κλειδί για την ελαχιστοποίηση αυού του αποτελέσματος. Όταν τα διαθέσιμα δεδομένα (και ο χρόνος για να το επεξεργαστεί) είναι περισσότερα από το ποσό που απαιτείται για να επιτευχθεί η επιθυμητή ανάλυση συχνότητας, μια βασική τεχνική είναι να εκτελέσετε πολλούς DFTs, για παράδειγμα, για να δημιουργήσετε ένα [[φασματογράφημα]]. Αν το επιθυμητό αποτέλεσμα είναι ένα φάσμα ισχύος και ο θόρυβος ή η τυχαιότητα παρουσιάζονται στα δεδομένα, κατά μέσο όρο το μέγεθος των συστατικών των πολλαπλών DFTs είναι μια χρήσιμη διαδικασία για τη μείωση της [[Διακύμανση|διασποράς]] του φάσματος (που ονομάζεται επίσης ένα [[περιοδόγραμμα]] σε αυτό το πλαίσιο) . Δύο παραδείγματα τέτοιων τεχνικών είναι η [[Μέθοδος Welch|Welch μέθοδος]] και η [[μέθοδος Bartlett]], το γενικό αντικείμενο της εκτίμησης του φάσματος ισχύος ενός θορυβώδες σήματος ονομάζεται [[φασματική εκτίμηση]].
 
Τελική πηγή παραμόρφωσης (ή ίσως ''την ψευδαίσθηση'') είναι ο DFT ο ίδιος, επειδή είναι απλά μια διακριτή δειγματοληψία του DTFT, η οποία είναι μια συνάρτηση συνεχής στο πεδίο της συχνότητας. Αυτό μπορεί να αντιμετωπιστεί με την αύξηση της ανάλυσης του DFT. Η διαδικασία αυτή απεικονίζεται στη [[Μετασχηματισμός Φουριέ Διακριτού Χρόνου|Δειγματοληψία του DTFT]].
* Η διαδικασία είναι μερικές φορές αναφέρεται ως ''zero-padding'', η οποία είναι μια συγκεκριμένη εφαρμογή που χρησιμοποιείται σε συνδυασμό με τον αλγόριθμο fastτου [[Ταχύς Μετασχηματισμός Φουριέ|ταχύ Fourierμετασχηματισμού transformΦουριέ]] (FFT). Η αναποτελεσματικότητα της εκτέλεσης πολλαπλασιασμών και προσθέσεων με το μηδενικής τιμής "δείγματα" είναι περισσότερη από ότι αντισταθμίζεται από την εγγενή αποτελεσματικότητα του FFT.
* Όπως έχει ήδη σημειωθεί, η διαρροή επιβάλλει ένα όριο για την εγγενή ανάλυση του DTFT. Έτσι, υπάρχει ένα πρακτικό όριο για τα οφέλη που μπορούν να προκύψουν από έναν λεπτόκοκκο DFT.
 
 
=== Μερικές διαφορικές εξισώσεις ===
Οι διακριτοί μετασχηματισμοί Φουριέ χρησιμοποιούνται συχνά για την επίλυση [[Μερική διαφορική εξίσωση|μερικών διαφορικών εξισώσεων]], όπου και πάλι ο DFT χρησιμοποιείται ως προσέγγιση για τη [[Σειρές Φουριέ|σειρά Fourier]] (που ανακτάται στο όριο άπειρο ''N''). Το πλεονέκτημα αυτής της προσέγγισης είναι ότι επεκτείνει το σήμα σε εκθετική συνάρτηση μιγαδικών ''ε''<sup>''inx''</sup>, ταη οποία είναι ιδιοσυναρτήσηςιδιοσυνάρτηση διαφορικών: ''d''/''dx'' ''e''<sup>''inx''</sup> = ''σ'' ''e''<sup>''inx''</sup>. Έτσι, στην αναπαράσταση Fourier , η παραγώγιση είναι απλή—απλά πολλαπλασιάστε με i n. (Σημειώστε, ωστόσο, ότι η επιλογή του ''n'' δεν είναι μοναδική . Για να είναι η μέθοδος συγκλίνουσα, μια επιλογή παρόμοια με εκείνη στο τριγωνομετρική[[Διακριτός μετασχηματισμός Φουριέ|τριγωνομετρικό τμήμα παρεμβολής]] παραπάνω θα πρέπει να χρησιμοποιείται.) Μια [[γραμμική διαφορική εξίσωση]] με σταθερούς συντελεστές μετατρέπεται σε μια εύκολα επιλύσιμη αλγεβρική εξίσωση. Ένα, στη συνέχεια, χρησιμοποιεί το αντίστροφο DFT για να μετατρέψει το αποτέλεσμα πίσω στοστη κανονική διαστηματική αναπαράσταση. Η προσέγγιση αυτή ονομάζεται [[φασματική μέθοδος]].
 
=== Πολλαπλασιασμός πολυωνύμων. ===
 
=== Εκπροσώπηση θεωρίας ===
(Για περισσότερες λεπτομέρειες σε αυτό το θέμα,δείτε [[θεωρία αναπαράστασης των πεπερασμένων ομάδων και διακριτός μετασχηματισμός Φουριέ]])
Ο DFT μπορεί να ερμηνευθεί ως η μιγαδική τιμή [[Θεωρία αναπαραστάσεων|εκπροσώπησης θεωρίας]] της πεπερασμένης κυκλικής ομάδας. Με άλλα λόγια, μια ακολουθία από ''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 είτε αλλάζοντας τον στόχο (παίρνει τιμές σε ένα πεδίο, εκτός από το μιγαδικοί αριθμοί), ή το πεδίο τιμών (ομάδα άλλη από μια πεπερασμένη κυκλική ομάδα), όπως περιγράφεται στη συνέχεια.
 
=== Άλλα πεδία ===
( Κύρια άρθρα : [[Διακριτός μετασχηματισμός Φουριέ]] και [[αριθμητικός-θεωρητικός μετασχηματισμός]] )
Πολλές από τις ιδιότητες του 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 εξαρτώνται μόνο από το γεγονός ότι <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 δρα σε πολυδιάστατες ακολουθίες, οι οποίες μπορούν να θεωρηθούν ως συναρτήσεις
: <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Φουριέ σε άμεσο άθροισμα των κυκλικών ομάδων.
 
== Εναλλακτικές λύσεις ==
Κύριο άρθρο : [[Διακριτός μετασχηματισμός κυμάτων]]
Υπάρχουν διάφορες εναλλακτικές λύσεις για τον DFT για διάφορες εφαρμογές, εξέχουσα μεταξύ των οποίων είναι κυματίδια. Το αναλογικό του DFT είναι η discrete wavelet transform (DWT). Από την άποψη του χρόνου–ανάλυση συχνότητας, ένα βασικό περιορισμό του μετασχηματισμού Fourier είναι ότι δεν περιλαμβάνει ''καταλύματος'' πληροφορίες, μόνο ''συχνότητας'' πληροφορίες, και έτσι έχει δυσκολία στην αντιπροσωπεύουν μεταβατικά φαινόμενα. Όπως κυματίδια έχουν θέση, καθώς και η συχνότητα, είναι καλύτερα σε θέση να αντιπροσωπεύουν τοποθεσία, σε βάρος μεγαλύτερη δυσκολία που αντιπροσωπεύει τη συχνότητα. Για λεπτομέρειες, ανατρέξτε σύγκριση των discrete wavelet transform, με το διακριτό μετασχηματισμό Fourier.
 
Υπάρχουν διάφορες εναλλακτικές λύσεις για τον DFT για διάφορες εφαρμογές, εξέχουσα μεταξύ των οποίων είναι κυματίδιατα κύματα. Το αναλογικό του DFT είναι ηο discrete[[διακριτός waveletμετασχηματισμός transformκυμάτων]] (DWT). Από την άποψη τουτης χρόνου–ανάλυσηανάλυσης χρόνου-συχνότητας, έναένας βασικόβασικός περιορισμόπεριορισμός του μετασχηματισμού FourierΦουριέ είναι ότι δεν περιλαμβάνει ''καταλύματος''πληροφορίες πληροφορίεςθέσης, μόνο ''συχνότητας'' πληροφορίες, και έτσι έχει δυσκολία στην αντιπροσωπεύουνεκπροσώπηση μεταβατικάμεταβατικών φαινόμεναφαινομένων. ΌπωςΕπειδή κυματίδιατα κύματα έχουν θέση, καθώς και η συχνότητα, είναι καλύτερα σε θέση να αντιπροσωπεύουν καλύτερα τοποθεσία, σε βάρος μεγαλύτερητης δυσκολίαμεγαλύτερης πουδυσκολίας να αντιπροσωπεύει τη συχνότητα. Για λεπτομέρειες, ανατρέξτε στη [[Διακριτός μετασχηματισμός κυμάτων|σύγκριση τωντου discreteδιακριτού waveletμετασχηματισμού transform,κυμάτων με το διακριτό μετασχηματισμό FourierΦουριέ]].
 
== Σημειώσεις ==
30

επεξεργασίες