analizator widma na 8051

Mon, 21 Jul 2003 20:56:25 +0200 jednostka biologiczna o nazwie "Piotr Wyderski" snipped-for-privacy@hoga.pl wyslala do portu 119 jednego z serwerow news nastepujace dane:

W ten sposob wyjasnil mi dzisiaj FFT kolega :-)) W sumie jest to nieskomplikowane:

- Bierzemy probki i odpowienio "mieszamy", tzn. nalezy zrobic tak, ze indeks danej probki w tablicy musimy odwrocic, tzn. jezeli np. bedziemy mieli tablice z osmioma probkami, to jej indeks jest zakodowany na trzech bitach, jezeli teraz mamy probke o indeksie 6, to binarnie jest to 110 i po odwroceniu indeksu mamy 011 czyli 3 i w to miejsce ma trafic probka.

- gwozdz programu - obliczenia przez mnozenie probek przez odpowienie wspolczynniki (jest wzor na te wspolczynniki) i odpowiednie dodawanie (nie bede rysowal tu tych grafow). eto wsio.

FFT dla 16 kresek? :-)

Fakt, domyslnie zalozylem jednorodny rozklad czestotliwosci. Ale w zaproponowanej metodzie to wiele nie zmienia, tylko macierz V bedzie miala nieco inna postac. Tylko znow trzeba ustalic co to znaczy "prazek dla 1500 Hz" -- dokladnie tyle, czy przedzial [1000,5000] Hz. Bo wowczas moje rozwiazanie moze byc za dokladne. :-)

Pozdrawiam Piotr Wyderski

A po co? :-)

Pozdrawiam Piotr Wyderski

Jasne, tylko Ty mowisz o jednej z mozliwych implementacji FFT (mozna tez "mieszac" na koncu, albo w ogole uzyc innego schematu mieszania, bo FFT wcale nie musi byc liczone przy podziale ciagu probek na 2). Mnie glownie chodzi o to _dlaczego_ w ogole takie mieszanie ma sens, skad sie ono bierze, dlaczego wzory opisujace wspolczyniki wygladaja tak, a nie inaczej itd. A bierze sie ono z pewnych wlasnosci ewaluacji wielomianu w zespolonym pierwiastku z 1 odpowiedniego stopnia, ktory to pierwiastek na potrzeby teorii sygnalow "przez przypadek" mozna zamienic na sinusy i cosinusy z wzoru Eulera. :-) Dzieki temu wielomian ten mozna zapisac jako sume dwoch krotszych, z ktorych kazdy znow dzielimy na dwa krotsze i tak az do uzyskania jednomianow. "Prawdziwe" FFT jest procedura rekurencyjna liczaca zaledwie kilka linijek pseudokodu i nie zawiera zadnego mieszania itp. bajerow. Ot, obliczanie FFT ciagu to "podziel go na dwa podciagi, oblicz FFT kazdego z nich, scal uzyskane wyniki. FFT ciagu jednoelementowego to ten sam ciag." Wszystko. :-) To, co Tobie pokazano to "wyczynowa" implementacja FFT, z rekurencja zamieniona na iteracje. Walory edukacyjne tego sa podobne do nauki programowania na podstawie schematu ideowego Pentium. :-)

Ale dlaczego wzor jest taki, a nie inny? :-) Ech moze kiedys w wolnej chwili napisze tu "edukacyjne" wyprowadzenie algorytmu FFT z "atomow", tylko nie wiem, czy ktos chcialby to przeczytac -- to bedzie troche pracochlonne, a pisac w proznie to taka sobie rozrywka.

Pozdrawiam Piotr Wyderski

Tue, 22 Jul 2003 14:43:00 +0200 jednostka biologiczna o nazwie "Piotr Wyderski" snipped-for-privacy@hoga.pl wyslala do portu 119 jednego z serwerow news nastepujace dane:

Aaaa to juz matematyka - brrrrr - dreszcze mnie przechodza na sama mysl :-)))

No to tez fajnie wyglada. Oki, wiec dziele ten bufor (dajmy na to 8 probek, indeksy przyjmijmy na mode jez C - od 0 do 7) na pol, czyli traktuje go jako dwie tablice, jedna bedzie miala elementy o indeksach od 0 do 3 poprzedniej, a druga od 4 do 7. Nastepnie dzielimy te mniejsze tablice znowu i teraz mamy cztery dwuelementowe. Nastepnie rozbijamy je znowu na pol i mamy 8 tablic jednoelementowych. Oki skoro FFT danego ciagu to ten sam ciag, to dotad wszystko rozumiem. Powiedzmy ze program doszedl do etapu podzielenia bufora wejsciowego na jednoelementowe tablice i wywolywana rekurencyjnie funkcja obliczania FFT juz sie dalej nie wywoluje bo doszla do tego miejsca i zwraca wartosci dla tablic jednoelementowych jako wlasnie ich zawartosc (pojedyncza probka). Powiedz mi w takim razie jak scalamy wyniki i bede mial juz kompletny obraz.

Rzeczywiscie, ale w tym przypadku chodzilo mi o otrzymanie recepty na wykonanie zadania (obliczenia FFT z danego ciagu probek), a nie o rozwazania dlaczego tak, a nie inaczej. Chociaz rzeczywiscie zaciekawiles mnie tym teraz.

Choc moze na to nie wyglada, ja przeczytam bardzo chetnie, jezeli rzeczywiscie uda Ci sie tak to ujac, zeby dalo sie zrozumiec.

