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

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Skomatas (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
ArisKalk (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Γραμμή 300:
Όταν ο DFT χρησιμοποιείται για [[Ανάλυση Φουριέ|σημειακή φασματική ανάλυση]], η <math>\{x_n\}\,</math> ακολουθία συνήθως αντιπροσωπεύει ένα πεπερασμένο σύνολο ομοιόμορφα κατανεμημένων χρονικών δειγμάτων κάποιου σήματος <math>x(t)\,</math>, όπου ''t'' είναι ο χρόνος. Η μετατροπή από το συνεχή χρόνο σε δείγματα (διακριτός χρόνος) αλλάζει το υποκείμενο [[Μετασχηματισμός Φουριέ|μετασχηματισμός Fourier]] του x(t) σε ένα διακριτού χρόνου μετασχηματισμό Fourier (DTFT), το οποίο συνήθως συνεπάγεται ένα είδος παραμόρφωσης που λέγεται aliasing.Η επιλογή κατάλληλου δείγματος ρυθμού (βλέπε ''Nyquist rate'') είναι το κλειδί για την ελαχιστοποίηση αυτής της στρέβλωσης. Επίσης, η μετατροπή από μία πολύ μεγάλη (ή άπειρη) ακολουθία σε ένα διαχειρίσιμο μέγεθος συνεπάγεται ένα είδος παραμόρφωσης που ονομάζεται ''[[Φασματική Διαρροή|διαρροή]]'', η οποία εκδηλώνεται ως απώλεια λεπτομέρειας.κ.α. ψήφισμα) του DTFT. Η επιλογή κατάλληλου μήκους υπο-ακολουθίας είναι το κύριο κλειδί για την ελαχιστοποίηση αυού του αποτελέσματος. Όταν τα διαθέσιμα δεδομένα (και ο χρόνος για να το επεξεργαστεί) είναι περισσότερα από το ποσό που απαιτείται για να επιτευχθεί η επιθυμητή ανάλυση συχνότητας, μια βασική τεχνική είναι να εκτελέσετε πολλούς DFTs, για παράδειγμα, για να δημιουργήσετε ένα [[φασματογράφημα]]. Αν το επιθυμητό αποτέλεσμα είναι ένα φάσμα ισχύος και ο θόρυβος ή η τυχαιότητα παρουσιάζονται στα δεδομένα, κατά μέσο όρο το μέγεθος των συστατικών των πολλαπλών DFTs είναι μια χρήσιμη διαδικασία για τη μείωση της [[Διακύμανση|διασποράς]] του φάσματος (που ονομάζεται επίσης ένα [[περιοδόγραμμα]] σε αυτό το πλαίσιο) . Δύο παραδείγματα τέτοιων τεχνικών είναι η [[Μέθοδος Welch|Welch μέθοδος]] και η [[μέθοδος Bartlett]], το γενικό αντικείμενο της εκτίμησης του φάσματος ισχύος ενός θορυβώδες σήματος ονομάζεται [[φασματική εκτίμηση]].
 
Τελική πηγή παραμόρφωσης (ή ίσως ''την ψευδαίσθηση'') είναι ο DFT ο ίδιος, επειδή είναι απλά μια διακριτή δειγματοληψία του DTFT, η οποία είναι μια συνάρτηση συνεχής στο πεδίο της συχνότητας. Αυτό μπορεί να αντιμετωπιστεί με την αύξηση της ανάλυσης του DFT. Η διαδικασία αυτή απεικονίζεται στη [[ΔιακριτούΜετασχηματισμός χρόνουΦουριέ μετασχηματισμόςΔιακριτού ΦουριέΧρόνου|Δειγματοληψία του DTFT]].
* Η διαδικασία είναι μερικές φορές αναφέρεται ως ''zero-padding'', η οποία είναι μια συγκεκριμένη εφαρμογή που χρησιμοποιείται σε συνδυασμό με τον αλγόριθμο fast Fourier transform (FFT). Η αναποτελεσματικότητα της εκτέλεσης πολλαπλασιασμών και προσθέσεων με το μηδενικής τιμής "δείγματα" είναι περισσότερη από ότι αντισταθμίζεται από την εγγενή αποτελεσματικότητα του FFT.
* Όπως έχει ήδη σημειωθεί, η διαρροή επιβάλλει ένα όριο για την εγγενή ανάλυση του DTFT. Έτσι, υπάρχει ένα πρακτικό όριο για τα οφέλη που μπορούν να προκύψουν από έναν λεπτόκοκκο DFT.
 
=== Φίλτρο τράπεζα ===
Δείτε FFT φίλτρο[[Τράπεζα φίλτρου|τράπεζες φίλτρου FFT]] και [[Μετασχηματισμός Φουριέ Διακριτού Χρόνου|Δειγματοληψία του DTFT]].
 
=== Συμπίεση δεδομένων ===
Το πεδίο της ψηφιακής επεξεργασίας σήματος εξαρτάταιβασίζεται σε μεγάλο βαθμό απόσε δραστηριότητες στο πεδίο των συχνοτήτων (δηλαδήγια οπαράδειγμα μετασχηματισμόςστον μετασχηματισμό Fourier). Για παράδειγμα, αρκετές απώλειεςμέθοδοι συμπίεσης εικόνας και ήχου μέθοδοιμε συμπίεσηςαπώλειες απασχολούν τοτον διακριτόςδιακριτό μετασχηματισμόςμετασχηματισμό Fourier: το σήμα κόβεται σε μικρά τεμάχιατμήματα , το καθένα έχειείναι μετασχηματισμένο μεταμορφωθεί, και τότε οι συντελεστές Fourierυψηλής τηςσυχνότητας υψηλές συχνότητεςFourier, ηοι οποίαοποίοι υποτίθεται ότι είναι δυσδιάκριτηδυσδιάκριτοι, απορρίπτονται. Το πρόγραμμα αποσυμπίεσης υπολογίζει τον αντίστροφο μετασχηματισμό με βάση αυτό το μειωμένο αριθμό συντελεστών Fourier συντελεστές. (Εφαρμογές συμπίεσης συχνά χρησιμοποιούν μια εξειδικευμένη μορφή του DFT, οτο διακριτός[[Διακριτός μετασχηματισμός συνημιτόνου|διακριτό μετασχηματισμό συνημιτόνου]] ή μερικές φορές τοτον τροποποιημένο[[Τροποποιημένος διακριτός μετασχηματισμός συνημιτόνου|τροποποιημένο διακριτό μετασχηματισμό συνημιτόνου]].) Κάποιοι σχετικά πρόσφατοι αλγόριθμοι συμπίεσης, ωστόσο, χρησιμοποιούν [[Κυμάτιος μετασχηματισμός|κυμάτιους μετασχηματισμούς]], οι οποίοι δίνουν έναν πιο ομοιόμορφο συμβιβασμό μεταξύ του χρόνου και του πεδίου συχνοτήτων από εκείνους που λαμβάνονται με τεμαχισμό των δεδομένων σε τμήματα και μετασχηματίζοντας κάθε τμήμα. Στην περίπτωση [[JPEG2000]], αυτό αποφεύγει τα ψεύτικα χαρακτηριστικά της εικόνας που εμφανίζονται όταν οι εικόνες είναι εξαιρετικά συμπιεσμένες με το αρχικό [[JPEG]].
Κάποια σχετικά πρόσφατη αλγόριθμους συμπίεσης, ωστόσο, η χρήση wavelet transforms, τα οποία δίνουν μια πιο ομοιόμορφη συμβιβασμό μεταξύ του χρόνου και των συχνοτήτων από εκείνα που λαμβάνονται με τεμαχισμό των δεδομένων σε τμήματα και μετατρέποντας κάθε τμήμα. Στην περίπτωση JPEG2000, αυτό αποφεύγει την ψευδή χαρακτηριστικά της εικόνας που εμφανίζεται όταν οι εικόνες είναι εξαιρετικά συμπιεσμένο με το αρχικό [[JPEG]].
 
=== Μερικές διαφορικές εξισώσεις ===
DiscreteΟι Fourierδιακριτοί μετασχηματισμοί Φουριέ χρησιμοποιούνται συχνά για την επίλυση [[Μερική διαφορική εξίσωση|μερικών διαφορικών εξισώσεων]], όπου και πάλι ο DFT χρησιμοποιείται ως προσέγγιση για τη [[Σειρές Φουριέ|σειρά Fourier]] (που ανακτάται στο όριο άπειρο ''N''). Το πλεονέκτημα αυτής της προσέγγισης είναι ότι επεκτείνει το σήμα σε συγκρότημαεκθετική exponentialsσυνάρτηση μιγαδικών ''ε''<sup>''inx''</sup>, τα οποία είναι eigenfunctionsιδιοσυναρτήσης διαφοροποίησηςδιαφορικών: ''d''/''dx'' ''e''<sup>''inx''</sup> = ''σ'' ''e''<sup>''inx''</sup>. Έτσι, στοστην αναπαράσταση Fourier εκπροσώπηση, η διαφοροποίησηπαραγώγιση είναι απλή—απλά πολλαπλασιάστε τηνμε από ''-i n''. (Σημειώστε, ωστόσο, ότι η επιλογή του ''n'' δεν είναι μοναδική λόγω. aliasingΓια *να είναι η μέθοδος είναι συγκλίνουσα, μια επιλογή παρόμοια με εκείνη τωνστο τριγωνομετρικώντριγωνομετρική παρεμβολήτμήμα παρεμβολής παραπάνω τμήμα θα πρέπει να χρησιμοποιηθείχρησιμοποιείται.) Μια [[γραμμική διαφορική εξίσωση]] με σταθερούς συντελεστές μετατρέπεται σε μια εύκολα επιλύσιμοεπιλύσιμη αλγεβρική εξίσωση. Ένα, στη συνέχεια, χρησιμοποιεί το inverseαντίστροφο DFT για να μετατρέψει το αποτέλεσμα πίσω στο κανονικόκανονική χωρικήδιαστηματική αναπαράσταση. Η προσέγγιση αυτή ονομάζεται [[φασματική μέθοδος]].
 
=== Πολλαπλασιασμός πολυωνύμων. ===
=== Πολυωνύμου πολλαπλασιασμός ===
Έστω ότι θέλουμε να υπολογίσουμε το πολυώνυμογινόμενο προϊόντοςπολυώνυμο ''γ''(''x'') = ''a''(''x'') · ''b''(''x''). ΤοΗ κανονικόκανονική προϊόνέκφραση έκφρασηςγινομένου για τους συντελεστές του ''c'' περιλαμβάνει μια γραμμική (άκυκλεςάκυκλη) συνέλιξη, όπου οι δείκτες δεν "wrapεκτυλίσσονται aroundγύρω"." Αυτό μπορεί να ξαναγραφεί ως μια κυκλική συνέλιξη μεπαίρνοντας τητους λήψηδιανυσματικούς του συντελεστή φορείςσυντελεστές για ''a''(''x'') και ''b''(''x'') με το σταθερό όρο πρώτηπρώτα, μετά την προσάρτηση μηδενικά,μηδενικών έτσι ώστε τοοι προκύπτονδιανυσματικοί συντελεστήςσυντελεστές διανύσματα '''a''' και '''b''' που προκύπτον να έχουν διάσταση ''d''&#x20;>&#x20;deg(''a''(''x''))&#x20;+&#x20;deg(''b''(''x'')). Στη συνέχεια,
: <math>\mathbf{c} = \mathbf{a} * \mathbf{b}</math>
Όπου '''c''' είναι το διάνυσμα των συντελεστών ''του c''(''x''), και η συνέλιξηπράξη φορέασυνέλιξη <math>*\,</math> ορίζεται έτσι
: <math>c_n = \sum_{m=0}^{d-1}a_m b_{n-m\ \mathrm{mod}\ d} \qquad\qquad\qquad n=0,1\dots,d-1</math>
Αλλά η συνέλιξη γίνεται πολλαπλασιασμός κάτω απόμέσω τοτου DFT:
: <math>\mathcal{F}(\mathbf{c}) = \mathcal{F}(\mathbf{a})\mathcal{F}(\mathbf{b})</math>
Εδώ το διάνυσμαγινόμενο προϊόντοςδιανυσμάτων elementwiseπροκύπτει στοιχειωδώς. Έτσι, οι συντελεστές του προϊόντοςπολυωνυμικού πολυώνυμογινομένου ''c''(''x'') είναι οι όροι 0, ..., deg(''a''(''x'')) + deg(''b''(''x'')) του συντελεστή διάνυσμα
: <math>\mathbf{c} = \mathcal{F}^{-1}(\mathcal{F}(\mathbf{a})\mathcal{F}(\mathbf{b})).</math>
Με fastέναν Fourier[[Ταχύς transform,Μετασχηματισμός τοΦουριέ|ταχύ αποτέλεσμαμετασχηματισμό Φουριέ]], ο αλγόριθμος που προκύπτει παίρνει O (''N''&#x20;log&#x20;''N'') αριθμητικές πράξεις. Λόγω της απλότητας και της ταχύτητας, ηο Κούλι–Τουρκία[[Couley-Tukey αλγόριθμοΤΜΦ αλγόριθμος]] FFT, ηο οποίαοποίος περιορίζεται σε [[Σύνθετος αριθμός|σύνθετα]] μεγέθη, είναι συχνά επιλέγεται για το μετασχηματισμόπράξη τηςτου μετασχηματισμού λειτουργίας. Σε αυτή την περίπτωση, το ''d'' θα πρέπει να επιλέγεται ως τοο μικρότερομικρότερος ακέραιοακέραιος μεγαλύτεροπου είναι μεγαλύτερος από το άθροισμα των εισροώνεισόδων πολυώνυμοβαθμών βαθμούςπολυωνύμων που είναι factorizable σεπαραγωγίσιμοι μικράστις primeπρώτες παράγοντεςπαραγώγους (π. χ. 2, 3, και 5, ανάλογα με την υλοποίηση FFT).
 
==== Πολλαπλασιασμός μεγάλων ακεραίων ====
Ο πιο γρήγορος γνωστοίγνωστός αλγόριθμοιαλγόριθμος για τον πολλαπλασιασμό των πολύ μεγάλων [[Ακέραιος αριθμός|ακεραίων]] χρήσηχρησιμοποιεί τουτην πολυωνύμουμέθοδο πολλαπλασιασμόςπολλαπλασιασμού μέθοδοπολυωνύμων που περιγράφεται παραπάνω.Οι Ακέραιοιακέραιοι μπορείμπορούν να αντιμετωπιστεί ως η τιμή ενός πολυωνύμου αξιολογούνταιδίνοντας συγκεκριμένατιμή τονειδικά στον αριθμό της βάσης, με τους συντελεστές του πολυωνύμου πουνα αντιστοιχούν στα ψηφία σε αυτή τη βάση. Μετά πολυωνύμουτον πολλαπλασιασμό πολυωνύμων πολλαπλασιασμός,ένα βήμα σχετικά χαμηλής πολυπλοκότητας μεταφορά μεταφοράς-διάδοσης βήμα ολοκληρώνει τον πολλαπλασιασμό.
 
==== Συνέλιξη ====
Όταν τα δεδομένα είναιέχουν [[Συνέλιξη|convolvedσυνελιχθεί]] με μια λειτουργίασυνάρτηση με μεγάλη υποστήριξη, όπως για downsamplingυποδειγματοληψία από ένα μεγάλο λόγοςλόγο δειγματοληψίας, λόγωεξαιτίας τηςτου [[Θεώρημα Συνέλιξης|θεωρήματος θεώρημαΣυνέλιξης]] και τοντου αλγόριθμοαλγορίθμου FFT, μπορεί να είναι πιο γρήγοραγρήγορη για να το μετατρέψειμετασχηματίσει, να πολλαπλασιάσετε pointwiseσημειακά από το μετασχηματισμό του φίλτρου και στη συνέχεια να αντιστραφείμετασχηματιστεί το μεταμορφώσειαντίστροφα. Εναλλακτικά, ένα καλό φίλτρο επιτυγχάνεται απλώς με την περικοπή των μετατραπείμετασχηματισμών δεδομένων και τηντου εκ νέου μετατροπήμετασχηματισμού του συντομευμένησυντομευμένου σύνολοσυνόλου δεδομένων.
 
== Κάποια διακριτός μετασχηματισμός Fourier ζεύγη ==