Διακριτή κατανομή Φουριέρ

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
Σχέση μεταξύ της (συνεχούς) μετασχηματισμός Fourier και ο διακριτός μετασχηματισμός Fourier. Αριστερή στήλη: συνεχής λειτουργία (επάνω) και του μετασχηματισμού Fourier (κάτω). Κέντρο-αριστερή στήλη: Περιοδική άθροιση της αρχικής λειτουργίας (κορυφή). Μετασχηματισμός Fourier (κάτω μέρος) είναι μηδέν εκτός από διακριτά σημεία. Ο αντίστροφος μετασχηματισμός είναι ένα άθροισμα ημιτονοειδών ονομάζεται σειρά Fourier. Κέντρο-δεξιά στήλη: Αρχική λειτουργία είναι discretized (πολλαπλασιάζεται με το Dirac χτένα) (κορυφή). Του μετασχηματισμού Fourier (κάτω μέρος) είναι περιοδική άθροιση (DTFT) της αρχικής μετασχηματισμό. Δεξιά στήλη: Το DFT (κάτω) υπολογίζει διακριτά δείγματα της συνεχούς DTFT. Το inverse DFT (κορυφή) είναι περιοδική άθροιση των αρχικών δειγμάτων. Το FFT αλγόριθμος υπολογίζει έναν κύκλο του DFT και το αντίστροφο είναι ένας κύκλος του inverse DFT.
Απεικόνιση ενός μετασχηματισμού Fourier (επάνω αριστερά) και της περιοδικής άθροισης (DTFT) στην κάτω αριστερή γωνία. Οι φασματικές ακολουθίες (a) επάνω δεξιά και (b) κάτω δεξιά, αντίστοιχα, υπολογίζονται από την (α) ένα κύκλο του περιοδικού αθροίσματος s(t) και (β) ένα κύκλο του περιοδικού αθροίσματος της s(nT) ακολουθίας. Οι αντίστοιχοι τύποι είναι (α) η σειρά Fourier ολοκλήρωμακαι (β) του DFT άθαθροίσματοςΟι ομοιότητες με το ανρχικό μετασχηματισμό, S(f), και η σχετική υπολογιστική ευκολία είναι συχνά το κίνητρο για τον υπολογισμό ενμιαςFT τηολουθίας.

Στα μαθηματικά, η διακριτή κατανομή Fourier (DFT) μετατρέπει μια πεπερασμένη ακολουθία από ισαπέχοντα δείγματα μιας συνάρτησης σε λίστα με συντελεστές από ένα πεπερασμένο συνδυασμό μιγαδικά ημιτονοειδής, καθορισμένη από τις συχνότητες της, που έχει τις ίδιες τιμές δείγματος. Αυτό μπορεί να ειπωθεί για τη μετατροπή του δείγματος της συνάρτησης από το αρχικό πεδίο ορισμού (συχνά το χρόνο ή τη θέση κατά μήκος της γραμμής) στο πεδίο της συχνότητας.






Η κανονικοποίηση παράγοντας πολλαπλασιασμού του DFT και IDFT (εδώ το 1 και 1/N) και τα σημεία των εκθέτες είναι απλώς συμβάσεις, και διαφέρουν σε ορισμένες θεραπείες. Το μόνο απαιτήσεις αυτών των συμβάσεων είναι ότι ο DFT και IDFT έχουν αντίθετο-σημάδι εκθέτες και ότι το προϊόν τους παράγοντες κανονικοποίησης είναι 1/N. Μια εξομάλυνση της τόσο για τον DFT και IDFT, για παράδειγμα, κάνει το μετατρέπει ενιαία.

Στη συζήτηση που ακολουθεί οι όροι "ακολουθία" και "διάνυσμα" θα θεωρούνται εναλλάξιμα.

Χρησιμοποιώντας τη φόρμουλα του Euler, ο DFT για βρέφη μπορούν να μετατραπούν σε τριγωνομετρικές μορφές μερικές φορές χρησιμοποιείται στη μηχανική και την επιστήμη των υπολογιστών:

Μετασχηματισμός Fourier:

Inverse Fourier Transform:

N = αριθμός φορά δείγματα που έχουμε
n = το τρέχον δείγμα που εξετάζουμε (0, ..., N − 1)
xn = αξία του σήματος στο χρόνο n
k = τρέχουσα συχνότητα εξετάζουμε (0 Hertz έως N-1 Hertz)
Xk = ποσό της συχνότητας k στο σήμα (το Πλάτος και τη Φάση, ένας μιγαδικός αριθμός)

Ιδιότητες[Επεξεργασία | επεξεργασία κώδικα]

Πληρότητα[Επεξεργασία | επεξεργασία κώδικα]

Ο διακριτός μετασχηματισμός Fourier είναι ένας αντιστρέψιμος, γραμμικός μετασχηματισμός

με το που υποδηλώνει το σύνολο των μιγαδικών αριθμών. Με άλλα λόγια, για κάθε N > 0, N-διαστάσεων, συγκρότημα διάνυσμα έχει ένα DFT και IDFT τα οποία με τη σειρά N-διαστάσεων, συγκρότημα φορείς.

Καθετότητα[Επεξεργασία | επεξεργασία κώδικα]

Τα διανύσματα σχηματίζουν μια ορθογώνια βάση πάνω από το σύνολο των N-διαστάσεων, συγκρότημα φορείς:

πού είναι ο Kronecker δέλτα. (Στο τελευταίο βήμα, το άθροισμα είναι ασήμαντο αν , όπου είναι 1+1+⋅⋅⋅=N, και το αντίθετο, είναι μια γεωμετρική σειρά που μπορεί να είναι ρητά αθροίζονται για να αποκτήσετε το μηδέν.) Αυτή η καθετότητα όρος μπορεί να χρησιμοποιηθεί για να αντλήσει η φόρμουλα για την IDFT από τον ορισμό του DFT, και είναι ισοδύναμο με το unitarity ιδιοκτησίας παρακάτω.

Το Plancherel θεώρημα και το θεώρημα του Parseval[Επεξεργασία | επεξεργασία κώδικα]

Αν Xk και Yk είναι το DFTs των xn και yn , αντίστοιχα, τότε το θεώρημα του Parseval μέλη:

όπου η σταρ δηλώνει συγκρότημα σύζευξη. Plancherel θεώρημα είναι μια ειδική περίπτωση το θεώρημα του Parseval και μέλη:

Αυτά τα θεωρήματα είναι επίσης ισοδύναμο με το ενιαίο όρος παρακάτω.

Περιοδικότητα[Επεξεργασία | επεξεργασία κώδικα]

Η περιοδικότητα μπορεί να αποδειχθεί άμεσα από τον ορισμό:

Ομοίως, μπορεί να αποδειχθεί ότι η IDFT φόρμουλα οδηγεί σε μια περιοδική επέκταση.

Shift το θεώρημα[Επεξεργασία | επεξεργασία κώδικα]

