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

καμία σύνοψη επεξεργασίας
 
=== Κυκλική συνέλιξη θεώρημα και συσχέτισή τους θεώρημα ===
Το [Μετασχηματισμός Φουριέ|θεώρημα συνέλιξης] για το χρονικό-διακριτό μετασχηματισμό 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\ ,
</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>
Ομοίως, η συσχέτισή της &#x20;<math>\mathbf{x}</math>&#x20; και &#x20;<math>\mathbf{y_N}</math>&#x20; δίνεται από''':'''
= \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'''). Δύο τέτοιες μέθοδοι είναι που ονομάζεται επικάλυψη-αποθήκευση και επικάλυψη-προσθήκη.<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> απόδοση του fast Fourier transform (FFT) για να επιτύχει πολύ καλύτερες επιδόσεις. Επιπλέον, οι περιελίξεις μπορούν να χρησιμοποιηθούν για την αποτελεσματική υπολογιστική DFTs μέσω Rader αλγόριθμο FFT και Bluestein είναι αλγόριθμο FFT.
 
=== Θεώρημα συνέλιξης δυαδικότητα ===
25

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