FFT

A pisza jak potem interpretowac wyniki ?

J.

"Unfortunately, it can lead to results that are easy to misinterpret"

J.

Zgadza sie ale nie pisalem ze to metoda ktora jest panaceum na wszystko i mozna ja stosowac bez zrozumienia... natomiast jest alternatywa dla DFT w wielu sytuacjach gdy nie mamy mozliwosci zrobienia zwyczjanie FFT bo mamy za malo probek...

Dnia Thu, 23 Nov 2006 22:23:10 +0100 "seba" snipped-for-privacy@o2.pl napisał(a):

Hej !!

Proponuje zajrzec do ksiazki o matematyce dyskretnej. Ogolnie nie jest to trudne. Pozatym calke mozna zastapic z pewna dokladnoscia skonczona suma skladnikow :). Polcam jakas ksiazke o metodach numerycznych np. Bjorck i Dalquist "Metody numeryczne" tam powinno sie to znalezc. Wszystko bedzie jasne, a sam algorytm tez zrobi sie duzo prostszy niezaleznie od jezyka programowania.

Pozdrawiam,

Wojciech Bartczak

BartekK napisał(a):

Możesz przyjąć skończoną dokładność i robić obliczenia na liczbach stałoprzecinkowych. Np. przeskalować wszystkie dane wejściowe do zakresu <-1,1) i zapisać je jako liczy 16 bitowe (1 bit znaku i 15 bitów części ułamkowej). Obliczenia na liczbach stałoprzecinkowych robi się szybko i przyjemnie, tak pracuje większość obecnie produkowanych procesorów sygnałowych (DSP), z czego Texas Instruments robi z 80% z nich.

A w jakim jezyku? Jeśli w C to FFT najlepiej liczyć chyba fftw.

Po klopocie, ale w sytuacjach wymagajacych zgrubnego podzialu na podpasma, takich jak filtrowanie itp. Jesli jednak chce sie policzyc _DFT_, to po dostawieniu zer wyniki beda opisywaly cos innego, niz dana funkcja.

A po co to liczyc sprzetowo, skoro algorytm jest latwy, dobrze implementowalny i wydajny, zwlaszcza przy wsparciu sprzetowym do adresowania w odwróconym porzadku bitowym?

Pozdrawiam Piotr Wyderski

Adam Dybkowski napisał(a):

Myslalem o tym, ale dla danych wejsciowych o rozdzielczosci 12bit (a docelowo raczej 16bit) skalowanie do 16bit nie byloby sensowne chyba (przeciez i tak juz maja zakres 0-0xffff) wiec mozna po prostu przyjac ze to co jest zapisane jako 0-65535 to jest -1 do +1. Tylko ze jak nakarmilem ten algorytm (tak na piechote na pc) dosc losowymi danymi o rozpietosci 16bitowej to floaty zaczely mi siegac od bardzo malych (ktore nijak na 16bit -1 do +1 bym nie zapisal na 1bicie) do bardzo duzych - ktore by mi sie w 32bit nie zmiescily... Sproboje jeszcze przerobic to wszystko na int, i zobaczyc czy z poobcinania bitow cokolwiek wyjdzie, czy wszystkie wspolczynniki powpadaja w nasycenie od dolu lub gory.

I bardzo dobrze do tego podszedles - trzeba sprawdzic, bo na oko to 16-bitowa dokladnosc moze byc za mala. Tymi malymi liczbami byc moze nie trzeba sie przejmowac - wpiszesz zero, a liczba i moze jest pomijalnie mala. Byc moze bedzie sens te 12-bitowe liczby wstepnie przemnozyc przez 2, 4 czy 8.

Niestety - jest to dosc skomplikowany przypadek do analizy dokladnosci.

J.

Wierze Ci na slowo.

Do tego by miec reverse adressing to trzeba miec DSP ktore wspiera - jesli mnie pamiec nie myli maja to dopiero TI z rodziny 50, a sprzetowo dlatego ze mozna trafic za grosze uklad ktory to zwyczajnie zrobi...

