FFT cu Atmega

[rotten]

A reusit cineva sa implementeze un FFT - fast fourier transformation pe un microcontroler atmega ? Problema la care m-am blocat eu e necesarul de memorie - la 22K frecventa maxima , am 2 esantioane -> 44KB de ram doar pentru esantioane

[Vizitator byteworks]

Pai ... RAM extern, daca-ti permiti.

[rotten]

RAM extern inseamna timp pierdut pentru accesare , ram-uri pe i2c nu esista decat pana la 256B -> trebuie un ram static de 65K -> 16 pini + liniile de comanda blocate pentru ram , sau varianta cu accesare seriala a ram-ului , ce la randul ei are viteza mica Sant curios daca se poate implementa si folosind mai putin ram , pe segmente mai mic, o lista fifo de ex de cativa octeti din care calculez pe masura ce primesc date noi de la ADC.Trebuie sa mai studiez nitel formulele de la FFT. Nu imi trebuie precizie prea mare -> pot sa fac o multime de aproximari ce ar scurta timpul de procesare

[cirip]

44KB de ram doar pentru esantioane

... asta doar daca vrei ca frecventa minima pe care "o vezi" sa fie de 1Hz. Daca mai lasi un pic de la tine si frecventa minima este de 10Hz sau 100Hz, poti face actizitie pe intervale mai scurte, adica de 1/10 sau 1/100 dintr-o secunda. La 44KHz asta inseamna 4400 sau 440 esantioane. In realitate trebuie sa extinzi la cel mai apropiat 2^n ca sa poti face FFT. Cred ca depinde si de tipul de atmel pe care il folosesti. De asemenea, folosesti esantioane de 8 biti sau mai mari? Daca-s mai mari, ai nevoie de 2 octeti ptr fiecare esantion.Problema reala nu cred ca este la memorie, ca daca vrei neaparat poti face FFT si pe 16 esantioane (cu pierderea asociata la joase). Eu cred ca fara multiplicator hardware si/sau instructiune MAC, sansele de a face FFT in timp real cu un controler sunt reduse. Atmelul are MAC? In ce scrii FFTul? Asm sau C sau ... ?Poti sa dai mai multe detalii ce vrei sa faci? Uneori exista solutii mai eficiente.Cirip

[aghora17]

de aia dsp-urile are DMA

[rotten]

Folosesc atmega32 la 20MhzScriu programele in cNu ma intereseaza o precizie prea mare, ci doar niste valori aprozimative Esantioanele sant pe 8 bitiAs vrea sa fac ceva asemanator cu indicatorul de nivel de la winamp (scope)Sa vad "nivelul" diferitelor frecvente, ca apoi sa le pot cotrola dintr-un egalizator.

instructiune MAC

ce inseamna MAC ?

[cirip]