Πολλαπλασιάζοντας με γραμμική φάση για κάποιο ακέραιος m αντιστοιχεί σε μια κυκλική μετατόπιση της παραγωγής : αντικαθίσταται από , όπου ο δείκτης ερμηνεύεται modulo N (δηλαδή, σε τακτά χρονικά διαστήματα). Ομοίως, μια κυκλική μετατόπιση της εισόδου αντιστοιχεί σε πολλαπλασιασμό της παραγωγής από μια γραμμική φάση. Μαθηματικά, αν αντιπροσωπεύει το διάνυσμα x τότε

αν
στη συνέχεια
και

Κυκλική συνέλιξη θεώρημα και συσχέτισή τους θεώρημα[Επεξεργασία | επεξεργασία κώδικα]

Το θεώρημα της συνέλιξης για την διακριτού χρόνου μετασχηματισμός Fourier δείχνει ότι συνέλιξη των δύο άπειρες ακολουθίες μπορούν να ληφθούν ως το αντίστροφο μετασχηματισμό των προϊόντων του ατόμου, μεταμορφώνεται. Μια σημαντική απλοποίηση προκύπτει όταν οι ακολουθίες έχουν πεπερασμένο μήκος, N. Όσον αφορά το DFT και inverse DFT, μπορεί να γραφτεί ως εξής:

που είναι η συνέλιξη της ακολουθίας με μια εκτεταμένη σειρά από περιοδική άθροιση:

Ομοίως, η συσχέτισή της και δίνεται από:

Όταν είτε ακολουθία περιέχει μια σειρά από μηδενικά, μήκους L, L+1 από την κυκλική συνέλιξη αποτελέσματα είναι ισοδύναμα με τις αξίες των Μεθόδων που έχουν αναπτυχθεί επίσης να χρησιμοποιήσετε αυτό το ακίνητο ως μέρος μιας αποτελεσματικής διαδικασίας που κατασκευάζει με ένα ή ακολουθία δυνητικά πολύ περισσότερο από την πρακτική μετατρέψει μέγεθος (N). Δύο τέτοιες μέθοδοι είναι που ονομάζεται επικάλυψη-αποθήκευση και επικάλυψη-προσθήκη.[1] Η αποδοτικότητα προκύπτει από το γεγονός ότι μια άμεση αξιολόγηση είτε άθροιση (παραπάνω) απαιτεί από τις επιχειρήσεις για την παραγωγή ακολουθία μήκους N. Μια έμμεση μέθοδο, χρησιμοποιώντας μετασχηματισμούς, μπορούν να επωφεληθούν από την απόδοση του fast Fourier transform (FFT) για να επιτύχει πολύ καλύτερες επιδόσεις. Επιπλέον, οι περιελίξεις μπορούν να χρησιμοποιηθούν για την αποτελεσματική υπολογιστική DFTs μέσω Rader αλγόριθμο FFT και Bluestein είναι αλγόριθμο FFT.

Θεώρημα συνέλιξης δυαδικότητα[Επεξεργασία | επεξεργασία κώδικα]

Μπορεί, επίσης, να αποδειχθεί ότι:

  που είναι η κυκλική συνέλιξη των και .

Τριγωνομετρικό πολυώνυμο παρεμβολής[Επεξεργασία | επεξεργασία κώδικα]

Το τριγωνομετρικό πολυώνυμο παρεμβολής

για N ακόμη ,
για N περιττός,

όπου οι συντελεστές του Xk δίνεται από τον DFT της xn ανωτέρω, πληροί τις παρεμβολή τοποθεσία για .

Ακόμα και για N, παρατηρούμε ότι η συχνότητα Nyquist στοιχείο αντιμετωπίζεται ειδικά.

Αυτή η παρεμβολή είναι μοναδική: aliasing σημαίνει ότι θα μπορούσε κανείς να προσθέσει N σε κάθε του συγκροτήματος-ημιτονοειδής συχνότητες (π. χ. αλλαγή να ) χωρίς να αλλάζει η παρεμβολή τοποθεσία, αλλά δίνοντας διαφορετικές τιμές μεταξύ των σημείων. Η επιλογή παραπάνω, ωστόσο, είναι χαρακτηριστική, διότι έχει δύο χρήσιμες ιδιότητες. Το πρώτο, αποτελείται από ημιτονοειδών των οποίων οι συχνότητες έχουν το μικρότερο δυνατό μεγέθη: η παρεμβολή είναι περιορισμένου εύρους. Δεύτερον, αν είναι πραγματικοί αριθμοί, τότε είναι αληθινό.

Σε αντίθεση, η πιο προφανής τριγωνομετρικό πολυώνυμο παρεμβολής είναι εκείνο στο οποίο οι συχνότητες κυμαίνονται από 0 έως (αντί των περίπου να όπως παραπάνω), παρόμοιο με το inverse DFT φόρμουλα. Αυτή η παρεμβολή δεν δεν ελαχιστοποιήσει την κλίση, και όχι γενικά πραγματική αξία για την πραγματική * η χρήση του είναι ένα κοινό λάθος.

Το ενιαίο DFT[Επεξεργασία | επεξεργασία κώδικα]

Ένα άλλο τρόπο θεώρησης του DFT είναι να σημειωθεί ότι στην παραπάνω συζήτηση, ο DFT μπορεί να εκφράζεται ως ο DFT matrix, Vandermonde matrix, που εισήγαγε ο Σιλβέστερ το 1867,

πού

είναι μια πρωτόγονη Νιοστή ρίζα της ενότητας.

Το αντίστροφο μετασχηματισμό, στη συνέχεια, δίνεται από το αντίστροφο του παραπάνω πίνακα,

Με ενιαία εξομάλυνση σταθερές , το DFT γίνεται ένα ενιαίο μετασχηματισμού, που ορίζεται από μια ενιαία μήτρα:

όπου det() είναι η ορίζουσα λειτουργία. Η ορίζουσα είναι το γινόμενο των ιδιοτιμών, η οποία είναι πάντα ή όπως περιγράφεται παρακάτω. Σε ένα πραγματικό διανυσματικό χώρο, ένα ενιαίο μετασχηματισμού μπορεί να θεωρηθεί ως απλά ένα άκαμπτο περιστροφή του συστήματος συντεταγμένων, καθώς και όλες τις ιδιότητες ενός στερεού περιστροφής μπορεί να βρεθεί στο ενιαίο DFT.

Η καθετότητα του DFT είναι τώρα εκφράζεται ως orthonormality κατάσταση (η οποία προκύπτει σε πολλούς τομείς των μαθηματικών, όπως περιγράφεται στην ρίζα της ενότητας):

Αν X ορίζεται ως το ενιαίο DFT του διανύσματος x, τότε

και το Plancherel θεώρημα εκφράζεται ως

Αν δείτε το DFT ως ένα μετασχηματισμού συντεταγμένων, η οποία απλώς καθορίζει τις συνιστώσες ενός διανύσματος σε ένα νέο σύστημα συντεταγμένων, τότε η παραπάνω είναι η δήλωση ότι η τελεία γινόμενο των δύο διανυσμάτων διατηρείται κάτω από ένα unitary μετασχηματισμό DFT. Για την ειδική περίπτωση , αυτό σημαίνει ότι το μήκος ενός διανύσματος είναι διατηρημένα, καθώς και—αυτό είναι το θεώρημα του Parseval,

