Διακριτός μετασχηματισμός Φουριέ

Σχέση μεταξύ του (συνεχούς) μετασχηματισμού Fourier και του διακριτού μετασχηματισμού Fourier. Αριστερή στήλη: μία συνεχής συνάρτηση (επάνω) και ο μετασχηματισμός της σε Fourier (κάτω). Κέντρο-αριστερή στήλη: Περιοδική άθροιση της αρχικής συνάρτησης (κορυφή). Μετασχηματισμός Fourier (κάτω μέρος) είναι μηδέν εκτός από τα διακριτά σημεία. Ο αντίστροφος μετασχηματισμός είναι ένα άθροισμα ημιτονοειδών και ονομάζεται σειρά Fourier. Κέντρο-δεξιά στήλη: Η αρχική συνάρτηση διακριτοποιείται (πολλαπλασιάζεται με το Dirac comb ) (κορυφή). O μετασχηματισμός της σε Fourier (κάτω μέρος) είναι μια περιοδική άθροιση (DTFT: Διακριτού-χρόνου μετασχηματισμό Fourier ) του αρχικού μετασχηματισμού της. Δεξιά στήλη: Το DFT(Διακριτός μετασχηματισμός Fourier) (κάτω) υπολογίζει διακριτά δείγματα της συνεχούς DTFT. Ο αντίστροφος DFT (κορυφή) είναι περιοδική άθροιση των αρχικών δειγμάτων. O FFT(γρήγορος μετασχηματισμός Fourier) αλγόριθμος υπολογίζει έναν κύκλο του DFT και το αντίστροφο του είναι ένας κύκλος του αντίστροφου DFT.

Απεικόνιση ενός μετασχηματισμού Fourier (επάνω αριστερά) και την περιοδική άθροιση (DTFT) στην κάτω αριστερή γωνία. Η φασματική ακολουθίες (a) επάνω δεξιά και (b) κάτω δεξιά, αντίστοιχα, υπολογίζονται από την (α) ένα κύκλο του περιοδικού άθροισμα s(t) και (β) ένα κύκλο του περιοδικού άθροισμα των s(nT) ακολουθία. Οι αντίστοιχοι τύποι είναι (α) η σειρά Fourier αναπόσπαστο και (β) του DFT άθροιση. Οι ομοιότητες με το αρχικό μετασχηματισμό, S(f), και η σχετική υπολογιστική ευκολία είναι συχνά το κίνητρο για τον υπολογισμό ενός DFT της ακολουθίας.

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

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

Ο DFT είναι το πιο σημαντικό διακριτό μετασχηματισμό, που χρησιμοποιείται για να εκτελέσει την ανάλυση Fourier σε πολλές πρακτικές εφαρμογές. Στην ψηφιακή επεξεργασία σήματος, η λειτουργία είναι οποιαδήποτε ποσότητα ή σήμα που ποικίλει με την πάροδο του χρόνου, όπως η πίεση των υγιών κυμάτων, ραδιόφωνο, σήμα, ή ημερήσια θερμοκρασία μετρήσεις, δειγματοληψίες πάνω από ένα πεπερασμένο χρονικό διάστημα (συνήθως ορίζεται από ένα παράθυρο λειτουργία). Στην επεξεργασία εικόνας, τα δείγματα μπορεί να είναι οι τιμές των pixels κατά μήκος της γραμμής ή της στήλης των εικόνων raster. Ο DFT είναι, επίσης, χρησιμοποιείται για την αποτελεσματική επίλυση μερικών διαφορικών εξισώσεων, και να εκτελέσετε άλλες ενέργειες, όπως οι έλικες ή πολλαπλασιασμός μεγάλων ακεραίων.

Δεδομένου ότι πρόκειται για ένα πεπερασμένο ποσό των δεδομένων, μπορεί να εφαρμοστεί σε υπολογιστές με αριθμητική αλγόριθμοι ή ακόμα και dedicated hardware. Αυτές οι εφαρμογές συνήθως χρησιμοποιούν αποτελεσματική fast Fourier transform (FFT) αλγόριθμοι; τόσο πολύ, που οι όροι "FFT" και "DFT" συχνά χρησιμοποιούνται εναλλακτικά. Πριν από την τρέχουσα χρήση, το "FFT" initialism μπορεί επίσης να χρησιμοποιηθεί για την ασαφής όρος "πεπερασμένος μετασχηματισμός Fourier".

Ορισμός

Η ακολουθία των N μιγαδικοί αριθμοί $x_{0},x_{1},\ldots ,x_{N-1}$ μετατρέπεται σε ένα N-περιοδική ακολουθία μιγαδικών αριθμών:

