Διακριτή κατανομή Φουριέρ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Δημιουργήθηκε από μετάφραση της σελίδας "Discrete Fourier transform" |
Δημιουργήθηκε από μετάφραση της σελίδας "Discrete Fourier transform" |
||
Γραμμή 1:
[[Αρχείο:Fourier_transform,_Fourier_series,_DTFT,_DFT.gif|μικρογραφία|400x400εσ|Απεικόνιση ενός μετασχηματισμού Fourier (επάνω αριστερά) και της περιοδικής άθροισης (DTFT) στην κάτω αριστερή γωνία. Οι φασματικές ακολουθίες (a) επάνω δεξιά και (b) κάτω δεξιά, αντίστοιχα, υπολογίζονται από (α) ένα κύκλο του περιοδικού αθροίσματος s(t) και (β) ένα κύκλο του περιοδικού αθροίσματος της s(nT) ακολουθίας. Οι αντίστοιχοι τύποι είναι (α) η [[Σειρές Φουριέ|σειρά Fourier]] <u>ολοκλήρωμα</u> και (β) του '''DFT''' <u>άθροισμα</u>. Οι ομοιότητες με τον αρχικό μετασχηματισμό, S(f), και η σχετική υπολογιστική ευκολία είναι συχνά το κίνητρο για τον υπολογισμό μιας DFT ακολουθίας.]]
Ο DFT είναι το πιο σημαντικό διακριτό μετασχηματισμό, που χρησιμοποιείται για να εκτελέσει [[Ανάλυση Φουριέ|την ανάλυση Fourier]] σε πολλές πρακτικές εφαρμογές.<ref>{{Πρότυπο:Cite journal|url=http://www.jstor.org/stable/29775194|title=Wavelets|last=Strang|first=Gilbert|date=May–June 1994|journal=American Scientist|accessdate=8 October 2013|issue=3|volume=82|page=253|quote=This is the most important numerical algorithm of our lifetime...}}</ref> Στην [[ψηφιακή επεξεργασία σήματος]], η λειτουργία είναι οποιαδήποτε ποσότητα ή [[Ηλεκτρικό σήμα|σήμα]] που ποικίλει με την πάροδο του χρόνου, όπως η πίεση των [[Ήχος|υγιών κυμάτων]], ραδιόφωνο, σήμα, ή ημερήσια [[θερμοκρασία]] μετρήσεις, δειγματοληψίες πάνω από ένα πεπερασμένο χρονικό διάστημα (συνήθως ορίζεται από ένα παράθυρο λειτουργία<ref>{{Πρότυπο:Cite journal|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6387265&isnumber=6380557|title=A Novel Windowing Technique for Efficient Computation of MFCC for Speaker Recognition|last=Sahidullah|first=Md.|date=Feb 2013|journal=IEEE Signal Processing Letters|issue=2|doi=10.1109/LSP.2012.2235067|volume=20|pages=149–152|arxiv=1206.2437|bibcode=2013ISPL...20..149S|author2=Saha, Goutam}}</ref>). Στην [[επεξεργασία εικόνας]], τα δείγματα μπορεί να είναι οι τιμές των [[Εικονοστοιχείο|pixels]] κατά μήκος της γραμμής ή της στήλης των εικόνων raster. Ο DFT είναι, επίσης, χρησιμοποιείται για την αποτελεσματική επίλυση [[Μερική διαφορική εξίσωση|μερικών διαφορικών εξισώσεων]], και να εκτελέσετε άλλες ενέργειες, όπως οι [[Συνέλιξη|έλικες]] ή πολλαπλασιασμός μεγάλων ακεραίων.
Δεδομένου ότι πρόκειται για ένα πεπερασμένο ποσό των δεδομένων, μπορεί να εφαρμοστεί σε [[Ηλεκτρονικός υπολογιστής|υπολογιστές]] με [[Αριθμητική ανάλυση|αριθμητική αλγόριθμοι]] ή ακόμα και dedicated [[Ψηφιακά ηλεκτρονικά|hardware]]. Αυτές οι εφαρμογές συνήθως χρησιμοποιούν αποτελεσματική fast Fourier transform (FFT) αλγόριθμοι;<ref name="colley">Cooley et al., 1969</ref> τόσο πολύ, που οι όροι "FFT" και "DFT" συχνά χρησιμοποιούνται εναλλακτικά. Πριν από την τρέχουσα χρήση, το "FFT" [[Αρκτικόλεξο|initialism]] μπορεί επίσης να χρησιμοποιηθεί για την ασαφής όρος "πεπερασμένος μετασχηματισμός Fourier".
== Ορισμός ==
Η [[ακολουθία]] των ''N'' [[Μιγαδικός αριθμός|μιγαδικοί αριθμοί]] <math>x_0, x_1, \ldots, x_{N-1}</math> μετατρέπεται σε ένα ''N''-περιοδική ακολουθία μιγαδικών αριθμών:
Λόγω της περιοδικότητας, το σύνηθες τομέα της '''k''' υπολογίσει είναι το [''0'', ''N'' − 1]. Αυτή είναι πάντα η περίπτωση, όταν ο DFT υλοποιείται μέσω του Fast Fourier transform (fft αλγόριθμο. Αλλά και άλλες κοινές περιοχές είναι  το[−''N''/2, ''N''/2 − 1]  (''N'' )  και  [−(''N'' − 1)/2, (''N'' − 1)/2]  (''N'' περιττός), όπως όταν το αριστερό και το δεξί ήμισυ ενός FFT παραγωγή ακολουθία αντάλλαξαν.<ref>{{Πρότυπο:Cite web|url=http://www.mathworks.com/help/matlab/ref/fftshift.html|title=Shift zero-frequency component to center of spectrum – MATLAB fftshift|publisher=The MathWorks, Inc.|location=Natick, MA 01760|accessdate=10 March 2014|work=http://www.mathworks.com/}}</ref>
Ο μετασχηματισμός είναι μερικές φορές συμβολίζεται με το σύμβολο <math>\mathcal{F}</math>, όπως και <math>\mathbf{X} = \mathcal{F} \left \{ \mathbf{x} \right \} </math> ή <math>\mathcal{F} \left ( \mathbf{x} \right )</math> ή <math>\mathcal{F} \mathbf{x}</math>.<ref group="note">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 ''X''<sub>''k''</sub> can thus be viewed as coefficients of ''x'' in an orthonormal basis.</ref>
{{Πρότυπο:EquationNote|Eq.1}} μπορεί να ερμηνευθεί ή παράγωγα με διάφορους τρόπους, για παράδειγμα:
* Εντελώς περιγράφει την διακριτού χρόνου μετασχηματισμός Fourier (DTFT) της ''N''-περιοδική ακολουθία, η οποία περιλαμβάνει μόνο διακριτή συχνότητα στοιχεία. (Χρησιμοποιώντας τον DTFT με περιοδική δεδομένων)
* Μπορεί επίσης να παρέχει ομοιόμορφα κατανεμημένες δείγματα της συνεχούς DTFT ενός πεπερασμένου μήκους ακολουθία. (Δειγματοληψία του DTFT)
* Είναι ο σταυρός συσχέτιση της ''εισαγωγής'' ακολουθία ''x<sub>n</sub>'', και ένα συγκρότημα ημιτονοειδής στη συχνότητα ''k''/''N''.  Έτσι λειτουργεί σαν ένα matched filter για αυτή τη συχνότητα.
* Είναι το διακριτό αναλογία του τύπου για τους συντελεστές της [[Σειρές Φουριέ|σειράς Fourier]]:
: το οποίο είναι, επίσης, '''N'''-περιοδική. Στον τομέα  <math>\scriptstyle n\ \in\ [0,\ N-1],</math>  αυτό είναι το '''αντίστροφο μετασχηματισμό''' του {{Πρότυπο:EquationNote|Eq.1}}. Σε αυτή την ερμηνεία, το καθένα <math>X_k</math> είναι ένας μιγαδικός αριθμός που κωδικοποιεί τόσο το εύρος και τη φάση του μια ημιτονοειδή συνιστώσα  <math>(e^{2 \pi i k n / N})</math>  της λειτουργίας <math>x_n.</math> Του ημιτονοειδής είναι [[Συχνότητα|η συχνότητα]] είναι ''k'' κύκλους ανά ''N'' δείγματα.  Το εύρος και η φάση είναι:
:: <math>|X_k|/N = \sqrt{\operatorname{Re}(X_k)^2 + \operatorname{Im}(X_k)^2}/N</math>
:: <math>\arg(X_k) = \operatorname{atan2}\big( \operatorname{Im}(X_k), \operatorname{Re}(X_k) \big)=-i\operatorname{ln}\left(\frac{X_k}{|X_k|}\right),</math>
: πού atan2 είναι τα δύο επιχείρημα μορφή της arctan λειτουργία.
Η κανονικοποίηση παράγοντας πολλαπλασιασμού του DFT και IDFT (εδώ το 1 και 1/''N'') και τα σημεία των εκθέτες είναι απλώς συμβάσεις, και διαφέρουν σε ορισμένες θεραπείες. Το μόνο απαιτήσεις αυτών των συμβάσεων είναι ότι ο DFT και IDFT έχουν αντίθετο-σημάδι εκθέτες και ότι το προϊόν τους παράγοντες κανονικοποίησης είναι 1/''N''.  Μια εξομάλυνση της <math>\scriptstyle \sqrt{1/N}</math> τόσο για τον DFT και IDFT, για παράδειγμα, κάνει το μετατρέπει ενιαία.
Στη συζήτηση που ακολουθεί οι όροι "ακολουθία" και "διάνυσμα" θα θεωρούνται εναλλάξιμα.
Χρησιμοποιώντας τη [[Τύπος του Όιλερ|φόρμουλα του Euler]], ο DFT για βρέφη μπορούν να μετατραπούν σε τριγωνομετρικές μορφές μερικές φορές χρησιμοποιείται στη μηχανική και την επιστήμη των υπολογιστών:
'''Μετασχηματισμός Fourier:'''
'''Inverse Fourier Transform:'''
:: '''N''' = αριθμός φορά δείγματα που έχουμε
:: '''n''' = το τρέχον δείγμα που εξετάζουμε (0, ..., ''N'' − 1)
:: '''x<sub>n</sub>''' = αξία του σήματος στο χρόνο n
:: '''k''' = τρέχουσα συχνότητα εξετάζουμε (0 Hertz έως N-1 Hertz)
:: '''X<sub>k</sub>''' = ποσό της συχνότητας k στο σήμα (το Πλάτος και τη Φάση, ένας μιγαδικός αριθμός)
== Ιδιότητες ==
=== Πληρότητα ===
Ο διακριτός μετασχηματισμός Fourier είναι ένας αντιστρέψιμος, [[γραμμικός μετασχηματισμός]]
: <math>\mathcal{F}\colon\mathbb{C}^N \to \mathbb{C}^N</math>
με το <math>\mathbb{C}</math> που υποδηλώνει το σύνολο των [[Μιγαδικός αριθμός|μιγαδικών αριθμών]]. Με άλλα λόγια, για κάθε ''N'' > 0, ''N''-διαστάσεων, συγκρότημα διάνυσμα έχει ένα DFT και IDFT τα οποία με τη σειρά ''N''-διαστάσεων, συγκρότημα φορείς.
=== Καθετότητα ===
Τα διανύσματα <math>u_k=\left[ e^{ \frac{2\pi i}{N} kn} \;|\; n=0,1,\ldots,N-1 \right]^T</math>
σχηματίζουν μια ορθογώνια βάση πάνω από το σύνολο των ''N''-διαστάσεων, συγκρότημα φορείς:
: <math>u^T_k u_{k'}^*
= \sum_{n=0}^{N-1} \left(e^{ \frac{2\pi i}{N} kn}\right) \left(e^{\frac{2\pi i}{N} (-k')n}\right)
= \sum_{n=0}^{N-1} e^{ \frac{2\pi i}{N} (k-k') n}
= N~\delta_{kk'}
</math>
πού <math>~\delta_{kk'}</math> είναι ο [[Δέλτα του Κρόνεκερ|Kronecker δέλτα]]. (Στο τελευταίο βήμα, το άθροισμα είναι ασήμαντο αν <math>k=k'</math>, όπου είναι 1+1+⋅⋅⋅=''N'', και το αντίθετο, είναι μια γεωμετρική σειρά που μπορεί να είναι ρητά αθροίζονται για να αποκτήσετε το μηδέν.) Αυτή η καθετότητα όρος μπορεί να χρησιμοποιηθεί για να αντλήσει η φόρμουλα για την IDFT από τον ορισμό του DFT, και είναι ισοδύναμο με το unitarity ιδιοκτησίας παρακάτω.
=== Το Plancherel θεώρημα και το θεώρημα του Parseval ===
Αν ''X''<sub>''k''</sub> και ''Y''<sub>''k''</sub> είναι το DFTs των ''x''<sub>''n''</sub> και ''y''<sub>''n''</sub> , αντίστοιχα, τότε το θεώρημα του Parseval μέλη:
: <math>\sum_{n=0}^{N-1} x_n y^*_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k Y^*_k</math>
όπου η σταρ δηλώνει [[Συζυγής μιγαδικός αριθμός|συγκρότημα σύζευξη]]. Plancherel θεώρημα είναι μια ειδική περίπτωση το θεώρημα του Parseval και μέλη:
: <math>\sum_{n=0}^{N-1} |x_n|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X_k|^2.</math>
Αυτά τα θεωρήματα είναι επίσης ισοδύναμο με το ενιαίο όρος παρακάτω.
=== Περιοδικότητα ===
Η περιοδικότητα μπορεί να αποδειχθεί άμεσα από τον ορισμό:
: <math>X_{k+N} \ \stackrel{\mathrm{def}}{=} \ \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} (k+N) n} =
\sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} k n} \underbrace{e^{-2 \pi i n}}_{1} = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} k n} = X_k. </math>
Ομοίως, μπορεί να αποδειχθεί ότι η IDFT φόρμουλα οδηγεί σε μια περιοδική επέκταση.
=== Shift το θεώρημα ===
Πολλαπλασιάζοντας <math>x_n</math> με ''γραμμική φάση'' <math>e^{\frac{2\pi i}{N}n m}</math> για κάποιο ακέραιος ''m'' αντιστοιχεί σε μια ''κυκλική μετατόπιση'' της παραγωγής <math>X_k</math>: <math>X_k</math> αντικαθίσταται από <math>X_{k-m}</math>, όπου ο δείκτης ερμηνεύεται [[Αριθμητική υπολοίπων|modulo]] ''N'' (δηλαδή, σε τακτά χρονικά διαστήματα). Ομοίως, μια κυκλική μετατόπιση της εισόδου <math>x_n</math> αντιστοιχεί σε πολλαπλασιασμό της παραγωγής <math>X_k</math> από μια γραμμική φάση. Μαθηματικά, αν <math>\{x_n\}</math> αντιπροσωπεύει το διάνυσμα '''x''' τότε
: αν <math>\mathcal{F}(\{x_n\})_k=X_k</math>
: στη συνέχεια <math>\mathcal{F}(\{ x_n\cdot e^{\frac{2\pi i}{N}n m} \})_k=X_{k-m}</math>
: και <math>\mathcal{F}(\{x_{n-m}\})_k=X_k\cdot e^{-\frac{2\pi i}{N}k m}</math>
=== Κυκλική συνέλιξη θεώρημα και συσχέτισή τους θεώρημα ===
Το θεώρημα της συνέλιξης για την διακριτού χρόνου μετασχηματισμός Fourier δείχνει ότι συνέλιξη των δύο άπειρες ακολουθίες μπορούν να ληφθούν ως το αντίστροφο μετασχηματισμό των προϊόντων του ατόμου, μεταμορφώνεται. Μια σημαντική απλοποίηση προκύπτει όταν οι ακολουθίες έχουν πεπερασμένο μήκος, '''N'''. Όσον αφορά το DFT και inverse DFT, μπορεί να γραφτεί ως εξής''':'''
: <math>
\mathcal{F}^{-1} \left \{ \mathbf{X\cdot Y} \right \}_n \ = \sum_{l=0}^{N-1}x_l \cdot (y_N)_{n-l} \ \ \stackrel{\mathrm{def}}{=} \ \ (\mathbf{x * y_N})_n\ ,
</math>
που είναι η συνέλιξη της <math>\mathbf{x}</math> ακολουθίας με μια <math>\mathbf{y}</math> εκτεταμένη σειρά από περιοδική άθροιση''':'''
== Notes ==
{{Reflist|group=note}}
== Citations ==
{{Reflist}}
[[Κατηγορία:Ψηφιακή επεξεργασία σήματος]]
[[Κατηγορία:Ανάλυση Φουριέ]]
| |||