Συνέπεια της κυκλικής συνέλιξης θεώρημα είναι ότι ο DFT matrix F diagonalizes κάθε circulant μήτρα.

Εκφράζοντας την inverse DFT όσον αφορά το DFT[Επεξεργασία | επεξεργασία κώδικα]

Μια χρήσιμη ιδιότητα του DFT είναι ότι το inverse DFT μπορεί εύκολα να εκφράζεται σε όρους της (προς τα εμπρός) DFT, μέσω διαφόρων γνωστά "κόλπα". (Για παράδειγμα, σε υπολογισμούς, είναι συχνά βολικό να εφαρμόσει ένα fast Fourier transform αντιστοιχεί σε μία κατεύθυνση μετασχηματισμού και, στη συνέχεια, να πάρει την άλλη κατεύθυνση μετασχηματισμού από την πρώτη.)

Πρώτα, μπορούμε να υπολογίσουμε τον αντίστροφο DFT αντιστρέφοντας τις εισόδους (Duhamel et al., 1988):

(Ως συνήθως, οι δείκτες ερμηνεύονται modulo N * έτσι, για να έχουμε .)

Δεύτερον, κάποιος μπορεί επίσης να συζευχθεί το εισόδους και εξόδους:

Τρίτον, μια παραλλαγή αυτής της σύζευξης κόλπο, η οποία είναι μερικές φορές προτιμότερη, επειδή δεν απαιτεί καμία τροποποίηση των δεδομένων των τιμών, συνεπάγεται την εναλλαγή πραγματικά και φανταστικά μέρη (η οποία μπορεί να γίνει σε έναν υπολογιστή απλά τροποποιώντας δείκτες). Ορίστε swap() με τα πραγματικά και φανταστικά μέρη αντάλλαξαν—ότι είναι, αν στη συνέχεια swap() . Aντίστοιχα, swap() ισούται με . Στη συνέχεια

Δηλαδή, το αντίστροφο μετασχηματισμό είναι η ίδια με την προς τα εμπρός μετατρέψει πραγματικά και φανταστικά μέρη αντάλλαξαν τόσο για την εισαγωγή και την παραγωγή, μέχρι την ομαλοποίηση (Duhamel et al., 1988).

Η σύζευξη κόλπο μπορεί επίσης να χρησιμοποιηθεί για να ορίσετε ένα νέο μετασχηματισμό, που σχετίζονται στενά με τον DFT, που είναι involutory—που είναι, που είναι το δικό αντίστροφο. Ειδικότερα, είναι καθαρά δική inverse: . Μια στενά συνδεδεμένη involutory μετασχηματισμού (με το συντελεστή (1+i) /√2) , δεδομένου ότι οι παράγοντες να ακυρώσει το 2. Για την πραγματική εισροές , το πραγματικό μέρος του δεν είναι άλλη από την διακριτού μετασχηματισμού Hartley, η οποία είναι επίσης involutory.

Ιδιοτιμές και ιδιοδιανύσματα[Επεξεργασία | επεξεργασία κώδικα]

Οι ιδιοτιμές του DFT matrix είναι απλό και γνωστό, ότι τα ιδιοδιανύσματα είναι περίπλοκο, δεν είναι μοναδική, και αποτελούν αντικείμενο της εν εξελίξει έρευνας.

Σκεφτείτε την ενιαία μορφή που ορίζεται ανωτέρω για τον DFT μήκους N, όπου

Η μήτρα αυτή ικανοποιεί το matrix πολυωνυμική εξίσωση:

Αυτό μπορούμε να το δούμε από την αντίστροφη ιδιότητες παραπάνω: λειτουργούν δύο φορές δίνει τα αρχικά δεδομένα σε αντίστροφη σειρά, έτσι ώστε το λειτουργικό τέσσερις φορές δίνει πίσω τα αρχικά δεδομένα και έτσι η μήτρα ταυτότητας. Αυτό σημαίνει ότι οι ιδιοτιμές ικανοποιούν την εξίσωση:

Συνεπώς, οι ιδιοτιμές του είναι η τέταρτη ρίζες της ενότητας: +1, -1, +i, −i.

Δεδομένου ότι υπάρχουν μόνο τέσσερις διακριτές ιδιοτιμές για αυτό το matrix, έχουν κάποια πολλαπλότητα. Η πολλαπλότητα δίνει τον αριθμό των γραμμικά ανεξάρτητων ιδιοδιανυσμάτων που αντιστοιχούν σε κάθε ιδιοτικών. (Σημειώστε ότι υπάρχουν N ανεξάρτητα ιδιοδιανύσματα, μια ενιαία μήτρα δεν είναι ελαττωματικό.)

Το πρόβλημα της πολλαπλότητας λύθηκε με McClellan και Πάρκα (1972), αν και αργότερα φαίνεται να έχουν ισοδύναμη με το πρόβλημα λύθηκε από τον Gauss (Dickinson και Steiglitz, 1982). Το πλήθος εξαρτάται από την τιμή του N modulo 4, και δίνεται από τον ακόλουθο πίνακα:

Οι πολλαπλότητες του ιδιοτιμές λ του ενιαίου DFT matrix U ως συνάρτηση του μετασχηματισμού μέγεθος N (σε σχέση με ένα ακέραιο m).
μέγεθος N λ = +1 λ = -1 λ = - - λ = + -
4m m + 1 m m m − 1
4m + 1 m + 1 m m m
4m + 2 m + 1 m + 1 m m
4m + 3 m + 1 m + 1 m + 1 m

Αναφέρεται διαφορετικά, το χαρακτηριστικό πολυώνυμο του είναι:

Όχι απλό αναλυτικό τύπο για τη γενική ιδιοδιανύσματα είναι γνωστή. Επιπλέον, τα ιδιοδιανύσματα δεν είναι μοναδική, επειδή κάθε γραμμικός συνδυασμός των ιδιοδιανυσμάτων για τις ίδιες ιδιοτιμές είναι, επίσης, ένα ιδιοδιάνυσμα για ιδιοτικών. Διάφοροι ερευνητές έχουν προτείνει διάφορες επιλογές των ιδιοδιανυσμάτων, επιλεγμένα για να ικανοποιήσουν χρήσιμες ιδιότητες, όπως η καθετότητα και να "απλές" μορφές (π. χ., 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, των οποίων η πιο γνωστή είναι η Gaussian συνάρτηση. Από την περιοδική άθροιση της συνάρτησης σημαίνει discretizing το φάσμα συχνοτήτων και διακριτοποίηση περιοδική άθροιση του φάσματος, το discretized και περιοδικά αθροίζονται Gaussian συνάρτηση αποδίδει ένα ιδιοδιάνυσμα του διακριτού μετασχηματισμού:

  • .
Κλειστή μορφή έκφρασης της σειράς δεν είναι γνωστή, αλλά συγκλίνει γρήγορα.

Δύο άλλα απλή κλειστή μορφή αναλυτικών ιδιοδιανύσματα για την ειδική DFT περίοδο N βρέθηκαν Κονγκ, 2008):

