DFT e FFT

« Older   Newer »
  Share  
Elemento 38
view post Posted on 28/12/2010, 17:38




Tutto parte da questa discussione https://thegeniusworkshop.forumcommunity.net/?t=42652317
Ho fatto una piccola prova, che adesso amplierò, per un programma in C che esegue la DFT.
Sono partito da questa perché é estremamente più facile della FFT e fa le stesse cose, anche se con un tempo molto maggiore(centinaia di volte, ma che si fa sentire solo con grandi quantità di campioni da analizzare).
Questa è la brutta copia del programma, che andrò poi a modificare con le prove successive:
SPOILER (click to view)
//---------------------------------------------------------------------------

#include <clx.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{
FILE *fp;
int Input[73];
int OutputR[36];
int OutputI[36];
int OutputAmp[36];
int OutputPha[36];
int i,k;
double angolo;

//carico i valori in ingresso con una sinusoide
for(i=0;i<73;i++){
angolo = (i*5*M_PI)/180;
Input[i] = (int)(sin(angolo)*255 + 255);
}
//ALGORITMO DFT
//azzero i vettori
for(i=0;i<36;i++){
OutputR[i] = 0;
OutputI[i] = 0;
}

//calcolo i valori con la formula
for(k=0;k<36;k++){
for(i=0;i<73;i++){
OutputR[k] = OutputR[k]+Input[i]*cos(2*M_PI*k*i/73);
OutputI[k] = OutputI[k]-Input[i]*sin(2*M_PI*k*i/73);
}
}
//conversione polare->rettangolare
for(i=0;i<36;i++){
OutputAmp[i] = (int)sqrt(OutputR[i]^2+OutputI[i]^2);
}
//scrivo su file
fp = fopen("file.txt","a");
for(i=0;i<36;i++){
fprintf(fp,"%­i \n",OutputAmp[i]);
}
fclose(fp);

return 0;
}

Se avete domande sul programma fate pure. Io genero come ingresso una sinusoide, campionata con una frequenza molto maggiore della sua frequenza(ho una settantina di punti. Ecco la sinusoide e lo spettro che mi è stato generato dal software:
image
Notare la mancanza di unità di misura negli assi perché ho ancora dei dubbi sulla faccenda.
Note sullo spettro: si avvicina a quello vero. C'è un'armonica a frequenza 0 che sarebbe la componente continua (che io ho messo nel mio segnale per averlo tutto positivo), ma il suo valore è un po' minore. Ci sono poi due righe spettrali dove dovrebbe essercene solo una 1 (entrambe inoltre hanno un valore molto basso). Ho provato a togliere la componente continua, ma il tutto peggiora, ci sono lo stesso due righe spettrali (la componente continua è sparita, ma sono entrambe molto basse, mentre una si dovrebbe aggirare sui 255. Mhh, qua bisogna continuare gli studi :lol:
Vi terrò aggiornati ;)
 
Top
view post Posted on 28/12/2010, 17:47
Avatar

Immane Rompiball

Group:
Administrator
Posts:
18,287
Location:
Orlo esterno della cintura di Orione stella 1957

Status:


:wacko:

Bhò... prova con una frequenza più bassa... :unsure:
Le ascisse è il dominio della frequenza, ma in teoria dovrebbe essere logaritmica, ovvero 10-100-1000-10k-100k... hz distanziati linearmente. Idem per le ordinate che dovrebbe essere il dominio del livello in dB. Lo zero frequenza viene sempre un picco di indeterminazione dei calcoli perchè da qualche parte esce sempre un "divide by zero" e sotto per i valori negativi di frequenza, assurdi, viene l'immagine spettrale inversa simmetrica. Quindi da non considerare. Poi ci sono altri casini come il tipo di campionamento da fare ovvero la finestra di scelta dei campioni e tantissime altre cose che non ricordo più. L'ultima volta che ho tentato è stato circa 15 anni fa, o più.
Ora mi faccio coraggio e guardo il tuo programma in "C"... :lol:
 
Web  Top
Elemento 38
view post Posted on 28/12/2010, 18:05




Si ha una divisione per 0 se si calcola la fase delle armoniche, perché c'è un rapporto con variabile al denominatore, che potrebbe venire 0.
Anche la frequenza mi puzza un po' ... voglio provare a generare una sorta di onda quadra e poi usare quella per trovare uno spettro.
Taglio la testa al toro e provo la funzione inversa della DFT con i valori trovati. Se viene fuori una sinusoide come la prima c'è solo da capire come sono messi i punti trovati.
 
Top
view post Posted on 29/12/2010, 08:21
Avatar

Rompiball

Group:
Appassionati
Posts:
2,612
Location:
briansa

Status:


