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

Jak napisać uniwersalną funkcję FFT w C dla różnych mikrokontrolerów?

drzasiek 15 Mar 2012 07:38 3181 4
REKLAMA
  • #1 10679262
    drzasiek
    Specjalista CNC
    Witam.
    Przeczytałem tematy związane z tą tematyką i nadal jestem trochę w niepewny.
    Chcę się upewnić, czy dobrze rozumuję.
    Chcę napisać własną funkcję w języku C realizującą FFT.
    Funkcja ma być uniwersalna, żebym mógł ją sobie przenosić na różne uC.
    Na początek, nie musi być szybka, byle by zadziałała.
    Ulepszaniem zajmę się potem.

    A więc co wiem i co mam:
    -Korzystam z książki prof. Tomasza Zielińskiego "Cyfrowe przetwarzanie sygnałów ..."
    -symulację przeprowadzam w programie MATLAB

    Ale muszę to robić w taki sposób, żeby kod później łatwo można było przenieść do funkcji w języku C na dowolny uC.

    I teraz jak ja to rozumuję: (radix-2)
    FFT jest to szybsza wersja DFT, ponieważ redukuje liczbę mnożeń zespolonych.

    1.Najpierw muszę "przemieszać" próbki sygnału wejściowego w buforze, czyli te tzw motylki.
    Algorytm znam, wystarczy tylko wykonać odbicie lustrzane bitów indeksu tablicy.
    A więc dla 8 punktowej transformaty kolejność próbek w buforze po przemieszaniu ma być:
    0
    4
    2
    6
    1
    5
    3
    7

    Dalej:
    Teraz muszę wykonać N/2 dwupunktowych DFT.
    I teraz czy dobrze rozumuję?
    Dwupunktowe DFT mają być wykonane kolejno w tym przypadku dla próbek:
    a-> (0,4)
    b-> (2,6)
    c-> (1,5)
    d-> (3,7)

    i teraz z każdej tej pary otrzymam po 2 wartości zespolone tak?
    Czyli w sumie 4 wartości, 2 rzeczywiste i 2 urojone?

    W języku C nie mogę zapisywać liczb urojonych tak jak w matlabie a więc muszę to zrealizować programowo w postaci 2 buforów, jeden na część wartość rzeczywistą a drugi na urojoną lub poprzez jeden bufor(tablicę) dwuwymiarową.

    Załóżmy że mam osobne bufory:
    real_x[N];
    imag_x[N];

    I teraz moje pytanie, jak wpisać wyniki tych czterech dwupunktowych DFT do tych buforów?

    Dla DFT->a
    real_x(0)=real1; imag_x(0)=imag1;
    real_x(1)=real2; imag_x(1)=imag2;

    Dla DFT->b
    real_x(2)=real1; imag_x(2)=imag1;
    real_x(3)=real2; imag_x(3)=imag2;

    Dla DFT->c
    real_x(4)=real1; imag_x(4)=imag1;
    real_x(5)=real2; imag_x(5)=imag2;

    Dla DFT->d
    real_x(6)=real1; imag_x(6)=imag1;
    real_x(7)=real2; imag_x(7)=imag2;

    W taki sposób?

    Ok, jeśli tak to mam teraz 2 bufory 8 elementowe z kolejno ułożonymi wynikami 4 kolejnych dwupunktowych DFT.

    Mam widma, ale teraz muszę je połączyć w jedno widmo.

    Jest algorytm:
    Jak napisać uniwersalną funkcję FFT w C dla różnych mikrokontrolerów?
    Ale tego już właśnie chyba nie do końca rozumiem;
    Znowu zamiana miejsc, ok, da się zrobić, nie ma problemu.
    Ale na niektórych strzałkach widać tu -1 albo np Wn² itd.
    Są to jakieś wpsółczynniki przez które mam mnożyć te próbki na tych odpowiednich im przejściach?

    Jeśli już potem połączę widma w jedno widmo, otrzymam 2 bufory z wartościami rzeczywistymi i urojonymi.

    Potem tylko zrobić z tego moduł, czyli w pętli:

    buff[i]=sqrt(real_x(i)^2 + imag_x(i)^2)

    ??

    Pokazałem tu pewien algorytm, jak ja to ruzumuję.
    Chciałbym, aby mi ktoś odpowiedział czy dobrze myślę i ewentualnie jeśli się mylę to gdzie.
  • REKLAMA
  • #2 10686850
    fantom
    Poziom 31  
    Wedlug tego co ja rozumiem to dla przykladu 8 punktowego liczycz dwie transformaty 4 punktowe a nastepnie "wymieniasz" sie wpolczynnikami w ostatniej fazie syntezy czyli 1 element widma powstanie z 1 elementu 1 transformaty plus 1 element 2 transformaty i jednoczesnie 5 element widma powstanie z 1 elementu 1 transformaty minus 1 element 2 transformaty (stad te minusy). Poniewaz wymieniasz sie wspolczynnikami nie musisz ich wyliczac dla kazdego elementu (mniej mnozen). Ale nie wiem czy z kolei ja dobrze rozumuje bo nigdy tego nie robilem.

    Jak napisać uniwersalną funkcję FFT w C dla różnych mikrokontrolerów?
  • REKLAMA
  • #3 10754761
    przemekbary
    Poziom 16  
    Witam
    1) W książce Lyonsa "Wstęp do cyfrowego przetwarzania sygnałów" jest chyba przykład implementacji. Dodatkowo DFT motylkowa jest dokładnie opisana
    2) W książce Tadeusiewicza jest dokładne wyprowadzenie i uzasadnienie
  • REKLAMA
  • #4 10758713
    jarekz_2
    Poziom 16  
    przemekbary napisał:
    (...)W książce Lyonsa "Wstęp do cyfrowego przetwarzania sygnałów" jest chyba przykład implementacji. Dodatkowo DFT motylkowa jest dokładnie opisana(...)
    Ja również gorąco polecam tę książkę. Dyskretne Przekształcenie Fouriera, w szczególności FFT, jest tam opisane bardzo wyczerpująco, z wieloma przykładami.
  • #5 10794107
    gaskoin
    Poziom 38  
    Zacznijmy od początku

    drzasiek napisał:
    Korzystam z książki prof. Tomasza Zielińskiego "Cyfrowe przetwarzanie sygnałów ..."


    Jest beznadziejna :) Weź coś porządnego jak koledzy radzą Lyonsa albo (moja ulubiona) S. Smith


    drzasiek napisał:
    FFT jest to szybsza wersja DFT, ponieważ redukuje liczbę mnożeń zespolonych.


    To nie jest wersja DFT, FFT to jest algorytm policzenia DFT.

    drzasiek napisał:

    Teraz muszę wykonać N/2 dwupunktowych DFT.
    I teraz czy dobrze rozumuję?
    Dwupunktowe DFT mają być wykonane kolejno w tym przypadku dla próbek:
    a-> (0,4)
    b-> (2,6)
    c-> (1,5)
    d-> (3,7)

    i teraz z każdej tej pary otrzymam po 2 wartości zespolone tak?


    To już zależy od algorytmu FFT, podstawą jest jednak jednopunktowe DFT(dla każdego punktu dziedziny czasu liczy się je osobno - dla 8 próbek będziesz miał 8 widm). Jeśli liczysz rzeczywiste FFT to już inna bajka :) Są też 4 punktowe FFT, i o które Ci chodzi ?

    drzasiek napisał:

    W języku C nie mogę zapisywać liczb urojonych tak jak w matlabie


    Można utworzyć strukturę, która odzwierciedla liczbę zespoloną + zespół funkcji, które operują na liczbach zespolonych, znacznie skraca to zapis FFT (dodawanie odejmowanie mnożenie dzielenie ABS itd)

    drzasiek napisał:

    Załóżmy że mam osobne bufory:
    real_x[N];
    imag_x[N];

    I teraz moje pytanie, jak wpisać wyniki tych czterech dwupunktowych DFT do tych buforów?


    Generalnie widma trzeba połączyć w kolejności odwrotnej do tej, która była przy rozkładzie w dziedzinie czasu. Jest to trochę problem więc trzeba się cofać etap po etapie, tzn z 8 widm (8, 4 lub 2 w zależności od algorytmu) 1 punktowych robimy 4, z 4 widm 2 punktowych robimy 2, z 2 widm 4 punktowych robimy finalnie jedno widmo 8 punktowe :)

    drzasiek napisał:

    Potem tylko zrobić z tego moduł, czyli w pętli:

    buff[i]=sqrt(real_x(i)^2 + imag_x(i)^2)


    DFT to już będzie to co masz w tablicy. Ty mówisz o PSD, które liczy się tak:

    $$\frac{\sqrt{Re^2 + Im^2}}{2 \pi}$$

    Trzeba też pamiętać o tym, że próbki MUSZĄ być znormalizowane (można to zrobić przed lub po obliczeniu widma) bo inaczej widmo będzie miało rzędy wartości zależnych od ilości próbek z jakich będziesz je liczył (czyli będzie nieprawdziwe).
REKLAMA