Για DFT περίοδο N = 2Λ + 1 = 4Κ +1, όπου K είναι ένας ακέραιος, το ακόλουθο είναι ένα ιδιοδιάνυσμα του DFT:

Για DFT περίοδο N = 2L = 4K, όπου K είναι ένας ακέραιος, το ακόλουθο είναι ένα ιδιοδιάνυσμα του DFT:

Η επιλογή των ιδιοδιανυσμάτων του DFT μήτρα έχει εξελιχθεί σημαντικά κατά τα τελευταία έτη, προκειμένου να καθορίσει ένα διακριτό ανάλογο του κλασματική Fourier transform—DFT matrix μπορούν να ληφθούν για να κλασματική εξουσίες από exponentiating οι ιδιοτιμές (π. χ., Rubio και Santhanam, 2005). Η συνεχής μετασχηματισμός Fourier, το φυσικό ορθογώνια eigenfunctions αποτελούν τον hermite λειτουργίες, έτσι ώστε τα διάφορα διακριτά ανάλογα από αυτά έχουν χρησιμοποιηθεί ως ιδιοδιανύσματα του DFT, όπως ο Kravchuk πολυώνυμα (Atakishiyev και Wolf, 1997). Η "καλύτερη" επιλογή των ιδιοδιανυσμάτων για να ορίσετε μια κλασματικός μετασχηματισμός Fourier διακριτού παραμένει ένα ανοιχτό ερώτημα, όμως.

Η αρχή της αβεβαιότητας[Επεξεργασία | επεξεργασία κώδικα]

Αν η τυχαία μεταβλητή Xk περιορίζεται από

στη συνέχεια

μπορεί να θεωρηθεί ότι αντιπροσωπεύει μια διακριτή συνάρτηση μάζας πιθανότητας του n, με μια σχετική συνάρτηση μάζας πιθανότητας κατασκευαστεί από τη μετασχηματισμένη μεταβλητή,

Για την περίπτωση των συνεχών συναρτήσεων και η απροσδιοριστία του Heisenberg μέλη που

όπου και είναι οι διακυμάνσεις του και , αντίστοιχα, με την ισότητα που επιτεύχθηκαν σε περίπτωση κατάλληλα κανονικοποιημένη κατανομή κατά Gauss. Αν και οι αποκλίσεις μπορεί να είναι κατ ' αναλογία ορίζεται για το DFT, μια ανάλογη αρχή της αβεβαιότητας δεν είναι χρήσιμη, διότι η αβεβαιότητα δεν θα shift-αναλλοίωτη. Ακόμα, μια σημαντική αρχή της αβεβαιότητας έχει εισαχθεί από Massar και Spindel.[2]

Ωστόσο, ο Hirschman εντροπίας αβεβαιότητα θα έχουν ένα χρήσιμο το ανάλογο για την περίπτωση του DFT.[3] Ο Hirschman αρχή της αβεβαιότητας εκφράζεται με την εντροπία Shannon των δύο συναρτήσεις πιθανότητας.

Στην διακριτή περίπτωση, η Σάνον entropies ορίζονται ως

και

και το εντροπίας αβεβαιότητα αρχή γίνεται[3]

Η ισότητα που λαμβάνεται ίση με μεταφράσεις και διαμορφώσεις του ένα κατάλληλα κανονικοποιημένη Kronecker χτένα της περιόδου που είναι ακριβώς ακέραιος διαιρέτης του . Η συνάρτηση μάζας πιθανότητας στη συνέχεια θα είναι ανάλογη με κατάλληλα μεταφρασμένο Kronecker χτένα της περιόδου .[3]

Υπάρχει, επίσης, ένα πολύ γνωστό ντετερμινιστική αρχή της αβεβαιότητας που χρησιμοποιεί το σήμα σπανιότητα (ή ο αριθμός των μη μηδενικών συντελεστών).[4] Ας και είναι ο αριθμός των μη μηδενικών στοιχείων, του χρόνου και της συχνότητας ακολουθίες και , αντίστοιχα. Στη συνέχεια,

Ως άμεση συνέπεια της ανισότητας, της αριθμητικής και της γεωμετρικής σημαίνει, επίσης . Και οι δύο αβεβαιότητα αρχές έδειξαν να είναι σφιχτό για ειδικά επιλεγμένα "φράχτη" ακολουθίες (διακριτά ώθηση τρένα), και βρείτε την πρακτική χρήση για το σήμα εφαρμογές ανάκτησης.[4]

Το πραγματικό εισαγωγής DFT[Επεξεργασία | επεξεργασία κώδικα]

Αν είναι πραγματικοί αριθμοί, όπως συμβαίνει συχνά σε πρακτικές εφαρμογές και, στη συνέχεια, το DFT υπακούει η συμμετρία:

  πού υποδηλώνει συγκρότημα σύζευξη.

Έπεται ότι X0 και XN/2 είναι η πραγματική αξία, και το υπόλοιπο του DFT είναι εντελώς καθορισμένη από ακριβώς N/2-1 μιγαδικών αριθμών.

Γενικευμένη DFT (μετατοπιστεί και μη-γραμμική φάση)[Επεξεργασία | επεξεργασία κώδικα]

Είναι δυνατό να μετατοπίσει την μετατρέψει δειγματοληψία στο χρόνο και/ή συχνοτήτων από κάποια πραγματική βάρδιες α και β, αντίστοιχα. Αυτό είναι μερικές φορές γνωστό ως μια γενικευμένη DFTGDFT), που ονομάζεται επίσης το μετατοπιστεί DFT ή όφσετ DFT, και έχει ανάλογες ιδιότητες με το συνηθισμένο DFT:

Πιο συχνά, βάρδιες (μισό δείγμα). Ενώ η συνήθης DFT αντιστοιχεί σε ένα περιοδικό σήμα τόσο σε χρόνο όσο και η συχνότητα τομείς, παράγει ένα σήμα που είναι αντι-περιοδική στο πεδίο της συχνότητας () και αντίστροφα, για . Έτσι, η συγκεκριμένη περίπτωση είναι γνωστό ως ένα περίεργο χρόνο περίεργο συχνότητας, διακριτός μετασχηματισμός Fourier (ή O2DFT). Τόσο μετατοπίζεται μετασχηματίζει είναι πιο συχνά χρησιμοποιείται για συμμετρική δεδομένα, για να αντιπροσωπεύουν διαφορετικά όρια συμμετρίες, και για το πραγματικό συμμετρικό δεδομένων που αντιστοιχούν σε διαφορετικές μορφές του διακριτού συνημιτόνου και ημιτόνου μεταμορφώνει.

Μια άλλη ενδιαφέρουσα επιλογή , η οποία ονομάζεται επίκεντρο DFTCDFT). Το επίκεντρο DFT έχει την χρήσιμη ιδιότητα ότι, όταν το N είναι πολλαπλάσιο του τέσσερα, τα τέσσερα από τα ιδιοτιμές (βλ. παραπάνω) έχουν ίσες οι πολλαπλότητες (Rubio και Santhanam, 2005)[5]