Λόγω της περιοδικότητας, το σύνηθες τομέα της k υπολογίσει είναι το [0, N − 1]. Αυτή είναι πάντα η περίπτωση, όταν ο DFT υλοποιείται μέσω του Fast Fourier transform (fft αλγόριθμο. Αλλά και άλλες κοινές περιοχές είναι το[−N/2, N/2 − 1] (N ) και [−(N − 1)/2, (N − 1)/2] (N περιττός), όπως όταν το αριστερό και το δεξί ήμισυ ενός FFT παραγωγή ακολουθία αντάλλαξαν.

Ο μετασχηματισμός είναι μερικές φορές συμβολίζεται με το σύμβολο ${\mathcal {F}}$, όπως και $\mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}$ ή ${\mathcal {F}}\left(\mathbf {x} \right)$ ή ${\mathcal {F}}\mathbf {x}$.

Eq.1 μπορεί να ερμηνευθεί ή παράγωγα με διάφορους τρόπους, για παράδειγμα:

• Εντελώς περιγράφει την διακριτού χρόνου μετασχηματισμός Fourier (DTFT) της N-περιοδική ακολουθία, η οποία περιλαμβάνει μόνο διακριτή συχνότητα στοιχεία. (Χρησιμοποιώντας τον DTFT με περιοδική δεδομένων)
• Μπορεί επίσης να παρέχει ομοιόμορφα κατανεμημένες δείγματα της συνεχούς DTFT ενός πεπερασμένου μήκους ακολουθία. (Δειγματοληψία του DTFT)
• Είναι ο σταυρός συσχέτιση της εισαγωγής ακολουθία x_n, και ένα συγκρότημα ημιτονοειδής στη συχνότητα k/N. Έτσι λειτουργεί σαν ένα matched filter για αυτή τη συχνότητα.
• Είναι το διακριτό αναλογία του τύπου για τους συντελεστές της σειράς Fourier:

το οποίο είναι, επίσης, N-περιοδική. Στον τομέα $\scriptstyle n\ \in \ [0,\ N-1],$ αυτό είναι το αντίστροφο μετασχηματισμό του Eq.1. Σε αυτή την ερμηνεία, το καθένα $X_{k}$ είναι ένας μιγαδικός αριθμός που κωδικοποιεί τόσο το εύρος και τη φάση του μια ημιτονοειδή συνιστώσα $(e^{2\pi ikn/N})$ της λειτουργίας $x_{n}.$ Του ημιτονοειδής είναι η συχνότητα είναι k κύκλους ανά N δείγματα. Το εύρος και η φάση είναι:

$|X_{k}|/N={\sqrt {\operatorname {Re} (X_{k})^{2}+\operatorname {Im} (X_{k})^{2}}}/N$

$\arg(X_{k})=\operatorname {atan2} {\big (}\operatorname {Im} (X_{k}),\operatorname {Re} (X_{k}){\big )}=-i\operatorname {ln} \left({\frac {X_{k}}{|X_{k}|}}\right),$

πού atan2 είναι τα δύο επιχείρημα μορφή της arctan λειτουργία.

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

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

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

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

Inverse Fourier Transform:

N = αριθμός φορά δείγματα που έχουμε

n = το τρέχον δείγμα που εξετάζουμε (0, ..., N − 1)

x_n = αξία του σήματος στο χρόνο n

k = τρέχουσα συχνότητα εξετάζουμε (0 Hertz έως N-1 Hertz)

X_k = ποσό της συχνότητας k στο σήμα (το Πλάτος και τη Φάση, ένας μιγαδικός αριθμός)

Ιδιότητες

Πληρότητα

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

${\mathcal {F}}\colon \mathbb {C} ^{N}\to \mathbb {C} ^{N}$

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

Καθετότητα

Τα διανύσματα $u_{k}=\left[e^{{\frac {2\pi i}{N}}kn}\;|\;n=0,1,\ldots ,N-1\right]^{T}$ σχηματίζουν μια ορθογώνια βάση πάνω από το σύνολο των N-διαστάσεων, συγκρότημα φορείς:

$u_{k}^{T}u_{k'}^{*}=\sum _{n=0}^{N-1}\left(e^{{\frac {2\pi i}{N}}kn}\right)\left(e^{{\frac {2\pi i}{N}}(-k')n}\right)=\sum _{n=0}^{N-1}e^{{\frac {2\pi i}{N}}(k-k')n}=N~\delta _{kk'}$

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

Το Plancherel θεώρημα και το θεώρημα του Parseval

Αν X_k και Y_k είναι το DFTs των x_n και y_n , αντίστοιχα, τότε το θεώρημα του Parseval μέλη:

$\sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}$

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

$\sum _{n=0}^{N-1}|x_{n}|^{2}={\frac {1}{N}}\sum _{k=0}^{N-1}|X_{k}|^{2}.$

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

Περιοδικότητα

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

$X_{k+N}\ {\stackrel {\mathrm {def} }{=}}\ \sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}(k+N)n}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}\underbrace {e^{-2\pi in}} _{1}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}=X_{k}.$

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

