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

καμία σύνοψη επεξεργασίας
 
=== Θεώρημα κυκλικής συνέλιξης και το θεώρημα συσχέτισης ===
Το [[Μετασχηματισμός Φουριέ|θεώρημα συνέλιξης]] για το [[Μετασχηματισμός Φουριέ|χρονικό-διακριτό μετασχηματισμό Fourier]] δείχνει ότι συνέλιξη των δύο άπειρων ακολουθιών μπορούν να ληφθούν ως ο αντίστροφος μετασχηματισμός των προϊόντων των ατομικών μετασχηματισμών. Μια σημαντική απλοποίηση προκύπτει όταν οι ακολουθίες έχουν πεπερασμένο μήκος, '''N'''. Όσον αφορά το ΔΜΦDFT και το αντίστροφο ΔΜΦ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\ ,
= \sum_{l=0}^{N-1}x_l^* \cdot (y_N)_{n+l} \ \ \stackrel{\mathrm{def}}{=} \ \ (\mathbf{x \star y_N})_n\ .
</math>
Όταν κάθε ακολουθία περιέχει μια σειρά από μηδενικά, μήκους L,&#x20; L+1 από τα αποτελέσματα των κυκλικών συνελέξεων είναι ισοδύναμα με τις αξίες των &#x20;<math>\mathbf{x * y}.</math>&#x20; Μέθοδοι έχουν αναπτυχθεί επίσης για να χρησιμοποιηθεί αυτή η ιδιότητα ως μέρος μιας αποτελεσματικής διαδικασίας που κατασκευάζει &#x20;<math>\mathbf{x * y}</math>&#x20; με μία <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. &#x20;Μια έμμεση μέθοδος, χρησιμοποιώντας μετασχηματισμούς, μπορεί να επωφεληθεί από την <math>\scriptstyle O(N\log N)</math> αποδοτικότητα του [[Μετασχηματισμός Φουριέ|γρήγορου μετασχημαισμού Φουριε (ΓΜΦ)]] για να επιτύχει πολύ καλύτερες επιδόσεις. Επιπλέον, οι περιελίξεις μπορούν να χρησιμοποιηθούν για να υπολογίσουν αποτελεσματικά DFTs μέσω τοντου αλγόριθμοαλγορίθμου Rader FFT και τοντου Bluestein αλγόριθμο FFT.
 
=== Δυαδικότητα θεωρήματος συνέλιξης ===
: <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> δίνεται από τον ΔΜΦDFT της ''x''<sub>''n''</sub> παραπάνω, ικανοποιούν την ιδιότητα παρεμβολής <math>p(n/N) = x_n</math> για <math>n=0,\ldots,N-1</math>.
 
Για άρτιο ''N'', παρατηρούμε ότι η συχνότητα Nyquist component <math>\frac{X_{N/2}}{N} \cos(N\pi t)</math> αντιμετωπίζεται ειδικά.
Αυτή η παρεμβολή ''δεν είναι μοναδική'': 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> είναι πραγματικό.
 
Σε αντίθεση, το πιο προφανές τριγωνομετρικό πολυώνυμο παρεμβολής είναι εκείνο στο οποίο οι συχνότητες κυμαίνονται από 0 έως <math>N-1</math> (σε αντίθεση με <math>-N/2</math> να <math>+N/2</math> όπως παραπάνω), παρόμοιο με τον αντίστροφο τύπο ΔΜΦDFT. Αυτή η παρεμβολή ''δεν'' ελαχιστοποιεί την κλίση, και ''δεν είναι'' γενικά πραγματικής-τιμής για πραγματικό <math>x_n</math> *, η χρήση του είναι ένα κοινό λάθος.
 
=== Το ενιαίο DFT ===
Ένας άλλος τρόπος θεώρησης του ΔΜΦDFT είναι να σημειωθεί ότι στην παραπάνω συζήτηση, ο ΔΜΦDFT μπορεί να εκφραστέι ως ο [[Μετασχηματισμός Φουριέ|πινακας ΔΜΦ]], [[Vandermonde matrix]],
που εισήγαγε ο Σιλβέστερ το 1867,
: <math>\mathbf{F} =
Ο αντίστροφος μετασχηματισμός, στη συνέχεια, δίνεται από τον αντίστροφο του παραπάνω πίνακα,
: <math>\mathbf{F}^{-1}=\frac{1}{N}\mathbf{F}^*</math>
Με ενιαίες [[Πίνακας (μαθηματικά)|ομαλοποιημένες]] σταθερές <math>1/\sqrt{N}</math>, τοο ΔΜΦDFT γίνεται ένας [[Εσωτερικό γινόμενο|ενιαίος μετασχηματισμός]], που ορίζεται από έναν ενιαίο πίνακα:
: <math>\mathbf{U}=\mathbf{F}/\sqrt{N}</math>
: <math>\mathbf{U}^{-1}=\mathbf{U}^*</math>
: <math>|\det(\mathbf{U})|=1</math>
όπου ''det()''&#x20; είναι η [[ορίζουσα]] συνάρτηση. Η ορίζουσα είναι το γινόμενο των ιδιοτιμών, η οποία είναι πάντα <math>\pm 1</math> ή <math>\pm i</math> όπως περιγράφεται παρακάτω. Σε ένα πραγματικό διανυσματικό χώρο, ένας ενιαίος μετασχηματισμός μπορεί να θεωρηθεί απλά ως μία άκαμπτη περιστροφή του συστήματος συντεταγμένων, καθώς και όλες οι ιδιότητες μίας άκαμπτης περιστροφής μπορεί να βρεθεί στον ενιαίο ΔΜΦDFT.
 
Η καθετότητα του DFT εκφράζεται τώρα ως [[Γινόμενο διανυσμάτων|ορθοκανονική]] κατάσταση (η οποία προκύπτει σε πολλούς τομείς των μαθηματικών, όπως περιγράφεται στην [[Κυκλοτομικό σώμα|ρίζα της ενότητας]]):
25

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