Ο όρος GDFT χρησιμοποιείται επίσης για τη μη-γραμμική φάση των επεκτάσεων του DFT. Ως εκ τούτου, GDFT μέθοδος παρέχει μια γενίκευση για σταθερό πλάτος ορθογώνια μπλοκ μετατρέπει συμπεριλαμβανομένων γραμμική και μη-γραμμική φάση τύπους. GDFT είναι ένα πλαίσιο για τη βελτίωση του χρόνου και στο πεδίο της συχνότητας ιδιότητες της παραδοσιακής DFT, π. χ. auto/cross-συσχετίσεων, με την προσθήκη των σχεδιαστεί σωστά φάσης που διαμορφώνει τη λειτουργία του (μη-γραμμική, σε γενικές γραμμές) με την αρχική γραμμική φάση λειτουργίες (Akansu και Agirman-Tosun, 2010).[6]

Ο διακριτός μετασχηματισμός Fourier μπορεί να θεωρηθεί ως μια ειδική περίπτωση του z-μετασχηματισμού, αξιολογούνται στη μονάδα κύκλο στο μιγαδικό επίπεδο, περισσότερες γενική z-μετασχηματισμών αντιστοιχούν σε συγκρότημα βάρδιες α και β ανωτέρω.

Πολυδιάστατη DFT[Επεξεργασία | επεξεργασία κώδικα]

Το συνηθισμένο DFT μετατρέπει μια μονοδιάστατη ακολουθία ή σειρά που είναι μια λειτουργία ακριβώς μία διακριτή μεταβλητή n. Η πολυδιάστατη DFT ενός πολυδιάστατου πίνακα που είναι συνάρτηση των d διακριτές κεταβλητές για σε , ορίζεται από:

όπου ως ανωτέρω και το δ παραγωγή δεικτών τρέξιμο από . Αυτό είναι πιο συμπαγώς εκφράζεται σε διανυσματική μορφή, όπου ορίζουμε και ως d-διαστάσεων διανύσματα των δεικτών από το 0 , το οποίο ορίζουμε ως :

όπου η διαίρεση ορίζεται να είναι ο μετασχηματισμός φουριέ, και το άθροισμα υποδηλώνει το σύνολο των ένθετων αθροίσεις παραπάνω.

Το αντίστροφο του πολυδιάστατου DFT είναι ανάλογη με την μονοδιάστατη περίπτωση, δίνεται από:

Όπως η μονοδιάστατη DFT εκφράζει την εισαγωγή ως υπέρθεση των ημιτονοειδών, η πολυδιάστατη DFT εκφράζει την εισαγωγή ως επαλληλία του αεροπλάνο κύματα, ή πολυδιάστατη ημιτονοειδών. Την κατεύθυνση της ταλάντωσης στο χώρο . Η πλάτη είναι . Αυτή η αποσύνθεση είναι μεγάλης σημασίας για τα πάντα, από την ψηφιακή επεξεργασία εικόνας (δύο διαστάσεων) για την επίλυση μερικών διαφορικών εξισώσεων. Το διάλυμα χωρίζεται σε επίπεδα κύματα.

Η πολυδιάστατη DFT μπορεί να υπολογιστεί από την σύνθεση της ακολουθίας μονοδιάστατη DFTs κατά μήκος κάθε διάσταση. Στη δισδιάστατη περίπτωση η ανεξάρτητη DFTs των σειρών (δηλ., κατά μήκος ), υπολογίζονται πρώτα για να σχηματίσουν ένα νέο πίνακα . Στη συνέχεια, η ανεξάρτητη DFTs του y κατά μήκος των στηλών (κατά μήκος ) υπολογίζονται για να διαμορφώσει το τελικό αποτέλεσμα . Εναλλακτικά, οι στήλες μπορεί να υπολογιστεί πρώτα και στη συνέχεια των σειρών. Η σειρά έχει σημασία, επειδή τα ένθετα αθροίσεις παραπάνω μετακίνηση.

Ένας αλγόριθμος για να υπολογίσει μια μονοδιάστατη DFT είναι συνεπώς επαρκές για την αποτελεσματική υπολογίσει μια πολυδιάστατη DFT. Αυτή η προσέγγιση είναι γνωστή ως γραμμή-στήλη αλγόριθμο. Υπάρχουν επίσης εγγενώς πολυδιάστατη FFT αλγόριθμοι.

Το πραγματικό εισαγωγής πολυδιάστατη DFT[Επεξεργασία | επεξεργασία κώδικα]

Για την εισαγωγή δεδομένων που αποτελείται από πραγματικούς αριθμούς, το DFT αποτελέσματα έχουν συζυγής συμμετρία παρόμοια με την μονοδιάστατη περίπτωση, ανωτέρω:

όπου το αστέρι και πάλι δηλώνει συγκρότημα σύζευξη και το -ου δείκτης είναι και πάλι ερμηνεύεται modulo (για ).

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

Η DFT έχει δει ευρεία χρήση σε πολλούς τομείς, μόνο σκίτσο μερικά παραδείγματα παρακάτω (βλέπε επίσης τις αναφορές στο τέλος). Όλες οι εφαρμογές του DFT εξαρτάται σε μεγάλο βαθμό από τη διαθεσιμότητα του ένα γρήγορο αλγόριθμο για να υπολογίσει discrete Fourier και τους αντίστροφες, fast Fourier transform.

Φασματική ανάλυση[Επεξεργασία | επεξεργασία κώδικα]

Όταν ο DFT χρησιμοποιείται για σημάτων, φασματική ανάλυση, η ακολουθία που συνήθως αντιπροσωπεύει ένα πεπερασμένο σύνολο ομοιόμορφα κατανεμημένες φορά-δείγματα κάποιο σήμα , όπου t είναι ο χρόνος. Η μετατροπή από τη συνεχή φορά σε δείγματα (discrete-time) αλλάζει το υποκείμενο μετασχηματισμός Fourier του x(t) σε ένα διακριτού χρόνου μετασχηματισμός Fourier (DTFT), το οποίο συνήθως συνεπάγεται ένα είδος παραμόρφωσης που λέγεται aliasing. Επιλογή κατάλληλου δείγματος ρυθμό (βλέπε Nyquist rate) είναι το κλειδί για την ελαχιστοποίηση αυτής της στρέβλωσης. Επίσης, η μετατροπή από πολύ καιρό (ή άπειρη) ακολουθία σε ένα διαχειρίσιμο μέγεθος συνεπάγεται ένα είδος παραμόρφωσης που ονομάζεται διαρροή, η οποία εκδηλώνεται ως απώλεια λεπτομέρεια.κ.α. ψήφισμα) του DTFT. Επιλογή κατάλληλης υπο-ακολουθία μήκους είναι το κύριο κλειδί για την ελαχιστοποίηση αυτό το αποτέλεσμα. Όταν τα διαθέσιμα δεδομένα (και το χρόνο να το επεξεργαστεί) είναι περισσότερα από το ποσό που απαιτείται για να επιτευχθεί το επιθυμητό ψήφισμα συχνότητας, μια βασική τεχνική είναι να εκτελέσετε πολλές DFTs, για παράδειγμα, για να δημιουργήσετε ένα φασματογράφημα. Αν το επιθυμητό αποτέλεσμα είναι ένα φάσμα ισχύος και το θόρυβο ή τυχαιότητα είναι παρούσα στα δεδομένα, κατά μέσο όρο το μέγεθος συστατικά των πολλαπλών DFTs είναι μια χρήσιμη διαδικασία για να μειώσει τη διασπορά του φάσματος (που ονομάζεται επίσης ένα periodogram σε αυτό το πλαίσιο) * δύο παραδείγματα τέτοιων τεχνικών είναι η Welch μέθοδος και η μέθοδος Bartlett, το γενικό αντικείμενο την εκτίμηση του φάσματος ισχύος του ένα θορυβώδες σήμα ονομάζεται φασματική εκτίμηση.