Shift το θεώρημα

Πολλαπλασιάζοντας $x_{n}$ με γραμμική φάση $e^{{\frac {2\pi i}{N}}nm}$ για κάποιο ακέραιος m αντιστοιχεί σε μια κυκλική μετατόπιση της παραγωγής $X_{k}$: $X_{k}$ αντικαθίσταται από $X_{k-m}$, όπου ο δείκτης ερμηνεύεται modulo N (δηλαδή, σε τακτά χρονικά διαστήματα). Ομοίως, μια κυκλική μετατόπιση της εισόδου $x_{n}$ αντιστοιχεί σε πολλαπλασιασμό της παραγωγής $X_{k}$ από μια γραμμική φάση. Μαθηματικά, αν $\{x_{n}\}$ αντιπροσωπεύει το διάνυσμα x τότε

αν ${\mathcal {F}}(\{x_{n}\})_{k}=X_{k}$

στη συνέχεια ${\mathcal {F}}(\{x_{n}\cdot e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m}$

και ${\mathcal {F}}(\{x_{n-m}\})_{k}=X_{k}\cdot e^{-{\frac {2\pi i}{N}}km}$

Κυκλική συνέλιξη θεώρημα και συσχέτισή τους θεώρημα

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

${\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}\ ,$

που είναι η συνέλιξη της $\mathbf {x}$ ακολουθίας με μια $\mathbf {y}$ εκτεταμένη σειρά από περιοδική άθροιση:

$(\mathbf {y_{N}} )_{n}\ {\stackrel {\mathrm {def} }{=}}\ \sum _{p=-\infty }^{\infty }y_{(n-pN)}=y_{n(modN)}.\,$

Ομοίως, η συσχέτισή της $\mathbf {x}$ και $\mathbf {y_{N}}$ δίνεται από:

${\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\star y_{N}} )_{n}\ .$

Όταν είτε ακολουθία περιέχει μια σειρά από μηδενικά, μήκους L, L+1 από την κυκλική συνέλιξη αποτελέσματα είναι ισοδύναμα με τις αξίες των $\mathbf {x*y} .$ Μεθόδων που έχουν αναπτυχθεί επίσης να χρησιμοποιήσετε αυτό το ακίνητο ως μέρος μιας αποτελεσματικής διαδικασίας που κατασκευάζει $\mathbf {x*y}$ με ένα $\mathbf {x}$ ή $\mathbf {y}$ ακολουθία δυνητικά πολύ περισσότερο από την πρακτική μετατρέψει μέγεθος (N). Δύο τέτοιες μέθοδοι είναι που ονομάζεται επικάλυψη-αποθήκευση και επικάλυψη-προσθήκη. Η αποδοτικότητα προκύπτει από το γεγονός ότι μια άμεση αξιολόγηση είτε άθροιση (παραπάνω) απαιτεί από τις $\scriptstyle O(N^{2})$ επιχειρήσεις για την παραγωγή ακολουθία μήκους N. Μια έμμεση μέθοδο, χρησιμοποιώντας μετασχηματισμούς, μπορούν να επωφεληθούν από την $\scriptstyle O(N\log N)$ απόδοση του fast Fourier transform (FFT) για να επιτύχει πολύ καλύτερες επιδόσεις. Επιπλέον, οι περιελίξεις μπορούν να χρησιμοποιηθούν για την αποτελεσματική υπολογιστική DFTs μέσω Rader αλγόριθμο FFT και Bluestein είναι αλγόριθμο FFT.

Θεώρημα συνέλιξης δυαδικότητα

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

${\mathcal {F}}\left\{\mathbf {x\cdot y} \right\}_{k}\ {\stackrel {\mathrm {def} }{=}}\sum _{n=0}^{N-1}x_{n}\cdot y_{n}\cdot e^{-{\frac {2\pi i}{N}}kn}$

$={\frac {1}{N}}(\mathbf {X*Y_{N}} )_{k},\,$   που είναι η κυκλική συνέλιξη των $\mathbf {X}$ και $\mathbf {Y}$.

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

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

$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]$ για N ακόμη ,

$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]$ για N περιττός,

όπου οι συντελεστές του X_k δίνεται από τον DFT της x_n ανωτέρω, πληροί τις παρεμβολή τοποθεσία $p(n/N)=x_{n}$ για $n=0,\ldots ,N-1$.

Ακόμα και για N, παρατηρούμε ότι η συχνότητα Nyquist στοιχείο ${\frac {X_{N/2}}{N}}\cos(N\pi t)$ αντιμετωπίζεται ειδικά.

