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

Real FFT - transformata dla sygnalow rzeczywistych

Freddie Chopin 31 Lip 2008 18:43 2828 6
REKLAMA
  • #1 5395986
    Freddie Chopin
    Specjalista - Mikrokontrolery
    szukam i szukam po necie, w kilku miejscach pisze, ze majac N probek mozna je upakowac do zespolonego wektora o dlugosci N/2, policzyc z niego transformate N/2 elementowa a nastepnie zastosowac 'trywialny i szybki' algorytm poukladania tego do kupy, tak aby wynik odpowiadal wlasciwej transformacie. niemniej jednak poszukiwania tego 'trywialnego algorytmu' pokazuja, ze albo nie umiem szukac, albo jego 'trywialnosc' to po prostu kolejny motylek na wyniku, ktory bynajmniej nie jest ani trywialny, ani szybki (tak jak nalezaloby sie spodziewac po opiniach z netu).

    czy ja czegos nie wiem, czy jednak motylek to jedyne wyjscie? nie chce pisac wlasnej biblioteki, poniewaz mam juz gotowe biblioteki w assemblerze do swojego procka (dsPIC33), tyle ze dla zespolonego FFT zespolonego sygnalu. nie chce marnowac polowy cennego miejsca i polowy cykli na liczenie zer, wiec szukam sposobu, zeby te zera pominac...

    z gory dzieki za pomoc.

    4\/3!!
  • REKLAMA
  • Pomocny post
    #2 5408923
    shg
    Poziom 35  
    Freddie Chopin napisał:
    Niemniej jednak poszukiwania tego 'trywialnego algorytmu' pokazuja, ze albo nie umiem szukac, albo jego 'trywialnosc' to po prostu kolejny motylek na wyniku, ktory bynajmniej nie jest ani trywialny, ani szybki (tak jak nalezaloby sie spodziewac po opiniach z netu).

    Niestety, szukać umiesz.
    Jest jeszcze jedna metoda - liczenie dwóch rzeczywistych FFT o rozmiarze N za pomocą jednej zespolonej o rozmiarze N, ale w zasadzie to na jedno wychodzi, przynajmniej pod względem szybkości, ale coś mi się zdaje, że "wyciaganie" wyniku jest prostsze (dodawanie i odejmowanie).

    Wygląda to tak:
    c = a + i*b
    gdzie: a, b - wektory wartości rzeczywistych
    Jako że FFT jest przekształceniem liniowym, to:
    FFT(c) = FFT(a) + i*FFT(b)
    Teraz trudna część bo nie pamiętam :P.
    W każdym razie wykorzystuje się tutaj symetrię, którą odznaczają się wartości zespolonej FFT obliczonej z wartości rzeczywistych.
    Symetria wyglada tak, że część rzeczywista jest symetryczna względem osi rzędnych, a część urojona względem środka układu współrzędnych.
    Nie za bardzo chce mi się "matematykować", na pewno jest to opisane w DSP Guide, albo w Numerical Recipes in C.

    Rewelacyjnie szybkie to to nie jest, ale na pewno szybsze niż liczenie zer.
    Jeżeli chcesz coś pisanego od początku dla liczb rzeczywistych, to proponuję na przykład algorytm Sorensona, ale... On jest strasznie dziwny, jakieś motylki z nieparzystą ilością elementów itp. kiedyś próbowałem się w tym połapać, ale dałem sobie spokój, ale to między innymi dlatego, że źródła miałem w Fortranie :/.
    Teraz znalazłem źródła w C:
    http://musicdsp.org/files/rvfft.cpp
    Nieco opisu i porównanie z innymi algorytmami, które zresztą w pliku z powyższego linku znajdziesz:
    http://musicdsp.org/files/rvfft.ps

    Jakiś algorytm (w C) znajdziesz też w GNU Scientific Library, kiedyś tego używałem, ale nie sprawdzałem jak wygląda kwestia szybkości. W każdym razie procedura jest wmiarę zwięzła i da się łatwo pzepisać na asm.
  • REKLAMA
  • #3 5437524
    vadkudr
    Poziom 12  
    Cytat:
    Wygląda to tak:
    c = a + i*b
    gdzie: a, b - wektory wartości rzeczywistych
    Jako że FFT jest przekształceniem liniowym, to:
    FFT(c) = FFT(a) + i*FFT(b)


    Jezeli a sa probkami 2*k (even), a b sa probkami 2*k+1 (odd), pan moge uzuc' ten algorytm dla kolejnosci rzeczywistej. Patrfi tylko dodac' jeden poziom FFT Cooley-Tukey z motylkami :-)
  • #4 5472716
    Krashan7
    Poziom 17  
    Freddie Chopin napisał:
    w kilku miejscach pisze, ze majac N probek mozna je upakowac do zespolonego wektora o dlugosci N/2, policzyc z niego transformate N/2 elementowa a nastepnie zastosowac 'trywialny i szybki' algorytm poukladania tego do kupy, tak aby wynik odpowiadal wlasciwej transformacie.

    Bo to prawda. Takie sposoby są opisane w książce Lyonsa "Wprowadzenie do cyfrowego przetwarzania sygnałów". Niestety piszę z pracy, a książkę mam w domu, ale postaram się wieczorem streścić ideę.
  • REKLAMA
  • #6 5473615
    __Grzegorz__
    Poziom 30  
    Zerknij do PW... :)
  • REKLAMA
REKLAMA