Τελική πηγή παραμόρφωσης (ή ίσως την ψευδαίσθηση) είναι ο DFT η ίδια, επειδή είναι απλά μια διακριτή δειγματοληψία του DTFT, η οποία είναι μια συνάρτηση συνεχής στο πεδίο της συχνότητας. Αυτό μπορεί να αντιμετωπιστεί με την αύξηση της ανάλυσης του DFT. Η διαδικασία αυτή απεικονίζεται στο Δειγματοληψία του DTFT.

  • Η διαδικασία είναι μερικές φορές αναφέρεται ως zero-padding, η οποία είναι μια συγκεκριμένη εφαρμογή χρησιμοποιείται σε συνδυασμό με το fast Fourier transform (FFT) αλγόριθμο. Η αναποτελεσματικότητα εκτελεί πολλαπλασιασμούς και προσθέσεις με το μηδέν-valued "δείγματα" είναι περισσότερο από αντισταθμίζεται από την εγγενή αποτελεσματικότητα του FFT.
  • Όπως έχει ήδη σημειωθεί, η διαρροή επιβάλλει ένα όριο για την εγγενή ανάλυση του DTFT. Έτσι, υπάρχει ένα πρακτικό όριο για τα οφέλη που μπορούν να προκύψουν από μια λεπτόκοκκη DFT.

Φίλτρο τράπεζα[Επεξεργασία | επεξεργασία κώδικα]

Δείτε FFT φίλτρο τράπεζες και Δειγματοληψία του DTFT.

Συμπίεση δεδομένων[Επεξεργασία | επεξεργασία κώδικα]

Το πεδίο της ψηφιακής επεξεργασίας σήματος εξαρτάται σε μεγάλο βαθμό από δραστηριότητες στο πεδίο των συχνοτήτων (δηλαδή ο μετασχηματισμός Fourier). Για παράδειγμα, αρκετές απώλειες εικόνας και ήχου μέθοδοι συμπίεσης απασχολούν το διακριτός μετασχηματισμός Fourier: το σήμα κόβεται σε μικρά τεμάχια, το καθένα έχει μεταμορφωθεί, και τότε οι συντελεστές Fourier της υψηλές συχνότητες, η οποία υποτίθεται ότι είναι δυσδιάκριτη, απορρίπτονται. Το πρόγραμμα αποσυμπίεσης υπολογίζει τον αντίστροφο μετασχηματισμό με βάση αυτό το μειωμένο αριθμό Fourier συντελεστές. (Εφαρμογές συμπίεσης συχνά χρησιμοποιούν μια εξειδικευμένη μορφή του DFT, ο διακριτός μετασχηματισμός συνημιτόνου ή μερικές φορές το τροποποιημένο διακριτός μετασχηματισμός συνημιτόνου.) Κάποια σχετικά πρόσφατη αλγόριθμους συμπίεσης, ωστόσο, η χρήση wavelet transforms, τα οποία δίνουν μια πιο ομοιόμορφη συμβιβασμό μεταξύ του χρόνου και των συχνοτήτων από εκείνα που λαμβάνονται με τεμαχισμό των δεδομένων σε τμήματα και μετατρέποντας κάθε τμήμα. Στην περίπτωση JPEG2000, αυτό αποφεύγει την ψευδή χαρακτηριστικά της εικόνας που εμφανίζεται όταν οι εικόνες είναι εξαιρετικά συμπιεσμένο με το αρχικό JPEG.

Μερικές διαφορικές εξισώσεις[Επεξεργασία | επεξεργασία κώδικα]

Discrete Fourier χρησιμοποιούνται συχνά για την επίλυση μερικών διαφορικών εξισώσεων, όπου και πάλι ο DFT χρησιμοποιείται ως προσέγγιση για τη σειρά Fourier (που ανακτάται στο όριο άπειρο N). Το πλεονέκτημα αυτής της προσέγγισης είναι ότι επεκτείνει το σήμα σε συγκρότημα exponentials εinx, τα οποία είναι eigenfunctions διαφοροποίησης: d/dx einx = σ einx. Έτσι, στο Fourier εκπροσώπηση, η διαφοροποίηση είναι απλή—απλά πολλαπλασιάστε την από - n. (Σημειώστε, ωστόσο, ότι η επιλογή του n δεν είναι μοναδική λόγω aliasing * η μέθοδος είναι συγκλίνουσα, μια επιλογή παρόμοια με εκείνη των τριγωνομετρικών παρεμβολή παραπάνω τμήμα θα πρέπει να χρησιμοποιηθεί.) Μια γραμμική διαφορική εξίσωση με σταθερούς συντελεστές μετατρέπεται σε μια εύκολα επιλύσιμο αλγεβρική εξίσωση. Ένα, στη συνέχεια, χρησιμοποιεί το inverse DFT να μετατρέψει το αποτέλεσμα πίσω στο κανονικό χωρική αναπαράσταση. Η προσέγγιση αυτή ονομάζεται φασματική μέθοδος.

Πολυωνύμου πολλαπλασιασμός[Επεξεργασία | επεξεργασία κώδικα]

Έστω ότι θέλουμε να υπολογίσουμε το πολυώνυμο προϊόντος γ(x) = a(x) · b(x). Το κανονικό προϊόν έκφρασης για τους συντελεστές c περιλαμβάνει μια γραμμική (άκυκλες) συνέλιξη, όπου οι δείκτες δεν "wrap around." Αυτό μπορεί να ξαναγραφεί ως μια κυκλική συνέλιξη με τη λήψη του συντελεστή φορείς για a(x) και b(x) με το σταθερό όρο πρώτη, μετά την προσάρτηση μηδενικά, έτσι ώστε το προκύπτον συντελεστής διανύσματα a και b έχουν διάσταση d > deg(a(x)) + deg(b(x)). Στη συνέχεια,

Όπου c είναι το διάνυσμα των συντελεστών του c(x), και η συνέλιξη φορέα ορίζεται έτσι

Αλλά συνέλιξη γίνεται πολλαπλασιασμός κάτω από το DFT:

Εδώ το διάνυσμα προϊόντος elementwise. Έτσι, οι συντελεστές του προϊόντος πολυώνυμο c(x) είναι οι όροι 0, ..., deg(a(x)) + deg(b(x)) του συντελεστή διάνυσμα