Αυτή η παρεμβολή είναι μοναδική: aliasing σημαίνει ότι θα μπορούσε κανείς να προσθέσει N σε κάθε του συγκροτήματος-ημιτονοειδής συχνότητες (π. χ. αλλαγή $e^{-it}$ να $e^{i(N-1)t}$ ) χωρίς να αλλάζει η παρεμβολή τοποθεσία, αλλά δίνοντας διαφορετικές τιμές μεταξύ των $x_{n}$ σημείων. Η επιλογή παραπάνω, ωστόσο, είναι χαρακτηριστική, διότι έχει δύο χρήσιμες ιδιότητες. Το πρώτο, αποτελείται από ημιτονοειδών των οποίων οι συχνότητες έχουν το μικρότερο δυνατό μεγέθη: η παρεμβολή είναι περιορισμένου εύρους. Δεύτερον, αν $x_{n}$ είναι πραγματικοί αριθμοί, τότε $p(t)$ είναι αληθινό.

Σε αντίθεση, η πιο προφανής τριγωνομετρικό πολυώνυμο παρεμβολής είναι εκείνο στο οποίο οι συχνότητες κυμαίνονται από 0 έως $N-1$ (αντί των περίπου $-N/2$ να $+N/2$ όπως παραπάνω), παρόμοιο με το inverse DFT φόρμουλα. Αυτή η παρεμβολή δεν δεν ελαχιστοποιήσει την κλίση, και όχι γενικά πραγματική αξία για την πραγματική $x_{n}$ * η χρήση του είναι ένα κοινό λάθος.

Το ενιαίο DFT

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

$\mathbf {F} ={\begin{bmatrix}\omega _{N}^{0\cdot 0}&\omega _{N}^{0\cdot 1}&\ldots &\omega _{N}^{0\cdot (N-1)}\\\omega _{N}^{1\cdot 0}&\omega _{N}^{1\cdot 1}&\ldots &\omega _{N}^{1\cdot (N-1)}\\\vdots &\vdots &\ddots &\vdots \\\omega _{N}^{(N-1)\cdot 0}&\omega _{N}^{(N-1)\cdot 1}&\ldots &\omega _{N}^{(N-1)\cdot (N-1)}\\\end{bmatrix}}$

πού

$\omega _{N}=e^{-2\pi i/N}\,$

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

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

$\mathbf {F} ^{-1}={\frac {1}{N}}\mathbf {F} ^{*}$

Με ενιαία εξομάλυνση σταθερές $1/{\sqrt {N}}$, το DFT γίνεται ένα ενιαίο μετασχηματισμού, που ορίζεται από μια ενιαία μήτρα:

$\mathbf {U} =\mathbf {F} /{\sqrt {N}}$

$\mathbf {U} ^{-1}=\mathbf {U} ^{*}$

$|\det(\mathbf {U} )|=1$

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

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

$\sum _{m=0}^{N-1}U_{km}U_{mn}^{*}=\delta _{kn}$

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

$X_{k}=\sum _{n=0}^{N-1}U_{kn}x_{n}$

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

$\sum _{n=0}^{N-1}x_{n}y_{n}^{*}=\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}$

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

$\sum _{n=0}^{N-1}|x_{n}|^{2}=\sum _{k=0}^{N-1}|X_{k}|^{2}$

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

Εκφράζοντας την inverse DFT όσον αφορά το DFT

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

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

${\mathcal {F}}^{-1}(\{x_{n}\})={\mathcal {F}}(\{x_{N-n}\})/N$

(Ως συνήθως, οι δείκτες ερμηνεύονται modulo N * έτσι, για να $n=0$έχουμε $x_{N-0}=x_{0}$.)

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

${\mathcal {F}}^{-1}(\mathbf {x} )={\mathcal {F}}(\mathbf {x} ^{*})^{*}/N$

Τρίτον, μια παραλλαγή αυτής της σύζευξης κόλπο, η οποία είναι μερικές φορές προτιμότερη, επειδή δεν απαιτεί καμία τροποποίηση των δεδομένων των τιμών, συνεπάγεται την εναλλαγή πραγματικά και φανταστικά μέρη (η οποία μπορεί να γίνει σε έναν υπολογιστή απλά τροποποιώντας δείκτες). Ορίστε swap($x_{n}$) $x_{n}$ με τα πραγματικά και φανταστικά μέρη αντάλλαξαν—ότι είναι, αν $x_{n}=a+bi$ στη συνέχεια swap($x_{n}$) $b+ai$. Aντίστοιχα, swap($x_{n}$) ισούται με $ix_{n}^{*}$. Στη συνέχεια

${\mathcal {F}}^{-1}(\mathbf {x} )={\textrm {swap}}({\mathcal {F}}({\textrm {swap}}(\mathbf {x} )))/N$

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

