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

καμία σύνοψη επεξεργασίας
= \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

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