logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

[solved]FFT potrzebna mała pomoc

skynet_2 03 Lip 2009 23:30 7206 22
REKLAMA
  • #1 6736729
    skynet_2
    Poziom 26  
    Udało mi się napisać program liczący z 1024 próbek DFT[512 prążków]
    wygląda to tak http://edytor.elektroda.net/out-9.avi 1280x1024(_at_)4.32MB

    Ale mam problem z FFT, ponieważ nie za bardzo rozumiem jak to działa.

    1. najpierw liczy się 2 punktowe DFT dla każdej pary próbek -> wyliczone wartości DFT następnie trafiają na "motylki" i teraz moje pytanie czy na każdym poziomie tych motylków liczy się ponownie DFT?

    2. kolejność próbek wejściowych można zmienić stosując negację binarną, powinno się to zrobić na wejściu czy na wyjściu, czy to bez różnicy?

    _edit: dodam iż rozumiem jak działa DFT, i jak jest wyliczana, łącznie z liczbami zespolonymi, skąd bierze się wysokość prążka, od czego zależy przeciek, co to jest okienkowanie itp.
  • REKLAMA
  • Pomocny post
    #2 6746627
    Tantalos
    Poziom 18  
    1. Obliczenia na wszystkich poziomach są podobne, inne są tylko próbki, zresztą to 2-punktowe DFT to dwa proste wzorki.

    2. Niektóre algorytmy są podane tak , że wymagają zmiany kolejności na wejściu, a inne na wyjściu. Generalnie da się to zmienić ale to wymaga modyfikacji algorytmu, tak aby 2-punktowa DFT była wykonywana dla właściwych próbek.
  • #3 6747405
    skynet_2
    Poziom 26  
    2. faktycznie są 2 algorytmy ale nie zauważyłem że się różnią właśnie zamianą wejść/wyjść.

    1. Czyli 2 punktowe DFT a później tylko dodawania/odejmowania w zależności od kąta fazowego.

    Jest to trochę prostsze niż myślałem, mam nadzieje że wreszcie zadziała bo liczenie DFT z 8192 próbek trochę trwa :P
  • REKLAMA
  • Pomocny post
    #4 6749155
    Aro_
    Poziom 15  
    skynet_2 napisał:
    Czyli 2 punktowe DFT a później tylko dodawania/odejmowania w zależności od kąta fazowego.

    Nie do końca. po tym 2 punktowym DFT następuje synteza widma. Czyli dodawanie i mnożenie przez sinusoidy. W dziedzinie czasu byłoby to dodawanie dwóch sygnałów, z czego jeden jest przesunięty. To przesunięcie to jest splot tego sygnału z funkcją delta, co w dziedzinie częstotliwości odpowiada mnożeniu widma przez sinusoidę. Dlatego na pierwszy rzut oka może to wyglądać jak DFT.
  • #5 6750135
    skynet_2
    Poziom 26  
    Aro_ napisał:
    Nie do końca. po tym 2 punktowym DFT następuje synteza widma. Czyli dodawanie i mnożenie przez sinusoidy. W dziedzinie czasu byłoby to dodawanie dwóch sygnałów, z czego jeden jest przesunięty. To przesunięcie to jest splot tego sygnału z funkcją delta, co w dziedzinie częstotliwości odpowiada mnożeniu widma przez sinusoidę. Dlatego na pierwszy rzut oka może to wyglądać jak DFT.


    Teraz już wiem, dziękuje.

    A możesz napisać na jakiej zasadzie działa FFT, bo jak to obliczyć i jak działa algorytm rozumiem ale dlaczego działa już nie :P

    w zwykłym DFT mnoży się próbki wejściowe przez cos i sin którego "kąt obrotu" dla danej próbki zależy od numeru próbki, po przemnożeniu jeżeli w próbkach jest zawarty sygnał o takiej samej długość fali jak sinusoida tworzona przez sin/cos to suma sin/cos się zwiększa[w zależności od fazy sygnału większa będzie w sin lub cos] a inne długości fali np. 2x się znoszą[pomijając wyciek itp.], teraz za pomocą wzoru pitagorasa wylicza się długość promienia[bo sygnał nie jest "płaski" tylko wygląda jak sprężyna] i stąd się bierze wysokość prążka w dużym uproszczeniu.

    natomiast w FFT na początku jest mnożenie przez 1 i -1, gdyż zależy od od kąta fazowego i dla 2 próbek jest właśnie to 1 i -1[szczyty sinusoid a dokładniej e^0=1; e^-jPI=-1], natomiast dalej występują takie same mnożenia tylko kąt fazowy jest inny, i pojawia już się część urojona. I tu właśnie nie jestem pewien skąd się bierze wysokość prążka, bo sumujemy przemnożone wyniki DFT przez kąt fazowy a nie próbki wejściowe, chyba że potraktujemy próbki po DFT jako zsumowane próbki wejściowe[bo właściwie tak jest :P] i wtedy mnożąc jest przez kąt fazowy otrzymujemy takie same operacje jak w DFT(N), chyba załapałem ja to działa pisząc odpowiedz :D
  • Pomocny post
    #6 6750406
    Aro_
    Poziom 15  
    skynet_2 napisał:
    ...i wtedy mnożąc jest przez kąt fazowy otrzymujemy takie same operacje jak w DFT(N)

    Coś mi tu nie pasuje w tym zdaniu, to nie jest DFT tylko synteza widma.
    FFT jak dla mnie jest bardzo skomplikowany i choć rozumiem zasadę działania to do końca jeszcze nie załapałem wszystkich szczegółów matematycznych. Ale na chłopski rozum to jest tak:
    Sygnał jest rozkładany na pojedyncze próbki, a jak wiadomo sygnał złożony z jednego punku ma takie samo widmo jak wartośc tego punktu, więc DFT nie musi być w ogóle obliczana. Czasem pomija się ostatni podział i wykonuje się proste DFT 2 lub 4 punktowe, poprawiając nieco ogólną szybkośc. Z postów wynika, że twój algorytm oblicza właśnie takie 2 punktowe DFT. Potem te widma trzeba poskładać w jedno. To już nie jest takie proste. Należy po kolei składac każde 2 punktowe ze sobą, następnie każde 4 punktowe itd. A skoro sygnał wejściowy był rozkładany z przeplotem (na próbki parzyste i nieparzyste) to teraz w taki sam sposób trzeba poskładac ale nie sygał a jego widmo. Tu sprawa się komplikuje, o ile poskładanie dwóch sygnałów jest proste, bo wystarczy interploracja i uzupełnienie zerami dodatkowych próbek. Następnie jeden sygnał należy przesunąć o 1 próbkę. Dodając te dwa sygnały uzyskamy sygnał oryginalny, bo próbki jednego sygnału trafiają na dodane zera drugiego sygnału. Uff, trochę zagmatwałem, ale teraz łatwiej będzie wyjaśnic jak sumowac widma. Trzeba po prostu zrobic to samo tylko w dziedzinie częstotliwości. A więc po kolei... ta interplorocja w dziedzinie czasu daje powielenie widma w dziedzinie częstotliwości, następnie przesuwa się sygnał o 1 punkt czyli wykonuje się splot z funkcą delta. W dziedzinie częstotliwości odpowiada to pomnożeniu widma przez sinusoidę. W tym miejscu zakładam że znasz tą parę transformat oraz wiesz co to dualnośc.
    Mam nadzieję, że choc trochę udało mi się wyjaśnić o co w tym biega. Polecam także książkę "Cyfrowe przetwarzanie sygnałów" Stevena W. Shmith'a. Bardzo dobra książka dla początkujących, wszyskto ładnie wytłumaczone bez zawiłych wzorów.
  • #7 6750733
    skynet_2
    Poziom 26  
    załóżmy N=8

    [solved]FFT potrzebna mała pomoc

    Mój algorytm[niekompletny] liczy 2 punktowe DFT[1 i -1] z próbek poddanych przestawieniu[1 warstwa][czyli po prostu dodaje i odejmuje] a umieszcza te dane w tablicy pierwszej[size=8][to prawa strona 1 warstwy] dalej już pojawia się część urojona więc dane po przemnożeniu pakowane są do 2 tablicy[dlatego że nie można ich tak po prostu dodać] później kolejne mnożenie i 3 tablica później jest to sumowane i wyciągana wartość prążka. Oczywiście jest tu za dużo obliczeń bo alg nie jest skończony.

    Aktualnie próbuje coś zdziałać przy pomocy książki "Wprowadzenie do cyfrowego przetwarzania sygnałów Richard G. Lyons"

    co to dualnośc niestety nie wiem co to jest, w ogóle się nie znam na tak zaawansowanej matematyce[chociaż bardzo lubię matematykę] więc mi to średnio idzie, ale się ucze :D.

    Cytat:
    ...i wtedy mnożąc jest przez kąt fazowy otrzymujemy takie same operacje jak w DFT(N)

    miałem na myśli że teoretycznie to jest to samo bo licząc DFT mamy 8 mnożeń zespolonych, a licząc w FFT każdą próbkę oddzielnie mamy podobną liczbę mnożeń tylko że wcześniej wykonane mnożenia można wykorzystać, żeby się o tym przekonać muszę sprawdzić wszystkie "W" w tym przykładzie i porównać z DFT, oczywiście mogę się mylić :P

    Cytat:
    Coś mi tu nie pasuje w tym zdaniu, to nie jest DFT tylko synteza widma.
    w książce piszą że FFT to DFT ze zmniejszoną liczbą obliczeń, oczywiście mogę to źle odbierać bo dopiero zacząłem to rozumieć.

    Cytat:
    A skoro sygnał wejściowy był rozkładany z przeplotem (na próbki parzyste i nieparzyste) to teraz w taki sam sposób trzeba poskładac ale nie sygał a jego widmo. Tu sprawa się komplikuje, o ile poskładanie dwóch sygnałów jest proste, bo wystarczy interploracja i uzupełnienie zerami dodatkowych próbek. Następnie jeden sygnał należy przesunąć o 1 próbkę. Dodając te dwa sygnały uzyskamy sygnał oryginalny, bo próbki jednego sygnału trafiają na dodane zera drugiego sygnału.

    co do tego uzupełniania zerami to ja piszę o algorytmie Cooleya-Tukeya, ten z motylkam i tam nic nie znalazłem nic o uzupełnianiu zerami
    i
    Cytat:
    następnie przesuwa się sygnał o 1 punkt czyli wykonuje się splot z funkcą delta. W dziedzinie częstotliwości odpowiada to pomnożeniu widma przez sinusoidę.

    tutaj też trochę nie rozumiem, przesuwanie gdzie? splot z funkcją delta?.

    przeanalizuje jak się ma FFT do DFT i dokończę algorytm bo aktualnie mi wywala jakieś bzdury[problem z rzutowaniem zmiennych] na ostatnim poziomie czyli tak gdzie się wylicza już wysokość prążka.

    Według mnie DFT to jest zwykły filtr[cyfrowy?] na każdy prążek a FFT to DFT tylko inaczej liczone.
  • Pomocny post
    #8 6754663
    Aro_
    Poziom 15  
    Tak, FFT wymaga dużo mniej obliczeń (N*log2N) od tradycyjnego dyskretnego DFT (N*N), ale daje identyczny wynik, jest to ta sama operacja matematyczna, ale obliczana różnymi sposobami.
    To uzupełnianie zerami, przesuwanie i sumowanie to jest właśnie motylek. Chciałem tylko wyjaśnić, że motylek to nie transformata DFT, ale widać jeszcze bardziej pogmatwałem. Może spróbuję tak:
    Powiedzmy, że masz sygnał abcdefgh, który poddajesz transformacie przez FFT. Czyli musisz rozdzielic sygnał na powiedzmy 4 dwupunkowe.
    Całośc wygląda tak:
    1. podział na parzyste i nieparzyste (numery próbek!, nie myl z rozkładem parzysto-nieparzystym, bo to całkiem co innego) otrzymujemy: aceg i bdfh
    2. kolejny podział na 4 sygnały: ae cg bf dh
    3. 2-punktowa transforamta DFT: ae->DFT->AE, cg->DFT->CG itd.
    4. Motylki, czyli synteza widma. Łączenie każdych dwóch widm. Tu pokaże o co chodzi z tymi "zerami":)
    AE i CG mają się stać jednym widmem, tylko jak to zrobić... trzeba podpatrzyc jak to się robi w dziedzinie czasu.
    ae i cg mają połączyc sie w aceg czyli trzeba poddac je interploracji i uzupełnic zerami: a0e0 oraz c0g0. Wciąż nie można ich dodac, jeden z nich należy przesunąc: 0c0g, piąta próbka wynosi 0 i nie musimy się nią martwic. Po tych zabiegach można dodac sygnały: a0e0 + 0c0g = aceg. Udało się, ale trzeba zrobic to samo w dziedzinie częstotliwości. Ale jak? Podpatrzymy jak mają wygląda widma tych sygnałów: a0b0->DFT->ABAB, 0c0g->DFT->? uwaga! sygnał jest przesunięty, żeby Cię nie martwic, musisz uwierzyc mi na słowo że takie przesunięcie sygnału w dziedzinie czasu to to samo co pomnożenie widma przez sinusoidę. Czyli nasze widmo będzie wyglądac tak: 0c0g->DFT->C*sin(90) G*sin(270) C*sin(90) G*sin(270). Tak naprawdę trzaba uwzględnic częśc rzeczywistą i urojoną, gdzie sinusoida jest przesunięta o -90 stopni. Widmo urojone dla tego przypadku będzie wynosiło 0000 gdyż wartości sinusoid dla 0 i 180 stopni też są zerowe. No i doszliśmy do rozwiązania a więc AE i CG dają widmo A+C*sin E+G*sin A+C*sin E+G*sin, pod skróceniu A+C E-G A+C E-G. BF i DH łączymy tak samo.
    5. dalsza synteza widma, łączenie 2 widm 4 punktowych. Robi się to tak samo jak wyżej, tylko mnoży się już przez 4 wartości sinusoidy (lub kosinusoidy, jak komu wygodniej:) dla części rzeczywistej i 4 wartości przesuniętej sinusoidy dla wartości urojonych.
    6. możemy cieszyc się wynikiem 8punktowego szybkiego przekształcenia Fouriera:)
    To jest moje rozumowanie, ale spotkałem się z innymi bardziej zagmatwanymi matematyczne.
    Dodam, że gdy kiedyś chciałem od początku napisac algorytm FFT to zatrzymałem się na 16 punktach... potem uznałem wyższośc algorytmu Cooleya-Tukeya. Mój był strasznie chaotyczny i mało uniwersalny, a dalsze zwiększanie ilości próbkek było bezcelowe. Ale to było dawno, jeszcze do końca nie wiedziałem co to FFT :P
    Jeśli chcesz mogę wrzucic sprawdzone algrorytmy dla dowolnej 2^N liczby próbek, mam ściągniętego z neta w C, oraz przerobiony na basica, w 100% dobry, zarówno dla liczb zespolonych, jak i zoptymalizowany dla rzeczywistych.
    Miałem kiedyś tą książkę o której piszesz, są tam ciekawe przykłady, ale o ile pamiętam autor pisze jak działa FFT, ale już nie tłumaczy. Dokładnie nie pamiętam, wiem tylko że to była moja pierwsza książka o DSP i bardzo się przydała.
    Cóż DFT jako zespół filtrów dla każdego prążka... no, można sobie to tak tłumaczyc na początek, łatwiej zrozumiec podstawowe zastosowanie, ale pamiętaj że DFT to przejście z dziedziny czasu do dziedziny częstotliwości, bez utraty informacji o sygnale.
  • #9 6755646
    skynet_2
    Poziom 26  
    Więc tak przegryzienie się przez to trochę mi zajmie ;).

    Aro_ napisał:
    Cóż DFT jako zespół filtrów dla każdego prążka... no, można sobie to tak tłumaczyc na początek, łatwiej zrozumiec podstawowe zastosowanie, ale pamiętaj że DFT to przejście z dziedziny czasu do dziedziny częstotliwości, bez utraty informacji o sygnale.


    wydaje mi się że mam rację, ale spójrz na poniższy wykres.
    [solved]FFT potrzebna mała pomoc
    hipotetyczny pierwszy prążek, wiem że normalnie będzie w innym miejscu przechodzić przez zero ale tak jest czytelniej.
    sygnał wejściowy sin(x)
    r(x) to wartości części rzeczywistej przez jakie mnożymy sygnał wejściowy.
    i(x) to wartości części urojonej przez jakie mnożymy sygnał wejściowy.

    Jak widzisz po pomnożeniu sygnału wejściowego[którym jest sin(x)] przez część rzeczywistą czyli cos i zsumowaniu sygnału otrzymany wartość zero, natomiast po przemnożeniu sygnału wejściowego przez część urojoną i zsumowaniu otrzymamy wartość 4[obliczyłem].
    fr(x) to sygnał wejściowy * część rzeczywista;
    fi(x) to sygnał wejściowy * część urojona;

    I jak widzisz sygnał fr(x) powstaje, ale się "znosi" podczas sumowania.
    natomiast fi(x) nie zostaje "zniesione" ponieważ jest w fazie.

    teraz napisałem prosty program aby to policzyć:

    //============================================================================
    // Name        : dft_example.cpp
    // Author      : skynet
    // Version     :
    // Copyright   :
    // Description : simple DFT example
    //============================================================================
    
    #include <iostream>
    #include <cmath>
    
    using namespace std;
    
    #define PI 3.1415926535897931160
    
    double zero(double i, int z)
    {
    	   return floor(i*pow(10.0, z))/pow(10.0, z);
    }
    
    int main() {
    	int n;
    	double in[8];
    	double r[8], i[8];
    	double out[2]={0, 0};
    	for(n=0; n<8; ++n)
    		in[n] = sin((2*PI)*n/8);
    
    	for(n=0; n<8; ++n)
    	{
    		r[n] = in[n]*cos((2*PI)*n/8);
    		i[n] = in[n]*sin((2*PI)*n/8);
    		cout << zero(r[n], 1) << "	" << zero(i[n], 1) << endl;
    	}
    
    	for(n=0; n<8; ++n)
    	{
    		out[0] += r[n];
    		out[1] -= i[n];
    	}
    
    	cout << endl << "suma R: " << zero(out[0], 1) << "	" << "suma I: " <<  zero(out[1], 1) << endl;
    
    	cout << "wysokość:	" << sqrt(pow(out[0], 2)+pow(out[1], 2)) << endl;
    	cout << "kąt:		" << atan(out[1]/out[0])*180/PI << endl;
    
    	return 0;
    }
    


    i w wyniku dostajemy:

    0	0
    0.5	0.4
    0	1
    -0.5	0.5
    -0.1	0
    0.5	0.4
    0	1
    -0.5	0.5
    
    suma R: 0	suma I: -4
    wysokość:	4
    kąt:		-90


    czyli wszystko się zgadza

    Dodam jeszcze że gdyby pojawiła się 2 częstotliwość np. sin(x*2) to została by ona zniesiona tak samo przez sin jak i cos czyli nie było by jej w naszym prążku. Natomiast częstotliwości o wartościach innych niż wielokrotność pierwszego prążka pojawią się jako wyciek ponieważ nie zmieści się cały okres[a raczej jego wielokrotność] owej częstotliwości w oknie próbkowania.

    I to by było na tyle jeżeli chodzi o to jak rozumiem DFT :D

    nad tym co napisałeś muszę jeszcze pomyśleć bo jakoś nie mam teraz do tego głowy :P
  • Pomocny post
    #10 6756113
    Aro_
    Poziom 15  
    Zgadza się! To o czym piszesz to metoda korelacyjna, która jest najczęściej stosowana do obliczania DFT (przynajmniej dla N<32, dla większych N stosuje się FFT).
    Wyobrażenie sobie DFT jako filtracji jest dobre i intuicyjne przy analizie widma, jednak samo DFT to nie filtracja! Dopiero cały proces: DTF->pomnożenie widma sygnału przez widmo odpowiedzi impulsowej filtra->odwrotne DFT - to jest filtracja. Od biedy można uznać że czasowo-częstotliwościowe DFT też jest zespołem filtrów, ale nie jestem tego pewien.
    Na koniec jeszcze mała poprawka do pkt 4 poprzedniego postu, bo zapomniałem że mnożenie liczb zespolonych jest trochę inne. (Re=Re1*Re2-Im1*Im2, Im=Im1*Re2+Re1*Im2) Po syntezie widmo urojone nie będzie więc zerowe, tylko będzie miało jakąś wartość.
  • REKLAMA
  • #11 6756660
    skynet_2
    Poziom 26  
    Aro_ napisał:
    Wyobrażenie sobie DFT jako filtracji jest dobre i intuicyjne przy analizie widma, jednak samo DFT to nie filtracja! Dopiero cały proces: DTF->pomnożenie widma sygnału przez widmo odpowiedzi impulsowej filtra->odwrotne DFT - to jest filtracja. Od biedy można uznać że czasowo-częstotliwościowe DFT też jest zespołem filtrów, ale nie jestem tego pewien.


    Wiem że to nie jest klasyczna filtracja, ale miałem na myśli że jakby wyciągasz fragment widma z sygnału wejściowego, usuwając pozostałe częstotliwości[jakby je odfiltrowujesz], najprościej mówiąc każdy wzór na prążek przepuszcza tylko fragment widma, blokując resztę widma. Dlatego jest to tak niewydajne, natomiast FFT analizuje jednocześnie całe widmo zamiast z każdym prążkiem liczyć znowu "to samo"[czyli znowu wywalać[odfiltrowywać] pozostałe prążki], FFT to już nie "zespół filtrów" a skomplikowane przekształcenie analizujące cały sygnał.
  • #12 6757374
    Aro_
    Poziom 15  
    Idea myślenia chyba dobra. No bo w końcu tak jest. W metodzie korelacyjnej obliczane jest wielokrotnie to samo, a FFT oblicza tylko to co potrzebne. Tak można wyjaśnić po co stosować FFT. Niestety wydaje mi się, że myśląc w ten sposób będziesz miał kłopoty z jego zrozumieniem. Oczywiście mogę się mylić. W każdym razie gdyby ktoś tłumaczył mi to w ten sposób, to łatwo zrozumiałbym dlaczego DFT jest nieefektywne, ale miałbym już spore kłopoty z załapaniem o co chodzi w szybkim przekształceniu.
  • #13 6766299
    skynet_2
    Poziom 26  
    dzięki za pomoc Aro_, mój własny FFT a nie jakiś tam skopiowany już działa :D
    Ale nadal nie mam pojęcia gdzie ty żeś to uzupełniał zerami.
    U mnie działa tylko jedna funkcja licząca wszystkie motylki na dany poziom.

    #define PI 3.14159265358979323846f
    
    void but(int lev, double **in, double **out)
    {
    //	level 0 1 2 dla N = 8
    	int n;
    	for(n=0; n<N; n++)
    	{
    		int b = (1<<lev);
    		if((n&b)==0)
    		{
    			if(lev==0)
    			{
    				//przyspiesza obliczenia na poziomie 0
    				out[n  ][0] = in[n][0]+in[n+1][0];
    				out[n+1][0] = in[n][0]-in[n+1][0];
    			}
    			else
    			{
    //			Re=Re1*Re2-Im1*Im2
    //			Im=Im1*Re2+Re1*Im2
    				int v = (1<<(lev+1));
    				double Re1;
    				double Im1;
    
    				double Re2 = in[n+b][0];
    				double Im2 = in[n+b][1];
    
    				Re1 =  cos(2*PI*(n%v)/v);
    				Im1 = -sin(2*PI*(n%v)/v);
    
    				out[n][0]  = Re1*Re2-Im1*Im2;
    				out[n][1]  = Im1*Re2+Re1*Im2;
    				out[n][0] += in[n][0];
    				out[n][1] += in[n][1];
    
    				Re1 =  cos(2*PI*((n+b)%v)/v);
    				Im1 = -sin(2*PI*((n+b)%v)/v);
    
    				out[n+b][0]  = Re1*Re2-Im1*Im2;
    				out[n+b][1]  = Im1*Re2+Re1*Im2;
    				out[n+b][0] += in[n][0];
    				out[n+b][1] += in[n][1];
    
    			}
    		}
    		cout << n << "	" << zero(out[n][0], 2) << " " << zero(out[n][1], 2) << endl;
    	}
    }


    Strasznie to proste jest, a się tyle czasu męczyłem żeby zaczęło działać.
    Później to usprawnię dając tablicę z sin cos, i jeszcze parę innych poprawek.

    i otrzymujemy dla
    	dataIn[0] =  0.3535;
    	dataIn[1] =  0.3535;
    	dataIn[2] =  0.6464;
    	dataIn[3] =  1.0607;
    	dataIn[4] =  0.3535;
    	dataIn[5] = -1.0607;
    	dataIn[6] = -1.3535;
    	dataIn[7] = -0.3535;

    wynik
    0.0001
    3.9999
    2.0001
    0.0001
    0.0001
    0.0001
    2.0001
    3.9999


    Za bezcenną pomoc przesyłam koledze 400pkt.
  • #14 6766481
    Aro_
    Poziom 15  
    Cytat:
    Ale nadal nie mam pojęcia gdzie ty żeś to uzupełniał zerami.

    Ehh, przecież mówiłem, że to tylko po to aby zrozumieć co to jest motylek w FFT. Tego nie znajdziesz w programie, bo operujesz na widmach, czyli sygnałach w dziedzinie częstotliwości.

    Cytat:
    Za bezcenną pomoc przesyłam koledze 400pkt.

    Noo, bez przesady, ale dzięki:) W końcu praktycznie sam rozgryzłeś ten algorytm.
  • #15 6766998
    skynet_2
    Poziom 26  
    Aro_ napisał:
    Cytat:
    Ale nadal nie mam pojęcia gdzie ty żeś to uzupełniał zerami.

    Ehh, przecież mówiłem, że to tylko po to aby zrozumieć co to jest motylek w FFT. Tego nie znajdziesz w programie, bo operujesz na widmach, czyli sygnałach w dziedzinie częstotliwości.

    Aha już zaczynam rozumieć, ale i tak niedługo kupię tą książkę "Cyfrowe przetwarzanie sygnałów" Stevena W. Shmith'a żeby zrozumieć co ten algorytm dokładnie robi :P bo całości jakoś nie mogę na razie załapać.
    Aro_ napisał:
    Cytat:
    Za bezcenną pomoc przesyłam koledze 400pkt.

    Noo, bez przesady, ale dzięki:) W końcu praktycznie sam rozgryzłeś ten algorytm.

    W kilku miejscach żeś mi bardzo pomógł.

    Tak czy inaczej jak będę miał książkę, to sobie na spokojnie spróbuje zrozumieć wszystkie zawiłości tego algorytmu, bo jednak wzory to nie wszystko ;).

    A co do tych 400pkt w porównaniu z czasem jaki zmarnowałem próbując to rozgryźć samemu, to naprawdę nic.
  • #16 6770041
    Aro_
    Poziom 15  
    Tylko koniecznie przeczytaj też o DFT, jej własnościach, także o splocie. W dalszej przyszłości polecam książkę "Cyfrowe przetwarzanie sygnałów" Tomasza P. Zielińskiego. Ogromna ilość materiału z DSP, tylko dużo matematyki.
  • #17 6771632
    Tantalos
    Poziom 18  
    Z matematycznego punktu wygląda to tak, że ktoś zauważył, że DFT o długości N próbek można obliczyć jako 2 DFT o długości N/2 probek - dla parzystych i nieparzystych próbek, a te znowu można podzielić na dwie części aż dojdziemy do DFT z dwu próbek. Wg wzoru:
    X[k]=∑x[n]WN^kn
    X[k]=∑x[2r]WN^2rk + ∑x[2r+1]WN^k(2r+1) = ∑x[2r]WN^2rk + WN^k ∑x[2r+1]WN^2rk = a + WN^k b

    W obydwu częściach mamy współczynnik WN^2rk, więc nie musimy go liczyć dwa razy. Poza tym obliczenie DFT o N/2 próbek jest czterokrotnie szybsze i stąd znaczne przyspieszenie obliczeń. DFT jest dyskretną wersją transformaty Fouriera. Aby zrozumieć DFT trzeba najpierw zrozumieć transformatę Fouriera, a to wymaga dużej wiedzy z matematyki. Jeśli jesteś zainteresowany to mogę to wyjaśnić w prosty sposób.
  • #18 6771784
    skynet_2
    Poziom 26  
    Cóż, wydaje mi się że rozumiem jak działa DFT.
    Fragment
    Cytat:
    Aby zrozumieć DFT trzeba najpierw zrozumieć transformatę Fouriera, a to wymaga dużej wiedzy z matematyki.
    jak dużej, albo raczej czego?
    wyżej Link opisałem jak według mnie działa DFT, tzn jak ja to rozumiem.

    Co do tych wzorów to 2 części po prostu wyłączyłeś stały kąt fazowy przed znak sumowania.

    Ale jeżeli masz czas chętnie się dowiem czegoś o transformacie Fouriera.
  • Pomocny post
    #19 6772411
    Tantalos
    Poziom 18  
    skynet_2 napisał:
    Co do tych wzorów to 2 części po prostu wyłączyłeś stały kąt fazowy przed znak sumowania.

    Na tym właśnie polega FFT - poprzez sprytne rozdzielenie pewnych obliczeń robi to samo co DFT, tyle że dużo szybciej.

    W skrócie jak można wyprowadzić wzór na transformatę Fouriera:

    Mamy przestrzeń wektorową, np. 3-wymiarową i dwa wektrory x=[x1,x2,x3] i y=[y1,y2,y3]. Każdy wektor można przedstawić jako kombinację liniową 3 wektorów bazowych x = a1*b1 + a2*b2 + a3*b3. Wybieramy wektory bazowe tak aby były ortogonalne, czyli iloczyn wektorowy <bn,bm> = 0, m≠n. Wtedy współczynnik an możemy obliczyć jako rzut danego wektora x na wektor bazowy bn:
    an = <x,bn>/||bn||.

    Iloczyn skalarny obliczamy wg wzoru:
    Σxn*yn, n - wymiar przestrzeni wektorowej

    Teraz wyobraźmy sobie, że przestrzeń wektorowa jest nieskończenie wymiarowa, a współrzędne są wartościami funkcji. Wtedy iloczyn skalarny takiej przestrzeni wektorowej możemy przedstawić:

    <f,g> = ∫f(x)g(x)dx, w granicach -∞ do +∞

    Funkcje również mogą być ortogonalne, takimi funkcjami są sin i cos, więc mogą być wektorami bazowymi - wtedy każdą funkcję można przedstawić jako kombinację liniową funkcji bazowych. Dla uproszczenia użyjemy formuły Eulera:

    cos(nx) + isin(nx) = exp(inx)

    Wtedy funkcję okresową można przedstawić:

    f(x) = 1/T Σ cn*exp(inωx), w granicach (-T/2, +T/2), ω=2π/T

    cn = <f(x),exp(inωx)> = ∫f(x)exp(-inωx)dx
  • REKLAMA
  • #20 6773402
    skynet_2
    Poziom 26  
    Trochę to zbyt skomplikowane więc dużo nie rozumiem, szkoda że żeś nie wyjaśnił po kolei co robisz.

    Przestrzeń 3-wymiarowa czyli x , y, z?[Re Im czas?]
    Formuła Eulera, tak używałem tego przy DFT więc już się tym sprawnie posługuje.

    Czyli jednak muszę się trochę podciągnąć z matematyki.
  • Pomocny post
    #21 6773790
    Tantalos
    Poziom 18  
    Widzę, że kolega jest głodny wiedzy, a warto to zrozumieć bo na tej zasadzie opierają się wszystkie transformaty używane do obróbki sygnałów jak. np transformata falkowa. No to po kolei.

    Najpierw przestrzeń 3-wymiarowa. Każdy wektor można wyrazić poprzez kombinację liniową 3 wektorów bazowych. W najprostszym przypadku mogą to być wektory osi współrzędnych e1=[1,0,0], e2=[0,1,0], e3=[0,0,1]. Np. wektor x[3,2,1] = 3*e1 + 2*e2 + 1*e1. Wektory e1,e2,e3 tworzą ortonormalną bazę dla przestrzeni 3-wymiarowej, czyli są ortogonalne i mają długość ||bn|| = 1. Równie dobrze możemy wybrać inną bazę wektorową - jest ich nieskończenie wiele, np. b1=1/√2[1,1,0], b2=√2[-1,1,0], b3=[0,0,1].
    Wektory te są ortonormalne np. <b1,b2> = 1*-1 + 1*1 + 0*0 = 0 oraz <b1,b1> = 1.
    Aby wyrazić nasz wektor x w nowej bazie musimy dokonać jego transformacji do nowej bazy. Nowe współrzędne obliczamy przez projekcję wektora x na wektory bazowe.

    a1 = <x,b1>/||b1|| = 5√2
    a2 = <x,b2>/||b2|| = -√2
    a3 = <x,b3>/||b3|| = 1

    W postaci macierzowej:

    |√2 √2 0| |3|
    |-√2 √2 0| * |2|
    |0 0 1| |1|

    Iloczyn wektorowy <x,y> = Σ xn*yn

    Teraz przejście do przestrzeni nieskończenie wymiarowej:
    Nie mamy tu współrzędnych wektorów, ale mamy funkcje. Dlatego symbol sumy zastępujemy całką:

    <f,g> = ∫f(x)*g(x)dx

    Wektory bazowe zastępujemy funkcjami, które spełniają warunek ortogonalności i traktujemy funkcje jak wektory. Fukcje sin i cos spełniają warunek ortogonalności dlatego inne funkcje możemy przedstawić jako kombinację liniową funkcji sin(nx) i cos(nx) w transformacie Fouriera.

    ∫sin(mx)*sin(nx) = 0, m≠n

    W przestrzeni nieskończenie wymiarowej mamy oczywiście nieskończenie wiele współrzędnych. To na tyle wstępu.
  • #22 6780977
    skynet_2
    Poziom 26  
    Niestety narazie mój poziom jest za niski, żeby coś z tego zrozumieć.
  • #23 6869143
    skynet_2
    Poziom 26  
    I wszystko pięknie działa.

    [solved]FFT potrzebna mała pomoc
    Tutaj skorzystałem z wejścia ALSY żeby analizator był zsynchronizowany z sygnałem.

    Jeszcze raz dziękuje pomoc w zrozumieniu części obliczeniowej FFT.
REKLAMA