4.4 Diszkrét Fourier transzformáció
Az előző fejezetekben tárgyalt Fourier transzformáció nagyon hasznos eszköz azokon a területeken, ahol képlettel megadott függvényeken kell az időtartományban bonyolult műveleteket végezni. Azonban a műszaki gyakorlatban nem tudunk mindig képlettel megadott függvényekkel dolgozni. Sokszor előfordul, hogy a kérdéses jel csak diszkrét időpontokban táblázatos formában áll rendelkezésre. Így felmerült az igény egy olyan módszer megalkotására, amellyel a Fourier transzformáció kiterjeszthető véges hosszúságú diszkrét adatsorokra.
Legyen N db minták egy jelből, melyek egyenlő távolságra vannak egymástól az időtengelyen. Tároljuk ezeket a mintákat egy x[N] vektorban. Ekkor definíció szerint az x[N] vektor diszkrét Fourier transzformáltján (továbbiakban DFT) az alábbi y[N] vektort értjük.
k=0,1,2,...,N-1
Természetesen a diszkrét esetben is létezik a transzformáció inverze:
n=0,1,2,...,N-1
Vegyük észre, hogy sem a T periódus idő, sem az ω körfrekvencia nem szerepel a DFT képleteiben. Tehát a DFT egy olyan függvény transzformáció (operáció), mely egy N db mintából álló sorozatból egy másik N db mintából álló sorozatot képez, a dimenzió nélküli k index segítségével. Fizikai jelentése akkor van a transzformációnak, ha az xn vektor valamilyen fizikai jellemzővel rendelkezik. Jelfeldolgozási szempontból a fizikai jellemző a kω, tehát a DFT ebben az esetben azt mondja meg, hogy az N db mintával megadott jelben az ω körfrekvencia N db egész számú többszöröse mekkora súllyal van jelen.
A DFT elvégezhetőségének feltétele, hogy az xn jel energiája véges legyen, azaz

Ez a gyakorlatban mindig teljesül az xn tagjainak korlátossága, valamint a véges mintaszám miatt.
A DFT szempontjából mindegy, hogy a bemenő jel ténylegesen periodikus vagy sem. Úgy tekinti az N db mintát tartalmazó xn vektort, mint egy végtelen periodikus jel egy periódusát.
A transzformáció eredményeképpen előálló yk vektor N db komplex számot tartalmaz, ahol az egyes tagok abszolút értékeiből képzett sorozat adja az amplitúdó spektrumot, a fázis szögek sorozata pedig a fázis spektrumot.

Az alábbi C nyelvű rutin a definíció szerint számolja ki a DFT-t.
typedef struct
{
double re;
double img;
}COMPLEX;
void dft(COMPLEX *in, COMPLEX *out, int N)
{
double re, im;
int k, n;
for(k=0; k<N; k++)
{
re=0; im=0;
for(n=0;n<N;n++)
{
re=re+in[n].re*cos(2*PI*k*n/N)+in[n].img*sin(2*PI*k*n/N);
im=im+in[n].img*cos(2*PI*k*n/N)-in[n].re*sin(2*PI*k*n/N);
}
out[k].re=re;
out[k].img=im;
}
}