Fast Fourier Transform in C.

Post per veri Ingegneri o per gente interessata….

Questo lo faccio più che altro come appunto personale. L’altro giorno io & Fox avevamo la necessità di fare per la tesi una FFT di un vettore di N elementi complessi. Come si può fare in C ? vediamolo subito.

Prima due parole su cosa sia la DFT e la FFT . Per chi non è del campo deve sapere che un segnale campionato nel tempo ,nel dominio della frequenza ha uno spettro che si replica ed è continuo. Questo spettro viene a sua volta campionato e si ottengono dei campioni che costituiscono la trasformata discreta (DFT = Discrete Fourier Transform ). Ora un metodo veloce per compiere queste operazioni è appunto la FFT (Fast Fourier Transform ) che nel campo dell’elaborazione odierna è una dei concetti più importanti. Basti pensare che viene utilizzata ovunque , un esempio tra tutti le codifiche dei vostri mp3 o delle vostre immagini digitali.

Torniamo al problema principale ..come ottenerla in C? naturalmente esistono delle librerie sviluppate per il nostro scopo che potete trovare qui:

http://www.fftw.org/

Per chi usa ubuntu naturalmente è già presente nei repository:

apt-get install fftw3 fftw3-dev

ok…

fatto questo bisogna includere la libreria nel codice , ricordatevi di fare quindi un #include fftw3.h e quando compilate non dimenticate di dire al compilatore che si deve occupare anche di questa libreria ( inserite -lfftw3 nel comando di compilazione).

Ecco un po’ di codice che al solito non commenterò a meno che a qualcuno interessi.

Due sole precisazioni: riguardo al comando fftw_plan_dft_1D notate il commento che ho messo per la FFT e per la IFFT. L’altra riguarda la normalizzazione dalla IFFT alla FFT , infatti c’è un 1/N come fattore di scala.

#include fftw3.h // vari include mettete quelli che volete

#define sqrt2 1.41421356
#define RAND_BIN ((rand()>RAND_MAX /2) ? 1/sqrt2 : -1/sqrt2)

int main(int argc, char** argv)
{
int i=0,N=2048;
double K=1/N;
fftw_complex *in, *out;
fftw_plan p;

in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
for (i = 0; i //vettore di dati 1,2,3,4,5 … (sia parte reale che immaginaria) volendo potete usare la macro RAND_BIN
{ in[i][0]= i;
in[i][1]=i;
}
for (i = 0; i < N; i++) //printf("parte R : %g\n parte Im :%g",in[i][0],in[i][1]); p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE); //IFFT = FFT_BACKWARD , FFT=FFT_FORWARD fftw_execute(p); /* repeat as needed */ fftw_destroy_plan(p); fftw_free(in); // fftw_free(out); //for (i = 0; i //{ //out[i][0]= out[i][0]/N; //out[i][1]=out[i][1]/N; //} for (i = 0; i < N; i++) printf("parte R : %f\n parte Im :%f",out[i][0],out[i][1]); return 0; }

10 risposte a “Fast Fourier Transform in C.”

I commenti sono chiusi