Molto interessante anche se ci capisco poco o niente.
Allora, partiamo da DFT e FFT, da come mi pare di aver capito, la DFT fa le stesse cose della FFT solo che è molto più lenta e applicabile solo se la mole di dati non è esagerata.
Mi pare di aver letto che un FFT può impiegare anche alcuni millisecondi con processori che girano molto velocemente, quindi presumo che ci siano calcoli a non finire.

Ma faccio un passo indietro: cosa è e a cosa serve la FFT?
Spesso su youtube si vedono analizzatori di spettro e quasi sempre il termine FFT viene tirato in ballo.
In poche parole la fft scompone le varie componenti di una frequenza? Cioe' mi visualizza i valori delle armoniche e via dicendo?
Ma come è' applicabile a un micro? Cioe' cosa dovrei fare io? Immetto la bassa frequenza direttamente nel convertitore analogico-digitale, senza filtri hardware, fa tutto la routine?

Non so proprio, ma sarei curioso di capire un po' i rudimenti.
 
Top
Elemento 38
view post Posted on 29/12/2010, 10:12




In pratica la DFT è una trasformata di Fourier. Con la trasformata di Fourier, da una funzione in ingresso nel dominio del tempo si passa ad un'altra funzione nel dominio delle frequenze. Al contrario della trasformata di Fourier che richiede una funzione continua in ingresso, la DFT richiede una funzione discreta, parlando molto per semplificare un segnale campionato(ma campionato bene!).
Tutto è applicabile ad un microcontrollore, per esempio il progrmma che ho messo funziona per un uC (per adesso il funziona è ancora un po' vago :unsure: ), ma calcola il tutto in differita, dopo avere campionato.

Ho dato un occhio al tutto ieri sera, voglio riprovare usando più periodi del segnale.
 
Top
view post Posted on 29/12/2010, 10:31
Avatar

Rompiball

Group:
Appassionati
Posts:
2,612
Location:
briansa

Status:


CITAZIONE
Io genero come ingresso una sinusoide, campionata con una frequenza molto maggiore della sua frequenza

Sarebbe interessante ( e mi pare che l'hai detto) usare un'onda quadra che contiene un sacco d'armoniche e vedere il risultato.
CITAZIONE
ma calcola il tutto in differita, dopo avere campionato.

E si, mi sa che servirebbe un micro molto potente e un quarzo molto alto tipo 20 Mhz o più

Ma la cosa che non mi è chira: allora dovresti entrare in un eventuale convertitore AD in alternata? Cioe' direttamente con la BF?
 
Top
Elemento 38
view post Posted on 29/12/2010, 10:42




Adesso provo a fare un'onda quadra, ma devo prima generarmi i valori e quindi devo stare attento a farli bene se no viene un casino :lol:
Per fare il tutto con un uC devi avere prima di passare nel dominio della frequenza i campioni, quindi devi avere un sistema di campionamenta a monte, con filtro antialiasing e convertitore AD. Penso (ma non ne sono certo) che il segnale che entri debba essere tutto positivo.
Aggiorniamo: ho fatto la prova che volevo con più periodi della sinusoide:
image
Ci sono ancora dei problemi. Ho anche letto che per avere uno spettro "pulito" bisognerebbe filtrare il segnale con una "Hamming Window" e poi mediare un po' i valori. Appena capisco come filtrare il segnale(soprattutto devo trovare almeno una formula per sta hamming window) vedo se migliora.
 
Top
view post Posted on 29/12/2010, 11:42
Avatar

Immane Rompiball

Group:
Administrator
Posts:
18,287
Location:
Orlo esterno della cintura di Orione stella 1957

Status:


Una cosa la posso dire, che non è necessario stare sempre in positivo, si può entrare dentro un convertitore A/D direttamente con un'onda di forma qualsiasi e lui convertirà ad ogni campionamento il valore che assume l'onda in quel determinato istante. La velocità di campionamento è quella che determina il numero di campioni per periodo dell'onda, ammesso che l'onda sia periodica.
Non dimentichiamo che il nostro caso è quello di un'onda periodica particolare, la sinusoide.

Per chiarire un pò di matematica della trasformata di Fourier bisogna introdurne le basi.
Se noi abbiamo una forma d'onda di tensione f(t) una a caso ma particolare che può essere presa per esempio:

V(t)=Voffset+Vmax·sinωt

Questa equazione rappresenta l'andamento nel tempo della tensione V(t) o v (minuscola). E quindi questa è la y=f(t) funzione di una variabile y nel tempo dove x=t. Ovvero possiamo, come sempre e largamente conosciuto e risaputo, rappresentare in x il tempo ed in y i valori di tensione, come nell'oscilloscopio.

La y=f(ξ) è invece, la rappresentazione della tensione in funzione della frequenza. Senza cadere in complicazioni del perchè una cosa del genere è stata trovata utile, si può concludere che è utile per determinare lo spettro di esistenza di un segnale che non è puramente sinusoidale come quello esemplificato quì sopra. Ovvero, per determinarne il contenuto armonico. Se ci si ricorda della serie di Fourier...

Quindi alla fine di pesanti ed esasperati calcoli di analisi si giunge al punto che:

f(ξ)=f(t)e-2πiξt(dt)

dove ξ rappresenta in questo caso la frequenza.
(se non ho sbagliato qualcosa, vado a memoria ma sono memorie che uso raramente, molto raramente, circa una volta a decennio...)
 
Web  Top
view post Posted on 29/12/2010, 12:01
Avatar

Rompiball

Group:
Appassionati
Posts:
2,612
Location:
briansa

Status:


accidenti che casino!!!

CITAZIONE
La y=f(ξ) è invece, la rappresentazione della tensione in funzione della frequenza.

ecco, qui già m'incasino! In poche parole, il mio segnale viene suddiviso nelle varie armoniche?
Quindi la portante a frequenza f0 avra' un valore di per esempio un volt, l'armonica un valore magari di mezzo volt ecc...?

In pratica io con una fft faccio quello che dovrei fare con dei filtri ,cioe' con dell'hardware, ma tutto via software?

Io avevo pensato per fare un piccolo analizzatore di spettro di usare dei filtri attivi e poi multiplexare i canali del covertitore ad
quindi avrei (mettiamo) 5 file di led da 8 led ciascuna che si accende sempre a vu-meter, ma solo per quel determinato campo di frequenza.

La FFT in pratica fa questo? Si smazza tutto via software, senza hardware esterno?
Da come posso capire allora, se è così, superato lo scoglio della difficoltà del software è molto vantaggiosa.
Anche se non mi è chiaro come un convertitore AD possa distinguere:

se io immetto 1000 hz a 2 volts il convertitore per esempio lo quantizza a 100 bit, ma anche se io immetto 500 hz e ho la stessa intensità mi segnera 100 bit e quindi?

Ovvio che mi sfugge qualcosa
 
Top
Elemento 38
view post Posted on 29/12/2010, 12:34




CITAZIONE
se io immetto 1000 hz a 2 volts il convertitore per esempio lo quantizza a 100 bit, ma anche se io immetto 500 hz e ho la stessa intensità mi segnera 100 bit e quindi?

In che senso lo quantizza a 100 bit?
 
Top
view post Posted on 29/12/2010, 12:51
Avatar

Rompiball

Group:
Appassionati
Posts:
2,612
Location:
briansa

Status:


CITAZIONE
In che senso lo quantizza a 100 bit?

cioè, se io immetto una tensione in un qualsiasi convertitore AD che sia dei pic o altro (parlo di quelli ad approssimazioni successive) questa grandezza viene quantizzata in bit cioe'
risoluzione 10 bit= range da 0 a 1024 passi
quindi su una tensione di riferimento di 5 volts se io ho 2.5 volts avrò
1024/2=512 bit

ma questi 512 bit io li posso avere sia a 100 hz sia a 1000 hz, il convertitore AD, mi misura solo l'intensità del segnale.
Ecco, questo non capisco, anche se io do in pasto questi dati alla FFTcome fa a capire?
Ripeto non ne so niente e facilmente sto dicendo una vaccata mostruosa...magari il convertitore Ad non si usa nemmeno!!!


Ma il resto del ragionamento che ho fatto, è giusto Ele? Ti fa tutto via software, senza utilizzare filtri hardware ecc?
 
Top
Elemento 38
view post Posted on 29/12/2010, 13:30




Così quantizzi a 10 bit ... il valore quantizzato è 100. Nel tuo esempio a 2.5V hai 512 come valore non 512 bit.
Nel libro che ho trova la frequenza delle armoniche sapendo la frequenza di campionamento, infatti nelle ascisse mette come ultimo valore 0.5*fc ... non so se è corretta come cosa, ma la spiega così. Vi rimando al libro, cap. 9
www.dspguide.com/ch9.htm
 
Top
Elemento 38
view post Posted on 29/12/2010, 17:02




Come avevo promesso ho provato velocemente con un'onda quadra, ho messo fino alla 7a armonica così per vedere cosa veniva fuori. Ecco:
image
In poche parole va filtrato con quella funzione di cui avevo parlato sopra perché lo spettro c'è ... c'è la fondamentale e le altre 3 armoniche ma con molto rumore in giro. La 5a è venuta più bassa della 7a e questo è sbagliato però ... bisogna fare più campioni ? Più periodi? Ve lo saprò dire con altre prove :lol:

Neanche a cercarlo ecco cosa è venuto fuori www.dsptutor.freeuk.com/WindowFunctionPlot/notes.html
Faccio un file di excel con dei valori prova e poi guardo se funziona il meccanismo :unsure:
 
Top
view post Posted on 29/12/2010, 17:34
Avatar

Immane Rompiball

Group:
Administrator
Posts:
18,287
Location:
Orlo esterno della cintura di Orione stella 1957

Status:


CITAZIONE (GILA75 @ 29/12/2010, 12:01) 
accidenti che casino!!!

CITAZIONE
La y=f(ξ) è invece, la rappresentazione della tensione in funzione della frequenza.

ecco, qui già m'incasino!

Normale, ma la cosa è molto semplice, anzi di più, almeno fino a quì. Il problema è che non ti figuri nella mente questa faccenda e perciò ti sembra mostruosamente incasinata.
Tutto questo vuol dire che:
Hai presente l'oscilloscopio? Eh? Si? Bene. Nell'asse delle Y cosa c'è? La tensione misurata. E nelle X cosa vedi? Il tempo che passa. La "cosa" che vedi nello schermo, sul piano cartesiano si chiama in matematica, è la funzione (da non scambiare con la funzione d'onda di una particella subnucleare come in tanti fanno, quella è tutt'un'altra cosa). Quindi, possiamo dire che quella linea non sono altro che la congiungente di tutti quei punti dello spazio cartesiano del display dell'oscilloscopio che coincidono con la descrizione della funzione. Della funzione di che? Diciamola giusta. Di Y in "funzione" di X. Per questo si chiama "funzione" abbreviando, e quindi si scrive y=f(x).
Nel nostro caso x=t cioè l'asse delle ascisse o asse "x" rappresenta lo scorrere del tempo.
Naturalmente noi possiamo decidere cosa diamine rappresentare negli assi e se noi mettiamo nelle ascisse invece che il tempo, la frequenza otterremo l'indicazione del contenuto della tensione in funzione della frequenza.

CITAZIONE
In poche parole, il mio segnale viene suddiviso nelle varie armoniche?
Quindi la portante a frequenza f0 avra' un valore di per esempio un volt, l'armonica un valore magari di mezzo volt ecc...?

La prima armonica non c'è, un'armonica è un multiplo intero della fondamentale. C'è la fondamentale la 2ª armonica che è il doppio, la 3ª armonica che è il triplo, la 4ª armonica che è il quadruplo e così via. Però il segnale potrebbe anche essere composto dalla somma di due frequenze non armoniche, queste daranno uno spettro che indica intensità del segnale e frequenza dell'onda 1 dell'onda 2 della somma delle due e della differenza delle due più la somma e la differenza di tutte le loro armoniche se ne hanno. Una sinusoide pura non ha armoniche.
Il segnale non viene suddiviso come si potrebbe pensare in una serie di filtri ma viene analizzato e "trasformato".

CITAZIONE
In pratica io con una fft faccio quello che dovrei fare con dei filtri ,cioe' con dell'hardware, ma tutto via software?

Ecco, non esattamente. Non è la stessa cosa.

CITAZIONE
Io avevo pensato per fare un piccolo analizzatore di spettro di usare dei filtri attivi e poi multiplexare i canali del covertitore ad
quindi avrei (mettiamo) 5 file di led da 8 led ciascuna che si accende sempre a vu-meter, ma solo per quel determinato campo di frequenza.

Si può anche fare un analizzatore con quel sistema ma ti servono più filtri e più convertitori, mentre con la FFT fai tutto con un solo convertitore e senza filtri.

CITAZIONE
La FFT in pratica fa questo? Si smazza tutto via software, senza hardware esterno?
Da come posso capire allora, se è così, superato lo scoglio della difficoltà del software è molto vantaggiosa.

Certo. Gli oscilloscopi digitali fanno proprio così.

CITAZIONE
Anche se non mi è chiaro come un convertitore AD possa distinguere:
se io immetto 1000 hz a 2 volts il convertitore per esempio lo quantizza a 100 bit, ma anche se io immetto 500 hz e ho la stessa intensità mi segnera 100 bit e quindi?

Il convertitore campiona, converte in numero digitale intero a n bit, tipo 8, 10, 12, 14, 16 bit, il valore di tensione che legge in ingresso. Come valore... P.es.
Per un convertitore a 8 bit con ±5Vfs:

0V= 0000 0000
5V= 0111 1111
-5V= 1000 0000
0.039V=0000 0001
-0.039V=1111 1111
1V= 0001 1001
-1V=1110 0111

CITAZIONE
Ovvio che mi sfugge qualcosa

Ovvio... :)
 
Web  Top
Elemento 38
view post Posted on 29/12/2010, 17:54




Essì, con quel "filtro" il tutto è un po' più bellino :unsure:
image
La funzione della Hamming Window è

i va da 0 a N-1 dove N è il numero dei campioni
M io l'ho scelto la metà di N, e sembra funzionare abbastanza bene.
 
Top
99 replies since 28/12/2010, 17:38   1846 views
  Share