Goertzeli algoritm

Autovoni klahvistikel kasutati 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 reaalarvulist koefitsienti, kasutades reaalarvulistel sisenditel reaalarvulist aritmeetikat. Goertzeli algoritmi saab kasutada ka tagurpidi (sinusoidi sünteesimiseks), kusjuures iga sämpli arvutamiseks tuleb teha üks korrutus- ning üks lahutamistehe. Lisaks ei pea Goertzeli algoritmis kasutatav akna suurus olema arvu 2 aste (erinevalt DFT-st) ning algoritm ei vaja nii palju mälu, kui DFT. Kuigi Goertzeli algoritm on kiirem, kui DFT, ei ole selle arvutamine oluliselt keerulisem ning tulemuse saamiseks on vaja teha vaid mõned arvutustehted. Samas ei ole Goertzeli algoritmi tulemus keerulisemate signaalide puhul nii täpne, kui DFT-l, seega tuleks mõnedel juhtudel (kui täpsus on olulisem kui kiirus) eelistada siiski DFT-d.

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. Kuna Goertzeli algoritm on optimeeritud väikeste sagedusvahemike jaoks, ei ole seda mõistlik kasutada kogu spektri uurimiseks. On olemas ka Goertzeli algoritmi optimeeritud versioon, mis on veelgi efektiivsem, kuid ei anna nii täpseid tulemusi. Goertzeli algoritmi kasutatakse näiteks helitöötluses üksiku tooni tuvastamiseks, energeetikas signaalide analüüsimiseks ning arhitektuuris hoonete struktuurikahjustuste tuvastamiseks.

Algoritm

Goertzeli algoritmi rakendamiseks on vaja kaht hulka: sisendandmete hulk X ning tulemuste hulk Y. Iga elemendi arvutamiseks tuleb kasutada kaht eelnevat tulemust ning üht eelnevalt välja arvutatud koosinust. Algoritmi üldine matemaatiline kuju:

$Y(z)=(1-e^{-j*2*\pi *k/N}*z^{-1})/(1-\cos(2*\pi *k/N)*z^{-1}+z^{-2})$, kus $Y$ on tulemuste hulk, $z$ on vaadeldava sageduse indeks, $z^{-1}$ on eelmine element ning $z^{-2}$ üle-eelmine element hulgas $Y$. Ülejäänud muutujad on täpsemalt kirjeldatud allpool.

Enne Goertzeli algoritmi kasutamist tuleb teha järgnevad sammud:

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

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$

Seejärel saab rakendada Goertzeli algoritmi, kasutades sisendandmete hulka X ning väljundandmete hulka Y (n-ndal kohal asuv element vastavalt x[n] või y[n]). Esimese kahe väärtuse arvutamiseks tuleb y[n-1] ja y[n-2] väärtustada nulliga.

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

$y[n]=2*\cos(W)*y[n-1]-y[n-2]+x[n]$, kus $x[n]$ on vaadeldav sämpel

$y[n-2]=y[n-1]$

$y[n-1]=y[n]$

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

$real=(y[N-1]-y[N-2]*\cos(W))$

$imag=(y[N-2]*\sin(W))$

Selleks et leida magnituudi väärtust, võtame ruutjuure reaalosa ja imaginaarosa ruutude summast:

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

Optimeeritud Goertzeli algoritm

Optimeeritud 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:

$magnituud={\sqrt {(y[N-1])^{2}+(y[N-2])^{2}-y[N-1]*y[N-2]*2*\cos(W)}}$

Kusjuures sämplite töötlemine toimub samamoodi, nagu tavalises Goertzeli algoritmis. Algoritmi optimeeritud versioon on rohkem levinud, kuna see on efektiivsem.