OK, banuiam ca vrei ceva gen spectru pe bara de lezi, dar am zis sa nu anticipez.Pentru asta nu ai neaparata nevoie de FFT. Exista un fel de FFT simplificat atunci cand nu ai nevoie de detalii, ci vrei sa stii cam care e puterea intr-o anumita banda sau in jurul unei anumite frecvente. Separi in cate benzi ai nevoie si... cam asta e. Cauta pe gogu algoritmul Goertzel. Asta se foloseste destul de frecvent la identificarea DTMFului cu desepelul. Goertzel e practic un banc de filtre biquad centrate pe frecventele pe care le doresti. Calculezi RMS-ul la iesirea fiecarui banc si aprinzi leduri proportional cu RMSul.Ai putea sa incerci si FFT in 8 sau 16 puncte, dar treaba se complica oricum, ptr ca inainte de FFT trebuie sa faci ponderarea (windowing) blocului de esantioane ca sa nu ai discontinuitate la capele intervalului si sa apara aliasuri in FFT. Cauta pe gogu "windowing si Hamming, Hanning, Blackman, Kaiser"... Sunt mai multe.Desi necesarul de calcule la Goertzel scade, totusi e mult de rasnit, mai ales daca nu ai multiplicator hardware in cipan. In schimb ai avantajul ca frecventa de refresh e scazuta (10...20Hz ptr ochi) si asta iti da timp sa termini ce ai de facut. Va trebui insa sa buferezi la greu, ptr ca esantionarea trebuie totusi facuta rapid.Eu incepusem un proiect oarecum asemanator folosind un MSP430F149. Am vrut sa fac o orga de lumini complet digitala in care pe un pin al procesorului sa bagi muzica, pe altul sa bagi 50Hz ptr sincronizare cu reteaua, iar pe 4 pini sa pui optocuploare care merg direct la triace ptr comanda in faza. Solutia adoptata a fost sa folosesc 4 filtre digitale de tip IIR (Infinite Impulse Response), dar pana la urma am abandonat ptr ca mi-a captat altceva interesul: m-am apucat de aeromodele :supz: . Pot doar sa-ti spun ca lucram cu 2 bufere de aprox 1000 de esantioane in contratimp. In timp ce procesam unul din ele, DMAul mi-l incarca pe celalalt samd.Probabil ca nu ti-am raspuns exact la intrebare, dar sper ca ti-am dat niste sugestii de cautare.Bafta!CiripEDIT: MAC = Multiply ACcumulate.EDIT2: Daca tot m-am pornit... Am impresia ca Winamp nu face FFT. Winamp profita de separarea in binuri de frecventa deja existente in codarea mp3. Desi pare un FFT, nu e, dar incanta ochiul. E un fel de "Pui p-asta pierzi ca n-are/Pui p-asta nu-i marcatoare..." Place la ochi, dar e facatura :smt005

[rotten]

Am facut primul benchmark , cu programul aratat in http://www.library.cornell.edu/nr/cbookcpdf.html - pdf-ul 12.2 si 12.3 , fara nici o modificare

Pentru parcurgerea unui array cu 256 valori , functia ruleaza ~ 49 mS in varianta fara nici o optimizare - calcule cu precizie double , etc

O sa incerc sa ii reduc precizia , eventual sa nu mai calculez nimic cu virgula mobila si postez rezultatele

Timpul ala nu include si timpul de conversie al ADC-ului

[bogdanm]

Iti garantez ca daca scapi de virgula mobila lucrurile se vor imbunatati semnificativ. In functie de precizia de care ai nevoie, poti sa mergi de la 8.8 pana la 16.16 in orice configuratie vrei. Am scris cateva librarii de emulare virgula mobila si pot sa-ti spun cu certitudine ca sunt extrem de lente chiar pe arhitecturi mult mai evoluate decat AVR-ul.

[cirip]

Corect ce zice @bogdanm.Orice mod de lucru emulat, in cazul asta virgula mobila, cand procesorul lucreaza nativ cu intregi, este extrem de costisitor la timp. Din experienta mea, lucrul cu intregi cu semn pe 16 biti este acceptabil ptr aplicatii nu foarte pretentioase.Am tras un ochi pe procesor. Are instructiune MUL, deci e pos. sa calculeze repejor daca ii spui compilatorului sa faca uz de multiplicatorul hardware. Viitorul pare luminos. :partyman: :supz: Cirip

[rotten]

E o problema la folosirea de integer in loc de float: FFT-ul in sine se foloseste de sinus / cosinus -> daca il convertesc la integer nu stiu cat de bine o sa mai functioneze. Incerc sa las doar rezultatele pe integre , si calculele interne in continuare pe float, sa vad ce obtin

[bogdanm]

Pai nu-l convertesti la integer, il convertesti la fixed point.

 

http://www.opferman.net/Text/fixed.txt

http://www.piclist.com/techref/method/math/fixed.htm

http://www.codeguru.com/cpp/cpp/algorit ... hp/c12097/

 

Daca pui gogu sa caute "fixed point math tutorial" sau ceva asemanator o sa gasesti si mai multe informatii, precum si "librarii" de fixed point (care sunt de fapt niste functii extrem de simple).