Kasutaja:Konnula/liivakast

Autovoni klahvistikud kasutasid DTFM-signaali, mille tuvastamiseks saab kasutada Goertzeli algoritmi.

Goertzeli algoritmi (ka Goertzeli filter, inglise keeles Goertzel algorithm) kasutatakse digitaalses signaalitöötluses (DSP) diskreetse Fourier' pöörde (DFT) üksikute komponentide tõhusaks määramiseks. Algoritmi leiutas Gerald Goertzel aastal 1958 ning seda algoritmi kasutatakse näiteks multisageduslikul kakstoonvalimisel.

Goertzeli algoritm analüüsib üksikut sageduskomponenti digitaalsignaalist, kuid erinevalt tavalisest DFT arvutusest, rakendab Goertzeli algoritm igal iteratsioonil üht realarvulist koefitsienti, kasutades realarvulistel sisenditel realarvulist aritmeetikat. Täieliku spektri katmisel (diskreetse sisendandmete hulga korral) on Goertzeli algoritmi keerukus suurem, kui Fourier' kiirteisendusel (FFT), kuid väikese arvu sageduskomponentide arvutamisel on see efektiivsem, kui FFT - seetõttu ei vaja algoritmi kasutamine suurt arvutusvõimsust. Goertzeli algoritmi saab kasutada ka tagurpidi (sinusoidi sünteesimiseks), kusjuures iga sämpli arvutamiseks tuleb teha üks korrutus- ning üks lahutamistehe. On olemas ka Goertzeli algoritmi optimiseeritud versioon, mis on veelgi efektiivsem, kuid ei anna nii täpseid tulemusi.

Algoritm

Enne Goertzeli algoritmi kasutamist tuleb teha järgnevad sammud:

1. Valida diskreetimissagedus (inglise keeles Sample rate);
2. Valida ploki suurus N.

Diskreetimissagedus määratakse enamasti rakenduse järgi (näiteks helisignaali puhul kasutatakse tavaliselt 44.1 kHz sagedust ehk diskreeditakse signaali 44100 korda sekundis), kuid seda saab leida ka näiteks Nyquisti teoreemi abil, mille alusel peab diskreetimissagedus olema vähemalt kaks korda suurem sisendsignaali suurimast sagedusest. Ploki suuruse valimisel tuleb arvestada, et mida suurem on N, seda suurem on sageduse resolutsioon, kuid seda pikem on algoritmi tööks kuluv aeg.

Lisaks tuleb arvutada välja järgnevad konstandid:

$k=(0.5+{\frac {N*f}{diskreetimissagedus}})$, kus $f$ on otsitav sagedus (inglise keeles target frequency)

$w=(2*\pi /N)*k$

$koosinus=\cos(w)$

$siinus=sin(w)$

$koef=2*koosinus$

Seejärel saab rakendada Goertzeli algoritmi, kasutades kolme muutujat: $Q_{0}$,$Q_{1}$ ja $Q_{2}$, millest $Q_{0}$ on hetkeväärtus, $Q_{1}$ eelmine ja $Q_{2}$ üle-eelmine väärtus. Muutujad $Q_{1}$ ja $Q_{2}$ tuleb algväärtustada nulliga iga andmeploki alguses.

Iga sämpli peal tuleb teostada järgnevad tehted:

$Q_{0}=koef*Q_{1}-Q_{2}+sample$, kus $sample$ on vaadeldav sämpel

$Q_{2}=Q_{1}$

$Q_{1}=Q_{0}$

Pärast tehete teostamist igal N sämplil, saame muutujate lõppväärtusi kasutades leida sagedusploki magnituudi kompleksarvuna:

$real=(Q_{1}-Q_{2}*koosinus)$, kus $koosinus$ on eelnevalt arvutatud koosinuse väärtus ning $real$ on arvutatava kompleksarvu reaalosa.

$imag=(Q_{2}*siinus)$, kus $siinus$ on eelnevalt arvutatud siinuse väärtus ning $imag$ on arvutatava kompleksarvu imaginaarosa.

Seejärel saame leida magnituudi reaalarvulise väärtuse, kasutades järgnevat valemit:

$magnituud^{2}=real^{2}+imag^{2}$

Oluline on enne järgmise sagedusploki juurde suundumist muuta muutujate $Q_{1}$ ja $Q_{2}$ väärtused uuesti nulliks.

Optimiseeritud Goertzeli algoritm

Optimiseeritud Goertzeli algoritm erineb tavalisest Goertzeli algoritmist vaid selle poolest, et algoritmi viimases faasis ei arvutata välja magnituudi reaal- ja imaginaarosa, vaid leitakse magnituud järgneva valemi abil:

$magnitude^{2}=(Q_{1})^{2}+(Q_{2})^{2}-Q_{1}*Q_{2}*koef$

Konstantide arvutamine ning sämplite töötlemine toimub samamoodi, nagu tavalises Goertzeli algoritmis. Algoritmi optimiseeritud versioon on rohkem levinud, kuna see on efektiivsem.