Διακριτός μετασχηματισμός Φουριέ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 81:
=== Κυκλική συνέλιξη θεώρημα και συσχέτισή τους θεώρημα ===
Το [[Μετασχηματισμός Φουριέ|θεώρημα συνέλιξης]] για το [[Μετασχηματισμός Φουριέ|χρονικό-διακριτό μετασχηματισμό Fourier]] δείχνει ότι συνέλιξη των δύο άπειρων ακολουθιών μπορούν να ληφθούν ως ο αντίστροφος μετασχηματισμός των προϊόντων των ατομικών μετασχηματισμών. Μια σημαντική απλοποίηση προκύπτει όταν οι ακολουθίες έχουν πεπερασμένο μήκος, '''N'''. Όσον αφορά το ΔΜΦ και το αντίστροφο ΔΜΦ, μπορεί να γραφτεί ως εξής''':'''
: <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> ακολουθία εκτεταμένη με σειρά [[Ανάλυση Φουριέ|περιοδικής άθροισης]]''':'''
: <math>(\mathbf{y_N})_n \ \stackrel{\mathrm{def}}{=} \ \sum_{p=-\infty}^{\infty} y_{(n-pN)} = y_{n (mod N)}. \,</math>
Ομοίως, η [[Συσχέτιση και εξάρτηση|συσχέτισή]] της  <math>\mathbf{x}</math>  και  <math>\mathbf{y_N}</math>  δίνεται από''':'''
: <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 \star y_N})_n\ .
</math>
Όταν κάθε ακολουθία περιέχει μια σειρά από μηδενικά, μήκους L,  L+1 από τα αποτελέσματα των κυκλικών συνελέξεων είναι ισοδύναμα με τις αξίες των  <math>\mathbf{x * y}.</math>  Μέθοδοι έχουν αναπτυχθεί επίσης για να χρησιμοποιηθεί αυτή η ιδιότητα ως μέρος μιας αποτελεσματικής διαδικασίας που κατασκευάζει  <math>\mathbf{x * y}</math>  με μία <math>\mathbf{x}</math> ή <math>\mathbf{y}</math> ακολουθία ενδεχομένως πολύ μεγαλύτερη από το μέγεθος του πρακτικού μετασχηματισμού ('''N'''). Δύο τέτοιες μέθοδοι ονομάζονται [[Overlap-save method|επικάλυψη-αποθήκευση]] και [[Overlap-save method|επικάλυψη-προσθήκη]].<ref>T. G. Stockham, Jr., "[http://dl.acm.org/citation.cfm?id=1464209 High-speed convolution and correlation]," in 1966 ''Proc. ''</ref> Η αποδοτικότητα προκύπτει από το γεγονός ότι μια άμεση αξιολόγηση της κάθε άθροισης (παραπάνω) απαιτεί <math>\scriptstyle O(N^2)</math> διαδικασίες για την παράγωγη ακολουθία μήκους N.  Μια έμμεση μέθοδος, χρησιμοποιώντας μετασχηματισμούς, μπορεί να επωφεληθεί από την <math>\scriptstyle O(N\log N)</math> αποδοτικότητα του [[Μετασχηματισμός Φουριέ|γρήγορου μετασχημαισμού Φουριε (ΓΜΦ)]] για να επιτύχει πολύ καλύτερες επιδόσεις. Επιπλέον, οι περιελίξεις μπορούν να χρησιμοποιηθούν για να
=== Θεώρημα συνέλιξης δυαδικότητα ===
Γραμμή 103:
=== Τριγωνομετρικό πολυώνυμο παρεμβολής ===
Το [[Πολυώνυμο|τριγωνομετρικό πολυώνυμο παρεμβολής]]
: <math>p(t) = \frac{1}{N} \left[ X_0 + X_1 e^{2\pi it} + \cdots + X_{N/2-1} e^{(N/2-1)2\pi it} + X_{N/2} \cos(N\pi t) + X_{N/2+1} e^{(-N/2+1)2\pi it} + \cdots + X_{N-1} e^{-2\pi it} \right]</math> για ''N'' [[Άρτιοι και περιττοί αριθμοί|άρτιος]] ,
: <math>p(t) = \frac{1}{N} \left[ X_0 + X_1 e^{2\pi it} + \cdots + X_{\lfloor N/2 \rfloor} e^{\lfloor N/2 \rfloor 2\pi it} + X_{\lfloor N/2 \rfloor+1} e^{-\lfloor N/2 \rfloor 2\pi it} + \cdots + X_{N-1} e^{-2\pi it} \right]</math> για ''N'' περιττός,
όπου οι συντελεστές ''του X''<sub>''k''</sub> δίνεται από τον ΔΜΦ της ''x''<sub>''n''</sub> παραπάνω, ικανοποιούν την ιδιότητα παρεμβολής <math>p(n/N) = x_n</math> για <math>n=0,\ldots,N-1</math>.
Για άρτιο ''N'', παρατηρούμε ότι η συχνότητα Nyquist
Αυτή η παρεμβολή ''δεν είναι μοναδική'': aliasing σημαίνει ότι θα μπορούσε κανείς να προσθέσει ''N'' σε κάθε μιγαδική-ημιτονοειδή συχνότητες (π. χ. αλλαγή <math>e^{-it}</math> να <math>e^{i(N-1)t}</math> ) χωρίς να αλλάζει η ιδιότητα παρεμβολής, αλλά δίνοντας ''διαφορετικές'' τιμές μεταξύ των <math>x_n</math> σημείων. Η επιλογή παραπάνω, ωστόσο, είναι χαρακτηριστική, διότι έχει δύο χρήσιμες ιδιότητες. Η πρώτη, αποτελείται από ημιτονοειδή κύματα των οποίων οι συχνότητες έχουν το μικρότερο δυνατό μεγέθος: η παρεμβολή είναι περιορισμένου εύρους. Ενώ η δεύτερη, αν <math>x_n</math> είναι πραγματικοί αριθμοί, τότε <math>p(t)</math> είναι πραγματικό.
Γραμμή 115:
=== Το ενιαίο DFT ===
Ένας άλλος τρόπος θεώρησης του ΔΜΦ είναι να σημειωθεί ότι στην παραπάνω συζήτηση, ο ΔΜΦ μπορεί να εκφραστέι ως ο [[Μετασχηματισμός Φουριέ|πινακας ΔΜΦ]], [[Vandermonde matrix]],
που εισήγαγε ο Σιλβέστερ το 1867,
: <math>\mathbf{F} =
Γραμμή 131:
Ο αντίστροφος μετασχηματισμός, στη συνέχεια, δίνεται από τον αντίστροφο του παραπάνω πίνακα,
: <math>\mathbf{F}^{-1}=\frac{1}{N}\mathbf{F}^*</math>
Με ενιαίες [[Πίνακας (μαθηματικά)|ομαλοποιημένες]] σταθερές <math>1/\sqrt{N}</math>, το ΔΜΦ γίνεται ένας [[Εσωτερικό γινόμενο|ενιαίος μετασχηματισμός]], που ορίζεται από έναν ενιαίο πίνακα:
: <math>\mathbf{U}=\mathbf{F}/\sqrt{N}</math>
: <math>\mathbf{U}^{-1}=\mathbf{U}^*</math>
Γραμμή 137:
όπου ''det()''  είναι η [[ορίζουσα]] συνάρτηση. Η ορίζουσα είναι το γινόμενο των ιδιοτιμών, η οποία είναι πάντα <math>\pm 1</math> ή <math>\pm i</math> όπως περιγράφεται παρακάτω. Σε ένα πραγματικό διανυσματικό χώρο, ένας ενιαίος μετασχηματισμός μπορεί να θεωρηθεί απλά ως μία άκαμπτη περιστροφή του συστήματος συντεταγμένων, καθώς και όλες οι ιδιότητες μίας άκαμπτης περιστροφής μπορεί να βρεθεί στον ενιαίο ΔΜΦ.
Η καθετότητα του DFT εκφράζεται τώρα ως [[Γινόμενο διανυσμάτων|ορθοκανονική]] κατάσταση (η οποία προκύπτει σε πολλούς τομείς των μαθηματικών, όπως περιγράφεται στην [[Κυκλοτομικό σώμα|ρίζα της ενότητας]]):
: <math>\sum_{m=0}^{N-1}U_{km}U_{mn}^*=\delta_{kn}</math>
Αν '''X''' ορίζεται ως ο ενιαίος DFT του διανύσματος '''x''', τότε
Γραμμή 145:
Αν δείτε το DFT ως ένα μετασχηματισμό συντεταγμένων, ο οποίος απλώς καθορίζει τις συνιστώσες ενός διανύσματος σε ένα νέο σύστημα συντεταγμένων, τότε η παραπάνω είναι η δήλωση ότι το dot γινόμενο των δύο διανυσμάτων διατηρείται κάτω από έναν ενιαίο μετασχηματισμό DFT. Για την ειδική περίπτωση <math>\mathbf{x} = \mathbf{y}</math>, αυτό σημαίνει ότι το μήκος ενός διανύσματος είναι διατηρημένο, καθώς και—αυτό είναι το θεώρημα του Parseval,
: <math>\sum_{n=0}^{N-1}|x_n|^2 = \sum_{k=0}^{N-1}|X_k|^2</math>
Συνέπεια του [[Μετασχηματισμός Φουριέ|θεωρήματος κυκλικής συνέλιξης]] είναι ότι ο DFT matrix F διαγωνιοποιεί κάθε [[Πίνακας (μαθηματικά)|circulant πίνακα]].
=== Εκφράζοντας την inverse DFT όσον αφορά το DFT ===
Γραμμή 160:
Δηλαδή, το αντίστροφο μετασχηματισμό είναι η ίδια με την προς τα εμπρός μετατρέψει πραγματικά και φανταστικά μέρη αντάλλαξαν τόσο για την εισαγωγή και την παραγωγή, μέχρι την ομαλοποίηση (Duhamel ''et al.'', 1988).
Η σύζευξη κόλπο μπορεί επίσης να χρησιμοποιηθεί για να ορίσετε ένα νέο μετασχηματισμό, που σχετίζονται στενά με τον DFT, που είναι
=== Ιδιοτιμές και ιδιοδιανύσματα ===
Οι [[Ιδιοτιμές και ιδιοδιανύσματα|ιδιοτιμές]] του DFT matrix είναι απλό και γνωστό, ότι τα [[Ιδιοτιμές και ιδιοδιανύσματα|ιδιοδιανύσματα]] είναι περίπλοκο, δεν είναι μοναδική, και αποτελούν αντικείμενο της εν εξελίξει έρευνας.
Σκεφτείτε την ενιαία μορφή <math>\mathbf{U}</math> που ορίζεται ανωτέρω για τον DFT μήκους ''N'', όπου
: <math>\mathbf{U}_{m,n} = \frac1{\sqrt{N}}\omega_N^{(m-1)(n-1)} = \frac1{\sqrt{N}}e^{-\frac{2\pi i}N (m-1)(n-1)}.</math>
Η μήτρα αυτή ικανοποιεί
: <math>\mathbf{U}^4 = \mathbf{I}.</math>
Αυτό μπορούμε να το δούμε από την αντίστροφη ιδιότητες παραπάνω: λειτουργούν <math>\mathbf{U}</math> δύο φορές δίνει τα αρχικά δεδομένα σε αντίστροφη σειρά, έτσι ώστε το λειτουργικό <math>\mathbf{U}</math> τέσσερις φορές δίνει πίσω τα αρχικά δεδομένα και έτσι
: <math>\lambda^4 = 1.</math>
Συνεπώς, οι ιδιοτιμές του <math>\mathbf{U}</math> είναι η τέταρτη [[Κυκλοτομικό σώμα|ρίζες της ενότητας]]: <math>\lambda</math> +1, -1, +''i'', −''i''.
Δεδομένου ότι υπάρχουν μόνο τέσσερις διακριτές ιδιοτιμές για αυτό το <math>N\times N</math> matrix, έχουν κάποια [[Ιδιοτιμές και ιδιοδιανύσματα|πολλαπλότητα]]. Η πολλαπλότητα δίνει τον αριθμό των [[Διανυσματικός χώρος|γραμμικά ανεξάρτητων ιδιοδιανυσμάτων]] που αντιστοιχούν σε κάθε ιδιοτικών. (Σημειώστε ότι υπάρχουν ''N'' ανεξάρτητα ιδιοδιανύσματα, μια ενιαία μήτρα δεν είναι [[Πίνακας (μαθηματικά)|ελαττωματικό]].)
Το πρόβλημα της πολλαπλότητας λύθηκε με McClellan και Πάρκα (1972), αν και αργότερα φαίνεται να έχουν ισοδύναμη με το πρόβλημα λύθηκε από τον [[Καρλ Φρίντριχ Γκάους|Gauss]] (Dickinson και Steiglitz, 1982). Το πλήθος εξαρτάται από την τιμή του ''N'' [[Αριθμητική υπολοίπων|modulo]] 4, και δίνεται από τον ακόλουθο πίνακα:
Γραμμή 209:
| ''m''
|}
Αναφέρεται διαφορετικά, το [[Πίνακας (μαθηματικά)|χαρακτηριστικό πολυώνυμο]] του <math>\mathbf{U}</math> είναι:
: <math>\det (\lambda I - \mathbf{U})=
(\lambda-1)^{\left\lfloor \tfrac {N+4}{4}\right\rfloor}
Γραμμή 215:
(\lambda+i)^{\left\lfloor \tfrac {N+1}{4}\right\rfloor}
(\lambda-i)^{\left\lfloor \tfrac {N-1}{4}\right\rfloor}.</math>
Όχι απλό αναλυτικό τύπο για τη γενική ιδιοδιανύσματα είναι γνωστή. Επιπλέον, τα ιδιοδιανύσματα δεν είναι μοναδική, επειδή κάθε γραμμικός συνδυασμός των ιδιοδιανυσμάτων για τις ίδιες ιδιοτιμές είναι, επίσης, ένα ιδιοδιάνυσμα για ιδιοτικών. Διάφοροι ερευνητές έχουν προτείνει διάφορες επιλογές των ιδιοδιανυσμάτων, επιλεγμένα για να ικανοποιήσουν χρήσιμες ιδιότητες, όπως η [[Καθετοτητα|καθετότητα]] και να "απλές" μορφές (π. χ., 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]],
των οποίων η πιο γνωστή είναι η
και διακριτοποίηση περιοδική άθροιση του φάσματος,
το discretized και περιοδικά αθροίζονται Gaussian συνάρτηση αποδίδει ένα ιδιοδιάνυσμα του διακριτού μετασχηματισμού:
Γραμμή 230 ⟶ 229 :
Για DFT περίοδο ''N'' = 2''L'' = 4''K'', όπου ''K'' είναι ένας ακέραιος, το ακόλουθο είναι ένα ιδιοδιάνυσμα του DFT:
* <math>F(m)=\sin\left(\frac{2\pi}{N}m\right)\prod_{s=K+1}^{L-1}\left[\cos\left(\frac{2\pi}{N}m\right)- \cos\left(\frac{2\pi}{N}s\right)\right]</math>
Η επιλογή των ιδιοδιανυσμάτων του DFT μήτρα έχει εξελιχθεί σημαντικά κατά τα τελευταία έτη, προκειμένου να καθορίσει ένα
=== Η αρχή της αβεβαιότητας ===
| |||