Naprawde nie wyobrazam sobie efektywnej implementacji FFT 16384 punkty na 8 czy nawet 16 bitowym staloprzecinkowym procesorze o ograniczonych zasobach i bez wsparcia w hardware... - juz predzej jakis ARM za 40zl jako koprocesor FFT...

BartekK napisał(a):

Pamiętaj jednak o prostych zasadach obliczeń na liczbach stałoprzecinkowych, gdzie wymagana jest m.in. konwersja przy mnożeniu. Przykładowo 1/2 * 1/2 = 1/4 ale proste zapisanie tego na liczbach stałoprzecinkowych z 15 bitami ułamka i wykonanie mnożenia 0x4000 *

Nie ma takiej potrzeby. Wez np. sinus zsamplowany w 5 punktach i wyznacz DFT wektora dlugosci 5. Nastepnie dopisz do niego 3 zera, zrób FFT wektora dlugosci 8 i porównaj wyniki. :-)

No tak, ale pytanie o to, po co komu taki uklad. Ja sobie nie wyobrazam mozliwosci jego zastosowania w warunkach amatorskich, a FFT uzywam. Pomijam przy tym fakt, ze uklad zajmuje miejsce na plytce, pobiera energie i slabo u niego z rekonfigurowalnoscia. Gdybym mial potrzebe szybkiego policzenia FFT, to po prostu wzialbym mocniejszy procesor, np.jakies zmiennoprzecinkowe DSP. Owszem, mozna sobie kupic sprzetowy procesor fourierowski "to impress chicks", ale ja pytam o rzeczywiste potrzeby... ;-)

Ale nie wiadomo, co dla kogo znaczy "efektywnie" -- jednemu wystarczy taka transformata raz na sekunde, inny bedzie chcial co 100 mikrosekund. Poza tym 16384 punkty to sporawo nawet jak na potrzeby przetwarzania sygnalów -- zwykle wystarcza 1024 punkty.

Pozdrawiam Piotr Wyderski

nie omieszkam w wolnym czasie... ale JF ma priorytet - wisze mu jeden opis...

Hm... bo jest okazja... gdyby nie bylo okazji to jak najbardziej proponowany przez Ciebie wariant jest najrozsadniejszy... a poza tym nie jestem programista... rozwiazania w hardware sa dla mnie najlepsze :D

Zdaje sobie sprawe - sporadycznie wykorzystuje FFT rzedu 2^16 - zazwyczaj 2048 - 8192 w zupelnosci wystarcza

pozdrawiam i dziekuje

Dziekuje! Chyba o cos takiego mi chodzilo, z tego co widze. :)

Uzytkownik "J.F." <jfox snipped-for-privacy@poczta.onet.pl> napisal w wiadomosci news: snipped-for-privacy@4ax.com...

J.F.: To juz jest, rzecz jasna, kwestia terminologii. Jezeli sygnal jest rzeczywisty i symetryczny (mozemy przeciez symetrycznie rozszerzyc), to DFT i DCT to to samo. Liczymy tylko na liczbach rzeczywistych, kosztem dluzszego wektora transformaty. Maciej

Jesli rozszerzysz, to jest to juz inna funkcja.

A chociaz liczy sie szybciej ? :-)

J.

Uzytkownik "J.F." <jfox snipped-for-privacy@poczta.onet.pl> napisal w wiadomosci >

J.F.: To znowu kwestia terminologii. Funkcja jest ta sama, tylko odtwarza sie z innych wspolczynnikow, innymi wzorami. Szybkosc tez jest ta sama, bo to jest ten sam algorytm. Oczywiscie, w konkretnych przypadkach ktoras z postaci moze sie okazac lepsza. Pozdrowienia, Maciej

No wlasnie nie jest. Czesc wspolczynnikow _od biedy_ pasuje. A reszta nie.

Hm, na DCT sie tak dobrze nie znam, ale wydaje mi sie ze algorytmy wcale nie sa te same.

J.