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

καμία σύνοψη επεξεργασίας
: και <math>\mathcal{F}(\{x_{n-m}\})_k=X_k\cdot e^{-\frac{2\pi i}{N}k m}</math>
 
=== Θεώρημα κυκλικής συνέλιξης και το θεώρημα συσχέτισης ===
=== Κυκλική συνέλιξη θεώρημα και συσχέτισή τους θεώρημα ===
Το [[Μετασχηματισμός Φουριέ|θεώρημα συνέλιξης]] για το [[Μετασχηματισμός Φουριέ|χρονικό-διακριτό μετασχηματισμό Fourier]] δείχνει ότι συνέλιξη των δύο άπειρων ακολουθιών μπορούν να ληφθούν ως ο αντίστροφος μετασχηματισμός των προϊόντων των ατομικών μετασχηματισμών. Μια σημαντική απλοποίηση προκύπτει όταν οι ακολουθίες έχουν πεπερασμένο μήκος, '''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>
Συνέπεια του [[Μετασχηματισμός Φουριέ|θεωρήματος κυκλικής συνέλιξης]] είναι ότι ο DFT matrix F διαγωνιοποιεί κάθε [[Πίνακας (μαθηματικά)|circulant πίνακα]].
 
=== Εκφράζοντας τηντον inverseαντίστροφο DFT όσονσε αφοράόρους τοτου DFT ===
Μια χρήσιμη ιδιότητα του DFT είναι ότι ο αντίστροφος DFT μπορεί εύκολα να εκφραστεί σε όρους του (forward) DFT, μέσω διαφόρων γνωστών "κόλπων". (Για παράδειγμα, σε υπολογισμούς, είναι συχνά βολικό να εφαρμόστει ένας γρήγορος μετασχηματισμός Φουριέ που αντιστοιχεί σε μία κατεύθυνση μετασχηματισμού και, στη συνέχεια, να πάρει την άλλη κατεύθυνση μετασχηματισμού από την πρώτη.)
 
Το πρόβλημα της πολλαπλότητας λύθηκε με McClellan και Πάρκα (1972), αν και αργότερα φαίνεται να έχουν ισοδύναμη με το πρόβλημα λύθηκε από τον [[Καρλ Φρίντριχ Γκάους|Gauss]] (Dickinson και Steiglitz, 1982). Το πλήθος εξαρτάται από την τιμή του ''N'' [[Αριθμητική υπολοίπων|modulo]] 4, και δίνεται από τον ακόλουθο πίνακα:
{| class="wikitable" style="margin:auto;"
|+ align="bottom" | Οι πολλαπλότητες τουτων ιδιοτιμέςιδιοτιμων λ του ενιαίου DFT matrixπίνακα '''U''' ως συνάρτηση του μετασχηματισμού μέγεθοςμεγέθους ''N'' (σε σχέση με ένα ακέραιο ''m'').
 
! μέγεθος ''N''
25

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