Bo "fast" z FFT daje sie objasnic w 5-15 minut.

Problemem jest ze nadal delikwent nie wie co zrobic FT

J.

Eee - tu akurat jest jeszcze w miare banalna.

Mamy N probek fi [i=0..N-1] chcemy policzyc wspolczynniki transformaty Fk

Fk=sum(od i=0;do i=N-1; fi*exp(-i*k*j*2pi/N))

j - wiadomo co.

Teraz rozdzielimy wyrazy parzyste i nieparzyste :

Fk = sum(od i=0;do i=N-2 co 2 ; fi*exp(-i*k*j*2pi/N)) + sum(od i=1;do i=N-1 co 2 ; fi*exp(-i*k*j*2pi/N))

czyli

Fk = sum(od i=0;do i=N/2-1 ; f{2i}*exp(-2i*k*j*2pi/N)) + sum(od i=0;do i=N/2-1 ; f{2i+1}*exp(-(2i+1)*k*j*2pi/N))

i oznaczmy obie sumy przez Vpk i Vnk

Teraz policzmy F{k+N/2} = sum(od i=0;do i=N-1; fi*exp(-i*(k+N/2)*j*2pi/N)) =

= sum(od i=0;do i=N/2-1 ; f{2i}*exp(-2i*(k+N/2)*j*2pi/N)) + sum(od i=0;do i=N/2-1 ; f{2i+1}*exp(-(2i+1)*(k+N/2)*j*2pi/N))

= sum(od i=0;do i=N/2-1; f{2i}*exp(-2i*k*j*2pi/N)*exp(-i*N*2pi/N))+ sum(od i=0;do i=N/2-1; f{2i+1}*exp(-(2i+1)*k*j*2pi/N)*exp(-(2i+1)*N/2*2pi/N)))

teraz wezmiemy pod uwage ze exp jest okresowa:

= sum(od i=0;do i=N/2-1; f{2i}*exp(-2i*k*j*2pi/N))- - sum(od i=0;do i=N/2-1;f{2i+1}*exp(-(2i+1)*k*j*2pi/N))

czyli: F{k} = Vpk+Vnk F{k+N/2} = Vpk-Vnk

Oszczednosc jest widoczna: zamiast liczyc dwie skomplikowane sumy po N elementow - liczymy dwie sumy o polowe krotsze i jednym dzialaniem [zespolonym] obliczamy dwa wspolczynniki.

Teraz przygladamy sie wzorom na Vpk ... tak, to tez jest FT. Liczymy ja wiec w taki sam sposob. A jesli szczesliwie N jest potega 2 - to mozemy ta redukcje do konca zastosowac :-)

J.

Tue, 22 Jul 2003 22:58:48 +0200 jednostka biologiczna o nazwie "Zbino" snipped-for-privacy@BEZSPAMUpoczta.onet.pl> wyslala do portu 119 jednego z serwerow news nastepujace dane:

Zgodze sie, ale gazeta bedzie pozniej trudno dostepna wiec lepiej jakby po napisaniu artykulu dla gazety i otrzymaniu honorarium umiescil swoj tekst gdzies na necie, zeby kazdy mogl latwo do tego dotrzec.

Tue, 22 Jul 2003 16:12:53 +0200 jednostka biologiczna o nazwie "Piotr Wyderski" snipped-for-privacy@hoga.pl wyslala do portu 119 jednego z serwerow news nastepujace dane:

Ok. to juz spoko tylko nadal nie czaje parametru w. jak to N-ty pierwiastek z 1 ?

Normalnie :-), chocby z wzoru de Moivre'a, w to pierwiastek zespolony N-tego stopnia z 1. Kazda liczba zespolona (a wiec i 1 :o)) ma dokladnie N pierwiastkow N-tego stopnia, np. sa 4 pierwiastki 4-tego stopnia z 1: 1,-1,i,-i -- kazda z nich podniesiona do potegi 4 da Ci 1. :-) Korzystajac z wzoru Eulera dane sa one wzorem p_k = e^(2*i*pi*k/N) dla k = 0..N-1; nas szczegolnie interesuje w = p_1. Czy to juz Ci cos przypomina? :-)

Pozdrawiam Piotr Wyderski

Pierwiastkuje sie _zwlaszcza_ liczby zespolone, przeciez to jedna z glownych przyczyn ich powstania. :o)

Pozdrawiam Piotr Wyderski

Wed, 23 Jul 2003 14:27:25 +0200 jednostka biologiczna o nazwie "Piotr Wyderski" snipped-for-privacy@hoga.pl wyslala do portu 119 jednego z serwerow news nastepujace dane:

Tak ? Wiec jest tu jakies tlo historyczne ? :-)

Jeszcze nie wiemy czego dokladnie chce ... Poza tym dla '51 oszczednosc chyba bedzie i dla 16 probek.

No wlasnie - 1500 moze oznaczac 1200-1800. A 3000: 2400-3600

I co wtedy ? :-)

J.

Bo na samej matematyce o tym ledwo wspominaja :-)

J.

No a jaka liczba _rzeczywista_ jest sqrt(-1)? :-)

Pozdrawiam Piotr Wyderski

Wlasnie mniej wiecej o to chodzi.

Sa w zasadzie dwa wyjscia. Albo sie upieramy przy DFT i bawimy sie w jakies twierdzenia Parsevala, albo robimy zbior filtrow pasmowych. :-)

Pozdrawiam Piotr Wyderski