Με fast Fourier transform, το αποτέλεσμα αλγόριθμος παίρνει O (N log N) αριθμητικές πράξεις. Λόγω της απλότητας και της ταχύτητας, η Κούλι–Τουρκία αλγόριθμο FFT, η οποία περιορίζεται σε σύνθετα μεγέθη, είναι συχνά επιλέγεται για το μετασχηματισμό της λειτουργίας. Σε αυτή την περίπτωση, το d θα πρέπει να επιλέγεται ως το μικρότερο ακέραιο μεγαλύτερο από το άθροισμα των εισροών πολυώνυμο βαθμούς που είναι factorizable σε μικρά prime παράγοντες (π. χ. 2, 3, και 5, ανάλογα με την υλοποίηση FFT).

Πολλαπλασιασμός μεγάλων ακεραίων[Επεξεργασία | επεξεργασία κώδικα]

Ο πιο γρήγορος γνωστοί αλγόριθμοι για τον πολλαπλασιασμό των πολύ μεγάλων ακεραίων χρήση του πολυωνύμου πολλαπλασιασμός μέθοδο που περιγράφεται παραπάνω. Ακέραιοι μπορεί να αντιμετωπιστεί ως η τιμή ενός πολυωνύμου αξιολογούνται συγκεκριμένα τον αριθμό της βάσης, με τους συντελεστές του πολυωνύμου που αντιστοιχούν στα ψηφία σε αυτή τη βάση. Μετά πολυωνύμου πολλαπλασιασμός, σχετικά χαμηλής πολυπλοκότητας μεταφορά διάδοσης βήμα ολοκληρώνει τον πολλαπλασιασμό.

Συνέλιξη[Επεξεργασία | επεξεργασία κώδικα]

Όταν τα δεδομένα είναι convolved με μια λειτουργία με μεγάλη υποστήριξη, όπως για downsampling από ένα μεγάλο λόγος δειγματοληψίας, λόγω της Συνέλιξης θεώρημα και τον αλγόριθμο FFT, μπορεί να είναι πιο γρήγορα για να το μετατρέψει, να πολλαπλασιάσετε pointwise από το μετασχηματισμό του φίλτρου και στη συνέχεια να αντιστραφεί το μεταμορφώσει. Εναλλακτικά, ένα καλό φίλτρο επιτυγχάνεται απλώς με την περικοπή των μετατραπεί δεδομένων και την εκ νέου μετατροπή του συντομευμένη σύνολο δεδομένων.

Κάποια διακριτός μετασχηματισμός Fourier ζεύγη[Επεξεργασία | επεξεργασία κώδικα]

Some DFT pairs
Note
Shift theorem
Real DFT
from the geometric progression formula
from the binomial theorem
is a rectangular window function of W points centered on n=0, where W is an odd integer, and is a sinc-like function (specifically, is a Dirichlet kernel)
Discretization and periodic summation of the scaled Gaussian functions for . Since either or is larger than one and thus warrants fast convergence of one of the two series, for large you may choose to compute the frequency spectrum and convert to the time domain using the discrete Fourier transform.

Γενικεύσεις[Επεξεργασία | επεξεργασία κώδικα]

Εκπροσώπηση θεωρία[Επεξεργασία | επεξεργασία κώδικα]

Ο DFT μπορεί να ερμηνευθεί ως το συγκρότημα-valued εκπροσώπηση θεωρία της πεπερασμένης κυκλικής ομάδας. Με άλλα λόγια, μια ακολουθία από n μιγαδικοί αριθμοί μπορεί να θεωρηθεί ως ένα στοιχείο του n-διαστάσεων χώρο συγκρότημα Cn ή αντίστοιχα μια συνάρτηση f από την πεπερασμένη κυκλική ομάδα τάξης n στο μιγαδικούς αριθμούς, το ZnC. Οπότε η f είναι μια συνάρτηση κλάσης σχετικά με την πεπερασμένη κυκλική ομάδα, και έτσι μπορεί να εκφραστεί ως γραμμικός συνδυασμός των αμείωτη χαρακτήρες αυτής της ομάδας, που είναι οι ρίζες της ενότητας.

Από αυτή την άποψη, μπορεί κανείς να γενικεύσει τον DFT για την εκπροσώπηση θεωρία, γενικά, ή πιο στενά για την εκπροσώπηση θεωρία των πεπερασμένων ομάδων.

Σε πιο στενό ακόμα, μπορεί κανείς να γενικεύσει το DFT είτε από την αλλαγή του στόχου (παίρνει τιμές σε ένα πεδίο, εκτός από το μιγαδικοί αριθμοί), ή το domain (ομάδα άλλη από μια πεπερασμένη κυκλική ομάδα), όπως περιγράφεται στη συνέχεια.

Άλλα πεδία[Επεξεργασία | επεξεργασία κώδικα]

Πολλές από τις ιδιότητες του DFT εξαρτώνται μόνο από το γεγονός ότι είναι μια πρωτόγονη ρίζα της ενότητας, μερικές φορές συμβολίζεται ή (έτσι ώστε ). Αυτές οι ιδιότητες περιλαμβάνουν την πληρότητα, την καθετότητα, Plancherel/Parseval, περιοδικότητα, shift, συνέλιξη, και unitarity ιδιότητες παραπάνω, καθώς και πολλά FFT αλγόριθμοι. Για το λόγο αυτό, ο διακριτός μετασχηματισμός Fourier μπορεί να οριστεί χρησιμοποιώντας ρίζες της ενότητας σε πεδία άλλα από των μιγαδικών αριθμών, και τέτοιες γενικεύσεις είναι κοινώς ονομάζεται αριθμός της θεωρίας μετατρέπει (NTTs) στην περίπτωση των πεπερασμένων πεδίων. Για περισσότερες πληροφορίες, δείτε τον αριθμό της θεωρίας μετατρέψει και διακριτός μετασχηματισμός Fourier (γενικά).

Άλλα πεπερασμένων ομάδων[Επεξεργασία | επεξεργασία κώδικα]

Το πρότυπο DFT πράξεις σε μια ακολουθία x0, x1, ..., xN−1 των μιγαδικών αριθμών, το οποίο μπορεί να θεωρηθεί ως μια συνάρτηση {0, 1, ..., N − 1} → C. Η πολυδιάστατη DFT πράξεις πολυδιάστατων ακολουθιών, η οποία μπορεί να θεωρηθεί ως λειτουργίες

Αυτό υποδηλώνει την γενίκευση να Fourier για την αυθαίρετη πεπερασμένων ομάδων, που δρουν στις συναρτήσεις GC , όπου η G είναι μια πεπερασμένη ομάδα. Σε αυτό το πλαίσιο, το πρότυπο DFT είναι ο μετασχηματισμός Fourier σε μια κυκλική ομάδα, ενώ η πολυδιάστατη DFT είναι ένας μετασχηματισμός Fourier σε άμεσο άθροισμα των κυκλικών ομάδων.

