Discrete fouriertransformatie

In de wiskunde is de discrete fouriertransformatie of DFT een fouriertransformatie die veel wordt toegepast in de digitale signaalverwerking en verwante vakgebieden voor het analyseren van de frequenties die aanwezig zijn in een bemonsterd signaal, en voor het uitvoeren van bewerkingen zoals discrete convoluties. De DFT kan efficiënt worden berekend door gebruik te maken van het FFT-algoritme.

De discrete fouriertransformatie, aangeduid met ${\mathcal {F}}$, is een lineaire transformatie en een discrete vorm van de fouriertransformatie. Ze transformeert een periodieke (periode $T\in \mathbb {Z}$) en discrete rij van $N$getallen in een eveneens periodieke discrete rij.

De rij van $N$ complexe getallen $x=(x(0),\ldots x(N-1))$ wordt door de DFT getransformeerd in de rij van $N$ complexe getallen $f=(f_{0},\ldots ,f_{N-1})$ volgens de formule:

$f_{k}=\sum _{n=0}^{N-1}x(n)e^{-i\omega nk}\quad \quad n=0,\dots ,N-1$ en $\omega ={\frac {2\pi }{N}}$

Hierin is $e$ de basis van de natuurlijke logaritme, $i$ de imaginaire eenheid, en $\pi$ het getal pi. De transformatie wordt ook wel genoteerd als ${\mathcal {F}}$, zoals in

$f={\mathcal {F}}(x)$.

De inverse discrete fouriertransformatie (IDFT) wordt gegeven door

$x(n)={\frac {1}{N}}\sum _{k=0}^{N-1}f_{k}e^{i\omega nk}\quad \quad n=0,\dots ,N-1$

Merk op dat de normalisatiefactor die gebruikt wordt in de DFT en IDFT (hier 1 en 1/n) en de tekens van de exponenten slechts conventies zijn, waar vaak van wordt afgeweken. De enige harde eisen bij deze conventies zijn dat de DFT en IDFT exponenten met tegengesteld teken moeten hebben, en dat het product van de beide normalisatie-factoren 1/n moet zijn. Een normalisatiefactor van $1/{\sqrt {n}}$ voor zowel DFT als IDFT maakt de transformaties unitair, hetgeen enkele theoretische voordelen biedt, maar vaak is het praktischer om de schaling van bovenstaande definities aan te houden.

Unitaire transformatie

Bij de unitaire variant van de discrete fouriertransformatie kunnen met behulp van matrixrekening de coëfficiënten eenvoudig als volgt gevonden worden (waarbij $\xi _{N}=e^{-i\omega }=e^{-2\pi i/N}$):

${\mathcal {F}}(x)={\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{N-1}\\\end{bmatrix}}={\frac {1}{\sqrt {N}}}{\begin{bmatrix}\xi _{N}^{0\cdot 0}&\xi _{N}^{0\cdot 1}&\ldots &\xi _{N}^{0\cdot (N-1)}\\\xi _{N}^{1\cdot 0}&\xi _{N}^{1\cdot 1}&\ldots &\xi _{N}^{1\cdot (N-1)}\\\vdots &\vdots &\ddots &\vdots \\\xi _{N}^{(N-1)\cdot 0}&\xi _{N}^{(N-1)\cdot 1}&\ldots &\xi _{N}^{(N-1)\cdot (N-1)}\\\end{bmatrix}}{\begin{bmatrix}x(0)\\x(1)\\\vdots \\x(N-1)\\\end{bmatrix}}$