Η σύζευξη κόλπο μπορεί επίσης να χρησιμοποιηθεί για να ορίσετε ένα νέο μετασχηματισμό, που σχετίζονται στενά με τον DFT, που είναι involutory—που είναι, που είναι το δικό αντίστροφο. Ειδικότερα, $T(\mathbf {x} )={\mathcal {F}}(\mathbf {x} ^{*})/{\sqrt {N}}$ είναι καθαρά δική inverse: $T(T(\mathbf {x} ))=\mathbf {x}$. Μια στενά συνδεδεμένη involutory μετασχηματισμού (με το συντελεστή (1+i) /√2) $H(\mathbf {x} )={\mathcal {F}}((1+i)\mathbf {x} ^{*})/{\sqrt {2N}}$, δεδομένου ότι οι $(1+i)$ παράγοντες $H(H(\mathbf {x} ))$ να ακυρώσει το 2. Για την πραγματική εισροές $\mathbf {x}$, το πραγματικό μέρος του $H(\mathbf {x} )$ δεν είναι άλλη από την διακριτού μετασχηματισμού Hartley, η οποία είναι επίσης involutory.

Ιδιοτιμές και ιδιοδιανύσματα

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

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

$\mathbf {U} _{m,n}={\frac {1}{\sqrt {N}}}\omega _{N}^{(m-1)(n-1)}={\frac {1}{\sqrt {N}}}e^{-{\frac {2\pi i}{N}}(m-1)(n-1)}.$

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

$\mathbf {U} ^{4}=\mathbf {I} .$

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

$\lambda ^{4}=1.$

Συνεπώς, οι ιδιοτιμές του $\mathbf {U}$ είναι η τέταρτη ρίζες της ενότητας: $\lambda$ +1, -1, +i, −i.

Δεδομένου ότι υπάρχουν μόνο τέσσερις διακριτές ιδιοτιμές για αυτό το $N\times N$ 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

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

$\det(\lambda I-\mathbf {U} )=(\lambda -1)^{\left\lfloor {\tfrac {N+4}{4}}\right\rfloor }(\lambda +1)^{\left\lfloor {\tfrac {N+2}{4}}\right\rfloor }(\lambda +i)^{\left\lfloor {\tfrac {N+1}{4}}\right\rfloor }(\lambda -i)^{\left\lfloor {\tfrac {N-1}{4}}\right\rfloor }.$

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

• $F(m)=\sum _{k\in \mathbb {Z} }\exp \left(-{\frac {\pi \cdot (m+N\cdot k)^{2}}{N}}\right)$.

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

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

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

• $F(m)=\prod _{s=K+1}^{L}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]$

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

• $F(m)=\sin \left({\frac {2\pi }{N}}m\right)\prod _{s=K+1}^{L-1}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]$

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

Η αρχή της αβεβαιότητας

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

$\sum _{n=0}^{N-1}|X_{n}|^{2}=1~,$

τότε

$P_{n}=|X_{n}|^{2}$

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

$Q_{m}=N|x_{m}|^{2}~.$

Για την περίπτωση των συνεχών συναρτήσεων $P(x)$ και $Q(k)$η απροσδιοριστία του Heisenberg μέλη που

$D_{0}(X)D_{0}(x)\geq {\frac {1}{16\pi ^{2}}}$

όπου $D_{0}(X)$ και $D_{0}(x)$ είναι οι διακυμάνσεις του $|X|^{2}$ και $|x|^{2}$ , αντίστοιχα, με την ισότητα που επιτεύχθηκαν σε περίπτωση κατάλληλα κανονικοποιημένη κατανομή κατά Gauss. Αν και οι αποκλίσεις μπορεί να είναι κατ ' αναλογία ορίζεται για το DFT, μια ανάλογη αρχή της αβεβαιότητας δεν είναι χρήσιμη, διότι η αβεβαιότητα δεν θα shift-αναλλοίωτη. Ακόμα, μια σημαντική αρχή της αβεβαιότητας έχει εισαχθεί από Massar και Spindel.

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

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

$H(X)=-\sum _{n=0}^{N-1}P_{n}\ln P_{n}$

και

$H(x)=-\sum _{m=0}^{N-1}Q_{m}\ln Q_{m}~,$

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

$H(X)+H(x)\geq \ln(N)~.$

Η ισότητα που λαμβάνεται $P_{n}$ ίση με μεταφράσεις και διαμορφώσεις του ένα κατάλληλα κανονικοποιημένη Kronecker χτένα της περιόδου $A$ που $A$ είναι ακριβώς ακέραιος διαιρέτης του $N$. Η συνάρτηση μάζας πιθανότητας $Q_{m}$ στη συνέχεια θα είναι ανάλογη με κατάλληλα μεταφρασμένο Kronecker χτένα της περιόδου $B=N/A$.

