logo elektroda
logo elektroda
X
logo elektroda
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.
  • #1 1926448
    elwiz
    Poziom 12  
    Witam.
    Jestem poczatkujacym programista w dziedzinie DSP wiec moje pytanie moze wydac sie dla niektorych banalne ale prosze o wyrozumialosc i pomoc.
    Korzystam z algorytmu Goertzela do detekcji kodow DTMF. Niestety algorytm zwraca mi bardzo dziwne wyniki.
    Wykonalem prosty test: Wygenerowalem prosty sygnal sinusoidalny o okreslonej czestotliwosci. Przepuscilem ten sygnal przez algorytm Goertzela wykrywajac kolejne czestotliwosci. Wykonalem ten test dla roznych czestotliwosci sygnalu wejsciowego.
    Algorytm prawidlowo pokazuje najwieksza wartosc dla czestotliwosci najblizszej czestotliwosci sygnalu wejsciowego ale wartosc ta jest dla mnie calkowicie niezrozumiala. Wynik ten zmienia sie w zaleznosci od ilosci badanych probek i co gorsza od czestotliwosci sygnalu wejsciowego. Nie mam zielonego pojecia jak przeliczyc wynik algorytmu Goertzela na rzeczywista amplitude.
    Dla lepszego zrozumienia problemu podam wam kilka przyklaodwych danych liczbowych: Przy probkowaniu z czestotliwoscia 8kHz i amplitudzie rownej 1000 testowalem czestotliwosci sygnalu wejsciowego od 40Hz do 4kHz ze skokiem 1. Nastepnie sprawdzalem wynik algorytmu dla kazdej z tych czestotliwosci.
    Przy ilosci probek rownej 1000 uzyskalem nastepujacy taki wynik (fragment):
    f -> wynik
    ---------------
    40 -> 500028
    41 -> 482863
    42 -> 449923
    43 -> 401914
    44 -> 333461
    45 -> 245575
    46 -> 150786
    47 -> 65923
    48 -> 500000
    49 -> 483563
    50 -> 449935
    51 -> 400252
    52 -> 331041
    53 -> 243961
    54 -> 150679
    55 -> 66502
    56 -> 500005
    57 -> 484070
    58 -> 449868
    59 -> 399067
    60 -> 329283
    61 -> 242799
    62 -> 150629
    63 -> 66934

    Po zwiekszeniu ilosci probek do 2000 uzyskalem juz:
    f -> wynik
    ---------------
    40 -> 1000057
    41 -> 900017
    42 -> 652131
    43 -> 300661
    44 -> 1000000
    45 -> 900025
    46 -> 650753
    47 -> 300631
    48 -> 1000000
    49 -> 899995
    50 -> 649669
    51 -> 300608
    52 -> 1000000
    53 -> 899992
    54 -> 648622
    55 -> 300590

    Juz na pierwszy rzut oka widac ze wyniki powtarzaja sie ale okres jest zalezny od ilosci probek. Obawiam sie ze moze byc wiecej czynnikow wplywajacych na wynik algorytmu Goertzela. Nie wiem juz jak stwierdzic jak ten wynik odzwierciedla oryginalna amplitude. Pomozcie prosze.

    ...:: ElwiZ ::...
  • #2 1934153
    vadkudr
    Poziom 12  
    Algorytm Goertzela moze byc interpretovany jak filtracja wejscjowego sygnala filtrem z impulsowej charakterystykoj h(k)=sin(w*k). Taki filtr jest rezonatorzem.

    To znachy, ze:
    1. Na wyiscju jest taksamo sinusoidalny sygnal.
    2. Magnitude tego sygnala postepowe sie powekszaje.

    Z tych dwuch twierdzen' oczywiesce, ze
    1. Pan musze zwraczac' uwage tylko na magnitude wyjsciowego sygnalu. Nie fakt, ze 1000 probka maje magnitudove znaczenie.
    2. Na 2000 probke magnituda sygnala bedzie dwukrat wyszej niz na 1000 probke.

    Jeszcze dodam, ze magnituda wyjsciowego sygnala sie powekszaje w zalezhnoscie od czestotliwosci. Zakon jest neliniowy. W tej chwili ego nie wiem. Ale w praktyke pan mozhe skompensowac' to po rezultatam wymerzien'.
  • #3 1934312
    elwiz
    Poziom 12  
    Udalo mi sie znalezc maly drobiazg ktory duzo mi wyjasnil. Wynik algorytmu jest rowny A*N/2 gdzie A to amplituda sygnalu wejsciowego a N to ilosc probek. Po uwzglednieniu tej zaleznosci wszystko dziala i to bardzo poprawnie ale niestety tylko w sytuacji gdy N jest rowne czestotliwosci probkowania. Przy mniejszej probce wyniki zaczynaja sie dyrastycznie zmieniac. Oczywiscie N po zmianie jest wciaz wieksze od podwojonej czestotliwosci szukanej. Nie potrafie wykluczyc jednak calkowicie mozliwosci ze jest to blad w moim rozumowaniu lub jakas wredna pomylka w kodzie. Jesli ktos z Was kiedykolwiek korzystal z algorytmu Goertzela to prosze o pomoc.

    PS: Jesli ktos jest zainteresowany kodem ktory stworzylem w pocie czola :) lub algorytmem z ktorego korzystalem to prosze o kontakt. Vadkudr nie zrozum mnie zle ale widze ze nie jestes z Polski i masz troche problemow z jezykiem polskim wiec jezeli wolalbys pisac po angielsku to prosze bardzo.

    ...:: by ElwiZ ::...
  • #4 2087644
    elwiz
    Poziom 12  
    Witam.

    Ponieważ ostatnio dostałem pytanie mailem co wiem na temat algorytmu Goertzela to postaram się streścić wszystko co najważniejsze co dowiedziałem się o nim w ostatnim czasie. Chciałbym jednak podkreślić że moja wiedza teoretyczna w zakresie przetwarzania sygnałów jest znikoma a wszystko co napiszę jest efektem badań naukowych znaną metodą "prób i błędów". Bardzo możliwe że wiedza jaką posiadam na temat algorytmu Goertzela jest błędna. Jeśli ktoś wie coś więcej ode mnie to zapraszam do dyskusji.
    Zacznijmy od początku. Algorytm Goertzela jest formą wybiórczej transformaty Fouriera. Pozwala na określenie wielkości części sygnału w pewnym przedziale częstotliwości. Podstawowy algorytm Goertzela można zapisać następująco:

    int k = (int)(0.5+N*f/FP);
    double omega   = 2*PI*k/N;
    double sinus   = sin(omega);
    double cosinus = cos(omega);
    double coeff   = 2*cosinus;
    
    double Q0 = 0;
    double Q1 = 0;
    double Q2 = 0;
    
    for (int i=0;i<N;i++) {
    	Q0 = coeff*Q1-Q2+blok[i];
    	Q2 = Q1;
    	Q1 = Q0;
    }
    double wynik = sqrt(Q1*Q1+Q2*Q2-Q1*Q2*coeff);
    
    
    Gdzie: N - ilość próbek, f - badana częstotliwość, FP - częstotliwość próbkowania, blok[] - tablica próbek sygnału. Proszę nie wypominać mi ewentualnych błędów składni ponieważ jest to fragment programu napisanego w Javie okrojonego z klas dla zyskania na przejrzystości.
    Niestety taka forma tego algorytmu ma wiele wad. Wynik algorytmu jest zależny od częstotliwości sygnału wejściowego oraz od ilości próbek.
    Oto kilka przykładów:
    1. Jeżeli wygenerujemy 2 sygnały harmoniczne o tej samej amplitudzie a różnych częstotliwościach to algorytm Goertzela przy ich poszukiwaniu da w wyniku dwie bardzo różne wartości.
    2. Dla tego samego sygnału wynik algorytmu dla zestawu 2*N próbek będzie dwa razy większy niż dla zestawu N próbek.
    Specjalnie pisałem na początku o "wielkości sygnału" gdyż wartość ta nie jest w żaden sposób proporcjonalna do amplitudy sygnału wejściowego lub jego wartości chwilowej. Można wprowadzić kilka modyfikacji które pozwolą na zbliżenie wyniku algorytmu Goertzela do amplitudy sygnału wejściowego. Aby w pewnym stopniu uniezależnić wynik od ilości analizowanych próbek należy pomnożyć go przez 2/N.
    Niestety nadal dla dwóch różnych wartości N wynik będzie różny.
    Wykonałem prosty test. Wygenerowałem wielokrotnie prosty sygnał sinusoidalny o kolejnych częstotliwościach a wynik rejestrowałem na wykresie. Okazało się że zmieniając częstotliwość sygnału wejściowego wynik algorytmu zmienia się cyklicznie rosnąc do amplitudy sygnału wejściowego a następnie malał. Zależność ta była bardzo podobna do |sin|. Niestety okres tej zależności jest zależny od N a więc wyznaczenie jej w matematyczny sposób przekraczało moje możliwości. Gdyby komuś się to udało możnaby określić zależność wyniku algorytmu Goertzela od amplitudy sygnału wejściowego a więc wyznaczyć w końcu tę amplitudę dla sygnału badanego.
    Jedyne co ja w tej sytuacji zrobiłem to wyznaczyłem na podstawie sygnału testowego mnożnik dla konkretnej częstotliwości f i ilości próbek N tak by wynik algorytmu był proporcjonalny do amplitudy sygnału wejściowego.
    Wiem że nie jest to wiele ale nic lepszego nie udało mi się znaleźć. Ponawiam więc prośbę: Jeżeli wiecie coś więcej to piszcie.

    Oto linki do stron z których korzystałem:
    http://www.embedded.com/story/OEG20020819S0057
    http://www.musicdsp.org/archive.php?classid=2#107
    http://en.wikipedia.org/wiki/Goertzel_algorithm

    ...:: by ElwiZ ::...
  • #5 2704429
    konyou
    Poziom 2  
    Witam, udalo Ci sie moze cos wiecej dowiedziec na temat wlasciwosci tego algorytmu? Mam wlasnie zadanie do zrobienia: porownanie go z fft Octave'a... Myslalem ze bedzie latwo, ale strasznie dziwne wyniki wychodza. Moja wiedza z DSP jest minimalna wiec za duzo nie jestem w stanie powiedziec o wynikach dzialania tego algorytmu...
  • #6 2704703
    Konto nie istnieje
    Konto nie istnieje  
  • #7 2779730
    teorom
    Poziom 13  
    Kurcze kiedys napisalem taki algorytm na tsm320. Jak znajde materialy (a mialem tego troche) to chetnie podrzuce.
    Oczywiscie musza byc spelnione wszystkie wymagania odnosnie
    cyfrowego przetwarzania sygnalow, filtracja, normalizacja.
  • #8 2786178
    qrdel
    Poziom 28  
    Od czasu jak ktoś (nie pamiętam, ale bardzo dziękuję) uświadomił mi istnienie algorytmu Goertzla zawsze pisałem go sam na piechotę, no i wyglądał znacząco inaczej niż to co prezentujecie.
    Dopiero link http://www.embedded.com/story/OEG20020819S0057 uświadomił mi o co biega.
    To jest zoptymalizowana wersja algorytmu (pod względem obliczeniowym).
    Idea algorytmu to policzenie całki sygnał(t)*sin(2*pi*f*t) po wybranym okresie, tyle że w dziedzinie liczb zespolonych i w dosyć chytry sposób.
    Łatwo widać, że całka jest zależna od długości przedziału całkowania, że zależy od fazy sygnału, zależy też od amplitudy sygnału.
    Ale dla sygnału A*sin(2*pi*f*t+faza) moduł (zespolony) całki jest z dokładnością do stałej równy A*przedział.
    Sztuczka polega na tym że do całki dodajemy kolejne próbki (zwykle rzeczywiste, składowa urojona - zerowa) a wynik obracamy (na płaszczyźnie Re*Im) o kąt wynikający z kroku próbkowania i badanej częstotliwości; czyli mnożymy przez macierz zespoloną (cos, sin, -sin, cos) {oczywiście kwadratową, 2*2 macierz obrotu; z argumentem 2*pi*f*dt }.
    Teraz można już czytać link który cytowałem powyżej.
    Algorytm G. ma kilka istotnych zalet i dlatego jest chętnie stosowany w prostych zadaniach detekcji znanych tonów jak DTMF lub podobne kodowe sygnały dźwiękowe w kanale fonicznym.
    Na życzenie mogę spróbować wyliczyć zalety.
REKLAMA