Εναλλακτικές λύσεις[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχουν διάφορες εναλλακτικές λύσεις για τον DFT για διάφορες εφαρμογές, εξέχουσα μεταξύ των οποίων είναι κυματίδια. Το αναλογικό του DFT είναι η discrete wavelet transform (DWT). Από την άποψη του χρόνου–ανάλυση συχνότητας, ένα βασικό περιορισμό του μετασχηματισμού Fourier είναι ότι δεν περιλαμβάνει καταλύματος πληροφορίες, μόνο συχνότητας πληροφορίες, και έτσι έχει δυσκολία στην αντιπροσωπεύουν μεταβατικά φαινόμενα. Όπως κυματίδια έχουν θέση, καθώς και η συχνότητα, είναι καλύτερα σε θέση να αντιπροσωπεύουν τοποθεσία, σε βάρος μεγαλύτερη δυσκολία που αντιπροσωπεύει τη συχνότητα. Για λεπτομέρειες, ανατρέξτε σύγκριση των discrete wavelet transform, με το διακριτό μετασχηματισμό Fourier.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

  • Companion matrix
  • DFT matrix
  • Fast Fourier transform
  • FFTPACK
  • FFTW
  • Γενικεύσεις του Pauli μήτρες
  • Λίστα Fourier που σχετίζονται με το μετατρέπει
  • Πολυδιάστατη μετατρέψει
  • Ο ζακ μετατρέψει

Notes[Επεξεργασία | επεξεργασία κώδικα]

Citations[Επεξεργασία | επεξεργασία κώδικα]

  1. T. G. Stockham, Jr., "High-speed convolution and correlation," in 1966 Proc.
  2. Massar, S.; Spindel, P. (2008). «Uncertainty Relation for the Discrete Fourier Transform». Physical Review Letters 100 (19). doi:10.1103/PhysRevLett.100.190401. Bibcode2008PhRvL.100s0401M. 
  3. 3,0 3,1 3,2 DeBrunner, Victor; Havlicek, Joseph P.; Przebinda, Tomasz; Özaydin, Murad (2005). «Entropy-Based Uncertainty Measures for , and With a Hirschman Optimal Transform for ». IEEE Transactions on Signal Processing 53 (8): 2690. doi:10.1109/TSP.2005.850329. Bibcode2005ITSP...53.2690D. http://redwood.berkeley.edu/w/images/9/95/2002-26.pdf. Ανακτήθηκε στις 2011-06-23. 
  4. 4,0 4,1 Donoho, D.L.; Stark, P.B (1989). «Uncertainty principles and signal recovery». SIAM Journal on Applied Mathematics 49 (3): 906–931. doi:10.1137/0149053. 
  5. Santhanam, Balu; Santhanam, Thalanayar S. "Discrete Gauss-Hermite functions and eigenvectors of the centered discrete Fourier transform"[νεκρός σύνδεσμος], Proceedings of the 32nd IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2007, SPTM-P12.4), vol.
  6. Akansu, Ali N.; Agirman-Tosun, Handan "Generalized Discrete Fourier Transform With Nonlinear Phase", IEEE Transactions on Signal Processing, vol. 58, no. 9, pp. 4547-4556, Sept. 2010.

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

  • Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 0-13-307505-2. 
  • Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R. (1999). Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. ISBN 0-13-754920-2. CS1 maint: Πολλαπλές ονομασίες: authors list (link) CS1 maint: Multiple names: authors list (link)
  • Smith, Steven W. (1999). «Chapter 8: The Discrete Fourier Transform». The Scientist and Engineer's Guide to Digital Signal Processing (Second έκδοση). San Diego, Calif.: California Technical Publishing. ISBN 0-9660176-3-3. 
  • Cormen, Thomas H.; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). «Chapter 30: Polynomials and the FFT». Introduction to Algorithms (Second έκδοση). MIT Press and McGraw-Hill. σελίδες 822–848. ISBN 0-262-03293-7.  esp. section 30.2: The DFT and FFT, pp. 830–838.
  • P. Duhamel; B. Piron; J. M. Etcheto (1988). «On computing the inverse DFT». IEEE Trans. Acoust., Speech and Sig. Processing 36 (2): 285–286. doi:10.1109/29.1519. 
  • J. H. McClellan; T. W. Parks (1972). «Eigenvalues and eigenvectors of the discrete Fourier transformation». IEEE Trans. Audio Electroacoust. 20 (1): 66–74. doi:10.1109/TAU.1972.1162342. 
  • Bradley W. Dickinson; Kenneth Steiglitz (1982). «Eigenvectors and functions of the discrete Fourier transform». IEEE Trans. Acoust., Speech and Sig. Processing 30 (1): 25–31. doi:10.1109/TASSP.1982.1163843.  (Note that this paper has an apparent typo in its table of the eigenvalue multiplicities: the +i/−i columns are interchanged. The correct table can be found in McClellan and Parks, 1972, and is easily confirmed numerically.)
  • F. A. Grünbaum (1982). «The eigenvectors of the discrete Fourier transform». J. Math. Anal. Appl. 88 (2): 355–363. doi:10.1016/0022-247X(82)90199-8. 
  • Natig M. Atakishiyev; Kurt Bernardo Wolf (1997). «Fractional Fourier-Kravchuk transform». J. Opt. Soc. Am. A 14 (7): 1467–1477. doi:10.1364/JOSAA.14.001467. Bibcode1997JOSAA..14.1467A. 
  • C. Candan; M. A. Kutay; H. M.Ozaktas (2000). «The discrete fractional Fourier transform». IEEE Trans. on Signal Processing 48 (5): 1329–1337. doi:10.1109/78.839980. Bibcode2000ITSP...48.1329C. 
  • Magdy Tawfik Hanna, Nabila Philip Attalla Seif, and Waleed Abd El Maguid Ahmed (2004). «Hermite-Gaussian-like eigenvectors of the discrete Fourier transform matrix based on the singular-value decomposition of its orthogonal projection matrices». IEEE Trans. Circ. Syst. I 51 (11): 2245–2254. doi:10.1109/TCSI.2004.836850.  CS1 maint: Multiple names: authors list (link)
  • Shamgar Gurevich; Ronny Hadani (2009). «On the diagonalization of the discrete Fourier transform». Applied and Computational Harmonic Analysis 27 (1): 87–99. doi:10.1016/j.acha.2008.11.003. preprint at. 
  • Shamgar Gurevich; Ronny Hadani; Nir Sochen (2008). «The finite harmonic oscillator and its applications to sequences, communication and radar». IEEE Transactions on Information Theory 54 (9): 4239–4253. doi:10.1109/TIT.2008.926440. preprint at. 
  • Juan G. Vargas-Rubio; Balu Santhanam (2005). «On the multiangle centered discrete fractional Fourier transform». IEEE Sig. Proc. Lett. 12 (4): 273–276. doi:10.1109/LSP.2005.843762. Bibcode2005ISPL...12..273V. 
  • J. Cooley, P. Lewis, and P. Welch (1969). «The finite Fourier transform». IEEE Trans. Audio Electroacoustics 17 (2): 77–85. doi:10.1109/TAU.1969.1162036.  CS1 maint: Multiple names: authors list (link)
  • F.N. Kong (2008). «Analytic Expressions of Two Discrete Hermite-Gaussian Signals». IEEE Trans. Circuits and Systems –II: Express Briefs. 55 (1): 56–60. doi:10.1109/TCSII.2007.909865. 

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]