Υπάρχει, επίσης, ένα πολύ γνωστό ντετερμινιστική αρχή της αβεβαιότητας που χρησιμοποιεί το σήμα σπανιότητα (ή ο αριθμός των μη μηδενικών συντελεστών). Ας $\|x\|_{0}$ και $\|X\|_{0}$ είναι ο αριθμός των μη μηδενικών στοιχείων, του χρόνου και της συχνότητας ακολουθίες $x_{0},x_{1},\ldots ,x_{N-1}$ και $X_{0},X_{1},\ldots ,X_{N-1}$, αντίστοιχα. Στη συνέχεια,

$N\leq \|x\|_{0}\cdot \|X\|_{0}.$

Ως άμεση συνέπεια της ανισότητας, της αριθμητικής και της γεωμετρικής σημαίνει, επίσης $2{\sqrt {N}}\leq \|x\|_{0}+\|X\|_{0}$. Και οι δύο αβεβαιότητα αρχές έδειξαν να είναι σφιχτό για ειδικά επιλεγμένα "φράχτη" ακολουθίες (διακριτά ώθηση τρένα), και βρείτε την πρακτική χρήση για το σήμα εφαρμογές ανάκτησης.

Το πραγματικό εισαγωγής DFT

Αν $x_{0},\ldots ,x_{N-1}$ είναι πραγματικοί αριθμοί, όπως συμβαίνει συχνά σε πρακτικές εφαρμογές και, στη συνέχεια, το DFT υπακούει η συμμετρία:

$X_{N-k}\equiv X_{-k}=X_{k}^{*},$  πού $X^{*}\,$ υποδηλώνει συγκρότημα σύζευξη.

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

Γενικευμένη DFT (μετατοπιστεί και μη-γραμμική φάση)

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

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}(k+b)(n+a)}\quad \quad k=0,\dots ,N-1.$

Πιο συχνά, βάρδιες $1/2$ (μισό δείγμα). Ενώ η συνήθης DFT αντιστοιχεί σε ένα περιοδικό σήμα τόσο σε χρόνο όσο και η συχνότητα τομείς, $a=1/2$ παράγει ένα σήμα που είναι αντι-περιοδική στο πεδίο της συχνότητας ($X_{k+N}=-X_{k}$) και αντίστροφα, για $b=1/2$. Έτσι, η συγκεκριμένη περίπτωση $a=b=1/2$ είναι γνωστό ως ένα περίεργο χρόνο περίεργο συχνότητας, διακριτός μετασχηματισμός Fourier (ή O²DFT). Τόσο μετατοπίζεται μετασχηματίζει είναι πιο συχνά χρησιμοποιείται για συμμετρική δεδομένα, για να αντιπροσωπεύουν διαφορετικά όρια συμμετρίες, και για το πραγματικό συμμετρικό δεδομένων που αντιστοιχούν σε διαφορετικές μορφές του διακριτού συνημιτόνου και ημιτόνου μεταμορφώνει.

Μια άλλη ενδιαφέρουσα επιλογή $a=b=-(N-1)/2$, η οποία ονομάζεται επίκεντρο DFT (ή CDFT). Το επίκεντρο DFT έχει την χρήσιμη ιδιότητα ότι, όταν το N είναι πολλαπλάσιο του τέσσερα, τα τέσσερα από τα ιδιοτιμές (βλ. παραπάνω) έχουν ίσες οι πολλαπλότητες (Rubio και Santhanam, 2005)

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

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

Πολυδιάστατη DFT

Το συνηθισμένο DFT μετατρέπει μια μονοδιάστατη ακολουθία ή σειρά $x_{n}$ που είναι μια λειτουργία ακριβώς μία διακριτή μεταβλητή n. Η πολυδιάστατη DFT ενός πολυδιάστατου πίνακα $x_{n_{1},n_{2},\dots ,n_{d}}$ που είναι συνάρτηση των d διακριτές κεταβλητές $n_{\ell }=0,1,\dots ,N_{\ell }-1$ για $\ell$ σε $1,2,\dots ,d$ , ορίζεται από:

$X_{k_{1},k_{2},\dots ,k_{d}}=\sum _{n_{1}=0}^{N_{1}-1}\left(\omega _{N_{1}}^{~k_{1}n_{1}}\sum _{n_{2}=0}^{N_{2}-1}\left(\omega _{N_{2}}^{~k_{2}n_{2}}\cdots \sum _{n_{d}=0}^{N_{d}-1}\omega _{N_{d}}^{~k_{d}n_{d}}\cdot x_{n_{1},n_{2},\dots ,n_{d}}\right)\right)\,,$

όπου $\omega _{N_{\ell }}=\exp(-2\pi i/N_{\ell })$ ως ανωτέρω και το δ παραγωγή δεικτών τρέξιμο από $k_{\ell }=0,1,\dots ,N_{\ell }-1$. Αυτό είναι πιο συμπαγώς εκφράζεται σε διανυσματική μορφή, όπου ορίζουμε $\mathbf {n} =(n_{1},n_{2},\dots ,n_{d})$ και $\mathbf {k} =(k_{1},k_{2},\dots ,k_{d})$ ως d-διαστάσεων διανύσματα των δεικτών από το 0 $\mathbf {N} -1$, το οποίο ορίζουμε ως $\mathbf {N} -1=(N_{1}-1,N_{2}-1,\dots ,N_{d}-1)$:

$X_{\mathbf {k} }=\sum _{\mathbf {n} =\mathbf {0} }^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }\,,$

όπου η διαίρεση $\mathbf {n} /\mathbf {N}$ ορίζεται $\mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\dots ,n_{d}/N_{d})$ να είναι ο μετασχηματισμός φουριέ, και το άθροισμα υποδηλώνει το σύνολο των ένθετων αθροίσεις παραπάνω.

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

$x_{\mathbf {n} }={\frac {1}{\prod _{\ell =1}^{d}N_{\ell }}}\sum _{\mathbf {k} =\mathbf {0} }^{\mathbf {N} -1}e^{2\pi i\mathbf {n} \cdot (\mathbf {k} /\mathbf {N} )}X_{\mathbf {k} }\,.$

Όπως η μονοδιάστατη DFT εκφράζει την εισαγωγή $x_{n}$ ως υπέρθεση των ημιτονοειδών, η πολυδιάστατη DFT εκφράζει την εισαγωγή ως επαλληλία του αεροπλάνο κύματα, ή πολυδιάστατη ημιτονοειδών. Την κατεύθυνση της ταλάντωσης στο χώρο $\mathbf {k} /\mathbf {N}$. Η πλάτη είναι $X_{\mathbf {k} }$. Αυτή η αποσύνθεση είναι μεγάλης σημασίας για τα πάντα, από την ψηφιακή επεξεργασία εικόνας (δύο διαστάσεων) για την επίλυση μερικών διαφορικών εξισώσεων. Το διάλυμα χωρίζεται σε επίπεδα κύματα.

Η πολυδιάστατη DFT μπορεί να υπολογιστεί από την σύνθεση της ακολουθίας μονοδιάστατη DFTs κατά μήκος κάθε διάσταση. Στη δισδιάστατη περίπτωση $x_{n_{1},n_{2}}$ η $N_{1}$ ανεξάρτητη DFTs των σειρών (δηλ., κατά μήκος $n_{2}$), υπολογίζονται πρώτα για να σχηματίσουν ένα νέο πίνακα $y_{n_{1},k_{2}}$. Στη συνέχεια, η $N_{2}$ ανεξάρτητη DFTs του y κατά μήκος των στηλών (κατά μήκος $n_{1}$) υπολογίζονται για να διαμορφώσει το τελικό αποτέλεσμα $X_{k_{1},k_{2}}$. Εναλλακτικά, οι στήλες μπορεί να υπολογιστεί πρώτα και στη συνέχεια των σειρών. Η σειρά έχει σημασία, επειδή τα ένθετα αθροίσεις παραπάνω μετακίνηση.

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

Το πραγματικό εισαγωγής πολυδιάστατη DFT

Για την εισαγωγή δεδομένων $x_{n_{1},n_{2},\dots ,n_{d}}$ που αποτελείται από πραγματικούς αριθμούς, το DFT αποτελέσματα έχουν συζυγής συμμετρία παρόμοια με την μονοδιάστατη περίπτωση, ανωτέρω:

$X_{k_{1},k_{2},\dots ,k_{d}}=X_{N_{1}-k_{1},N_{2}-k_{2},\dots ,N_{d}-k_{d}}^{*},$

όπου το αστέρι και πάλι δηλώνει συγκρότημα σύζευξη και το $\ell$-ου δείκτης είναι και πάλι ερμηνεύεται modulo $N_{\ell }$ (για $\ell =1,2,\ldots ,d$).

Εφαρμογές

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

Φασματική ανάλυση

Όταν ο DFT χρησιμοποιείται για σημάτων, φασματική ανάλυση, η $\{x_{n}\}\,$ ακολουθία που συνήθως αντιπροσωπεύει ένα πεπερασμένο σύνολο ομοιόμορφα κατανεμημένες φορά-δείγματα κάποιο σήμα $x(t)\,$, όπου 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 e^inx = σ e^inx. Έτσι, στο 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)). Στη συνέχεια,

$\mathbf {c} =\mathbf {a} *\mathbf {b}$

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

$c_{n}=\sum _{m=0}^{d-1}a_{m}b_{n-m\ \mathrm {mod} \ d}\qquad \qquad \qquad n=0,1\dots ,d-1$

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

${\mathcal {F}}(\mathbf {c} )={\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} )$

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

$\mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} )).$

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

Πολλαπλασιασμός μεγάλων ακεραίων

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

Συνέλιξη

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

Κάποια διακριτός μετασχηματισμός Fourier ζεύγη

Some DFT pairs

$x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}e^{i2\pi kn/N}$	$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-i2\pi kn/N}$	Note
$x_{n}e^{i2\pi n\ell /N}\,$	$X_{k-\ell }\,$	Shift theorem
$x_{n-\ell }\,$	$X_{k}e^{-i2\pi k\ell /N}\,$
$x_{n}\in \mathbb {R}$	$X_{k}=X_{N-k}^{*}\,$	Real DFT
$a^{n}\,$	$\left\{{\begin{matrix}N&{\mbox{if }}a=e^{i2\pi k/N}\\{\frac {1-a^{N}}{1-a\,e^{-i2\pi k/N}}}&{\mbox{otherwise}}\end{matrix}}\right.$	from the geometric progression formula
${N-1 \choose n}\,$	$\left(1+e^{-i2\pi k/N}\right)^{N-1}\,$	from the binomial theorem
$\left\{{\begin{matrix}{\frac {1}{W}}&{\mbox{if }}2n<W{\mbox{ or }}2(N-n)<W\\0&{\mbox{otherwise}}\end{matrix}}\right.$	$\left\{{\begin{matrix}1&{\mbox{if }}k=0\\{\frac {\sin \left({\frac {\pi Wk}{N}}\right)}{W\sin \left({\frac {\pi k}{N}}\right)}}&{\mbox{otherwise}}\end{matrix}}\right.$	$x_{n}$ is a rectangular window function of W points centered on n=0, where W is an odd integer, and $X_{k}$ is a sinc-like function (specifically, $X_{k}$ is a Dirichlet kernel)
$\sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi }{cN}}\cdot (n+N\cdot j)^{2}\right)$	${\sqrt {cN}}\cdot \sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi c}{N}}\cdot (k+N\cdot j)^{2}\right)$	Discretization and periodic summation of the scaled Gaussian functions for $c>0$. Since either $c$ or ${\frac {1}{c}}$ is larger than one and thus warrants fast convergence of one of the two series, for large $c$ you may choose to compute the frequency spectrum and convert to the time domain using the discrete Fourier transform.

Γενικεύσεις

Εκπροσώπηση θεωρία

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

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

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

Άλλα πεδία

Πολλές από τις ιδιότητες του DFT εξαρτώνται μόνο από το γεγονός ότι $e^{-{\frac {2\pi i}{N}}}$ είναι μια πρωτόγονη ρίζα της ενότητας, μερικές φορές συμβολίζεται $\omega _{N}$ ή $W_{N}$ (έτσι ώστε $\omega _{N}^{N}=1$). Αυτές οι ιδιότητες περιλαμβάνουν την πληρότητα, την καθετότητα, Plancherel/Parseval, περιοδικότητα, shift, συνέλιξη, και unitarity ιδιότητες παραπάνω, καθώς και πολλά FFT αλγόριθμοι. Για το λόγο αυτό, ο διακριτός μετασχηματισμός Fourier μπορεί να οριστεί χρησιμοποιώντας ρίζες της ενότητας σε πεδία άλλα από των μιγαδικών αριθμών, και τέτοιες γενικεύσεις είναι κοινώς ονομάζεται αριθμός της θεωρίας μετατρέπει (NTTs) στην περίπτωση των πεπερασμένων πεδίων. Για περισσότερες πληροφορίες, δείτε τον αριθμό της θεωρίας μετατρέψει και διακριτός μετασχηματισμός Fourier (γενικά).

Άλλα πεπερασμένων ομάδων

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

$\{0,1,\ldots ,N_{1}-1\}\times \cdots \times \{0,1,\ldots ,N_{d}-1\}\to \mathbb {C} .$

Αυτό υποδηλώνει την γενίκευση να Fourier για την αυθαίρετη πεπερασμένων ομάδων, που δρουν στις συναρτήσεις G → C , όπου η 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 που σχετίζονται με το μετατρέπει
• Πολυδιάστατη μετατρέψει
• Ο ζακ μετατρέψει

Βιβλιογραφία

• 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: 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. Bibcode: 1997JOSAA..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. Bibcode: 2000ITSP...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. Bibcode: 2005ISPL...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. 

Εξωτερικοί σύνδεσμοι

• Διαδραστική εξήγηση του DFT
• Matlab tutorial για το Διακριτό Μετασχηματισμό Fourier
• Interactive flash tutorial για το DFT
• Τα μαθηματικά της Διακριτός Μετασχηματισμός Fourier από τον ιούλιο. O. Smith III
• FFTW: η Γρήγορη υλοποίηση του DFT - κωδικοποιημένα σε C και κάτω από τη Γενική Άδεια Δημόσιας χρήσης (GPL)
• Γενικού Σκοπού FFT Συσκευασία: ένα Ακόμη γρήγορο DFT υλοποίηση σε C & FORTRAN, ανεκτική άδεια
• Επεξήγηση: Ο Διακριτός Μετασχηματισμός Fourier